一个系统中要发生死锁,必须同时满足以下四个必要条件。只要能破坏其中任意一个,死锁就不会发生。
互斥使用 (Mutual Exclusion)
占有且等待 (Hold and Wait)
不可抢占 (No Preemption)
循环等待 (Circular Wait)
为了更直观地描述和分析死锁,我们引入了资源分配图。
RAG是一个有向图 ,包含两类节点:
图中包含两类有向边:
下面是一些RAG的例子,我们可以用Mermaid流程图来表示它们。
十字路口的四个区域可以看作四个资源,四辆车看作四个进程。每辆车都占用了自己当前的路口,同时又想进入前方的路口。
graph TD
P1(P1) --> Ra[Ra]
P2(P2) --> Rb[Rb]
P3(P3) --> Rc[Rc]
P4(P4) --> Rd[Rd]
Ra --> P2
Rb --> P3
Rc --> P4
Rd --> P1
mermaid这就形成了一个 P1 -> R_a -> P2 -> R_b -> P3 -> R_c -> P4 -> R_d -> P1
的循环等待,导致死锁。
RAG和死锁之间存在一个重要的关系,我们称之为死锁定理:
为什么有环路却”可能”没有死锁呢?这通常用来阐明在每类资源拥有多个实例的情况下,环路是死锁的必要不充分条件。看下面这个例子。
graph TD
R1["R1 (2)"]
R2["R2 (2)"]
P1(P1)
P2(P2)
P3(P3)
P4(P4)
R2 --"持有"--> P1
R1 --"持有"--> P2
R1 --"持有"--> P3
R2 --"持有"--> P4
P1 --"请求"--> R1
P3 --"请求"--> R2
mermaid在这个图中,存在环路 P1 → R1 → P3 → R2 → P1
。
虽然图中存在一个 P1 → R1 → P3 → R2 → P1
的循环等待,但我们可以通过一个简单的推演 (这其实就是资源图化简法的思路) 发现,系统仍然可以找到一个让所有进程都完成的执行序列,因此没有死锁:
我们观察到进程 P2
和 P4
。它们虽然持有资源,但没有请求任何新资源 (即没有从它们出发的指向资源框的请求边) 。这意味着它们不处于等待状态,可以顺利执行完毕并释放资源。
P2 (或 P4) 先完成:假设 P2
先执行完毕,它会释放它持有的1个 R1
资源实例。
R1
资源变为1个 (Available R1 = 1
)。P1的请求被满足:P1
一直在等待 R1
。现在系统有可用的 R1
了,于是就可以把这个 R1
实例分配给 P1
。
P1
获得了所需的全部资源 (它原来持有的R2
和新获得的R1
) ,可以继续执行直到完成。僵局被打破。P1完成并释放资源:P1
完成后,会释放它持有的所有资源:1个 R1
实例和1个 R2
实例。
其他进程相继完成:P1
释放的 R2
可以满足 P3
的请求,P3
也能完成。P4
本来就可以自己完成。最终,所有进程都能顺利结束。
因为存在一个可以让所有进程都完成的执行序列 (例如 <P2, P1, P4, P3>
) ,所以系统没有发生死锁。这个例子完美地说明了:当每个资源类有多个实例时,资源分配图中存在环路是死锁的必要条件,但不是充分条件。
我们可以通过一种称为”图化简”的方法来检测死锁。基本思想是:模拟系统资源的分配和释放过程,看看是否能满足所有进程的需求。
化简步骤:
结论: 如果最终图中所有的进程都被化简掉 (成为孤立节点) ,则称该图是可完全化简的,系统没有死锁。反之,如果最后还剩下无法化简的进程节点,则系统存在死锁。
面对死锁,主要有四大类处理策略:
这是最直接的思路,即破坏四个必要条件中的一个。
死锁避免不像预防那样施加严格的限制,而是更加灵活。它允许前三个条件的存在,但在分配资源时会小心翼翼,确保不会踏入死胡同。这里的核心概念是安全状态。
$<P_1, P_2, ..., P_n>$
是安全的,指的是对于序列中的每一个进程 ,它未来所需要的最大资源量,可以被系统当前剩余的资源加上所有排在它前面的进程 () 所持有的资源所满足。状态关系:
graph TD
A[系统状态] --> B(安全状态)
A --> C(不安全状态)
C --> D(死锁状态)
mermaid就是资源分配图化简法,但是考虑了进程的最大需求。
这是由Dijkstra提出的最著名的死锁避免算法。它模拟银行家审批贷款的过程:银行家 (操作系统) 在批出贷款 (分配资源) 前,要确保即使这笔钱放出去了,自己手头的资金 (剩余资源) 依然能满足其他客户 (进程) 后续的最大需求,从而保证银行不会倒闭 (系统不会死锁) 。
算法所需的数据结构: 假设有n个进程和m类资源。
Available[m]
: 一个向量,表示每类资源当前还可用的实例数量。Max[n][m]
: 一个矩阵,表示每个进程对每类资源最大的需求量。Allocation[n][m]
: 一个矩阵,表示每个进程当前已分配到的每类资源的实例数量。Need[n][m]
: 一个矩阵,表示每个进程还需要的每类资源的实例数量。Need[i][j] = Max[i][j] - Allocation[i][j]
算法核心:
资源请求: 当进程 请求资源 Request[i]
时: a. 检查请求是否合法:Request[i] <= Need[i]
?如果一个进程请求的超过了它声明的最大需求,则为非法请求。 b. 检查系统是否有足够资源:Request[i] <= Available
?如果没有,进程必须等待。 c. 假装分配: 如果前两步都通过,系统暂时将资源分配给它,并更新数据结构:
Available = Available - Request[i]
Allocation[i] = Allocation[i] + Request[i]
Need[i] = Need[i] - Request[i]
d. 安全检查: 调用安全性算法,检查分配后的新状态是否安全。安全性算法: a. 初始化工作向量 Work = Available
,和完成标记 Finish[n]
(所有元素为false
) 。 b. 从进程中寻找一个满足以下两个条件的进程 :
Finish[i] == false
(还没执行完)Need[i] <= Work
(它需要的资源小于等于系统当前可用的资源) c. 如果找不到这样的进程,直接跳到第 e 步。 d. 如果找到了 ,则假设它执行完毕并释放所有资源。更新 Work
和 Finish
:Work = Work + Allocation[i]
Finish[i] = true
Finish
数组,如果所有元素都为 true
,则说明系统处于安全状态。否则,为不安全状态。进程 | 目前占有量 | 最大需求量 | 尚需要量 (Need) |
---|---|---|---|
P1 | 1 | 4 | 3 |
P2 | 4 | 6 | 2 |
P3 | 5 | 8 | 3 |
12 - (1+4+5) = 2
安全性检查:
Work = 2
, Finish = [F, F, F]
Need=3 > Work=2
(不行)Need=2 <= Work=2
(可以!)Need=3 > Work=2
(不行)Work = Work + Allocation[P2] = 2 + 4 = 6
Finish = [F, T, F]
Need=3 <= Work=6
(可以!)Work = Work + Allocation[P1] = 6 + 1 = 7
Finish = [T, T, F]
Need=3 <= Work=7
(可以!)Work = Work + Allocation[P3] = 7 + 5 = 12
Finish = [T, T, T]
结论: 由于所有进程的 Finish
标记都为 true
,所以当前状态是安全的。一个安全序列是 <P2, P1, P3>
。
已分配 (Allocation) | 最大需求 (Max) | 尚需要 (Need) | |
---|---|---|---|
A B C | A B C | A B C | |
P1 | 0 1 0 | 7 5 3 | 7 4 3 |
P2 | 2 0 0 | 3 2 2 | 1 2 2 |
P3 | 3 0 2 | 9 0 2 | 6 0 0 |
P4 | 2 1 1 | 2 2 2 | 0 1 1 |
P5 | 0 0 2 | 4 3 3 | 4 3 1 |
问题1:此状态是否安全?
Work = [3, 3, 2]
, Finish = [F, F, F, F, F]
[7,4,3] > [3,3,2]
(不行)[1,2,2] <= [3,3,2]
(可以!) -> 找到 P2。Work = [3,3,2] + [2,0,0] = [5,3,2]
Finish = [F, T, F, F, F]
[7,4,3] > [5,3,2]
(不行)[6,0,0] > [5,3,2]
(不行)[0,1,1] <= [5,3,2]
(可以!) -> 找到 P4。Work = [5,3,2] + [2,1,1] = [7,4,3]
Finish = [F, T, F, T, F]
[7,4,3] <= [7,4,3]
(可以!) -> 找到 P1。Work = [7,4,3] + [0,1,0] = [7,5,3]
Finish = [T, T, F, T, F]
[6,0,0] <= [7,5,3]
(可以!) -> 找到 P3。Work = [7,5,3] + [3,0,2] = [10,5,5]
Finish = [T, T, T, T, F]
[4,3,1] <= [10,5,5]
(可以!) -> 找到 P5。Work = [10,5,5] + [0,0,2] = [10,5,7]
Finish = [T, T, T, T, T]
结论: 是安全状态。一个安全序列为 <P2, P4, P1, P3, P5>
。
问题2:P1申请(0,2,0)能否分配?
Request_P1 = [0,2,0] <= Need_P1 = [7,4,3]
(合法)Request_P1 = [0,2,0] <= Available = [3,3,2]
(有资源)Available = [3,3,2] - [0,2,0] = [3,1,2]
Allocation_P1 = [0,1,0] + [0,2,0] = [0,3,0]
Need_P1 = [7,4,3] - [0,2,0] = [7,2,3]
Work = [3,1,2]
, Finish = [F,F,F,F,F]
[7,2,3] > [3,1,2]
(不行)[1,2,2] > [3,1,2]
(不行)[6,0,0] > [3,1,2]
(不行)[0,1,1] <= [3,1,2]
(可以!) -> 找到 P4Work = [3,1,2] + [2,1,1] = [5,2,3]
Finish = [F,F,F,T,F]
[7,2,3] > [5,2,3]
(不行)[1,2,2] <= [5,2,3]
(可以!) -> 找到 P2Work = [5,2,3] + [2,0,0] = [7,2,3]
Finish = [F,T,F,T,F]
[7,2,3] <= [7,2,3]
(可以!) -> 找到 P1结论: 可以分配。安全序列存在。
这种策略不预防也不避免,而是采取”亡羊补牢”的方式。
一旦检测到死锁,就需要采取措施打破僵局。代价越小越好。
这个问题是Dijkstra提出的一个经典的并发同步问题,用以说明死锁。
每个筷子是一个信号量。哲学家i
先拿左边的筷子fork[i]
,再拿右边的fork[(i+1)%5]
。
// 伪代码
void philosopher(int i) {
while(true) {
think();
P(fork[i]); // 拿左筷子
P(fork[(i+1) % 5]); // 拿右筷子
eat();
V(fork[(i+1) % 5]); // 放右筷子
V(fork[i]); // 放左筷子
}
}
c将获取和释放筷子的操作封装在管程内部。但幻灯片中给出的get_forks
实现是有问题的,它依然是顺序地申请左右筷子,如果获取左筷子后在等待右筷子时被阻塞,同样会造成死锁,并没有解决根本问题。一个正确的管程实现需要能原子地检查并获取两只筷子。
这是 Tanenbaum 提出的一个经典解法,可以避免死锁和饥饿。
state
数组记录每个哲学家的状态 (思考、饥饿、进食) 。一个哲学家只有在他左右两边的邻居都没有在进食时,才允许他从”饥饿”状态转为”进食”状态。这个检查和状态转换是原子的 (通过mutex
互斥锁保护) 。// 伪代码
#define N 5
#define THINKING 0
#define HUNGRY 1
#define EATING 2
int state[N];
semaphore mutex = 1; // 保护对state数组的访问
semaphore s[N] = {0}; // 每个哲学家一个信号量,用于阻塞
void philosopher(int i) {
while(true) {
think();
take_forks(i); // 核心逻辑
eat();
put_forks(i); // 核心逻辑
}
}
void take_forks(int i) {
P(mutex); // 进入临界区
state[i] = HUNGRY;
test(i); // 尝试获取筷子
V(mutex); // 退出临界区
P(s[i]); // 如果不能吃,则在此阻塞
}
void put_forks(int i) {
P(mutex); // 进入临界区
state[i] = THINKING;
test((i+N-1) % N); // 检查左邻居能否开吃
test((i+1) % N); // 检查右邻居能否开吃
V(mutex); // 退出临界区
}
void test(int i) {
// 如果哲学家i饿了,并且左右邻居都没在吃
if (state[i] == HUNGRY &&
state[(i+N-1) % N] != EATING &&
state[(i+1) % N] != EATING)
{
state[i] = EATING;
V(s[i]); // 唤醒哲学家i (如果他被阻塞了)
}
}
ctest
邻居,它也能保证一定的公平性,避免饥饿。room
,并初始化为4。// 伪代码
semaphore room = 4; // 餐厅最多坐4人
void philosopher(int i) {
while(true) {
think();
P(room); // 进入餐厅
P(fork[i]);
P(fork[(i+1) % 5]);
eat();
V(fork[(i+1) % 5]);
V(fork[i]);
V(room); // 离开餐厅
}
}
c这实际上是寻找5个节点的所有强连通有向图的非同构类。我按最小边数和结构复杂度系统分析:
模型1: 单个5环
graph TD
P1 --> P2 --> P3 --> P4 --> P5 --> P1
mermaid**模型2: 5环+1条弦 (跨2个节点) **
graph TD
P1 --> P2 --> P3 --> P4 --> P5 --> P1
P1 --> P3
mermaid模型3: 4环+分支链
graph TD
P1 --> P2 --> P3 --> P4 --> P1
P5 --> P2 --> P5
mermaid模型4: 5环+2条相邻弦
graph TD
P1 --> P2 --> P3 --> P4 --> P5 --> P1
P1 --> P3
P2 --> P4
mermaid模型5: 5环+2条对称弦
graph TD
P1 --> P2 --> P3 --> P4 --> P5 --> P1
P1 --> P3
P3 --> P5
mermaid**模型6: 3环+2环 (共享1个节点) **
graph TD
P1 --> P2 --> P3 --> P1
P1 --> P4 --> P5 --> P1
mermaid模型7: 5环+2条非相邻、非对称弦
graph TD
P1 --> P2 --> P3 --> P4 --> P5 --> P1
P1 --> P3
P1 --> P4
mermaid**模型8: 双4环结构 (共享1条边) **
graph TD
P1 --> P2 --> P3 --> P1
P2 --> P4 --> P5 --> P2
P1 --> P4
mermaid模型9: 3环+双分支汇聚
graph TD
P1 --> P2 --> P3 --> P1
P4 --> P1
P5 --> P1
P1 --> P4
P2 --> P5
mermaid模型10: 中心星型+反向环
graph TD
P1 --> P2
P1 --> P3
P1 --> P4
P1 --> P5
P2 --> P3 --> P4 --> P5 --> P2
mermaid模型11: 双3环交叉结构
graph TD
P1 --> P2 --> P3 --> P1
P3 --> P4 --> P5 --> P3
P2 --> P4
P5 --> P1
mermaid**模型12: 准完全图 (缺少部分边的强连通图) **
graph TD
P1 --> P2 --> P1
P2 --> P3 --> P2
P3 --> P4 --> P3
P4 --> P5 --> P4
P5 --> P1 --> P5
P1 --> P3
P2 --> P4
P3 --> P5
mermaid模型13: 高度连接的复杂图
graph TD
P1 --> P2 --> P3 --> P4 --> P5 --> P1
P1 --> P4
P2 --> P5
P3 --> P1
P4 --> P2
P5 --> P3
mermaid根据图论分析,5个节点的强连通有向图共有13种主要的非同构类。这些结构可以按边数分类:
每种结构都代表了一种可能的5进程死锁模式,死锁问题的复杂性远超简单的环形等待。
问题: 进程请求资源时启动计时器。如果因阻塞超时,就”释放”该进程并让它重新执行。
我的评价: 作为老师,我会给这位同学一个及格分,但不会给高分。比如 60-70分。
优点 (为什么给分):
缺点 (为什么不能给高分):