ch6

F
U
V
U
V
W
G (a)
G (b)

单资源类型的死锁检测

(a) 资源图 (b) 从(a)中抽取的环路
19

如果图中有环，说明系统中有死锁
单资源类型的死锁检测

该算法的执行步骤如下：
1.
2.
3.
4.
5.
6.
对于图中的每个节点N，以N作为起点执行下面5个 步骤。 初始化L为空表，并清除所有弧线的标记。 LL+{N}，并检测N是否在L中已出现2次。如果 是，那么该图包含了一个环路(在L中)，算法结束。 从N为始点的有向边，是否有未被标记的。如果有， 执行步骤5；如果没有，转到步骤6。 随机选取一条有向边，标记它。N此边的另一个 节点，转到步骤3。 NN的前一节点，即当前节点的前面一个节点， 如果该节点为起始节点，则表明该图不存在任何 环路，算法结束。否则转步骤3。

例如，如果类1为磁带驱动器，则El = 2表示 系统有两台磁带驱动器。
22
多资源类型的死锁检测


在任一时刻，某些资源已被指派而不可 用。 令A为可用资源向量(available resource vector)，Ai表示资源类i当前可供使用的 (即尚未分配的)实例数目。

如果两台磁带驱动器都被指派了，则A1 = 0。
15
鸵鸟算法(Ostrich Algorithm)

视而不见 理由：

死锁极少发生 预防死锁的代价太高

UNIX和Windows采用这方法 这是方便性与正确性的平衡
16
死锁检测和恢复

当使用该技术时，系统并不试图阻止死 锁的发生，相反，它允许死锁发生，当 死锁发生时尝试去检测它，然后采取某 些行动来进行恢复。
4
资源获得


对于某些类型的资源，完全是由用户进 程来管理其自身的使用。由用户管理资 源的一种可能方法是给每个资源赋予一 个信号量。这些信号量的初值均为1。 其执行过的三步为：获取资源时对信号 量执行down操作，然后使用资源，最后 释放资源时执行up操作。
5
资源获得—一个用户
typedef int semaphore; semaphore resource_1; void process_A(void) { down(&resource _1); use_resource_1( ); up(&resource _1); } typedef int semaphore; semaphore resource_1; semaphore resource_2; void process_A(void) { down(&resource _1); down(&resource _2); use_both_resources( ); up(&resource _2); up(&resource _1); } (b)
(a)

使用信号量保护资源


(a) 一个资源 (b) 两个资源
6
资源获得—两个用户


在下图 (a)中，某个进程将先于另一个获得第 一个资源。接着，该进程将成功地获得第二个 资源，并且完成其工作。如果另一个进程试图 在其释放前获取资源1，该进程将被简单地阻 塞，直到资源可用。 在下图 (b)中，情况就不同了。可能会发生一 个进程获取两个资源，并且有效地阻塞另一个 进程直到它结束。但是，同样也可能发生： 进程A获得资源1，请求资源2 进程B获得资源2，请求资源1。 每个进程都会在它试图获取另一个资源时被阻 塞。两个进程都无法继续运行。这种情形就是 一种死锁。 7
R
S (n)
T
A
B
C
A
B
C
A
B
C
R
S
T
R
S
T
R
S
T
(o)
(p)
(q)

死锁的避免
14
死锁模型
总而言之，处理死锁有以下四种策略： 1. 忽略该问题。

也许你忽视它，它也会忽视你。
2.

检测并恢复。
允许死锁发生，然后检测它们，再采取行 动。
3. 4.
通过仔细地资源分配来动态地避免死锁。 通过在结构上破坏死锁的四个必要条件 之一来预防死锁。
第六章 死锁



资源 死锁简介 鸵鸟算法 死锁检测和恢复 死锁避免 死锁预防 其他问题
1
资源(resource)



当进程获得对设备、文件等对象的独占访问权 时，有可能会发生死锁。为了尽可能地使死锁 的讨论一般化，我们把已授权的对象称为资源 (resource)。资源可以是硬件(如磁带驱动器)， 或者是一些信息(如数据库中加锁的记录)。 对于某些资源可能会有几个相同的实例。 当某个资源有几个拷贝时，其中任何一个都可 以用于满足对该资源的请求。 简单的说，资源就是在任何时候都只能被一个 进程使用的任何对象。
25
多资源类型的死锁检测

这四种数据结构之间有一个重要的恒等 式。
C
i 1
n
ij
Aj E j
26
多资源类型的死锁检测

死锁检测算法可以按下列步骤进行：



寻找一个尚未标记的进程Pi，且(Ri1, Ri2, …., Rim) 小于等于A。 AA+ (Ci1, Ci2, …., Cim) ， 并标记Pi，转步 骤1。 如果没有这样的进程存在，则算法终止。
R
S (e) B
T
R
S (f)
T
R
S (g)
T
C
A
B
C
A
B
C
R
S (h)
T
R
S (i)
T
R
S
T
(j)

死锁的产生
13
死锁模型
A 1. A请求R 2. C请求T 3. A请求S 4. C请求R 5. A释放R 6. A释放S 不死锁 (k) B C A B C A B C
R
S (l)
T
R
S (m)
T
11
死锁模型
A S D T U
R (a)
B (b)
C (c)

资源分配图


(a) 资源R被指派给进程A (b) 进程B请求/等待资源S (c) 进程C和D死锁
12
死锁模型
A 请求R 请求S 释放R 释放S (a) A B C A B 请求S 请求T 释放S 释放T (b) B C A C 请求T 请求R 释放T 释放R (c) B C 1. 2. 3. 4. 5. 6. A请求R B请求S C请求T A请求S B请求T C请求R 死锁 (d) A
(a) 无死锁代码 (b) 具有潜在死锁的代码
8
死锁简介

死锁可以正式地定义如下：

如果在一个进程集合中的每个进程都在等待 只能由该集合中的另一个进程引发的事件， 该组进程就被死锁。


在大多数情形下，进程都是在等待该集 合中另一个成员将目前占有的资源释放。 死锁的进程都不能

运行 释放资源 被唤醒

算法结束时，所有尚未标记的进程(如果 ቤተ መጻሕፍቲ ባይዱ的话)都已死锁。
27
多资源类型的死锁检测
磁 磁 带 驱 绘 动器 图 仪 扫 描 仪 CD Ro ms
1 0 0 ) 请求矩阵 2 1 2 0 0 1 0 1 0 1 0 0
28
E = ( 4
绘
动 图 器 仪 扫 描 仪 CD Ro ms
2 3 1 )
带
驱
17
单资源类型的死锁检测


从最简单的例子开始：即每种类型只存 在一个资源。 对于这样的系统，可以构造一个资源图， 如果这张图包含了一个或多个的环路， 那么就存在死锁。该环路中任何进程都 被死锁。如果不存在环路，系统就不会 死锁。
18
单资源类型的死锁检测
R A B C S D T E D R E
24
多资源类型的死锁检测
死锁检测所需的数据结构 (a) 所有资源 (E1, E2, E3, …, Em) (b) 可用资源 (A1, A2, A3, …, Am) (c) 当前分配矩阵 (d) 请求矩阵
C11 C12 C 21 C22 Cn1 Cn 2 C13 C23 Cn 3 C1m C2 m Cnm R11 R 21 Rn1 R12 R22 Rn 2 R13 R23 Rn 3 R1m R2 m Rnm
23
多资源类型的死锁检测


另外还有两个数组。C为当前分配矩阵 (current allocation matrix)，R为请求矩 阵(request matrix)。 C的第i行表示进程Pi当前占有每一类资源 的数目。因此，Cij表示进程i所占有的资 源j的数量。类似的，Rij代表Pi申请的资 源j的数量。
20
单资源类型的死锁检测

该算法的原理： 将图中每个节点作为一棵树的根节点， 作深度优先遍历，如果返回到已遍历的 节点，说明有环存在。
21
多资源类型的死锁检测


使用基于矩阵的算法来检测n个进程(从P1 到Pn)中的死锁。假设资源类为m，E1表 示资源类1，E2表示资源类2，Ei表示资源 类i (1<i<m)。 E为现有资源向量(existing resource vector)，它表示每类资源的总数。
A = ( 2
当前分配矩阵 0 2 0 0 0 1 1 0 2 0 1 0