第3章处理机调度和死锁

2023/2/4阜阳师范学院计算机与信息学院1第3章处理机调度与死锁3.1处理机调度的基本概念3.2调度算法3.3实时调度3.4产生死锁的原因和必要条件3.5预防死锁的方法3.6死锁的检测与解除2023/2/4阜阳师范学院计算机与信息学院23.1处理机调度的基本概念3.1.1高级调度、中级调度、低级调度3.1.2调度队列模型3.1.3选择调度方式和调度算法的若干准则2023/2/4阜阳师范学院计算机与信息学院32023/2/4阜阳师范学院计算机与信息学院43.1.1高级、中级和低级调度经历下述三级调度:高级调度（HighScheduling）中级调度（Intermediate-LevelScheduling）低级调度（LowLevelScheduling）2023/2/4阜阳师范学院计算机与信息学院51.高级调度

又称为作业调度、宏观调度或长程调度。用于决定把后备队列中的哪些作业调入内存，为他们分配必要的资源，并创建进程。批处理系统：分时系统：实时系统：需要作业调度不需作业调度不需作业调度2023/2/4阜阳师范学院计算机与信息学院61.高级调度执行作业调度时，必须作出两个决定：接纳多少作业——每次接纳多少作业进入内存，取决于多道程序度，即允许多少个作业同时在内存中运行。接纳哪些作业——应接纳哪些作业从外存调入内存，取决于所采用的调度算法。2023/2/4阜阳师范学院计算机与信息学院72.低级调度

通常也称为进程调度、微观调度或短程调度。进程调度是最基本的一种调度，在三种OS中都有。用于决定就绪队列中哪个进程应先获得处理机，并将处理机分配给选中的进程。为实现进程调度，应具有如下三个基本机制：排队器分派器上下文切换2023/2/4阜阳师范学院计算机与信息学院82.低级调度进程调度可采用下述两种调度方式：非抢占方式抢占方式抢占的原则有：（1）优先权原则（2）短作业（进程）优先原则（3）时间片原则2023/2/4阜阳师范学院计算机与信息学院93.中级调度

中级调度又称为交换调度、中程调度或内存调度。它按一定的算法将外存中已具备运行条件的进程换入内存，而将内存中处于阻塞状态的某些进程换出至外存。运行就绪阻塞挂起阻塞挂起就绪创建退出进程调度中级调度作业调度调度的层次2023/2/4阜阳师范学院计算机与信息学院113.1.2调度队列模型仅有进程调度的调度队列模型具有高级和低级调度的调度队列模型同时具有三级调度的调度队列模型2023/2/4阜阳师范学院计算机与信息学院121.仅有进程调度的调度队列模型

在分时系统中就绪进程组织成FIFO队列形式，按时间片轮转方式运行。CPU就绪队列阻塞队列时间片完进程调度等待事件进程完成交互用户事件出现2023/2/4阜阳师范学院计算机与信息学院132.具有高级和低级调度的调度队列模型CPU就绪队列时间片完进程调度等待事件1进程完成后备队列等待事件2等待事件n事件1出现事件2出现事件n出现作业调度2023/2/4阜阳师范学院计算机与信息学院143.同时具有三级调度的调度队列模型CPU就绪队列时间片完进程调度进程完成后备队列等待事件事件出现作业调度批量作业交互型作业中级调度就绪、挂起队列事件出现阻塞、挂起队列挂起阻塞队列挂起中级调度2023/2/4阜阳师范学院计算机与信息学院153.1.3选择调度方式和调度算法的若干准则面向用户的准则周转时间短平均周转时间T平均带权周转时间（W=T(周转)/Ts(CPU执行))响应时间快截止时间的保证优先权准则面向系统的准则系统吞吐量高处理机利用率好各类资源的平衡利用练习1设有4个作业同时到达，每个作业执行时间均为2h，它们在一台处理器上按单道方式运行，则平均周转时间为（）A.1hB.5hC.2.5hD.8hB2023/2/4阜阳师范学院计算机与信息学院173.2调度算法3.2.1FCFS与SJF/SPF调度算法3.2.2高优先权优先调度算法3.2.3基于时间片的轮转调度算法2023/2/4阜阳师范学院计算机与信息学院183.2.1FCFS与SJF/SPF调度算法1.先来先服务调度算法(FCFS)

按进程申请CPU（就绪）的次序processRuntimeP127P23P35P1P2P302730352023/2/4阜阳师范学院计算机与信息学院19

FCFS实例下表列出了A、B、C、D四个作业分别到达系统的时间、要求服务的时间、开始执行的时间及各自的完成时间，计算出各自的周转时间和带权周转时间。FCFS（FirstComeFirstServe)2023/2/4阜阳师范学院计算机与信息学院20作业名到达时间服务时间开始执行时间完成时间周转时间带权周转时间A01B1100C21D3100FCFS（FirstComeFirstServe)0111110110011011021001001022021991.992023/2/4阜阳师范学院计算机与信息学院21FCFS的特点:

FCFS调度算法有利于CPU繁忙型的作业，而不利于I/O繁忙型的作业（进程）比较有利于长作业，而不利于短作业FCFS（FirstComeFirstServe)2023/2/4阜阳师范学院计算机与信息学院222.短作业（进程）优先调度算法带权周转时间周转时间完成时间SJF带权周转时间周转时间完成时间FCFS42534服务时间43210到达时间平均EDCBA作业名

作业情况调度算法4417621210214115.518143.592.8441982.6718163.2631.51392.2582.12023/2/4阜阳师范学院计算机与信息学院232.短作业（进程）优先调度算法SJF调度算法的优缺点：优点：有效降低作业的平均等待时间，提高系统吞吐量缺点：(1)对长作业不利(2)不能保证紧迫性作业（进程）的及时处理(3)不一定能真正做到短作业优先2023/2/4阜阳师范学院计算机与信息学院243.2.2高优先权优先调度算法1.优先权调度算法的类型为照顾紧迫性作业，使之在进入系统后便获得优先处理，引入了最高优先权优先（HPF）调度算法。它分为两种：非抢占式优先权算法抢占式优先权调度算法2023/2/4阜阳师范学院计算机与信息学院253.2.2高优先权优先调度算法2.优先权的类型静态优先权：在创建进程时确定的，在进程的整个运行期间保持不变,又称优先数。动态优先权：在创建进程时所赋予的优先权可以随进程的推进或随其等待时间的增加而改变。2023/2/4阜阳师范学院计算机与信息学院263.高响应比优先调度算法(HRRN)

为每个作业引入动态优先权，并使作业的优先级随着等待时间的增加而以速率a提高，则可解决问题。见下式：

优先权=(等待时间+要求服务时间)/要求服务时间＝响应时间/要求服务时间3.2.2高优先权优先调度算法练习2一个作业8：00到达系统，估计运行时间为1h。若10:00开始执行该作业，其响应比是（）A.2B.1C.3D.0.5C例题1设有4个作业J1、J2、J3、J4，它们的到达时间和计算时间如表所示。若这4个作业在一台处理器上按单道方式运行，采用高响应比优先调度算法，试写出各作业的执行顺序、各作业的周转时间及平均周转时间作业到达时间计算时间J18：00120minJ28：3040minJ39：0025minJ49：3030min解析：优先权（响应比）=(等待时间+要求服务时间)/要求服务时间＝响应时间/要求服务时间作业提交时间开始时间执行时间结束时间周转时间J18：008：00120min10：00120minJ28：3010：2540min11：05155minJ39：0010：0025min10：2585minJ49：3011：0530min11：35125min例题2在一个批处理系统中，有两个作业进程。有一个作业序列，其到达时间及估计运行时间如表所示。系统作业采用最高响应比优先调度算法，进程的调度采用短进程优先的抢占式调度算法作业到达时间估计运行时间J110：0035minJ210：1030minJ310：1545minJ410：2020minJ510：3030min例题2（1）列出各作业的执行时间（即列出每个作业运行的时间片段，如作业i的运行时间序列为10：00-10：40）（2）计算这批作业的平均周转时间。2023/2/4阜阳师范学院计算机与信息工程学院32J110:00J4:20m10:10J2到达J210:35J1完成J4进内存分析：J3J4J510:55J4完成J3进内存J1:10mJ1:25m11:25J2完成J5进内存J2:30mJ5:30m11:55J5完成12:40J3完成J3:45m例题3有一个具有两道作业的批处理系统，作业调度采用短作业优先调度算法，进程调度采用抢占式优先级调度算法，作业的运行情况如表所示，其中作业的优先数即为进程的优先数，优先数越小，优先级越高。2023/2/4阜阳师范学院计算机与信息学院33作业到达时间运行时间优先数J18：0040min5J28：2030min3J38：3050min4J48：5020min6（1）列出所有作业进入内存的时间及结束的时间（2）计算平均周转时间2023/2/4阜阳师范学院计算机与信息工程学院34J18:00J1:20m8:20J2到达J28:30分析：J3J48:50J2完成J4进入J1:20mJ2:10m9:10J1完成J3进内存J3:50mJ4:20m10:00J3完成10:20J4完成J2:20m2023/2/4阜阳师范学院计算机与信息学院353.2.3基于时间片的轮转调度算法(RR)

在分时系统中，为保证能及时响应用户的请求，必须采用基于时间片的轮转式进程调度算法。在早期，分时系统中采用的是简单的时间片轮转法，进入90年代后，广泛采用多级反馈队列调度算法。2023/2/4阜阳师范学院计算机与信息学院36将系统中所有的就绪进程按照FCFS原则，排成一个队列。每次调度时将CPU分派给队首进程，让其执行一个时间片。在一个时间片结束时，将其送到就绪队列的末尾，并通过上下文切换执行当前的队首进程。一、时间片轮转算法1.基本原理2023/2/4阜阳师范学院计算机与信息学院372.时间片长度的确定时间片长度变化的影响过长－>退化为FCFS算法。过短－>用户的一次请求需要多个时间片才能处理完，上下文切换次数增加。对响应时间的要求：T(响应时间)=N(进程数目)*q(时间片)一、时间片轮转算法2023/2/4阜阳师范学院计算机与信息学院382023/2/4阜阳师范学院计算机与信息学院39二、多级反馈队列调度算法

实施过程如下：（1）应设置多个队列并为各个队列赋予不同的优先级。第一个最高，依次降低。该算法赋予各个队列中进程执行时间片的大小也不相同，优先权越高，时间片越短。1.调度算法2023/2/4阜阳师范学院计算机与信息学院40多级反馈队列调度算法

2023/2/4阜阳师范学院计算机与信息学院41二、多级反馈队列调度算法(2)当一个新进程进入内存后，首先将它放入第一队列的末尾，按FCFS原则排队等待调度。如它在一个时间片结束时尚未完成，调度程序便将该进程转入第二队列的末尾。(3）仅当第1～（i-1）队列空闲时，才会调度第i队列中的进程运行。2023/2/4阜阳师范学院计算机与信息学院422.多级反馈队列调度算法的性能终端型作业用户短作业优先短批处理作业用户周转时间较短长批处理作业用户二、多级反馈队列调度算法2023/2/4阜阳师范学院计算机与信息学院43补充作业1、假如有四道作业，它们的进入时间和运行时间由下表给出，在单道程序环境下，分别填写先来先服务、短作业优先和RR（2）算法的完成时间、周转时间、带权周转时间、平均周转时间和带权平均周转时间。2023/2/4阜阳师范学院计算机与信息学院44作业号进入时间运行时间FCFSSJFRR（3）完成时间周转时间带权周转时间完成时间周转时间带权周转时间完成时间周转时间带权周转时间1042110326432平均2、有一个内存只能装入两道作业的批处理系统，作业调度采用短作业优先的调度算法，进程调度采用以优先数为基础的抢占式调度算法。下表中所列的优先数是指进程调度的优先数，且优先数越小优先级越高。作业名到达时间估计运行时间优先数A10:0040分5B10:2030分3C10:3050分4D10:5020分6问：列出所有作业进入内存的时刻以及结束的时刻计算作业的平均周转时间3、假设一个系统中有5个进程，它们的到达时间和服务时间如表所示，忽略I/O以及其他开销时间，若分别按先来先服务（FCFS），非抢占及抢占的短进程优先（SPF）、高响应比优先（HRRN）、时间片轮转（RR=1）、多级反馈队列调度算法（FB，第i级队列的时间片=2i-1)以及立即抢占的多级反馈队列调度算法进行CPU调度，请给出各进程的完成时间、周转时间、带权周转时间、平均周转时间和平均带权周转时间。进程到达时间服务时间A03B26C44D65E822023/2/4阜阳师范学院计算机与信息学院49第3章处理机调度与死锁3.3实时调度3.4产生死锁的原因和必要条件3.5预防死锁的方法3.6死锁的检测与解除2023/2/4阜阳师范学院计算机与信息学院503.3实时调度实时调度：合理安排就绪实时任务的执行次序，满足每个实时任务时间约束条件的调度实时任务：具有明确时间约束的计算任务2023/2/4阜阳师范学院计算机与信息学院513.3实时调度3.3.1实现实时调度的基本条件3.3.2实时调度算法的分类3.3.3常用的几种实时调度算法2023/2/4阜阳师范学院计算机与信息学院523.3.1实现实时调度的基本条件提供必要的信息系统处理能力强采用抢占式调度机制具有快速切换机制2023/2/4阜阳师范学院计算机与信息学院531.提供必要的信息就绪时间开始截止时间和完成截止时间处理时间资源要求优先级2023/2/4阜阳师范学院计算机与信息学院542.系统处理能力强

假如系统中有M个周期性的硬实时任务，处理时间为Ci，周期时间表示为Pi

则单机系统中必须满足条件

∑（Ci/

Pi）≤1

多处理机系统∑（Ci/

Pi）≤N2023/2/4阜阳师范学院计算机与信息学院553.采用抢占式调度机制

硬实时任务：广泛采用抢占机制小的实时系统：可采用非抢占调度机制（简化调度程序和对任务调度时所花费的系统开销）3.采用抢占式调度机制2023/2/4阜阳师范学院计算机与信息学院562023/2/4阜阳师范学院计算机与信息学院574.具有快速切换机制

(1)对外部中断的快速响应能力(2)快速的任务分派能力2023/2/4阜阳师范学院计算机与信息学院583.3.2实时调度算法的分类可以按照不同方式对实时调度算法加以分类：根据实时任务性质的不同可分为硬实时调度算法和软实时调度算法；按调度方式的不同可分为非抢占调度算法和抢占调度算法；2023/2/4阜阳师范学院计算机与信息学院593.3.3常用的几种实时调度算法

最早截止时间优先EDF（EarliestDeadlineFirst）算法最低松弛度优先LLF（LeastLaxityFirst）算法2023/2/4阜阳师范学院计算机与信息学院60EDF算法用于非抢占调度图示

1342t按开始截止时间早晚的排序任务执行任务到达134212341.最早截止时间优先EDF算法

截止时间越早，其优先级越高2023/2/4阜阳师范学院计算机与信息学院612.最低松弛度优先LLF算法松弛度=完成截止时间—运行时间—当前时间任务的紧急程度愈高，松弛度愈低，优先级愈高。要求系统有一个按松弛度排序的实时任务就绪队列该算法主要用于可抢占调度方式中2023/2/4阜阳师范学院计算机与信息学院62LLF算法例tA1A2A3A4A5A6B1B2020406080100120

假如在一个实时系统中，有两个周期型实时任务A、B，任务A要求每20ms执行一次，执行时间为10ms；任务B要求每50ms执行一次，执行时间为25ms；由此可得知AB任务每次必须完成的时间分别为A1、A2、A3…和B1、B2、B3…如下图：2023/2/4阜阳师范学院计算机与信息学院63LLF算法例图示tt1

t2

t3

t4

t5

t6

t7

t8

01020304050607080A1(10)A2(10)A3(10)A4(10)B1(20)B1(5)B2(15)B2(10)

4、对下面的5个非周期性实时任务，按最早开始截止时间优先调度算法，判断是该用抢占方式还是非抢占方式，并给出调度顺序。补充作业进程到达时间执行时间开始截止时间A1020110B202020C402050D502090E6020705、若有3个周期性任务，任务A要求每20ms执行一次，执行时间为10ms；任务B要求每50ms执行一次，执行时间为10ms；任务C要求每50ms执行一次，执行时间15ms应如何按最低松弛度优先算法对它们进行调度？2023/2/4阜阳师范学院计算机与信息学院673.5产生死锁的原因和必要条件3.5.1产生死锁的原因3.5.2产生死锁的必要条件3.5.3处理死锁的基本方法2023/2/4阜阳师范学院计算机与信息学院68关于死锁

死锁是指多个进程在运行过程中因争夺资源而造成的一种僵局，当进程处于这种状态时，若无外力作用，它们都将无法再向前推进。2023/2/4阜阳师范学院计算机与信息学院693.5.1产生死锁的原因产生死锁的原因可归结为如下两点：竞争资源

进程间推进顺序非法可抢占和非抢占性资源可重用性（永久性）资源和可消耗性（临时性）资源2023/2/4阜阳师范学院计算机与信息学院70P2Rel(R1)P2Rel(R2)P2Req(R1)P2Req(R2)P1Req(R1)P1Req(R2)P1Rel(R1)P1Rel(R2)①②③④D进程推进顺序不当引起死锁2023/2/4阜阳师范学院计算机与信息学院713.5.2产生死锁的必要条件

虽然进程在运行过程中可能发生死锁，但死锁的发生也必须具备一定的条件。可以看出，必须具备以下四个条件:1.互斥条件：进程所竞争的资源必须被互斥使用。2.请求和保持条件：指进程已经保持了至少一个资源，但又提出了新的资源请求，而该资源又被其他进程占有，此时请求进程阻塞，但又对自己已获得的其他资源保持不放。2023/2/4阜阳师范学院计算机与信息学院723.5.2产生死锁的必要条件

3.不剥夺条件：指进程已获得的资源，只能在使用完时由自己释放。

4.环路等待条件：指在发生死锁时，必然存在一个“进程——资源”的环形链，环路中的每一条边是进程在请求另一进程已经占有的资源。

2023/2/4阜阳师范学院计算机与信息学院733.5.3处理死锁的基本方法一、预防死锁——消除产生死锁的必要条件二、避免死锁——分配资源时防止进入不安全状态三、检测死锁——不预防死锁，出现死锁就解除四、解除死锁——与检测死锁配合使用2023/2/4阜阳师范学院计算机与信息学院743.6预防与避免死锁的方法3.6.1预防死锁3.6.2系统安全状态3.6.3利用银行家算法避免死锁2023/2/4阜阳师范学院计算机与信息学院753.6.1预防死锁1.摒弃“请求和保持”条件静态资源分配法一次性地申请其在整个过程运行过程中所需要的全部资源优点：算法简单、易于实现且很安全缺点：资源浪费严重，进程延迟运行2023/2/4阜阳师范学院计算机与信息学院762.摒弃“不剥夺”条件资源暂时释放策略:申请新的资源得不到满足则暂时释放已有的所有资源。从而摒弃了“不剥夺”条件。该方法实现起来比较复杂且付出很大代价。可能会造成前功尽弃，反复申请和释放情况。3.6.1预防死锁2023/2/4阜阳师范学院计算机与信息学院773.摒弃“环路等待”条件有序资源分配法：

与前两种策略比较，资源利用率和系统吞吐量都有较明显的改善。但也存在严重问题：为资源编号限制新设备的增加；进程使用设备顺序与申请顺序相反；限制用户编程自由。r1r2rk......申请次序rm2023/2/4阜阳师范学院计算机与信息学院78检测可满足请求

分配

不分配安全不安全系统处于安全状态：存在安全进程序列<p1,p2,…,pn>;安全不安全死锁1.安全状态3.6.2系统安全状态避免死锁的实质就是系统在进行资源分配时，如何使系统不进入不安全状态。2023/2/4阜阳师范学院计算机与信息学院792.安全状态之例

假定系统中有三个进程A、B和C，共有12台磁带机。进程A总共要求10台，B和C分别要求4台和9台。假设在T0时刻,进程A、B和C已分别获得5台、2台和2台，尚有3台未分配，如下表所示：进程最大需求已分配还需可用ABC10495225273进程最大需求已分配还需可用B42235A105510C92712

经分析发现，在T0时刻系统是安全的，因为此时存在一个安全序列<B,A,C>，即只要系统按此进程序列分配资源，就能使每个进程都顺利完成。2023/2/4阜阳师范学院计算机与信息学院803.由安全状态向不安全状态的转换如果在T0时刻后，C又请求到一台磁带机，若此时系统把剩余3台中的1台分配给C，则系统便进入不安全状态。因为，此时再也无法找到一个安全序列，结果导致死锁。进程最大需求已分配还需可用A10553B422C927

所以，引入安全状态的目的在于进行资源分配时，要使系统不发生死锁，只要保证当前的系统状态是安全的，即每次资源分配之后系统都处于安全状态。2C936练习1某计算机系统中有8台打印机，由K个进程竞争使用，每个进程最多需要3台打印机。该系统可能会发生死锁的K的最小值是（），不会发生死锁的最大值是（）。A.2B.3C.4D.5解析：R类资源共m个，n个进程互斥使用，每个进程对R类资源最大需求量为w设：M=n*（w-1）+1则m<M的可能会发生死锁，m>=M绝对不会死锁练习1某计算机系统中有8台打印机，由K个进程竞争使用，每个进程最多需要3台打印机。该系统可能会发生死锁的K的最小值是（），不会发生死锁的最大值是（）。A.2B.3C.4D.5CB2023/2/4阜阳师范学院计算机与信息学院843.6.3利用银行家算法避免死锁最有代表性的避免死锁的算法，是Dijkstra的银行家算法。这是由于该算法能用于银行系统现金贷款的发放而得名的。银行家算法中的数据结构（1）可利用资源向量Available。这是一个含有m个元素的数组，其中的每一个元素代表一类可利用的资源数目，其动态初始值是系统中所配置的该类全部可用资源的数目，其数值随该类资源的分配与回收而动态的改变。如果Available[j]=K,则表示系统中现有Rj类资源K个。（2）最大需求矩阵Max。这是一个n*m的矩阵，它定义了系统中n个进程中的每一个进程对m类资源的最大需求。如果Max[i,j]=K,则表示进程i需要Rj类资源的最大数目为K。（3）分配矩阵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]2023/2/4阜阳师范学院计算机与信息学院853.6.3利用银行家算法避免死锁安全性算法系统所执行的安全性算法可描述如下：（1）设置两个向量：工作向量work：表示系统可提供给进程继续运行所需的各类资源数目，它含有m个元素，在执行安全算法开始时，work:=Available;Finish:

它表示系统是否有足够的资源分配进程，使之运行完成。开始时先做Finish[i]:=false;当有足够资源分配给进程时，再令Finish[i]:=true。2023/2/4阜阳师范学院计算机与信息学院86安全性检测算法FWork:=Available;Finish:=false;有满足条件的j:Finish[i]=falseNeed[j]WorkFinish[i]=true;Work:=Work+Allocation[j]Ti,Finish[i]=trueTF安全不安全赋初值进程是否完成资源是否够用进程获得资源后，顺利完成并释放资源进程是否都完成2023/2/4阜阳师范学院计算机与信息学院87（2）从进程集合中找到一个能满足下述条件的进程：

Finish[i]=false;Need[i,j]<=work[j];若找到，执行步骤3，否则执行步骤4。（3）当进程Pi获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行：

work[j]:=work[i]+Allocation[i,j];Finish[i]:=true;gotostep2;（4）如果所有进程的Finish[i]=true都满足，则表示系统处于安全状态；否则，系统处于不安全状态。安全性算法2023/2/4阜阳师范学院计算机与信息学院884.银行家算法之例

假定系统中有五个进程{P0,P1,P2,P3,P4}和三类资源{A,B,C}，各种资源的数量分别为10、5、7，在T0时刻的资源分配情况如图所示。431002433P4011211222P3600302902P2122200322P1332743010753P0AvailableABCNeedABCAllocationABCMaxABC

资源情况进程2023/2/4阜阳师范学院计算机与信息学院894.银行家算法之例T0时刻的安全性：利用安全性算法对T0时刻的资源分配情况进行分析可知，在T0时刻存在着一个安全序列{P1,P3,P4,P2,P0}，故系统是安全的。FalseFalseFalseFalseFalseTrue10570107431047P0True1047302600745P2True745002431743P4True743211011532P3True532200122332P1FinishWork+AllocationABCAllocationABCNeedABCWorkABC

资源情况进程2023/2/4阜阳师范学院计算机与信息学院903.6.3利用银行家算法避免死锁银行家算法设Requesti是进程Pi的请求向量，如果Requesti

[j]=K，表示进程Pi需要K个Rj类型的资源。当Pi发出资源请求后，系统按下述步骤进行检查：2023/2/4阜阳师范学院计算机与信息学院91Pi请求资源Requesti[j]Need[j]请求超量，错返Requesti[j]Available[j]不满足，等待Available[j]:=Available[j]-Requesti[j]Allocation[i,j]:=Allocation[i,j]+Requesti[j]Need[i,j]:=Need[i,j]-Requesti[j]安全确认，pi继续Available[j]:=Available[j]+Requesti[j]Allocation[i,j]:=Allocation[i,j]-Requesti[j]Need[i,j]:=Need[i,j]+Requesti[j]pi等待FTFTTF请求的资源是否超出实际需求是否有足够的资源暂时分配资源恢复原来的资源分配状态2023/2/4阜阳师范学院计算机与信息学院92（1）如果Requesti[j]<=Need[i,j],便转向步骤2；否则认为出错，因为它所需要的资源数已超过它所宣布的最大值。（2）如果Requesti[j]<=Available[j],便转向步骤3；否则，表示尚无足够资源，Pi需等待。（3）系统试探着把资源分配给进程Pi

，并修改下面数据结构中的数值：

Available[j]:=Available[j]-Requesti[j];

Allocation[i,j]:=Allocation[i,j]+Requesti[j];Need[i,j]:=Need[i,j]-Requesti[j];（4）系统执行安全性算法，检查此次资源分配后系统是否出于安全状态以决定是否完成本次分配。银行家算法2023/2/4阜阳师范学院计算机与信息学院934.银行家算法之例P1请求资源：P1发出请求向量Request1(1，0，2),系统按银行家算法进行检查：（1）Request1(1，0，2)<=Need1(1，2，2)（2）Request1(1，0，2)<=Available1(3，3，2)（3）系统先假定可为P1分配资源，并修改Available、Allocation1和Need1向量。（4）再利用安全性算法检查此时系统是否安全。如下表：2023/2/4阜阳师范学院计算机与信息学院94FalseFalseFalseFalseFalse4.银行家算法之例

由所进行的安全性检查得知，可以找到一个安全序列{P1,P3,P4,P0,P2},因此，系统是安全的，可以立即将P1所申请的资源分配给它。True1057302600755P2True755010743745P0True745002431743P4True743211011532P3True532302020230P1FinishWork+AllocationABCAllocationABCNeedABCWorkABC

资源情况进程2023/2/4阜阳师范学院计算机与信息学院954.银行家算法之例P4请求资源：P4发出请求向量Request4(3，3，0),系统按银行家算法进行检查：（1）Request4(3，3，0)<=Need4(4