氢原子百科 
死锁（Deadlock）是指多个进程因竞争资源而造成的一种互相等待对方手里的资源的僵局，其使得各个进程都被阻塞，即若无外力干涉，这些进程都无法向前推进。[4][5]出现死锁时，系统必然同时满足互斥条件、请求和保持条件、不可抢占条件和循环等待这四个条件。[2]一旦死锁发生，整个系统将停滞或做空操作，操作员难以察觉，从而造成资源浪费。[6]
1965年，荷兰计算机科学家艾兹赫尔·韦伯·戴克斯特拉（Edsger Wybe Dijkstra）[7]在研究银行家算法的过程中，首次提出了死锁问题，以探索银行家如何安全地将有限资金借给多个客户。这一问题随后引起了广泛关注，并被众多科学家进一步研究。[1]1971年，考夫曼（E. G. Coffman）等人在分析了大量死锁现象后总结了产生死锁的4个必要条件，并给出了有关多个资源实例的死锁检测算法。[8]1973年，霍华德（Howard）提出了死锁综合处理的策略，即把系统中的资源分为几大类，整体上采用资源顺序分配法，再根据每类资源的特点选择最适合的方法。[9][10]20世纪80年代以后，各种死锁检测、死锁解除、死锁避免等算法得到了广泛的应用和研究，涌现了大量的相关研究成果。[3]
并行进程的执行改善了系统资源的利用率，提高了系统的处理能力，[1]但同时也可能产生由于进程资源竞争或推进顺序不当，使系统进入死锁状态的问题。[5]随着云计算和分布式系统的发展，死锁问题日益普遍，有效处理和预防死锁是确保系统效率和可靠性的核心挑战。[11]
发展历程
1965年，荷兰计算机科学家E.W.Dijkstra在研究银行家算法时提出了死锁问题，并提出了单个资源类型的死锁避免的银行家算法。[3]银行家算法（Banker's Algorithm）是Dijkstra为T.H.E操作系统[注1]设计的一种避免发生死锁的算法，该算法通过预测未来可能的资源请求，即在死锁形成之前进行评估，从而有效避免产生死锁。[13]Banker's Algorithm需要检查申请者对各类资源的最大需求量，如果系统现存的各类资源可以满足它对各类资源的最大需求量，就满足当前的申请。[14]
1971年，美国科学家Coffman等人在"System Deadlocks"中总结了产生死锁的4个必要条件：互斥条件、请求和保持条件、不可抢占条件、循环等待条件。[1]Coffman在该文章中还给出了有关多个资源实例的死锁检测算法，[3]该算法使用了一些随时间变化的数据结构，且其检测算法为需要完成的所有进程探究各种可能的分配序列。[8]
1972年，加拿大科学家霍尔特（R. C. Holt）在其论文 “Some Deadlock Properties of Computer Systems"中第一次将死锁问题用分配图模型[注2]来形式化，并讨论了饥饿问题。[3]饥饿和死锁一样，是一种由于资源竞争所导致的进程无法向前推进的现象，但饿死现象的进程不仅可能处于等待态，也可能处于运行态或就绪态，且进程等待的是会被释放但不会分配给自己的资源。[5]
20世纪80年代以后，随着计算机系统规模的扩大和复杂度的增加，死锁问题逐渐成为实际系统中需要解决的重要问题。各种死锁检测、死锁解除、死锁避免等算法得到了广泛的应用和研究，涌现了大量的相关研究成果。例如，1987年，美国科学家巴赫（M. J. Bach）讨论了传统UNIX内核如何处理死锁。1998年，加利福尼亚大学卡勒（D. E. Culler）等教授讨论了网络中死锁问题的解决方案，其综合考虑资源管理、协议设计、算法优化等多个方面来避免死锁的发生，以确保网络的稳定性和可靠性。[3]2003年，费尔利·迪金森大学教授莱文（G. N. Levine）进一步给出了有关死锁处理方面的研究，其对死锁的不同状态进行了更精确的分类和定义。[16]
进入21世纪以后，随着云计算、大数据、物联网等新技术和新应用场景的兴起，死锁问题在分布式系统、并行计算、嵌入式系统等领域变得更加复杂和重要。[11]随着进程的数量增多，程序的多线程化，持久文件和数据库服务器更受重视，死锁问题越来越普遍。新的死锁检测算法、预防机制和容错机制在不断涌现，以应对不断变化的系统环境和需求。[17]
系统资源的竞争
在系统中，某些非抢占式资源（例如磁带机和打印机）的数量有限，无法同时满足多个进程的需求。这种情况下，进程在运行过程中可能会因为争夺这些有限资源而陷入死锁。死锁通常发生在对非抢占式资源的竞争中，而抢占式资源（如CPU和主存）的竞争则不会导致死锁。[18]
进程推进顺序非法
请求和释放资源的顺序不当，也同样会导致死锁。例如，进程分别保持了资源，而 申请资源、申请资源时，两者都会因为所需资源被占用而阻塞，于是导致死锁。[18]
产生死锁的必要条件
产生死锁必须同时满足包括互斥条件、请求和保持条件、不可抢占条件和循环等待条件在内的4个条件，只要其中任一条件不成立，死锁就不会发生。[2]
互斥条件：进程要求对所分配的资源进行排他性使用，[2]即系统中的资源在任何时刻只能被一个进程使用，其余请求该资源的进程只能等待。[19]请求和保持条件：一个进程新申请的资源已被其他进程占有，此时请求进程被阻塞，但在等待申请资源的过程中对己有资源保持不放。[2][19]不可抢占条件：进程已获得的资源在未使用完之前，不能被其他进程抢占，只能由获得该资源的进程主动释放。[2]循环等待条件：系统中存在一种进程—资源的循环等待链，链中每个进程已获得的资源同时被链中下一个进程所请求。[19]例进程集合中的正在等待一个占用的资源，正在等待已占用的资源，......，正在等待已被占用的资源。[2]
死锁的预防
预防死锁是通过设置某些限制条件，去破坏产生死锁的四个必要条件中的一个或几个以避免产生死锁。[20]在产生死锁的四个必要条件中，由于互斥条件是非共享设备所必须的，不仅不能改变，还应加以保证，因此死锁的预防主要是通过破坏请求和保持条件、不可抢占条件以及循环等待条件来实现。[21]
破坏“请求和保持”条件
系统通过保证当一个进程在请求资源时，该进程不能持有不可抢占资源来破坏“请求和保持”条件。该保证可通过以下两种协议实现。[21]
第一种协议
协议规定进程在开始前一次性申请所有必需资源。如果系统不能满足全部资源需求，则不分配任何资源，直至所有资源可用。这避免了“请求”和“保持”死锁条件，简单、易行且安全，但可能导致资源浪费和进程饥饿。[21]
第二种协议
改进版协议允许进程获取初期资源后开始运行，随后根据需要逐步释放已用资源并请求新资源。例如，一个处理任务的进程先复制数据，完成后释放资源再请求下一步所需资源。这种方式使进程更快完成任务，提升资源效率，减少了饥饿风险。[21]
破坏“不可抢占”条件
协议规定，当持有特定不可被抢占资源的进程发出新资源请求而未获满足时，必须释放其当前保有的所有资源。后续再根据需要重新申请资源，以此方法破坏“不可抢占”条件。该方法实现起来比较复杂，且可能会造成进程前一阶段工作的失效。同时，还可能使进程的执行因为反复地申请和释放资源致而被无限地推迟，从而延长了进程的周转时间，增加了系统开销，降低了系统吞吐量。[21]
破坏“循环等待”条件
通过对所有资源类型进行排序并赋予唯一序号，可以破坏“循环等待”条件。设定一个资源序列，每种资源赋予一个序号。例如，磁带驱动器、硬盘和打印机分别赋予不同的序号，函数按如下形式来定义:
协议规定进程按照资源的序号递增顺序请求资源。进程初始可以请求任意资源Ri，后续仅在条件下，才能请求资源。若需多个相同资源，需一次性请求。例如，进程若需打印机和磁带机，需先请求序号较低的磁带机。该策略避免资源分配图中形成环路，破坏“循环等待”条件。[21]
死锁的避免
通过在资源的动态分配过程中，用某种方法防止系统进入不安全状态，从而避免发生死锁。[2]
系统安全状态
在死锁避免方法中，把系统的状态分为安全状态和不安全状态。当系统处于安全状态时，可避免发生死锁。反之，系统可能进入死锁状态。在该方法中，允许进程动态地申请资源，但系统在进行资源分配之前，应先计算此次资源分配的安全性。若此次分配不会导致系统进入不安全状态，才可将资源分配给进程，否则，令进程等待。[22]
系统安全状态是指系统能按某种进程推进顺序为每个进程分配其所需资源，直至满足每个进程对资源的最大需求，使每个进程都可顺利地完成，其中被称为安全序列。如果系统无法找到这样一个安全序列，则称系统处于不安全状态。[22]
例如，系统中有三个进程，以及12台磁带机。各进程对磁带机的总需求和在时刻已获得资源如下表所示，[22]
| 进程 | 最大需求 | 已分配 | 可用 |
|---|---|---|---|
| P1 | 10 | 5 | 3 |
| P2 | 4 | 2 | |
| P3 | 9 | 2 |
此时存在一个安全序列，使得系统按此进程序列分配资源，可保证每个进程都顺利完成。例如先为进程分配给两台磁带机，使之继续运行，其完成便可释放出4台磁带机，于是剩余可用磁带机增值5台；再将5台磁带机全部分配给进程，待运行完成后，释放磁带机，是剩余可用磁带机增值10台；之后进程可获得足够的资源以运行，从而使三个进程都能顺利完成。因此，在时刻系统是安全的。[22]
银行家算法
该算法要求每一个新进程在进入系统时，必须申明其在运行过程中可能需要的每种资源类型的最大单元数目，其数目不应超过系统所拥有的资源总量。而当进程请求一组资源时，系统需先确定是否有足够的资源分配给该进程，并进一步计算若将这些资源分配给该进程，是否会使系统处于不安全状态。若系统有足够的资源分配，并不会导致系统进入不安全状态，则将资源分配给该进程，否则让进程等待。[22]
为实现银行家算法，系统中需设置四个数据结构，分别用来描述系统中可利用的资源、所有进程对资源的最大需求、系统中的资源分配，以及所有进程还需要多少资源。[22]
| 名称 | 定义 | 说明 |
|---|---|---|
| 可利用资源向量 Available | 一个含有个元素的数组，其中的每一个元素代表一类可利用的资源数目，数值随该类资源的分配和回收而动态地改变，其初始值是系统中所配置的该类全部可用资源的数目 | ，则表示系统中现有类资源个类资源可用 |
| 最大需求矩阵 Max | 一个的矩阵，定义了系统中个进程中的每一个进程对类资源的最大需求 | ，表示进程i需要类资源的最大数目为 |
| 分配矩阵 Allocation | 一个的矩阵，定义了系统中每一类资源当前已分配给每一进程的资源数 | ，表示进程当前已获得个类资源 |
| 需求矩阵 Need | 一个的矩阵，表示每一个进程尚需的各类资源数 | ，表示进程i还需要个类资源才能完成任务 |
三个矩阵Max、Allocation、Need之间存在关系：[22]
死锁检测和解除
当系统中不采取死锁预防措施和死锁避免算法时，系统很可能会发生死锁。此时，系统应提供死锁检测算法用于检测系统状态，以确定系统中是否发生了死锁；以及死锁解除算法用于认定系统中已发生了死锁时，将系统从死锁状态中解脱出来。[23]
死锁的检测
死锁检测要求系统中必须保存有关资源的请求和分配信息，以及提供一种算法利用这些信息来检测系统是否已进入死锁状态。[23]
资源分配图
资源分配图是由一组结点和一组边所组成的一个对偶 ，[23]可以更精确地描述死锁,[24]定义和限制如下：
把分为两个互斥的子集，活动进程的集合和一组资源类型的集合，。[23][24]所有属于中的一个边，都连接着中的一个结点和中的一个结点，是资源请求边，由进程指向资源；是资源分配边，由资源指向进程。[23]
例，在下面的资源分配图中，用圆形表示进程，用矩形表示资源类型。由于可能有多个实例，矩形内的点的数量表示资源类型的实例数量。[24]
根据资源分配图的定义，证明了如果分配图没有环，那么系统就没有进程死锁。[24]
死锁定理
简化资源分配图可检测系统状态S是否为死锁状态。以下面所示的资源分配图为例，简化方法如下：[23]
在资源分配图中，找出既不阻塞又不孤立的进程（找出一条有向边与它相连，且该有向边对应资源的申请数量小于或等于系统中已有的空闲资源数量，如在图 (a)中，没有空闲资源，有一个空闲资源，若所有连接该进程的边均满足上述条件，则这个进程能继续运行直至完成，然后释放它所占有的所有资源），消去它所有的请求边和分配边，使之成为孤立的节点。在图 (a)中，是满足这一条件的进程节点，将的所有边消去，便得到图 (b)所示的情况。[23]进程 所释放的资源，可以唤醒某些因等待这些资源而阻塞的进程，原来的阻塞进程可能变为非阻塞进程。在图 (a)中，就满足这样的条件。根据步骤1中的方法进行一系列简化后，若能消去图中所有的边，则称该图是可完全简化的，如图(c)所示。[23]
为死锁的条件是当且仅当状态的资源分配图是不可完全简化的，该条件为死锁定理。[23][25]
死锁的解除
一旦检测出死锁，就应立即采取相应的措施来解除死锁。死锁解除的主要方法有资源剥夺法和撤销进程法。[25]
资源剥夺法：挂起某些死锁进程，并抢占它的资源，将这些资源分配给其他的死锁进程。但应防止被挂起的进程长时间得不到资源而处于资源匮乏的状态。[26]撤销进程法：强制撤销部分、甚至全部死锁进程并剥夺这些进程的资源。撤销的原则可以按进程优先级和撤销进程代价的高低进行。这种方式实现简单，但付出的代价可能很大，因为有些进程可能已经接近结束，一旦被终止，以后还得从头再来。[25]
死锁的处理策略
处理死锁的策略有预防死锁、避免死锁、死锁的检测，各有优缺点如下：[10]
| 方法 | 资源分配策略 | 各种可能模式 | 主要优点 | 主要缺点 |
|---|---|---|---|---|
| 死锁预防 | 保守，宁可资源闲置 | 一次请求所有资源，资源剥夺，资源按序分配 | 适用于突发式处理的进程，不必进行剥夺 | 效率低，初始化时间延长；剥夺次数过多；不便灵活申请新资源 |
| 死锁避免 | 是预防和检测的折中(在运行时判断是否可能死锁) | 寻找可能的安全允许顺序 | 不必进行剥夺 | 须知道将来的资源需求；进程不能被长时间阻塞 |
| 死锁检测 | 宽松，只要允许就分配资源 | 定期检查死锁是否已经发生 | 不延长进程初始化时间，允许对死锁进行现场处理 | 通过剥夺解除死锁，造成损失 |
死锁综合策略
上述策略中，无论哪种方法都无法适用于各类资源。1973年，Howard对此提出了死锁综合处理的策略。[9]其具体步骤为：首先根据资源特性把资源分成几大类；为了预防资源类之间由于循环等待产生死锁，整体上采用资源线性排序策略；最后对每类资源根据其特点择最适合的方法。[10][9]
资源分类：根据资源特性对资源进行分类，将各种资源归入若干个不同的资源类中，如外存交换区空间资源、外部设备资源、内存资源等。[28]资源线性排序方法：对于具有资源层次的系统，一种比较理想的处理死锁的综合措施是资源的线性排序方法，即对内部资源，通过破坏循环等待条件来预防死锁。[29]如 I/O通道，可采用基于资源排序的预防策略。[10]针对性策略选择：对由不同类资源竞争引起的死锁问题，使用最适合于它的办法。例如，对主存储器使用剥夺资源的方法，以防止死锁的产生，因为主存储器空间本质上是可以被剥夺的；对作业资源，可以使用死锁避免算法；对交换空间，可以采用预分配措施。[29]
死锁与饥饿
在一个动态系统中，进程会不断地请求资源和释放资源，并发执行向前推进。进程申请资源后，申请的资源正在被其他进程使用，则需要等待，当等待时间给进程的推进和响应带来明显的影响时，就称发生进程的饥饿。当饥饿到一定程度的进程所赋予的任务即使完成也不再具有实际意义时，称该进程被饿死。[5]
死锁和饥饿的共同点是都是由于资源竞争所导致的进程无法向前推进的现象，但从进程状态考虑，参与死锁的进程都处于等待态，而发生饿死现象的进程不仅可能处于等待态，也可能处于运行态或就绪态；另外死锁进程等待的是永远不会被释放的资源，而饿死进程等待的是会被释放但不会分配给自己的资源。[5]
Windows
在 Windows 操作系统中，针对死锁问题，有以下具体策略：
资源管理和分配：系统中大多数软硬件资源由系统统一管理和分配，进程请求资源时，先通过系统调用向系统提出申请，系统根据资源情况按一定的策略来实施分配。[30][31]同步机制：系统中的少数资源可由程序自行使用，系统提供一些同步机制来协调竞争以避免各并发进程因为争夺资源而发生混乱。[30][31]资源的动态分配：为避免死锁，系统对进程所发出的每一个申请资源命令加以动态地检查，并根据检查结果决定是否进行资源分配，如银行家算法。[30]
Linux
在 Linux 操作系统中，针对死锁问题，有以下具体策略：
进程调度策略：为了能让进程有效地使用系统资源,又能使进程有较快的响应时间,就需要对进程的切换调度采用一定的调度策略。例如，在 Linux0.12中采用了基于优先级排队的调度策略。[32]优先级调整：当系统检测到死锁可能发生时，可以通过提高或降低进程或线程的优先级来打破死锁循环。例如，进程可以通过系统调用sched_setscheduler改变自己的调度策略，通过系统调用sys_setpriority、sys_nice改变优先数。[33]
可抢占资源与不可抢占资源
计算机系统中的资源按照占用方式，可分为可抢占资源与不可抢占资源。[34]
可抢占资源：指某进程在获得该资源后，即使该进程并没有使用完该资源，也可能被抢夺走，被其他进程剥夺使用，因而不会产生死锁。例如，处理机是一种特殊的资源，一个处理机在一段时间内只能分配给一个进程，但优先级别高的进程可以抢占优先级别低的进程处理机。[34]不可抢占资源：指某进程在获得该资源后，在没有主动释放该资源前，其他进程不可强行抢夺走，只能等该资源被释放后才能使用。例如，打印机正在打印一个任务，任务未结束前，是无法打印其他任务的。[34]
可重用资源和可消耗资源
计算机系统中的资源按照资源的利用方式，可分为可重用资源和可消耗资源。[34]
可重用资源：一种可供用户重复使用多次的资源。具有以下性质：
①每一个可重用资源中的单元只能分配给一个进程使用，不允许多个进程共享。[35]
②进程在使用资源时需要遵循的使用顺序为：申请资源，若进程申请资源失败，则该进程被阻塞或循环等待；使用资源，即该进程对资源进行操作；释放资源，该进程使用完资源后自己主动释放资源。[35]
③系统中每一类可重用资源中的单元数目是相对固定的，进程在运行期间既不能创建也不能删除它。[35]
可消耗资源：又称为临时性资源，是由进程在运行期间动态创建和消耗的。具有以下性质:
①每一类可消耗资源的单元数目在进程运行期间是可以不断变化的。[35]
②进程在运行过程中可以不断地创建可消耗资源的单元，将它们放入该资源类的缓冲区中以增加该资源类的单元数目。[35]
③进程在运行过程中可请求若干个可消耗资源，用于进程自己的消耗，不再将它们返回给该资源类中。[35]
分布式系统中的死锁检测
分布式数据库在提供强大计算和存储能力的同时，由于在各种事务处理过程中大多采用封闭技术，以及大量用户频繁访问分布式数据库，容易发生同资源异操作的问题，从而导致分布式数据库死锁。 若计算机系统无法及时检测到死锁，死锁持续时间不断延长，最终会导致系统瘫痪。 [36]目前，已有多种针对分布式系统的死锁检测算法被提出。如闫盛楠教授于2020年提出的提出一种基于关联规则挖掘的检测方法，但是该方法受到空间爆炸影响不能及时更新分布式数据库死锁集合，导致死锁检测精准度较低。[37]基于静态分析的死锁检测方法的提出有效提高死锁检测的精准度，但其在理论和工程上的难点方面还有很多有待研究和改进的地方，如完善分布式数据库敏感数据分析流程，以提高检测效率。[38]
新型动态死锁分析方法
常见的死锁检测方法有模型检测、符号执行、静态分析和动态分析四种。[39]其中，动态分析通过分析程序运行轨迹及研究锁授权顺序中存在的特定模式，从而进行死锁检测，其具有分析效率高、可自动化进行的优点，但同时由于对锁的授权／释放操作及其执行场景难以准确刻画，可能导致误报现象。因此，如何减少误报，提高准确率，对于死锁检测具有重要意义。[40]
Linux操作系统用户态死锁检测方法
参考资料 42
- 参考 1
- 参考 2
- 参考 3
- 参考 4
- 参考 5
- 参考 6
- Edsger Wybe Dijkstra — ACM
- 参考 8
- 参考 9
- 参考 10
- 参考 11
- 参考 12
- 参考 13
- 参考 14
- 参考 15
- 参考 16
- 参考 17
- 参考 18
- 参考 19
- 参考 20
- 参考 21
- 参考 22
- 参考 23
- 参考 24
- 参考 25
- 参考 26
- 参考 27
- 参考 28
- 参考 29
- 参考 30
- 参考 31
- 参考 32
- 参考 33
- 参考 34
- 参考 35
- 参考 36
- 参考 37
- 参考 38
- 参考 39
- 参考 42
注释
- T.H.E 操作系统：由 C. Strachey、C. Morris、D. Hartley 等于 1968 年在英国牛津大学计算机实验室开发的一个早期操作系统。[12]
- 分配图模型：即资源分配图，一种用于描述资源分配和死锁问题的图形模型。通过分析分配图模型，可以识别潜在的死锁情况，并采取相应的措施来避免或解决死锁问题。[15]