北工大-操作系统-作业合集

第⼋次作业基础作业

1.假设⼀个磁盘驱动器有5000个柱⾯，从0到4999。驱动器正在为143的⼀个请求服务，且前⾯的⼀个请求在125。按照FIFO的顺序，即将到来的请86，1470，913，1774，948，1509，1022，1750，130。请按照FCFS、SSTF、SCAN、LOOK、C-SCAN、C-LOOK，要满⾜队列中的服务要求磁头总的移动距离是多少。143 86 1470 913 1774 948 1509 1022 1750 130

a. FCFS : 143, 86, 1470, 913, 1774, 948, 1509, 1022, 1750, 130.总寻道距离7081.

b. SSTF : 143, 130, 86, 913, 948, 1022, 1470, 1509, 1750, 1774.总寻道距离1745.

c. SCAN ：143, 913, 948, 1022, 1470, 1509, 1750, 1774, 4999, 130, 86.总寻道距离9769.

d.LOOK:143, 913, 948, 1022, 1470, 1509, 1750, 1774, 130, 86.总寻道距离3319.

e. C-SCAN : 143, 913, 948, 1022, 1470, 1509, 1750, 1774, 4999, 0, 86, 130.总寻道距离9813

f. C-LOOK : 143, 913, 948, 1022, 1470, 1509, 1750, 1774, 86, 130.总寻道距离3363.

2. 为什么⽂件分配的位图必须保存在⼤容量存储器中，⽽不是主存中？

答：因为如果保存在存中，当系统崩溃时，这些空闲区间的信息将会被丢失，⽽如果保存在⼤容量存储器中就可以解决这个问题。

3．假设要为⼀个⽂件换⼀个名字。⼀种选择是使⽤操作系统提供的RENAME⽅法，另⼀种⽅法是：把⽂件复制为新⽂件，然后删除原来的⽂件以实现重命名。请问，这两种⽅法在实现上有什么不同？

答：RENAME⽅法是修改⽬录⽂件的⽂件名部分，⽽删除原来⽂件再重命名则需要再创⽴⼀个新⽂件，⽬录⽂件中增加⼀项，分配新空间；删除⽬录⽂件中的⽂件项⽬，然后回收占⽤的空间。4．请解释使⽤索引节点有什么好处

答：减⼩⽬录⽂件的⼤⼩，提⾼查找⽂件的效率

5．在UNIX 中open 系统调⽤绝对需要么？如果没有会产⽣什么结果。

答：如果没有open 命令，那么每个read 命令都需要确定要打开的⽂件名。系统必须找到⽂件的i 节点，虽然这个数据放⼊cache 可以减少⼀些时间，但是当数据变化的时候，i 节点的数据需要刷新到磁盘上。

6．UNIX 系统中有关盘块的分配与释放是借助超级块中的栈来进⾏的。假如某个时刻系统状况如下图所⽰，若此时某个进程要删除⽂件A ，并归还它所占⽤的盘块220，110，645，549，176。请说明过程，并给出删除完毕后有关数据及表⽬的更改情况。

100 199 786 278 …80 230 110 6452 549 176 …

7. 考虑⼀个索引节点所表⽰的UNIX⽂件的组织。假设有12个直接块指针，在每个索引节点中有⼀个单重、双重和三重间接指针。此外，假设系统块⼤⼩和磁盘扇区⼤⼩都是8K，如果磁盘块指针是32位，其中8位表⽰物理磁盘，24位表⽰物理块，那么

a.该系统⽀持的最⼤⽂件⼤⼩是多少？b.该系统⽀持的最⼤⽂件分区是多少？

c.假设主存中除了⽂件索引节点外没有其他信息，访问在位置12423956中的字节需要多少磁盘访问？答：

a.通过⽤块⼤⼩除以指针⼤⼩得到盘块指针的数⽬：每块8K/4 = 2K

这样I节点可以⽀持的最⼤⽂件容量是:

12+2k+2k*2k+2k*2k*2k=(12+2K+4M+8G)*8K(块⼤⼩)= 96KB + 16MB + 32GB + 64TB直接寻址⼀级间接寻址⼆级间接寻址三级间接寻址b.在⼀个分区中识别⼀个块需要24位。所以:*8K =16M*8K=128GB

c.使⽤从(a)得到的信息, 发现直接块只能表⽰96KB, ⽽⼀次间接块表⽰16MB. 题⽬中要求的请求位置在13M 左右，使⽤⼀次间接块.就可以了。所以要⽤两次磁盘访问，⼀次访问⼀次间接块，另⼀次访问包含数据的盘块第七次作业

1．什么是设备⽆关性？

应⽤程序只按套路调⽤操作系统提供的功能即可，不关⼼实际的设备是什么，这就是与设备⽆关性2．以下各项⼯作由I/O软件的哪⼀层完成？

a.为⼀个磁盘读操作计算磁道、扇区、磁头；设备驱动程序b.向设备寄存器写命令；中断处理程序c.检查⽤户是否允许使⽤设备；设备独⽴性软件d.将⼆进制整数转换成ASCII码以便打印硬件

3．为什么在要打印的⽂件通常都假脱机输出到磁盘上？

答：达到缓冲的⽬的，实现提⾼I/O设备性能的⽬的。为了打印⼀个⽂件，⼀个进程⾸先要⽣成需要打印的整个⽂件并把它放在假脱机⽬录⾥。由守护进程打印该⽬录下的⽂件，该进程是允许使⽤打印机设备⽂件的唯⼀进程。通过保护设备⽂件来防⽌⽤户直接使⽤，可以解决某些进程不必要地长期空占打印机的问题。第六次作业

1．假设页表在存保存的分页系统，

a.如果⼀次访问存⽤200ns，那么访问⼀个页的⼀次数据访问⽤多少时间？b.如果加⼊TLB，有75%的命中率，那么存有效访问时间是多少？

a)访问⼀个页数据需要访问两次存，第⼀次访问存中的页表，第⼆次根据页表中的信息形成的物理地址访问存访问数据，所以要⽤200*2=400ns

b)加⼊TLB，获得物理地址的过程为：先在TLB中查找，如果TLB中命中，则直接获得物理地址，如果TLB中不存在，则去访问页表，所以需要的访问时间为0.25*200=50ns总共需要的时间为50ns+200ns=250ns

2.在⼀个虚拟存储管理系统中采⽤页式⽅法对存空间进⾏管理，它有24位的虚拟地址空间，⽽实际的物理地址空间是16位，页框⼤⼩为2k。假设有两个进程A和B。其中A进程的0、2页已经调⼊到存的2、3号页框；B进程的1、3页已经调⼊到存的7、8号页框。请问：A进程的虚拟地址12FF可以转换成什么物理地址？B进程的虚拟地址17BA可以转换成什么物理地址？如果不能转换，操作系统会执⾏什么操作？页框⼤⼩为2k=2^11,有11位的位移。

A进程：12FF=0001 0010 1111 1111 ,00010=2,A进程中2页调进3号框，因此物理地址为：0001 1010 1111 1111B进程：17BA=0001 0111 1011 1010，在进程2中没有2号页，需要的页⾯不在存时，请求调⼊所需的页⾯判断对错

如果缺页率太⾼，通常说明⼀个进程分得的页框太多了。X第五次作业基础作业

1．部碎⽚与外部碎⽚之间的区别？

部碎⽚：存分页时，最后⼀页未装满的部分就是部碎⽚。或因调⼊的数据⼩于分区⽽产⽣分区空间的浪费，称为部碎⽚。外部碎⽚：共享时要分段，在段的换⼊换出时未使⽤的部分就是外部碎⽚。⼀开始运⾏得很好，但是在执⾏⼀段时间后,会出现⼀些⼩的洞。这种在分区外的洞称为外部碎⽚。存按顺序有100k，500k，200k，300k，600k，⽤⾸次适应、最佳适应和最差适应如何放置212k，417k，112k，426k的进程？

⾸次适应：212k分配给500k，417k分配给600k，112k分配给200k，426k没有可分配

最佳适应：⾸先将212k分配给300k，将417k分配给500k，将112k分配给200k，将426k分配给600k；最差适应：将212k分配给600k，将417分配给500k，将112分配给300k，最后426没有可分配的。

2．假设⼀个有8个1k页⾯的逻辑地址空间，映射到⼀个32个页框的物理存，问：逻辑地址多少位？物理地址多少位？逻辑地址：13位物理地址：15位4．（8.12）有段表段基地址长度0 219 6001 2300 142 90 1003 1327 5804 1952 96

下⾯的物理地址是多少？

a)0,430; b)1,10; c)2,500; d)3,400; e)4,122a、649b、2310c、590d、1727e、2074

5．在页⾯⼤⼩为4k的系统中，根据图中所⽰

页表，下⾯的逻辑地址经过重定位之后的物理地址是什么？a)20; b)4100; c)8300

A、49172 b、53252 c、61548

6．⼀台计算机为每个进程提供65536字节的地址空间，页⾯的⼤⼩为4k。⼀个程序有32768字节的正⽂，16386字节的数据，15870字节的堆栈，此程序是否能装⼊此地址空间？若页⾯⼤⼩为512字节呢？4k不能，512字节可以；

解析过程：65536/4096=16，共计16个页⾯；正⽂需要页⾯：32768/4096=8数据需要页⾯：16386/4096=5对战需要：15870/4096=4共需17个页⾯，所以不能装⼊512字节同理可得正好能够装⼊补充作业判断对错

编译时绑定是⼤多数通⽤操作系统使⽤的地址绑定⽅法。 X最佳适配法可以在存分配过程中留下最⼩的洞。√

为解决存分配时导致的外部碎⽚可以采⽤压缩的⽅法来解决，因此需要在地址绑定的时候采⽤静态重定位⽅法。 X如果现在基地址寄存器的值是1200，界限寄存器的值是350，那么当前进程产⽣对绝对地址1551的访问是合法的。 X可重⼊代码不可以被共享。 X基础作业

1．考虑下⾯⼀组进程，进程占⽤的CPU区间长度以毫秒计算。假设在0时刻进程以P1, P2, P3, P4, P5的顺序到达。进程区间时间优先级P1 10 3P2 1 1P3 2 3P4 1 4P5 5 2

（1）画出4个Gantt图，分别演⽰使⽤FCFS, SJF, ⾮抢占优先级（数字越⼩表⽰优先级越⾼）和RR（时间⽚=1）算法调度时进程的执⾏过程。

（2）每个进程的周转时间是多少？

（3）每个进程在每种调度算法下的等待时间是多少？解：（1）GANTT图FCFS：P1 P2 P3 P4 P5SJF：P2 P4 P3 P5 P1

⾮抢占优先级：P2 P5 P1 P3 P4

RR：P1 P2 P3 P4 P5 P1 P3 P5 P1 P5 P1 P5 P1 P5 P1 (2)周转时间：

(3)等待时间：

2．考虑下⾯⼀个系统在某⼀个时刻的状态。Allocation Max AvailableA B C D A B C D A B C DP0 0 0 1 2 0 0 1 2 1 5 2 0P1 1 0 0 0 1 7 5 0P2 1 3 5 4 2 3 5 6P3 0 6 3 2 0 6 5 2P4 0 0 1 4 0 6 5 6

使⽤银⾏家算法回答下⾯的问题：（1）Need矩阵的容（2）系统是否处于安全状态

（3）如果从进程P1发来⼀个请求（0，4，2，0），这个请否可以⽴即满⾜？解：

（1）Need矩阵

（2）处于安全状态，先是P0完成，之后P3，之后P2，之后P1，之后P4。（3）可以⽴即满⾜，满⾜后仍处于安全状态。补充作业判断对错

在RR调度中，上下⽂切换的时间应该⼩于时间⽚的长度。X SJF调度算法是最适合分时系统的调度算法。X FCFS调度算法只能是⾮抢占式的。√ 如果资源分配图中有环，那么就⼀定有死锁。X死锁的时候系统⼀定处于⾮安全状态。√第三次作业⼀、基础作业1.什么是忙等待？

持续地检测⼀个变量直到它具有某⼀个特定值称为忙等待。

2．吸烟者问题：有3个吸烟者和⼀个供应者。第⼀个吸烟者有⾃⼰的烟草；第⼆个吸烟者有⾃⼰的纸；第三个吸烟者有⾃⼰的⽕柴。供应者每次随机放两样东西到桌⼦上提供给3个吸烟者之中的⼀个以完成吸烟。请⽤信号量为吸烟者和供应者进程编写程序。

Semaphore n[2]={0};Semaphore s=1;

0代表烟草，1代表纸，2代表⽕柴.//供应者程序Void procucer()

{While(1){

随机⽣成⼀个在0~2之间的数ｉ;Wait(s);

将除了ｉ表⽰的另外两件东西放在桌⼦上;Signal(n[i]);}

//吸烟者程序Void smoker(int i){While(1){Wait(n[i]);Somke();Signal(s);}｝

⼆、补充作业

1．假设有三个进程R、W1、W2共享缓冲区B。B中只能存放⼀个数。R每次从输⼊设备中读⼀个整数放⼊B中。如果这个整数是奇数，由W1取出打印。如果这个整数是偶数，则由W2取出打印。规定仅当B中没有数据或数据已经被打印才会启动R去读数。W1、W2对B中的数据不能重复打印，当B中没有数据时也不能打印。要求⽤信号量操作写出R、W1、W2三个进程的程序。（请详细描述所使⽤变量的含义）

Semaphore s=1;//进程R可以存⼊缓冲区B的数据个数信号量

Semaphore n[2]={0};//n[0]/n[1]表⽰进程W1/W2可以从缓冲区B中取出的数据个数；//进程RVoid R(){While(1){

读⼊⼀个正数m;Wait(s);将m放⼊B中；if(m/2!=0)Signa([n[0]);ElseSignal(n[1]);

}}Void w1(){While(1);{

Wait(n[0]);

从缓冲区B 取数据k;Signal(s);打印K;}}Void w1(){While(1);{

Wait(n[1]);

从缓冲区B 取数据k;Signal(s);打印K;}}

2．有⼀个铁笼⼦，猎⼿放⼊⽼虎，农民放⼊猪，动物园等待取⾛⽼虎，饭店等待取⾛猪。笼⼦中只能放⼊⼀个动物。请使⽤信号量⽅法为猎⼿、农民、动物园、饭店进程编写程序。Semaphore cage=1;//可以放⼊笼⼦中的动物数量Semaphore tiger=0;//动物园从笼⼦中取出⽼虎的数量Semaphore pig=0;//饭店从笼⼦中取出猪的数量////////////////////猎⼿进程Void hunter(){While(1){

Wait(cage);将⽼虎放⼊笼⼦;Signal(tiger);}

}

Void farmer(){While(1){

Wait(cage);将猪放⼊笼⼦;Signal(pig);}}

Void zoo(){While(1){

wait(tiger);从笼⼦中取出⽼虎;signal(cage);}}

Void restaurant(){While(1){

waitl(pig);从笼⼦中取出猪；signal(cage);}}

3．某寺庙，有⼩、⽼和尚若⼲。有⼀个⽔缸，由⼩和尚提⽔⼊缸供⽼和尚饮⽤。⽔缸可容10桶⽔。⽔取⾃⼀个井中，⽔井窄，每次只能容⼀个⽔桶。⽔桶总数为3。⽔缸每次进出也仅1桶⽔，不可以同时进⾏。请设置合适的信号量描述⼩和尚、⽼和尚取⽔、⼊⽔的算法。

Semaphore bucket=3;//⽔桶的数量

Semaphore tank=1;//⽔缸每次能容⽔桶的数量; Semaphore s=10;//⽔缸容⽔桶⽔量; Semaphore well=1;//井每次能容⽔桶的数量；Semaphore empty=0;//⽔缸中现有的⽔量；Void youngmonk(){While(1){

Wait(bucket);获得⽔桶;Wait(well);井中取⽔；signal(well);Wait(s);Wait(tank);倒⽔⼊⽔缸;Signal(tank);Signal(bucket);Signal(empty);}}

Void oldmonk(){While(1){

Wait(empty);Wait(bucket);获得⽔桶；Wait(tank);从⽔缸中取⽔；Signal(tank);Signal(s);Signal(bucket);}}

4. 判断对错

(1)⼀个系统中进程之间可能是独⽴的也可能是合作的。√(2)如果⽤锁来保护临界区可以防⽌竞争条件。√(3)⼀个计数信号量的值只能取0或者1. X(4)在管程中本地变量只能由本地过程来访问。√5. 选择题

(1)关于竞争条件那句话是对的？BA. ⼏个线程要并发访问同样的数据

B. ⼏个线程要并发访问并修改同样的数据C. 只有在执⾏结果与执⾏顺序⽆关的时候发⽣(2)关于原⼦指令那句话是对的？BA. 原⼦指令只能由⼀条机器指令组成B. 作为⼀个单独的，不可以中断的单元执⾏C. 不能⽤于解决临界区问题

(3)⼀个临界区的解决⽅案不需要实现下⾯的哪⼀条？CA. 互斥B. 有空让进C. 原⼦性D. 有限等待

(4)当低优先级的进程正在访问⼀个数据的时候，若⼀个⾼优先级的进程需要访问同样的数据，可能发⽣AA. 优先级反转B. 死锁C. 竞争条件D. 临界区附加题：

1．独⽊桥问题：某条河上只有⼀座独⽊桥，两边都有⼈要过河，为保证安全，⼀个⽅向有⼈过河另⼀个⽅向的⼈就要等待，并且允许⼀个⽅向上的⼈连续过河。请使⽤信号量实现正确的管理。Semaphore s=1;//两岸过河能使⽤的桥的数量；Semaphore left=1,right=1;Int leftcount=0,rightcount=0;//////////////左岸过河进程Void Left(){While(1){Wait(left);Leftcount++;If(leftcount==1)Wait(s);Signal(left);左岸过河；Wait(left);Leftcount--;If(leftcount==0)

Signal(s);Signal(left);}}

////////////////右岸进程Void right(){While(1){

Wait(right);Rightcount++;If(rightcount==1)Wait(s);Signal(right);右岸过河;Wait(right);