C 语言死锁检测程序

在本文中，我们将讨论 C 语言中的死锁检测程序。但在讨论之前，我们必须了解死锁。

什么是死锁？

当一个组被困在一个进程中，因为每个人都占有着资源，同时又在等待其他方式来获取它们时，就会发生死锁。

示例

想象一下，只有一个轨道可用，两辆火车正朝着对方行驶。一旦两辆火车在对方前面停下，它们都无法移动。在操作系统中，当多个进程因为每个进程都在等待另一个进程占有的资源而无法继续执行时，就会发生死锁。当一个进程或线程因为请求了一个被另一个进程占有的系统资源而进入等待状态，而该另一个进程又在等待第一个进程占有的资源时。

死锁可能发生在几乎所有基于锁定的程序中。例外情况是 Berkeley DB Concurrent Data Store 产品，它以降低并发性为代价提供无死锁操作，以及所有访问关系数据库的控制流都是只读的场景。存在无死锁的数据访问模式，尽管它们极其罕见（例如，当程序覆盖现有数据库中的固定长度条目时）。

死锁检测器通过在“等待-获取”图（"waits-for" graph）中搜索循环来识别死锁。更准确地说，死锁检测器会检查当前被锁定的每个锁对象，并遍历锁表。每个条目都有一个等待锁的队列和一个不再可访问的锁持有者列表。每个对象上剩余空闲的锁持有者列表构成了一个偏序。每个持有锁的进程都排在每个等待锁的进程之后，因为每个持有锁的进程都必须先释放其锁，然后等待锁的进程才能继续。概念上，在分析完每个条目后，这些偏序会被拓扑排序。在拓扑排序中揭示出的任何循环中包含的锁持有者都无法继续执行。

死锁的条件

死锁的产生有几个条件。一些主要的死锁条件如下：

互斥（Mutual exclusion）： 资源一次只能被一个进程占用。换句话说，如果进程 P1 在某个时间点使用资源 R，那么进程 P2 就不能同时使用相同的资源 R。进程 P1 不能与进程 P2 同时使用资源 R，而进程 P2 拥有对它的访问权。

占有并等待（Hold & Wait）： “占有并等待”是指一个进程占有了一些资源，并请求其他由其他进程占有的资源的情况。例如，一个进程 P1 可能正在请求进程 P2 已经拥有的资源 R3，同时它自己又占有着资源 R1 和 R2。

不可抢占（Preemption is not permitted）： 另一个进程不能强制一个进程放弃它正在使用的资源。例如，如果资源 R 被进程 P1 使用，进程 P2 就不能强制抢占它。如果是这样，就不需要使用各种调度方法。要获取资源 R，进程 P2 必须先等待进程 P1 使用完毕。

防止死锁的策略

操作系统可以使用死锁避免策略来预防死锁。操作系统会在一个进程执行之前，跟踪该进程在其生命周期内所需的最大资源量。操作系统会在向任何进程提供任何新请求的资源之前，持续检查系统的状态。

在死锁避免过程中，操作系统会避免进入循环等待状态。如果系统在假想的未来进入僵局，任何资源请求都会被满足，以防止死锁。

根据最简单也是最有效的方法，进程应该定义它可能使用的每种类型的最大资源量。死锁预防方法会检查资源分配，并确保永远不会出现循环等待状态。

死锁的检测

操作系统通过这种行动计划预测未来的死锁。因此，它会定期运行死锁检测程序，并在检测到死锁时执行恢复计划。

识别死锁是操作系统的一个主要功能。

有两种检测方法。

死锁可以通过死锁检测来产生。然后，评估系统状态以判断是否发生了僵局并加以解决。通过算法跟踪资源分配和进程状态、回滚、重启一个或多个进程以及打破发现的死锁来完成。识别死锁很简单，因为操作系统的资源调度器知道每个进程锁定了哪些资源或正在积极寻求哪些资源。

1. 对于单个实例的每个资源
   在“等待-获取”图方法中，操作系统专注于形成一个环。它类似于资源分配图（RAG），但有一些区别。最常见的情况是它结合了 RAG 和“等待-获取”图。
2. 对于多个实例的每个资源
   对于包含多个实例的资源，我们使用安全算法（Safety algorithm），它实现了与银行家算法（Banker's algorithm）相同的逻辑。这里没有最大需求资源矩阵，只有已分配、可用和当前需求矩阵。

算法

C 语言实现死锁检测算法的程序

文件名：Deadlock.c

输出

Enter the number of processes: 3
Enter the number of resources: 3
Enter the total amount of Resource R1: 4
Enter the total amount of Resource R2: 5
Enter the total amount of Resource R3: 7
Enter the request matrix:
1 2 3
4 5 6
7 8 9
Enter the allocation matrix:
5 6 7 1 2 3 7 8 9
Deadlock detected