Cha6 死锁和饿死要求掌握
发生死锁的条件
死锁预防的方法
死锁避免的方法
死锁检测的方法死锁的例子获得 A 获得 B 释放 A 释放 B
获得 B
获得 A
释放 B
释放 A
1 2
3 4
5
6
PQ都要 A
PQ都要 B
进程的一般形式
Process P
…
Get A
…
Get B
…
release A
…
release B
Process Q
…
Get B
…
Get A
…
release B
…
release A
Process P
…
Get A
…
release A
…
Get B
…
release B
可能死锁 不会死锁无死锁的例子获得 A 获得 B释放 A 释放 B
获得 B
获得 A
释放 B
释放 A
1 2
3 4
5
6
PQ都要 A
PQ都要 B
可重用资源的分配
p0 p1 q0 q1 p2 q2→ 死锁
p0 request D
p1 lock D
p2 request T
p3 lock T
p4 执行
p5 unlock D
p6 unlock T
q0 request T
q1 lock T
q2 request D
q3 lock D
q4 执行
q5 unlock T
q6 unlock D
进程 P 进程 Q
可重用资源的分配 -200k内存
…
request 80 kb
…
request 60 kb
进程 P1 进程 P2
…
request 70 kb
…
request 80 kb
可消费资源的分配
…
receive (p2);
…
send (p2,m1);
进程 P1 进程 P2
…
receive (p1);
…
send (p1,m2);
检测、预防、避免方法小结原则 不同方案 优点 缺点预防
(保守 )
一次请求所有资源无需剥夺适合连续使用低效要知道将来资源请求延迟进程初始化剥夺 状态容易保存和恢复经常剥夺循环重启资源排序 系统设计时解决编译时检测剥夺无效禁止增加资源请求检测、预防、避免方法小结原则 不同方案 优点 缺点避免 发现安全路径无需剥夺 要知道将来资源请求不能长时间阻塞检测 周期性测试不会延迟初始化易于在线处理丢失剥夺死锁的条件
互斥
占有等待
非剥夺
循环等待资源 A
资源 B
进程 P1 进程 P2
请求 占有占有 请求死锁避免－拒绝启动进程
resource=(R1,R2… Rm)每种资源的总量
available=(V1,V2… Vm)每种资源的剩余量
C11 C12 … C1m
C21 C22 … C2m
…
Cn1 Cn2 … Cnm
Claim= 各进程的最大资源需求
A11 A12 … A1m
A21 A22 … A2m
…
An1 An2 … Anm
allocation= 当前资源分配情况
A<C<R
资源分配拒绝目前状态 新状态 安全不安全同意不同意假设同意分配请求
resource
9 3 6
available
1 1 2
claim
3 2 2
6 1 3
3 1 4
4 2 2
allocation
1 0 0
5 1 1
2 1 1
0 0 2
resource
9 3 6
available
0 1 1
claim
3 2 2
6 1 3
3 1 4
4 2 2
allocation
1 0 0
6 1 2
2 1 1
0 0 2
P2请求
(1,0,1)
该状态是否安全?
resource
9 3 6
available
0 1 1
claim
3 2 2
6 1 3
3 1 4
4 2 2
allocation
1 0 0
6 1 2
2 1 1
0 0 2
available
6 2 3
allocation
1 0 0
0 0 0
2 1 1
0 0 2
available
7 2 3
allocation
0 0 0
0 0 0
2 1 1
0 0 2
available
9 3 4
allocation
0 0 0
0 0 0
0 0 0
0 0 2
available
9 3 6
allocation
0 0 0
0 0 0
0 0 0
0 0 0
不安全状态
resource
9 3 6
available
1 1 2
claim
3 2 2
6 1 3
3 1 4
4 2 2
allocation
1 0 0
5 1 1
2 1 1
0 0 2
resource
9 3 6
available
0 1 1
claim
3 2 2
6 1 3
3 1 4
4 2 2
allocation
2 0 1
5 1 1
2 1 1
0 0 2
P1请求
(1,0,1)
死锁检测
resource
2 1 1 2 1
available
0 0 0 0 1
request
0 1 0 0 1
0 0 1 0 1
0 0 0 0 1
1 0 1 0 1
allocation
1 0 1 1 0
1 1 0 0 0
0 0 0 1 0
0 0 0 0 0
available
0 0 0 1 1
结论－ P1,P2死锁死锁的恢复
取消所有死锁进程
所有死锁进程恢复到检查点
连续取消死锁进程
连续剥夺资源已经使用 CPU时间最少产生的输出最少预计剩余耗时最少获得资源总量最少优先级最低综合的死锁策略
资源分组
组间－线性排序策略
组内－适合的算法可交换空间－一次性请求进程资源－死锁避免，排序内存－剥夺内部资源－资源排序哲学家就餐问题
Semaphore fork[5]={1};
Int I;
Void philosopher(int i)
{while true
{think();
Wait(fork[i]);
Wait(fork[(i+1) mod 5]);
Eat();
signal (fork[(i+1) mod 5]);
signal (fork[i]);
}}
Void main()
{parbegin (philosopher(0),
(philosopher(1),
(philosopher(2),
(philosopher(3),
(philosopher(4))
}
哲学家就餐问题
Semaphore fork[5]={1};
Semaphore roo={4};
Int i;
Void philosopher(int i)
{while true
{think();
Wait (room);
Wait(fork[i]);
Wait(fork[(i+1) mod 5]);
Eat();
signal (fork[(i+1) mod 5]);
signal (fork[i]);
signal (room);
}}
Void main()
{parbegin (philosopher(0),
(philosopher(1),
(philosopher(2),
(philosopher(3),
(philosopher(4))
}