《第3章-4 进程调度.ppt》由会员分享，可在线阅读，更多相关《第3章-4 进程调度.ppt（21页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第第第第3 3章章章章 进程管理进程管理进程管理进程管理 3.1 进程的引入进程的引入 3.2 进程的结构进程的结构 3.3 进程控制进程控制 3.4 进程的同步与互斥进程的同步与互斥 3.5 进程间通信进程间通信 3.6 进程调度进程调度 3.7 死锁死锁 3.8 线程线程4/9/20231进程调度概念进程调度概念进程调度概念进程调度概念又称微观调度、又称微观调度、低级调度低级调度、短程调度、短程调度、处理机调度处理机调度。控制协调进程对控制协调进程对CPUCPU的竞争，即按一定的调度算的竞争，即按一定的调度算法从就绪队列中选中一个进程，把法从就绪队列中选中一个进程，把CPUCPU的使用权交
2、给的使用权交给被选中的进程。被选中的进程。操作系统中实现进程调度的程序称为操作系统中实现进程调度的程序称为进程进程(线程线程)调度程序调度程序，或分派程序，或分派程序(Dispatcher)Dispatcher)，常驻内存。常驻内存。进进程程调调度度程程序序是是操操作作系系统统最最为为核核心心的的部部分分，进进程调度策略的优劣直接影响到整个系统的性能。程调度策略的优劣直接影响到整个系统的性能。4/9/20232进程调度方式进程调度方式进程调度方式进程调度方式非抢占方式非抢占方式(Non-preemptive Non-preemptive）某一进程被调度运行后，除非由于它自身的原因某一进程被调度
3、运行后，除非由于它自身的原因不能运行，否则一直运行下去。不能运行，否则一直运行下去。抢占方式抢占方式(PreemptivePreemptive）当有比正在运行的进程优先级更高的进程就绪时，当有比正在运行的进程优先级更高的进程就绪时，系统可强行剥夺正在运行进程的系统可强行剥夺正在运行进程的CPUCPU，提供给具有更提供给具有更高优先级的进程使用。高优先级的进程使用。优先权原则优先权原则短进程优先原则短进程优先原则时间片原则时间片原则4/9/20233何时发生进程调度何时发生进程调度何时发生进程调度何时发生进程调度呢呢呢呢?有四种情况都会发生进程调度有四种情况都会发生进程调度:当一个进程从运行态切
4、换成阻塞态时；当一个进程从运行态切换成阻塞态时；当一个进程从运行态切换成就绪态时；当一个进程从运行态切换成就绪态时；当一个进程从阻塞态切换成就绪态时；当一个进程从阻塞态切换成就绪态时；当一个进程中止时。当一个进程中止时。4/9/20234选择调度方式和算法的准则选择调度方式和算法的准则选择调度方式和算法的准则选择调度方式和算法的准则 调度实质上是一个策略问题，设定的目标往往是相互调度实质上是一个策略问题，设定的目标往往是相互冲突的，如何选择取决于操作系统的类型和目标冲突的，如何选择取决于操作系统的类型和目标.面向用户的准则面向用户的准则周转时间短周转时间短响应时间快响应时间快截止时间的保证截止
5、时间的保证优先权准则优先权准则面向系统的准则面向系统的准则系统吞吐量高系统吞吐量高处理机利用率高处理机利用率高 各类资源的平衡利用各类资源的平衡利用4/9/20235调度算法性能衡量调度算法性能衡量调度算法性能衡量调度算法性能衡量 周转时间周转时间如如果果进进程程i i进进入入内内存存的的时时刻刻是是t ts s，完完成成时时刻刻是是t tf f，该该进进程程的的周周转转时间时间t ti i为：为：t ti i=t tf f-t ts s实际上，它是进程的等待时间与运行时间之和。实际上，它是进程的等待时间与运行时间之和。平均周转时间平均周转时间为为了了提提高高系系统统的的性性能能，要要让让若若
6、干干个个进进程程的的平平均均周周转转时时间间和和平平均均带权周转时间最小。带权周转时间最小。平均周转时间平均周转时间 T=(T=(t ti i)/n)/n带权周转时间和平均带权周转时间带权周转时间和平均带权周转时间如果进程如果进程i i的周转时间为的周转时间为t ti i，所需运行时间为所需运行时间为t tk k，则称则称 w wi i=t ti i/t tk k为该进程的带权周转时间。为该进程的带权周转时间。t ti i是等待时间与运行时间之和，故带权周转时间总大于是等待时间与运行时间之和，故带权周转时间总大于1 1。平均带权周转时间平均带权周转时间W=(W=(w wi i)/n)/n4/9
7、/20236调度算法调度算法调度算法调度算法先先来先服务算法（来先服务算法（FCFS）最短进程优先算法（最短进程优先算法（SJF）最短剩余时间优先调度算法（最短剩余时间优先调度算法（SRTF）最高响应比优先调度算法（最高响应比优先调度算法（HRRF）高优先权优先调度算法（高优先权优先调度算法（HPF）基于时间片的轮转调度算法（基于时间片的轮转调度算法（RR）多级反馈队列调度算法多级反馈队列调度算法4/9/20237先来先服务调度算法先来先服务调度算法先来先服务调度算法先来先服务调度算法FCFSFCFS调度算法调度算法按照进程进入就绪队列的先后次序来选择。按照进程进入就绪队列的先后次序来选择。调
8、度方式采用调度方式采用非抢占方式非抢占方式。例例优点优点实现简单实现简单缺点缺点算法只顾及进程的等候时间，没考虑进程要求服务时间的长短；算法只顾及进程的等候时间，没考虑进程要求服务时间的长短；不利于短进程而优待了长进程；不利于短进程而优待了长进程；没考虑进程的优先级。没考虑进程的优先级。4/9/20238算法算法以以进进程程所所要要求求的的CPUCPU时时间间为为标标准准，总总选选取取估估计运行时间最短的进程投入运行。计运行时间最短的进程投入运行。调度方式采用调度方式采用非抢占方式。非抢占方式。例例最短进程优先算法（最短进程优先算法（最短进程优先算法（最短进程优先算法（SPFSPF）优点优点算
9、法易于实现。算法易于实现。缺点缺点 忽视了进程等待时间；不利于长进程，会出现饥饿现象。忽视了进程等待时间；不利于长进程，会出现饥饿现象。4/9/20239最短剩余时间优先调度算法最短剩余时间优先调度算法最短剩余时间优先调度算法最短剩余时间优先调度算法SRTFSRTFSRTFSRTF最最短短剩剩余余时时间间优优先先调调度度算算法法也也称称为为抢抢占占式式的的SPFSPF算法算法基本思想基本思想 一一个个新新进进程程进进入入就就绪绪状状态态，如如果果新新进进程程需需要要的的CPUCPU时时间间比比当当前前正正在在执执行行的的进进程程剩剩余余下下来来还还需需的的CPUCPU时时间间短短，SRTFSR
10、TF强强行行赶赶走走当当前前正在执行进程。正在执行进程。调度方式采用调度方式采用抢占方式抢占方式。4/9/202310最短剩余时间优先调度最短剩余时间优先调度最短剩余时间优先调度最短剩余时间优先调度SRTFSRTFSRTFSRTF算法示例算法示例算法示例算法示例优点优点可以用于分时系统，保证及时响应用户要求。可以用于分时系统，保证及时响应用户要求。缺点缺点系统开销增加，首先要保存进程的运行情况记录，以比较其剩余时间大小；系统开销增加，首先要保存进程的运行情况记录，以比较其剩余时间大小；其次，抢占本身也要消耗处理机时间其次，抢占本身也要消耗处理机时间4/9/202311 响应比响应比 R=周转时
11、间周转时间/运行时间运行时间 =（运行时间（运行时间+等待时间）等待时间）/运行时间运行时间 =1+（等待时间（等待时间/运行时间）运行时间）短进程容易得到较高响应比；短进程容易得到较高响应比；长进程等待时间足够长后，也将获得足够高的响应比；长进程等待时间足够长后，也将获得足够高的响应比；饥饿现象不会发生饥饿现象不会发生例例最高响应比最高响应比最高响应比最高响应比(HRRF)HRRF)HRRF)HRRF)优先调度算法优先调度算法优先调度算法优先调度算法4/9/202312高优先权调度算法高优先权调度算法高优先权调度算法高优先权调度算法HPFHPF（1 1）算法思想算法思想 从就绪队列中选择优先
12、权最高的进程投入运行。从就绪队列中选择优先权最高的进程投入运行。调度算法类型调度算法类型非抢占式非抢占式抢占式抢占式优先权类型优先权类型静态优先数法静态优先数法:在进程创建时指定优先数，在进程运行期在进程创建时指定优先数，在进程运行期间优先数不变。间优先数不变。动态优先数法动态优先数法:在进程创建时创立一个优先数，但在其生在进程创建时创立一个优先数，但在其生命周期内优先数可以动态变化。如等待时间长优先数可改命周期内优先数可以动态变化。如等待时间长优先数可改变。变。4/9/202313高优先权调度算法高优先权调度算法高优先权调度算法高优先权调度算法HPFHPF（2 2）优先权的规定优先权的规定由
13、用户规定优先数（外部优先数）由用户规定优先数（外部优先数）用户根据急迫程度规定适当的优先数。用户根据急迫程度规定适当的优先数。由系统计算优先数（内部优先数）由系统计算优先数（内部优先数）例，如下计算优先数的公式例，如下计算优先数的公式 优先权优先权=用户规定优先数用户规定优先数 进程处理时间进程处理时间 +进程等待时间进程等待时间4/9/202314高优先权调度算法高优先权调度算法高优先权调度算法高优先权调度算法HPFHPF示例示例示例示例优先数越大，优先权越高，非抢占式优先数越大，优先权越高，非抢占式优先数越小，优先权越高，抢占式优先数越小，优先权越高，抢占式4/9/202315时间片轮转调
14、度算法（时间片轮转调度算法（时间片轮转调度算法（时间片轮转调度算法（RRRR）抢占方式抢占方式调度。调度。基本思想基本思想 把把CPUCPU划分成若干时间片划分成若干时间片,并且按顺序赋给就绪队列中并且按顺序赋给就绪队列中的每一个进程，进程轮流占有的每一个进程，进程轮流占有CPUCPU，当时间片用完时，即当时间片用完时，即使进程未执行完毕，系统也剥夺该进程的使进程未执行完毕，系统也剥夺该进程的CPUCPU，将该进程将该进程排在就绪队列末尾。同时系统选择另一个进程运行。排在就绪队列末尾。同时系统选择另一个进程运行。就绪队列就绪队列4/9/202316时间片的选取时间片的选取时间片的选取时间片的选
15、取时间片长度的选择时间片长度的选择轮转法的性能取决于时间片（记为轮转法的性能取决于时间片（记为q）长度的选择，进程间在长度的选择，进程间在CPU上的切换需上的切换需要时间。要时间。q足够大到每一进程执行完，足够大到每一进程执行完，FCFS(先到先服务先到先服务)q 适当适当 进程均匀执行进程均匀执行q 太小太小 开销太大，有切换时间，开销太大，有切换时间，CPU利用率低。利用率低。例：切换例：切换t=5ms,q=20ms,则则CPU利用率利用率80，有，有20花费在进程调度程花费在进程调度程序。为了改善序。为了改善CPU的利用率，可以增大时间片，设的利用率，可以增大时间片，设q=500ms，此
16、时此时CPU利用利用率达率达99之多，但每一进程的响应时间也因之增大。若就绪队列中共有之多，但每一进程的响应时间也因之增大。若就绪队列中共有10个个进程，则每一进程需要等待进程，则每一进程需要等待5秒钟，才能在秒钟，才能在CPU上服务一次。上服务一次。通常来说，选择时间片为通常来说，选择时间片为100毫秒毫秒左右比较适宜。左右比较适宜。与时间片大小有关的因素与时间片大小有关的因素系统响应时间系统响应时间(进程等待时间进程等待时间)就绪进程个数（就绪队列长度）就绪进程个数（就绪队列长度）CPUCPU能力能力(运算速度运算速度)轮换时间轮换时间(切换时间切换时间)4/9/202317轮转调度算法示
17、例轮转调度算法示例轮转调度算法示例轮转调度算法示例进程名进程名 A B C D E 平均平均 到达时间到达时间 0 1 2 3 4 作业情况作业情况 时间片时间片 服务时间服务时间 4 3 4 2 4 完成时间完成时间 12 10 16 11 17 周转时间周转时间 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 4/9/202318多级反馈队列调度算法多级反
18、馈队列调度算法多级反馈队列调度算法多级反馈队列调度算法FCFS调调度算法度算法时间片时间片轮转轮转结合了结合了FCFSFCFS、抢占式抢占式HPFHPF和和RRRR算法算法基本思想基本思想4/9/202319 (1)(1)将就绪队列分为将就绪队列分为N N级，每个就绪队列分配给不同级，每个就绪队列分配给不同的时间片；的时间片；(2)(2)队列级别越高，时间片越长，级别越小，时间片队列级别越高，时间片越长，级别越小，时间片越短；越短；(3)(3)系统从第一级调度，当第一级为空时，系统转向系统从第一级调度，当第一级为空时，系统转向第二个队列，第二个队列，.(4)(4)当运行进程用完一个时间片，放弃
19、当运行进程用完一个时间片，放弃CPUCPU时，进入时，进入下一级队列；下一级队列；(5)(5)等待进程被唤醒时，进入原来的就绪队列；等待进程被唤醒时，进入原来的就绪队列；(6)(6)当进程第一次就绪时，进入第一级队列。当进程第一次就绪时，进入第一级队列。多级反馈队列调度算法多级反馈队列调度算法多级反馈队列调度算法多级反馈队列调度算法4/9/202320 例：例：有有一个具有两道作一个具有两道作业业的批的批处处理系理系统统，作，作业调业调度采用短度采用短作作业优业优先的先的调调度算法，度算法，进进程程调调度采用以度采用以优优先数先数为为基基础础的的抢抢占式占式调调度算法。在下表所示的作度算法。在下表所示的作业业序列，作序列，作业优业优先数即先数即为为进进程程优优先数，且先数，且优优先数越小先数越小优优先先级级越高。越高。调度算法综合应用例子调度算法综合应用例子调度算法综合应用例子调度算法综合应用例子(1)(1)列出所有作业进入内存时间及结束时间列出所有作业进入内存时间及结束时间(2)(2)计算平均周转时间。计算平均周转时间。4/9/202321