操作系统习题解析

习题分析习题一：进程调度习题二：P/V操作例子习题三：页式存储管理中的一级页表地址计算习题四：磁盘调度SSTF存在的问题习题五：磁盘空闲块的成组分配算法5/22/20231习题一：进程调度有5个进程如下表。时间从0开始，单位为1，最高优先级为0.进程到达时间优先级所需运行时间A023B238C446D615E804绘图说明以下进程调度过程：（1CPU系统，所有进程只使用CPU）。请使用时间为横向坐标轴，并请在图中标明每个进程的“等待”和“运行”两种状态。先来先服务（FCFS）。轮转调度（Round-Robin）时间片=2。优先级轮转法（PriorityRound-Robin）时间片=2。最短进程优先算法（ShortestProcessNext）。5/22/20232答案新进程出现，重新调度，新进程的优先级与当前正运行进程比较，抢占发生。时间片用完，进程切换，就绪队列中的首进程投入运行，换下来的进程按其优先级插入到就绪队列中，体现轮转与优先级各自的特点可能引起调度CPU的时机：进程运行结束时进程的时间片用完时（RR）进程申请资源未得到满足时(被阻塞)拥有更高的优先级的进程到达时可看成是抢占式的FCFS5/22/20233PRR的其它应用PRR应用的参考文献：题目：PriorityRuond-RobinSchedulingforVeryLargeVirtualEnvironment作者： ChrisFaisstnauer DieterSchmalstieg WernerPurgathofer所属单位：ViennaUniversityofTechnology,Austria

奥地利维也纳科技大学邮件地址：faisst@cg.tuwien.ac.at检索网址：/xpls/abs_all.jsp?arnumber=8404915/22/20234BasicPriorityRound-RobinSelectedelements:A,C,G-B,D,G-A,E,G-B,F,G循环计数

=每个级别上的进程数目

*优先级层次总数本例中，优先级分为3个层次，分别为：0级/1级/2级i=0i=1i=2优先级5/22/20235习题二：P/V操作的应用某公司有两个生产部门和一个装配部门，两个生产部门分别生产甲、乙两种零件，装配部门的任务是把甲、乙两种零件组装成产品。两个生产部门每生产一个零件后都要分别把它们送到装配部门的货架S1、S2上。S1存放零件甲，S2存放零件乙，S1和S2均可容纳20个零件。装配人员每次从货架上取走一个甲零件和一个乙零件后，将其组装成产品。请利用P、V操作控制各部门之间使用零件的货架规则，保证零件入/出货架的正确性。5/22/20236算法描述Begin信号量初值：mutex1:=1;mutex2:=1;empty1:=20;full1:=0;empty2:=20;full2:=0CobeginA部门：beginRepeat生产一个产品A;P(empty1);P(mutex1);将产品A放入S1;V(mutex1);V(full1);UntilfalseEndB部门：begin Repeat 生产一个产品B; P(empty2); P(mutex2); 将产品B放入S2; V(mutex2); V(full2); UntilfalseEnd装配人员：begin Repeat P(full1); P(full2); P(mutex1); 从S1中取出产品A; V(mutex1); V(empty1); P(mutex2); 从S2中取出产品B; V(mutex2); V(empty2); 把A和B组装成产品 Untilfalse End CoendEnd;5/22/20237习题三：确定页表位置习题一个32位的虚拟存储系统有两级页表，其逻辑地址中，第22到31位是第一级页表，12位到21位是第二级页表，页内偏移占0到11位。一个进程的地址空间为4GB，如果从0XC0000000开始映射

4MB大小页表，请问第一级页表所占的4KB空间映射在什么位置，并说明理由。（注意B代表字节，一个32位地址占4字节）

第一级页表项第二级页表项

页内相对位移31021115/22/20238习题三：续一虚拟地址空间0=0X000000003G=0XC0000000第768K个页面4G-1=0XFFFFFFFF4MB页表所在位置（全部页表占1K个页面）二级页表每块1024项4KB大小每项代表1页=4KB一级页表4KB共有1024项,每项代表1k个页表项=1M页=4MB7684MB=3G一级页表所在位置第768块页表是3G虚拟地址映射位置共有1024个页表块(页表页面)1M个页表项，总共占4MB大小内存。1M个页表项可表示1M×4K=4G内存其中包括了一级页表的4K区域。...：：：............：：：一个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：：：：：：5/22/20239习题三-续二虚拟地址空间03G4MB页表所在位置（有1K个页面）二级页表一级页表所在位置768页表块即：768×1024项开始一级页表4KB共有1024项每项占4B共有1M个页表项1M×4B大小=4MB大小...一个32位的虚拟存储系统有两级页表，其逻辑地址中，第22到31位是第一级页表，12位到21位是第二级页表，页内偏移占0到11位。一个进程的地址空间为4GB，如果从0XC0000000开始映射

4MB大小页表，请问第一级页表所占的4KB空间映射在什么位置，并说明理由。（注意B代表字节，一个32位地址占4字节）

...第0项第768项0xC0000000+((0xC0000000>>12)<<2)=0xC0000000+0x00300000=0xC0300000第一级页表所占的4KB空间的虚拟地址范围是：0xC0300000~0xC300FFF5/22/202310磁盘调度算法寻道时间旋转延迟时间Ts=mn+s，寻道时间其中：m为常数；n为移动磁道数；s为启动磁盘时间Tr旋转延迟时间：硬盘大约8.3ms，软盘50ms~100msTt传输时间：读/写数据的实际时间=b/(rN)b:读写字节数；r:磁盘转速；N:每条磁道上的字节数。磁盘访问时间

Ta=Ts+

Tr+Tt

5/22/202311习题四：SSTF磁盘调度存在的问题应用SSTF(shortest-seek-time-first)调度策略，某些进程可能永远不能被调度到假定每当在满足磁道376上的信息请求之前，系统总会接收到一个新的请求流，而且这些请求所要移动磁头的距离总小于达到磁道376所移动的距离，因而，对于376磁道和396磁道上的信息请求将永远得不到满足。试设计一种磁盘访问调度算法，以确保不会发生诸如上例的“饥饿”现象。进程号磁道号移动磁道数713401419258232051322561492940163229114191012190341811731563763733339620设：磁头当前位置为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、扫描算法等等。5/22/202312习题五：磁盘空闲块的成组分配算法参看下图，现有某一进程的文件要释放三个物理块，其块号为150#，152#，160#，试给出其释放过程和释放后的卷资源表filsys的状况。其后，又有一个文件要求分配4个空闲块，试给出其分配过程和分配后的filsys状况：s-nfree：98[0]120[1]121

……[96]145[97]210

……

卷资源表filsyss-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……160#s-nfree：1[0]

160[1]

…[96]

[97]

…卷资源表filsys5/22/202313习题五：续s-nfree：100[0]120[1]121

……[96]145[97]210[98]150[99]152……160#s-nfree：99[0]120[1]121

……[96]145[97]210[98]150

……s-nfree：98[0]120[1]