第3章 进程同步与通信 第8课时 死锁的避免《操作系统原理课件（第2版）》 同步教学（电子工业出版社）

操作系统原理(第2版） 3.8.3 死锁的避免 死锁的避免（DeadLock Avoidance）是在不改变资源的固有性质的前提下，对资源的分配策略施加较少的限制条件来避免死锁的发生。 死锁的避免对资源的分配策略施加了较少限制条件，即对资源的申请和分配策略基本不做改变，只是在每次分配资源时做个例行检查，然后根据检查的结果决定是否分配资源。 死锁的避免就是在动态检查前提下动态的分配资源，通过检查来阻止会导致进程进入死锁状态的资源分配，从而避免死锁的发生。 3.8 死锁 1. 系统的安全状态和不安全状态 从资源的角度和死锁的角度来看系统的安全状态与不安全状态： （1）资源角度。从当前状态出发，如果操作系统能够给出一个方案，使得系统的所有进程都能在有限的时间内得到其宣称所要的全部资源（建立在预先知道全部资源需求这一假设前提上），那么当前状态是系统的一个安全状态。反之，若从当前状态出发，操作系统的所有调度方案都无法使所有进程能够在有限时间内得到所需的全部资源，则当前状态是系统的一个不安全状态。 3.8 死锁 （2）死锁角度。死锁状态必定是不安全状态，但非死锁状态也不一定安全。 安全状态是指在某一时刻，系统中存在一个包含所有进程的进程序列（P1，P2，…，Pn），按照该进程序列的顺序为所有进程分配资源，则所有进程的资源需求都可以得到满足；所有进程都可以顺利完成，称此时系统的状态为安全状态，并称这样的进程序列为安全序列。反之，如果在某时刻系统中找不到进程的一个安全序列，则称此时系统处于不安全状态。 3.8 死锁 例：假设系统有10台打印机，有3个进程P1、P2和P3在并发执行，进程P1总共需要8台打印机，进程P2总共需要5台打印机，进程P3总共需要9台打印机。在T时刻，P1、P2和P3已分别获得了4台、2台和1台打印机，系统尚有3台打印机空闲。打印机的分配情况如下表所示。 3.8 死锁 进程 最大需求 已分配 空闲 P1 8 4 3 P2 5 2 P3 9 1 2. 使用银行家算法避免死锁 采用银行家向客户贷款时怎样保证资金安全的方法。 例如，一个银行家拥有1亿资金，有10家工厂筹建且每家工厂需要2000万元方可建成。如果将这1亿资金平均借贷给这10家工厂，则每个工厂都将无法建成也就不能还贷，即这10家工厂都将处于“死锁”状态。如果借贷给其中的3家工厂各2000万，借贷给另外4家工厂各1000万；这样，虽然还有3家工厂没有开工建设，但有3家工厂可以建成投产和4家工厂在建设中，那么这投产的3家工厂生产所获得的利润可以给银行还贷，银行家再利用还贷的资金继续给其余工厂投入，直至最终这10家工厂都建成投产。 3.8 死锁 假设系统存在m类资源，有n个进程在并发执行，使用银行家算法来避免死锁需要设置以下数据结构： （1）系统可用资源向量Available。一个具有m个数组元素的一维数组，每个数组元素代表一类资源当前可用（空闲）的数量，初始值为系统中该类资源的总量。例如，若Available[i]＝k，则表示系统第i类资源现有k个空闲。 （2）最大需求矩阵Max。一个n×m矩阵，定义了系统中所有n个进程对m类资源的最大需求量。例如，若Max[i][j]＝k，则表示第i号进程在运行过程中总共需要k个第j类资源。 （3）分配矩阵Allocation。一个n×m矩阵，表示系统中的所有n个进程当前已获得各类资源的数量。例如，若Allocation[i][j]＝k，则表示第i号进程当前已获得k个第j类资源。 3.8 死锁 （4）需求矩阵Need。一个n×m矩阵，表示系统中的所有n个进程当前还需要各类资源的数量。例如，若Need[i][j]＝k，则表示第i号进程当前还需要k个第j类资源。 上述3个矩阵存在如下关系： Need[i][j]＝Max[i][j]－Allocation[i][j] （i=1, 2, …, n; j=1, 2, …, m） （5）请求向量Request。一个具有m个数组元素的一维数组，每个数组元素代表当前正在运行的进程i（i=1, 2, …, n）此时请求某类资源的数量。例如，若Request[j]=k，则表示当前运行进程i正请求k个第j类资源。 3.8 死锁 3. 银行家算法 当进程i向系统提出k个j类资源请求时，系统按下述步骤进行检查： （1）若Request[j]≤Need[i][j]，转步骤（2）；否则认为出错，因为进程i申请的j类资源已经超出它宣称的最大资源请求。 （2）若Request[j]