第三章计算机操作系统处理机调度与死锁介绍

2020/2/291学院:计算机与信息技术学院教师:刘贤梅2020/2/292内容概述3.1处理机调度的层次3.2调度队列模型和调度准则3.3调度算法3.4实时调度3.5产生死锁的原因和必要条件3.6预防死锁的方法3.7死锁的检测与解除处理机调度的主要任务是分配处理机。在多道程序环境下,进程数目通常多于处理机的数目。系统必须按一定方法动态地把处理机分配给就绪队列中的一个进程。处理机利用率和系统性能(吞吐量、响应时间)在很大程度上取决于处理机调度。2020/2/2933.1处理机调度的层次3.1.1高级调度3.1.2低级调度3.1.3中级调度2020/2/2943.1.1高级调度1.高级调度的含义又称为作业调度或长程调度：将外存上处于后备队列上的作业调入内存，并创建进程、分配资源，安排在就绪队列上。2.作业程序、数据和作业说明书。以作业为单位从外存调入内存。2020/2/2953.作业控制块JCB是作业在系统中存在的标志。JCB包含的内容：–作业标识–用户名称、用户账户–作业类型（CPU繁忙型、I/O繁忙型等）、作业状态–调度信息（优先级、已运行时间）–资源需求（预计运行时间、内存大小、I/O设备类型等）–进入系统时间、开始处理时间、作业完成时间、作业推出时间–资源使用情况2020/2/2964.作业调度在每次执行作业调度时，都须做出以下两个决定：(1)接纳多少个作业取决于多道程序度，即允许多少个作业同时在内存中运行。作业太少资源利用率低作业太多服务质量下降(2)接纳哪些作业：作业调度算法先来先服务短作业优先优先权高优先2020/2/2973.1处理机调度的层次3.1.1高级调度3.1.2低级调度3.1.3中级调度2020/2/2983.1.2低级调度1.低级调度的含义也称为进程调度或短程调度，决定就绪队列中的哪个进程应获得处理机。2.低级调度的功能保存处理机的现场信息按照某种算法选取进程把处理机分配给进程（恢复处理机现场）2020/2/2993.进程调度方式(1)非抢占方式(非剥夺方式)(2)抢占方式（剥夺方式)抢占原则优先权原则短作业(进程)优先原则时间片原则2020/2/29103.1处理机调度的层次3.1.1高级调度3.1.2低级调度3.1.3中级调度2020/2/2911中级调度又称中程调度为了提高内存利用率和系统吞吐量暂时不能运行的进程，而将它们调至外存上去等待，把此时的进程状态称为就绪驻外存状态或挂起状态。当这些进程重又具备运行条件、且内存又稍有空闲时,由中级调度来决定把外存上的哪些又具备运行条件的就绪进程,重新调入内存,并修改其状态为就绪状态,挂在就绪队列上等待进程调度3.1.3中级调度对换功能2020/2/2912内容概述3.1处理机调度的层次3.2调度队列模型和调度准则3.3调度算法3.4实时调度3.5产生死锁的原因和必要条件3.6预防死锁的方法3.7死锁的检测与解除2020/2/29133.2.1调度队列模型3.2.2选择调度方式和调度算法的若干准则3.2调度队列模型和调度准则2020/2/29143.2.1调度队列模型1.仅有进程调度的调度队列模型图3-1仅具有进程调度的调度队列模型就绪队列阻塞队列进程调度CPU进程完成等待事件交互用户事件出现时间片完①②③2020/2/29152.具有高级和低级调度的调度队列模型图3-2具有高、低两级调度的调度队列模型就绪队列进程调度CPU进程完成等待事件1作业调度事件1出现时间片完等待事件2事件2出现……等待事件n事件n出现后备队列……①②③2020/2/29163.同时具有三级调度的调度队列模型图3-3具有三级调度时的调度队列模型就绪队列进程调度CPU就绪，挂起队列中级调度阻塞，挂起队列阻塞队列等待事件进程完成时间片完作业调度交互型作业后备队列批量作业挂起事件出现事件出现挂起外存内存①②③2020/2/29173.2.1调度队列模型3.2.2选择调度方式和调度算法的若干准则3.2调度队列模型和调度准则2020/2/29183.2.2选择调度方式和调度算法的若干准则1.面向用户的准则(1)周转时间短(2)响应时间快(3)截止时间保证(4)优先权准则作业周转时间：作业在外存后备队列上等待作业调度的时间进程在就绪队列上等待进程调度的时间进程在CPU上执行的时间进程等待I/O操作完成的时间n11iiTnTniSiiTTnW11平均周转时间：平均带权周转时间：2020/2/29192.面向系统的准则(1)系统吞吐量高吞吐量指单位时间内系统所完成的作业数作业调度的方式和算法对吞吐量的大小有较大影响(2)处理机利用率高(3)各类资源的平衡利用使内存、外存和I/O设备的利用率高2020/2/2920内容概述3.1处理机调度的层次3.2调度队列模型和调度准则3.3调度算法3.4实时调度3.5产生死锁的原因和必要条件3.6预防死锁的方法3.7死锁的检测与解除2020/2/29213.2.1先来先服务和短作业优先算法3.2.2高优先权优先调度算法3.2.3基于时间片的轮转调度算法3.2调度算法2020/2/29223.2.1先来先服务和短作业(进程)优先调度算法1.先来先服务调度算法(FCFS)按照作业进入系统的先后次序进行调度，先进入系统者先调度；即启动等待时间最长的作业。是一种最简单的调度算法，即可用于作业调度，也可用于进程调度。FCFS算法比较有利于长作业(进程),而不利于短作业(进程)。2020/2/2923内存无限大，作业调度和进程调度都采用FCFS。作业名进入磁盘需要服务装入主存开始执行结束执行周转带权周转时间时间时间时间时间时间时间A01B1100C21D3100执行顺序:A-B-C-D周转时间=结束执行时间-进入磁盘时间带权周转时间=周转时间/服务时间00111131101100121022021991.99101102100100先来先服务调度算法(FCFS)平均值:10025.99752020/2/29242.短作业(进程)优先调度算法SJ(P)F对短作业或短进程优先调度的算法。可以分别用于作业调度和进程调度。调度过程SJF：从后备队列中选择一个或若干个估计运行时间最短的作业，将它们调入内存运行。SPF：从就绪队列中选出一个估计运行时间最短的进程，将处理机分配给它，使它立即执行并一直执行到完成，或发生某事件而被阻塞放弃处理机时，再重新调度。2020/2/29251）内存无限大,作业调度和进程调度都采用FCFS作业名进入磁盘需要服务装入主存开始执行结束执行周转带权周转时间时间时间时间时间时间时间A04B13C25D32E44执行顺序:A-B-C-D-E2）作业调度和进程调度都采用SJFA04B13C25D32E44周转时间=结束执行时间-进入磁盘时间带权周转时间=周转时间/服务时间0044113476221214115.5712102短作业(进程)优先调度算法SJ(P)F41418143.500441136988/324631.513181616/5491399/4平均值:92.8平均值:82.1执行顺序:A-D-B-E-C2020/2/2926SJ(P)F调度算法也存在不容忽视的缺点:(1)该算法对长作业不利。由于调度程序总是优先调度那些(即使是后进来的)短作业(进程),将导致长作业(进程)长期不被调度。(2)该算法完全未考虑作业的紧迫程度,因而不能保证紧迫性作业(进程)会被及时处理。(3)由于作业(进程)的长短只是根据用户所提供的估计执行时间而定的,而用户又可能会有意或无意地缩短其作业的估计运行时间,致使该算法不一定能真正做到短作业优先调度。2020/2/29273.2.1先来先服务和短作业优先算法3.2.2高优先权优先调度算法3.2.3基于时间片的轮转调度算法3.2调度算法2020/2/29283.2.2高优先权优先调度算法1.优先权调度算法的类型(1)非抢占式优先权算法主要用于批处理系统中，也可用于某些对实时性要求不严的实时系统中。(2)抢占式优先权调度算法能更好地满足紧迫作业的要求,故而常用于要求比较严格的实时系统中,以及对性能要求较高的批处理和分时系统中。2020/2/29292.优先权的类型(1)在创建进程时确定的，且在进程的整个运行期间保持不变。一般地。(2)动态优先权在创建进程时所赋予的优先权,是可以随进程的推进或随其等待时间的增加而改变的,以便获得更好的调度性能。2020/2/29303.高响应比优先调度算法(HRF)该算法是FCFS和SJF的结合，克服了两种算法的缺点。响应比最高的作业优先启动由于等待时间与服务时间之和,就是系统对该作业的响应时间，故该优先权又相当于响应比RP。据此，又可表示为要求服务时间要求服务时间等待时间优先权要求服务时间响应时间要求服务时间要求服务时间等待时间pR2020/2/2931对高响应比优先调度算法(HRF)的解释(1)如果作业的等待时间相同,则要求服务的时间愈短,其优先权愈高,因而该算法有利于短作业。(2)当要求服务的时间相同时,作业的优先权决定于其等待时间,等待时间愈长,其优先权愈高,因而它实现的是先来先服务。(3)对于长作业,作业的优先级可以随等待时间的增加而提高,当其等待时间足够长时,其优先级便可升到很高,从而也可获得处理机。2020/2/29323.2.1先来先服务和短作业优先算法3.2.2高优先权优先调度算法3.2.3基于时间片的轮转调度算法3.2调度算法2020/2/29333.2.3基于时间片的轮转调度算法1.时间片轮转法就绪进程按先来先服务的原则排成一个队列，每次调度时，把CPU分配给队首进程，并令其执行一个时间片。当执行的时间片用完时，停止该进程的执行，并将它送往就绪队列的末尾；然后，再把处理机分配给就绪队列中新的队首进程，同时也让它执行一个时间片。可以保证就绪队列中的所有进程,在一给定的时间内,均能获得一时间片的处理机执行时间。2020/2/2934图3-5多级反馈队列调度算法就绪队列1就绪队列2就绪队列3就绪队列nS1S2S3至CPU至CPU至CPU至CPU时间片：S1S2S3…SnSn2.多级反馈队列调度算法优先级高2020/2/2935设置多个就绪队列,并为各个队列赋予不同的优先级，各队列的优先权逐个降低。各个队列中进程执行时间片的大小也各不相同，在优先权愈高的队列中，为每个进程所规定的执行时间片就愈小。调度方式当一个新进程进入内存后,首先将它放入第一队列的末尾，按FCFS原则排队等待调度。当轮到该进程执行时,如它能在该时间片内完成,便可准备撤离系统;如果它在一个时间片结束时尚未完成,调度程序便将该进程转入第二队列的末尾，再同样地按FCFS原则等待调度执行；如果它在第二队列中运行一个时间片后仍未完成，再依次将它放入第三队列,……,如此下去，当一个长作业(进程)从第一队列依次降到第n队列后，在第n队列中便采取按时间片轮转的方式运行。2020/2/2936仅当第一队列空闲时,调度程序才调度第二队列中的进程运行;仅当第1~(i-1)队列均空时,才会调度第i队列中的进程运行。如果处理机正在第i队列中为某进程服务时,又有新进程进入优先权较高的队列(第1~(i-1)中的任何一个队列),则此时新进程将抢占正在运行进程的处理机,即由调度程序把正在运行的进程放回到第i队列的末尾,把处理机分配给新到的高优先权进程。2020/2/29373.多级反馈队列调度算法的性能(1)终端型作业用户终端型作业用户所提交的作业多属于交互型作业，通常较小，系统只要能使这些作业在第一队列所规定的时间片内完成即可。(2)短批处理作业用户若在第1队列中执行一个时间片即可完成，便可获得与终端型作业一样的响应时间。如在第一个队列中不能完成，只需在第2、3队列中各执行一个时间片。(3)长批处理作业用户长作业将依次在第1,2,3…,n队列中执行，