分布式计算系统中死锁的预防技术探讨

　　1 分布式计算系统中的死锁
　　分布式计算机系统是一种具有多处理器并且各个处理器之间通过互连网络构建成一个具有整体功能的计算机系统。系统工作的原理是采用分布式计算结构，即将传统计算机系统内中央处理器处理的任务分散给相应的各个处理器，实现不同功能的各个处理器可以相互协调合作，达到共享系统中外设与软件的效果。系统具有的优点是加快了处理的速度，简化了主机的逻辑结构，特别适合于应用在工业生产线自动控制和企事业单位的管理，同时具有成本低和易于维护的特点，并且成为计算机应用领域发展中的一个重要方向。但是，在分布式环境下，由于通讯延迟的不确定性、地域的分布性以及资源和数据的高度共享性等影响因素的存在，使得死锁预防和检测变得极为困难。
　　1.1 死锁的定义
　　在分布式计算系统中，有两个以上的进程在并发执行，每个进程都在等待被其它的进程所占用的系统资源（每个进程都在等待其它的进程释放所持有的锁）而不能继续运行，即导致系统中任何一个进程都无法运行下去（死循环），这就产生了死锁[1]。
　　1.2 死锁发生的条件
　　Peterson[2]指出了发生死锁的必要条件，确切地说，当且仅当以下四个条件同时成立时，死锁才会发生。
　　1） 互斥。同一个资源在同一时刻最多只能被一个进程占用。
　　2） 占有并等待。必然有一个进程至少占用了系统中的一个资源，同时在等待获取被其他进程占用的资源。
　　3） 不可剥夺。一个进程不能剥夺被其他进程占用的资源。
　　4） 循环等待。在等待图中有一个循环。
　　其中条件4） 是关于一组进程的特定动态行为的陈述[3]。
　　2 分布式计算系统中死锁的预防
　　2.1 一般方法
　　1） 静态分配资源
　　这种方法是要求进程必须在开始执行前就申请它所需要的全部资源，并且只有当系统能满足进程的资源申请要求并把资源分配给进程之后，该进程才开始执行。这种策略可以预防死锁的发生是由于其破坏了“占有且等待资源”和“循环等待资源”的条件，从而系统中的所有进程必然不会发生死锁。
　　2） 按序分配资源
　　这种方法是指在系统中的每一个资源都会给出一个编号。分配资源的时候作了以下规定：任何进程在申请两个以上资源时，总是按照编号的大小顺序申请。这种策略可以预防死锁的发生是由于其破坏了“循环等待资源”的条件，从而系统中的所有进程必然不会发生死锁。
　　3） 剥夺式分配资源
　　这种方法是指当一个进程申请资源得不到满足时，可从另一个拥有这种资源的进程那里去抢夺，然后继续运行。这种策略可以预防死锁的发生是由于其破坏了“非抢夺式分配”的条件，从而系统中的所有进程必然不会发生死锁。
　　以上的策略都是预防死锁发生的有效方法，但是它们也有不足之处。例如，静态分配策略和按序分配资源策略都有可能会出现进程在占有了资源后在相当一段时间里并不使用的情况，从而导致了系统资源利用率的下降；剥夺式分配资源策略在当前却只适合于应用在对处理器和主存资源的分配，适用范围较小。
　　2.2 基于时间戳的方法
　　这里主要介绍两种基于时间戳的死锁预防方法。
　　1） “伤害-等待”的方法
　　该方法基于剥夺方法。其主要思想是：当进程Pi请求的系统资源正被进程Pj占有时，只有当进程Pi比Pj年轻（即它们的时间戳关系是Li>Lj）时，进程Pi才能处于等待状态；否则进程Pj会被取消（即Pj被Pi伤害）并带有同一时间戳重新启动，而Pi则可以获得锁后继续执行。该方法是以进程启动的时间戳来快速判断进程的优先级，并以此决定进程是应该终止、继续执行还是等待。
　2） “等待-死亡”的方法
　　该方法基于非剥夺方法。其主要思想是：当进程Pi请求的系统资源被进程Pj占有时，只有当进程Pi比Pj老（即它们的时间戳关系是Li　　3 分布式计算系统中死锁的检测
　　基于事先预防死锁的方法基本上都会增加系统的开销，降低资源的利用率，因此在实践中并不太适用。在分布式系统中，为了降低系统开销，在分配资源时会不加限制，只要系统中有剩余的资源，总是把资源分配给申请者。显然，这样的结果是可能会出现死锁。那么，为了使系统能够正常工作，在系统中会采用定时运行一个“死锁检测”程序的方法，当检测到死锁时该程序再将会设法将其排除。在分布式系统中的死锁检测法不会造成很多不必要的进程流产，但是也会增加了系统的额外开销和复杂度。
　　在分布式的死锁检测算法[4]中，每个机器都保持它们的独立性，一个局部的失效不会对算法产生致命的影响。通常可以将其划分成两种：第一种是每个机器都有一个全局等待图的复制，即每个机器都有一个关于分布式系统的全局视图；第二种是把系统的全局等待图分解后分布在不同的机器上。
　　Knapp提出把分布式的死锁检测算法分成如下四类[5]。
　　1） 路径推动算法。该算法的基本思想是：首先在每个机器上都构建形式简单的全局等待图，当进行死锁检测时，各个机器就将全局等待图的复制发送给一定数量的邻近节点，若局部复制有更新则会被传播下去。重复以上这一过程，直到某个节点获得了足够的信息并能够构造出一个全局等待图并可以判断出系统是否存在死锁的结论。
　　2） 边跟踪算法。该算法的基本思想是：通过沿分布式网络结构图的边发送一种叫探测器的特殊信息来检测是否存在回路。当一个发起者得到一个与自己发送的探测器相匹配的探测器时，它就可以知道它是在该结构图中的一个回路里。
　　3） 扩散计算。该算法的基本思想是：若怀疑系统发生死锁的时候，进程管理器将会通过向依赖于它的进程发送查询启动一个扩散进程，使得系统不会生成全局等待图。当处于发送查询信息时，扩散计算就会增加；当接收回答之后，扩散计算就会减少。最后由所得信息，发起者会检测到死锁的发生。
　　4） 全局状态检测。该算法的基本思想是：通过建立一个统一的全局状态但不需要暂停当前的计算来获得一个一致的全局等待图。
　　4 总结
　　在死锁预防的策略中 ，通常的做法是防止死锁发生的四个条件中的任意一个发生。但是死锁预防的缺点是降低了资源利用率和系统吞吐率。解决死锁的另一个方法是死锁避免，在死锁避免中，需要知道如何请求资源，它动态检查资源分布状态，以保证没有循环等待发生。实际上，死锁避免算法的一个潜在问题是需要及时地收集到一致的全局状态信息，一般来说，在分布系统中，很少使用死锁避免，因为它对请求进程和可用资源的数量这些信息的要求太严格了，而且对系统进行安全性状态的检查也会涉及到大量的计算，这些都会引起巨大的开销。当死锁不可避免地发生的时候，采取相应的死锁检测算法进行检测与处理。
　　参考文献：
　　[1] 邵佩英.分布式数据库系统及其应用[M].2版.北京：科学出版社，2005.[2] Peterson J.L， Silberschatz A. Operating System Concepts， Second Edition. Addison-Wesley Publishing Company， 1985.
　　[3] Jean B， Tim H. 操作系统-并发与分布式软件设计[M].陈向群，译.北京：电子工业出版社，2005.
　　[4] 贾焰，王志英，韩伟红，等.分布式数据库技术[M].北京：国防大学出版社，2000.
　　[5] Edgar Knapp. Deadlock Detection in Distributed Databases. ACM Computing Surveys， 1987， 19：303-328.