DIN中的死锁避免和死锁恢复

DIN中的死锁避免和死锁恢复

由于存在占用资源者申请另一个资源的情形，在DIN中由于拓扑结构本身存在环状路径，所以在DIN中易死锁。图2所示，A,B,C,D是4个分组的路径(Path)构成循环形成死锁的情形。文献[4]讨论了互连结构中死锁的问题，提出了用通道依赖图(channel dependency graph，CDG)是否存在循环来判断是否死锁。文献[6]改进了这种方法，肯定了CDG图的充分性和必要性，即动态出现CDG图循环时不死锁。
解决死锁的方法可分为两大类：死锁避免和死锁恢复。死锁避免是指通过在路由算法设置禁用某些资源来防止出现路径环。文献[10]通过限制一个方向上的路由来打破循环，避免死锁。本文2中路由算法也都采用死锁避免策略。死锁避免是通过限制对一些资源(缓存或物理通道)的利用来防止死锁，因此交换结构资源利用率不高。
死锁恢复是在发现结构内发生死锁后，通过一定的策略来解决死锁。允许分组使用交换结构中的任何资源，提高交换结构的资源利用率。一般有两种死锁恢复方法。消极死锁恢复法，采用丢弃，偏移路由来处理死锁分组。积极死锁恢复法通过分配其他资源来传送死锁分组到达目标节点。对于死锁的判决是死锁恢复机制中的一个难点，特别是在业务负载和分组长度变化范围大时。如何快速区别分组是阻塞还是死锁。在文献[11]中讨论了基于等待时间的死锁恢复机制。文献[12]介绍了一种分布式死锁检测机制，它采用判断阻塞分组中根节点的方法来降低误判率。

图2 A,B,C,D 4个分组构成一个死锁

在数据交换结构中采用死锁恢复机制更适合在数据交换技术中，整个结构资源有限，数据交换对于传送带宽的要求更高。数据恢复机制需要结合自适应路由算法来降低死锁的发生率。因此分析各种路由算法的死锁发生率是十分必要的。