(6)--9.2操作系统原理课件.ppt

《(6)--9.2操作系统原理课件.ppt》由会员分享，可在线阅读，更多相关《(6)--9.2操作系统原理课件.ppt（20页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、9.2几种经典调度算法 几种经典的短程调度算法先来先服务(FCFS)轮转(RR)最短进程优先(SPN)最短剩余时间优先(SRT)最高响应比优先(HRRN)多级反馈几种经典的短程调度算法以此进程集合为例。假设：不考虑I/O。“服务时间”就是作业所需要的整个执行时间，或者是进程所需的CPU运算时间。进程进程到达时刻到达时刻服务时间服务时间A03B26C44D65E82先来先服务First Come First Serve调度最先进入就绪队列的进程，直至运行完或阻塞时，再重新调度。FCFS进程运行轨迹EDCBA2.568.60612202.412182.259131.1779133归一化周转时间（T

2、r/Ts）周转时间（Tr）完成时刻25463服务/执行时间（Ts）86420到达时刻平均平均EDCBA先来先服务：进程轮转Round Robin各进程按提交顺序排成就绪队列，然后依次占用处理机，运行某一时间片(通常10-200 ms)，时间片完则排入就绪队列尾。时间片的长度：关键参数时间片q 太大 相当于FCFS，响应慢。时间片q 太小 上下文切换频繁，开销大。采用轮转法，q=4时，进程运行轨迹：注意就绪队列变化2.715.52.81.752.511011147153192011173归一化周转时间（Tr/Ts）周转时间（Tr）完成时刻25463服务/执行时间（Ts）86420到达时刻平均ED

3、CBA轮转（q=4）：进程02456137911810131215141716191820EDCBAq=4就绪队列：CDBDBEEDBED使得每个进程的使得每个进程的响应速度会更快响应速度会更快 最短进程优先Shortest Process Next调度CPU执行时间预期最短的进程，直至运行完或阻塞时，再重新调度。利于短进程；不利于长进程及紧迫任务。最短进程优先SPN1.51.842.82.751.17137.614117311201593915113028E平均值56D44C62B30ATr/Ts周转时间Tr结束时刻开始时刻执行时间Ts提交时刻进程0245613791181013121514

4、1716191820ABCED最短剩余时间Shortest Remaining Time新进程到达时，若新进程的预计运行时间比当前进程的剩余运行时间更短，则抢占当前进程。最短剩余时间优先SRT1.5912.812.1717.2214413310208153归一化周转时间（Tr/Ts）周转时间（Tr）完成时刻25463服务/执行时间（Ts）86420到达时刻平均EDCBA最短剩余时间优先：进程ACED02456137911810131215141716191820剩余时间:A:1B:6BB:5C:4B:5C:2D:5B:5D:5E:2B:5D:5BD:5最高响应比优先Highest Respon

5、se Ratio Next综合了FCFS和SPN算法当前进程完成或阻塞时发生调度。每次调度前，计算所有就绪进程的响应比，高者优先。响应比R=周转时间执行时间最高响应比优先Highest Response Ratio Next实际上，响应比就是一个进程在某一时刻的“归一化周转时间(即 带权周转时间)”。响应比R=周转时间执行时间=等待时间+执行时间执行时间等待时间越长，响应比越大。执行时间越短，响应比越大。最高响应比优先算法 HRRN02456137911810131215141716191820ABCEDn 在A运行完时（时刻3），B的响应比为：(1+6)/6=1.17。调度B运行。n 在B运

6、行完时（时刻9），C、D、E的响应比分别为：C=(5+4)/4=2.25；D=(3+5)/5=1.6；E=(1+2)/2=1.5。调度C运行。n 在C运行完时（时刻13），D、E的响应比分别为：D=(7+5)/5=2.4；E=(5+2)/2=3.5。调度E运行。n 在E运行完时（时刻15），D的响应比为：(9+5)/5=2.8。调度D运行。最高响应比优先算法 HRRN2.143.52.82.251.171871497315201393归一化周转时间（Tr/Ts）周转时间（Tr）完成时刻25463服务/执行时间（Ts）86420到达时刻平均EDCBA最高响应比优先：进程反馈(多级反馈队列)Mul

7、tilevel Feedback基于时间片的抢占+动态优先级调度。设立多个就绪队列，优先级越高的队列，其时间片越小；就绪队列0（q0=8ms,FCFS）就绪队列1（q1=16ms,FCFS）就绪队列2（q2=32ms,FCFS）就绪队列 n（qn=x ms,RR）同一队列内进程按FCFS调度，但末级队列按轮转法调度。当进程在一个时间片内未运行完，则降到下一级队列末尾；当上级队列均无进程就绪时，才调度本级队列内进程；实用，能较好地满足交互型进程、短进程、长进程的要求。就绪队列0（q0=8ms,FCFS）就绪队列1（q1=16ms,FCFS）就绪队列2（q2=32ms,FCFS）就绪队列 n（qn=x ms,RR）新进程CPUCPUCPUCPU性能比较先来先服务FCFS：简单，偏向长进程，平均周转时间长。轮转RR：公平。所有进程的带权周转时间比较平均。最短进程优先SPN：对于大多数进程来说，带权周转时间优于轮转。性能比较最短剩余时间SRT：由于抢占，效率优于SPN。最高响应比优先HRRN：性能介于FCFS和SPN之间。反馈FB：短进程的带权周转时间短。