第3章 处理机调度与死锁(新)

第3章处理机调度与死锁本章学习目标掌握处理机的三级调度掌握作业调度及进程调度的概念理解调度算法的评价准则掌握并灵活运用常用的几种作业调度、进程调度算法掌握死锁的概念、产生的原因及死锁的必要条件掌握死锁的预防方法及利用银行家算法避免死锁的方法掌握死锁的检测与恢复的方法，并能灵活运用第3章处理机调度与死锁1教学内容3.1处理机调度的层次3.2

调度队列模型和调度准则3.3

调度算法3.4实时调度3.5产生死锁的原因和必要条件3.6预防死锁的方法3.7死锁的检测与解除3.1处理机调度的层次

一个作业从用户提交后驻留在外存设备开始，直到作业运行结束，可能要经历多级调度才能实现。

高级调度（作业调度）低级调度（进程调度）中级调度（交换）3.1.1高级调度

1.基本概念作业：用户向计算机提交任务的任务实体作业步之间的关系作业步：作业的执行步骤（一个作业步在执行过程中可以由多个进程来实现）

作业和进程的关系？

作业是描述用户向系统提交工作任务的实体单位进程是系统完成工作任务时程序执行的实体单位作业作业步作业步作业步………进程进程进程………3.1.1高级调度

2.作业控制块

是作业在系统中存在的标志，包含了对作业进行管理的必要信息。作业控制块的内容3.1.1高级调度

3.作业调度从外存的后备队列中选择一个或者多个作业调入内存，并为它们创建进程、分配必要的资源。然后再将新创建的进程插入到就绪队列中，准备执行。需要解决的问题：一是每次接纳多个作业：（取决于多道程序的度）二是接纳哪些作业：（取决于调度算法）记录进入系统的各作业的情况；选择合适的作业调度算法；为选中运行的作业分配资源；作业运行结束后回收资源。3.1.2低级调度

一个系统中最基本的，也是必需需求的一种调度，是CPU资源在可运行实体间的分配。

1.任务

其主要任务是按照某种策略和算法，从就绪进程队列中选择一个进程将它移出就绪队列并设置为运行态，同时启动CPU立即执行。2.进程调度方式

进程调度可分为下列两种方式：（1）非抢占方式：非抢占方式不允许进程抢占已经分配出去的处理机。（2）抢占方式：抢占调度方式允许调度程序根据某种原则，暂停某个正在执行的进程，将处理机收回，重新分配给另一个进程。第3章处理机调度与死锁9该方式下，可能引起的进程调度原因有：完成任务；等待资源、发现标志；…………3.进程调度功能保存现场：记录放弃CPU的进程A的现场信息（如PC，通用寄存器的内容等）选择进程：当进程出让CPU或调度程序剥夺执行状态进程占用的CPU时，选择适当的进程B分派CPU完成上下文切换：

用户态执行进程A代码，之后进入OS内核（通过时钟中断或系统调用）保存进程A的上下文，载入进程B的上下文（CPU寄存器和一些表格的当前指针）用户态执行进程B代码第3章处理机调度与死锁103.1.3中级调度其主要任务是按照给定的原则和策略，把那些暂时不能运行的进程从主存移到外存上，释放其所占有的宝贵资源，让其他进程运行。当移到外存上的进程具备运行条件时，再由中级调度把它们重新调入主存，等待运行。

三种调度类型之间的关系：当创建新进程时，执行高级调度，将新进程加入到当前活动的一组进程中。中级调度是交换功能的一部分，它将一个进程至少部分换入内存中，使之以后能够执行。低级调度才真正决定哪个就绪进程是下一个得以执行的进程。【例1】进程调度是指根据一定的调度算法，从_____队列中挑选出一个的进程，分配给它CPU。

A．阻塞

B．就绪

C．运行

D．等待【解答】B【例2】作业调度程序从处于________状态的队列中先取适当的作业调入主存运行。A．运行 B．提交C．完成 D．后备【解答】D例题解析【例3】用户要求计算机处理的一个任务称为一个

。【解答】作业【例4】作业调度从

中选择一道作业，为它分配资源，并为它创建

。【解答】后备队列，进程3.2调度队列模型和调度准则3.2.2调度算法的评价及准则1．面向用户的准则2．面向系统的准则181．面向用户的准则（1）周转时间短（评价批处理系统性能的准则）周转时间：是指作业被提交给系统开始，到作业终止为止的这段时间间隔，也称为作业周转时间。它包括四部分时间：a．作业在外存后备队列上等待调度的时间。b．进程在就绪队列上等待进程调度的时间。c．进程占用CPU执行的时间。d．进程等待I/O操作完成的时间。第3章处理机调度与死锁19作业i的周转时间Ti可定义为：

Ti=Tei—Tsi其中，Tei为作业i的完成时间，Tsi为作业i的提交时间。平均周转时间为：

T=]作业的周转时间T与系统为它提供服务的时间（即作业要求运行时间）Ts之比，称为带权周转时间，即：带权周转时间W＝Ｔ／Ts

第3章处理机调度与死锁20（２）响应时间快（评价分时系统性能的准则）

所谓响应时间，是指从用户提交一个作业请求开始，直至系统首次产生响应为止的时间。它包括三部分时间：从键盘输入的请求信息传送到处理机的时间。处理机执行响应处理的时间。将所形成的响应信息在终端显示器上显示出来的时间。（３）截止时间的保证（评价实时系统性能的准则）

所谓截止时间，是指某任务必须开始执行的最晚时间，或必须完成的最晚时间。

（４）优先权准则（在批处理，分时，实时系统中都使用）

调度程序根据任务的优先权确定先选中哪个作业。第3章处理机调度与死锁212．面向系统的准则

（１）系统的吞吐量。（２）处理机的利用率。（３）各类资源的平衡利用。第3章处理机调度与死锁22要设计一个理想的调度算法是一件十分困难的事在实际系统中，调度算法往往折衷考虑设计调度算法时应考虑的因素：调度算法应与系统设计目标保持一致注意系统资源均衡使用保证提交的作业在截止时间内完成设法缩短作业平均周转时间3.3调度算法

3.2.11.先来先服务（FCFS）调度算法

先来先服务（FCFS）调度算法既可用于作业调度，也适用于进程调度。思想：该算法是按照作业或进程到达的先后次序来进行调度。

第3章处理机调度与死锁24FCFS调度算法评价：有利于CPU繁忙型的进程，而不利于I/O繁忙型的进程2.短作业（进程）优先调度算法

是对短作业调度算法（SJF）或短进程调度算法的（SPF），既可用于作业调度，也适用于进程调度。

思想：以进程（作业）的本次CPU时间长短作为调度的依据来选择进程（作业）投入运行。第3章处理机调度与死锁26SJ(P)F调度算法也存在一些不容忽视的缺点：（1）该算法对长作业不利。（2）该算法未考虑作业的紧迫度，因而不能保证紧迫作业的及时处理。（3）不一定保证做到真正意义上的短作业优先调度。

第3章处理机调度与死锁283.3.2高优先级优先调度算法优先级调度算法也叫做优先权调度算法，可做为作业调度或进程调度策略。这种算法可用于批处理系统，也可用于实时系统中。第3章处理机调度与死锁291．优先级调度算法的类型

（1）非抢占式优先级调度算法（2）抢占式优先级调度算法2.优先级的类型

在优先级调度算法中，优先级用来表示作业或进程所享有的调度优先权。该算法的关键是确定进程或作业的优先级。确定优先级的方法有两类：1）静态优先级

静态优先级是在创建进程时确定的，且在进程的整个运行期间保持不变。（2）动态优先级

动态优先级是指，在创建进程时所赋予的优先级，是随进程的推进或随其等待时间的增加而改变的，以便获得更好的调度性能。第3章处理机调度与死锁30确定进程优先权的依据：进程类型；进程对资源的需求；用户要求3．高响应比优先调度算法（HRN）

思想：当需要从就绪队列中选择进程投入运行时，先计算各进程的响应比，选择响应比最高的进程运行。

响应比R可定义如下：

R＝（已等待时间＋要求服务时间）／要求服务时间即：R＝1＋已等待时间／要求服务时间对于同样长度的作业，其R值可以从其等待调度的时间长短来区分；同样等待时间的作业，要求执行时间少的作业R值高。因此，它既照顾了短作业，又考虑了作业的等待时间。当然，在利用该算法时，每次在进行调度之前，都要先计算相应比，因此增加了系统的开销第3章处理机调度与死锁31例题：4个进程的提交、运行时间如下表所示。若采用最高响应比优先调度算法，试求出进程的执行顺序，进程的开始时间、完成时间、周转时间及进程的平均周转时间。进程提交时间运行时间P18.02.0P28.40.3P38.60.1P49.00.2

练习题1：假定某非多道程序设计系统中，有5道作业，它们的提交时间和运行时间如下图。若采用以下调度算法，试求每种调度算法中作业调度的次序及平均周转时间。（1）先来先服务 （2）短作业优先第3章处理机调度与死锁33作业号提交时刻服务时间A8:0025分钟B8:2010分钟C8:20 20分钟D8:3020分钟E8:3515分钟

练习题2：设有四道作业，它们的提交时间及运行时间如下表，若采用（1）短作业优先调度策略（2）最高相应比优先策略。试给出作业的平均周转时间。第3章处理机调度与死锁34作业提交时间运行时间J105J213J332J4443.3.3基于时间片的轮转调度算法第3章处理机调度与死锁351．时间片轮转法（RR）（1）思想

主要用于分时系统中的进程调度。系统把所有就绪进程按先入先出的原则排成一个队列。新来的进程加到就绪队列末尾。每当执行进程调度时，就绪队列的队首进程总是先被调度程序选中，让它在CPU上运行一个时间片的时间。

思想：该算法为每个进程分配一个时间片。如果在时间片一到，即进程还没有运行完，也要让出CPU。如果进程在时间片还没结束之前阻塞或结束，则CPU当即进行切换。第3章处理机调度与死锁37（2）执行过程将系统中所有的就绪进程按照FCFS原则，排成一个队列。每次调度时将CPU分派给队首进程，让其执行一个时间片。时间片的长度从几个ms到几百ms。在一个时间片结束时，发生时钟中断。调度程序据此暂停当前进程的执行，将其送到就绪队列的末尾，并通过上下文切换执行当前的队首进程。进程可以未使用完一个时间片，就出让CPU（如阻塞）。第3章处理机调度与死锁38（3）时间片长度变化的影响

过长－>响应时间长。退化为FCFS算法，进程在一个时间片内都执行完，过短－>响应时间长。用户的一次请求需要多个时间片才能处理完，上下文切换次数增加。因为处理时钟中断、执行调度和分派函数都需要处理器开销策略：时间段最好略大于一次典型的交互所需要的时间，否则使响应时间延长（使用两个时间片）。

考虑下述四个进程A、B、C和D的执行情况。设它们依次进入就绪队列，但前后时间忽略不计。四个进程分别需要运行12，5，3和6个时间单位。如下表所示。计算当时间片分别为q=1时各进程的开始运行时间、完成时间、周转时间及带权周转时间进程名到达时间运行时间A012B05C03D06解：通过分析及计算，我们可以得到下表：平均周转时间T=18.5

平均带权周转时间平均周转时间T=19.75

平均带权周转时间进程名到达时间到达时间运行时间开始时间完成时间周转时间带权周转时间时间片q=1A012026262.17B05117173.4C03211113.67D06320203.33=3.14第3章处理机调度与死锁403.3.3基于时间片的轮转调度算法第3章处理机调度与死锁412．多级反馈队列调度算法多个就绪队列，进程所属队列可变，即进程可以在不同的就绪队列之间移动设置多个就绪队列，分别赋予不同的优先级，如逐级降低，队列1的优先级最高。每个队列执行时间片的长度也不同，规定优先级越低则时间片越长，如：逐级加倍

队列优先级逐级降低，而时间片长度逐级递增就绪队列1就绪队列2就绪队列3就绪队列n运行完成运行完成运行完成运行完成时间片S2时间片S1时间片S3时间片Sn（时间片S1<S2<S3<…<Sn）多级反馈队列调度算法示意图思想：该算法设立了优先级类。其原则是优先级越高的进程，时间片越少，优先级越低的进程，时间片越多。同时当一个进程用完其时间片的时候，被移到下一级类。这种算法较好地实现了进程调度的公平性与系统资源利用率之间的平衡。第3章处理机调度与死锁43特点：短进程和新进程优先于长进程和老进程

运行时间短的进程在经过前面几个队列之后便已经执行完，而这些队列中的进程被优先调度。响应速度快

交互式进程反应及时设备资源利用率高

因为与设备打交道的进程可能经常会由于下面原因而进入等待状态：所申请的资源被占用，启动了I/O传输。当等待事件发生时，它将进入最高优先级就绪队列，尽快获得处理机并使用资源。系统开销小

因为运行时间长的进程最后进入低优先级的队列，这些队列的时间片较长，因而进程的调度频率较低。【例1】下列作业调度算法中，具有最短的作业平均周转时间的是________。

A．先来先服务法

B．短作业优先法

C．优先数法

D．时间片轮转法【解答】B【例2】在分时操作系统中，进程调度经常采用_______算法。A．先来先服务B．最高优先权C．时间片轮转D．随机【解答】C【例3】进程调度在采用优先级调度算法时，一个高优先级的进程占用处理机时可以采用

或

两种处理方式。【解答】非抢占式，可抢占式例题解析例1：假设一个系统中有5个进程，它们的到达时间、运行时间及优先级（5最高）如表所示，忽略I/O及其他开销时间。若分别按(1)FCFS；(2)非抢占式短进程优先；(3)非抢占式高优先权优先算法进行调度，请给出各进程的开始时间、完成时间及周转时间。第3章处理机调度与死锁45进程到达时间运行时间优先级A031B262C443D654E825例2：系统中有3个进程P1，P2，P3，优先级顺序P3，P2，P1，I1,I2,I3和CPU可以并行运行，各自运行的要求是：

P1:CPU260ms,I1300ms,CPU150msP2:I2180ms,CPU130ms,I2110ms,CPU120msP3:I3190ms,CPU70ms,I3270ms,CPU80ms采用按时间片运行的优先级法，q=100ms，试求：（1）3个进程从投入到完成分别需要的时间（2）从投入到完成的CPU利用率（3）I/O设备利用率。第3章处理机调度与死锁46第3章处理机调度与死锁47进程到达和需服务时间进程到达时间服务时间A03B26C44D65E82多级反馈队列调度算法（FB算法）

原理：q=2i-1，其中的i表示是在哪个级的的队列上，所以，优先级愈高的队列时间片愈小。新就绪进程总是先进入第一级（即最高优先级）队列的末尾；系统总是调度第一级队列上的进程执行；仅当第一级队列为空时，才调度第二级队列上的进程执行。类推之，仅当1～(i-1)为空时，才调度第i级队列上的进程执行。3.4实时调度

实时调度是指，计算机对外部事件的处理速度，要能跟上外部事件的快速变化，以便做出及时的响应。在进程调度时，要以适当的方式优先调度实时进程的运行。

3.4.1实现实时调度的基本条件

1.提供必要的信息

就绪时间。(2)开始截止时间和完成截止时间。(3)处理时间。(4)资源要求。(5)优先级。

2.系统处理能力强

在实时系统中，通常都有着多个实时任务。若处理机的处理能力不够强，则有可能因处理机忙不过来而使某些实时任务不能得到及时处理，从而导致发生难以预料的后果。3.采用抢占式调度机制

当一个优先权更高的任务到达时，允许将当前任务暂时挂起，而令高优先权任务立即投入运行，这样便可满足该硬实时任务对截止时间的要求。但这种调度机制比较复杂。

4.

具有快速切换机制

该机制应具有如下两方面的能力：

(1)对外部中断的快速响应能力。

(2)快速的任务分派能力。3.4.2

实时调度算法的分类

1.非抢占式调度算法

非抢占式轮转调度算法。(2)非抢占式优先调度算法。

2.

抢占式调度算法

基于时钟中断的抢占式优先权调度算法(2)立即抢占(ImmediatePreemption)的优先权调度算法。实时进程调度

3.4.3常用的几种实时调度算法

1.最早截止时间优先即EDF(EarliestDeadlineFirst)算法

EDF算法用于非抢占调度方式

2.最低松弛度优先即LLF(LeastLaxityFirst)算法

该算法是根据任务紧急(或松弛)的程度，来确定任务的优先级。任务的紧急程度愈高，为该任务所赋予的优先级就愈高，以使之优先执行。图A和B任务每次必须完成的时间

图3-9利用ELLF算法进行调度的情况3.5产生死锁的原因和必要条件

一个死锁的例子：如下图所示，系统中的两个进程都因等待对方的临界资源而不能继续运行。这种现象称为死锁。该例中的临界资源R1和R2可能是打印机、磁带机、缓冲区等。第3章处理机调度与死锁58●R1●R2进程P1、P2陷入死锁状态P1P2死锁的概念

所谓死锁，是指两个或两个以上进程由于竞争资源而处于的僵持状态，在这种僵持状态下若没有外力作用，所有进程都无法正常向前推进。第3章处理机调度与死锁593.5.1产生死锁的原因及必要条件1．死锁产生的原因系统产生死锁的根本原因可归结为两点：（1）各进程竞争有限的资源（2）进程间推进顺序非法

第3章处理机调度与死锁603.5.2．死锁产生的必要条件系统中如果死锁发生，则一定同时存在下列四个条件，即死锁的必要条件：（1）互斥条件（2）占有且申请条件

（3）不可抢占条件（4）环路条件第3章处理机调度与死锁6162（1）互斥条件

对于一个排它性资源，某一时刻最多只能由一个进程占有，不能同时分配给两个以上的进程。必须要在占有该资源的进程放弃该资源后，其它进程才能占有该资源。如打印机是临界资源，各进程必须互斥地使用。（2）占有且申请条件

进程至少已经占有一个资源，但又申请新的资源；由于该资源已被另外进程占有，此时该进程阻塞；但是，它在等待新资源时，仍不释放已占有的资源。（3）不可抢占条件

也称为不剥夺条件。进程所获得的资源在未使用完毕之前，资源申请者不能强行地从资源占有者进程夺取该资源，而只能等待占有该资源的进程释放该资源后，其它进程才可以使用。第3章处理机调度与死锁63（4）环路条件

如果死锁产生，则一定存在一个进程等待序列{P1，P2，…Pn}，其中P1等待进程P2所占有的资源，P2等待进程P3所需的资源，…，Pn-1等待进程Pn所占有的资源，Pn等待进程P1所占有的资源，形成一个循环等待的环路。

上面四个条件是在死锁发生时同时出现的，我们可以利用它的逆否命题，即：四个条件中只要有一个不满足，则死锁不会发生。这正是我们预防死锁所需考虑的方法。第3章处理机调度与死锁643.5.3解决死锁问题的基本方法为保证系统的正常运行，应事先采取措施，预防或避免死锁的发生。在系统已出现死锁后，要及时检测到死锁并解除死锁。目前用于处理死锁问题的方法有以下几种：1．死锁的预防2．死锁的避免3．死锁的检测4．死锁的解除1．死锁的预防采取某种策略，限制并发进程对资源的请求，从而保证死锁的必要条件在系统执行的任何时间都不能得到满足。2．死锁的避免是指系统在分配资源时，根据资源的使用情况提前做出预测，给定一个合适的安全的进程推进顺序，从而避免死锁的发生。实现起来有一定的难度，但在一些较完善的系统中，常用这种方法。第3章处理机调度与死锁663．死锁的检测允许系统发生死锁。系统设有专门的机构，当死锁发生时，该机构能够检测到死锁的发生，并能确定参与死锁的进程及相关资源。第3章处理机调度与死锁674．死锁的解除

这是与死锁检测相配套的措施，用于将进程从死锁状态中解脱出来。一般地，由于操作系统的并发与共享以及随机性等特点，通过预防和避免死锁的手段达到排除死锁的目的，这是一个十分困难的事，需要相当大的系统开销，对于资源的利用也不够充分。死锁的检测与解除则相反，不必花费多少执行时间就能发现死锁和从死锁中恢复出来。因此，在实际操作系统中，很多都采用了后两种方法。第3章处理机调度与死锁683.6预防死锁的方法在系统中采用预防和避免死锁的方法，都是为了防止死锁的发生。它们在实现上也分别采用了不同的原理：死锁的预防是根据死锁的四个必要条件，即只要有一个条件不满足，则死锁不发生；死锁的避免，是给系统中并发执行的进程，找到一个安全的推进顺序。第3章处理机调度与死锁69死锁的四个必要条件中，我们从打破四个必要条件的任意一个，使它们之中的一条不成立，来达到预防死锁的目的。具体有三种方法：

１．摒弃请求和保持条件２．摒弃不剥夺条件３．摒弃环路条件第3章处理机调度与死锁703.6.1预防死锁死锁的避免

死锁的预防是排除死锁的静态策略。死锁的避免，是一种排除死锁的动态策略，它不限制进程有关申请资源的命令，而是对进程所发出的每一个申请资源的活动加以动态地检查，并根据检查结果决定是否进行资源分配。即，在资源分配过程中预测是否会出现死锁，如不会死锁，则分配资源；若有发生死锁的可能，则加以避免。第3章处理机调度与死锁713.6.2系统的安全状态

避免死锁的方法中，允许进程动态地申请资源，但系统在进行资源分配之前，应先计算此次资源分配的安全性。若此次分配不会导致系统进入不安全状态，则将资源分配给进程；否则，让进程等待。第3章处理机调度与死锁723.6.2系统的安全状态安全状态，是指系统中的所有进程能够按照某种次序得到资源，并且依次地运行完毕，这种进程序列{P1，P2，…，Pn}就是安全序列。如果存在这样一个安全序列，则称此时系统处于安全状态。否则，如果系统不存在这样一个序列，则称系统是不安全的。第3章处理机调度与死锁73安全状态例

假定系统中有三个进程P1、P2、P3，共有12台磁带机。进程P1总共需要10台磁带机，P2和P3分别需要4台和9台。假设在T0时刻，磁带机分配如下：进程最大需求已分配可用P11053P242P392T0时刻系统是安全的么？例：有三个进程C1，C2，C3，系统的资源总额为10个单位，其中C1进程要9个资源，C2进程要3个资源，C3进程要8个资源，总计20个资源单位。这时，进程占用及还需资源的状态如下图所示，系统该如何分配资源？客户已分配资源还需申请资源C127C221C344第3章处理机调度与死锁75思考：若在T0时刻以后，C3又申请到2个资源单位，会怎样？由安全状态向不安全状态的转化如果不按照安全序列的顺序分配资源，则系统可能由安全状态进入不安全状态。例如：若在T0时刻以后，C3又申请到2个资源单位，则系统进入不安全状态。因为，此时无法再找到一个安全序列，结果造成系统产生死锁。由此可见，当C3申请资源时，尽管当时系统中还有可用资源，但却不能分配给它，必须让它等待。第3章处理机调度与死锁76

并非所有的不安全状态都是会进入死锁状态。但当系统进入不安全状态后，便可能进入死锁状态。反之，只要系统处于安全状态，系统便可以避免进入死锁状态。第3章处理机调度与死锁77课堂练习

1、系统中有3个进程，每个进程需2台打印机，如果系统配有4台打印机，则系统______出现死锁的情况。

2、某系统中有4个并发进程，都需要同类资源3个，试问该系统不会发生死锁的最少资源数是()。

3、判断题：当由于为进程分配资源使系统处于不安全状态时，系统一定会导致死锁。4、某系统有同类资源m个，n个并发进程可共享该类临界资源。求：每个进程最多可申请多少个该类临界资源，保证系统一定不会发生死锁。第3章处理机调度与死锁79课堂练习

5、3个进程共享4个同类资源，这些资源的分配与释放只能一次一个。已知每一个进程最多需要两个该类资源，则该系统（）。

A.有某进程可能永远得不到该类资源

B.必然有死锁

C.进程请求该类资源立刻能得到

D.必然无死锁3.6.3银行家算法银行家对当前顾客的贷款操作进行判断，以确定其安全性。看能否支持顾客贷款，即该客户能否运行完成。安全时，贷款；否则，暂不贷款。第3章处理机调度与死锁80基本思想：把操作系统看做是银行家，操作系统管理的资源相当于银行家管理的资金，进程向操作系统请求分配资源相当于用户向银行家贷款。操作系统按照银行家制定的规则为进程分配资源。第3章处理机调度与死锁81利用银行家算法避免死锁银行家算法中的数据结构1．可利用资源向量Available。也称为空闲向量。这是一个含有m个元素的数组。其中的每一个元素，代表一类可利用的资源数目，其初始值是系统中所配置的该类全部可用资源的数目。其数值随该类资源的分配和回收而动态地改变。如果Available[j]=K，则表示系统中现有Rj类资源K个。2．最大需求矩阵Max。这是一个n×m的矩阵，它定义了系统中n个进程中的每一个进程对m类资源的最大需求。如果Max[i,j]=K，则表示第i个进程需要Rj类资源的最大数目为K。

第3章处理机调度与死锁823．分配矩阵Allocation。也叫做占有矩阵。这也是一个n×m的矩阵，它定义了系统中每一进程已占有的每一类资源数。如果Allocation[i,j]=K，则表示第i个进程当前已分得Rj类资源的数目为K。

4．需求矩阵Need也叫做申请矩阵。这也是一个n×m的矩阵，用以表示每一个进程尚需的各类资源数。如果Need[i,j]=K，则表示第i个进程还需要Rj类资源K个，才能完成其任务。显然，以上三个矩阵之间存在如下关系：Need[i,j]=Max[i,j]-Allocation[i,j]第3章处理机调度与死锁83222202103420need=max-Allocation=322613314422100411211002—=例:一般情况下,各数据结构举例:Allocation=100411211002max=322613314422available=(2，1，2）银行家算法的实现1．进程申请资源的情况设Requesti是进程Pi的请求向量，如果Requesti[j]=K，表示进程Pi需要Rj类型的资源的个数为K。这里要提及的是，Requesti与Needi的关系可能为以下三种情况：（1）Requesti>Need[i]。这种情况表示该进程的资源需求已超过它所宣布的最大值，因此认为出错。（2）Requesti=Need[i]。这种情况下，表示该进程现在对它所还需的全部资源一次申请完成。（3）Requesti<Need[i]。这种情况下，表示该进程现在对它所需资源再进行部分的申请，剩余的资源以后可再次申请。第3章处理机调度与死锁852．银行家算法的描述当进程Pi发出资源请求后，系统按下述步骤进行检查：（1）如果Requesti≤Need[i]，便转向步骤2；否则显示出错，因为它所需要的资源数已超过它所事先要求的最大值。（2）如果Requesti≤Available，便转向步骤(3)；否则，表示尚无足够资源，Pi须等待。（3）假设系统将资源分配给Pi，则需修改如下数据结构的值：Available:=Available-Requesti;Allocation[i]:=Allocation[i]+Requesti;Need[i]:=Need[i]-Requesti;（4）系统执行安全性算法，检查若此次资源分配后，系统是否处于安全状态。如果是安全的，则将资源真正地分配给进程Pi，否则，将本进程的试探分配作废，恢复原来的资源分配状态，进程Pi等待。第3章处理机调度与死锁863．安全性算法设置两个向量：设工作向量Work。初始置Work:=Available。完成向量Finish，它表示系统能否运行完成。若Finish[i]:=true，则表示第i个进程能够获得足够的资源，运行完成；若Finish[i]:=false则表示该进程不能获得所需全部资源，不能运行完成。设初值Finish[i]:=false，i=0,1,2,…,n-1。当有足够资源分配给第i个进程时，再令Finish[i]:=true。第3章处理机调度与死锁87安全算法的步骤：（1）设置两个工作向量。设置工作向量Work、完成向量Finish，并赋初值。（2）进行安全性检查。从进程集合中查找一个能满足下述条件的进程i：Finish[i]=false并且Needi≤Work；若找到这样的进程，执行步骤（3）；若找不到这样的进程，则转步骤（4）。（3）Work:=Work+Allocation[i];Finish[i]:=true;返回步骤（2）。因为进程Pi若能执行完成，则能够释放它所占的资源。（4）若所有进程的Finish[i]=true都满足，则表示系统处于安全状态，正式将资源分配给进程Pi；否则，系统处于不安全状态，系统不能进行这次试探性分配，恢复原来的资源分配状态，让进程Pi等待。如果已判定系统处于安全状态，则通过运算过程同时可以找到一个安全序列。

第3章处理机调度与死锁88设系统中有3中类型的资源（A,B,C）和5个进程P0、P1、P2、P3、P4，A类资源的数目为10，B类资源的数目为5，C类资源的数目为7。在T0时刻系统状态如下表所示。系统采用银行家算法实施死锁避免策略。

MaxABC

AllocationABC

NeedABC

AvailableABCP0753010743332P13

2

2200122P2902302600P322221101

1P443

30024

3

1（1）T0时刻是否安全？（2）P1请求资源，发出请求向量Request1(1,0,2，能否分配给它？（3）之后，若P4又发出资源请求向量Request4（3，3，0），能否分配给它？（4）P0发出请求向量Request0(0,2,0），能否分配给它？第3章处理机调度与死锁90

P1申请向量进行银行家算法检查后，此时还需要对其进行安全性检查：

MaxABC

AllocationABC

NeedABC

AvailableABCP0753010743230P13

2

2302020P2902302600P322221101

1P443

30024

3

1

P0申请向量进行银行家算法检查后，此时还需要对其进行安全性检查：

MaxABC

AllocationABC

NeedABC

AvailableABCP0753030723210P13

2

2302020P2902302600P322221101

1P443

30024

3

1设系统中有3中类型的资源（A,B,C）和5个进程P1、P2、P3、P4、P5，A类资源的数目为17，B类资源的数目为5，C类资源的数目为20。在T0时刻系统状态如下表所示。系统采用银行家算法实施死锁避免策略。

MaxABCAllocationABCAvailableABCP1559212233P2536402P34011405P4425204P5424314（1）T0时刻是否为安全状态？若是，给出安全序列。（2）若在T0时刻进程P2请求资源（0，3，4），是否能实施资源分配？为什么？（3）在（2）的基础上，若进程P4请求资源（2，0，1），是否能实施资源分配？为什么？银行家算法的应用例．某系统有A、B、C类型的3种资源，在T0时刻进程P1、P2、P3、P4对资源的占用和需求情况见下表。此刻系统可用资源向量为（2，1，2）。问：

资源请求进程最大需求量max已分配资源AllocationABCABCP1P2P2P4322613314422100411211002第3章处理机调度与死锁95（1）将系统中各种资源总数和进程对资源的需求数目用向量或矩阵表示出来。（2）判定此刻系统的安全性。如果是安全的，写出安全序列，如果是不安全的，写出参与死锁的进程。（3）如果此时P1和P2均再发出资源请求向量Request（1，0，1），为了保持系统安全性，应该如何分配资源给这两个进程？说明你所采用策略的原因。（4）如果（3）中的请求都立刻满足后，系统此刻是否处于死锁状态？最终能否进入死锁状态？若能，说明参与死锁的进程，若不能，说明原因。第3章处理机调度与死锁96课堂练习1：若系统运行中出现如下表所示的资源分配情况，该系统是否安全？若是，给出安全序列；如果进程P2此时提出资源申请（1，2，2，2），系统能否将资源分配给它？为什么？

Allocation已分配资源数Need还需资源数Available可分配资源P0003200121622P110001750P213542356P303320652P400140656课堂练习2：假定系统中有4个进程P1、P2、P3、P4和3类资源R1、R2、R3（资源数量分别为9、3、6），在T0时刻的资源分配情况如下表所示。

Max

R1

R2

R3

Allocation

R1

R2

R3

Need

R1

R2

R3

Available

R1

R2

R3P13

2

2100222

112P26

1

3511102P33

1

42111

0

3P442

20024

2

0（1）T0时刻是否安全？（2）P2发出请求向量Request2(1,0,1），能否分配给它？（3）在P2申请资源后，若P1发出资源请求向量Request1（1，0，1），能否分配给它？（4）在P1申请资源后，若P3发出请求向量Request3(0,0,1），能否分配给它？第3章处理机调度与死锁99为P2试分配资源后的有关资源数据：

Max

R1

R2

R3

Allocation

R1

R2

R3

Need

R1

R2

R3

Available

R1

R2

R3P13

2

2100222

011P26

1

3612001P33

1

42111

0

3P442

20024

2

0为P3试分配资源后的有关资源数据：

Max

R1

R2

R3

Allocation

R1

R2

R3

Need

R1

R2

R3

Available

R1

R2

R3P13

2

2100222

010P26

1

3612001P33

1

42121

0

2P442

20024

2

03.7死锁的检测与解除死锁的预防和死锁的避免都是要对资源的分配加以限制，操作系统解决死锁问题的另一条途径是死锁的检测方法。死锁检测方法与死锁预防和死锁避免两种策略不同，这种方法对资源的分配不加限制，只要有剩余的资源，就可把资源分配给申请的进程，允许系统有死锁发生。这样做的结果可能会造成死锁。关键是当死锁发生时系统能够尽快检测到，以便及时解除死锁，使系统恢复正常运行。第3章处理机调度与死锁102因此，采用这种方法必须要解决三个问题：

一是何时检测死锁的发生二是如何判断系统是否出现了死锁三是当发现有死锁发生时如何去解除死锁。死锁检测的时机由于死锁检测算法允许系统发生死锁，因此最好的情况是一旦死锁产生，就能立即检测到。也就是说死锁发现得越早越好。死锁产生的时间一般是在资源分配时发生，所以将死锁的检测时机定在有资源请求之时是比较合理的。另一种方法是周期性地去检测，即每隔一定的时间检测一次。或者根据CPU的使用效率去检测。第3章处理机调度与死锁103方框中圆点的数量表示该类资源的个数。当然，申请边只能指向方框，而赋给边必须指向方框中的一个圆点。例如：P1P2●资源分配图R如图所示的资源分配图表示：P1申请临界资源R，同时R已被进程P2占有。临界资源R类中只有一个资源。第3章处理机调度与死锁104死锁的检测1．利用资源分配图通常采用的检测算法主要是通过对资源分配图的化简来确定资源分配时是否有循环等待事件。2．资源分配图的简化如果满足下列条件，那么一个连续可重被利用的资源图就能够通过进程P来进行化简：（1）进程没有被阻塞（2）进程没有请求边（3）有分配边指向P通过消除所有指向P的分配边，可以化简资源分配图。如果一个资源分配图不能通过任一个进程化简，那么它就是不可被简化的；如果有一个化简序列，导致图中没有任何种类的边，那么它就是可完全简化的。第3章处理机调度与死锁1053．死锁定理某系统状态S为死锁的充分必要条件是：