操作系统复习题参考答案整理

1、作业参考答案整理第二章作业1、2、5、6、7、8、16、17、18、19、21、22（b）、）、27、28、29、33、34、36、38、41第二章第二章第二章第二章第二章第二章第二章第二章第二章第二章第二章第二章第二章第二章 Var c array of semaphor :=(1,1,1,1,1)Philosopher(I) repeatif (I mod 2=1) then beginwait(cI);wait(c(I+1)mod 5);Eating;signal(c(I+1)mod 5);signal (cI);Thinking; endelse begin wait (c(I+1)m

2、od 5);wait (cI);Eating;signal (cI);signal (c(I+1)mod 5);Thinking; enduntil false;第二章 29 画图说明管程由哪几部分组成画图说明管程由哪几部分组成?为什么要为什么要引入条件变量引入条件变量? 管程由三部分组成:局部于管程的共享变量说明；对该数据结构进行操作的一组过程；对局部于管程的 数据设置初始值的语句. (图见P80) 因为调用wait原语后，使进程等待的原因有多种，为了区别它们，引入了条件变量. 第二章第二章第三章作业第三章1 1、考虑考虑5 5个进程个进程P P1 1，P P2 2，P P3 3，P P4

3、4，P P5 5，见表，规定进程的优先数越，见表，规定进程的优先数越小，优先级越高，试描述在采用下述调度算法时各个进程运行过小，优先级越高，试描述在采用下述调度算法时各个进程运行过程，并计算采用每种算法时进程平均周转时间。假设忽略进程的程，并计算采用每种算法时进程平均周转时间。假设忽略进程的调度时间。调度时间。1)1)先来先服务调度算法；先来先服务调度算法；2 2）时间片轮转调度算法（时间片为）时间片轮转调度算法（时间片为1ms1ms）；）； 3 3）非剥夺式优先级调度算法；）非剥夺式优先级调度算法；4 4）剥夺式优先级调度）剥夺式优先级调度算法。算法。进程创建时刻ms运行时间ms优先数P10

4、33P2265P3441P4652P5824第三章第三章第三章第三章第三章2（1）3个进程共享个进程共享4个同种类型的资源，每个进程个同种类型的资源，每个进程最大需要最大需要2个资源，请问该系统是否因为竞争该个资源，请问该系统是否因为竞争该资源而死锁？资源而死锁？ （2）n个进程共享个进程共享m个同类资源，若每个进程都个同类资源，若每个进程都需要用该类资源，而且各进程对该类资源的最大需要用该类资源，而且各进程对该类资源的最大需求量小于需求量小于m，且各进程最大需求之和小于，且各进程最大需求之和小于m+n，试证明在这个系统中不可能发生死锁试证明在这个系统中不可能发生死锁。30题2解答由已知条件可

5、得：Maxim+n又因为：Needi = Maxi - Allocationi若系统处于死锁状态, 则有：Allocationi=m则：Needim+n-m=n如此，则至少存在一个进程Pi其Needi=0，因此该系统不会发生死锁。 ni=1 ni=1 ni=1 ni=1 ni=1 ni=1第三章 P114 1、5、6、7、9、13、18、20、21、22第三章第三章第三章第三章第三章第三章第三章 21 在银行家算法的例子中，如果在银行家算法的例子中，如果P0发出的请发出的请求向量由求向量由Request0(0,2,0)改为改为Request0(0,1,0),问系统可否将资源分配给它问系统可否将

6、资源分配给它? 可以. 首先，Request0(0,1,0)=Need0(7,4,3), Request0(0,1,0)=Available(2,3,0); 分配后可修改得一资源数据表,进行安全性检查，可以找到一个安全序列P1,P4,P3,P2,P0, 或P1,P4,P3,P0,P2,因此，系统是安全的，可以立即将资源分配给P0. 第三章第三章第三章【补充】【补充】 有有5个批处理作业（个批处理作业（A，B，C，D，E）按顺序几乎同）按顺序几乎同时到达一个计算中心，估计运行时间分别为时到达一个计算中心，估计运行时间分别为6，8，4，10，2分分钟，他们的优先级分别为钟，他们的优先级分别为3，4

7、，2，5，1（1为最低）。对下面为最低）。对下面每种调度算法，分别给出作业调度序列，并计算作业的平均周每种调度算法，分别给出作业调度序列，并计算作业的平均周转时间：转时间：1、最高优先级优先；、最高优先级优先；2、FIFO；3、短作业优先；、短作业优先；4、时间片轮转（时间片为、时间片轮转（时间片为2分钟）。分钟）。解：1、最高优先级：作业调度序列： D B A C E 0 10 18 24 28 30t = (10+18+24+28+30)/5 = 22 分钟 2、FIFO算法：作业调度序列： A B C D E 0 6 14 18 28 30t = (6+14+18+28+30)/5 =

8、19.2 分钟 3、SJF算法：作业调度序列： E C A B D 0 2 6 12 20 30t = (2+6+12+20+30)/5 = 14 分钟 4、时间片轮转算法：作业调度序列： A B C D E A B C D A B D B D D 0 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30t = (10+16+20+26+30)/5 = 20.4 分钟第四章作业45练习练习1 1有一矩阵：有一矩阵：VAR A: ARRAY 1.100,1.100 OF INTEGER;VAR A: ARRAY 1.100,1.100 OF INTEGER;按先行后列

9、次序存储。在一个虚存系统中，采用按先行后列次序存储。在一个虚存系统中，采用LRULRU淘汰算淘汰算法，一个进程有法，一个进程有3 3页内存空间，每页可以存放页内存空间，每页可以存放200200个整数，其个整数，其中第一页存放程序，且假定程序已经在内存。中第一页存放程序，且假定程序已经在内存。程序程序A A FOR I:=1 TO 100 DO FOR I:=1 TO 100 DO FOR J:=1 TO 100 DO FOR J:=1 TO 100 DO A I,J :=0; A I,J :=0;程序程序B B FOR J:=1 TO 100 DO FOR J:=1 TO 100 DO FOR

10、 I:=1 TO 100 DO FOR I:=1 TO 100 DO A I,J :=0; A I,J :=0;分别就程序分别就程序A A 和和 B B 的执行过程计算缺页次数。的执行过程计算缺页次数。第四章作业第四章作业第四章作业第四章作业第四章作业第四章作业481 1、 某操作系统采用可变分区分配存储管理方法，用户区为某操作系统采用可变分区分配存储管理方法，用户区为512K512K，且始址为且始址为0 0。若分配时采用分配空闲区低地址部分的方案，且初始。若分配时采用分配空闲区低地址部分的方案，且初始时用户的时用户的512K512K空间空闲，对下述申请序列：空间空闲，对下述申请序列： 申请申

11、请300K300K，申请，申请100K100K，释放，释放300K300K，申请，申请150K150K，申请，申请30K30K，申请，申请40K40K，申请，申请60K60K，释放，释放30K30K回答：回答：（1 1）采用首次适应算法，空闲分区中有哪些空块（给出始址、大）采用首次适应算法，空闲分区中有哪些空块（给出始址、大小）？小）？（2 2）采用最佳适应算法，空闲分区中有哪些空块（给出始址、大）采用最佳适应算法，空闲分区中有哪些空块（给出始址、大小）？小）？（3 3）如再申请）如再申请100K100K，针对（，针对（1 1）和（）和（2 2）各有什么结果）各有什么结果第四章第四章作业作业第

12、四章作业第四章作业522、设有一页式存储管理系统，向用户提供的逻辑地址空间最大为64页，每页1024B，内存总共有32个存储块，试问逻辑地址至少应为多少位？内存空间有多大？解：逻辑地址为16位；内存空间有32KB;第四章作业533、在一分页存储管理系统中，逻辑地址长度为16位，页面大小为4096B，现有一逻辑地址为2F6AH，且第0、1、2页依次存放在物理块5、10、11中，问相应的物理地址为多少？ 0010111101101010544、在一个段式存储管理系统中，其段表为： 段号 内存起始地址 段长 0 210 500 1 2350 20 2 100 90 3 1350 590 4 1938

13、 95试求表中逻辑地址对应的物理地址是什么？第一个：2360第二个：段号不合法返回110532555、什么是虚拟存储器？ 虚拟存储器(Virtual Memory)：在具有层次结构存储器的计算机系统中，自动实现部分装入和部分替换功能，能从逻辑上为用户提供一个比物理贮存容量大得多，可寻址的“主存储器”。返回566、假定系统为某进程分配了3个物理块，进程运行时的页面走向为 7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1,开始时3个物理块均为空，给出采用最佳置换算法时页面置换情况，并计算出该算法的缺页率？（1）最佳置换淘汰算法 （2）先进先出淘汰算法 （3）最近最久未

14、使用淘汰算法返回第四章第四章作业作业 最佳置换算法 缺页9次，置换6次 缺页率9/20第四章第四章作业作业 （2）先进先出淘汰算法 缺页13次，置换10次；缺页率13/20第四章第四章作业作业 最近最久未使用淘汰算法缺页12次，置换9次；缺页率12/2060第四章第四章作业作业P 159 1 6 13 17 1 3 6 8 13 17 19 22 26 (增加最佳置换、LRU算法情况分析) 第四章作业第四章作业第四章作业第四章作业 页表机制、缺页中断机构以及地址变换机构第四章作业第四章作业访问访问页面页面4 3 2 1 4 3 5 4 3 2 1 5内存内存页面页面4 4 4 4 4 2 2

15、3 3 3 3 3 1 2 1 5 5 5 解：M=3，最佳置换过程如下：缺页次数：7次，缺页率：7/12=58.3%。访问页访问页面面432143543215内存页内存页面面4444 4 1 333 3 3 22 2 2 1 5 5 M=4，最佳置换过程如下：缺页次数：6次，缺页率：6/12=50%。访问页访问页面面432143543215内存页内存页面面4441115 55 333444 22 22233 31 M=3，FIFO置换过程如下：缺页次数：9次，缺页率：9/12=75%。访问页面访问页面432143543215内存页面内存页面4444 555511 333 344445 22

16、223333 1 111222M=4，FIFO置换过程如下：缺页次数：10次，缺页率：10/12=83.3%。访问页访问页面面432143543215内存页内存页面面4441115 222 333444 411 23333 335M=3，LRU置换过程如下：缺页次数：10次，缺页率：10/12=83.3%。访问页访问页面面432143543215内存页内存页面面4444 4 445 333 3 333 22 5 511 1 1 222M=4，LRU置换过程如下：缺页次数：8次，缺页率：8/12=67.7%。第五章作业第五章P202 习题 2 7 9 15 18 21 27第五章第五章第五章第五

17、章1、设某磁盘有200个柱面，编号为0，1，2，199，磁头刚从140道移到143道完成了读写。若某时刻有9个磁盘请求分别对如下各道进行读写： 86，147，91，177，94，150，102，175，130 试分别求FCFS、SSTF及SCAN磁盘调度算法响应请求的次序及磁头移动的总距离。【补充】【补充】 某单片磁盘旋转速度为每分钟某单片磁盘旋转速度为每分钟6000转，每个磁道有转，每个磁道有20个扇个扇区，相邻磁道间移动时间为区，相邻磁道间移动时间为1ms（忽略磁头启动时间）。若在某时刻，（忽略磁头启动时间）。若在某时刻，磁头位于磁头位于100磁道处，并沿着磁道号增大的方向移动；磁道号请求

18、队磁道处，并沿着磁道号增大的方向移动；磁道号请求队列为列为50、90、30、120、40、150，对请求队列中每个磁道需要读取，对请求队列中每个磁道需要读取1个随机分布的扇区。个随机分布的扇区。针对如下不同调度策略，分别计算读完这些扇区总共大约需要多长时针对如下不同调度策略，分别计算读完这些扇区总共大约需要多长时间，要求给出计算过程。间，要求给出计算过程。 （1）SSTF（2）SCAN（3）CSCAN解：（1）SSTF响应顺序为：90、120、150、50、40、30；移动总磁道数为190，总移道时间为190ms；转速为6000转/分，即100转/秒，旋转一周需要10ms；平均每次读盘的旋转等

19、待时间为5ms，总的旋转延迟为：65=30ms；读取一个扇区的时间为：10ms/20=0.5ms；总的读取时间为：60.5 =3ms；总共需要约：190+30+3 = 223ms。（2）SCAN响应顺序为：120、150、90、50、40、30；移动总磁道数为170，总移道时间为170ms；总的旋转延迟为：65=30ms；总的读取时间为：60.5 =3ms；总共需要约：170+30+3 = 203ms。（3）CSCAN响应顺序为：120、150、30、40、50、90；移动总磁道数为230，总移道时间为230ms；总的旋转延迟为：65=30ms；总的读取时间为：60.5 =3ms；总共需要约：

20、230+30+3 = 263ms。第六章作业第六章作业P246 习题： 2 9 16 22 24(1)(2) 26 2782第六章作业第六章作业假设用户给定的文件路径名为/Level1/Level2/Leveln/datafile，则关于树型目录结构采用线性检索法检索该文件的基本过程为：读入第一个文件分量名Level1，用它与根目录文件（或当前目录文件）中各个目录项的文件名顺序地进行比较，从中找出匹配者，并得到匹配项的索引结点号，再从对应索引结点中获知Level1目录文件所在的盘块号，将相应盘块读入内存。对于2n，循环执行以下步骤，以检索各级目录文件：读入第i个文件分量名Leveli，用它与最

21、新调入内存的当前目录文件中各个目录项的文件名顺序地进行比较，从中找出匹配者，并得到匹配项的索引结点号，再从对应索引结点中获知Leveli目录文件所在的盘块号，将相应盘块读入内存。读入最后一个文件分量名即datafile，用它与第n级目录文件中各个目录项的文件名进行比较，从而得到该文件对应的索引结点号，进而找到该文件物理地址，目录查找操作成功结束。如果在上述查找过程中，发现任何一个文件分量名未能找到，则停止查找并返回“文件未找到”的出错信息。第六章作业第六章作业 就基于索引结点的共享方式而言，其优点在于“建立新的共享链接，并不改变文件拥有者的关系，仅把索引结点共享计数器加1，所以系统可方便获悉由

22、多少个目录项指向该文件”。同时，该方式也存在所谓“悬空指针”的问题和缺点。具体而言，文件拥有者不能删除自己的文件，否则将留下指向该结点的悬空指针，造成该结点再分配时，系统出错；为此，拥有者只能清除自己的目录项，且要为其它共享者无端付费，直至其它共有者清除该文件?第六章作业就基于符号链的文件共享方式来说，只有文件主才拥有指向其索引结点的指针，而共享该文件的其它用户只有该文件的路径名且没有指向索引结点的指针，所以也就不会发生在文件主删除共享文件后留下所谓“悬空指针”的问题。当文件拥有者把一个共享文件删除后，其它用户试图通过符号链来访问一个被删除的共享文件时将因系统找不到该文件而使访问失败，于是将符

23、号链删除，此时不会有任何其它负面效应。当然，这种方式也存在自己的问题。在其它用户访问共享文件时，系统是根据给定的文件路径名，逐个分量地去查找目录，直至找到该文件的索引结点。因此，在访问共享文件时要多次读盘，使每次访问文件的系统开销加大，且增加了启动磁盘的频率。此外，要为每个共享用户建立一条符号链，而该链实际上是一个文件，尽管该文件非常简单，却仍需为之配置一个索引结点，故而也要消耗一定的磁盘空间。需要指出的是，本共享方式还有一个特殊的优点，即它能够用于链接（通过计算机网络）世界上任何地方的机器中的文件，此时只需提供该文件所在机器的网络地址以及在该机器中的文件路径。第六章作业 1、使用文件系统时，为什么通常要显式地进行OPEN、CLOSE操作 ？ 第六章作业 2、假定盘块的大小为1KB，硬盘的大小为500MB，采用显式链接分配方式时，其FAT需占用多少存储空间？ 解：该硬盘共有500K个盘块，则