处理机管理进程的调度课件

,段景山,*,Click to edit Master title style,*,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,2020/9/14,#,软件技术基础,制作,主讲,处理机管理,进程的调度,1,处理机的管理功能分为：,进程的描述,进程的控制,进程的同步,进程的通信,进程的调度,处理机管理,2,第四章 进程的调度,第二篇 操作系统,进程调度的模型,进程调度的算法,死锁及解决,3,进程调度引言,引言,处理机调度的主要目的：分配处理机,调度影响的因素：,响应的及时性,进程是否能在限定时间内获得处理机，对用户进行响应,周转时间（等待时间+使用CPU时间）,进程是否等待时间太长,系统吞吐量（进程时间+系统开销）,CPU是否总是用在刀刃上,4,调度类型,4.1调度的类型与模型,4.1.1调度类型,从调度层次：,高级调度,低级调度,中级调度,从OS类型：,批处理、分时、实时、多处理机调度,5,作业调度,（1）高级调度作业调度,对象：,外存上后备队列中的作业,动作：,调入内存、创建进程,、分配资源、新进程进入就绪队列,决策内容：,接纳作业量、作业类型,其它,作业成批进入,输入井,输出井,内存,CPU,高级调度,6,进程调度,（2）低级调度进程调度,对象：,就绪队列中的进程,动作：,决定由哪个进程获得CPU,调度方式：,非抢占式,抢占式,低级调度,进程并发执行,其它,作业成批进入,输入井,输出井,内存,CPU,高级调度,7,进程调度过程,进程调度对象：就绪队列中的进程,进程调度功能及过程,纪录当前进程的状态、保存CPU,现场,选取适当的就绪进程,进程调度算法,分配处理机：恢复选取进程的,现场,CPU,就绪队列,交互用户,1,2,3,进程调度,8,进程调度方式,进程调度的方式,非抢占式（非剥夺式）,现运行进程的CPU使用权不能被中途强行剥夺,除非进程主动放弃,抢占式（剥夺式）,系统按照某种原则剥夺现行进程的CPU使用权,将CPU使用权分配给其他进程,抢占原则,优先权原则,时间片原则,短进程优先原则,9,中级调度,（3）中级调度,对象：,外存中因暂时不能运行而被挂起的进程,动作：,将外存挂起的进程激活，调入内存，进入就绪队列,目的：,提高内存利用率,10,单级调度队列模型,4.1.2调度队列模型,阻塞队列,交互用户,阻塞,进程调度是最基本的调度，,必须配置,1)单级调度模型,CPU,进程调度,就绪队列,结束,时间片完/被中断,唤醒,11,二级调度队列模型,2）二级调度模型,CPU,就绪队列,阻塞队列,时间片完,阻塞,唤醒,进程调度,后备队列,作业调度,在批处理或类似系统中,需要从外存后备队列中调入作业,12,3）三级调度模型,CPU,就绪队列,阻塞队列,时间片完,阻塞,唤醒,后备队列,挂起,挂起,事件出现,外存阻塞队列,外存就绪队列,配置中级,调度机制,可以提高,内存利用率,进程调度,作业调度,中级,调度,13,进程调度原因,4.1.3进程调度原因（调度时刻）,阻塞队列,交互用户,阻塞,进程调度,就绪队列,结束,时间片完,唤醒,现进程运行完毕,现进程阻塞,优先权高的进程进入就绪队列,现进程“超时”,/被中断,CPU,14,进程调度算法准则,4.2调度算法,从多个目标（就绪进程）中选取一个,算法准则,面向用户,面向系统,周转时间,响应时间,截止时间,优先权,系统吞吐量,处理机利用率,各类资源的利用,短,快,保证,可设置,大,高,平衡,15,进程调度算法类型,算法类型,简单的调度算法,先来先服务算法,短进程优先,轮转法,等时间片轮转,不等时间片轮转,优先权法,抢占式优先权,非抢占式优先权,静态优先权,动态优先权,多级反馈队列算法,16,FCFS,1）先来先服务算法FCFS,按照就绪进程进入就绪队列的先后次序进行调度,简单易实现,利于长进程，CPU繁忙型作业,不利于短进程,排队时间相对过长,CPU,就绪队列,1,2,3,17,SCBF,2）短进程优先算法,对系统服务时间需求短的进程优先被调度,短进程估算：,依赖于前一周期的实际CPU时间和估计时间,系统性能改善，平均带权周转时间优于FCFS,不利于长作业，当不断有短进程到达时，不保证长进程响应的及时性，甚至可能得不到调度,其中,n,为估计的第n个CPU 周期。t,n,为实际值。,为控制值，0,1，,常取,0.5,n+1,n,n,t,（1,）,18,典型如分时系统，从用户敲键到字符显示在用户终端屏幕上,调度算法评价指标,响应时间RT（Response Time）,从提交一个请求开始到计算作出响应，显示结果在屏幕上,RT q N,q：时间片大小,19,调度算法评价指标,周转时间（Trunaround Time）,进程第一次进入就绪队列到进程运行结束的时间间隔,TT 等待时间(WT)服务时间(ST),平均周转时间（ATT）,系统各进程周转时间的平均值,ATT,TT/N,带权周转时间（QTT）,进程周转时间与系统服务时间的比值,QTT=TT/服务时间,平均带权周转时间（AQTT）,例,A,B,C,WT,10,10,30,ST,2,100,10,TT,12,110,40,ATT,54,QTT,6,1.1,4,AQTT,3.7,AQTT=,QTT/N,20,调度算法比较例,例：A请求系统服务时间5s，B请求系统服务时间为100s，,设第0到第5秒前，CPU运行C进程。,第1秒时B进入系统内存，第2秒时A进入内存,当CPU空闲，需要调度进程时根据不同的算法选择A或B,问：分别计算FCFS算法下和SCBF算法下，A和B的周转时间，带权周转时间和系统平均周转时间,B,A,21,FCFS算法先来先服务,A：周转时间为 3+100+5108s,带权周转时间为108/5 20.4,B：周转时间为 4100104s,带权周转时间为104/100 1.04,平均带权周转时间为(20.4+1.04)2,10.72,SCBF算法短进程优先,A：周转时间为 3+59s,带权周转时间为8/5 1.6,B：周转时间为 4+5+100109s,带权周转时间为109/100 1.09,平均带权周转时间为(1.6+1.09)2,1.345,调度算法比较例,先调度B,后调度A,先调度A,后调度B,调度顺序,调度顺序,22,RR等时间片,3）等时间片轮转,保证人机交互的及时性,（1）按照FCFS顺序从就绪队列选取进程,（2）每个进程分配给相同的CPU时间片,（3）时间片到后将进程排到就绪队列尾,公平性的保证,响应及时性的保证,23,RR时间片,时间片q的选择,q,N,T,q：时间片大小,T：响应时间,N：就绪队列进程数,=,q,N,T,=,当N一定时：,q与T成正比。,q不能太大,当T一定时：,q与N成反比,q不能太小,保证响应时间,减少开销,24,RR不等时间片,4）不等时间片轮转法,短时间片满足快速响应的需要,长时间片使周转时间降低,在保证及时响应的基础上，为不同的需求分配大小不等的时间片,降低周转时间,长进程,短进程,I/O频繁型,CPU密集型,长时间片,短时间片,引入“前台”、“后台”,提高系统资源利用率,课,堂,练,习,25,前、后台调度,“前台”、“后台”进程调度,进程分为前台和后台两种。,前台：频繁和用户交互的进程，要求及时响应。如，支持界面的进程。,后台：需要大量时间运行，与用户交互较少的进程。如，查病毒进程。可见Windows系统右下角的驻留进程。,只要前台就绪队列里有进程，就不会调度后台进程。,前台进程按时间片轮转，后台进程按FCFS调度（也可按时间片轮转）,26,前、后台调度,“前台”、“后台”进程调度,前台进程主要与用户交互，除了及时响应外，大量的时间都在等待用户的输入或向用户输出,后台进程可利用前台进程交互的间隙执行运算,这样，即不会因为执行繁重计算工作的进程影响了界面的及时响应，又不会因为频繁与用户交互而使系统无法完成负荷重的工作。,27,HPF,5）最高优先权调度算法（HPF）,保证实时性。（事件响应的及时性）,（1）为每个进程设置优先级,（2）调度时选取优先级最高的进程，相同优先级的进程按照FCFS选取,抢占式调度：,高优先权的进程进入就绪队列时引起调度,非抢占式调度：,高优先权的进程进入就绪队列仅引起队列重排,28,HPF,优先级与优先数,易混淆的概念,优先级：高、低,优先数：大、小,在某些系统中：优先机高的，优先数反而小。,29,HPF静态优先权,静态优先权,进程的优先权在进程创建时设定，以后,不会改变,优先权设定的一般依据：,（1）进程类型,（2）进程对资源的需求,（3）根据用户的需求,优先级设定后可能造成低优先权的进程得不到运行的机会,当不断有高优先进程进入就绪队列时,30,HPF动态优先权,动态优先权,进程的优先权在系统周转过程中动态改变,就绪等待进程优先级随等待时间以,速率升高,执行进程的优先级以,速率下降,优先权,=,等待时间,+,要求服务时间,要求服务时间,等待时间一定：优先权与要求服务时间成反比,要求服务时间一定：优先权与等待时间成正比,短进程优先,优先权低的进程也能有运行的机会,31,多级反馈队列,6）多级反馈队列调度,综合各种算法长处,设计思想,设置多个就绪队列,各队列优先级不一样，,分配的时间片也不一样，高优先权队列进程的时间片较小,调度算法（见后）,32,多级反馈队列算法,短时间片,长时间片,（1）在选取进程时，选取高优先权队列里的进程。,分配给相应的时间片。同一队列按照FCFS,（2）进程使用完时间片后，回到就绪态是则进入低一级优先权队列,（3）当高优先权队列里没有进程时，才调度低优先权队列进程,（4）进程创建后进入最高优先权队列,优先级调度,时间片轮转,动态优先权、不等时间片,33,多级反馈队列性能,多级反馈队列的性能,（1）短进程,在第一级队列的时间片中完成，,满足及时响应和短进程的周转要求,（2）动态变化的优先权,使优先权低的进程也得到执行的机会,（3）动态变化的时间片,长进程在长时间等待后获得长时间片，可减少周转时间和系统开销,34,死锁,4.3死锁问题（dead lock）,例：,P(s1),P(s2),临界区,V(s2),V(s1),P(s2),P(s1),临界区,V(s1),V(s2),.,.,.,.,进程1,进程2,就绪,就绪,执行,执行,阻塞,s1,s2,阻塞,状态：,状态：,死锁,35,死锁,死锁,当两个或两个以上进程因竞争资源而无休止地处于相互等待状态,死锁将使进程已占用的资源的不到利用,严重情况下，死锁“蔓延”开，会导致“死机”,Proc1,s2,Proc2,s1,36,死锁原因,4.3.1死锁原因,资源不够,进程推进顺序不当,死锁解决方法初探,法一：预先让进程获得所有的资源,法二：改变进程推进顺序按序使用资源,在进程内部解决,法三：改变系统调度进程的顺序,在进程外部，系统中解决,P(s1),P(s2),.,V(s2),V(s1),P(s2),P(s1),.,V(s1),V(s2),进程1 P(s1),进程1,进程2,死锁,进程2 P(s1),进程1 P(s2),进程2 P(s2),阻塞进程2,阻塞进程1,37,死锁原因,死锁解决方法初探,法一：预先为进程分配足够资源,资源利用率极低,法二：改变进程推进顺序,各进程申请资源的顺序完全一致。,很难约束进程行为,法三：改变系统调度进程的顺序,如何界定正确的系统推进顺序？,P(s1),P(s2),.,V(s2),V(s1),进程1 P(s1),进程1 P(s2),进程2 P(s2),P(s1),P(s2),.,V(s2),V(s1),进程1,进程2,38,死锁的解决,如何解决死锁问题？,开环：,从破坏产生问题的必要条件入手,不使问题出现,闭环：,允许问题存在，研究问题的检测和解除方法,39,死锁产生的必要条件,4.3.2死锁产生的必要条件,死锁和“资源”密切相关,1）,资源,访问的互斥条件,2）请求和保持条件,进程在需要时才申请,资源,进程对,资源,的申请是分步的,进程在申请新,资源,时，对旧,资源,仍然保持占用,3）不剥夺条件,资源,一旦获得后在V(s)之前不放弃,4）环路等待条件,40,死锁产生的必要条件,4）环路等待条件,存在进程资源环形链,Proc1,s2,Proc2,s1,Proc1,Proc3,Proc2,s2,s3,s1,从进程出发的箭头表示进程正在申请资源,从资源出发的箭头表示已分配该资源,41,预防死锁,4.3.3解决死锁的方法之一,预防,破坏死锁产生的四个条件的一个或几个,1）破坏互斥条件,互斥访问是大部分资源的固有属性,2）破坏请求和保持条件,资源预分配，,资源利用率低,3）破坏不剥夺条件,阻塞进程释放所有的资源，,进程先前工作白费,4、破坏环路等待条件,资源按序分配，,资源利用率低，进程受限,42,避免死锁,4.3.4解决死锁的方法之二,死锁避免,资源预测分配，分配资源前，检查分配的安全性,系统的安全状态和安全状态检测,安全状态,在当前的状态下，能找到一个正确的推进顺序满足所有的进程的资源需求，将它们推进完毕,2、安全状态检测,假设本次分配，检测分配后的系统状态是否安全,安全，则执行资源分配。,不安全，则不予分配，将进程阻塞,43,避免死锁例,例：条件 P1、P2、P3三个进程对同类资源竞争。P1最大需要10个该资源，P2最大需要4个，P3为9个。该资源总数为12个。,已知当前时刻，系统状态,1、当前是否为安全状态,2、若进程2提出2个资源需求是否可以分配,3、若进程3提出1个资源需求是否可以分配,进程,最大需求,已分配,剩余,1,2,3,10,4,9,2,P2,P1,P3,3,1,2,4,5,0,5,10,10,存在一个正确的顺序推进进程,44,避免死锁例,例：条件 P1、P2、P3三个进程对同类资源竞争。P1最大需要10个该资源，P2最大需要4个，P3为9个。该资源总数为12个。,已知当前时刻，系统状态,1、当前是否为安全状态,2、若进程2提出2个资源需求是否可以分配,3、若进程3提出1个资源需求是否可以分配,进程,最大需求,已分配,剩余,1,2,3,10,4,9,2,P2,P1,P3,3,2,5,假设分配给2两个资源,1,4,P2,P1,P3,45,避免死锁例,例：条件 P1、P2、P3三个进程对同类资源竞争。P1最大需要10个该资源，P2最大需要4个，P3为9个。该资源总数为12个。,已知当前时刻，系统状态,1、当前是否为安全状态,2、若进程2提出2个资源需求是否可以分配,3、若进程3提出1个资源需求是否可以分配,进程,最大需求,已分配,剩余,1,2,3,10,4,9,P2,P1,P3,3,2,5,假设分配给3一个资源,2,P2,P1,P3,2,3,46,死锁的检测与解除,4.3.4解决死锁的方法之三死锁的检测与解除,死锁产生后的解决办法,1）死锁的检测,找出死锁的进程和相应的资源,2）死锁的解除,对死锁进程和资源加以处理，解除死锁,47,死锁的检测,1）死锁的检测,资源分配图,结点：,进程结点,资源结点（同类资源形成一个结点）,有向线段：,进程正申请一个资源,进程已获得一个资源,P1,P1,P1,48,资源分配图的化简,死锁检测法资源图的化简,P1,P2,r1,r2,P1,P2,1）在图中找出一个不阻塞，又不孤立的结点,2）削去该结点的所有边，使结点成为孤立结点,3）继续步骤1直到所有的结点都成为孤立结点，或找不到可简化的结点,若资源分配图能被完全简化，则当前状态不存在死锁。,反之，存在死锁进程，即那些非孤立结点。,49,资源分配图的化简,课堂练习：请化简下图,P1,P2,r1,r2,P4,P6,P5,P3,P7,50,2）死锁的解除,（1）剥夺资源：,从其它进程处剥夺足够的资源给死锁进程使其能正常完成。,剥夺的策略,（2）撤销进程,撤销所有的死锁进程,撤销部分死锁进程，直到回收的资源可以使剩下的进程完成。,撤销的策略,死锁的解除,51,经常,不断地学习,你就什么都知道。你知道得越多,你就越有,力量,Study Constantly,And You Will Know Everything.The More You Know,The More Powerful You Will,Be,写,在最后,Thank,You,在别人的演说中思考,，,在自己的故事里成长,Thinking,In Other,PeopleS Speeches,，,Growing,Up In Your Own,Story,讲师,：,XXXXXX,XX,年,XX,月,XX,日,