5.2.5 预防死锁
解决死锁问题的基本方法有：预防死锁、避免死 锁、检测死锁和解除死锁。除此之外还有鸵鸟算 法和综合措施。 预防死锁是指通过某种策略来限制并发进程对资 源的请求，使系统在任何时刻都不满足死锁的必 要条件。 就是在设计操作系统时，通过设置某些限制条件， 去破坏死锁四个必要条件中的一个或多个，来防 止死锁，使系统能预先排除死锁的可能性。
8
5.2.2 资源分配图
该图是由一组结点V和一组边E所组成的： G=（V，E），具有以下形式的定义和限 制： （1）V被分为两个互斥的子集，一组进 程结点P={p1,p2,…,pn},一组资源结点 R={r1,r2,…rn},
r1
P1
r2
P2
(2) 凡属于E中的一个边e∈E，都连接着P中的一个结点和 R中的一个结点，e={pi, rj}是资源请求边，由进程pi指向 资源rj， 它表示进程pi请求一个单位的rj资源。e={rj, pi}是 资源分配边，由资源rj指向进程pi, 它表示把一个单位的资 源rj分配给进程pi。
P2
图 5-1 进程之间通信时的死锁
7
死锁的定义:死锁是一组并发进程,它们共享系统 的某些资源,该组进程中每个进程都已经占有了 部分资源,但都在不释放自己占有资源的情况下 要求获得被其它进程已经占有的资源,从而造成 它们相互等待,永远不能继续推进的状态. 说明： ①参与死锁的进程最少是两个（两个以上进程才 会出现死锁）。 ②参与死锁的进程至少有两个已经占有资源。 ③参与死锁的所有进程都在等待事件。 ④参与死锁的进程是当前系统中所有进程的子集。
25
⒋银行家算法之例
如表5-4所示T0时刻的资源分配表，假定系统中有 五个进程{P0，P1，P2，P3，P4}和三种类型的资 源{A，B，C}，每一种资源的数量分别为10、5、7。
26
如表5-5所示，对T0时刻进行安全性检查，可以找到一
个安全序列{P1，P3，P4，P2，P0}，系统是安全的。
2、资源信息块
资源信息块：描述某类资源的请求者、可利用的资 源以及该类资源分配程序的地址的数据结构。
4
5.1.4 资源分配策略
1、先请求先服务（FIFO）
先请求先服务是一种最简单的资源分配策略，可用 于对进程或作业的调度，也可用于对外部设备、主 存储区的分配。
2、优先调度
优先调度策略调度是一种比较灵活的调度策略。进 程调度队列按进程的优先级由高到低的顺序排列。
22
④系统执行安全性算法，检查此次资源分配后， 系统是否处于安全状态。若安全，才正式将资 源分配给进程Pi，以完成本次分配；否则，将 试探分配作废，恢复原来的资源分配状态，让 进程Pi等待。
23
⒊安全性算法 系统所执行的安全性算法可描述如下： ①设置两个工作向量，工作向量Work。它含有m 个元素，它表示系统可提供给进程继续运行所 需要的各类资源数目，初值Work=Available。 完成标志工作向量Finish。它含有n个元素，它 表示系统是否有足够的资源分配给进程，使之 运行完成，当有足够资源分配给进程时， Finish[i]=true，初值Finish[i]=false。 ②从进程集合中找到一个能满足下述条件的进 程： Finish[i]=false； Needi<=Work； 如找到，执行步骤③；否则，执行步骤④。 24
18
进程 P1
P2
最大需求 10
4
已分配 5
2
可用磁带机 3
P3
9
2
经分析，在T0时刻系统是安全的，因为存在一 个安全序列<p2,p1,p3> 向不安全状态的转换 若在T0时刻以后，p3请求1台磁带机，若满足 其要求，则系统进入不安全状态。
19
三、银行家算法避免死锁
⒈银行家算法中的数据结构 ①可利用资源向量Available(R1,R2„Rm)。它 是一个含有m个元素的数组，其中的每一个元素 代表一类可利用的资源数目，其初始值是系统 中所配置的该类全部可用资源数目。其数值随 该类资源的分配和回收而动态地改变。 ②最大需求矩阵Max。这是—个n×m的矩阵，它 定义了系统中n个进程中的每一个进程对m类资 源的最大需求。如果Max[i，j]＝k，表示进程 Pi需要Rj类资源的最大数目为k。 ③分配矩阵Allocation。这是一个n×m的矩阵， 它定义了系统中每一类资源当前已分配给每个 进程的资源数。如果Allocation[i，j]＝k，表 示进程Pi当前已分得Rj类资源的数目为k。
12
5.2.6 解决死锁问题的策略
1、条件1（互斥条件） 互斥条件是由于设备本身特性所决定的,不 能简单的把其打破;只有通过改造设备特性 实现.具体办法采用Spooling技术,把独占设 备改造成共享设备来实现.
13
2、条件2（不可剥夺条件） 为了破坏不可剥夺条件，我们采用这样的策 略，一个已拥有资源的进程，若它再提出新 资源要求而不能立即得到满足时，它必须释 放已经拥有的所有资源，以后需要时再重新 申请。拥有资源的进程在运行过程中其资源 可能被剥夺，从而破坏了不可剥夺条件。 该方法实现复杂，被剥夺资源的进程前期工 作失效，重复申请和释放资源给系统增加了 开销，系统要付出很大的代价。
27
⑴P1发出请求Request(1，0，2)，执行银行家算法。 如表5-6所示，进行安全性检查，通过第一步和第二 步检查，并找到一个安全序列{P1，P3，P4，P2， P0}，系统是安全的，可以分配P1的请求。
28
29
⑵P4发出请求Request(3，3，0)，执行银行家算法。 Available=(2，3，0)，不能通过第二步检查 （Request[i]≤Available），所以P4等待。 ⑶P0请求资源，Request（0，2，0），执行银行家算法。 进行安全性检查，通过第一步和第二步检查，如表5-7 所示，Available{2，1，0}已不能满足任何进程需要， 所以系统进入不安全状态，P0的请求不能分配。
14
3、条件3（占有并等待） 采用设备的静态预先分配办法,具体做法:作业调度 程序在选择作业时,只选择那些系统能满足其运行时 所需的全部资源的作业投入运行,并且在作业运行前, 将其所需的全部资源一次性地分配给该作业. 该方法的优点和缺点如下： ①简单、安全、易于实现。 ②程序在运行之前很难提出将要使用的全部设备。 ③直到所有资源满足才能运行，实际上某些资源可 能要到运行后期才会用到。 ④一个进程运行期间，对某些设备的使用时间很短， 甚至不会用到。 ⑤作业的周转时间被加长,系统资源的使用率被降低
可消耗资源(consumable resource):是指可以动态生成
和动态消耗的资源，一般不限制数量，如中断、信号量、消息、 缓冲区等都是可消耗资源。由于可消耗资源的生成和消耗存在 依赖关系，因此他们的使用也可能因为双方都等待对方生成资 源而形成死锁。(如图5-1所示）
6
P1 S3 S1
P3 S2
16
5.2.7 避免死锁
死锁的避免是动态的预防措施,系统允许进程动 态地申请资源,如果措施得当,可以使系统获得较 为满意的系统性能. 具体的办法是:系统为进程分配资源之前,首先对 系统的安全性进行计算,如果为进程分配了所需 资源后,系统仍处于安全状态,那么就把资源分配 给该进程,反之则不为该进程分配资源. 银行家算法:该问题是研究一个银行家如何将其 总数一定的现金,安全的借给若干个顾客,使这些 顾客既能满足对资金的要求又能完成其交易,也 使银行家可以收回自己的资金不至于破产.
（2）确定资源的分配策略 （3）执行资源分配 （4）存取控制和安全保护
2
5.1.2 虚拟资源
虚拟资源：用户使用的逻辑资源，是操作系统将
物理资源改造后，呈现给用户的可供使用的资源。
目的：一是提高资源的利用率；二是为了方便用
户的使用。
3
5.1.3 资源分配机制
1、资源描述器
资源描述器：描述各类资源的最小分配单位的数据 结构。
3、针对设备特性的调度
（1）移臂调度 （2）旋转调度
5
5.2 死锁及其解决方法 5.2.1 死锁的定义
可重用资源(reusable resource):各个进程可以轮流使
用，如处理机、内存、I/0外设、文件等都是可重用资源，在 使用可重用资源时可能出现的死锁（Deadlock）。通常是由于 各进程巳拥有部分资源，同时请求其他进程已占有的资源，从 而造成永远等待。
第5章 操作系统的资源管理
5.1 资源管理的机制和策略 5.1.1 资源管理任务
1、资源的静态分配和动态分配 ◆静态分配: 在作业运行前，将所需的资源一次
性的分配给它，在作业运行完毕后释放所获得的 全部资源。
Hale Waihona Puke ◆动态分配：在进程运行过程中根据情况动态地
分配、使用和释放资源。
1
2、资源管理的任务
（1）资源数据结构的描述
17
一、系统的安全状态和不安全状态 安全状态:是指系统能按某种进程推进顺序 (p1,p2,„pn),来为每个进程分配其所需资源, 直至最大需求,使每个进程都能顺利完成其任 务.只要系统存在这样的安全序列 <p1,p2,„pn>,则系统处于安全状态. 二、安全状态的例子 假定系统有三个进程p1,p2和p3,共有12台磁 带机,进程p1、p2、p3分别要求10台、4台和9 台，设在T0时刻p1、p2、p3已分别获得5台、 2台和2台，尚有3台空闲磁带机未分配出去， 分配情况如下所示：
20
