操作系统chapter3.ppt

《操作系统chapter3.ppt》由会员分享，可在线阅读，更多相关《操作系统chapter3.ppt（156页珍藏版）》请在三一文库上搜索。

1、第三章 处理机调度与死锁,第三章 处理机调度与死锁,3.1 处理机调度的层次 3.2调度队列模型和调度准则 3.3调度算法 3.4实时调度 3.5 产生死锁的原因和必要条件 3.6 预防死锁的方法 3.7 死锁的检测和解除,3.1 处理机调度的层次,在多道程环境下，进程数目往往多于处理机数目，致使它们争用处理机。这就要求系统能按某种算法，动态地把处理机分配给就绪队列中的一个进程，使之执行。分配处理机的任务是由进程调度程序完成的。它是操作系统设计的中心问题之一。,进程调度要解决的问题,WHAT：按什么原则分配CPU 进程调度算法 WHEN：何时分配CPU 进程调度的时机 HOW： 如何分配CPU

2、 CPU调度过程（进程的上下文切换）,3.1 处理机调度的层次,处理机是计算机系统中的重要资源 处理机调度算法对整个计算机系统的综合性能指标有重要影响 可把处理机调度分成三个层次： 高级调度 中级调度 低级调度,3.1.1 高级调度,高级调度又称为作业调度或长程调度。长程调度决定哪些作业可参与竞争CPU和其他资源，即决定给哪个作业分配一台虚拟处理机，它的调度对象是作业，它是处理机的宏观调度。,1作业和作业步,(1)作业(Job)。它不仅包含了通常的程序和数据，而且还应配有一份作业说明书，系统根据该说明书来对程序的运行进行控制。在批处理系统中，是以作业为基本单位从外存调入内存的。,(2) 作业步

3、(Job Step)。通常，在作业运行期间，每个作业都必须经过若干个相对独立，又相互关联的顺序加工步骤才能得到结果，我们把其中的每一个加工步骤称为一个作业步，各作业步之间存在着相互联系，往往是把上一个作业步的输出作为下一个作业步的输入。,1作业和作业步,1作业和作业步,(3) 作业流。若干个作业进入系统后，被依次存放在外存上，这便形成了输入的作业流；在操作系统的控制下，逐个作业进行处理，于是便形成了处理作业流。,2作业控制块JCB(Job Control Block),每个作业进入系统时由系统为其建立一个作业控制块JCB（Job Control Block)，其中保存了系统对作业进行管理和调度

4、所需的全部信息. 通常包含的内容有：作业标识、用户名称、用户帐户、作业类型、作业状态、调度信息、资源需求、进入系统时间、开始处理时间、作业完成时间、作业退出时间、资源使用情况等。,3.作业调度,作业调度的主要功能是根据作业控制块中的信息，审查系统能否满足用户作业的资源需求，以及按照一定的算法，从外存的后备队列中选取某些作业调入内存，并为它们创建进程、分配必要的资源。然后再将新创建的进程插入就绪队列，准备执行。因此，有时也把作业调度称为接纳调度(Admission Scheduling)。,3作业调度,作业调度的主要任务是完成作业从后备状态到执行状态和从执行状态到完成状态的转变。 作业调度功能：

5、 1.记录已进入系统的各作业的情况（JCB，Job Control Block）； 2.按一定的调度算法，从后备作业中选择一个或几个作业进入系统内存； 3.为被选中的作业创建进程，并且为其申请系统资源； 4.作业结束后作善后处理工作。,3作业调度,每次执行作业调度时，都须做出以下两个决定 1) 决定接纳多少个作业 作业调度每次要接纳多少个作业进入内存，取决于多道程序度(Degree of Multiprogramming)， 2) 决定接纳哪些作业 应将哪些作业从外存调入内存，这将取决于所采用的调度算法。,作业与进程的关系,每一个作业将动态地转换成了一组运行实体进程组，并由此来完成该作业所需要

6、完成的一系列加工步骤，当作业所对应的进程完成时，作业便进入了完成状态，整个作业也就完成了。,3.1.2 低级调度,通常也把低级调度称为进程调度或短程调度，它所调度的对象是进程(或内核级线程)。进程调度是最基本的一种调度，在多道批处理、分时和实时三种类型的OS中，都必须配置这级调度。,1低级调度的功能,低级调度的任务是控制协调进程对CPU的竞争,按一定的调度算法决定就绪队列中的哪个进程应获得处理机，然后再由分派程序执行把处理机分配给该进程的具体操作。 (1) 保存处理机的现场信息。 (2) 按某种算法选取进程。 (3) 把处理器分配给进程。,2进程调度中的三个基本机制,为了实现进程调度，应具有如

7、下三个基本机制： (1) 排队器。将系统中所有的就绪进程按照一定的方式排成一个或多个队列，以便调度程序能最快地找到它。 (2) 分派器。分派器把由进程调度程序所选定的进程，从就绪队列中取出该进程，然后将处理机分配给它 (3) 上下文切换机制。当对处理机进行切换时，会发生两对上下文切换操作。,3进程调度方式,进程调度可采用下述两种调度方式。 1) 非抢占方式(Nonpreemptive Mode) 在采用这种调度方式时，一旦把处理机分配给某进程后，不管它要运行多长时间，都一直让它运行下去，决不会因为时钟中断等原因而抢占正在运行进程的处理机，也不允许其它进程抢占已经分配给它的处理机。,3进程调度方

8、式,在采用非抢占调度方式时，可能引起进程调度的因素可归结为如下几个： (1) 正在执行的进程执行完毕，或因发生某事件而不能再继续执行； (2) 执行中的进程因提出I/O请求而暂停执行； (3) 在进程通信或同步过程中执行了某种原语操作，如P操作(wait操作)、Block原语、Wakeup原语等。,3进程调度方式,非抢占方式的优点：系统开销小；采用非抢占方式时，程序员可以在某种程度上预知进程的运行轨迹，程序设计相应简化。 缺点：损失了系统的并发性，使系统不能根据内部的并发事件及时实施进程调度，难以实现要求比较严格的实时调度要求。,3进程调度方式,2) 抢占方式(Preemptive Mode)

9、 这种调度方式允许调度程序根据某种原则去暂停某个正在执行的进程，将已分配给该进程的处理机重新分配给另一进程。抢占方式的优点是，可以防止一个长进程长时间占用处理机，能为大多数进程提供更公平的服务，特别是能满足对响应时间有着较严格要求的实时任务的需求。抢占调度方式是基于一定原则的：,3进程调度方式,(1) 优先权原则。通常是对一些重要的和紧急的作业赋予较高的优先权。允许优先权高的新到进程抢占当前进程的处理机。 (2) 短作业(进程)优先原则。短作业(进程)可以抢占当前较长作业(进程)的处理机。 (3) 时间片原则。各进程按时间片轮流运行，当一个时间片用完后，便停止该进程的执行而重新进行调度。,3.

10、1.3 中级调度,又称中程调度，对换调度。为提高内存的利用率和系统的呑吐量，中级调度决定哪些进程被允许参与竞争处理器资源，哪些进程调至外存上去等待，在合适的情况下，再重新调入内存，并将其挂在就绪队列上，以恢复对处理器资源的竞争。,3.2 调度队列模型和调度准则,3.2.1 调度队列模型 1仅有进程调度的调度队列模型 在分时系统中，通常仅设置了进程调度，用户键入的命令和数据都直接送入内存。对于命令，是由OS为之建立一个进程。系统可以把处于就绪状态的进程组织成栈、树或一个无序链表，至于到底采用其中哪种形式，则与OS类型和所采用的调度算法有关。,1仅有进程调度的调度队列模型,每个进程在执行时都可能出

11、现以下三种情况： (1) 任务在给定的时间片内已经完成，该进程便在释放处理机后进入完成状态； (2) 任务在本次分得的时间片内尚未完成，OS便将该任务再放入就绪队列的末尾； (3) 在执行期间，进程因为某事件而被阻塞后，被OS放入阻塞队列。,图 仅具有进程调度的调度队列模型,2具有高级和低级调度的调度队列模型,在批处理系统中，不仅需要进程调度，而且还需有作业调度，由后者按一定的作业调度算法，从外存的后备队列中选择一批作业调入内存，并为它们建立进程，送入就绪队列，然后才由进程调度按照一定的进程调度算法选择一个进程，把处理机分配给该进程。,3同时具有三级调度的调度队列模型,当在OS中引入中级调度后

12、，人们可把进程的就绪状态分为内存就绪(表示进程在内存中就绪)和外存就绪(进程在外存中就绪)。类似地，也可把阻塞状态进一步分成内存阻塞和外存阻塞两种状态。在调出操作的作用下，可使进程状态由内存就绪转为外存就绪，由内存阻塞转为外存阻塞；在中级调度的作用下，又可使外存就绪转为内存就绪。,3同时具有三级调度的调度队列模型,3.2.2选择调度方式和调度算法的若干准则,1面向用户的准则 (1)周转时间短 所谓周转时间是指从作业被提交给系统开始，到作业完成为止的这段时间间隔。包括：1、作业在外存后备队列上等待调度的时间，2、进程在就绪队列上等待进程调度的时间,3 、进程在CPU上执行的时间，4 、进程等待I

13、/O操作完成的时间。,1面向用户的准则,作业的周转时间： ti = tci-tsi ti:作业周转时间 tci：作业完成时间 tsi: 作业提交时间,其中，n为被测定作业流中的作业数,1面向用户的准则,T：衡量不同调度算法对同一个作业流的性能 W：同一调度算法对不同作业流的性能衡量,1面向用户的准则,(2)响应时间快 所谓响应时间是指从用户通过键盘提交一个请求开始，直至系统首次产生响应为止的时间。包括：1、从键盘输入的请求信息传送到处理机的时间，2、处理机对请求信息进行处理的时间，3、以及将所形成的响应信息送回到终端显示器的时间。,1面向用户的准则,(3)截至时间的保证 所谓截止时间是指某任务

14、必须开始执行的最迟时间，或者必须完成的最迟时间。 (4)优先权准则 为了便于让某些紧急的作业能得到及时的处理，在选择调度算法时还应该遵循优先权准则。,2面向系统的准则,(1)系统吞吐量高 所谓吞吐量是指在单位时间内系统所完成的工作量。 (2)处理机利用率好 (3)各类资源的平衡使用,3.3 调 度 算 法,先进先出(FIFO)算法 短作业(进程)优先调度算法 高优先权优先调度算法 时间片轮转法 多级反馈队列,3.2.1 先来先服务和短作业(进程)优先调度算法,1先来先服务调度算法 将用户作业和就绪进程按提交顺序或变为就绪状态的先后排成队列，并按照先来先服务的方式进行调度处理，是一种最普遍和最简

15、单的方法。它优先考虑在系统中等待时间最长的作业，而不管要求运行时间的长短。,1先来先服务调度算法,该调度方式属于非抢占方式，获得处理机的进程将一直运行，直到该进程完成或因进程本身发生某事件而阻塞后，才放弃处理机。,1先来先服务调度算法,FCFS算法比较有利于长作业(进程)，而不利于短作业(进程)。下表列出了JOB1、JOB2、JOB3、JOB4四个作业分别到达系统的时间、要求服务的时间、开始执行的时间及各自的完成时间，并计算出各自的周转时间和带权周转时间。,1先来先服务调度算法,这种调度从形式上讲是公平的，但它使短作业要等待长作业的完成，重要的作业要等待不重要作业的完成。从这个意义上讲又是不公

16、平的。 先进先出调度使响应时间的变化较小，因此它比其它大多数调度都可预测。由于这种调度方法不能保证良好的响应时间，在处理交互式用户时很少用这种方法。 这种调度算法突出的优点是实现简单，但效率较低。,2短作业(进程)优先调度算法,短作业优先调度算法(SJF)是指对短作业优先调度，即从后备队列中选择一个或若干个估计运行时间最短的作业，将它们调入内存。 短进程优先调度算法(SPF)，是指对短进程优先调度，即从就绪队列中选择一个或若干个估计运行时间最短的进程，为它们分配处理机，使之投入运行。,2短作业(进程)优先调度算法,图 FCFS和SJF调度算法的性能,FCFS和SJF的性能比较,2短作业(进程)

17、优先调度算法,SJ(P)F调度算法也存在不容忽视的缺点： 该算法对长作业不利。 (2) 该算法完全未考虑作业的紧迫程度，因而不能保证紧迫性作业(进程)会被及时处理。 (3) 由于作业(进程)的长短只是根据用户所提供的估计执行时间而定的，使该算法不一定能真正做到短作业优先调度。,3.3.2 高优先权优先调度算法,使用该算法前，系统将根据某些因素赋予每一个作业或进程一个对应的优先权，当用于作业调度时，从后备队列中选择若干个优先权最高的作业调入内存；当用于进程调度时，则把处理机分配给就绪队列中优先权最高的进程。 优先权在调度过程中所起的作用与系统对进程调度采用非抢占式调度策略还是抢占式调度策略有关,

18、1优先权调度算法的类型,1) 非抢占式优先权算法 在这种方式下，系统一旦把处理机分配给就绪队列中优先权最高的进程后，该进程便一直执行下去，直至完成；或因发生某事件使该进程放弃处理机时，系统方可再将处理机重新分配给另一优先权最高的进程。这种调度算法主要用于批处理系统中；也可用于某些对实时性要求不严的实时系统中。,1优先权调度算法的类型,2) 抢占式优先权调度算法 在这种方式下，系统同样是把处理机分配给优先权最高的进程，使之执行。但在其执行期间，只要又出现了另一个其优先权更高的进程，进程调度程序就立即停止当前进程(原优先权最高的进程)的执行，重新将处理机分配给新到的优先权最高的进程。,2优先权的类

19、型,该算法总是把处理机分配给就绪队列中具有最高优先权的进程。首先考虑的问题是如何确定进程的优先数，一种是静态优先数，另一种是动态优先数。 静态优先数法：静态优先权是在创建进程时确定的，在整个运行期间不再改变。,2优先权的类型,确定进程优先权的依据有如下三个方面： (1) 进程类型。通常，系统进程(如接收进程、对换进程、磁盘I/O进程)的优先权高于一般用户进程的优先权。 (2) 进程对资源的需求。如进程的估计执行时间及内存需要量的多少，对这些要求少的进程应赋予较高的优先权。 (3) 用户要求。这是由用户进程的紧迫程度及用户所付费用的多少来确定优先权的。,2优先权的类型,动态优先权是指在创建进程时

20、所赋予的优先权，但在其生命周期内优先权可以动态变化。如随进程的推进或随其等待时间的增加而改变的，以便获得更好的调度性能。,3高响应比优先调度算法,先来先服务和短作业优先算法都有其片面性，先来先服务调度算法只考虑作业的等待时间，而忽视了作业的运行时间，短作业优先算法则相反，只考虑了作业的运行时间，而忽视了作业的等待时间。响应比高者优先调度算法是介于这两种算法之间的一种拆衷的算法。,3.高响应比优先调度算法,优先权的变化规律可描述为：,由于等待时间与服务时间之和，就是系统对该作业的响应时间，故该优先权又相当于响应比RP。据此，又可表示为：,算法特点,(1) 作业的等待时间相同，则要求服务的时间愈短

21、，其优先权愈高，因而该算法有利于短作业。 (2) 服务的时间相同时，作业的优先权决定于其等待时间，等待时间愈长，其优先权愈高，因而它实现的是先来先服务。 (3) 对于长作业，作业的优先级可以随等待时间的增加而提高，当其等待时间足够长时，其优先级便可升到很高，从而也可获得处理机。,3.3.3 基于时间片的轮转调度算法,1时间片轮转法 1）基本原理 进程调度程序总是选择就绪队列中的第一个进程，也就是说按照先来先服务原则调度，但一旦进程占用处理机则仅使用一个时间片。在使用完一个时间片后，进程还没有完成其运行，它必须释放出处理机给下一个就绪的进程，返回到就绪队列的末尾重新排队等待再次运行。,简单轮转法

22、的调度模型,1时间片轮转法,2) 时间片大小的确定 在轮转法中，时间片长度的选取非常重要，时间片长度的选择会直接影响系统开销和响应时间。 当时间片很大时，每个进程得到比完成该进程多的处理机时间，此时轮转调度模式退化为先进先出模式。 当时间片非常小时，进程间的转换开销就成了决定因素，系统性能降低，大多数时间都消耗在处理机的转换上，只有少许用在用户的计算上。,1时间片轮转法,时间片的大小是该算法中的一个重要因素。应综合考虑以下几个因素来确定： 系统对响应时间的要求。系统要求对用户的响应时间短，则时间片要短；反之，时间片可以长一些。 就绪队列中进程的数目。进程数目多，则时间片应短一些。 系统的处理能

23、力。 CPU运行速度快,则时间片可以短；反之，时间片可以长一些。,图 q=1和q=4时的进程运行情况,图 q=1和q=4时进程的周转时间,2多级反馈队列调度算法,在多级反馈队列调度下，就绪队列被分为若干个独立子队列。 但进程不是根据其性质或类型固定地分属于一个队列，而是根据其使用CPU时间的长短来动态地决定进程属于哪级队列。,2多级反馈队列调度算法,（1） * 首先系统中设置多个就绪队列 * 每个就绪队列分配给不同时间片，优先级高的为第一级队列，时间片最小，随着队列级别的降低，时间片加大 * 各个队列按照先进先出调度算法，最后一级采用时间片轮转,（2） * 一个新进程就绪后进入第一级队列末尾

24、* 进程由于等待而放弃CPU后，进入等待队列，一旦等待的事件发生，则回到原来的就绪队列 * 如果它在一个时间片结束时尚未完成，调度程序便将该进程转入第二队列的末尾，如果它在第二队列中运行一个时间片后仍未完成，再依次将它放入第三队列，,2多级反馈队列调度算法,2多级反馈队列调度算法,（3） *系统从第一级调度，仅当第一队列空闲时，调度程序才调度第二队列中的进程运行；仅当第1(i-1)队列均空时，才会调度第i队列中的进程运行。 * 当有一个优先级更高的进程就绪时，可以抢占CPU，被抢占进程回到原来一级就绪队列末尾。,2多级反馈队列调度算法,3多级反馈队列调度算法的性能,多级反馈队列调度算法具有较好

25、的性能，能很好地满足各种类型用户的需要。 (1) 终端型作业用户。由于终端型作业用户所提交的作业大多属于交互型作业，作业通常较小，系统只要能使这些作业(进程)在第一队列所规定的时间片内完成，便可使终端型作业用户都感到满意。,(2) 短批处理作业用户。对于很短的批处理型作业，开始时像终端型作业一样，如果仅在第一队列中执行一个时间片即可完成，便可获得与终端型作业一样的响应时间。 (3) 长批处理作业用户。对于长作业，它将依次在第1，2，n个队列中运行，然后再按轮转方式运行，用户不必担心其作业长期得不到处理。,3多级反馈队列调度算法的性能,进程调度的时机,当一个进程运行完毕，或由于某种错误而终止运行

26、 当一个进程在运行中处于等待状态（等待I/O） 分时系统中时间片到 当有一个优先级更高的进程就绪（可抢占式） 在进程通信中，执行中的进程执行了某种原语操作（P操作，阻塞原语，唤醒原语）,3.4 实 时 调 度,3.4.1 实现实时调度的基本条件 1提供必要的信息 2系统处理能力强 3采用抢占式调度机制 4具有快速切换机制,1提供必要的信息,(1) 就绪时间。 (2) 开始截止时间和完成截止时间。 (3) 处理时间。 (4) 资源要求。 (5) 优先级。,2系统处理能力强,在实时系统中，若处理机的处理能力不够强，则有可能因处理机忙不过来而使某些实时任务不能得到及时处理。假定系统中有m个周期性的硬

27、实时任务，它们的处理时间可表示为Ci，周期时间表示为Pi，则在单处理机情况下，必须满足下面的限制条件：,2系统处理能力强,对于不能满足实时性要求的解决方法是提高系统的处理能力，其途径有二：其一仍是采用单处理机系统，但须增强其处理能力，以显著地减少对每一个任务的处理时间；其二是采用多处理机系统。假定系统中的处理机数为N，则应将上述的限制条件改为：,3采用抢占式调度机制,在含有硬实时任务的实时系统中，广泛采用抢占机制。这样便可满足该硬实时任务对截止时间的要求。但这种调度机制比较复杂。 对于一些小型实时系统，如果能预知任务的开始截止时间，则对实时任务的调度可采用非抢占调度机制，以简化调度程序和对任务

28、调度时所花费的系统开销。,4具有快速切换机制,为保证要求较高的硬实时任务能及时运行，在实时系统中还应具有快速切换机制。该机制应具有如下两方面的能力： (1) 对外部中断的快速响应能力。 (2) 快速的任务分派能力。,3.4.2 实时调度算法的分类,1非抢占式调度算法 1) 非抢占式轮转调度算法 该算法常用于工业生产的群控系统中，由一台计算机控制若干个相同的(或类似的)对象，为每一个被控对象建立一个实时任务，并将它们排成一个轮转队列。调度程序每次选择队列中的第一个任务投入运行。当该任务完成后，便把它挂在轮转队列的末尾，等待下次调度运行，而调度程序再选择下一个(队首)任务运行。,1非抢占式调度算法

29、,2) 非抢占式优先调度算法 如果在实时系统中存在着要求较为严格(响应时间为数百毫秒)的任务，则可采用非抢占式优先调度算法为这些任务赋予较高的优先级。当这些实时任务到达时，把它们安排在就绪队列的队首，等待当前任务自我终止或运行完成后才能被调度执行。,2抢占式调度算法,在要求较严格的实时系统中，应采用抢占式优先权调度算法。可根据抢占发生时间的不同而进一步分成以下两种调度算法。 1) 基于时钟中断的抢占式优先权调度算法 在某实时任务到达后，如果该任务的优先级高于当前任务的优先级，这时并不立即抢占当前任务的处理机，而是等到时钟中断到来时。,2抢占式调度算法,2) 立即抢占的优先权调度算法 在这种调度

30、策略中，要求操作系统具有快速响应外部事件中断的能力。一旦出现外部中断，只要当前任务未处于临界区，便立即剥夺当前任务的执行，把处理机分配给请求中断的紧迫任务。这种算法能获得非常快的响应。,图 实时进程调度,时钟,时钟（clock），又称为定时器（timer） (1) 时钟负责提供一天的时间 (2) 防止一个进程垄断CPU 时钟既不是块设备，也不是字符设备，但时钟软件通常也采用设备驱动程序的形式,1) 时钟硬件,两种类型： 比较简单的时钟被连到110V或220V的电源线上，每个电压周期产生一个中断，频率是50Hz或60Hz 另一种时钟由三个部件构成：晶体振荡器、计数器和存储寄存器 石英晶体产生的精

31、确的周期信号，典型的范围是5到100MHz 信号送到到计数器，使其递减计数至0。当计数器变为0时，产生一个CPU中断信号,可编程时钟操作方式：在单脉冲方式（one-shot mode）下，当时钟启动时，它把存储寄存器的值拷贝到计数器中，然后，晶体的每一个脉冲使计数器减1。当计数器为0时，产生一个中断，并停止工作，直到软件再一次显式启动它。 在方波方式（square-wave mode）下，当计数器为0并产生中断时，存储寄存器的值自动拷贝到计数器，这个过程不断地重复下去。周期性的中断称为时钟滴答（clock tick ） 可编程时钟的优点是其中断频率可由软件控制。,2) 时钟软件,时钟硬件所做的

32、工作是每隔一定的时间间隔产生一个中断。 涉及时间的其他所有工作都必须由软件-时钟驱动程序完成,3) 时钟软件功能,1维护日期时间 2防止进程超时运行 3对CPU的使用情况记帐 4处理用户进程提出的ALARM系统调用 5为系统本身各部分提供监视定时器 6绘制CPU运行直方图，完成监视和统计信息收集 系统的其他部分也需要定时器称为监视定时器（watchdog timer）。,3.4.3 常用的几种实时调度算法,1最早截止时间优先即EDF算法 该算法是根据任务的开始截止时间来确定任务的优先级。截止时间愈早，其优先级愈高。就绪队列按各任务截止时间的早晚排序。调度程序在选择任务时，总是选择就绪队列中的第

33、一个任务。该算法既可用于抢占式调度，也可用于非抢占式调度方式中。,1最早截止时间优先算法,1) 非抢占式调度方式用于非周期实时任务 有四个非周期任务，它们先后到达。系统首先调度任务1执行，在任务1执行期间，任务2、3又先后到达。由于任务3的开始截止时间早于任务2，故系统在任务1后将调度任务3执行。在此期间又到达作业4，其开始截止时间仍是早于任务2的，故在任务3执行完后，系统又调度任务4执行，最后才调度任务2执行。,1最早截止时间优先算法,图 EDF算法用于非抢占调度方式,2) 抢占式调度方式用于周期实时任务 有两个周期性任务，任务A的周期时间为20 ms，每个周期的处理时间为10 ms；任务B

34、的周期时间为50 ms，每个周期的处理时间为25 ms。图中的第一行示出了两个任务的到达时间、最后期限和执行时间图。,1最早截止时间优先算法,图 最早截止时间优先算法用于抢占调度方式之例,2最低松弛度优先即LLF(Least Laxity First)算法,该算法是根据任务紧急(或松弛)的程度，来确定任务的优先级。 例如，一个任务在200 ms时必须完成，而它本身所需的运行时间就有100 ms，因此，调度程序必须在100 ms之前调度执行，该任务的紧急程度(松弛程度)为100 ms。在实现该算法时要求系统中有一个按松弛度排序的实时任务就绪队列。,2.最低松弛度优先(LLF)算法,假如在一个实时

35、系统中，有两个周期性实时任务A和B，任务A要求每 20 ms执行一次，执行时间为 10 ms；任务B只要求每50 ms执行一次，执行时间为 25 ms。,图 A和B任务每次必须完成的时间,在刚开始时(t1=0)，A1必须在20ms时完成，而它本身运行又需 10 ms，可算出A1的松弛度为10ms；B1必须在50ms时完成， 而它本身运行就需25 ms，可算出B1的松弛度为25 ms，故调度程序应先调度A1执行。在t2=10 ms时，A2的松弛度可按下式算出： A2的松弛度=必须完成时间-其本身的运行时间-当前时间 =40 ms-10 ms-10 ms=20 ms,2.最低松弛度优先(LLF)算

36、法,2.最低松弛度优先(LLF)算法,类似地，可算出B1的松弛度为15ms，调度程序应选择B2运行。t3=30 ms时，A2的松弛度已减为0，B1的松弛度为15 ms，于是调度程序应抢占B1的处理机而调度A2运行.,图 3-8 利用ELLF算法进行调度的情况,3.5 产生死锁的原因和必要条件,死锁问题在1965年由Dijkstra（迪科斯彻 ） 发现，并随着计算机技术的发展，逐渐成为人们关心的问题。那么，什么是死锁？其确切的定义是什么？死锁是怎么产生的？用什么方法来解决死锁？这些正是今天我们要讨论的问题。,3.5 产生死锁的原因和必要条件,早期的操作系统对申请某种资源的进程，若该资源尚未分配时

37、，立即将该资源分配给这个进程。后来发现，对资源不加限制地分配可能导致进程间由于竞争资源而相互制约以至于无法继续运行的局面，人们把这种局面称为死锁 (deadlock)。,例. 日常生活中常有许多有关死锁。,显然各路车队等待的事件都不会发生。 (假设它们都不改变行车方向) 这样若不采用特殊方法，它们将永远停留在这“ 井”字形的路上，而处于死锁状态。,在计算机系统中，进程发生死锁与上述事例实质上是一样的。进程是因相互竞争资源而导致死锁的，与四路车队(可视为进程)竞争路口(可视为资源) 类似。计算机系统中有各种资源，如外设、数据、文件、程序等。,关于死锁的一些结论,参与死锁的进程最少是两个 参与死锁

38、的进程至少有两个已经占有资源 参与死锁的所有进程都在等待资源 参与死锁的进程是当前系统中所有进程的子集 注：如果死锁发生，会浪费大量系统资源，甚至导致系统崩溃。,3.5.1 产生死锁的原因,1.竞争系统资源 2.进程的推进顺序不当,1竞争资源引起进程死锁,1) 可剥夺和非剥夺性资源 可把系统中的资源分成两类 一类是可剥夺性资源，是指某进程在获得这类资源后，该资源可以再被其他进程或系统剥夺。 另一类是不可剥夺性资源，当系统把这类资源分配给某进程后，再不能强行收回。,1竞争资源引起进程死锁,2) 竞争非剥夺性资源 系统中所配置的非剥夺性资源，由于它们的数量不能满足诸进程运行的需要，会使进程在运行过

39、程中，因争夺这些资源而陷入僵局。,1竞争资源引起进程死锁,若系统中只有一台打印机R1和一台磁带机R2，可供进程P1和P2共享。若形成环路，这样会产生死锁。,永久性资源和临时性资源,永久性资源：可以被多个进程多次使用（可再用资源） 可抢占资源 不可抢占资源 临时性资源：只可使用一次的资源；如信号量,中断信号，同步信号等（可消耗性资源） “申请-分配-使用-释放”模式,3) 竞争临时性资源 S1、S2和S3是临时性资源。进程P1产生消息S1，又要求从P3接收消息S3；进程P3产生消息S3，又要求从进程P2接收其所产生的消息S2；进程P2产生消息S2，又需要接收进程P1所产生的消息S1。,1竞争资源

40、引起进程死锁,进程之间通信时的死锁,1竞争资源引起进程死锁,如果消息通信按下述顺序进行： P1： Release(S1)； Request(S3)； P2： Release(S2)； Request(S1)； P3： Release(S3)； Request(S2)； 则不可能发生死锁，但若改成下述的运行顺序： P1： Request(S3)； Release(S1)； P2： Request(S1)； Release(S2)； P3： Request(S2)； Release(S3)； 则可能发生死锁。,2进程推进顺序不当引起死锁,由于进程在运行中具有异步性特征，这就可能使上述P1和P2两个

41、进程按下述两种顺序向前推进。 1) 进程推进顺序合法 在进程P1和P2并发执行时，如果按下述顺序推进： P1：Request(R1)；Request(R2)； P1：Release(R1)； Release(R2)； P2：Request(R2)；Request(R1)； P2：Release(R2)；Release(R1)；,2进程推进顺序不当引起死锁,在进程P1和P2并发执行时，按照左图曲线所示顺序推进时，两进程会顺利完成，我们称这种推进顺序是合法的。,2进程推进顺序不当引起死锁,2) 进程推进顺序非法 若并发进程P1和P2按曲线所示的顺序推进，它们将进入不安全区D内。此时P1保持了资源R

42、1，P2保持了资源R2，系统处于不安全状态。因为这时两进程再向前推进，便可能发生死锁。,在一个进程集合中，若每个进程都在等待某些事件（指：释放资源）的发生，而这些事件又必须由这个进程集合中的某些进程来产生，就称该进程集合处于死锁状态。 即：多个进程循环等待他方占有的资源而无限期地僵持下去的局面,3.5.2 产生死锁的必要条件,虽然进程在运行过程中可能发生死锁，但死锁的发生也必须具备一定的条件。死锁的发生必须具备下列四个必要条件。 (1) 互斥条件 (2) 请求和保持条件 (3) 不剥夺条件 (4) 环路等待条件,3.5.3 处理死锁的基本方法,预防死锁 该方法是通过设置某些限制条件，去破坏产生

43、死锁的四个必要条件中的一个或几个条件，来预防发生死锁。 避免死锁 而是在资源的动态分配过程中，用某种方法去防止系统进入不安全状态，从而避免发生死锁。,3.5.3 处理死锁的基本方法,检测死锁 通过系统所设置的检测机构，及时地检测出死锁的发生，并精确地确定与死锁有关的进程和资源。 解除死锁 当检测到系统中已发生死锁时，须将进程从死锁状态中解脱出来。,3.6 预防死锁的方法,3.6.1预防死锁 1.摒弃“请求和保持”条件 系统规定所有进程在开始运行之前，都必须一次性地申请其在整个运行过程所需的全部资源。此时，若系统有足够的资源分配给某进程，便可把其需要的所有资源分配给该进程，这样，该进程在整个运行

44、期间便不会再提出资源要求，从而摒弃了请求和保持条件,2摒弃“不剥夺”条件,进程是逐个地提出对资源的要求的。当一个已经保持了某些资源的进程，再提出新的资源请求而不能立即得到满足时，必须释放它已经保持了的所有资源，待以后需要时再重新申请。这意味着某一进程已经占有的资源，在运行过程中会被暂时地释放掉，从而摒弃了“不剥夺”条件。,3摒弃“环路等待”条件,这种方法中规定，系统将所有资源按类型进行线性排队，并赋予不同的序号。所有进程对资源的请求必须严格按照资源序号递增的次序提出，这样，在所形成的资源分配图中，不可能再出现环路，因而摒弃了“环路等待”条件。,3.6.2 系统安全状态,1安全状态 在避免死锁的

45、方法中，允许进程动态地申请资源，但系统在进行资源分配之前，应先计算此次资源分配的安全性。若此次分配不会导致系统进入不安全状态，则将资源分配给进程；否则，令进程等待。,3. 安全状态,安全状态指系统能按某种进程顺序来为每个进程分配其所需资源，直至最大需求，使每个进程都可顺序完成。若系统不存在这样一个序列，则称系统处于不安全状态。,1. 安全状态,一个进程序列P1，Pn是安全的，如果对于每一个进程Pi(1in），它以后尚需要的资源量不超过系统当前剩余资源量与所有进程Pj (j i )当前占有资源量之和，系统处于安全状态。这个序列称为安全序列 (安全状态一定是没有死锁发生的),假定系统中有三个进程P

46、1、 P2和P3，共有12台磁带机。进程P1总共要求10台磁带机，P2和P3分别要求4台和9台。假设在T0时刻，进程P1、P2和P3已分别获得5台、2台和2台磁带机，尚有3台空闲未分配，如下表所示：,2. 安全状态之例,如果不按照安全序分配资源，则系统可能会由安全状态进入不安全状态。例如，在T0时刻以后，P3又请求1台磁带机，若此时系统把剩余3台中的1台分配给P3，则系统便进入不安全状态。 因为，此时无法再找到一个安全序列。,3.由安全状态向不安全状态的转换,安全状态与不安全状态,不安全状态:不存在一个安全序列，不安全状态不一定导致死锁,预防死锁的几种策略，会严重地损害了系统性能。因此要施加较

47、弱的限制，从而获得较满意得系统性能来避免死锁。 死锁避免：在系统运行过程中，对进程发出的每一个系统能够满足的资源申请进行动态检查，并根据检查结果决定是否分配资源，若分配后系统可能发生死锁，则不予分配，否则予以分配。,3.6.3 利用银行家算法避免死锁,由于在避免死锁的策略中，允许进程动态地申请资源。因而，系统在进行资源分配之前预先计算资源分配的安全性。若此次分配不会导致系统进入不安全状态，则将资源分配给进程；否则，进程等待。其中最具有代表性的避免死锁算法是银行家算法。,1.银行家算法中的数据结构,(1) 可利用资源向量Available。这是一个含有m个元素的数组，其中的每一个元素代表一类可利

48、用的资源数目，其初始值是系统中所配置的该类全部可用资源的数目，其数值随该类资源的分配和回收而动态地改变。如果Availablej=K，则表示系统中现有Rj类资源K个。,1.银行家算法中的数据结构,(2) 最大需求矩阵Max。这是一个nm的矩阵，它定义了系统中n个进程中的每一个进程对m类资源的最大需求。如果Maxi,j=K，则表示进程i需要Rj类资源的最大数目为K。,1.银行家算法中的数据结构,(3) 分配矩阵Allocation。这也是一个nm的矩阵，它定义了系统中每一类资源当前已分配给每一进程的资源数。如果Allocationi,j=K，则表示进程i当前已分得Rj类资源的数目为K。,1.银行

49、家算法中的数据结构,(4) 需求矩阵Need。这也是一个nm的矩阵，用以表示每一个进程尚需的各类资源数。如果Needi,j=K，则表示进程i还需要Rj类资源K个，方能完成其任务。 上述三个矩阵间存在下述关系： Needi, j=Maxi, j-Allocationi, j,2银行家算法,设Requesti是进程Pi的请求向量，如果Requestij =K，表示进程Pi需要K个R j类型的资源。当P i发出资源请求后，系统按下述步骤进行检查： (1) 如果RequestijNeedi,j，便转向步骤(2)；否则认为出错，因为它所需要的资源数已超过它所宣布的最大值。 (2) 如果RequestijAvailablej，便转向步(3)；否则，表示尚无足够资源，Pi须等待。,(3) 系统试探着把资源分配给进程Pi，并修改下面数据结构中的数值： Availablej=Availablej-Requesti