《操作系统》第3章处理机调度与死锁.ppt

操作系统原理Principles of Operating System,2,第3章 处理机调度与死锁,处理机是计算机系统中的重要资源，处理机调度就是按照一定的规则分派处理机，合理地分配和使用处理机。传统操作系统处理机调度的单位是进程，现代操作系统处理机调度的单位是线程。如何在进程间或线程间分配和回收处理机，处理机调度算法对整个计算机系统的综合性能指标有重要影响，不仅影响处理机的利用率和用户进程的执行，还与内存等其他资源的使用密切相关。,3,3.1.1 处理机调度的类型,我们可把处理机调度分成宏观调度（作业调度）、中程调度（交换调度，涉及进程在内存和外存之间的交换）和微观调度（进程调度和线程调度）三个层次。,4,具有三级调度的调度队列模型,5,3.1.2 宏观调度,宏观调度在多道批处理系统中对应作业调度，就是按照系统所规定的调度算法从系统已接纳的一批作业中选取一个子集，做好运行前的准备工作，使其进入内存并运行。现代操作系统中一般不配备作业调度。作业调度完成以下几方面的工作：按某种调度算法从后备队列中选取一个子集。为选中的作业子集分配所需的资源，如内存、外设等。为选中的作业子集创建相关进程。填写修改被选中的作业的JCB及有关表格。作业完成时的善后工作。,6,3.1.3 微观调度,微观调度也称低级调度，微观调度才是真正的处理机调度，在实际系统中对应线程调度、进程调度或任务调度。微观调度要解决的问题WHAT：按什么原则分配CPU，即调度算法。WHEN：何时分配CPU，即调度的时机。HOW：如何分配CPU，即调度过程，进程的上下文切换。,7,进程调度器,操作系统为了对进程进行有效的监控，需要维护一些与进程相关的数据结构，记录所有进程的运行状况，并在进程出让处理机或调度程序剥夺执行状态进程占用的处理机时，选择适当的进程分派处理机，完成上下文切换。我们把操作系统内核中与进程调度相关代码称为进程调度器(dispatcher)。,8,调度方式,非剥夺方式：也叫非抢占方式，调度程序一旦把处理机分配给某进程或线程后便让它一直执行下去，直到进程或线程完成或等待某事件而阻塞时，才把处理机分配给另一个进程或线程。剥夺方式：也叫抢占方式，当一个进程或线程正在执行时，系统可以基于某种原则，剥夺已分配给它的处理机，将处理机分配给其他进程或线程。常用的剥夺原则有优先权原则和时间片原则。,9,3.2 调度算法,选择调度方式和算法的若干准则调度算法的确定基于一定因素，我们希望好的调度算法是，系统运行尽能多的任务，使CPU保持忙，使I/O保持忙，对所有任务公平合理，也要有轻重缓急，重要的任务优先处理。衡量操作系统及计算机系统的重要指标如下：周转时间短。响应时间快。截止时间的保证。优先权准则。系统吞吐量高处理机利用率好各类资源的平衡利用-是面向用户的指标，-是面向系统的指标。采用何种调度方法，是衡量操作系统及计算机系统的重要指标之一。指标的好与差，对系统的使用直接产生影响。,10,调度性能评价指标,CPU的利用率：CPU是一个重要且昂贵的资源，人们需要使CPU尽可能忙，并希望它的利用率越高越好。CPU使用率从0到100，对于真实系统，它应从40(轻负荷系统)到90(重负荷使用的系统)。读者要注意CPU的利用率和使用率的含义，如果运行进程的个数多，各进程之间的时间片切换频繁，CPU的使用率很高，但将造成CPU的利用率越低。吞吐量：如果CPU忙于执行进程，那么就要评估其工作量。其中一种测量工作量的方法称为吞吐量，吞吐量是指单位时间内所完成任务的数量。,11,周转时间：从一个特定任务的角度来看，重要指标是运行该任务需要花费多长时间。即从任务提交到任务完成的时间间隔称为周转时间。周转时间Ti：Ti=Tci-Tpi(Tpi-进程提交时间，Tci-进程完成时间)。周转时间是以下所有时间段之和，包括等待进入内存、在就绪队列中等待、阻塞队列中的等待时间、在CPU上执行等。等待时间包括等待进入内存、在就绪队列中等待、阻塞队列中的等待时间。故Ti=Twi+Tsi(Twi-进程等待时间，Tsi-进程执行时间)。为了去除进程本身因素的影响，在讨论处理机调度时也使用平均周转时间T和平均带权周转时间W作为衡量指标。平均周转时间T设：系统中有n个任务，则平均周转时间T为：(i=1，2，n)利用平均周转时间可衡量不同调度算法对相同任务流的调度性能。带权周转时间W：带权周转时间是用周转时间除以进程的执行时间，能够合理反映任务长短差别的指标。Wi=Ti/Tsi=（Twi+Tsi）/Tsi,12,平均带权周转时间：(i=1，2，n)利用平均带权周转时间可比较某种调度算法对不相同任务流的调度性能。响应时间：对于交互式系统，周转时间并不是最佳指标。另一时间度量是从提交请求到产生第一响应的时间，我们称为响应时间。响应时间是开始响应所需要的时间，而不是输出该响应所需要的时间。周转时间通常受输出设备速度的限制，响应时间是分时系统中衡量系统交互性能的指标。截止时间：在实时系统中，还使用截止时间来衡量系统的实时性能，截止时间可分为开始截止时间和完成截止时间。,13,3.2.2 调度算法,先来先服务调度算法先来先服务调度算法(First Come First Server，FCFS)，总是把处理机分配给最先进入就绪队列的进程或线程。由于它的处理机调度采用非抢占方式，一个进程或线程一旦分得处理机，便执行下去，直到该进程或线程完成或阻塞时，才释放处理机。先来先服务调度算法很简单，很“公平”，但对进程或线程的特殊要求（没有考虑进程的优先级）无法满足，一般作为子调度算法，先来先服务调度算法的例子如表3-1所示。该算法适合于进程调度、线程调度、任务调度、作业调度和其他资源调度等。,14,先来先服务调度算法例子,15,最短作业优先调度算法,在最短作业优先调度算法中，作业的长短是以要求运行时间来衡量的，这种算法优先调度要求运行时间最短的作业作为处理机的服务对象。最短作业优先调度算法的例子如表3-2所示。,16,最高响应比优先算法,响应比高者优先算法就是在每调度一个作业投入运行时，计算后备作业表中每个作业的响应比，挑选响应比最高者作为处理机的服务对象。响应比R=(等待时间+要求运行时间)要求运行时间。它是FCFS和SJF的一种折中。采用响应比高者优先调度算法例子如表3-3所示。,17,优先权算法,静态优先权法：是指在创建进程时确定进程优先权，并一直保持到进程结束，即“终生”不变。影响进程的静态优先权的主要因素包括进程类型、进程的资源需求和用户要求。通常系统进程的优先权高于其他用户进程，对处理机、内存和打开文件的数量等资源要求较少的进程优先权较高。进程优先权也可按用户的紧急程度和付费情况等来确定。动态优先权法：是指在创建进程时赋予进程的优先权，在进程的生命期内优先权可以动态变化，在进程运行过程中可以自动改变优先权，以便获得更好的调度性能。影响进程动态优先权变化的因素包括进程等待时间和占用处理机时间等，一个进程在就绪队列中等待的时间越长，它的优先权会越高。这种做法的目的是使优先级较低的进程在等待足够的时间后，提高其优先权，提高被调度执行机会。一个进程占用处理机执行的时间越长，它的优先权就会越低。这种做法的目的是使持续执行的进程会在优先权降低后出让处理机。,18,静态优先权和动态优先权都是基于合理分配CPU时间和紧迫的进程优先的原则。优先权调度可以是可抢占的或者非抢占的。当一个进程到达就绪队列时，其优先权与当前运行进程的优先权相比较。如果新到达进程的优先权高于当前运行进程的优先权，那么抢占优先权调度算法会抢占CPU。非抢占优先权调度算法只是将新进程加到就绪队列的头部。优先权调度算法需要考虑饥饿问题，就是某些就绪进程无穷等待CPU。据说，在1973年关闭MIT的IBM 7094时，发现有一个低优先权进程是于1967年提交但是一直未运行。适合于进程调度、线程调度、任务调度、作业调度和资源调度等。,19,时间片轮转法,轮转法调度算法是专门为分时系统而设计的，时间片轮转算法主要用于微观调度。在时间片轮转算法中，系统中所有的就绪进程按照FCFS原则，排成一个队列，新增加进程到就绪队列的尾部。每次调度时将处理机分派给队首进程，让其执行一个时间片。时间片的长度从几个毫秒到几百毫秒。在一个时间片结束时，发生时钟中断，进程调度器暂停当前进程的执行，将其送到就绪队列的末尾，并通过上下文切换执行当前的队首进程。进程可以因阻塞在未使用完一个时间片时就出让处理机。轮转法的性能很大程度上依赖于时间片的大小。在极端情况下，如果时间片非常长，长到大多数进程可在一个时间片内执行完，该算法将退化为FCFS算法。此时进程的响应时间长，不能达到提高响应特性的目标。如果时间片过短，用户的一次交互过程需要多个时间片才能处理完，此时上下文切换次数增加，将造成CPU的利用率越低。,20,多级队列算法,多级队列算法(MLQ)是先来先服务算法、时间片轮转算法和优先权算法的综合。其基本思想是将就绪队列分成多个独立队列，相同优先权的进程按FIFO原则排成一个队列，按时间片轮转算法分派CPU。不同队列可有不同的优先权、不同的时间片长度。在多级队列算法中，优先调度优先权高的队列，当优先权高的队列为空时，才可以调度下一级队列，依次类推，同一队列按时间片轮转算法分派CPU。此算法的性能好，适合于线程调度、进程调度或任务调度。且比较容易实现，实用性好，被目前流行的操作系统采用，如NT、UNIX等。,21,多级反馈队列法,多级反馈队列也是系统中设置多个就绪队列，对每个队列赋予各不相同的优先权。它的每个队列按不同优先权给于不同的时间片，优先权越大，时间片越短，优先权越小，时间片越长。同时，每个进程并不固定在一个队列上，系统将新创建的进程放入优先权最高的队列中去。当它在CPU上运行完一个时间片以后并被投入下一个队列，每个队列均按先进先出的算法组织，而CPU则先执行最高优先级队列中的进程，当其队列空时，便执行下一队列的进程。如图3-3所示，图中时间片S1S2S3 Sn，,22,首先系统中设置多个就绪队列。每个就绪队列分配给不同时间片，优先权高的为第一级队列，时间片最短，随着队列级别的降低，时间片加长。各个队列按照先进先出调度算法。一个新进程就绪后进入第一级队列。进程因等待事件而放弃CPU后，进入等待队列，一旦等待的事件发生，则回到原来的就绪队列。当有一个优先权更高的进程就绪时，可以抢占CPU，被抢占进程回到原来一级就绪队列末尾。当高级队列都为空时，就去调度下一级队列。当时间片到后，进程放弃CPU，进入下一级就绪队列。,23,3.3 死锁的概念,可重用资源(reusable resource)，各个进程可以轮流使用，如处理机、内存、I/0外设、文件等都是可重用资源，在使用可重用资源时可能出现的死锁（Deadlock）。通常是由于各进程巳拥有部分资源，同时请求其他进程已占有的资源，从而造成永远等待。可消耗资源(consumableresource)是指可以动态生成和动态消耗的资源，一般不限制数量，如中断、信号量、消息、缓冲区等都是可消耗资源。由于可消耗资源的生成和消耗存在依赖关系，因此他们的使用也可能因为双方都等待对方生成资源而形成死锁。,24,一般教材的死锁定义：多个进程因竞争资源而造成的一种僵局状态，若无外力作用，这些进程都将永远不能再向前推进。这种状态就是死锁。我们把死锁定义如下：在多个进程并发执行中，某进程申请的资源被其他等待进程占有，如果该等待进程永远无法改变其等待状态，这种情况我们称为死锁。如果该等待进程长期无法改变其等待状态，这种情况我们称为饥饿。关于死锁的一些结论如下：参与死锁的进程最少是两个（两个以上进程才会出现死锁）。参与死锁的进程至少有两个已经占有资源。参与死锁的所有进程都在等待事件。参与死锁的进程是当前系统中所有进程的子集。,25,3.3.2 资源分配图,资源类:用方框表示资源的不同类型。资源实例:用方框中的黑圆点表示每个资源的数量。进程:用圆圈中加进程名表示。分配边：资源实例进程的一条有向边，即RjPi。申请边：进程资源类的一条有向边，即PiRj。,26,3.3.3 产生死锁的原因,资源不足，引起资源竞争进程推进顺序不合理,27,3.3.4 死锁产生的必要条件,互斥条件。进程要求对所分配的资源进行排他性使用，即在一段时间内某资源仅为一个进程所占用。不剥夺条件。进程所获得的资源在未使用完毕之前，不能被其他进程强行夺走，即只能由获得该资源的进程自己来释放。请求和保持条件。进程每次申请所需要的一部分资源，在等待新资源的同时，进程继续占有已分配到的资源。循环等待条件。存在进程资源的循环等待链，链中的每一个进程已获得资源，同时被链中的下一个进程所请求。,28,