DISTRIBUTED SYSTEMS中死锁问题解决方法研究

韦侃

[摘要]本文介绍了分布式系统下出现死锁的原因，类型。分布式系统死锁的检测，在检测中出现的问题。以及预防分布式系统死锁和解决分布式系统死锁的方法。

[关键词]分布式系统，死锁，进程，资源

[中图分类号][C94] [文献标识码]A [文章编号]1672-5158（2013）06-0392-02

一、引言

分布式系统就是把多个处理机通过线路互连而构成系统，它的处理和控制功能分布在各处理机上。在系统中的一组进程，由于竞争系统资源或由于彼此通信而永远阻塞，我们称这些进程处于死锁状态。产生死锁的原因，可归结为两点：（1）竞争资源，（2）进程推进顺序非法。

二、死锁类型

总的来说，系统中的资源可分为两种类型：可剥夺性资源，如处理机，存储器等；非剥夺性资源，如打印机，磁带机等；在网络和分布式系统中上述两种资源都可能引起以下两种类型的死锁：

2.1 资源型死锁（resource deadlock）

当有一组进程竞争非剥夺性资源时，如果出现因进程的推进顺序不正确，进入了不安全区，导致发生进程死锁。

2.2 消息型死锁（message deadlock）

在不同结点中的进程，为发送和接收分组而竞争缓冲区，以致发生了既不能发送消息，也不能接收消息的僵持状态。典型的消息型死锁有三种类型：重新组装型死锁（reassembly deadlock）、直接存储-转发型死锁（direct store-and-forward deadlock）、间接存储-转发型死锁。

三、死锁检测中出现的问题

分布式系统下产生的死锁与单机系统下产生死锁有很多相似，其产生原因和必要条件，基本相同。但也有着自己的一系列特殊性。

3.1 进程与资源的分布性

在单机环境下，非剥夺性资源和一组竞争该资源的进程都处于同一系统中。相应地，在系统中设置一个死锁检测机构，由它统一监视和计算机使用共享资源时，是否会出现环路条件。

在分布式环境下，可供全网共享的资源是分布在各个结点中，而竞争资源的进程又是来自于不同的结点。然而，拥有共享资源的每个结点，通常都只知道本结点中资源的使用情况。因此，要检测来自不同结点的进程在竞争共享资源时是否会引起死锁，无疑是十分困难的。

3.2 死锁的虚假性

在单机环境下，当一组进程竞争非剥夺性资源时，如果在资源分配图中已经检测到出现了环行链，说明这组进程中的每个进程，至少都保持了一个其后继进程所需的资源。则可认为此时发生了进程死锁。

然而，分布系统环境下，如果检测出资源分配图中出现了环行链，却不能认为是发生了真正的死锁，此时的死锁可能是真正的死锁。也可能是虚假的死锁。因为在分布式系统环境下存在着进程发出的请求资源和释放资源的时序性。

在图1（a）所示的资源分配图中，有一组进程p1，p2，p3。其中，p1保持资源R1又请求资源R2；p2保持R2又请求R3；p3保持R3。假设此时p3又先发出释放R3的命令，然后再发出请求R1的命令。如果释放R3的命令先到达，环路检测进程，而p3请求R1的命令后到达，则此时会出现图1（b）所示的资源分配图，从图可知，这组进程未进入死锁状态。但如果p3请求R1的命令比它释放R3的命令先到达检测进程，此时的资源分配图，将如图（c）所示出现了环路，因而检测进程认为发生了死锁。然而，此时的死锁是虚假的。因为当释放R3的命令到达后，在图中的R3到p3的分配边将被消去，环路条件不成立。

四、死锁的解除与恢复

在网络和分布式系统环境下，资源型死锁的解除方法与单机系统时类似，当然要复杂得多。对于消息型死锁，由于消息是一种特殊形式的资源，它很容易产生、控制和复制，致使其解除死锁的方法，比资源型死锁的解除方法更多且更方便。例如，当发现分组在网络中传输过多时，就会很容易因缓冲区的不足而产生死锁，这时就可采取禁止主机产生新的消息并送入网络的方法来避免死锁。又如，当某个结点没有足够的缓冲区来接收新的分组的时候，可以利用流量控制机构，来禁止源结点继续向本结点发送分组，或者可以将到达的分组丢弃，以避免死锁的发生。在发生死锁时，可通过撤销一部分网络中正在传输分组的方法来解决死锁。

当检测到一组进程处于死锁中，应立即采用事先商定好的死锁恢复算法将死锁解除，以使系统恢复正常工作。死锁恢复方法有：

（1）杀死处于死锁状态中的一个或若干个进程。或干脆杀掉所有的死锁过程，然后回收它们占有的资源，以解除死锁。这是比较简单的方法，也是分布式操作系统常用死锁恢复方法。

（2）系统周期性地对进程进行检查，在每个检查点都将进程的状态写入文件以便需要时备用。这样做也为进程从死锁中恢复提供了帮助。当死锁发生时，将死锁的进程回退到前面备份的检查点，然后再重新启动所有的进程。则该检查点以后的工作将被丢弃。这种方法实现起来要比第（1）种方法复杂得多，开销也大，而且可能会导致再次死锁的分险。但在并发系统中这种可能性几乎为零。

五、死锁预防

为了防止在网络中出现死锁，可以采取摒弃产生死锁的四个必要条件之一的方法来实现。

5.1 摒弃“请求和保持”条件

（1）资源型死锁的预防

像单机系统一样，为防止进程争夺网络资源而发生死锁，可让所有的进程在运行之前，一次性地申请其所需的全部网络资源。这样，进程在运行中便不会再提出资源请求，从而摒弃了请求条件。如果网络无法满足进程的所有资源要求，便不把任何资源分配给该进程，这样也就摒弃了保持条件。

（2）重新组装型死锁的预防

为了避免发生重装型死锁，源结点中的发送进程在发送一分报文中的各个分组之前，应一次性地向目标结点申请一份报文所需的全部缓冲区。如果目标结点有足够的缓冲区，便为发送进程如数地分配其所需的全部缓冲区。这样，发送进程在传送这些分组时，便不会再提出缓冲区请求，因而摒弃了请求条件，目标结点若无足够的缓冲区，便一个也不分配给发送进程，于是也就摒弃了保持条件。

5.2 摒弃“环路等待”条件

（1）线形排序法、

将网络中所有可供共享的网络资源，进行线形排序。同时，要求所有进程对网络资源的请求，严格按资源号递增的次序提出申请。这样便可防止在资源分配图中出现“环路等待”条件。

（2）等待死亡（waiFdie）算法

该算法用于分布式数据库系统的并发控制。这里把能并发执行的基本单位称为事物。在创建一个事物T时，便为它打上一个时间邮戳（timestamp）e（T），并建立一个严格的按时间排序的事物序列。如果某一资源R1已被事物T1占有而又被事物T2请求时，检测机构比较两个事物的时间邮戳，如e（T2）

综上所述我们可以知道，对于分布式环境下的死锁检测，所付出的通信开销是非常大的，而且还可能出现虚假死锁。所以我们在实际应用中，主要还是采用预防死锁的方法。

参考文献

[1]屠祁，屠立德等著，《操作系统基础》，北京：清华大学出版社，2000年9月，第120～160页

[2]何炎祥，宋文欣，彭锋编著，《高级操作系统》，北京：科学出版社，1999年4月，第178～281页