4.2.3
避免死锁
银行家算法实例:(P126-128）
补充例题：见WORD文件“死锁试题”
4.2.4 检测和解除死锁
一、RAG图
二、死锁定理
三、利用RAG图化简法判断死锁的实例
4.2 死锁
4.2.1 死锁的概念 4.2.2 预防死锁 4.2.3 避免死锁 4.2.4 检测和解除死锁ຫໍສະໝຸດ .2.1 死锁的概念一、死锁
多个进程因竞争资源而造成的一种僵局， 若无外力作用，这些进程都无法向前推进。 二、产生死锁的原因
1.竞争 非剥夺性资源。
2.进程间推进顺序非法。
4.2.1 死锁的概念
4.2.3
避免死锁
避免死锁:它允许三个必要条件，但通过明智的 选择，确保永远不会到达死锁点，因此避免比预 防允许更多的并发; 思想:系统在进行资源分配之前，应先计算此 次资源分配后状态的安全性。若此次分配后的状 态是安全状态，则将资源分配给进程；否则，令 进程等待。 避免死锁的算法：银行家算法
安全状态 银行家算法
4.2.3
避免死锁
安全状态:所谓安全状态，是指系统能按某种进程 顺序(P1, P2, …，Pn)(称〈P1, P2, …, Pn〉序 列为安全序列)，来为每个进程Pi分配其所需资源， 直至满足每个进程对资源的最大需求，使每个进程 都可顺利地完成。如果系统无法找到这样一个安全 序列，则称系统处于不安全状态。
可能出现反复申请、释放资源而被无限延迟执行的现象；
4.2.2 预防死锁
三、破坏“环路等待条件”---有序资源分配法
1.思想： 资源编号； 进程以递增顺序申请资源； 2.缺点： 资源编号难以确定； 后用的资源先申请，资源利用率低； 限制编程的独立性；
结论：
在预防死锁中，通过破坏产生死锁的必要条件，排除 发生死锁的可能性，但都会导致低效的资源使用率和低效 的进程执行。
三、产生死锁的必要条件
1.互斥条件
2.请求和保持条件 3.不剥夺条件 4.环路等待条件
4.2.1 死锁的概念
四、处理死锁的基本方法
1.预防死锁：通过破坏产生死锁的四个必要条件之一
2.避免死锁：不破坏死锁产生的四个必要条件，在资 源的动态分配中，防止进程进入可能发生死锁的不安 全状态。 3.检测死锁 4.解除死锁 允许系统出现死锁，但系统设臵了检测机制， 及时检测出死锁；检测出死锁后，系统将采取措施 解除死锁。
Finish [ i] ＝ true
y
返回安全状态
返回不安全状态
4.2.3
三、银行家算法
避免死锁
设进程i申请资源，表示为：Request i
1. 2. 3.
4.
若request i ≤ need i，转2，否则出错。 若request i ≤ Available，转3，否则进程阻塞。 试分配： Available =Available-Request i Allocation i= Allocation i+Request i Need i=Need i-Request i 调用安全检查算法 若为安全状态，则正式分配 若为不安全状态，则不分配，进程i阻塞。恢复系统状态
4.2.2 预防死锁
---静态资源分配法 一、破坏“请求和保持条件” 1.思想：资源调度时，若资源全满足，则调度，否则等待。 2.缺点： 资源浪费；
进程延迟运行，降低进程的并发性；
二、破坏“不剥夺条件”
1.思想：进程新申请资源得不到满足时,必须释放已占有资源 2.缺点： 保存放弃资源时的现场及以后的现场恢复；
4.2.3
安全状态之例：
进 程 最大需求
避免死锁
已分配
尚需
可用
P1 P2 P3
10 4 9
5 2 2
5 2
3
7
该状态安全性： 安全 ，安全序列P2、 P1、 P3 若此时，P3请求一台磁带机，能否分配？
不能，因为分配后状态不安全
4.2.3
避免死锁
一、银行家算法中的数据结构 设系统中有n个进程，提供m类资源： 1.Available[m]:可利用资源向量。
Available［j］=K，则表示系统中现有Rj类资源K 个，初值是系统中所配臵的该类全部可用资源的数目。
2.Max[n][m]:最大需求矩阵。
3.Allocation [n][m]:分配矩阵。
4.Need[n][m]:需求矩阵。
Need［i][j］=Max［i][j］-Allocation［i][j］
二、安全性算法
2.安全性检测
4.2.3
避 免 死 锁
Work＝Available Finish 根据Need赋值
寻找进程i，满足 Finish [ i]＝ false 且Need i<=work 找到
没找到
n
所有进程的 Finish [ i] ＝ true？
Work=work+Allocation i
4.2.3
二、安全性算法 1.设臵两个向量：
避免死锁
(1) 工作向量 Work[m]: 它表示系统可提供 给进程继续运行所需的各类资源数目， Work初∶=Available; (2) Finish[n]: 它表示系统是否有足够的资 源分配给进程，使之运行完成。 false表示 未完成， true表示完成。