第三章 处理机调度与死锁 本章主要理解进程调度和死锁的基本概念，熟悉进程调度的各种算法及适用范围，了解产生死锁的原因和必要条件，掌握如何预防、避免、检测、解除死锁的各种方法，特别是银行家算法。 重、难点： 进程调度算法 产生死锁的原因和必要条件 银行家算法

第三章 处理机调度与死锁 3.1 处理机调度的基本概念 3.2 调度算法 3.3 实时调度 3.4 多处理机系统中的调度 3.1 处理机调度的基本概念 3.2 调度算法 3.3 实时调度 3.4 多处理机系统中的调度 3.5 产生死锁的原因和必要条件 3.6 预防死锁的方法 3.7 死锁的检测与解除

3.1 处理机调度的基本概念 要解决的问题 WHAT：按什么原则分配CPU —进程调度算法 WHEN：何时分配CPU —进程调度的时机 HOW： 如何分配CPU —CPU调度过程 （进程的上下文切换） CPU调度的目的：分配CPU。 CPU调度方式：一级调度或二级调度。 调度算法有：FCFS、SPF(SJF)、时间片轮转、优先权高者优先、多级反馈队列等不同的调度算法。

进程调度的分类有： 高级调度 按调度层次，分为 中级调度 低级调度 批处理调度 分时调度 按OS的类型，分为 实时调度 多处理机调度

3.1.1 高级、中级和低级调度 一、高级调度(又称为作业调度、长程调度/ High Scheduling)： 为什么在分(实)时系统中不配置高级调度？ 其原因是因为分时系统中，为了能及时响应用户请求，用户通过键盘输入的命令或数据等，都是直接送入内存，因而无需配置作业，而在批处理系统中，作业进入系统时先是驻留在外存上，然后根据需要才调入内存，因此需要作业调度。 在每次执行作业调度时，都需要做： 1.接纳多少个作业 2.接纳哪些作业

二、低级调度(又称进程调度、短程调度/Low Level Scheduling)： 执行分配处理机的程序称为进程调度程序（分派程序） 进程调度是操作系统中最基本的调度，在批处理系统及分时系统、实时系统中都必须配置它。

进程调度有以下两种基本方式： 1.非抢占方式： 这种调度方式的优点是：简单、系统开销小，貌似公正。 这种调度方式的缺点是：可能导致系统性能的恶化。表现为： (1)一个紧急任务到达时，不能立即投入运行，以致延误时机； (2)若干个后到的短作业，须等待长作业运行完毕才能运行，致使短作业的周转时间增长。这对短作业用户来说是不公平的。

2.抢占方式： 剥夺原则有： (1)优先权原则：优先权高的进程可以剥夺优先权低的进程的运行； (2)短作业（进程）优先原则：短进程到达后可以剥夺长进程的运行； (3)时间片原则：一个时间片用完后进程重新调度。

三、中级调度(中程调度/Intermediate-Level Scheduling)： 中级调度实际上就是存储器管理的对换。它决定哪些进程被允许参与竞争处理机资源。中级调度主要只是起到短期调整系统负荷的作用，以平顺系统的操作。其所使用的方法是通过“挂起 ” 和“激活 ” 一些进程，来达到平顺系统操作的目的。

3.1.2 调度队列模型 一、仅有进程调度的调度队列模型 在分时系统中通常只设置进程调度。 图 3 - 1 仅具有进程调度的调度队列模型 交互用户 进程调度 end 事件出现 就绪队列 I/O阻塞队列 I/O CPU 等待事件 时间片完 处于就绪队列中的进程在依次执行时，可能会发生以下三种情况： (1)进程未用完一个时间片便结束，这时系统应提前调度； (2)进程在执行过程中提出I/O请求而阻塞，系统应将它放入 阻塞队列并引起调度； (3)进程用完一个时间片后尚未完成，系统应将它放入就绪队 列的末尾，等待下次执行。

二、具有进程调度和作业调度的调度队列模型 作业后备队列 进程调度 end 就绪队列 CPU 事件1出现 I/O阻塞队列1 I/O 等待事件1 时间片完 作业调度 事件2出现 I/O阻塞队列2 等待事件2 事件n出现 I/O阻塞队列n 等待事件n … 区别： (1)在OS中不仅引入进程调度之后，而且还引入了作业调度。 (2)在OS中设置了多个阻塞队列。每一阻塞队列对应一种引起进程阻塞的事件。

三、同时具有三级调度的调度队列模型 RUN readya blockeda readys blokeds 后备 完成 执行 内存 作业后备状态 执行 内存 时间片到 I/O请求 I/O完成 高级调度(作业调度) 挂起 激活 进程调度 低级调度 中级调度

3.1.3 选择调度方式和调度算法的若干准则 一、面向用户的准则 1.周转时间短：是批处理系统中衡量性能的一个重要指标。主要有两个具体指标： (1)作业周转时间：指一个作业从提交开始到完成为止的这段时间间隔。它等于下列四个部分之和。 ① 作业从外存后备队列上等待进入内存的时间； ②在就绪队列上等待获得处理机的时间； ③在CPU上的执行时间； ④等待I/O操作完成的时间。 (2)进程周转时间：是指一个进程从第一次进入就绪队列开始到进程运行完毕所经历的时间。它等于作业周转时间中的后三部分之和。

作业的平均周转时间或作业的平均带权周转时间 前者用来衡量不同调度算法对同一作业流的调度性能，后者用来比较某一调度算法对不同作业流的调度性能。它们定义如下： 作业平均周转时间：T=1/n(∑Ti) i =1 n 其中：n——被测定作业流中的作业数 Ti——作业 i 的周转时间： Ti=Tci- Tsi Tsi ——作业 i 的提交时间 Tci ——作业 i 的完成时间 作业平均带权周转时间：W=1/n(∑Wi)= 1/n(∑Ti/tRi) 其中：tRi——作业 i 的实际执行时间 i =1 n

2.响应时间快：它是分时系统中衡量性能的一个重要指标。是指从提交一个请求开始到首次产生响应为止(显示出结果)的一段时间间隔。它等于下列三部分之和： (1)把请求信号从键盘传输到计算机的时间； (2)计算机对请求进行处理的时间； (3)再将响应送回终端的时间。 3.截止时间的保证：它是实时系统中衡量性能的一个重要指标。是指某任务必须从开始执行的最近时间，或必须完成的最迟时间。 4.优先权准则：它是紧急作业得到及时处理的重要保证。

二、面向系统的准则 1.系统吞吐量大：是用于评价批处理系统的重要指标，因而它是选择批处理系统的重要准则。 2.处理机利用率高：是大、中型计算机系统选择调度算法的重要依据。但对单用户或实时系统，它不是十分重要的准则了。 3.各类资源的平衡利用：也是大、中型计算机系统选择调度算法的重要依据。对单用户或实时系统，它不是十分重要的准则了。

3.2 调 度 算 法 3.2.1 先来先服务和短作业(进程)优先调度算法 1. 先来先服务调度算法（FCFS） 3.2 调 度 算 法 3.2.1 先来先服务和短作业(进程)优先调度算法 1. 先来先服务调度算法（FCFS） 该算法总是把处理机分配给最先进入就绪队列的进程，即：就绪队列按进入的先后顺序排队。 属于不可抢占策略 优点:实现简单 缺点:没考虑进程的优先级 此算法是有利于长(大)作业(进程)，不利于短(小)作业(进程)；有利于CPU繁忙的作业(进程)，不利于I/O繁忙的作业(进程)。

FCFS算法实例 作业 提交时间 运行时间 开始时间 完成时间 周转时间 带权周 转时间 ts(时) tR(时) tB(时) tC(时) ti(时) Wi(Z) 1 2 3 4 8.00 8.50 9.00 9.50 2.00 0.50 0.10 0.20 8.00 10.00 10.50 10.60 10.00 10.50 10.60 10.80 2.00 1.60 1.30 6.90 1.00 4.00 16.00 6.50 27.50 平均周转时间 T=6.90/4=1.725(小时) 平均带权时间 W=27.5/4=6.875

2. 短作业(进程)优先调度算法（SJF/SPF） 是指对短作业或短进程优先调度的算法。 短作业优先(SJF)的调度算法，是从后备队列中选择一个或若干个估计运行时间最短的作业，将它们调入内存运行。 短进程优先(SPF)调度算法，则是从就绪队列中选出一估计运行时间最短的进程，将处理机分配给它，使它立即执行并一直执行到完成，或发生某事件而被阻塞放弃处理机时，再重新调度。 属于不可抢占策略

优点：该算法相对FCFS来说调度性能要好些，且能满足大多数作业(均是短作业)用户的要求。 缺点：⑴该算法对长作业不利。 ⑵该算法未考虑作业的紧迫程度，因而不能保证紧迫性作业（进程 ）及时得到处理。 ⑶该算法不一定能真正做到短作业优先调度。 计算下一个CPU执行期的预测公式如下： tn：第n个实际的CPU执行期 n：第n个实际的CPU执行期预测值 ：用于控制最近的tn和其预测值n n+1=tn+(1-)n

SJF算法实例 优: 比FCFS， T ↙ W ↙ 缺: 有的作业可能始终得不到运行 作业 提交时间 运行时间 开始时间 完成时间 周转时间 带权周 转时间 ts(时) tR(时) tB(时) tC(时) ti(时) Wi(Z) 1 2 3 4 8.00 8.50 9.00 9.50 2.00 0.50 0.10 0.20 8.00 10.30 10.00 10.10 10.00 10.80 10.10 10.30 2.00 2.30 1.10 0.80 6.20 1.00 4.60 11.00 4.00 20.60 平均周转时间 T=6.20/4=1.55(小时) 平均带权时间 W=20.6/4=5.15 优: 比FCFS， T ↙ W ↙ 缺: 有的作业可能始终得不到运行

3.2.2 高优先权优先调度算法 一、优先权调度算法的类型 基本原理是：对于进程调度，它总是把处理机分配给就绪队列中具有最高优先权的进程；对于作业调度，它总选择后备队列中若干具有高优先权的作业进入内存。 优先级调度算法又可分为： 非抢占的优先级调度法 可抢占的优先级调度法

1.静态优先权：静态优先权是在创建进程时确定的，在整个运行期间不再发生改变。 二、优先权的类型 1.静态优先权：静态优先权是在创建进程时确定的，在整个运行期间不再发生改变。 确定静态优先权的依据有： (1)进程类型 (2)进程对资源的需求 (3)用户要求的优先权。 静态优先权简单易行，系统开销小，但不精确。 2.动态优先权：动态优先权是基于某种原则，使进程的优先权随时间而改变。

优点：该算法既照顾了短作业用户，同时也避免了长作业用户无限期的等待，是 FCFS 和 SJ(P)F 两种算法的较好折衷方案。 三、 高响应比优先调度算法 响应比Rp定义如下： Rp=作业响应时间tR /要求执行的时间 作业响应时间tR=作业进入系统后等待时间+要求执行的时间 Rp=1+(作业等待时间tW /要求执行的时间) HRN原理：就是在每调度一个作业投入运行时，先计算后备作业队列中每个作业的响应比，然后挑选响应比最高者投入运行。 优点：该算法既照顾了短作业用户，同时也避免了长作业用户无限期的等待，是 FCFS 和 SJ(P)F 两种算法的较好折衷方案。 缺点：算法较为复杂，增加了系统开销(计算响应比)。

HRN算法实例 作业 提交时间 运行时间 开始时间 完成时间 周转时间 带权周 转时间 ts(时) tR(时) tB(时) tC(时) ti(时) Wi(Z) 1 2 3 4 8.00 8.50 9.00 9.50 2.00 0.50 0.10 0.20 8.00 10.10 10.00 10.60 10.00 10.60 10.10 10.80 2.00 2.10 1.10 1.30 6.50 1.00 4.20 11.00 6.50 22.70 平均周转时间 T=6.50/4=1.625(小时) 平均带权时间 W=22.7/4=5.675

3.2.3 基于时间片的轮转调度算法 1. 时间片轮转法 ⑴基本原理 轮转法是最简单又最公平的进程调度算法。主要用于分时系统中作为其主调度算法。 属于可抢占策略。 轮转法分配给每一进程在CPU上运行的时间长度，称之为时间片。其基本原理是：诸进程以此时间片为限制，轮流使用CPU。如果时间片到期时，进程尚未完成运行，调度程序将剥夺它正在使用的CPU，转让给另一进程使用；如果进程在使用完它的某一时间片之前已经完成运行或已阻塞，CPU也立即转让给另一进程使用。

上运行。时间片的计数则可通过定时中断实现。 100ms 轮转法在实现上也很容易，调度 程序只要维护一个先进先出的队列 数据结构，将就绪进程排队，每当 一个进程的时间片运行完后，便把 它从原来的队头位置移到队尾，然后 把现在处于队头位置的进程调度到CPU 上运行。时间片的计数则可通过定时中断实现。 交互用户 进程调度 end 事件出现 就绪队列 I/O阻塞队列 I/O CPU 等待事件 时间片完

时间片选择有：固定时间片和可变时间片；与时间片大小有关的因素有：系统响应时间、就绪进程个数和CPU处理能力三个。 ⑵时间片大小的确定 轮转法的性能取决于时间片大小的选择。 例：若一次切换时间为5毫秒，时间片长度选择为20毫秒，则20％的CPU时间花费于进程调度程序。为了改善CPU的利用率，可以增大时间片，比如说为500毫秒，此时CPU利用率达99％之多，但每一进程的响应时间也因之增大。若就绪队列中共有10个进程，则每一进程需要等待5秒钟，才能在CPU上服务一次。 通常来说，选择时间片为100毫秒左右比较适宜。 时间片选择有：固定时间片和可变时间片；与时间片大小有关的因素有：系统响应时间、就绪进程个数和CPU处理能力三个。

实际中，轮转法常和优先级算法结合使用，也就是按优先级将进程分组，组间采用优先级调度算法，而组内优先级相同的进程则按轮转法调度（即多级反馈队列调度算法）。显然，若优先级不动态地进行调整，则优先级低的就绪进程就可能饿死。 2. 多级队列调度算法 基本思路：把终端型作业作为前台作业，并排成一个队列，称为前台队列；把批处理作业作为后台作业，也排成一个队列，称为后台队列。系统令前台队列中各进程按时间片轮转，仅当前台队列中出现空闲时间片时，才把处理机分配给后台队列中的各进程，并令它们按FCFS方式依次执行。

3. 多级反馈队列调度算法 ⑴调度算法 思路如下：把进程按优先级分组，优先级最高的进程组中的进程每次在CPU上运行一个时间片t长度；优先级次之的进程组的进程每次运行二个时间片2t长度；优先级再次之的进程组的进程每次运行4个时间片4t长度，以此类推，进程每次运行完它的时间片后便降低一个优先级别，移至另一优先级的进程组中。

(时间片：s1<s2<s3<…) 最高优先权队列时间片 次高优先权队列时间片 最低优先权队列时间片 新进程 进入 s1 s2 s3 sn 至CPU (时间片：s1<s2<s3<…) 多级反馈队列调度算法示意图

* 首先系统中设置多个就绪队列 * 每个就绪队列分配给不同时间片，优先级高的为第一级队列，时间片最小，随着队列级别的降低，时间片加大 * 各个队列按照按时间片轮转的先来先服务出调度算法 * 一个新进程就绪后进入第一级队列 * 进程由于等待而放弃CPU后，进入等待队列，一旦等待的事件发生，则回到原来的就绪队列 * 当有一个优先级更高的进程就绪时，可以抢占CPU，被抢占进程回到原来一级就绪队列末尾 * 当第一级队列空时，就去调度第二级队列，如此类推 * 当时间片到后，进程放弃CPU，回到下一级队列

⑵多级反馈队列调度算法的性能 多级反馈队列调度算法具有较好的性能，能满足各种类型用户的需要。 1.终端型用户：作业较小，可在第一队列的时间片内完成。 2.短批处理型作业用户：大多数作业可在第一队列的时间片内完成，稍长的也可在第二队列的时间片内完成。 3.长批处理型作业用户：可依次在第一、二、 …… 、n队列的时间片内完成。

3.3 实 时 调 度 3.3.1 实现实时调度的基本条件 1. 提供必要的信息 就绪时间。 (2) 开始截止时间和完成截止时间。 (3) 处理时间。 (4) 资源要求。 (5) 优先级。

2. 系统处理能力强 在实时系统中，通常都有着多个实时任务。若处理机的处理能力不够强，则有可能因处理机忙不过来而使某些实时任务不能得到及时处理， 从而导致发生难以预料的后果。 假定系统中有m个周期性的硬实时任务，它们的处理时间可表示为Ci，周期时间表示为Pi，则在单处理机情况下，必须满足下面的限制条件：

系统才是可调度的。假如系统中有6个硬实时任务，它们的周期时间都是 50 ms，而每次的处理时间为 10 ms，则不难算出，此时是不能满足上式的，因而系统是不可调度的。 解决的方法是提高系统的处理能力，其途径有二：其一仍是采用单处理机系统， 但须增强其处理能力， 以显著地减少对每一个任务的处理时间；其二是采用多处理机系统。假定系统中的处理机数为N，则应将上述的限制条件改为：

3. 采用抢占式调度机制 当一个优先权更高的任务到达时，允许将当前任务暂时挂起，而令高优先权任务立即投入运行，这样便可满足该硬实时任务对截止时间的要求。但这种调度机制比较复杂。 对于一些小的实时系统，如果能预知任务的开始截止时间，则对实时任务的调度可采用非抢占调度机制，以简化调度程序和对任务调度时所花费的系统开销。但在设计这种调度机制时，应使所有的实时任务都比较小，并在执行完关键性程序和临界区后，能及时地将自己阻塞起来，以便释放出处理机， 供调度程序去调度那种开始截止时间即将到达的任务。

4. 具有快速切换机制 该机制应具有如下两方面的能力： (1) 对外部中断的快速响应能力。为使在紧迫的外部事件请求中断时系统能及时响应，要求系统具有快速硬件中断机构，还应使禁止中断的时间间隔尽量短，以免耽误时机(其它紧迫任务)。 (2) 快速的任务分派能力。在完成任务调度后，便应进行任务切换。为了提高分派程序进行任务切换时的速度， 应使系统中的每个运行功能单位适当的小，以减少任务切换的时间开销。

3.3.2 实时调度算法的分类 1. 非抢占式调度算法 (1)非抢占式轮转调度算法。能获得秒级的响应时间，只适合于实时信息处理系统

(2) 非抢占式优先调度算法。能获得秒级至数百毫秒级的响应时间，适合于要求不太严格的实时控制处理系统。

2. 抢占式调度算法 (1)基于时钟中断的抢占式优先权调度算法。能获得数十毫秒级至数毫秒级的响应时间，适合于大多数的实时控制处理系统。

(2) 立即抢占(Immediate Preemption)的优先权调度算法。能获得数毫秒级至百微秒级的响应时间，适合于对响应时间要求非常严格的实时控制处理系统。

3.3.3 常用的几种实时调度算法 1. 最早截止时间优先即EDF算法 (Earliest Deadline First)

2. 最低松弛度优先即LLF算法(Least Laxity First) 该算法是根据任务紧急(或松弛)的程度，来确定任务的优先级。假如在一个实时系统中，有两个周期性实时任务A和B，任务A要求每 20ms执行一次，执行时间为10ms；任务B只要求每50ms执行一次，执行时间为25ms。 图 3-8 A和B任务每次必须完成的时间

图 利用ELLF算法进行调度的情况 t1=0 A1 的松驰度：20-10=10(ms) B1 的松驰度：50-25=25(ms) 抢占B2调度A4执行 t8=80 A5 的松驰度：100-10-80=10(ms) B2 的松驰度：100-10-80=10(ms) 调度B2执行 t5=45， B1 完成 A3 的松驰度：60-10-45=5(ms) B2 的松驰度：100-25-45=30(ms) 调度A3执行 t6=55 任务A尚未进入第4周期 任务B已经进入第2周期 调度B2执行 t4=40 A3 的松驰度：60-10-40=10(ms) B1 的松驰度：50-5-40=5(ms) 调度B1执行 t2=10 ，A1 完成 任务A尚未进入第2周期 任务B已经进入第1周期 调度B1执行 t3=30 A2 的松驰度：40-10-30=0(ms) B1 的松驰度：50-5-30=15(ms) 抢占B1调度A2执行 A1(10) A2(10) A3(10) A4(10) t1 t2 t3 t4 t5 45 50 t6 55 60 t7 t8 10 20 30 40 70 80 B1(20) B1(5) B2(15) B2(10) 图 利用ELLF算法进行调度的情况

3.4 多处理机系统中的调度 前面所讨论的是单CPU下的进程调度，对于多CPU，一方面由于有多台处理机，可采用的调度策略也随之增多，另一方面在调度目标上，要求的是整个系统的运行效率的提高，即不能只保证单CPU忙，而且在引入线程后，调度的基本单位已经是线程了。因此，在多CPU的OS中，广泛采用了线程调度机制，本节主要介绍对线程的调度问题。

特点：通过高速总线或高速交叉开关进行处理机之间的互连，并共享存储器。 一般说，该结构里的所有处理机都是相同的。 3.4.1 多处理器系统(MPS)的类型 1.紧密耦合MPS和松散耦合MPS (1)紧密耦合MPS结构（同构型） 高 速 交 叉 开 关 M1 M2 M3 Mn I/O2 I/O1 … . P1 P2 P3 Pn 特点：通过高速总线或高速交叉开关进行处理机之间的互连，并共享存储器。 一般说，该结构里的所有处理机都是相同的。

特点：各个处理机有自己的存储器和OS，它们之间通过通道或通信线路实现互连。 一般说，该结构里的所有处理机可以不相同。 (2)松散耦合MPS结构（异构型） P1 P2 Pn Mn M2 M1 I/O2 I/O1 I/On …… 特点：各个处理机有自己的存储器和OS，它们之间通过通道或通信线路实现互连。 一般说，该结构里的所有处理机可以不相同。 在多处理机系统中，进程调度与系统结构和OS的工作模式均相关。

2. 对称多处理器系统和非对称多处理器系统 (1)对称多处理器系统SMPS (Symmetric MultiProcessor System) 在系统中所包含的各处理器单元，在功能和结构上都是相同的，当前的绝大多数MPS都属于SMPS。例如，IBM公司的SR/6000 Model F50, 便是利用4片Power PC处理器构成的。 (2) 非对称多处理器系统AMPS(Asymmetrical MultiProcessor System) 在系统中有多种类型的处理单元，它们的功能和结构各不相同，其中只有一个主处理器，有多个从处理器。

3.4.2 进程分配方式 1. 对称多处理器系统中的进程分配方式 在SMP系统中，所有的处理器都是相同的，因而可把所有的处理器作为一个处理器池(Processor pool)，由调度程序或基于处理器的请求， 将任何一个进程分配给池中的任何一个处理器去处理。在进行进程分配时，可采用以下两种方式之一。

1. 静态分配：是指一个进程从开始执行直到完成，都被固定分配到一台处理机上去执行。 采用该分配，需为每个处理机设置一个专用的就绪进程队列，该队列中的诸进程先后都被分配到该处理机上。在进程阻塞后再次就绪时，仍被挂在原来这个就绪队列中。 优点：进程调度的开销小。 缺点：会使各CPU的忙、闲不均。

2. 动态分配：是指一个进程从开始执行直到完成，可以随机的被分配到任意一台空闲处理机上去执行。 采用该分配，只需为系统设置一个公共的就绪队列，所有就绪进程均放在此队列中。在进程阻塞后再次被执行时，分配给它的处理机可能已经不是它原来分配给的处理机。 优点：消除了各CPU的忙、闲不均的现象。 缺点：进程调度的开销较大。

2. 非对称MPS中的进程分配方式 对于异构型多处理机系统，OS大多采用主—从式(Master/Slave)式OS，即OS的核心部分驻留在主机上，而从机只是执行用户程序，进程调度只由主机执行。每当从机空闲时，便向主机发送一要求进程的信号，主机便从队首摘下一进程分配给发出请求信号的从机。从机执行完毕后又向主机发送一要求进程的信号，如此继续，直到任务完成。 优点：系统易于实现，系统开销较小。 缺点：资源利用率低，可靠性差，缺乏灵活性。

3.4.3 进程(线程)调度方式 1. 自调度(Self-Scheduling)方式 1) 自调度机制 在多处理器系统中，自调度方式是最简单的一种调度方式。它是直接由单处理机环境下的调度方式演变而来的。在系统中设置有一个公共的进程或线程就绪队列，所有的处理器在空闲时，都可自己到该队列中取得一进程(线程)来运行。在自调度方式中，可采用在单处理机环境下所用的调度算法，如先来先服务调度算法、最高优先权优先调度算法和抢占式最高优先权优先调度算法等。

2) 自调度方式的优点 ① 只要系统中有工作可做，或说只要就绪队列不空，就不会出现处理机空闲的情况。 ② 系统中没有集中的调度机制，任何处理机都可以利用OS的调度例程去选择一线程。 ③对就绪队列可按单处理机所采用的各种方式加以组织，其调度算法可沿用单处理机所用的算法。

3) 自调度方式的缺点 ① 瓶颈问题。这个问题在多处理机系统中当处理机个数不多时，表现得并不严重，但当处理机数目增大到数十乃至数百个时，就会产生严重的瓶颈问题了。 ② 低效性。由于一个线程在整个生命期中可能要多次更换处理机，保存在原来（上一次）处理机高速缓存中的该线程数据需要在新处理机上重新建立拷贝，使得高速缓存的使用效率很低。 ③对线程切换频繁。一个应用程序的若干线程在自调度方式中很难同时获得处理机而同时运行，使得该应用程序中的某些线程会因其合作线程未获得处理机而被阻塞，进而被切换下来。

2. 成组调度(Gang Scheduling)方式 为了解决自调度方式中线程切换频繁的问题，提出了成组调度。它的调度性能通常优于自调度，目前已得到广泛认可。 所谓成组调度，是将一个进程的若干线程分配到一组处理机上去执行。这样分配有如下好处： ① 如果一组相互合作的线（进）程，能并行执行，则可有效地减少线（进）程的阻塞情况的发生，从而可以减少线程的切换，使系统性能得到改善。 ② 因为每次调度都可以解决一组线程的处理机分配问题，因而可以显著地减少调度频率，从而也就减少了调度开销。

(1) 面向所有的应用程序平均分配处理机时间 假定应用程序A有4个线程、B有1 个线程。 在成组调度中分配处理机可以采用： (1) 面向所有的应用程序平均分配处理机时间 假定应用程序A有4个线程、B有1 个线程。 应用程序A 应用程序B 线程1 线程2 空闲 线程3 线程4 处理机1 处理机2 处理机3 处理机4 1/2 1/2 浪费：3/8=37.5%

(2) 面向所有的线程平均分配处理机时间 假定应用程序A有4个线程、B有1 个线程。 应用程序A 应用程序B 线程1 线程2 空闲 线程3 线程4 处理机1 处理机2 处理机3 处理机4 4/5 1/5 浪费：3/20=15%

3. 专用处理器分配方式(Dedicated Processor Assigement) 该调度方式是在一个应用程序执行期间，专门为该应用程序分配一组处理机，每一个线程一个，直到应用程序完成。 显然这会造成处理机的严重浪费。如一个线程为了和另一个线程保持同步而阻塞起来，则该线程所分配到的处理机就会空闲。 选择这种调度方式的理由是： ① 在具有数十乃至数百个处理机的高度并行的系统中，每个处理机的投资费用在整个系统中只占很小一部分，对系统效率和性能来说，单个处理机的利用率已远不像在单机系统中那么重要。 ② 在一个应用程序的整个运行过程中，由于每个进（线）程专用一台处理机，因此可以完全避免进程或线程的切换，从而大大加速程序的完成。

3.5 产生死锁的原因和必要条件 早期的操作系统对申请某种资源的进程，若该资源尚未分配时，立即将该资源分配给这个进程。后来发现，对资源不加限制地分配可能导致进程间由于竞争资源而相互制约以至于无法继续运行的局面，人们把这种局面称为死锁 (deadlock)。 死锁问题在1965年由Dijkstra发现，并随着计算机技术的发展，逐渐成为人们关心的问题。那么，什么是死锁？其确切的定义是什么？死锁是怎么产生的？用什么方法来解决死锁？这些正是今天我们要讨论的问题。

死锁(Deadlock)的定义：一组进程中，每个进程都无限等待被该组进程中另一进程所占有的资源，因而永远无法得到的资源，这种现象称为进程死锁，这一组进程就称为死锁进程。 关于死锁的一些结论： 参与死锁的进程最少是两个 两个以上进程才会出现死锁 参与死锁的进程至少有两个已经占有资源 参与死锁的所有进程都在等待资源 参与死锁的进程是当前系统中所有进程的子集 注：如果死锁发生，会浪费大量系统资源，甚至导致系统崩溃。

3.5.1 产生死锁的原因 产生死锁的原因有两点： (1)竞争资源：为多个进程所共享的资源不够，引起它们对资源的竞争而产生死锁； (2)进程推进顺序不当：在进程运行过程中，请求资源和释放资源的顺序不当，也会产生死锁。 一、竞争资源引起的死锁 首先，介绍两个与死锁有关的概念。 可剥夺性资源：是指系统中那些已被进程占用但又可被其它进程所抢占的系统资源。如处理机、内存区等。 非剥夺性资源：是指系统中那些已被进程占用后便不能被其它进程所抢占的系统资源。如：打印机、扫描仪等。

1.竞争非剥夺性资源的例子 例1. 日常生活中常有许多有关死锁的事件。 当然，各路车队等待的事件都不会发生(假设它们都不改变行车方向)。这样若不采用特殊方法，它们将永远停留在这“井”字形的路上，而处于死锁状态。

共享资源的严重缺乏，多个进程对共享资源的竞争，尤其是管理者的调度策略不高明或失误，使它们都处于无止境的等待状态。 在计算机系统中，进程发生死锁的现象与上述事例实质上是一样的。进程是因相互竞争资源而导致死锁的，与四路车队(可视为进程)竞争路口(可视为资源) 类似。计算机系统中有各种资源，如外设、数据、文件、程序等。

例2. 竞争外部设备。设系统中有打印机、磁带机各一台，进程A、B的申请如下： 请求 占用 请求 占用 打印机 阻塞 阻塞 磁带机 死锁

临时性资源是指由一个进程产生的被另一进程使用一短暂时间后便无用的资源。也称消耗性资源。如信号量,中断信号，同步信号等。 2.竞争临时性资源： 临时性资源是指由一个进程产生的被另一进程使用一短暂时间后便无用的资源。也称消耗性资源。如信号量,中断信号，同步信号等。 进程 P2 P3 P1 产生 请求 临时性 资源S3 资源S1 资源S2 请求 产生 请求 产生

P1: … Release(S1);Request(S3);… P2: … Release(S2);Request(S1);… 若按下列顺序进行： 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); … 则很可能发生“死锁”。 进程 P2 P3 P1 临时性 资源S3 资源S1 资源S2 产生 请求

二、进程推进顺序不当引起的死锁 由于进程具有异步特征，这就使得进程可能按下列两种顺序向前推进： 1.进程推进顺序合法：进程P1和P2并发执行时，若按曲线① 即： P1:Request(S1);→P1:Request(S2);→P1:Release(S1);→Release(S2);→P2:Request(S1);→P2:Request(S2);→ P2:Release(S1);→Release(S2)；则两个进程可顺利完成，不会产生“死锁”。 类似地，曲线②和曲线③也不会产生“死锁”。

D ② ① ③ P2Req(S1) P2Req(S2) P1Req(S2) P1Req(S1) P1Rel(S2) P1Rel(S1)

则两个进程间互相产生了阻塞，从而产生“死锁”。 把区域D称为是“系统不安全区”。 2.进程推进顺序非法：进程P1和P2并发执行时，若按曲线④ 即：P1:Request(S1);→P2:Request(S2);→ P1:Request(S2); 阻塞。→ P2:Request(S1); 阻塞。 则两个进程间互相产生了阻塞，从而产生“死锁”。 把区域D称为是“系统不安全区”。 ① ③ ② D P2Req(S1) P2Req(S2) P1Req(S2) P1Req(S1) P1Rel(S2) P1Rel(S1) P2Rel(S2) P2Rel(S1) ④

3.5.2 产生死锁的必要条件 1.互斥：进程要求对所分配的资源进行互斥性访问。即在一段时间内某资源仅为一个进程所占有，如果此时还有其它进程要求访问该资源，则要求者只能被阻塞，直到该资源的占用进程用毕释放； 2.请求和保持：当进程已经占有了至少一个资源，若又提出了新的资源请求，而该资源又被其它进程所占用，则此请求被阻塞，但对它对已获得的资源保持不放；

3.不剥夺：进程已获得的资源，在未使用完之前，不能被剥夺，只能由使用者在使用完后释放； 4.环路等待：在发生死锁时，必然存在一个进程—资源的环形链。即进程集合{P1、P2、…、Pn}中的P1正在等待一个P2占用的资源，P2正在等待一个P3占用的资源，……、Pn正在等待一个P1占用的资源。 这四个必要条件中只要有一个条件不满足，都不会形成“死锁”。

3.5.3 处理死锁的基本方法 1.预防死锁：通过设置某些限制条件，以破坏产生死锁必要条件中的一个或几个来预防死锁的产生； 3.5.3 处理死锁的基本方法 1.预防死锁：通过设置某些限制条件，以破坏产生死锁必要条件中的一个或几个来预防死锁的产生； 2.避免死锁：这是通过在资源的动态分配过程中，使用某种方法去防止系统进入不安全状态，从而避免了死锁的产生； 3.检测死锁：这种方法是在死锁出现时通过系统设置的检测机构来及时地检测出死锁，并精确地确定出与死锁有关的进程和资源，然后采取适当措施，从系统中清除所发生的死锁； 4.解除死锁：这是与检测死锁相配套的一种设施，用于将进程从死锁状态下解脱出来。常用方法撤消或挂起一些进程，以便释放一些资源，再将这些资源分配给已处于阻塞状态的进程，使之转为就绪状态以继续执行。

3.6 预防死锁的方法 3.6.1 预防死锁 由于死锁产生的必要条件中(1)是设备的固有特性，不仅不能改变之，还要设法加以保证。因此，只能通过让从(2)、(3)、(4) 条件中之一不成立上考虑。 一、屏弃“请求和保持”条件 为了屏弃这一条件，系统要求所有进程一次性地申请其所需的全部资源。这样，进程在运行期间便不会再提出任何资源要求，从而使“请求”条件不成立；在分配时只要有一种资源请求未能满足，便把已有的其它资源也全部不分配给该进程，该进程只能等待，从而破坏了“保持”条件，最终可以避免死锁的产生。

注意：1.破坏请求条件虽可保证无死锁，但是 资源的利用率低 (如制表打印程序，在运行过程中，打印机空闲)；由于所需资源不能在一次中得到全部满足，而使作业无限期延长。 2.破坏保持条件虽然能提高资源利用率，但要仔细进行程序设计，有时仍需提前申请资源才能保证正确性。这使用户倍感不便（要考虑无限等待现象 <其实质与死锁一样>）。 优点：简单、易于实现，且比较安全。 缺点：(1)资源浪费严重； (2)进程延迟执行。

二、屏弃“不剥夺”条件 该策略规定，一个已保持了某些资源的进程，若新资源要求不能立即得到满足，必须释放已保持的所有资源，以后需要时再重新申请。这意味着一个进程已占有的资源在运行过程中可能被其它进程剥夺，从而使“不剥夺”条件不成立，最终可以避免死锁的产生。 有两种方式实现： 方法一：当进程Pi申请rj类资源时，检查rj中有无可分配的资源，有则分配给Pi；否则将Pi占有的资源全部释放进入等待状态。

方法二：当Pi申请rj时，检查rj中有无可分配的资源，有则分配；否则检查占有rj类资源的进程Pk。若Pk处于等待资源状态，则剥夺Pk的rj分给Pi；若Pk处于不等待资源状态，则置Pi于等待资源状态 (此时Pi原占有的资源可能被剥夺) 剥夺资源时，需保存中间信息。因使用资源的进程尚未主动释放资源，这样开销很大。故只宜在CPU和主存这类重要资源的管理上使用。不宜剥夺临介资源等类型资源。 因此，屏弃“不剥夺”条件有如下缺点： (1)实现困难且代价太大； (2)会延长进程周转时间、增加系统开销和降低系统吞吐率。

三、屏弃“环路等待”条件 在该策略中，将所有的系统资源按类型进行线性排队，并赋予不同的序号。所有进程对资源的请求严格按资源序号递增顺序提出，这样在所形成的资源分配图中不可能出现环路，从而使“环路等待”条件不成立，最终可以避免死锁的产生。 采用资源顺序分配法，可以破坏循环等待条件。该方法首先给系统中的资源编号 (唯一)，即寻找一个函数F：RN (R：表资源类集合) 即： F(R)=N 每个进程只能按序号由小到大的顺序申请资源，而且对它所必须使用的且属于某一类的所有资源，必须一次申请完。

因为在任何时刻，总有一个进程占有较高序号的资源，该进程继续请示的资源必然是空闲的。故该进程可一直向前推进。 优点：资源利用率高，系统吞吐量大。 缺点：(1)为系统中各种资源类型分配序号时，必须相对稳定，从而限制了新设备的增加； (2)会出现作业使用的资源顺序与系统规定的顺序不同的情况，造成资源的浪费。 (3)限制了用户简单、自由地编程。

3.6.2 系统安全状态 在避免死锁的方法中，允许进程动态地申请资源，但系统在进行资源分配之前，应先计算此次资源分配的安全性。若此次分配不会导致系统进入不安全状态，则将资源分配给进程； 否则，令进程等待。 一、安全状态与不安全状态 安全状态：是指系统能按某种进程顺序如<P1，P2，…，Pn> (称<P1，P2，…，Pn>序列为安全序列)，来为每个进程分配其所需资源，直至最大需求，使每个进程都可以顺利完成。 不安全状态：是指系统找不到一个进程安全序列<P1，P2，…，Pn>，当为每个进程分配其所需资源后，能使每个进程可以顺利完成。

虽然并非所有的不安全状态都是死锁状态，但当系统进入不安全状态后，可能进入死锁状态；反之系统只要处于安全状态，就可避免进入死锁状态。因此避免死锁的实质就是如何使系统不进入不安全状态。 二、安全状态之例 例：假定系统有三个进程P1、P2和P3，12台磁带机。 进程 最大需求量 已分配 可用 P1 10 5 3 P2 4 2 P3 9 2 经分析知，存在一个安全序列< P2，P1，P3 >，只要系统按此进程序列分配资源，每个进程都可以顺利完成。

如果不按照安全顺序分配资源，则系统可能由安全状态进入不安全状态。 三、由安全状态向不安全状态的转换 如果不按照安全顺序分配资源，则系统可能由安全状态进入不安全状态。 例：假定系统有三个进程P1、P2和P3，有12台磁带机。 进程 最大需求量 已分配 可用 P1 10 5 3 P2 4 2 P3 9 2 在T0时刻P3又申请了一台磁带机，若将剩余3台中的一台分配给P3 则系统会进入不安全状态。 因为此时也无法再找到一个安全序列， 例如把其余的2台分配给P2，这样在P2完成后只能释放出4台，既不能满足P1尚需5台的要求，也不能满足P3尚需6台的要求，致使它们都无法推进到完成，彼此都在等待对方释放资源，陷入僵局，导致死锁。

3.6.3 利用银行家算法避免死锁 1. 银行家算法中的数据结构 (1)可利用资源向量Available: ARRAY[1..m] of integer。这是一个含有m个元素的数组，其中的每一个元素代表一类可利用的资源数目，其初始值是系统中所配置的该类全部可用资源的数目，其数值随该类资源的分配和回收而动态地改变。如果Available[j]=K，则表示系统中现有Rj类资源K个。 (2)最大需求矩阵Max: ARRAY[1..n,1..m] of integer 。这是一个n×m的矩阵，它定义了系统中n个进程中的每一个进程对m类资源的最大需求。如果Max[i,j]=K，则表示进程i需要Rj类资源的最大数目为K。

Need[i,j]=Max[i,j]-Allocation[i,j] (3) 分配矩阵Allocation: ARRAY[1..n,1..m] of integer 。这也是一个n×m的矩阵，它定义了系统中每一类资源当前已分配给每一进程的资源数。如果Allocation[i,j]=K，则表示进程i当前已分得Rj类资源的数目为K。 (4) 需求矩阵Need: ARRAY[1..n,1..m] of integer 。这也是一个n×m的矩阵，用以表示每一个进程尚需的各类资源数。如果Need[i,j]=K，则表示进程i还需要Rj类资源K个，方能完成其任务。 Need[i,j]=Max[i,j]-Allocation[i,j] (5)请求矩阵Request: ARRAY[1..n,1..m] of integer; 一进程申请需要某类资源的资源数

2. 银行家算法 当进程Pi提出资源申请时，系统执行下列步骤： ⑴若Request[i]≤Need[i],转⑵；否则错误返回。因为它所 需要的资源数已超过它所宣布的最大值。 ⑵若Request[i]≤Available，转⑶；否则表示尚无足够资源， Pi须等待。 。 ⑶系统试探着把资源分配给进程Pi，并修改下面数据结构 中的数值： Available:=Available-Request[i]; Allocation[i]:=Allocation[i]+Request[i]; Need[i]:=Need[i]-Request[i]; ⑷系统执行安全性算法，检查此次资源分配后，系统是 否处于安全状态。若安全，才正式将资源分配给进程Pi，以 完成本次分配；否则， 将本次的试探分配作废，恢复原来 的资源分配状态，让进程Pi等待。

三、安全性算法 为进行安全性检查， 1. 定义数据结构： Work:ARRAY[1..m] of integer; 表示系统可提供给进程继续运行所需要 的各类资源数目。 Finish:ARRAY[1..n] of Boolean; 表示系统是否有足够资源分配给进程， 使之运行完成。初值设为false。

2.安全性检查的步骤： (1) Work:=Available; Finish:=false; (2) 寻找满足条件的i： ①Finish[i]=false; ②Need[i]≤Work; 如果不存在，则转(4) (3) Work:=Work+Allocation[i]; Finish[i]:=true; 转(2) (4) 若对所有i，Finish[i]=true，则系统处于安全 状态，否则处于不安全状态

四、银行家算法例子 例1：假定系统中有{P0, P1, P2 , P3 , P4} 5个进程和3类资源{A, B, C}及其数量为{10, 5, 7}，在T0时刻的资源分配如下： 资 源 进 情 况 程 Max A B C Allocation Need Available P0 P1 P2 P3 P4 7 5 3 3 2 2 9 0 2 2 2 2 4 3 3 0 1 0 2 0 0 3 0 2 2 1 1 0 0 2 7 2 5 7 4 3 1 2 2 6 0 0 0 1 1 4 3 1 3 3 2

(1)利用银行家算法计算T0时刻的安全性 P0 P1 P2 P3 P4 0 1 0 2 0 0 3 0 2 2 1 1 0 0 2 资源 情况 进程 work A B C Allocation Need A B C Work+ Allocation Finish P0 P1 P2 P3 P4 0 1 0 2 0 0 3 0 2 2 1 1 0 0 2 7 4 3 1 2 2 6 0 0 0 1 1 4 3 1 3 3 2 true 10 4 7 10 5 7 3 3 2 5 3 2 true 7 4 5 10 4 7 true 5 3 4 7 4 5 true 5 3 2 5 3 4 true 在系统中存在有安全序列{P1, P4, P3 , P2 , P0}

(2)P1发出请求资源Request1(1, 0, 2) ①Request1(1, 0, 2)≤Need1(1, 2, 2) ②Request1(1, 0, 2)≤Availabe(3, 3, 2) ③假定系统先为P1分配资源，并修改相关向量后的资源分配如下： 资 源 进 情 况 程 Max A B C Allocation Need Available P0 P1 P2 P3 P4 7 5 3 3 2 2 9 0 2 2 2 2 4 3 3 0 1 0 3 0 2 2 1 1 0 0 2 8 2 7 7 4 3 0 2 0 6 0 0 0 1 1 4 3 1 2 3 0

在系统中存在有安全序列{P1, P4, P3 , P2 , P0}，因此系统是安全的，故可以将P1所申请的资源分配给它。 ④利用银行家算法计算此时刻的安全性 资源 情况 进程 work A B C Allocation Need Work+ Allocation Finish P0 P1 P2 P3 P4 0 1 0 3 0 2 2 1 1 0 0 2 7 4 3 0 2 0 6 0 0 0 1 1 4 3 1 2 3 0 10 4 7 10 5 7 true 3 3 2 5 3 2 true 7 4 5 10 4 7 true 7 4 5 true 5 3 4 5 3 2 5 3 4 true 在系统中存在有安全序列{P1, P4, P3 , P2 , P0}，因此系统是安全的，故可以将P1所申请的资源分配给它。

(3)若此时P4又发出请求资源Request4(3, 3, 0) ①Request4(3, 3, 0)≤Need4(4, 3, 1) ②Request4(3, 3, 0)≤Availabe(2, 3, 0) 让P4等待。 (4)若此时P0又发出请求资源Request0(0, 2, 0) ①Request0(0, 2, 0)≤Need0(7, 4, 3) ②Request0(0, 2, 0)≤Availabe(2, 3, 0) ③假定系统为P0分配资源，并修改相关向量后的资源分配如下

资 源 进 情 况 程 Max A B C Allocation Need Available P0 P1 P2 P3 P4 7 5 3 3 2 2 9 0 2 2 2 2 4 3 3 0 3 0 3 0 2 2 1 1 0 0 2 8 4 7 7 2 3 0 2 0 6 0 0 0 1 1 4 3 1 2 1 0 ④利用银行家算法计算此时刻的安全性 Availabe(2, 1, 0)≤Need0(7, 2, 3), Availabe(2, 1, 0)≤Need1(0, 2, 0) Availabe(2, 1, 0)≤Need2(6, 0, 0), Availabe(2, 1, 0)≤Need3(0, 1, 1) Availabe(2,1, 0)≤Need4(4, 3, 1), 系统进入不安全状态，不分配。

3.7 死锁的检测与解除 3.7.1 死锁的检测 当系统为进程分配资源时，未采用任何限制性条件来保证系统不进入死锁状态，则系统必须提供检测和解除死锁的手段。为此系统必须： (1)保存有关资源的请求和分配信息； (2)提供一种算法，以利用这些信息来检测系统是否已进入死锁状态。 检测时机： ◆当进程等待时检测死锁 （其缺点是系统的开销大） ◆定时检测 ◆系统资源利用率下降时检测死锁

系统死锁可以利用资源分配图来描述。该图是由一组结点N和一组边E所组成的一对偶 G=(N，E)，具有下述形式的定义和限制： 一、资源分配图 系统死锁可以利用资源分配图来描述。该图是由一组结点N和一组边E所组成的一对偶 G=(N，E)，具有下述形式的定义和限制： 1.N被分为两个互斥的子集，一组进程结点P={p1,p2,…,pn}，一组资源结点R={r1,r2,…,rn}，N=P∪R。 2.凡属于E中的一个边e∈E，都连接着P中的一个结点和R中的一个结点。 e=(pi , rj), 是资源请求边，由进程pi指资源rj，表示进程pi请求一个单位的资源rj 。 e=(rj , pi), 是资源分配边，由资源rj指进程pi，表示分配一个单位的资源rj给进程pi。 我们用“○”代表一个进程，用“□”代表一类资源，由于一类资源可能较多，用方框中的“●”代表一个资源。

资源分配图在系统中是随时间变化的。当进程Pi请求rj 时，将一条请求边(Pi , rj)加在图中。若此请求被满足(分给Pi 一个rj 类的资源)，则将这个请求边改成分配边(rj , Pi)。当进程Pi 释放一个 rj 时，便去掉分配边(rj , Pi)。 例：系统有两台宽行打印机和一台图形显示器，进 程P1请求一台宽打则有(图a)的资源分配图。 进程P1分配到一台宽打，并请求一台图形显示器，进程P2已分到一台图显，并请求一台宽打，则其分配图见(图b)。 P1 P2 · · · r1 r2 (P1, r2) (P2, r1) (r2, P2) (r1, P1) (图b) P1 · · · (P1, r1) r2图显 r1宽打 (图a)

1.如果资源分配图中没有环路，则系统中没有死锁，如果图中存在环路则系统中可能存在死锁。 二、死锁定理 1.如果资源分配图中没有环路，则系统中没有死锁，如果图中存在环路则系统中可能存在死锁。 2.如果每个资源类中只包含一个资源实例，则环路是死锁存在的充分必要条件. 有环有死锁 有环无死锁

死锁定理：系统处于S状态为死锁状态的充分条件是：当且仅当S状态资源分配图是不可完全简化的。 资源分配图的化简步骤： ★在图中找一个进程顶点Pi，Pi的请求边均能立即满足。 ☆若找到了这样的Pi， 则将与Pi相连的边(包括分配边) 全部删去；若无请求边的Pi，则删去其所有的分配边；再把相应的资源分配给一个等待该资源的进程，即将某进程的申请边变为分配边，转★ 。否则化简结束。 如果化简后所有进程顶点都为孤立点，对称该图为可完全化简图 ，否则称之为不可完全化简的。

(图a)可完全化简 (图b)不可完全化简 P1 P3 P2 P4 · P1 P3 P2 P4 · · P1 P3 P2 P4 P1 P2

三、 死锁检测中的数据结构 (1) 可利用资源向量Available，它表示了m类资源中每一类资源的可用数目。 (2) 把不占用资源的进程(向量Allocation∶=0)记入L表中， 即Li∪L。 (3) 从进程集合中找到一个Requesti≤Work的进程，做如下处理：① 将其资源分配图简化，释放出资源，增加工作向量Work∶=Work+Allocationi。 ② 将它记入L表中。

(4) 若不能把所有进程都记入L表中，表明系统状态S的资源分配图是不可完全简化的。因此该系统状态将发生死锁。 Work ∶=Available; L∶={Li|Allocationi=0∩Requesti=0} for all Li  L do begin for all Requesti≤Work do Work∶=Work+Allocationi; Li∪L; end deadlock∶ = (L={p1, p2, …, pn});

3.7.2 死锁的解除 ––– 前提是能检测出死锁 一旦发现死锁及时排除，是有关排除死锁的研究。当前系统中使用的死锁恢复办法有两种：(撤消进程，剥夺资源) (1)强制性地从系统中撤消进程，并剥夺它们的资源给剩下的进程使用。(使前面的工作全部损失) (2)使用一个有效的挂起和解挂机构来挂起一些进程。其实质是从被挂起的进程那里剥夺资源以解除死锁。(即可从死锁中恢复，又使进程的损失最小) 此外，还有(3)重新启动和(4)进程回退等。重要的 是以最小的代价恢复系统的运行。

图 3-21 付出代价最小的死锁解除方法