分布计算系统笔记——第五章 死锁

死锁 ​

条件 ​

互斥、不可剥夺的资源分配、占有并等待、循环等待

图模型 ​

等待图：i->j，i等待j用完资源

资源分配图：进程指向资源，意思是请求资源；资源指向进程，意思是分配给了这个进程

资源分配图转化为等待图 ​

指向资源的进程 改为指向 该资源指向的进程

处理死锁的方法：PAID ​

1. 预防(prevent)死锁。通过限制请求，保证四个死锁条件中至少有一个不能发生，从而预防死锁。
2. 避免(avoid)死锁。如果资源分配会导致一个安全的结果状态，就将资源动态地分配给进程。如果至少有一个执行序列使所有的进程都能完成运行，那么这个状态就是安全的。
3. 忽略(ignore)死锁。忽略死锁是UNIX常采用的一种方法，这种方法只是简单地忽略死锁问题。
4. 检测(detect)死锁和从死锁中恢复。允许死锁发生，然后发现并解除死锁。

AND OR条件 ​

资源死锁使用and条件，通信死锁使用or条件

or条件：在等待图中，如果沿箭头走无论如何都走不出某个结，说明存在死锁

预防死锁 ​

一般方法 ​

1. 进程执行前必须同时获得所有需要的资源
2. 一个进程只能请求一个资源，不能请求资源编号更大的资源
3. 进程设置优先级，根据优先级决定是否等待

基于时间戳的预防死锁方法 ​

1. 等待-死亡方案。年轻者请求年老者资源，年轻者死亡。年老者请求年轻者资源，年老者等待。
2. 伤害-等待方案。年轻者请求年老者资源，年轻者等待。年老者请求年轻者资源，年轻者死亡。

集中式死锁检测 ​

每个机器维护一个局部资源分配图，局部资源分配图组合成全局资源分配图，由协调者维持。

1. 当在局部图中有边被加入或删除时，向协调者发送一个报文，协调者根据报文信息对全局图进行更新。
2. 定期地更新，每个机器定期地向协调者发送自上次更新以来所有添加的边和删除的边，协调者根据报文信息对全局图进行更新。
3. 当协调者认为需要运行回路检测算法时，它要求所有的机器向它发送局部图的更新信息，协调者对全局图进行更新。
4. 当开始死锁检测时，协调者便查找全局等待图。如果发现回路，一个进程就会被卷回，从而打破循环等待

假死锁：协调者的部分资源分配图没有及时更新

分布式死锁检测 ​

Knapp的分类：路径推动算法(path-pushing algorithm)、边跟踪算法(edge-chasing algorithm)、扩散计算(diffusing computation)、全局状态检测(global state detection)

AND模型下的Chandy-Misra-Hass算法 ​

发送探测报文(i, j, k)，从i发起，现在要从j传给k

收到探测报文时，向所有自己等待的进程发送探测报文，如果最后报文发给了发起者，说明有死锁。

打破死锁：1. 发起者杀死自己。如果多个进程同时检测到同一个死锁时就群体自杀了。2. 每个进程在报文中添加自己的标识符，发起者选一个最大的杀死。

AND模型下的Mitchell-Merritt算法 ​

每个进程只请求一个资源时，向等待的反方向发送探测报文，途中进程比较自己的进程号，如果自己的大，就覆盖掉，如果最后收到了自己的，说明有死锁。

因为有覆盖，所以当几个进程同时发起死锁检测时，只有一个进程能够成为唯一的探测者

因为只请求一个资源，所以反向等待图不会有进入环的边

OR模型下的Chandy-Misra-Hass算法 ​

1. 使用两类报文：(query,i,j,k)和(reply,i,j,k)，表示这些报文属于由进程Pi发起的并由Pj送往Pk的扩散计算。
2. 一个进程的依赖集合包括所有它在等待以便获得报文的进程。如果接收进程Pk是活动的，它会忽略所有的查询和回答报文。如果它被阻塞，它会向它的依赖集合中的进程发送查询。
3. 一旦收集到回答报文，接收进程将向发起者发送一个回答报文。发起者以及每个中间进程用一个计数器记录查询和回答的数目。如果这两个数字相同，即发起者的每个查询都得到了回答，就表明发起者处于死锁状态。