第三章 处理机调度与死锁 第三章第三章 处理机调度与死锁处理机调度与死锁 3.1 3.1 处理机调度的层次处理机调度的层次 3.2 3.2 调度队列模型和调度准则调度队列模型和调度准则 3.3 3.3 调度算法调度算法 3.4 3.4 实时调度实时调度 3.5 3.5 产生死锁的原因和必要条件产生死锁的原因和必要条件 3.6 3.6 预防死锁的方法预防死锁的方法 3.7 3.7 死锁的检测与解除死锁的检测与解除 1处理机调度与死锁par最新课件第三章 处理机调度与死锁 调度介绍调度介绍早期早期批处理系统，依次运行磁带上的作业。批处理系统，依次运行磁带上的作业。分时系统分时系统多个作业等候服务多个作业等候服务复杂一些的调度算法复杂一些的调度算法批处理与分时系统结合批处理与分时系统结合要决定下一个运行的是一个批处理作业还是一个交互用户要决定下一个运行的是一个批处理作业还是一个交互用户个人计算机个人计算机高端网络工作站和服务器高端网络工作站和服务器CPU是稀缺资源，是稀缺资源，好的调度可以提高好的调度可以提高系统性能和用户满系统性能和用户满意度。意度。2处理机调度与死锁par最新课件第三章 处理机调度与死锁 调度介绍调度介绍早期早期个人计算机个人计算机多数时间只有一个活动进程多数时间只有一个活动进程计算机速度极快计算机速度极快高端网络工作站和服务器高端网络工作站和服务器调度程序在简单的调度程序在简单的PC机机上并不重要。上并不重要。3处理机调度与死锁par最新课件第三章 处理机调度与死锁 调度介绍调度介绍早期早期个人计算机个人计算机高端网络工作站和服务器高端网络工作站和服务器多个进程经常竞争多个进程经常竞争CPU例如当例如当CPU必须在用户关闭窗口之后的屏幕刷新进程和运必须在用户关闭窗口之后的屏幕刷新进程和运行发送排队的电子邮件之间选择时。若关闭窗口花费行发送排队的电子邮件之间选择时。若关闭窗口花费2秒秒钟，而此时电子邮件正在发送，用户会注意到系统极端停钟，而此时电子邮件正在发送，用户会注意到系统极端停滞；而如果延迟滞；而如果延迟2秒钟发送电子邮件，用户根本不会注意秒钟发送电子邮件，用户根本不会注意到。这个例子中，进程调度如何处理是非常重要的。到。这个例子中，进程调度如何处理是非常重要的。调度程序要考虑调度程序要考虑CPU的利用率，因为进程切换的代的利用率，因为进程切换的代价是比较高的。价是比较高的。进程调度如何处理是进程调度如何处理是非常重要的。非常重要的。4处理机调度与死锁par最新课件第三章 处理机调度与死锁 3.1 处理机调度的层次处理机调度的层次 3.1.1 高级、中级和低级调度高级、中级和低级调度 1. 高级调度高级调度(High Scheduling) 在每次执行作业调度时，都须做出以下两个决定。 1) 接纳多少个作业 2) 接纳哪些作业 5处理机调度与死锁par最新课件第三章 处理机调度与死锁 2. 低级调度低级调度(Low Level Scheduling) 1) 非抢占方式(Non-preemptive Mode) 在采用非抢占调度方式时，可能引起进程调度的因素可归结为这样几个： 正正在在执执行行的的进进程程执执行行完完毕毕， 或或因因发发生生某某事事件件而而不不能能再再继继续续执执行行； 执执行行中中的的进进程程因因提提出出I/O请请求求而而暂暂停停执执行行； 在在进进程程通通信信或或同同步步过过程程中中执执行行了了某某种种原原语语操操作作，如如P操操作作(wait操操作作)、Block原语、原语、Wakeup原语等。原语等。 这种调度方式的优优点点是实实现现简简单单、系系统统开开销销小小，适用于大多数的批处理系统环境。但它难以满足紧急任务的要求立即执行，因而可能造成难以预料的后果。显然，在要求比较严格的实时系统中，不宜采用这种调度方式。 6处理机调度与死锁par最新课件第三章 处理机调度与死锁 2) 抢占方式抢占方式(Preemptive Mode) 抢占的原则有： (1)优先权原则。(2)(2) 短作业(进程)优先原则。 (3)(3) 时间片原则。 7处理机调度与死锁par最新课件第三章 处理机调度与死锁 3. 中级调度中级调度(Intermediate-Level Scheduling) 中级调度又称中程调度(Medium-Term Scheduling)。 引入中级调度的主要目的，是为了提提高高内内存存利利用用率率和和系系统统吞吞吐吐量量。 为此，应使那些暂时不能运行的进程不再占用宝贵的内存资源，而将它们调至外存上去等待，把此时的进程状态称为就就绪绪驻驻外外存存状状态态或挂挂起起状状态态。当这些进程重又具备运行条件、且内存又稍有空闲时，由中级调度来决定把外存上的哪些又具备运行条件的就绪进程，重新调入内存，并修改其状态为就绪状态，挂在就绪队列上等待进程调度。 8处理机调度与死锁par最新课件第三章 处理机调度与死锁 3.2 调度队列模型和调度准则调度队列模型和调度准则 1. 仅有进程调度的调度队列模型仅有进程调度的调度队列模型 图 3 - 1 仅具有进程调度的调度队列模型 3.2.1 调度队列模型调度队列模型9处理机调度与死锁par最新课件第三章 处理机调度与死锁 2. 具有高级和低级调度的调度队列模型具有高级和低级调度的调度队列模型 图 3-2 具有高、低两级调度的调度队列模型 (1)就绪队列的形式。就绪队列的形式。 (2)(2) 设置多个阻塞队列。设置多个阻塞队列。 图图 3-2 示示出出了了具具有有高高、低低两两级级调调度度的的调调度度队队列列模模型型。该该模模型型与与上上一一模型的主要区别在于如下两个方面。模型的主要区别在于如下两个方面。 10处理机调度与死锁par最新课件第三章 处理机调度与死锁 3. 同时具有三级调度的调度队列模型同时具有三级调度的调度队列模型 图 3-3 具有三级调度时的调度队列模型 11处理机调度与死锁par最新课件第三章 处理机调度与死锁 3.2.2 选择调度方式和调度算法的若干准则选择调度方式和调度算法的若干准则 1. 面向用户的准则面向用户的准则 (1) 周转时间短。周转时间短。 可把平均周转时间描述为： 作作业业的的周周转转时时间间T与与系系统统为为它它提提供供服服务务的的时时间间TS之之比比，即即W=T/TS，称称为为带带权权周周转转时时间间，而平均带权周转时间则可表示为: 12处理机调度与死锁par最新课件第三章 处理机调度与死锁 (2) 响应时间快。 (3) 截止时间的保证。 (4) 优先权准则。 13处理机调度与死锁par最新课件第三章 处理机调度与死锁 2. 面向系统的准则面向系统的准则 (1)系统吞吐量高。(2)(2) 处理机利用率好。 (3)(3) 各类资源的平衡利用。 14处理机调度与死锁par最新课件第三章 处理机调度与死锁 3.3 调调 度度 算算 法法 3.3.1 先来先服务和短作业先来先服务和短作业(进程进程)优先调度算法优先调度算法 1. 先来先服务调度算法先来先服务调度算法 15处理机调度与死锁par最新课件第三章 处理机调度与死锁 图 3-4 FCFS和SJF调度算法的性能 3.23.216处理机调度与死锁par最新课件第三章 处理机调度与死锁 2. 短作业短作业(进程进程)优先调度算法优先调度算法 短作业(进程)优先调度算法SJ(P)F，是指对短作业或短进程优先调度的算法。它们可以分别用于作业调度和进程调度。 短作业优先(SJF)的调度算法，是从后备队列中选择一个或若干个估计运行时间最短的作业，将它们调入内存运行。 短进程优先(SPF)调度算法，则是从就绪队列中选出一估计运行时间最短的进程，将处理机分配给它，使它立即执行并一直执行到完成，或发生某事件而被阻塞放弃处理机时，再重新调度。17处理机调度与死锁par最新课件第三章 处理机调度与死锁 图 3-4 FCFS和SJF调度算法的性能 3.23.218处理机调度与死锁par最新课件第三章 处理机调度与死锁 SJ(P)F调度算法也存在不容忽视的缺点缺点： (1) 该算法对长作业不利，如作业C的周转时间由10增至16，其带权周转时间由2增至3.1。更严重的是，如果有一长作业(进程)进入系统的后备队列(就绪队列)，由于调度程序总是优先调度那些(即使是后进来的)短作业(进程)，将导致长作业(进程)长期不被调度。 (2) 该算法完全未考虑作业的紧迫程度，因而不能保证紧迫性作业(进程)会被及时处理。 (3) 由于作业(进程)的长短只是根据用户所提供的估计执行时间而定的，而用户又可能会有意或无意地缩短其作业的估计运行时间，致使该算法不一定能真正做到短作业优先调度。 19处理机调度与死锁par最新课件第三章 处理机调度与死锁 先来先服先来先服务短作短作业优先先高响高响应比比优先先时间片片轮转多多级反反馈队列列能否是可能否是可抢占占否否能能能能能能队列内不一定列内不一定能否是不可能否是不可抢占占能能能能能能否否队列内不一定列内不一定优点点公平，公平，实现简单，利于利于CPU繁忙型繁忙型平均等待平均等待时间最少，效最少，效率最高率最高兼兼顾长短作短作业兼兼顾长短作短作业兼兼顾长短作短作业，有有较好的响好的响应时间，利于，利于终端型端型作作业和短批和短批处理理作作业缺点缺点不利于短作不利于短作业，不利用，不利用I/O繁忙型繁忙型长作作业会会饥饿，估估计时间不易不易确定，未考确定，未考虑紧迫程度迫程度计算响算响应比比的开的开销大大平均等待平均等待时间较长，上下文，上下文切切换浪浪费时间尤其适用于尤其适用于作作业调度，度，批批处理系理系统分分时系系统相当通用相当通用能否用于作能否用于作业调度度能能能能能能否否否否能否用于能否用于进程程调度度能能能能能能能能能能 调度算法比较调度算法比较20处理机调度与死锁par最新课件第三章 处理机调度与死锁 关于调度算法的几点说明：关于调度算法的几点说明：（1）批处理系统、分时系统和实时系统中的主要调度算法：）批处理系统、分时系统和实时系统中的主要调度算法：l批处理系统批处理系统中即设有作业调度，又设有进程调度。批处理系中即设有作业调度，又设有进程调度。批处理系统中的作业调度算法有先来先服务（统中的作业调度算法有先来先服务（FCFS）、短作业优先）、短作业优先（SJF）、优先级调度（）、优先级调度（HPF）和高响应比优先（）和高响应比优先（RF）。批处）。批处理系统的进程调度算法有：先进先出（理系统的进程调度算法有：先进先出（FIFO）、短进程优先）、短进程优先（SPF）、优先级调度（）、优先级调度（PRI）和高响应比优先（）和高响应比优先（RF）。）。l分时系统中分时系统中只设有进程调度，不设作业调度。其进程调度算只设有进程调度，不设作业调度。其进程调度算法只有轮转法（法只有轮转法（RR）一种。）一种。21处理机调度与死锁par最新课件第三章 处理机调度与死锁 关于调度算法的几点说明：关于调度算法的几点说明：实时系统实时系统中只设有进程调度，不设作业调度。其进程调度中只设有进程调度，不设作业调度。其进程调度算法有：轮转法（算法有：轮转法（RR）、优先级调度算法（）、优先级调度算法（HPF）。后者）。后者又可细分为：非抢占式优先级调度、抢占式优先级调度又可细分为：非抢占式优先级调度、抢占式优先级调度（基于时钟中断的抢占式优先级调度和立即抢占的优先级（基于时钟中断的抢占式优先级调度和立即抢占的优先级调度）。调度）。说明：实时系统中不可以使用先进先出（说明：实时系统中不可以使用先进先出（FIFO）和短进）和短进程优先算法（程优先算法（SPF）。）。（2）时间片轮转法：分时系统中，多个进程以轮流方式）时间片轮转法：分时系统中，多个进程以轮流方式分享分享CPU，一般与进程的优先级、进程进入就绪队列的时，一般与进程的优先级、进程进入就绪队列的时间、进程的长短等无关。间、进程的长短等无关。22处理机调度与死锁par最新课件第三章 处理机调度与死锁 【例】有【例】有5个任务个任务A，B，C，D，E，它们几乎同时到达，预，它们几乎同时到达，预计它们的运行时间为计它们的运行时间为10，6，2，4，8min。其优先级分别为。其优先级分别为3，5，2，1和和4，这里，这里5为最高优先级。对于下列每一种调度算法，为最高优先级。对于下列每一种调度算法，计算其平均进程周转时间（进程切换开销可不考虑）。计算其平均进程周转时间（进程切换开销可不考虑）。（1）先来先服务（按）先来先服务（按A，B，C，D，E）算法。）算法。 23处理机调度与死锁par最新课件第三章 处理机调度与死锁 解：解：（1）采用先来先服务（）采用先来先服务（FCFS）调度算法时，）调度算法时，5个任务在系个任务在系统中的执行顺序、完成时间及周转时间如表统中的执行顺序、完成时间及周转时间如表3-2所示：所示：表表3-2 采用先来先服务（采用先来先服务（FCFS）调度算法）调度算法执行次序执行次序到达时间到达时间服务时间服务时间开始执行时间开始执行时间完成时间完成时间周转时间周转时间A01001010B06101616C02161818D04182222E082230305个进程的平均周转时间个进程的平均周转时间T为：为：T=（10+16+18+22+30）/5=19.2min24处理机调度与死锁par最新课件