1、作业参考答案整理第二章作业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)repeatif(Imod2=1)thenbeginwait(cI);wait(c(I+1)mod5);Eating;signal(c(I+1)mod5);signal(cI);Thinking;endelsebeginwait(c(I+1)mod5);wait(cI);Eatin
2、g;signal(cI);signal(c(I+1)mod5);Thinking;enduntilfalse;第二章29 画画图说明管程由哪几部分明管程由哪几部分组成成?为什么要什么要引入条件引入条件变量量?管程由三部分组成:局部于管程的共享变量说明；对该数据结构进行操作的一组过程；对局部于管程的数据设置初始值的语句.(图见P80)因为调用wait原语后，使进程等待的原因有多种，为了区别它们，引入了条件变量.第二章第二章第三章作业第三章1 1、考考虑5 5个个进程程P P1 1，P P2 2，P P3 3，P P4 4，P P5 5，见表，表，规定定进程的程的优先数越先数越小，小，优先先级越高
3、越高，试描述在采用下述描述在采用下述调度算法度算法时各个各个进程运行程运行过程，程，并并计算采用每种算法算采用每种算法时进程平均周程平均周转时间。假。假设忽略忽略进程的程的调度度时间。1)1)先来先服先来先服务调度算法；度算法；2 2）时间片片轮转调度算法（度算法（时间片片为1ms1ms）；）；3 3）非剥）非剥夺式式优先先级调度算法；度算法；4 4）剥）剥夺式式优先先级调度算法。度算法。进程创建时刻ms运行时间ms优先数P1033P2265P3441P4652P5824第三章第三章第三章第三章第三章2（1）3个个进进程程共共享享4个个同同种种类类型型的的资资源源，每每个个进进程程最最大大需
4、需要要2个个资资源源，请请问问该该系系统统是是否否因因为为竞竞争争该该资资源而死锁？源而死锁？（2）n个个进进程程共共享享m个个同同类类资资源源，若若每每个个进进程程都都需需要要用用该该类类资资源源，而而且且各各进进程程对对该该类类资资源源的的最最大大需需求求量量小小于于m，且且各各进进程程最最大大需需求求之之和和小小于于m+n，试证明在这个系统中不可能发生死锁。试证明在这个系统中不可能发生死锁。题2解答由已知条件可得：Maxim+n又因为：Needi=Maxi-Allocationi若系统处于死锁状态,则有：Allocationi=m则：Needim+n-m=n如此，则至少存在一个进程Pi其
5、Needi=0，因此该系统不会发生死锁。ni=1 ni=1 ni=1 ni=1 ni=1 ni=130第三章P114 1、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);分配后可修改得一资源数据表,进行安全性检查，可以找到一个安
6、全序列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分分钟）。）。
7、解：1、最高优先级：作业调度序列：DBACE01018242830t=(10+18+24+28+30)/5=22分钟2、FIFO算法：作业调度序列：ABCDE0614182830t=(6+14+18+28+30)/5=19.2分钟3、SJF算法：作业调度序列：ECABD026122030t=(2+6+12+20+30)/5=14分钟4、时间片轮转算法：作业调度序列：ABCDEABCDABDBDD024681012141618202224262830t=(10+16+20+26+30)/5=20.4分钟第四章作业练习练习1 1有一矩有一矩阵：VAR A:ARRAY 1.100,1.100 OF
8、INTEGER;VAR A:ARRAY 1.100,1.100 OF INTEGER;按先行后列次序存按先行后列次序存储。在一个虚存系。在一个虚存系统中，采用中，采用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
9、J:=1 TO 100 DO FOR J:=1 TO 100 DO FOR I:=1 TO 100 DO FOR I:=1 TO 100 DO A I,J:=0;A I,J:=0;分分别就程序就程序A A 和和 B B 的的执行行过程程计算缺算缺页次数。次数。第四章作第四章作业45第四章作第四章作业第四章作第四章作业1 1、某操作系某操作系统采用可采用可变分区分配存分区分配存储管理方法，用管理方法，用户区区为512K512K，且始址且始址为0 0。若分配。若分配时采用分配空采用分配空闲区低地址部分的方案，且初始区低地址部分的方案，且初始时用用户的的512K512K空空间空空闲，对下述申下述申请
10、序列：序列：申申请300K300K，申，申请100K100K，释放放300K300K，申，申请150K150K，申，申请30K30K，申，申请40K40K，申，申请60K60K，释放放30K30K回答：回答：（1 1）采用首次适）采用首次适应算法，空算法，空闲分区中有哪些空分区中有哪些空块（给出始址、大小）出始址、大小）？（2 2）采用最佳适）采用最佳适应算法，空算法，空闲分区中有哪些空分区中有哪些空块（给出始址、大小）出始址、大小）？（3 3）如再申）如再申请100K100K，针对（1 1）和（）和（2 2）各有什么）各有什么结果果第四章作第四章作业48第四章作业第四章作业2、设有一页式存储
11、管理系统，向用户提供的逻辑地址空间最大为64页，每页1024B，内存总共有32个存储块，试问逻辑地址至少应为多少位？内存空间有多大？解：逻辑地址为16位；内存空间有32KB;第四章作业523、在一分页存储管理系统中，逻辑地址长度为16位，页面大小为4096B，现有一逻辑地址为2F6AH，且第0、1、2页依次存放在物理块5、10、11中，问相应的物理地址为多少？0010111101101010534、在一个段式存储管理系统中，其段表为：段号 内存起始地址 段长 0 210 500 1 2350 20 2 100 90 3 1350 590 4 1938 95试求表中逻辑地址对应的物理地址是什么？
12、第一个：2360第二个：段号不合法返回110532545、什么是虚拟存储器？虚拟存储器(VirtualMemory)：在具有层次结构存储器的计算机系统中，自动实现部分装入和部分替换功能，能从逻辑上为用户提供一个比物理贮存容量大得多，可寻址的“主存储器”。返回556、假定系统为某进程分配了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）最近最久未使用淘汰算法返回56第四章作第四章作业最佳置换算法
13、缺页9次，置换6次缺页率9/20第四章作第四章作业（2）先进先出淘汰算法 缺页13次，置换10次；缺页率13/20第四章作第四章作业最近最久未使用淘汰算法缺页12次，置换9次；缺页率12/20第四章作第四章作业P 159 1 6 13 17 1 3 6 8 13 17 19 22 26(增加最佳置换、LRU算法情况分析)60第四章作第四章作业第四章作第四章作业页表机制、缺页中断机构以及地址变换机构第四章作第四章作业访问页面4 3 2 1 4 3 5 4 3 2 1 5内存页面4 4 4 4 4 2 2 3 3 3 3 3 1 2 1 5 5 5 解：M=3，最佳置换过程如下：缺页次数：7次，缺
14、页率：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内存页面44411152223334444112
15、3333335M=3，LRU置换过程如下：缺页次数：10次，缺页率：10/12=83.3%。访问页面432143543215内存页面44444445333333322551111222M=4，LRU置换过程如下：缺页次数：8次，缺页率：8/12=67.7%。第五章作业第五章P202 习题 2 7 9 15 18 21 27第五章第五章第五章第五章1、设某磁盘有200个柱面，编号为0，1，2，199，磁头刚从140道移到143道完成了读写。若某时刻有9个磁盘请求分别对如下各道进行读写：86，147，91，177，94，150，102，175，130 试分别求FCFS、SSTF及SCAN磁盘调度算
16、法响应请求的次序及磁头移动的总距离。【补充】充】某某单片磁片磁盘旋旋转速度速度为每分每分钟6000转，每个磁道有，每个磁道有20个扇区，相个扇区，相邻磁道磁道间移移动时间为1ms（忽略磁（忽略磁头启启动时间）。）。若在某若在某时刻，磁刻，磁头位于位于100磁道磁道处，并沿着，并沿着磁道号增大的方向移磁道号增大的方向移动；磁道号；磁道号请求求队列列为50、90、30、120、40、150，对请求求队列中每个磁道需要列中每个磁道需要读取取1个随机分布的扇区。个随机分布的扇区。针对如下不同如下不同调度策略，分度策略，分别计算算读完完这些扇区些扇区总共大共大约需要多需要多长时间，要求，要求给出出计算算
17、过程。程。（1）SSTF（2）SCAN（3）CSCAN解：（1）SSTF响应顺序为：90、120、150、50、40、30；移动总磁道数为190，总移道时间为190ms；转速为6000转/分，即100转/秒，旋转一周需要10ms；平均每次读盘的旋转等待时间为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
18、总共需要约：170+30+3=203ms。（3）CSCAN响应顺序为：120、150、30、40、50、90；移动总磁道数为230，总移道时间为230ms；总的旋转延迟为：65=30ms；总的读取时间为：60.5=3ms；总共需要约：230+30+3=263ms。第六章作业第六章作业P246习题：29162224(1)(2)262782第六章作业第六章作业假设用户给定的文件路径名为/Level1/Level2/Leveln/datafile，则关于树型目录结构采用线性检索法检索该文件的基本过程为：读入第一个文件分量名Level1，用它与根目录文件（或当前目录文件）中各个目录项的文件名顺序地进
19、行比较，从中找出匹配者，并得到匹配项的索引结点号，再从对应索引结点中获知Level1目录文件所在的盘块号，将相应盘块读入内存。对于2n，循环执行以下步骤，以检索各级目录文件：读入第i个文件分量名Leveli，用它与最新调入内存的当前目录文件中各个目录项的文件名顺序地进行比较，从中找出匹配者，并得到匹配项的索引结点号，再从对应索引结点中获知Leveli目录文件所在的盘块号，将相应盘块读入内存。读入最后一个文件分量名即datafile，用它与第n级目录文件中各个目录项的文件名进行比较，从而得到该文件对应的索引结点号，进而找到该文件物理地址，目录查找操作成功结束。如果在上述查找过程中，发现任何一个文
20、件分量名未能找到，则停止查找并返回“文件未找到”的出错信息。第六章作业第六章作业就基于索引结点的共享方式而言，其优点在于“建立新的共享链接，并不改变文件拥有者的关系，仅把索引结点共享计数器加1，所以系统可方便获悉由多少个目录项指向该文件”。同时，该方式也存在所谓“悬空指针”的问题和缺点。具体而言，文件拥有者不能删除自己的文件，否则将留下指向该结点的悬空指针，造成该结点再分配时，系统出错；为此，拥有者只能清除自己的目录项，且要为其它共享者无端付费，直至其它共有者清除该文件?第六章作业就基于符号链的文件共享方式来说，只有文件主才拥有指向其索引结点的指针，而共享该文件的其它用户只有该文件的路径名且没
21、有指向索引结点的指针，所以也就不会发生在文件主删除共享文件后留下所谓“悬空指针”的问题。当文件拥有者把一个共享文件删除后，其它用户试图通过符号链来访问一个被删除的共享文件时将因系统找不到该文件而使访问失败，于是将符号链删除，此时不会有任何其它负面效应。当然，这种方式也存在自己的问题。在其它用户访问共享文件时，系统是根据给定的文件路径名，逐个分量地去查找目录，直至找到该文件的索引结点。因此，在访问共享文件时要多次读盘，使每次访问文件的系统开销加大，且增加了启动磁盘的频率。此外，要为每个共享用户建立一条符号链，而该链实际上是一个文件，尽管该文件非常简单，却仍需为之配置一个索引结点，故而也要消耗一定
22、的磁盘空间。需要指出的是，本共享方式还有一个特殊的优点，即它能够用于链接（通过计算机网络）世界上任何地方的机器中的文件，此时只需提供该文件所在机器的网络地址以及在该机器中的文件路径。第六章作业1、使用文件系统时，为什么通常要显式地进行OPEN、CLOSE操作？第六章作业2、假定盘块的大小为1KB，硬盘的大小为500MB，采用显式链接分配方式时，其FAT需占用多少存储空间？解：该硬盘共有500K个盘块，则FAT表共有500K项；要表示这500K个盘块，每个FAT表项至少需要19位。通常在实际中，FAT表项的长度取作半个字节的整数倍，所以这里可以取每个FAT表项为20位。这样，FAT表需要的存储空
23、间为：2.5字节500K=1250KB.第六章作业补充：充：在在Unix中，如果一个中，如果一个盘块的大小的大小为1KB，每个，每个盘块号占号占4个字个字节，即每，即每块可放可放256个地址，个地址，请转换下列文件的字下列文件的字节偏移量偏移量为物理地址：物理地址：（1）9999；（；（2）18000；（；（3）420000。解：（1）9999/1024=9;9999%1024=783相对块号为9，属于直接索引项范围（09）。读取索引节点表中索引项9（索引表偏移量36字节处），其数值为需要访问的物理块号；该物理块内容偏移783字节处即需要访问的数据。（2）18000/1024=17;18000
24、1024=592相对块号为17，属于一次间接索引项范围（10265）。读取索引节点表中索引项10（索引表偏移量40字节处），其数值为直接索引块的物理块号；读取该物理块，其偏移(17-10)*4=28字节处为需要访问的物理块号；该物理块内容偏移592字节处即需要访问的数据。（3）420000/1024=410;420000%1024=160相对块号为410，属于二次间接索引项范围（26665791）。读取索引节点表中索引项11（索引表偏移量44字节处），其数值为一次间接索引块的物理块号；读取该物理块，其偏移(410-266)/256)*4=0字节处第一个直接索引块的物理块号，读取该物理块，其偏移(410-266)%256)*4=576字节处为需要访问的物理块号；该物理块内容偏移160字节处即需要访问的数据。
