《操作系统》分布式系统中的死锁问题之 预防死锁

最近读了 《操作系统》(第2版)     狄东宁 战晓苏 侯彩虹译 中的第十一章 分布式系统，觉得里面的一些理论非常好，故在此记录下。

原文  转载自： http://book.51cto.com/art/200907/133346.htm

 

 

分布式系统中的死锁问题

        同分布式系统中的多数其他内容一样，死锁提出了一种好的设计挑战。即使在非分布式环境中解决死锁问题也并不容易，当遇到多进程/节点/操作系统的挑战时，这个任务将变得更棘手。

这里讨论分布式环境中与死锁相关的三种策略：预防死锁、避免死锁和检测死锁。这里用术语"事务"替代消息，因为前者在分布式系统相关文献中较为通用(在死锁环境中)。

 

11.14.1  预防死锁

该方法使用了时间戳技术。每个事务都有自己的时间戳。考虑一下，有两个事务T1和T2，以及一个T1和T2都感兴趣的资源S。在给定时刻，T1占用 R，而之后很快T2也想占用R。显然，必须赶快决定如何解决这个问题。否则，最终将会导致死锁。有两种可能的解决方法，它们分别是：等待死亡法和受伤等待 法。

 

1. 等待死亡法

如同前面提到过的一样，开始是T1占用R，T2也试图占用R。假定T1的时间戳是TS1，T2的是TS2。该方法避免死锁的解决方式如图11-35所示。

 

图11-35  等待死亡法

 

       诚如所见，如果事务T2在事务T1之前开始(按照时间戳值)，那么T2等待T1结束。否则，分布式操作系统就会杀死T2，并在一段时间后重新启动它(具有相同的时间戳TS2)，同时假设T1目前已经释放了资源R。

总结一下，如同期望的一样，事务发生越早，优先级越高。同样可以看到，被杀死的进程重新启动时，它的时间戳值是最初的时间戳值。那样该进程就可以保持它以前的优先级(在重新启动该进程时，它的优先级将比大部分其他事务的优先级高)。

 

 

2. 受伤等待法

       相比于前面的方法，该方法采用了不同的技术。这里，开始也是先进行类似的比较。比较T1和T2的时间戳(也就是TS1和TS2)。如果TS2小于 TS1(意味着T2在T1之前先运行)，现在杀死T1。注意：在前面的例子中，这种情况下将阻塞T2。然后，如果T1开始得比较早，那么就停止T2，过程 如图11-36所示。

 

图11-36  受伤等待法

 

        总结一下，在该方法中，可以通过杀死较新事务而立刻处理比较老的事务的请求。这意味着比较老的事务不需要等待较年轻的事务(这不同于前面的方法)。