死锁的概念

在共享资源的系统中，防止访问冲突极为重要，但这有可能导致另一个问题：死锁。当通过"锁定"一个资源来防止任何其它线程访问这个资源，以避免竞争条件时，必须对设计进行评估，确保绝对不会发生死锁。死锁测试通常没有什么效果，因为只有某种特定顺序的资源锁定才可能产生死锁，而一般的测试不大可能导致这种顺序。



死锁只不过是多线程环境中一个锁定资源的问题。以下四个条件必须同时具备，才会发生死锁。防止其中任何一个条件出现都可以排除死锁的可能性：



* 相互排除---每次只有一个线程可以使用某个锁定的资源；


* 非先占---其它线程不能强迫另一个线程释放资源；


* 保持并等待---线程在等待需要的其它任何资源时，保持它们已经锁定的资源；


* 循环等待---存在一个线程循环链，其中每个线程保持链中下一个线程所需要的资源。



图1中的资源分配图是死锁问题的一个例子。线程1首先锁定Buf资源，在保持Buf时，指向Bus，然后是Mux。如果线程1一直运行到结束，它最终将释放所有这些资源。线程2运行时，必须指向Bus、Sem，最后是Mux。线程3运行时，需要Sem和Buf。



在这个设计实例中，无法保证任何一个线程能够在另一个线程开始执行之前结束。如果一个线程不能得到需要的某个资源，它将挂起执行(阻塞)，直到该资源有效为止。在系统运行过程中，各线程都将对资源进行锁定或解锁。由于各线程运行和指向其资源的相对时序各不相同，有可能出现由于各个线程正在等待被其它线程保持的资源，导致所有线程都无法运行的情况。例如，如果线程1保持Buf，线程2保持Bus，而线程3已经取得了Sem，则系统将发生死锁。因为按照从Buf到Bus到Sem，再回到Buf的线程分配箭头，循环等待条件得到了满足。



潜在死锁问题识别出来之后，通常很容易进行修复。在图2中，对线程3进行了修改，使其在得到Sem之前首先设法指向Buf。这样，循环等待的条件就被打破了，系统将不会再受到死锁的影响。



一些操作系统过多地使用消息传递来进行线程间通信和同步。在这些类型的系统中，当某线程向另一个线程传递消息时，发送线程将阻塞，直到从接收线程收到响应为止。接收线程通常将一直阻塞到从其它某个线程接收到一个消息为止。这些结构中也会发生死锁。为了给一个基于消息的操作系统建立一张资源分配图，我们利用消息通道来模拟分配的资源。图3是一个例子。线程2建立了通道T2 Ch，当它未因为等待这个通道上的一个消息而阻塞时，线程2就将"锁定"这个通道。当它阻塞并等待一个消息时，另一个线程可在这个通道上向它发送一个消息，并且这个消息将立即被接收到。



现在考虑下面这个系统：线程1指向Mutex并在通道T2 Ch上向线程2发送消息。在线程2中的某个地方，线程2在通道T3 Ch上向线程3发送消息。线程3也在通道T4 Ch上向线程4发送消息。在线程4中的某个地方，它也尝试指向Mutex，如果得不到，它就将阻塞。显然，各资源之间存在一条循环路径，这表明有可能发生死锁。例如，如果某一时刻线程1保持Mutex而线程4尝试指向它，线程4就将在Mutex上阻塞。然后当线程3尝试在通道T4 Ch上向线程4发送一个消息时，线程3将阻塞，等待来自线程4的应答(因为线程4是由于等待Mutex而阻塞，不是为了等待这个消息)。类似地，当线程2 尝试向线程3发送一个消息时，将被阻塞；线程1尝试向线程2发送一个消息时也将阻塞，由于它仍然保持着Mutex，所以系统将发生死锁。



对付死锁的最容易的办法是通过设计进行避免。采用以下任何一条设计约束都可排除死锁出现的可能性：



* 任意时刻线程锁定的资源不超过一个。

* 线程开始执行前就完全分配它所需的全部资源。

* 指向多个资源的线程必须按照一种系统范围的预设顺序来锁定(并释放)这些资源。



如果无法通过设计来避免死锁，则应该建立资源分配图。检查资源分配图可以识别潜在的死锁。通过仔细跟踪系统中的所有线程和它们锁定的共享资源，可以维护资源分配图并周期性地进行检查，及时发现循环等待的特征。



建立资源分配图需要识别每个受保护的共享资源，以及指向其中某一资源的所有线程。如果使用一个操作系统，可以采用下面的过程步骤：



1. 识别所有可能阻塞的系统调用，如Mutex_Lock()，每个受保护的共享资源总是有一些与访问它有关的阻塞调用。


2. 识别出获取共享资源的阻塞调用之后，在源代码中查找它们的各次调用情况。


3. 对于每次调用，记录下指向资源的线程名称和该资源的名称。通常调用本身将受保护的资源作为一个参数来传递，调用在源代码中所处的位置表明了哪个线程需要该资源。通过这种方式，可以识别出所有受保护的资源以及分配资源的线程。


4. 建立资源分配图，并检查是否有任何资源存在循环路径。当线程和共享资源较少时，画出资源分配图比较简单。在较为复杂的系统中，最好将这些信息输入分析表格，并编写一个宏来检查线程和资源分配结构，以识别潜在的死锁。编写好宏之后，就可以快速地对资源分配变化进行重新评估。编写宏时，可以忽略不会导致死锁的资源之间的循环。在表2所示的例子中，各种资源之间有许多循环，但只有线程6和线程7之间可能存在死锁。



在一些类型的系统中，预先确定每一个共享资源并建立分配图是不实际或不可能的。此时可以增加一些额外的代码，以便在系统运行时检测出潜在的死锁。许多不同的算法都致力于优化这个检测过程，但本质上它们几乎都动态地建立某种资源分配图。只要有线程请求、分配或释放资源，分配图就会被修改和检测，以确定是否存在表明潜在死锁的循环路径。



检测到某个死锁之后，唯一的克服方法是强迫线程释放关键的资源。通常，这意味着中断正保持着所需资源的线程。对于某些应用，这种方法可能是无法接受的。另一个有趣的解决方案是在运行时收集资源分配情况并进行事后分析处理，以确定在程序运行过程中是否有死锁情况发生。尽管这种方法并不能防止在运行时发生死锁，但它确实有助于在死锁出现后发现问题并进行修复。