处理机管理-进程的调度PPT课件VIP

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