操作系统 习题解析.

1、2022-5-231习题分析习题分析 习题一：进程调度习题一：进程调度 习题二：习题二：P/V操作例子操作例子 习题三：页式存储管理中的一级页表地址计算习题三：页式存储管理中的一级页表地址计算 习题四：磁盘调度习题四：磁盘调度SSTF存在的问题存在的问题 习题五：磁盘空闲块的成组分配算法习题五：磁盘空闲块的成组分配算法2022-5-232习题一：进程调度习题一：进程调度有有5个进程如下表。时间从个进程如下表。时间从0开始，单位为开始，单位为1，最高优先级为，最高优先级为0. 进程进程 到达时间到达时间 优先级优先级 所需运行时间所需运行时间A 0 2 3B 2 3 8C 4 4 6 D 6 1

2、 5E 8 0 4绘图说明以下进程调度过程：（绘图说明以下进程调度过程：（1 CPU系统，所有进程只使用系统，所有进程只使用CPU）。）。请使用时间为横向坐标轴，并请在图中标明每个进程的请使用时间为横向坐标轴，并请在图中标明每个进程的“等待等待”和和“运运行行”两种状态。两种状态。先来先服务（先来先服务（FCFS）。）。轮转调度（轮转调度（Round-Robin） 时间片时间片=2。优先级轮转法（优先级轮转法（Priority Round-Robin） 时间片时间片=2。最短进程优先算法（最短进程优先算法（Shortest Process Next）。）。2022-5-233答案答案新进程出现

3、，重新调度，新进新进程出现，重新调度，新进程的优先级与当前正运行程的优先级与当前正运行进程比较，进程比较，抢占发生抢占发生。时间片用完，进程切换，就绪时间片用完，进程切换，就绪队列中的首进程投入运行，队列中的首进程投入运行，换下来的进程按其优先级换下来的进程按其优先级插入到就绪队列中，体现插入到就绪队列中，体现轮转与优先级各自的特点轮转与优先级各自的特点可能引起调度可能引起调度CPU的时机：的时机：进程运行结束时进程运行结束时进程的时间片用完时（进程的时间片用完时（RR）进程申请资源未得到满足时进程申请资源未得到满足时(被阻塞被阻塞)拥有更高的优先级的进程到达时拥有更高的优先级的进程到达时可看

4、成是可看成是抢占式的抢占式的FCFS2022-5-234PRR的其它应用的其它应用PRR应用的参考文献：应用的参考文献：题目：题目：Priority Ruond-Robin Scheduling for Very Large Virtual Environment作者：作者：Chris FaisstnauerDieter SchmalstiegWerner Purgathofer所属单位：所属单位：Vienna University of Technology, Austria奥地利维也纳科技大学 邮件地址：邮件地址：faisstcg.tuwien.ac.at检索网址：检索网址：http:/i

5、/xpls/abs_all.jsp?arnumber=8404912022-5-235Basic Priority Round-RobinSelected elements: A,C,G - B,D,G - A,E,G - B,F,G循环计数 = 每个级别上的进程数目 * 优先级层次总数本例中，优先级分为3个层次，分别为：0级/1级/2级i=0i=1i=2优先级2022-5-236习题二：习题二：P/V操作的应用操作的应用 某公司有两个生产部门和一个装配部门，两个生某公司有两个生产部门和一个装配部门，两个生产部门分别生产甲、乙两种零件，装配部门的任产部门分别

6、生产甲、乙两种零件，装配部门的任务是把甲、乙两种零件组装成产品。两个生产部务是把甲、乙两种零件组装成产品。两个生产部门每生产一个零件后都要分别把它们送到装配部门每生产一个零件后都要分别把它们送到装配部门的货架门的货架S1、S2上。上。S1存放零件甲，存放零件甲，S2存放零存放零件乙，件乙，S1和和S2均可容纳均可容纳20个零件。装配人员每次个零件。装配人员每次从货架上取走一个甲零件和一个乙零件后，将其从货架上取走一个甲零件和一个乙零件后，将其组装成产品。请利用组装成产品。请利用P、V操作控制各部门之间使操作控制各部门之间使用零件的货架规则，保证零件入用零件的货架规则，保证零件入/出货架的正确性

7、。出货架的正确性。2022-5-237算法描述算法描述Begin 信号量初值：信号量初值：mutex1:=1;mutex2:=1;empty1:=20;full1:=0;empty2:=20;full2:=0CobeginA部门：部门： begin Repeat 生产一个产品生产一个产品A; P(empty1); P(mutex1); 将产品将产品A放入放入S1; V(mutex1); V(full1); Until false EndB部门：部门：beginRepeat 生产一个产品生产一个产品B; P(empty2); P(mutex2); 将产品将产品B放入放入S2; V(mutex2)

8、; V(full2);Until falseEnd装配人员：装配人员：beginRepeat P(full1); P(full2); P(mutex1); 从从S1中取出产品中取出产品A; V(mutex1); V(empty1); P(mutex2); 从从S2中取出产品中取出产品B; V(mutex2); V(empty2); 把把A和和B组装成产品组装成产品Until false EndCoendEnd;2022-5-238习题三：确定页表位置习题习题三：确定页表位置习题 一个一个32位的虚拟存储系统有两级页表，其逻辑地位的虚拟存储系统有两级页表，其逻辑地址中，第址中，第22到到31位是

9、第一级页表，位是第一级页表，12位到位到21位是位是第二级页表，页内偏移占第二级页表，页内偏移占0到到11位。一个进程的位。一个进程的地址空间为地址空间为4GB，如果从，如果从0XC0000000开始映射开始映射4MB大小页表，请问第一级页表所占的大小页表，请问第一级页表所占的4KB空间空间映射在什么位置，并说明理由。（注意映射在什么位置，并说明理由。（注意B代表字代表字节，一个节，一个32位地址占位地址占4字节）字节）第一级页表项第一级页表项 第二级页表项第二级页表项 页内相对位移页内相对位移31021112022-5-239习题三：续一习题三：续一虚拟地址空间虚拟地址空间0= 0X0000

10、00000= 0X000000003G= 3G= 0XC00000XC0000000000第第768K768K个页面个页面4G-1= 0XFFFFFFFF4G-1= 0XFFFFFFFF4MB页表所在位置页表所在位置（全部页表占（全部页表占1K个页面）个页面）二级页表每块1024项4KB大小每项代表1页=4KB一级页表4KB共有1024项,每项代表1k个页表项=1M页=4MB7684MB=3G一级页表所在位置第768块页表是3G虚拟地址映射位置共有1024个页表块(页表页面)1M个页表项，总共占4MB大小内存。1M个页表项可表示1M 4K=4G内存其中包括了一级页表的4K区域。. . . .：

11、. . . . . . . . . .：一个32位的虚拟存储系统有两级页表，其逻辑地址中，第22到31位是第一级页表，12位到21位是第二级页表，页内偏移占0到11位。一个进程的地址空间为4GB，如果从0XC0000000开始映射4MB大小页表，请问第一级页表所占的4KB空间映射在什么位置，并说明理由。（注意B代表字节，一个32位地址占4字节）第一级页表项第一级页表项 第二级页表项第二级页表项 页内相对位移页内相对位移31021111页=4KB,4GB虚拟空间共1M个页面第768项第768项0页1023页1024页2047页第768块7681024+768：2022-5-2310习题三习题三-

12、续二续二虚拟地址空间虚拟地址空间03G4MB页表所在位置页表所在位置（有（有1K个页面）个页面）二级页表二级页表一级页表所在位置一级页表所在位置768768页表块页表块即：即：76876810241024项开始项开始一级页表一级页表4KB共有共有1024项项每项占每项占4B共有共有1M1M个页表项个页表项1M1M4B4B大小大小=4MB=4MB大小大小.一个32位的虚拟存储系统有两级页表，其逻辑地址中，第22到31位是第一级页表，12位到21位是第二级页表，页内偏移占0到11位。一个进程的地址空间为4GB，如果从0XC0000000开始映射4MB大小页表，请问第一级页表所占的4KB空间映射在什

13、么位置，并说明理由。（注意B代表字节，一个32位地址占4字节）.第第0 0项项第第768768项项0 xC0000000+(0 xC000000012)2)= 0 xC0000000+0 x00300000=0 xC0300000第一级页表所占的4KB空间的虚拟地址范围是：0 xC03000000 xC300FFF2022-5-2311磁盘调度算法磁盘调度算法寻道时间寻道时间旋转延迟时间旋转延迟时间Ts= m n + s，寻道时间，寻道时间其中：其中：m为常数；为常数；n为移动磁道数；为移动磁道数；s为启动磁盘时间为启动磁盘时间Tr旋转延迟时间：硬盘大约旋转延迟时间：硬盘大约8.3ms，软盘，

14、软盘50ms100msTt 传输时间：读传输时间：读/写数据的实际时间写数据的实际时间=b/(rN)b:读写字节数；读写字节数；r:磁盘转速；磁盘转速；N:每条磁道上的字节数。每条磁道上的字节数。磁盘访问时间磁盘访问时间 Ta = Ts + Tr + Tt 2022-5-2312习题四：习题四：SSTF磁盘调度存在的问题磁盘调度存在的问题应用应用SSTF (shortest-seek-time-first)调调度策略，某些进程可度策略，某些进程可能永远不能被调度到能永远不能被调度到假定每当在满足磁道假定每当在满足磁道376上的信息请求之上的信息请求之前，系统总会接收到前，系统总会接收到一个新的

15、请求流，而一个新的请求流，而且这些请求所要移动且这些请求所要移动磁头的距离总小于达磁头的距离总小于达到磁道到磁道376所移动的所移动的距离，因而，对于距离，因而，对于376磁道和磁道和396磁道磁道上的信息请求将永远上的信息请求将永远得不到满足。得不到满足。试设计一种磁盘访问调试设计一种磁盘访问调度算法，以确保不会度算法，以确保不会发生诸如上例的发生诸如上例的“饥饥饿饿”现象。现象。进程号进程号磁道号磁道号移动磁道数移动磁道数713401419258232051322561492940163229114191012190341811731563763733339620设：磁头当前位置为134磁

16、道，现有一磁盘读写请求队列为：3、18、19、19、29、40、56、134、192、205、376、396，若采用SSTF优先磁盘调度算法进行调度，给出调度的次序。磁盘请求序列：3、18、19、19、29、40、56、134、192、205、376、396答：无饥饿现象的磁盘调度算法有答：无饥饿现象的磁盘调度算法有FCFS、扫描算法等等。、扫描算法等等。2022-5-2313习题五：磁盘空闲块的成组分配算法习题五：磁盘空闲块的成组分配算法 参看下图，现有某一进程的文件要释放三个物理块，其块参看下图，现有某一进程的文件要释放三个物理块，其块号为号为150#，152#，160#，试给出其释放过程和释放后的，试给出其释放过程和释放后的卷资源表卷资源表filsys的状况。其后，又有一个文件要求分配的状况。其后，又有一个文件要求分配4个个空闲块，试给出其分配过程和分配后的空闲块，试给出其分配过程和分配后的filsys状况：状况：s-nfree：980 1201 121 96 14597 210 卷资源表卷资源表filsyss-nfree：990 1201 121 96 14597 21098 150 s-nfree：1000 1201 121 96 14597 21098 15099 152 160#s-nfree：10 160