操作系统习题解析.ppt

2019/7/25,1,习题分析,习题一：进程调度 习题二：P/V操作例子 习题三：页式存储管理中的一级页表地址计算 习题四：磁盘调度SSTF存在的问题 习题五：磁盘空闲块的成组分配算法,2019/7/25,2,习题一：进程调度,有5个进程如下表。时间从0开始，单位为1，最高优先级为0. 进程 到达时间 优先级 所需运行时间 A 0 2 3 B 2 3 8 C 4 4 6 D 6 1 5 E 8 0 4 绘图说明以下进程调度过程：（1 CPU系统，所有进程只使用CPU）。 请使用时间为横向坐标轴，并请在图中标明每个进程的“等待”和“运行”两种状态。 先来先服务（FCFS）。 轮转调度（Round-Robin） 时间片=2。 优先级轮转法（Priority Round-Robin） 时间片=2。 最短进程优先算法（Shortest Process Next）。,2019/7/25,3,答案,可能引起调度CPU的时机： 进程运行结束时 进程的时间片用完时（RR） 进程申请资源未得到满足时(被阻塞) 拥有更高的优先级的进程到达时,可看成是 抢占式的FCFS,2019/7/25,4,PRR的其它应用,PRR应用的参考文献： 题目：Priority Ruond-Robin Scheduling for Very Large Virtual Environment 作者： Chris Faisstnauer Dieter Schmalstieg Werner Purgathofer 所属单位：Vienna University of Technology, Austria 奥地利维也纳科技大学 邮件地址：faisstcg.tuwien.ac.at 检索网址：/xpls/abs_all.jsp?arnumber=840491,2019/7/25,5,Basic Priority Round-Robin,Selected elements: A,C,G - B,D,G - A,E,G - B,F,G,循环计数 = 每个级别上的进程数目 * 优先级层次总数 本例中，优先级分为3个层次，分别为：0级/1级/2级,i=0 i=1 i=2,优先级,2019/7/25,6,习题二：P/V操作的应用,某公司有两个生产部门和一个装配部门，两个生产部门分别生产甲、乙两种零件，装配部门的任务是把甲、乙两种零件组装成产品。两个生产部门每生产一个零件后都要分别把它们送到装配部门的货架S1、S2上。S1存放零件甲，S2存放零件乙，S1和S2均可容纳20个零件。装配人员每次从货架上取走一个甲零件和一个乙零件后，将其组装成产品。请利用P、V操作控制各部门之间使用零件的货架规则，保证零件入/出货架的正确性。,2019/7/25,7,算法描述,Begin 信号量初值： mutex1:=1; mutex2:=1; empty1:=20; full1:=0; empty2:=20; full2:=0 Cobegin A部门： begin Repeat 生产一个产品A; P(empty1); P(mutex1); 将产品A放入S1; V(mutex1); V(full1); Until false End,B部门： begin Repeat 生产一个产品B; P(empty2); P(mutex2); 将产品B放入S2; V(mutex2); V(full2); Until false End,装配人员：begin Repeat P(full1); P(full2); P(mutex1); 从S1中取出产品A; V(mutex1); V(empty1); P(mutex2); 从S2中取出产品B; V(mutex2); V(empty2); 把A和B组装成产品 Until false End Coend End;,2019/7/25,8,习题三：确定页表位置习题,一个32位的虚拟存储系统有两级页表，其逻辑地址中，第22到31位是第一级页表，12位到21位是第二级页表，页内偏移占0到11位。一个进程的地址空间为4GB，如果从0XC0000000开始映射 4MB大小页表，请问第一级页表所占的4KB空间映射在什么位置，并说明理由。（注意B代表字节，一个32位地址占4字节）,2019/7/25,9,习题三：续一,虚拟地址空间 0= 0X00000000 3G= 0XC0000000 第768K个页面 4G-1= 0XFFFFFFFF,4MB页表所在位置 （全部页表占1K个页面）,二级页表 每块1024项 4KB大小 每项代表1页=4KB,一级页表4KB,： ： ：,： ： ：,一个32位的虚拟存储系统有两级页表，其逻辑地址中，第22到31位是第一级页表，12位到21位是第二级页表，页内偏移占0到11位。一个进程的地址空间为4GB，如果从0XC0000000开始映射4MB大小页表，请问第一级页表所占的4KB空间映射在什么位置，并说明理由。（注意B代表字节，一个32位地址占4字节）,31,0,21,11,1页=4KB,4GB虚拟空间共1M个页面,第768项,第768项,0页,1023页,1024页,2047页,第768块,7681024+768,： ： ：,： ： ：,2019/7/25,10,习题三-续二,虚拟地址空间 0 3G,4MB页表所在位置 （有1K个页面）,二级页表,一级页表所在位置 768页表块 即：7681024项开始,一级页表4KB,共有1024项 每项占4B,共有1M个页表项 1M4B大小 =4MB大小,一个32位的虚拟存储系统有两级页表，其逻辑地址中，第22到31位是第一级页表，12位到21位是第二级页表，页内偏移占0到11位。一个进程的地址空间为4GB，如果从0XC0000000开始映射 4MB大小页表，请问第一级页表所占的4KB空间映射在什么位置，并说明理由。（注意B代表字节，一个32位地址占4字节）,. . .,第0项 第768项,0xC0000000+(0xC000000012)2)= 0xC0000000+0x00300000=0xC0300000 第一级页表所占的4KB空间的虚拟地址范围是：0xC03000000xC300FFF,2019/7/25,11,磁盘调度算法,Ts= m n + s，寻道时间 其中：m为常数；n为移动磁道数；s为启动磁盘时间 Tr旋转延迟时间：硬盘大约8.3ms，软盘50ms100ms Tt 传输时间：读/写数据的实际时间=b/(rN) b:读写字节数；r:磁盘转速；N:每条磁道上的字节数。 磁盘访问时间 Ta = Ts + Tr + Tt,2019/7/25,12,习题四：SSTF磁盘调度存在的问题,应用SSTF (shortest-seek-time-first)调度策略，某些进程可能永远不能被调度到 假定每当在满足磁道376上的信息请求之前，系统总会接收到一个新的请求流，而且这些请求所要移动磁头的距离总小于达到磁道376所移动的距离，因而，对于376磁道和396磁道上的信息请求将永远得不到满足。 试设计一种磁盘访问调度算法，以确保不会发生诸如上例的“饥饿”现象。,设：磁头当前位置为134磁道，现有一磁盘读写请求队列为：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、扫描算法等等。,2019/7/25,13,习题五：磁盘空闲块的成组分配算法,参看下图，现有某一进程的文件要释放三个物理块，其块号为150#，152#，160#，试给出其释放过程和释放后的卷资源表filsys的状况。其后，又有一个文件要求分配4个空闲块，试给出其分配过程和分配后的filsys状况：,s-nfree：98 0 120 1 121 96 145 97 210 卷资源表filsys,s-nfree：99 0 120 1 121 96 145 97 210 98 150 ,s-nfree：100 0 120 1 121 96 145 97 210 98 150 99 152 ,s-nfree：1 0 160 1 96 97 卷资源表filsys,2019/7/25,14,习题五：续,s-nfree：100 0 120 1 121 96 145 97 210 98