作业参考答案整理第二章作业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) repeat if (I mod 2=1) then begin wait(cI); wait(c(I+1)mod 5); Eating; signal(c(I+1)mod 5); signal (cI); Thinking; end elsebeginwait (c(I+1)mod 5); wait (cI); Eating; signal (cI); signal (c(I+1)mod 5); Thinking;end until false;第二章 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第三章 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); 分配后可修改得一资源数据表,进行安全性检查，可以找到一个安全序列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、最高优先级： 作业调度序列： D B A C E 0 10 18 24 28 30 t = (10+18+24+28+30)/5 = 22 分钟 2、FIFO算法： 作业调度序列： A B C D E 0 6 14 18 28 30 t = (6+14+18+28+30)/5 = 19.2 分钟 3、SJF算法： 作业调度序列： E C A B D 0 2 6 12 20 30 t = (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 30 t = (10+16+20+26+30)/5 = 20.4 分钟第四章作业45练习1 有一矩阵：VAR A: ARRAY 1.100,1.100 OF INTEGER; 按先行后列次序存储。在一个虚存系统中，采用LRU淘汰算 法，一个进程有3页内存空间，每页可以存放200个整数，其中 第一页存放程序，且假定程序已经在内存。 程序A FOR I:=1 TO 100 DOFOR J:=1 TO 100 DOA I,J :=0; 程序BFOR J:=1 TO 100 DOFOR I:=1 TO 100 DOA 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、在一个段式存储管理系统中，其段表为：段号 内存起始地址 段长0 210 5001 2350 202 100 903 1350 5904 1938 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）最近最久未使用淘汰算法返回第四章作业 最佳置换算法 缺页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 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 555511333 34444522 2233331 111222M=4，FIFO置换过程如下： 缺页次数：10次，缺页率：10/12=83.3%。访问页 面432143543215内存页页 面4441115 222333444 41123333 335M=3，LRU置换过程如下： 缺页次数：10次，缺页率：10/12=83.3%。访问页 面432143543215内存页页 面4444 4 445333 3 33322 5 5111 1 222M=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磁盘调度算法响应请求的次序及磁头移动的总距 离。【补充】 某单片磁盘旋转速度为每分钟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，总的旋转延迟为：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