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

作业参考答案整理第二章作业1、2、5、6、7、8、16、17、18、19、21、22（b）、27、28、29、33、34、36、38、41第二章第二章第二章第二章第二章第二章第二章第二章第二章第二章第二章第二章第二章第二章•Varcarrayofsemaphor:=(1,1,1,1,1)•Philosopher(I)•repeat•if(Imod2==1)then•begin•wait(c[I]);•wait(c[(I+1)mod5]);•Eating;•signal(c[[(I+1)mod5]);•signal(c[I]);•Thinking;•end•else{beginwait(c[[(I+1)mod5]);wait(c[I]);Eating;signal(c[I]);signal(c[[(I+1)mod5]);Thinking;end}untilfalse;第二章•29画图说明管程由哪几部分组成?为什么要引入条件变量?•管程由三部分组成:局部于管程的共享变量说明；对该数据结构进行操作的一组过程；对局部于管程的•数据设置初始值的语句.(图见P80)•因为调用wait原语后，使进程等待的原因有多种，为了区别它们，引入了条件变量.第二章第二章第三章作业第三章1、考虑5个进程P1，P2，P3，P4，P5，见表，规定进程的优先数越小，优先级越高，试描述在采用下述调度算法时各个进程运行过程，并计算采用每种算法时进程平均周转时间。假设忽略进程的调度时间。1)先来先服务调度算法；2）时间片轮转调度算法（时间片为1ms）；3）非剥夺式优先级调度算法；4）剥夺式优先级调度算法。进程创建时刻ms运行时间ms优先数P1033P2265P3441P4652P5824第三章第三章第三章第三章第三章2（1）3个进程共享4个同种类型的资源，每个进程最大需要2个资源，请问该系统是否因为竞争该资源而死锁？（2）n个进程共享m个同类资源，若每个进程都需要用该类资源，而且各进程对该类资源的最大需求量小于m，且各进程最大需求之和小于m+n，试证明在这个系统中不可能发生死锁。30题2解答•由已知条件可得：Maxim+n•又因为：Needi=Maxi-Allocationi•若系统处于死锁状态,则有：Allocationi=m•则：Needim+n-m=n•如此，则至少存在一个进程Pi其Needi=0，因此该系统不会发生死锁。ni=1ni=1ni=1ni=1ni=1ni=1第三章•P1141、5、6、7、9、13、18、20、21、22第三章第三章第三章第三章第三章第三章第三章•21在银行家算法的例子中，如果P0发出的请求向量由Request0(0,2,0)改为Request0(0,1,0),问系统可否将资源分配给它?•可以.•首先，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，2，5，1（1为最低）。对下面每种调度算法，分别给出作业调度序列，并计算作业的平均周转时间：1、最高优先级优先；2、FIFO；3、短作业优先；4、时间片轮转（时间片为2分钟）。•解：•1、最高优先级：•作业调度序列：DBACE•01018242830•t=(10+18+24+28+30)/5=22分钟••2、FIFO算法：•作业调度序列：ABCDE•0614182830•t=(6+14+18+28+30)/5=19.2分钟••3、SJF算法：•作业调度序列：ECABD•026122030•t=(2+6+12+20+30)/5=14分钟••4、时间片轮转算法：•作业调度序列：ABCDEABCDABDBDD•024681012141618202224262830•t=(10+16+20+26+30)/5=20.4分钟第四章作业45练习1有一矩阵：VARA:ARRAY[1..100,1..100]OFINTEGER;按先行后列次序存储。在一个虚存系统中，采用LRU淘汰算法，一个进程有3页内存空间，每页可以存放200个整数，其中第一页存放程序，且假定程序已经在内存。程序AFORI:=1TO100DOFORJ:=1TO100DOA[I,J]:=0;程序BFORJ:=1TO100DOFORI:=1TO100DOA[I,J]:=0;分别就程序A和B的执行过程计算缺页次数。第四章作业第四章作业第四章作业481、某操作系统采用可变分区分配存储管理方法，用户区为512K，且始址为0。若分配时采用分配空闲区低地址部分的方案，且初始时用户的512K空间空闲，对下述申请序列：申请300K，申请100K，释放300K，申请150K，申请30K，申请40K，申请60K，释放30K回答：（1）采用首次适应算法，空闲分区中有哪些空块（给出始址、大小）？（2）采用最佳适应算法，空闲分区中有哪些空块（给出始址、大小）？（3）如再申请100K，针对（1）和（2）各有什么结果第四章作业第四章作业第四章作业522、设有一页式存储管理系统，向用户提供的逻辑地址空间最大为64页，每页1024B，内存总共有32个存储块，试问逻辑地址至少应为多少位？内存空间有多大？解：逻辑地址为16位；内存空间有32KB;第四章作业533、在一分页存储管理系统中，逻辑地址长度为16位，页面大小为4096B，现有一逻辑地址为2F6AH，且第0、1、2页依次存放在物理块5、10、11中，问相应的物理地址为多少？0010111101101010544、在一个段式存储管理系统中，其段表为：段号内存起始地址段长02105001235020210090313505904193895试求表中逻辑地址对应的物理地址是什么？第一个：2360第二个：段号不合法返回110532555、什么是虚拟存储器？虚拟存储器(VirtualMemory)：在具有层次结构存储器的计算机系统中，自动实现部分装入和部分替换功能，能从逻辑上为用户提供一个比物理贮存容量大得多，可寻址的“主存储器”。返回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）最近最久未使用淘汰算法返回第四章作业•最佳置换算法•缺页9次，置换6次•缺页率9/20第四章作业•（2）先进先出淘汰算法缺页13次，置换10次；缺页率13/20第四章作业•最近最久未使用淘汰算法缺页12次，置换9次；缺页率12/2060第四章作业P15916131713681317192226(增加最佳置换、LRU算法情况分析)第四章作业第四章作业•页表机制、缺页中断机构以及地址变换机构第四章作业访问页面432143543215内存页面444442233333121555解：M=3，最佳置换过程如下：缺页次数：7次，缺页率：7/12=58.3%。访问页面432143543215内存页面444441333332222155M=4，最佳置换过程如下：缺页次数：6次，缺页率：6/12=50%。访问页面432143543215内存页面444111555333444222223331M=3，FIFO置换过程如下：缺页次数：9次，缺页率：9/12=75%。访问页面432143543215内存页面4444555511333344445222233331111222M=4，FIFO置换过程如下：缺页次数：10次，缺页率：10/12=83.3%。访问页面432143543215内存页面444111522233344441123333335M=3，LRU置换过程如下：缺页次数：10次，缺页率：10/12=83.3%。访问页面432143543215内存页面44444445333333322551111222M=4，LRU置换过程如下：缺页次数：8次，缺页率：8/12=67.7%。第五章作业第五章P202习题27915182127第五章第五章第五章第五章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磁道处，并沿着磁道号增大的方向移动；磁道号请求队列为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；平均每次读盘的旋转等待时间为5ms，总的旋转延迟为：6×5=30ms；•读取一个扇区的时间为：10ms/20=0.5ms；总的读取时间为：6×0.5=3ms；•总共需要约：190+30+3=223ms。•（2）SCAN•响应顺序为：120、150、90、50、40、30；移动总磁道数为170，总移道时间为170ms；•总的旋转延迟为：6×5=30ms；•总的读取时间为：6×0.5=3ms；•总共需要约：170+30+3=203ms。•（3）CSCAN•响应顺序为：120、150、30、40、50、90；移动总磁道数为230，总移道时间为230ms；•总的旋转延迟为：6×5=30ms；•总的读取时间为：6×0.5=3ms；•总共需要约：230+30+3=263ms。•第六章作业第六章作业P246习题：29162224(1)(2)262782第六章作业第六章作业•假设用户给定的文件路径名为/Level1/Level2/…/Leveln/datafile，则关于树型目录结构采用线性检索法检索该文件的基本过程为：①读入第一个文件分量名Level1，用它与根目录文件（或当前目录文件）中各个目录项的文件名顺序地进行比较，从中找出匹配者，并得到匹配项的索引结点号，再从对应索引结点中获知Level1目录文件所在的盘块号，将相应盘块读入内存。②对于2~n，循环执行以下步骤，以检索各级目录文件：读入第i个文件分量名Leveli，用它与最新调入内存的当前目录文件中各个目录项的文件名顺序地进行比较，从中找出匹配者，并得到匹配项的索引结点号，再从对应索引结点中获知Leveli目录文件所在的盘块号，将相应盘块读入内存。③读入最后一个文件分量名即datafile，用它与第n级目录文件中各个目录项的文件名进行比较，从而得到该文件对应的索引结点号，进而找到该文件物理地址，目录查找操作成功结束。如果在上述查找过程中，发现任何一个文件分量名未能找到，则停止查找并返回“文件未找到”的出错信息。第六章作业第六章作业•就基于索引结点的共享方式而言，其优点在于“建立新的共享链接，并不改变文件拥有者的关系，仅把索引结点共享计数器加1，所以系统可方便获悉由多少个目录项指向该文件”。同时，该方式也存在所谓“悬空指针”的问题和缺点。具体而言，文件拥有者不能删除自己的文件，否则将留下指向该结点的悬空指针，造成该结点再分配时，系统出