4进程调度.pptx

《4进程调度.pptx》由会员分享，可在线阅读，更多相关《4进程调度.pptx（25页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、12022-5-24处理机调度概述处理机调度概述处理机调度（处理机调度（CPUCPU调度）调度）要解决的问题：要解决的问题： WHATWHAT：按什么原则分配：按什么原则分配CPUCPU调度算法调度算法 WHENWHEN：何时分配：何时分配CPUCPU调度的时机调度的时机 HOWHOW： 如何分配如何分配CPUCPUCPUCPU调度过程（进程的上下调度过程（进程的上下文切换）文切换）处理机调度的三个层次（类型）处理机调度的三个层次（类型）高级调度（作业调度）高级调度（作业调度）中级调度中级调度 ( 交换调度交换调度 )低级调度（进程调度）低级调度（进程调度）22022-5-24高级调度高级调度

2、什么是高级调度什么是高级调度 也称为也称为作业调度作业调度(长程调度、宏观调度、接纳调长程调度、宏观调度、接纳调度），一般在度），一般在批处理系统批处理系统中有作业调度。中有作业调度。 按一定原则对外存输入井上的作业进行调度，按一定原则对外存输入井上的作业进行调度，并建立进程并建立进程PCBPCB。作业一旦被系统收容，就变成。作业一旦被系统收容，就变成进程或进程组。进程或进程组。高级调度内容高级调度内容 接纳多少作业接纳多少作业 接纳哪些作业接纳哪些作业32022-5-24中级调度中级调度 什么是中级调度什么是中级调度 又称：平衡负载调度，中程调度。又称：平衡负载调度，中程调度。 决定将外存上

3、的哪些重又具备运行条件的就绪进程重新调入决定将外存上的哪些重又具备运行条件的就绪进程重新调入内存，等待进程调度。内存，等待进程调度。 中级调度内容中级调度内容 涉及进程在内外存间的交换，涉及进程在内外存间的交换，中级调度根据存储资源量和进中级调度根据存储资源量和进程的当前状态来决定辅存和主存中进程的对换。程的当前状态来决定辅存和主存中进程的对换。 从存储器资源管理的角度来看，把进程的部分或全部换出到从存储器资源管理的角度来看，把进程的部分或全部换出到外存上，可为当前运行进程的执行提供所需内存空间外存上，可为当前运行进程的执行提供所需内存空间 作用作用 为了提高内存的利用率和系统吞吐量为了提高内

4、存的利用率和系统吞吐量42022-5-24进程调度概念进程调度概念 又称微观调度、又称微观调度、低级调度低级调度、短程调度、短程调度、处理机调度处理机调度。 控制协调进程对控制协调进程对CPUCPU的竞争，即按一定的调度的竞争，即按一定的调度算法从就绪队列中选中一个进程，把算法从就绪队列中选中一个进程，把CPUCPU的使用权的使用权交给被选中的进程。交给被选中的进程。 操作系统中实现进程调度的程序称为操作系统中实现进程调度的程序称为进程进程( (线线程程) )调度程序调度程序，或分派程序，或分派程序(Dispatcher)(Dispatcher)，常驻内，常驻内存。存。 进程调度程序是操作系统

5、最为核心的部分，进进程调度程序是操作系统最为核心的部分，进程调度策略的优劣直接影响到整个系统的性能。程调度策略的优劣直接影响到整个系统的性能。52022-5-24处理器调度层次图示处理器调度层次图示中级调度中级调度新建态新建态挂起就绪挂起就绪态态挂起等待挂起等待态态高级调度高级调度低级调度低级调度运行态运行态就绪态就绪态等待态等待态终止终止态态62022-5-24处理器调度与进程状态转换处理器调度与进程状态转换高级高级调度调度中级调中级调度度低级低级调度调度运行态运行态就绪态就绪态终止态终止态新建态新建态挂起就绪态挂起就绪态中级中级调度调度挂起等待态挂起等待态等待态等待态高级调度高级调度高级调

6、度高级调度中级中级调度调度72022-5-24进程调度方式进程调度方式非抢占方式非抢占方式(Non-preemptive Non-preemptive ） 某一进程被调度运行后，除非由于它自身的原因某一进程被调度运行后，除非由于它自身的原因不能运行，否则一直运行下去。不能运行，否则一直运行下去。抢占方式抢占方式(Preemptive(Preemptive） 当有比正在运行的进程优先级更高的进程就绪时，当有比正在运行的进程优先级更高的进程就绪时，系统可强行剥夺正在运行进程的系统可强行剥夺正在运行进程的CPUCPU，提供给具有更，提供给具有更高优先级的进程使用。高优先级的进程使用。 优先权原则优先

7、权原则 短进程优先原则短进程优先原则 时间片原则时间片原则82022-5-24何时发生进程调度呢何时发生进程调度呢? ? 有四种情况都会发生进程调度有四种情况都会发生进程调度: :当一个进程从运行态切换成阻塞态时；当一个进程从运行态切换成阻塞态时； 当一个进程从运行态切换成就绪态时；当一个进程从运行态切换成就绪态时；当一个进程从阻塞态切换成就绪态时；当一个进程从阻塞态切换成就绪态时；当一个进程中止时。当一个进程中止时。 92022-5-24选择调度方式和算法的准则选择调度方式和算法的准则 调度实质上是一个策略问题，设定的目标往往是相调度实质上是一个策略问题，设定的目标往往是相互冲突的，如何选择

8、取决于操作系统的类型和目标互冲突的，如何选择取决于操作系统的类型和目标. . 面向用户的准则面向用户的准则 周转时间短周转时间短 响应时间快响应时间快 截止时间的保证截止时间的保证 优先权准则优先权准则 面向系统的准则面向系统的准则系统吞吐量高系统吞吐量高处理机利用率高处理机利用率高 各类资源的平衡利用各类资源的平衡利用102022-5-24调度算法性能衡量调度算法性能衡量 周转时间周转时间 如果进程如果进程i i进入内存的时刻是进入内存的时刻是t ts s，完成时刻是，完成时刻是t tf f，该进程的周转，该进程的周转时间时间t ti i为：为：t ti i = t = tf f - t -

9、 ts s 实际上，它是进程的等待时间与运行时间之和。实际上，它是进程的等待时间与运行时间之和。 平均周转时间平均周转时间 为了提高系统的性能，要让若干个进程的平均周转时间和平均为了提高系统的性能，要让若干个进程的平均周转时间和平均带权周转时间最小。带权周转时间最小。 平均周转时间平均周转时间 T = (tT = (ti i) / n) / n 带权周转时间和平均带权周转时间带权周转时间和平均带权周转时间 如果进程如果进程i i的周转时间为的周转时间为t ti i，所需运行时间为，所需运行时间为t tk k，则称，则称 w wi i=t=ti i /t /tk k为该进程的带权周转时间。为该进

10、程的带权周转时间。 t ti i是等待时间与运行时间之和，故带权周转时间总大于是等待时间与运行时间之和，故带权周转时间总大于1 1。 平均带权周转时间平均带权周转时间W = (wW = (wi i) / n) / n112022-5-24调度算法调度算法 先来先服务算法（先来先服务算法（FCFS） 最短进程优先算法（最短进程优先算法（SJF） 最短剩余时间优先调度算法（最短剩余时间优先调度算法（SRTF） 最高响应比优先调度算法（最高响应比优先调度算法（HRRF） 高优先权优先调度算法（高优先权优先调度算法（HPF） 基于时间片的轮转调度算法（基于时间片的轮转调度算法（RR） 多级反馈队列调度

11、算法多级反馈队列调度算法122022-5-24 进程进程 进入时间进入时间 估计运行估计运行时间时间 （分钟）（分钟） 开始时间开始时间 结束时间结束时间 周转时间周转时间 （分钟）（分钟） 带权周转带权周转时间时间 A 8：00 120 B 8：50 50 C 9：00 10 D 9：50 20 进程平均周转时间进程平均周转时间 T = 进程带权平均周转时间进程带权平均周转时间 W = 先来先服务调度算法先来先服务调度算法FCFS调度算法调度算法 按照进程进入就绪队列的先后次序来选择。按照进程进入就绪队列的先后次序来选择。 调度方式采用调度方式采用非抢占方式非抢占方式。例例优点优点实现简单实

12、现简单缺点缺点算法只顾及进程的等候时间，没考虑进程要求服务时间的长短；算法只顾及进程的等候时间，没考虑进程要求服务时间的长短；不利于短进程而优待了长进程；不利于短进程而优待了长进程；没考虑进程的优先级。没考虑进程的优先级。 进程进程 进入时间进入时间 估计运行估计运行时间时间 （分钟）（分钟） 开始时间开始时间 结束时间结束时间 周转时间周转时间 （分钟）（分钟） 带权周转带权周转时间时间 A 8：00 120 8：00 10：00 120 1 B 8：50 50 10：00 10：50 120 2.4 C 9：00 10 10：50 11：00 120 12 D 9：50 20 11：00

13、11：20 90 4.5 进程平均周转时间进程平均周转时间 T = 112.5 进程带权平均周转时间进程带权平均周转时间 W = 4.975 450 19.9 132022-5-24算法算法 以进程所要求的以进程所要求的CPUCPU时间为标准，总选取估时间为标准，总选取估计运行时间最短的进程投入运行。计运行时间最短的进程投入运行。 调度方式采用调度方式采用非抢占方式。非抢占方式。例例 进程进程 进入时间进入时间 估计运行估计运行时间时间 （分钟）（分钟） 开始时间开始时间 结束时间结束时间 周转时间周转时间 （分钟）（分钟） 带权周转带权周转时间时间 A 8：00 120 B 8：50 50

14、C 9：00 10 D 9：50 20 进程平均周转时间进程平均周转时间 T = 进程带权平均周转时间进程带权平均周转时间 W = 最短进程优先算法（最短进程优先算法（SPF） 进程进程 进入时间进入时间 估计运行估计运行时间时间 （分钟）（分钟） 开始时间开始时间 结束时间结束时间 周转时间周转时间 （分钟）（分钟） 带权周转带权周转时间时间 A 8：00 120 8：00 10：00 120 1 B 8：50 50 10：30 11：20 150 3 C 9：00 10 10：00 10：10 70 7 D 9：50 20 10：10 10：30 40 2 进程平均周转时间进程平均周转时间

15、 T = 95 进程带权平均周转时间进程带权平均周转时间 W = 3.25 380 13 优点优点算法易于实现。算法易于实现。缺点缺点 忽视了进程等待时间；不利于长进程，会出现饥饿现象。忽视了进程等待时间；不利于长进程，会出现饥饿现象。142022-5-24最短剩余时间优先调度算法最短剩余时间优先调度算法SRTFSRTF 最短剩余时间优先调度算法也称为抢占式的最短剩余时间优先调度算法也称为抢占式的SPFSPF算法算法 基本思想基本思想 一个新进程进入就绪状态，如果新进程一个新进程进入就绪状态，如果新进程需要的需要的CPUCPU时间比当前正在执行的进程剩余时间比当前正在执行的进程剩余下来还需的下

16、来还需的CPUCPU时间短，时间短，SRTFSRTF强行赶走当前强行赶走当前正在执行进程。正在执行进程。 调度方式采用调度方式采用抢占方式抢占方式。152022-5-24最短剩余时间优先调度最短剩余时间优先调度SRTFSRTF算法示例算法示例 进程进程 进入时间进入时间 估计运行估计运行时间时间 （分钟）（分钟） 开始时间开始时间 结束时间结束时间 周转时间周转时间 （分钟）（分钟） 带权周转带权周转时间时间 A 8：00 120 B 8：50 50 C 9：00 10 D 9：50 20 进程平均周转时间进程平均周转时间 T = 进程带权平均周转时间进程带权平均周转时间 W = 进程进程 进

17、入时间进入时间 估计运行估计运行时间时间 （分钟）（分钟） 开始时间开始时间 结束时间结束时间 周转时间周转时间 （分钟）（分钟） 带权周转带权周转时间时间 A 8：00 120 8:00 11:20 200 1.67 B 8：50 50 8:50 9:50 60 1.2 C 9：00 10 9:00 9:10 10 1 D 9：50 20 9:50 10:10 20 1 进程平均周转时间进程平均周转时间 T = 72.5 进程带权平均周转时间进程带权平均周转时间 W = 1.2175 290 4.87 优点优点可以用于分时系统，保证及时响应用户要求。可以用于分时系统，保证及时响应用户要求。缺

18、点缺点系统开销增加，首先要保存进程的运行情况记录，以比较其剩余时间大小；系统开销增加，首先要保存进程的运行情况记录，以比较其剩余时间大小；其次，抢占本身也要消耗处理机时间其次，抢占本身也要消耗处理机时间162022-5-24 响应比响应比 R = 周转时间周转时间 / 运行时间运行时间 =（运行时间（运行时间+等待时间）等待时间）/ 运行时间运行时间 = 1 +（等待时间（等待时间 / 运行时间）运行时间） 短进程容易得到较高响应比；短进程容易得到较高响应比； 长进程等待时间足够长后，也将获得足够高的响应比；长进程等待时间足够长后，也将获得足够高的响应比； 饥饿现象不会发生饥饿现象不会发生例例

19、 进程进程 进入时间进入时间 估计运行估计运行时间时间 （分钟）（分钟） 开始时间开始时间 结束时间结束时间 周转时间周转时间 （分钟）（分钟） 带权周转带权周转时间时间 A 8：00 120 B 8：50 50 C 9：00 10 D 9：50 20 进程平均周转时间进程平均周转时间 T = 进程带权平均周转时间进程带权平均周转时间 W = 最高响应比最高响应比(HRRF)(HRRF)优先调度算法优先调度算法 进程进程 进入时间进入时间 估计运行估计运行时间时间 （分钟）（分钟） 开始时间开始时间 结束时间结束时间 周转时间周转时间 （分钟）（分钟） 带权周转带权周转时间时间 A 8：00

20、120 8:00 10:00 120 1 B 8：50 50 10:10 11:00 130 2.6 C 9：00 10 10:00 10:10 70 7 D 9：50 20 11:00 11:20 90 4.5 进程平均周转时间进程平均周转时间 T = 102.5 进程带权平均周转时间进程带权平均周转时间 W = 3.775 410 15.1 172022-5-24高优先权调度算法高优先权调度算法HPF（1） 算法思想算法思想 从就绪队列中选择优先权最高的进程投入运行。从就绪队列中选择优先权最高的进程投入运行。 调度算法类型调度算法类型 非抢占式非抢占式 抢占式抢占式 优先权类型优先权类型

21、静态优先数法静态优先数法: : 在进程创建时指定优先数，在进程运行期在进程创建时指定优先数，在进程运行期间优先数不变。间优先数不变。 动态优先数法动态优先数法: : 在进程创建时创立一个优先数，但在其生在进程创建时创立一个优先数，但在其生命周期内优先数可以动态变化。如等待时间长优先数可改命周期内优先数可以动态变化。如等待时间长优先数可改变。变。182022-5-24高优先权调度算法高优先权调度算法HPF（2） 优先权的规定优先权的规定 由用户规定优先数（外部优先数）由用户规定优先数（外部优先数） 用户根据急迫程度规定适当的优先数。用户根据急迫程度规定适当的优先数。 由系统计算优先数（内部优先数

22、）由系统计算优先数（内部优先数） 例，如下计算优先数的公式例，如下计算优先数的公式 优先权优先权= = 用户规定优先数用户规定优先数 进程处理时间进程处理时间 + + 进程等待时间进程等待时间192022-5-24高优先权调度算法高优先权调度算法HPF示例示例 进程进程 进入时间进入时间 估计运行时估计运行时间间 （分钟）（分钟） 优先数优先数 结束时间结束时间 周转时间周转时间 （分钟）（分钟） 带权周转带权周转时间时间 A 8：00 120 5 B 8：50 50 3 C 9：00 10 4 D 9：50 20 6 进程平均周转时间进程平均周转时间 T = 进程带权平均周转时间进程带权平均

23、周转时间 W = 优先数越大，优先权越高，非抢占式优先数越大，优先权越高，非抢占式 进程进程 进入时间进入时间 估计运行估计运行时间时间 （分钟）（分钟） 开始时间开始时间 结束时间结束时间 周转时间周转时间 （分钟）（分钟） 带权周转带权周转时间时间 A 8：00 120 8:00 10:00 120 1 B 8：50 50 10:30 11:20 150 3 C 9：00 10 10:20 10:30 90 9 D 9：50 20 10:00 10:20 30 1.5 进程平均周转时间进程平均周转时间 T = 97.5 进程带权平均周转时间进程带权平均周转时间 W = 3.625 390

24、14.5 优先数越小，优先权越高，抢占式优先数越小，优先权越高，抢占式 进程进程 进入时间进入时间 估计运行时估计运行时间间 （分钟）（分钟） 优先数优先数 结束时间结束时间 周转时间周转时间 （分钟）（分钟） 带权周转带权周转时间时间 A 8：00 120 5 B 8：50 50 3 C 9：00 10 4 D 9：50 20 6 进程平均周转时间进程平均周转时间 T = 进程带权平均周转时间进程带权平均周转时间 W = 进程进程 进入时间进入时间 估计运行估计运行时间时间 （分钟）（分钟） 开始时间开始时间 结束时间结束时间 周转时间周转时间 （分钟）（分钟） 带权周转带权周转时间时间 A

25、 8：00 120 8:00 11:00 180 1.5 B 8：50 50 8:50 9:40 50 1 C 9：00 10 9:40 9:50 50 5 D 9：50 20 11:00 11:20 90 4.5 进程平均周转时间进程平均周转时间 T = 92.5 进程带权平均周转时间进程带权平均周转时间 W = 3 370 12 202022-5-24时间片轮转调度算法（时间片轮转调度算法（RR）抢占方式抢占方式调度。调度。基本思想基本思想 把把CPUCPU划分成若干时间片划分成若干时间片, ,并且按顺序赋给就绪队列中并且按顺序赋给就绪队列中的每一个进程，进程轮流占有的每一个进程，进程轮流

26、占有CPUCPU，当时间片用完时，即，当时间片用完时，即使进程未执行完毕，系统也剥夺该进程的使进程未执行完毕，系统也剥夺该进程的CPUCPU，将该进程，将该进程排在就绪队列末尾。同时系统选择另一个进程运行。排在就绪队列末尾。同时系统选择另一个进程运行。就绪队列就绪队列212022-5-24时间片的选取时间片的选取 时间片长度的选择时间片长度的选择 轮转法的性能取决于时间片（记为轮转法的性能取决于时间片（记为q）长度的选择，进程间在）长度的选择，进程间在CPU上的切换需上的切换需要时间。要时间。 q足够大到每一进程执行完，足够大到每一进程执行完，FCFS (先到先服务先到先服务) q 适当适当

27、进程均匀执行进程均匀执行 q 太小太小 开销太大，有切换时间，开销太大，有切换时间，CPU利用率低。利用率低。 例：切换例：切换t = 5ms, q = 20ms, 则则CPU利用率利用率80，有，有20花费在进程调度程花费在进程调度程序。为了改善序。为了改善CPU的利用率，可以增大时间片，设的利用率，可以增大时间片，设q = 500ms，此时此时CPU利用利用率达率达99之多，但每一进程的响应时间也因之增大。若就绪队列中共有之多，但每一进程的响应时间也因之增大。若就绪队列中共有10个个进程，则每一进程需要等待进程，则每一进程需要等待5秒钟，才能在秒钟，才能在CPU上服务一次。上服务一次。 通

28、常来说，选择时间片为通常来说，选择时间片为100毫秒毫秒左右比较适宜。左右比较适宜。 与时间片大小有关的因素与时间片大小有关的因素 系统响应时间系统响应时间( (进程等待时间进程等待时间) ) 就绪进程个数（就绪队列长度）就绪进程个数（就绪队列长度） CPUCPU能力能力( (运算速度运算速度) ) 轮换时间轮换时间 ( (切换时间切换时间) ) 222022-5-24轮转调度算法示例轮转调度算法示例进程名进程名 A B C D E 平均平均 到达时间到达时间 0 1 2 3 4 作业情况作业情况 时间片时间片 服务时间服务时间 4 3 4 2 4 完成时间完成时间 12 10 16 11 1

29、7 周转时间周转时间 12 9 14 8 13 11.2 RR q1 带权周转时间带权周转时间 3 3 3.5 4 3.25 3.35 完成时间完成时间 4 7 11 13 17 周转时间周转时间 4 6 9 10 13 8.4 RR q4 带权周转时间带权周转时间 1 2 2.25 5 3.25 2.7 232022-5-24多级反馈队列调度算法多级反馈队列调度算法FCFS调调度算法度算法时间片时间片轮转轮转结合了结合了FCFSFCFS、抢占式、抢占式HPFHPF和和RRRR算法算法基本思想基本思想 q2nnq222q111n时时间间片片优优先先级级队队列列242022-5-24 (1) (

30、1)将就绪队列分为将就绪队列分为N N级，每个就绪队列分配给不同级，每个就绪队列分配给不同的时间片；的时间片； (2)(2)队列级别越高，时间片越长，级别越小，时间片队列级别越高，时间片越长，级别越小，时间片越短；越短； (3)(3)系统从第一级调度，当第一级为空时，系统转向系统从第一级调度，当第一级为空时，系统转向第二个队列，第二个队列，. (4) (4)当运行进程用完一个时间片，放弃当运行进程用完一个时间片，放弃CPUCPU时，进入时，进入下一级队列；下一级队列； (5)(5)等待进程被唤醒时，进入原来的就绪队列；等待进程被唤醒时，进入原来的就绪队列； (6)(6)当进程第一次就绪时，进入

31、第一级队列。当进程第一次就绪时，进入第一级队列。 多级反馈队列调度算法多级反馈队列调度算法252022-5-24 例：例：有有一个具有两道作业的批处理系统，作业调度采用短一个具有两道作业的批处理系统，作业调度采用短作业优先的调度算法，进程调度采用以优先数为基础的抢作业优先的调度算法，进程调度采用以优先数为基础的抢占式调度算法。在下表所示的作业序列，作业优先数即为占式调度算法。在下表所示的作业序列，作业优先数即为进程优先数，且优先数越小优先级越高。进程优先数，且优先数越小优先级越高。调度算法综合应用例子调度算法综合应用例子(1)(1)列出所有作业进入内存时间及结束时间列出所有作业进入内存时间及结束时间(2)(2)计算平均周转时间。计算平均周转时间。