图3 资源分配死锁图举例
现在考虑下面这个系统：线程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()，每个受保护的共享资源总是有一些与访问它有关的阻塞调用。
www.55dianzi.com
2. 识别出获取共享资源的阻塞调用之后，在源代码中查找它们的各次调用情况。
3. 对于每次调用，记录下指向资源的线程名称和该资源的名称。通常调用本身将受保护的资源作为一个参数来传递，调用在源代码中所处的位置表明了哪个线程需要该资源。通过这种方式，可以识别出所有受保护的资源以及分配资源的线程。
4. 建立资源分配图，并检查是否有任何资源存在 循环 路径。当线程和共享资源较少时，画出资源分配图比较简单。在较为复杂的系统中，最好将这些信息输入分析表格，并编写一个宏来检查线程和资源分配结构，以识别潜在的死锁。编写好宏之后，就可以快速地对资源分配变化进行重新评估。编写宏时，可以忽略不会导致死锁的资源之间的循环。在表1所示的例子中，各种资源之间有许多循环，但只有线程6和线程7之间可能存在死锁。
表1 循环死锁
在一些类型的系统中，预先确定每一个共享资源并建立分配图是不实际或不可能的。此时可以增加一些额外的代码，以便在系统运行时检测出潜在的死锁。许多不同的算法都致力于优化这个检测过程，但本质上它们几乎都动态地建立某种资源分配图。只要有线程请求、分配或释放资源，分配图就会被修改和检测，以确定是否存在表明潜在死锁的循环路径。
检测到某个死锁之后，唯一的克服方法是强迫线程释放关键的资源。通常，这意味着中断正保持着所需资源的线程。对于某些应用，这种方法可能是无法接受的。另一个有趣的解决方案是在运行时收集资源分配情况并进行事后分析处理，以确定在程序运行过程中是否有死锁情况发生。尽管这种方法并不能防止在运行时发生死锁，但它确实有助于在死锁出现后发现问题并进行修复。
还有一些工具也可以用来帮助发现代码中的死锁。例如，Solaris程序设计员可以采用 Sun公司的LOCkLint工具来对代码进行统计分析。它可以发现对锁定技术的不一致用法，识别引起竞争条件和死锁的许多原因。
上一篇：MCU 中输入/输出口的使用
