作系统 习题解析.ppt

* * 习题分析 习题一：进程调度 习题二：P/V操作例子 习题三：页式存储管理中的一级页表地址计算 习题四：磁盘调度SSTF存在的问题 习题五：磁盘空闲块的成组分配算法 * * 习题一：进程调度 有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）。 * * 答案 新进程出现，重新调度，新进程的优先级与当前正运行进程比较，抢占发生。 时间片用完，进程切换，就绪队列中的首进程投入运行，换下来的进程按其优先级插入到就绪队列中，体现轮转与优先级各自的特点 可能引起调度CPU的时机： 进程运行结束时 进程的时间片用完时（RR） 进程申请资源未得到满足时(被阻塞) 拥有更高的优先级的进程到达时 可看成是 抢占式的FCFS * * PRR的其它应用 PRR应用的参考文献： 题目：Priority Ruond-Robin Scheduling for Very Large Virtual Environment 作者： Chris Faisstnauer Dieter Schmalstieg Werner Purgathofer 所属单位：Vienna University of Technology, Austria 奥地利维也纳科技大学 邮件地址：faisst@cg.tuwien.ac.at 检索网址：/xpls/abs_all.jsp?arnumber=840491 * * 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 优先级 * * 习题二：P/V操作的应用 某公司有两个生产部门和一个装配部门，两个生产部门分别生产甲、乙两种零件，装配部门的任务是把甲、乙两种零件组装成产品。两个生产部门每生产一个零件后都要分别把它们送到装配部门的货架S1、S2上。S1存放零件甲，S2存放零件乙，S1和S2均可容纳20个零件。装配人员每次从货架上取走一个甲零件和一个乙零件后，将其组装成产品。请利用P、V操作控制各部门之间使用零件的货架规则，保证零件入/出货架的正确性。 * * 算法描述 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和