第3章 处理机调度和死锁

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

2、Scheduling）n中级调度（Intermediate-Level Scheduling）n低级调度（Low Level Scheduling）2022-5-24阜阳师范学院计算机与信息学院51. 高级调度 又称为作业调度、宏观调度或长程调度。用于决定把后备队列中的哪些作业调入内存，为他们分配必要的资源，并创建进程。 批处理系统 ：分时系统 ：实时系统 ：需要作业调度不需作业调度不需作业调度2022-5-24阜阳师范学院计算机与信息学院61. 高级调度执行作业调度时，必须作出两个决定：o 接纳多少作业每次接纳多少作业进入内存，取决于多道程序度，即允许多少个作业同时在内存中运行。o 接纳哪些

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

4、度 中级调度又称为交换调度、中程调度或内存调度。 它按一定的算法将外存中已具备运行条件的进程换入内存，而将内存中处于阻塞状态的某些进程换出至外存。运行就绪阻塞挂起阻塞挂起就绪创建退出进程调度中级调度作业调度调度的层次2022-5-24阜阳师范学院计算机与信息学院113.1.2 调度队列模型1. 仅有进程调度的调度队列模型2. 具有高级和低级调度的调度队列模型3. 同时具有三级调度的调度队列模型2022-5-24阜阳师范学院计算机与信息学院121. 仅有进程调度的调度队列模型 在分时系统中就绪进程组织成FIFO队列形式，按时间片轮转方式运行。CPU就 绪 队 列阻 塞 队 列时间片完进程调度等待

5、事件进程完成交互用户事件出现2022-5-24阜阳师范学院计算机与信息学院132. 具有高级和低级调度的调度队列模型CPU就 绪 队 列时间片完进程调度等待事件1进程完成后备队列等待事件2等待事件n事件1出现事件2出现事件n出现作业调度2022-5-24阜阳师范学院计算机与信息学院143. 同时具有三级调度的调度队列模型CPU就 绪 队 列时间片完进程调度进程完成后备队列等待事件事件出现作业调度批量作业交互型作业中级调度就绪、挂起队列事件出现阻 塞、挂 起 队 列挂起阻 塞 队 列挂起中级调度2022-5-24阜阳师范学院计算机与信息学院153.1.3 选择调度方式和调度算法的若干准则o 面向

6、用户的准则周转时间短n平均周转时间Tn平均带权周转时间（W= T(周转)/Ts(CPU执行)响应时间快截止时间的保证优先权准则o 面向系统的准则 系统吞吐量高 处理机利用率好 各类资源的平衡利用练习1o 设有4个作业同时到达，每个作业执行时间均为2h，它们在一台处理器上按单道方式运行，则平均周转时间为（ ） A. 1h B. 5h C. 2.5h D.8hB2022-5-24阜阳师范学院计算机与信息学院173.2 调度算法o 3.2.1 FCFS与SJF/SPF调度算法o 3.2.2 高优先权优先调度算法o 3.2.3 基于时间片的轮转调度算法2022-5-24阜阳师范学院计算机与信息学院18

7、3.2.1 FCFS与SJF/SPF调度算法1. 先来先服务调度算法(FCFS) 按进程申请CPU（就绪）的次序processRun timeP127P23P35P1P2P3 0 27 30 352022-5-24阜阳师范学院计算机与信息学院19 FCFS实例 下表列出了A、B、C、D四个作业分别到达系统的时间、要求服务的时间、开始执行的时间及各自的完成时间，计算出各自的周转时间和带权周转时间。FCFS（First Come First Serve)2022-5-24阜阳师范学院计算机与信息学院20作业名 到达时间服务时间开始执行时间完成时间周转时间带权周转时间A01B1100C21D3100

8、FCFS（First Come First Serve)0111110110011011021001001022021991.992022-5-24阜阳师范学院计算机与信息学院21FCFS的特点: o FCFS调度算法有利于CPU繁忙型的作业，而不利于I/O繁忙型的作业（进程）o 比较有利于长作业，而不利于短作业FCFS（First Come First Serve)2022-5-24阜阳师范学院计算机与信息学院222. 短作业（进程）优先调度算法带权周转时间周转时间完成时间 SJF带权周转时间周转时间完成时间 FCFS42534服务时间43210到达时间平均EDCBA作业名 作业情 况调度算

9、法4417621210214115.518143.592.8441982.6718163.2631.51392.2582.12022-5-24阜阳师范学院计算机与信息学院232 . 短作业（进程）优先调度算法SJF调度算法的优缺点：优点：有效降低作业的平均等待时间，提高系统吞吐量缺点：(1) 对长作业不利(2) 不能保证紧迫性作业（进程）的及时处理(3) 不一定能真正做到短作业优先2022-5-24阜阳师范学院计算机与信息学院243.2.2 高优先权优先调度算法1. 优先权调度算法的类型 为照顾紧迫性作业，使之在进入系统后便获得优先处理，引入了最高优先权优先（HPF）调度算法。它分为两种：o

10、非抢占式优先权算法o 抢占式优先权调度算法2022-5-24阜阳师范学院计算机与信息学院253.2.2 高优先权优先调度算法2. 优先权的类型1) 静态优先权：在创建进程时确定的，在进程的整个运行期间保持不变,又称优先数。2) 动态优先权：在创建进程时所赋予的优先权可以随进程的推进或随其等待时间的增加而改变。2022-5-24阜阳师范学院计算机与信息学院263. 高响应比优先调度算法(HRRN) 为每个作业引入动态优先权，并使作业的优先级随着等待时间的增加而以速率a提高，则可解决问题。见下式： 优先权=(等待时间+要求服务时间)/要求服务时间 响应时间/要求服务时间 3.2.2 高优先权优先调

11、度算法练习2o 一个作业8：00到达系统，估计运行时间为1h。若10:00开始执行该作业，其响应比是（ ） A. 2 B.1 C.3 D.0.5C例题1o 设有4个作业J1、J2、J3、J4，它们的到达时间和计算时间如表所示。若这4个作业在一台处理器上按单道方式运行，采用高响应比优先调度算法，试写出各作业的执行顺序、各作业的周转时间及平均周转时间作业到达时间 计算时间J18：00120minJ28：3040minJ39：0025minJ49：3030min解析：优先权（响应比）=(等待时间+要求服务时间)/要求 服务时间响应时间/要求服务时间作业提交时间开始时间执行时间结束时间周转时间J18：

12、008：00120min10：00120minJ28：3010：2540min11：05155minJ39：0010：0025min10：2585minJ49：3011：0530min11：35125min例题2o 在一个批处理系统中，有两个作业进程。有一个作业序列，其到达时间及估计运行时间如表所示。系统作业采用最高响应比优先调度算法，进程的调度采用短进程优先的抢占式调度算法作业到达时间 估计运行时间J110：0035minJ210：1030minJ310：1545minJ410：2020minJ510：3030min例题2o （1）列出各作业的执行时间（即列出每个作业运行的时间片段，如作业i

13、的运行时间序列为10：00-10：40）o （2）计算这批作业的平均周转时间。2022-5-24阜阳师范学院计算机与信息工程学院32J110:00J4:20m10:10J2到达到达J210:35J1完成完成J4进内存进内存分析：分析：J3J4J510:55J4完成完成J3进内存进内存J1:10mJ1:25m11:25J2完成完成J5进内存进内存J2:30mJ5:30m11:55J5完成完成12:40J3完成完成J3:45m例题3o 有一个具有两道作业的批处理系统，作业调度采用短作业优先调度算法，进程调度采用抢占式优先级调度算法，作业的运行情况如表所示，其中作业的优先数即为进程的优先数，优先数越

14、小，优先级越高。2022-5-24阜阳师范学院计算机与信息学院33作业到达时间运行时间优先数J18：0040min5J28：2030min3J38：3050min4J48：5020min6（1）列出所有作业进入内存的时间及结束的时间（2）计算平均周转时间2022-5-24阜阳师范学院计算机与信息工程学院34J18:00J1:20m8:20J2到达到达J28:30分析：分析：J3J48:50J2完成完成J4进入进入J1:20mJ2:10m9:10J1完成完成J3进内存进内存J3:50mJ4:20m10:00J3完成完成10:20J4完成完成J2:20m2022-5-24阜阳师范学院计算机与信息学

15、院353.2.3 基于时间片的轮转调度算法(RR) 在分时系统中，为保证能及时响应用户的请求，必须采用基于时间片的轮转式进程调度算法。在早期，分时系统中采用的是简单的时间片轮转法，进入90年代后，广泛采用多级反馈队列调度算法。2022-5-24阜阳师范学院计算机与信息学院36u将系统中所有的就绪进程按照FCFS原则，排成一个队列。u每次调度时将CPU分派给队首进程，让其执行一个时间片。u在一个时间片结束时，将其送到就绪队列的末尾，并通过上下文切换执行当前的队首进程。一、时间片轮转算法1. 基本原理2022-5-24阜阳师范学院计算机与信息学院372. 时间片长度的确定v时间片长度变化的影响过长

16、退化为FCFS算法。过短用户的一次请求需要多个时间片才能处理完，上下文切换次数增加。对响应时间的要求：T(响应时间)=N(进程数目)*q(时间片)一、时间片轮转算法2022-5-24阜阳师范学院计算机与信息学院382022-5-24阜阳师范学院计算机与信息学院39二、多级反馈队列调度算法 实施过程如下：（1） 应设置多个队列并为各个队列赋予不同的优先级。第一个最高，依次降低。该算法赋予各个队列中进程执行时间片的大小也不相同，优先权越高，时间片越短。1. 调度算法2022-5-24阜阳师范学院计算机与信息学院40多级反馈队列调度算法 就绪队列1就绪队列2就绪队列3就绪队列nS1S2S3至CPU至

17、CPU至CPU至CPU(时间片：S1 S2 S3)2022-5-24阜阳师范学院计算机与信息学院41二、多级反馈队列调度算法(2) 当一个新进程进入内存后，首先将它放入第一队列的末尾，按FCFS原则排队等待调度。如它在一个时间片结束时尚未完成，调度程序便将该进程转入第二队列的末尾。(3）仅当第1（i-1）队列空闲时，才会调度第i队列中的进程运行。2022-5-24阜阳师范学院计算机与信息学院422. 多级反馈队列调度算法的性能p 终端型作业用户p 短作业优先o 短批处理作业用户n 周转时间较短o 长批处理作业用户二、多级反馈队列调度算法2022-5-24阜阳师范学院计算机与信息学院43补充作业

18、1、假如有四道作业，它们的进入时间和运行时间由下表给出，在单道程序环境下，分别填写先来先服务、短作业优先和RR（2）算法的完成时间、周转时间、带权周转时间、平均周转时间和带权平均周转时间。2022-5-24阜阳师范学院计算机与信息学院44作业号进入时间运行时间FCFSSJFRR（3）完成时间周转时间带权周转时间完成时间周转时间带权周转时间完成时间周转时间带权周转时间1042110326432平均2、有一个内存只能装入两道作业的批处理系统，作业调有一个内存只能装入两道作业的批处理系统，作业调度采用短作业优先的调度算法，进程调度采用以优先度采用短作业优先的调度算法，进程调度采用以优先数为基础的抢占

19、式调度算法。下表中所列的优先数是数为基础的抢占式调度算法。下表中所列的优先数是指进程调度的优先数，且优先数越小优先级越高。指进程调度的优先数，且优先数越小优先级越高。作业名作业名到达时间到达时间估计运行时间估计运行时间优先数优先数A10:0040分5B10:2030分3C10:3050分4D10:5020分6问：列出所有作业进入内存的时刻以及结束的时刻问：列出所有作业进入内存的时刻以及结束的时刻 计算作业的平均周转时间计算作业的平均周转时间3、假设一个系统中有假设一个系统中有5个进程，它们的到达时间和服务时个进程，它们的到达时间和服务时间如表所示，忽略间如表所示，忽略I/O以及其他开销时间，若

20、分别按先来以及其他开销时间，若分别按先来先服务先服务（FCFS），），非抢占及抢占的短进程优先（非抢占及抢占的短进程优先（SPF）、）、高响应比优先高响应比优先（HRRN）、时间片轮转、时间片轮转（RR=1）、多级反、多级反馈队列调度算法（馈队列调度算法（FB，第，第i级队列的时间片级队列的时间片=2i-1)以及立以及立即即抢占的多级反馈队列调度算法进行抢占的多级反馈队列调度算法进行CPU调度，请给出各进调度，请给出各进程的完成时间、周转时间、带权周转时间、平均周转时间程的完成时间、周转时间、带权周转时间、平均周转时间和平均带权周转时间。和平均带权周转时间。进程到达时间服务时间A03B26C4

21、4D65E822022-5-24阜阳师范学院计算机与信息学院49第3章 处理机调度与死锁o 3.3 实时调度o 3.4 产生死锁的原因和必要条件o 3.5 预防死锁的方法o 3.6 死锁的检测与解除 2022-5-24阜阳师范学院计算机与信息学院503.3 实时调度o 实时调度：n 合理安排就绪实时任务的执行次序，满足每个实时任务时间约束条件的调度o 实时任务：n 具有明确时间约束的计算任务2022-5-24阜阳师范学院计算机与信息学院513.3 实时调度o 3.3.1 实现实时调度的基本条件o 3.3.2 实时调度算法的分类o 3.3.3 常用的几种实时调度算法2022-5-24阜阳师范学院

22、计算机与信息学院523.3.1 实现实时调度的基本条件o 提供必要的信息o 系统处理能力强o 采用抢占式调度机制o 具有快速切换机制2022-5-24阜阳师范学院计算机与信息学院531. 提供必要的信息o 就绪时间o 开始截止时间和完成截止时间o 处理时间o 资源要求o 优先级2022-5-24阜阳师范学院计算机与信息学院542. 系统处理能力强 假如系统中有M个周期性的硬实时任务，处理时间为Ci，周期时间表示为Pi 则单机系统中必须满足条件 （ Ci / Pi ）1 多处理机系统 （ Ci / Pi ）N2022-5-24阜阳师范学院计算机与信息学院553. 采用抢占式调度机制o 硬实时任务

23、： 广泛采用抢占机制 o 小的实时系统： 可采用非抢占调度机制（简化调度程序和对任务调度时所花费的系统开销）3. 采用抢占式调度机制2022-5-24阜阳师范学院计算机与信息学院56(a) 非抢占式轮转调度当前进程实时进程实时进程请求调度实时进程抢占当前进程并立即执行(d) 立即抢占的优先权调度调度时间进程 1进程 2实时进程要求调度进程 n实时进程调度实时进程运行(b) 非抢占式优先权调度当前进程实时进程实时进程请求调度 当前进程运行完成调度时间当前进程实时进程请求调度时钟中断到来时调度时间(c) 基于时钟中断抢占的优先权抢占调度调度时间实时进程2022-5-24阜阳师范学院计算机与信息学院

24、574. 具有快速切换机制 (1) 对外部中断的快速响应能力(2) 快速的任务分派能力2022-5-24阜阳师范学院计算机与信息学院583.3.2 实时调度算法的分类可以按照不同方式对实时调度算法加以分类：o 根据实时任务性质的不同可分为硬实时调度算法和软实时调度算法；o 按调度方式的不同可分为非抢占调度算法和抢占调度算法；2022-5-24阜阳师范学院计算机与信息学院593.3.3 常用的几种实时调度算法 o 最早截止时间优先EDF（Earliest Deadline First）算法o 最低松弛度优先LLF（Least Laxity First）算法2022-5-24阜阳师范学院计算机与信

25、息学院60EDF算法用于非抢占调度图示 1 3 4 2t按开始截止时间早晚的排序任务执行任务到达 1 3 4 2 1 2 3 4 1. 最早截止时间优先EDF算法 截止时间越早，其优先级越高2022-5-24阜阳师范学院计算机与信息学院612. 最低松弛度优先LLF算法o 松弛度=完成截止时间运行时间当前时间o 任务的紧急程度愈高，松弛度愈低，优先级愈高。o 要求系统有一个按松弛度排序的实时任务就绪队列o 该算法主要用于可抢占调度方式中2022-5-24阜阳师范学院计算机与信息学院62LLF算法例tA1 A2 A3 A4 A5 A6B1 B2 0 20 40 60 80 100 120 假如在

26、一个实时系统中，有两个周期型实时任务A、B，任务A要求每20ms执行一次，执行时间为10ms；任务B要求每50ms执行一次，执行时间为25ms；由此可得知AB任务每次必须完成的时间分别为A1、A2、A3和B1、B2、B3如下图：2022-5-24阜阳师范学院计算机与信息学院63LLF算法例图示tt1 t2 t3 t4 t5 t6 t7 t8 0 10 20 30 40 50 60 70 80A1(10) A2(10) A3(10) A4 (10) B1(20) B1 (5) B2(15) B2(10) 4、对下面的对下面的5个非周期性实时任务，按最早开始截个非周期性实时任务，按最早开始截止时间

27、优先调度算法，判断是该用抢占方式还是非止时间优先调度算法，判断是该用抢占方式还是非抢占方式，并给出调度顺序。抢占方式，并给出调度顺序。补充作业进程到达时间执行时间开始截止时间A1020110B202020C402050D502090E6020705、若有若有3个周期性任务，任务个周期性任务，任务A要求每要求每20ms执行一次，执行一次，执执行时间为行时间为10ms；任务；任务B要求每要求每50ms执行一次，执行时间执行一次，执行时间为为10ms；任务；任务C要求每要求每50ms执行一次，执行时间执行一次，执行时间15ms应如何按最低松弛度优先算法对它们进行调度？应如何按最低松弛度优先算法对它们

28、进行调度？2022-5-24阜阳师范学院计算机与信息学院673.5 产生死锁的原因和必要条件o3.5.1 产生死锁的原因o3.5.2 产生死锁的必要条件o3.5.3 处理死锁的基本方法2022-5-24阜阳师范学院计算机与信息学院68关于死锁 死锁是指多个进程在运行过程中因争夺资源而造成的一种僵局，当进程处于这种状态时，若无外力作用，它们都将无法再向前推进。2022-5-24阜阳师范学院计算机与信息学院693.5.1 产生死锁的原因产生死锁的原因可归结为如下两点：1. 竞争资源2. 进程间推进顺序非法n 可抢占和非抢占性资源n 可重用性（永久性）资源和可消耗性（临时性）资源2022-5-24阜

29、阳师范学院计算机与信息学院70P2Rel(R1)P2Rel(R2)P2Req(R1)P2Req(R2)P1Req(R1)P1Req(R2)P1Rel(R1) P1Rel(R2)D进程推进顺序不当引起死锁2022-5-24阜阳师范学院计算机与信息学院713.5.2 产生死锁的必要条件 虽然进程在运行过程中可能发生死锁，但死锁的发生也必须具备一定的条件。可以看出，必须具备以下四个条件:1. 互斥条件：进程所竞争的资源必须被互斥使用。2. 请求和保持条件：指进程已经保持了至少一个资源，但又提出了新的资源请求，而该资源又被其他进程占有，此时请求进程阻塞，但又对自己已获得的其他资源保持不放。2022-5

30、-24阜阳师范学院计算机与信息学院723.5.2 产生死锁的必要条件 3. 不剥夺条件：指进程已获得的资源，只能在使用完时由自己释放。 4. 环路等待条件：指在发生死锁时，必然存在一个“进程资源”的环形链，环路中的每一条边是进程在请求另一进程已经占有的资源。2022-5-24阜阳师范学院计算机与信息学院733.5.3 处理死锁的基本方法一、预防死锁消除产生死锁的必要条件二、避免死锁分配资源时防止进入不安全状态三、检测死锁不预防死锁，出现死锁就解除四、解除死锁与检测死锁配合使用2022-5-24阜阳师范学院计算机与信息学院743.6 预防与避免死锁的方法o3.6.1 预防死锁o3.6.2 系统安

31、全状态o3.6.3 利用银行家算法避免死锁2022-5-24阜阳师范学院计算机与信息学院753.6.1 预防死锁1. 摒弃“请求和保持”条件静态资源分配法 一次性地申请其在整个过程运行过程中所需要的全部资源o优点：算法简单、易于实现且很安全o缺点：资源浪费严重，进程延迟运行2022-5-24阜阳师范学院计算机与信息学院762. 摒弃“不剥夺”条件o 资源暂时释放策略:申请新的资源得不到满足则暂时释放已有的所有资源。从而摒弃了“不剥夺”条件。o 该方法实现起来比较复杂且付出很大代价。可能会造成前功尽弃，反复申请和释放情况。3.6.1 预防死锁2022-5-24阜阳师范学院计算机与信息学院773.

32、 摒弃“环路等待”条件o 有序资源分配法：o 与前两种策略比较，资源利用率和系统吞吐量都有较明显的改善。o 但也存在严重问题：为资源编号限制新设备的增加；进程使用设备顺序与申请顺序相反；限制用户编程自由。r1r2rk.申请次序rm2022-5-24阜阳师范学院计算机与信息学院78检测可满足请求 分配 不分配安全不安全系统处于安全状态：存在安全进程序列;安全不安全死锁1. 安全状态3.6.2 系统安全状态o 避免死锁的实质就是系统在进行资源分配时，如何使系统不进入不安全状态。2022-5-24阜阳师范学院计算机与信息学院792. 安全状态之例 假定系统中有三个进程A、B和C，共有12台磁带机。进

33、程A总共要求10台，B和C分别要求4台和9台。假设在T0时刻,进程A、B和C已分别获得5台、2台和2台，尚有3台未分配，如下表所示：进程最大需求已分配还需可用ABC10495225273进程最大需求已分配还需可用B 4 2 235A 10 5 510C 9 2 712 经分析发现，在T0时刻系统是安全的，因为此时存在一个安全序列，即只要系统按此进程序列分配资源，就能使每个进程都顺利完成。2022-5-24阜阳师范学院计算机与信息学院803. 由安全状态向不安全状态的转换o 如果在T0时刻后，C又请求到一台磁带机，若此时系统把剩余3台中的1台分配给C，则系统便进入不安全状态。因为，此时再也无法找

34、到一个安全序列，结果导致死锁。进程最大需求已分配还需可用A10553B422C927o 所以，引入安全状态的目的在于进行资源分配时，要使系统不发生死锁，只要保证当前的系统状态是安全的，即每次资源分配之后系统都处于安全状态。 2C 9 3 6练习1o 某计算机系统中有8台打印机，由K个进程竞争使用，每个进程最多需要3台打印机。该系统可能会发生死锁的K的最小值是（ ），不会发生死锁的最大值是（ ）。 A. 2 B. 3 C. 4 D. 5解析：p R类资源共m个， n个进程互斥使用，每个进程对R类资源最大需求量为wp 设：M=n*（w-1）+1p 则m=M绝对不会死锁 练习1o 某计算机系统中有8

35、台打印机，由K个进程竞争使用，每个进程最多需要3台打印机。该系统可能会发生死锁的K的最小值是（ ），不会发生死锁的最大值是（ ）。 A. 2 B. 3 C. 4 D. 5CB2022-5-24阜阳师范学院计算机与信息学院843.6.3 利用银行家算法避免死锁o最有代表性的避免死锁的算法，是Dijkstra的银行家算法。这是由于该算法能用于银行系统现金贷款的发放而得名的。1. 银行家算法中的数据结构（1）可利用资源向量Available。这是一个含有m个元素的数组，其中的每一个元素代表一类可利用的资源数目，其动态初始值是系统中所配置的该类全部可用资源的数目，其数值随该类资源的分配与回收而动态的改

36、变。如果Availablej=K,则表示系统中现有Rj类资源K个。（2）最大需求矩阵Max。这是一个n*m的矩阵，它定义了系统中n个进程中的每一个进程对m类资源的最大需求。如果Maxi,j=K,则表示进程i需要Rj类资源的最大数目为K。（3）分配矩阵Allocation。这也是一个n*m的矩阵，它定义了系统中每一类资源当前已分配给每一进程的资源数。如果Allocationi,j=K,则表示进程i当前已分得Rj类资源的数目为K。（4）需求矩阵Need。这也是一个n*m的矩阵，用以表示每一个进程尚需的各类资源数。如果Needi,j=K,则表示进程i还需要Rj类资源K个，方能完成其任务。上述三个矩阵

37、间存在的关系：Needi,j=Maxi,j-Allocationi,j2022-5-24阜阳师范学院计算机与信息学院853.6.3 利用银行家算法避免死锁3. 安全性算法系统所执行的安全性算法可描述如下：（1）设置两个向量： 工作向量work：表示系统可提供给进程继续运行所需的各类资源数目，它含有m个元素，在执行安全算法开始时，work:=Available; Finish: 它表示系统是否有足够的资源分配进程，使之运行完成。开始时先做Finishi:=false;当有足够资源分配给进程时，再令Finishi:=true。2022-5-24阜阳师范学院计算机与信息学院86安全性检测算法FWor

38、k:=Available;Finish:=false; 有满足条件的有满足条件的j:Finishi=falseNeedj WorkFinishi=true;Work:=Work+AllocationjT i ,Finishi=trueTF安全安全不安全不安全赋初值赋初值进程是否完成进程是否完成资源是否够用资源是否够用进程获得资源后，顺进程获得资源后，顺利完成并释放资源利完成并释放资源进程是否进程是否都完成都完成2022-5-24阜阳师范学院计算机与信息学院87（2）从进程集合中找到一个能满足下述条件的进程： Finishi=false;Needi,j=workj;若找到，执行步骤3，否则执行步

39、骤4。 （3）当进程Pi获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行： workj:= worki+ Allocationi,j ; Finishi:=true; goto step 2;（4）如果所有进程的Finishi=true都满足，则表示系统处于安全状态；否则，系统处于不安全状态。安全性算法2022-5-24阜阳师范学院计算机与信息学院884. 银行家算法之例 假定系统中有五个进程P0,P1,P2,P3,P4和三类资源A,B,C，各种资源的数量分别为10、5、7，在T0时刻的资源分配情况如图所示。4 3 10 0 24 3 3P40 1 12 1 12 2 2P3

40、6 0 03 0 29 0 2P21 2 22 0 03 2 2P13 3 27 4 30 1 07 5 3P0AvailableA B CNeedA B CAllocationA B CMaxA B C 资源情况资源情况进程进程2022-5-24阜阳师范学院计算机与信息学院894. 银行家算法之例 T0时刻的安全性：利用安全性算法对T0时刻的资源分配情况进行分析可知，在T0时刻存在着一个安全序列P1,P3,P4,P2,P0，故系统是安全的。FalseFalseFalseFalseFalseTrue10 5 70 1 07 4 310 4 7P0True10 4 73 0 26 0 07 4

41、5P2True7 4 50 0 24 3 17 4 3P4True 7 4 32 1 10 1 15 3 2P3True5 3 22 0 01 2 23 3 2P1FinishWork+AllocationA B CAllocationA B CNeedA B CWorkA B C 资源情况资源情况进程进程2022-5-24阜阳师范学院计算机与信息学院903.6.3 利用银行家算法避免死锁2. 银行家算法 设Requesti是进程Pi的请求向量，如果Requesti j=K，表示进程Pi需要K个Rj类型的资源。当Pi发出资源请求后，系统按下述步骤进行检查：2022-5-24阜阳师范学院计算机与

42、信息学院91Pi请求资源请求资源Requestij Needj请求超量，错返请求超量，错返Requestij Availablej不满足，等待不满足，等待Availablej:=Availablej-RequestijAllocationi,j:=Allocationi,j+RequestijNeedi,j:=Needi,j-Requestij安全安全确认，确认，pi继续继续Availablej:=Availablej+RequestijAllocationi,j:=Allocationi,j-RequestijNeedi,j:=Needi,j+Requestijpi等待等待FTFTTF请求的

43、资源是否超请求的资源是否超出实际需求出实际需求是否有足够的是否有足够的资源资源暂时分配资源暂时分配资源恢复原来的资源恢复原来的资源分配状态分配状态2022-5-24阜阳师范学院计算机与信息学院92（1）如果Requestij= Needi,j,便转向步骤2；否则认为出错，因为它所需要的资源数已超过它所宣布的最大值。（2）如果Requestij= Availablej,便转向步骤3；否则，表示尚无足够资源，Pi需等待。 （3）系统试探着把资源分配给进程Pi ，并修改下面数据结构中的数值： Availablej:= Availablej- Requestij; Allocationi,j:=All

44、ocationi,j+Requestij; Needi,j:=Needi,j-Requestij;（4）系统执行安全性算法，检查此次资源分配后系统是否出于安全状态以决定是否完成本次分配。银行家算法2022-5-24阜阳师范学院计算机与信息学院934. 银行家算法之例o 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向量。 （

45、4）再利用安全性算法检查此时系统是否安全。如下表：2022-5-24阜阳师范学院计算机与信息学院94FalseFalseFalseFalseFalse4. 银行家算法之例 由所进行的安全性检查得知，可以找到一个安全序列P1,P3,P4,P0,P2,因此，系统是安全的，可以立即将P1所申请的资源分配给它。True10 5 73 0 26 0 07 5 5P2True7 5 50 1 07 4 37 4 5P0True7 4 50 0 24 3 17 4 3P4True 7 4 32 1 10 1 15 3 2P3True5 3 23 0 20 2 02 3 0P1FinishWork+AllocationA B CAllocationA B CNeedA B CWorkA B C 资源情况资源情况进程进程2022-5-24阜阳师范学院计算机与信息学院954. 银行家算法之例o P4请求资源：P4发出请求向量Request4(3，3，0),系统按银行家算法进行检查：（1）Req