《操作系统第9章单处理器调度.ppt》由会员分享，可在线阅读，更多相关《操作系统第9章单处理器调度.ppt（30页珍藏版）》请在三一办公上搜索。
1、1,第9章 单处理器调度,主要内容9.1 处理器调度的类型9.2 调度算法9.3 传统的UNIX调度,2,9.1 处理器调度的类型,3,9.1.1 长程调度,何时调度？有作业终止时处理器的空余时间片超过了一定的阈值调度哪个？先来先服务优先级实时性I/O需求,4,9.1.2 中程调度,换入：取决于管理系统并发度的要求；换出：进程的存储需求。9.1.3 短程调度长程调度程序执行频率较低；中程调度程序执行频率稍高；短程调度程序执行频率最高。分派程序，精确地决定下一次执行哪一个进程。,5,9.2 调度算法 9.2.1 短程调度准则,面向用户的准则单个用户或进程感知到的系统行为例：响应时间面向系统的准则
2、处理器使用的效果和效率例：吞吐量与性能相关的准则是定量的，可以很容易地度量例：响应时间和吞吐量与性能无关的准则或者本质上是定性的，或者不容易测量和分析例：可预测性,6,调度准则,1、面向用户，与性能相关周转时间从提交到完成之间的时间间隔响应时间从提交到开始接收响应之间的时间间隔最后期限进程完成的最后期限2、面向用户，与性能无关可预测性希望提供给用户的服务能够随着时间的流逝展现给用户一贯相同的特性，而与系统执行的其他工作无关。,7,3、面向系统，与性能相关,吞吐量单位时间内完成的进程数目处理器利用率处理器处于忙的状态的时间百分比4、面向系统，与性能无关公平性进程被平等对待强制优先级进程被指定优先
3、级，调度策略优先选择高优先级进程。平衡资源保持系统中所有资源处于繁忙状态，较少适用紧缺资源的进程应该受到照顾。,8,9.2.2 优先级的使用,每个进程被指定一个优先级，调度程序总是选择具有较高优先级的进程。纯粹的优先级调度方案可能会导致低优先级进程长时间处于饥饿状态；一个进程的优先级可随着它的时间或执行历史而变化。,9,9.2.3 选择调度策略,选择函数确定在就绪进程中选择哪一个进程在下一次执行。决策模式非抢占抢占调度准则周转时间Tr归一化周转时间Tr/Ts,10,1、先来先服务 FCFS,0 3 9 13 18 20平均周转时间：(3+7+9+12+12)/5=8.6平均归一化周转时间：(1
4、+1.17+2.25+2.4+6)/5=2.56,11,2、轮转 RR（1）q=1,0 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 20平均周转时间：(4+16+13+14+7)/5=10.8平均归一化周转时间：(1.33+2.67+3.25+2.8+3.5)/5=2.71,12,2、轮转 RR（1）q=4,0 3 7 11 15 17 19 20平均周转时间：(3+15+7+14+11)/5=10平均归一化周转时间：(1+2.5+1.75+2.8+5.5)/5=2.71,13,3、最短进程优先 SPN,0 3 9 11 15 20平均周转时间：(3+
5、7+11+14+3)/5=7.6平均归一化周转时间：(1+1.17+2.75+2.8+1.5)/5=1.84,14,4、最短剩余时间 SRT,0 3 4 8 10 15 20平均周转时间：(3+13+4+14+2)/5=7.2平均归一化周转时间：(1+2.17+2+2.8+1)/5=1.59,15,5、最高响应比优先 HRRN,R=(w+s)/sR：响应比w：等待处理器的时间s：预计的服务时间,16,5、最高响应比优先 HRRN,0 3 9 13 15 20平均周转时间：(3+7+9+14+7)/5=8平均归一化周转时间：(1+1.17+2.25+2.8+3.5)/5=2.14,B运行完，计算
6、CDE的响应比：RC=(5+4)/4=2.25RD=(3+5)/5=1.6RE=(1+2)/2=1.5C运行完，计算DE的响应比：RD=(7+5)/5=2.4RE=(5+2)/2=3.5,17,6、优先级,静态优先级动态优先级抢占非抢占约定：数小代表优先级高,18,非抢占优先级,0 3 9 14 18 20平均周转时间：(3+7+14+8+12)/5=8.8平均归一化周转时间：(1+1.17+3.5+1.6+6)/5=2.65,19,抢占优先级,0 2 6 11 13 14 18 20平均周转时间：(14+11+14+5+12)/5=11.2平均归一化周转时间：(4.67+1.83+3.5+1
7、+6)/5=3.4,20,7、反馈法,21,综合练习题,进程 到达时间 服务时间 优先级 P1 0 20 2 P2 5 15 3 P3 10 5 1 P4 15 10 4 FCFS、SPN、SRT、优先级（抢占、非抢占）、RR（时间片5）、最高响应比优先计算平均周转时间,22,1、FCFS,0 20 35 40 50平均周转时间:20+(35-5)+(40-10)+(50-15)/4=115/4=28.75,进程 到达时间 服务时间 优先级 P1 0 20 2 P2 5 15 3 P3 10 5 1 P4 15 10 4,23,2、SPN,0 20 25 35 50平均周转时间:20+(50-
8、5)+(25-10)+(35-15)/4=100/4=25,进程 到达时间 服务时间 优先级 P1 0 20 2 P2 5 15 3 P3 10 5 1 P4 15 10 4,24,2、SRT,0 10 15 25 35 50平均周转时间:25+(50-5)+(15-10)+(35-15)=95/4=23.75,进程 到达时间 服务时间 优先级 P1 0 20 2 P2 5 15 3 P3 10 5 1 P4 15 10 4,25,3、优先级（非抢占）,0 20 25 40 50平均周转时间:20+(40-5)+(25-10)+(50-15)/4=105/4=26.25,进程 到达时间 服务时
9、间 优先级 P1 0 20 2 P2 5 15 3 P3 10 5 1 P4 15 10 4,26,3、优先级（抢占）,0 10 15 25 40 50平均周转时间:25+(40-5)+(15-10)+(50-15)=100/4=25,进程 到达时间 服务时间 优先级 P1 0 20 2 P2 5 15 3 P3 10 5 1 P4 15 10 4,27,4、RR（5）,0 5 10 15 20 25 30 35 40 45 50平均周转时间:50+(40-5)+(20-10)+(45-15)/4=125/4=31.25,进程 到达时间 服务时间 优先级 P1 0 20 2 P2 5 15 3
10、 P3 10 5 1 P4 15 10 4,28,5、最高响应比优先,0 20 25 40 50 平均周转时间:20+(40-5)+(25-10)+(50-15)/4=105/4=26.25,进程 到达时间 服务时间 优先级 P1 0 20 2 P2 5 15 3 P3 10 5 1 P4 15 10 4,P1运行完，计算P2P3P4的响应比：RP2=(15+15)/15=2RP3=(10+5)/5=3RP4=(5+10)/10=1.5P3运行完，计算P2P4的响应比：RP2=(20+15)/15=2.3RP4=(10+10)/10=2,29,9.3 传统的UNIX调度,多级反馈每个优先级队列中使用轮转方法使用1秒抢占方式每秒都会重新计算每个进程的优先级,30,作业,复习题 9.1 9.5习题 9.16（要求计算平均周转时间和平均归一化周转时间）,
