【软件设计师考点】死锁

在深入探讨操作系统死锁之前，先来看一个生活中常见的场景：假设在一个繁忙的十字路口，四个方向的车辆都在等待通过。此时，A 方向的车辆进入了路口中央，想要左转，但被 B 方向直行的车辆挡住了；B 方向的车辆也进入了路口，想要右转，却被 C 方向的车辆阻碍；C 方向的车辆同样进入路口，准备左转，又被 D 方向的车辆拦住；而 D 方向的车辆进入路口后，想直行却被 A 方向的车辆堵住。这就导致了四个方向的车辆都无法前进，谁也动不了，形成了交通堵塞。

在操作系统中，死锁（Deadlock）就类似于这种交通堵塞的情况。当两个或多个进程在执行过程中，因争夺资源而造成一种互相等待的现象，若无外力作用，它们都将无法推进下去，此时系统就陷入了死锁状态。在这个过程中，每个进程都持有对方需要的资源，却又不愿意释放自己已持有的资源，从而导致所有进程都被阻塞，无法继续执行任务。

死锁产生的原因和条件

（一）死锁产生的原因

资源竞争：操作系统中的资源可分为多种类型，如打印机、内存、CPU 时间片等。当多个进程同时竞争这些有限的资源时，如果资源分配不当，就容易引发死锁。例如，系统中只有一台打印机，进程 A 和进程 B 都需要使用打印机进行打印任务。进程 A 先申请并获得了打印机资源，开始打印；此时进程 B 也请求打印机，但由于打印机已被进程 A 占用，进程 B 只能等待。如果进程 A 在打印完成之前，又请求其他资源（如内存），而该资源被进程 B 占用，并且进程 B 在释放内存之前也请求打印机，这样就形成了互相等待的局面，导致死锁的发生。同样，在内存资源分配中，如果多个进程对内存块的需求超过了系统的可用内存，并且分配算法不合理，也可能使进程因争夺内存而陷入死锁。

进程推进顺序不当：进程在执行过程中，请求和释放资源的顺序至关重要。不合理的进程推进顺序可能导致死锁的出现。假设有进程 P1 和进程 P2，它们共享资源 R1 和 R2。正常情况下，如果 P1 先请求 R1，再请求 R2，使用完后依次释放；P2 先请求 R2，再请求 R1，使用完后依次释放，这样不会发生死锁。但如果 P1 先请求 R1，此时 P2 请求 R2，接着 P1 请求 R2，而 R2 被 P2 占用，P1 等待；同时 P2 请求 R1，R1 被 P1 占用，P2 等待，这就形成了死锁。这种因进程推进顺序不当引发的死锁，在多进程并发执行的系统中较为常见，且难以调试和排查。

（二）死锁产生的四个必要条件

互斥条件：在操作系统中，许多资源具有互斥访问的特性，即一个资源在同一时间内只能被一个进程使用。以打印机为例，当一个进程正在使用打印机进行打印时，其他进程不能同时使用该打印机，必须等待打印机被释放后才能申请使用。这种互斥性是资源的固有属性，是保证数据一致性和完整性的必要条件，但同时也为死锁的产生提供了基础条件。如果资源可以被多个进程同时访问，就不会出现因争夺资源而导致的死锁问题。

请求与保持条件：当一个进程已经持有了至少一个资源，但又提出了新的资源请求，而该资源已被其他进程占有，此时请求进程就会被阻塞。但在阻塞期间，它对自己已获得的资源保持不放，这就可能导致死锁。比如，进程 A 已经获得了资源 R1，然后它请求资源 R2，而 R2 被进程 B 占用，进程 A 进入阻塞状态，但它仍然持有 R1。如果进程 B 在释放 R2 之前，也请求 R1，由于 R1 被进程 A 持有，进程 B 也会阻塞，这样就形成了死锁的潜在风险。

不可剥夺条件：进程已获得的资源在未使用完之前，不能被其他进程强行剥夺，只能由持有该资源的进程在使用完毕后自行释放。这意味着一旦某个进程占有了资源，其他进程就无法通过强制手段获取该资源，只能等待占有进程主动释放。例如，一个进程获得了内存块用于存储数据，在它完成数据处理并释放内存块之前，其他进程不能强行将该内存块夺走。这种不可剥夺性使得资源的分配和释放具有一定的稳定性，但也增加了死锁发生的可能性。如果资源可以被其他进程剥夺，那么死锁就有可能避免。

循环等待条件：这是死锁产生的关键条件，它指的是存在一组进程，它们之间形成了一种头尾相接的循环等待资源关系。以经典的哲学家就餐问题为例，假设有五位哲学家围坐在一张圆桌旁，每位哲学家面前有一碗面，每两位哲学家之间有一根筷子。哲学家只有同时拿起左右两根筷子才能吃面。如果每位哲学家都先拿起左边的筷子，然后等待右边的筷子，就会出现所有哲学家都拿着左边筷子，同时等待右边筷子的情况，形成一个循环等待链。在这个循环中，每个哲学家都在等待下一个哲学家放下筷子（释放资源），但由于他们都不会主动放下自己已持有的筷子，导致谁也无法吃面，系统陷入死锁状态。

死锁的危害

死锁一旦发生，会给操作系统和相关应用带来一系列严重的危害，对系统性能、资源利用率以及用户体验都将产生负面影响。

（一）系统性能急剧下降

当系统陷入死锁时，进程无法继续推进，CPU、内存等系统资源被大量占用却无法有效执行任务。这使得系统的整体响应速度变慢，原本能够快速处理的任务，现在需要等待更长的时间才能完成。在多任务处理环境中，其他正常运行的进程也会受到牵连，因为系统资源被死锁进程占用，它们得不到足够的资源来执行，导致整个系统的吞吐量大幅降低。比如在一个同时运行多个应用程序的计算机系统中，若出现死锁，可能会使原本流畅运行的办公软件、浏览器等应用程序变得卡顿，甚至无响应。

（二）资源利用率大幅降低

死锁导致资源被无效占用，无法被其他需要的进程使用，造成了极大的资源浪费。以打印机为例，若一个进程在死锁状态下持有打印机资源，其他进程即使急需打印文件也无法使用，导致打印机长时间闲置。内存资源也是如此，死锁进程占用的内存空间无法释放，使得其他进程可能因内存不足而无法正常运行，严重影响了系统资源的利用率，降低了系统的整体运行效率。

（三）任务无法完成，用户体验恶化

对于用户而言，死锁最直观的影响就是正在进行的任务无法完成。在日常使用计算机时，如果某个应用程序因死锁而停止响应，用户的操作将得不到任何反馈，可能导致用户的数据丢失、工作中断。比如在编辑文档时，若文档编辑软件发生死锁，用户未保存的内容可能会丢失，这对用户来说是非常糟糕的体验。在服务器端，死锁可能导致网站无法正常访问、在线服务中断等问题，严重影响用户对服务的满意度和信任度。

死锁的检测与解决方法

（一）死锁检测方法

资源分配图算法：资源分配图是一种用于表示系统中资源分配状态的图形化工具，它通过将进程和资源抽象为图中的节点，以及用有向边表示资源的请求和分配关系，来帮助我们直观地分析系统是否存在死锁。在资源分配图中，用圆圈表示进程，用方框表示资源。如果进程已经分配到了某个资源，就从该资源节点向进程节点画一条有向边；如果进程请求某个资源，则从进程节点向资源节点画一条有向边。

当构建好资源分配图后，通过分析图中是否存在环路来判断是否存在死锁。如果资源分配图中存在环路，且环路上的每个进程都在等待下一个进程所占有的资源，那么系统就可能处于死锁状态。以哲学家就餐问题为例，假设用 P1 - P5 表示五位哲学家（进程），用 R1 - R5 表示五根筷子（资源）。如果 P1 已经持有 R1，同时请求 R2；P2 持有 R2，请求 R3；以此类推，P5 持有 R5，请求 R1，这样就形成了一个环路，满足循环等待条件，表明系统可能发生了死锁。不过，需要注意的是，当资源类型有多个实例时，即使图中存在环，系统也可能通过资源的动态分配来避免死锁。

利用系统工具检测：在实际操作中，操作系统提供了多种工具来帮助检测死锁。在 Linux 系统中，常用的命令有 ps、top、lsof、pstack 等。ps 命令可以列出系统中当前正在运行的进程，包括进程 ID（PID）、进程状态、运行时间、CPU 使用率、内存使用率等详细信息，通过查看这些信息，可以初步判断进程是否处于异常状态。top 命令则能动态地监视系统中各个进程的资源占用情况，包括 CPU 使用率、内存占用、执行时间等，还能显示系统的整体负载，若发现某些进程长时间占用大量资源且状态异常，可能是死锁的征兆。lsof 命令用于查看哪些文件（包括设备文件、socket 等）被哪些进程打开，通过分析文件资源的占用情况，有助于发现因文件或资源争用导致的死锁。pstack 命令可以输出指定进程的线程堆栈，帮助分析死锁位置，当怀疑某个进程发生死锁时，使用 pstack 命令查看其堆栈信息，能找到线程间的依赖关系和等待情况。

在 Windows 系统中，任务管理器是一个常用的工具，在任务管理器的性能选项中可以监控线程和资源锁情况，通过查看进程的 CPU、内存等资源使用情况，以及线程的状态，来判断是否存在死锁。另外，Process Explorer 或 WinDbg 等调试工具也可以帮助检测死锁，它们提供了更详细的进程和线程信息，能深入分析系统中资源的分配和使用情况。

（二）死锁解决方法

死锁预防：死锁预防是通过破坏死锁产生的四个必要条件来避免死锁的发生。

- 破坏互斥条件：对于某些可以同时访问的资源，修改资源的访问方式，允许多个进程同时访问，从而打破互斥条件。例如，在一些文件系统中，对于只读文件，可以允许多个进程同时读取，而不是独占访问。不过，这种方法对于很多具有物理独占性的资源（如打印机）并不适用。

- 破坏请求与保持条件：可以要求进程在开始运行前一次性申请所有需要的资源，如果无法满足，则不分配任何资源，进程等待。例如，一个进程需要使用打印机和扫描仪两种资源，那么在进程启动时就申请这两种资源，若资源不足，进程就等待，直到所有资源都可用时再开始执行，这样就避免了进程在持有部分资源的情况下又请求其他资源而导致死锁。

- 破坏不可剥夺条件：当一个进程占有一些资源时，如果申请新的资源被拒绝，可以允许系统强制性地剥夺已占有的资源，分配给其他更需要的进程。比如，在实时操作系统中，对于一些优先级较高的任务，如果其资源需求未得到满足，可以剥夺优先级较低进程所占有的资源，以保证高优先级任务的正常执行。

- 破坏循环等待条件：对系统中的资源进行编号，规定进程只能按照编号递增（或递减）的顺序申请资源。例如，系统中有资源 R1、R2、R3，编号依次为 1、2、3，进程在申请资源时，只能先申请 R1，再申请 R2，最后申请 R3，这样就避免了循环等待的情况发生。

死锁避免：死锁避免是在资源动态分配过程中，通过合理的资源分配策略，确保系统始终处于安全状态，从而避免死锁的发生。银行家算法是一种经典的死锁避免算法。该算法的核心思想是模拟银行系统中资金的分配和回收，确保系统始终处于安全状态。它通过以下关键数据结构实现资源分配和管理：

- 可利用资源向量（Available）：表示系统中各类资源的剩余数量。

- 最大需求矩阵（Max）：表示每个进程对各类资源的最大需求数量。

- 分配矩阵（Allocation）：表示已经分配给每个进程的各类资源数量。

- 需求矩阵（Need）：表示每个进程还需要的各类资源数量，计算公式为 Need = Max - Allocation 。

在进行资源分配时，当进程提出资源请求，系统首先检查请求是否合法，即请求的资源数量小于等于进程的需求数量，且小于等于系统的可利用资源数量。若请求合法，尝试分配资源，将请求的资源数量从可利用资源向量中减去，并将分配矩阵相应元素加上请求的资源数量，然后进行安全状态判断。若系统处于安全状态，则资源分配成功；否则，撤销分配，恢复系统状态，拒绝资源请求。例如，系统中有三个进程 P1、P2、P3，三种资源 R1、R2、R3，初始状态下，Available = [3, 3, 2]，Max = [[7, 5, 3], [3, 2, 2], [9, 0, 2]]，Allocation = [[0, 1, 0], [2, 0, 0], [3, 0, 2]]，计算得到 Need = [[7, 4, 3], [1, 2, 2], [6, 0, 0]] 。此时，若 P1 请求资源 [0, 1, 0]，系统检查后发现请求合法，尝试分配后，Available 变为 [3, 2, 2]，Allocation 变为 [[0, 2, 0], [2, 0, 0], [3, 0, 2]]，再通过安全性算法判断系统是否安全，如果安全则正式分配，否则撤销分配。

3. 死锁解除：当检测到死锁发生后，需要采取措施来解除死锁。

资源剥夺法：挂起部分或全部死锁进程，并抢占它们的资源，将这些资源分配给其他需要的进程。例如，系统中进程 A、B、C 发生死锁，进程 A 持有资源 R1，进程 B 持有资源 R2，进程 C 持有资源 R3，且它们相互等待对方的资源。此时，可以挂起进程 A，剥夺其资源 R1，将 R1 分配给需要它的进程，使其他进程能够继续运行。但这种方法需要注意防止被挂起的进程长时间得不到资源而饥饿。

进程撤销法：强制撤销部分或全部死锁进程，并剥夺这些进程的资源。这种方法实现简单，直接终止死锁进程，释放其占用的资源。但可能付出较大的代价，因为有些进程可能已经运行了很长时间，完成了部分工作，结果被终止后还得重头再来。例如，一个进行复杂计算的进程在死锁时被撤销，其之前的计算成果就会丢失。

进程回退法：让一个或多个死锁进程回退到足以避免死锁的地步。这就要求操作系统要记录进程的历史信息，并设置还原点。比如，进程在执行过程中，每完成一个关键步骤就记录当前状态作为还原点，当发生死锁时，将进程回退到最近的一个还原点，重新执行。这种方法相对较为复杂，但可以保留进程已完成的部分工作，减少损失。

实际案例分析

为了更直观地理解操作系统死锁，来看一个在多线程编程中发生死锁的实际案例。

假设我们正在开发一个简单的文件管理系统，其中有两个线程，线程 A 和线程 B 。这个系统涉及对文件的读取和写入操作，并且为了保证数据的一致性，对文件操作进行了加锁处理。线程 A 的任务是先读取文件 1 的内容，然后写入文件 2；线程 B 的任务是先读取文件 2 的内容，然后写入文件 1 。

以下是简化后的代码示例（以 Python 语言为例）：

import threading

import time

# 创建两个锁对象，分别用于保护文件1和文件2

file1_lock = threading.Lock()

file2_lock = threading.Lock()

def thread_A():

file1_lock.acquire() # 线程A获取文件1的锁

print("线程A获取了文件1的锁")

time.sleep(1) # 模拟读取文件1的操作耗时

file2_lock.acquire() # 线程A尝试获取文件2的锁

print("线程A获取了文件2的锁")

try:

# 执行写入文件2的操作

print("线程A正在写入文件2")

finally:

file2_lock.release() # 释放文件2的锁

file1_lock.release() # 释放文件1的锁

def thread_B():

file2_lock.acquire() # 线程B获取文件2的锁

print("线程B获取了文件2的锁")

time.sleep(1) # 模拟读取文件2的操作耗时

file1_lock.acquire() # 线程B尝试获取文件1的锁

print("线程B获取了文件1的锁")

try:

# 执行写入文件1的操作

print("线程B正在写入文件1")

finally:

file1_lock.release() # 释放文件1的锁

file2_lock.release() # 释放文件2的锁

# 创建并启动线程A和线程B

thread_a = threading.Thread(target=thread_A)

thread_b = threading.Thread(target=thread_B)

thread_a.start()

thread_b.start()

# 等待两个线程执行完毕

thread_a.join()

thread_b.join()

死锁发生原因分析

资源竞争：线程 A 和线程 B 都需要访问文件 1 和文件 2 这两个资源，它们对这两个资源的竞争是死锁产生的根本原因。在这个案例中，文件 1 和文件 2 是有限的共享资源，并且在同一时间只能被一个线程访问，这就满足了死锁产生的互斥条件。

进程推进顺序不当：线程 A 先获取了文件 1 的锁，然后试图获取文件 2 的锁；而线程 B 先获取了文件 2 的锁，然后试图获取文件 1 的锁。这种不合理的资源请求顺序导致了循环等待的情况出现，满足了死锁产生的循环等待条件。当线程 A 持有文件 1 的锁并等待文件 2 的锁时，线程 B 持有文件 2 的锁并等待文件 1 的锁，两个线程相互等待对方释放锁，从而陷入死锁状态。

请求与保持条件：线程 A 在获取了文件 1 的锁后，没有释放该锁就去请求文件 2 的锁；线程 B 在获取了文件 2 的锁后，没有释放该锁就去请求文件 1 的锁。这符合死锁产生的请求与保持条件，即进程已经占有了至少一个资源，但又提出了新的资源请求，而该资源已被其他进程占有，此时请求进程阻塞，但又对自己已获得的其他资源保持不放。

不可剥夺条件：在 Python 的线程锁机制中，一旦一个线程获取了锁，其他线程不能强行剥夺该锁，只能等待持有锁的线程主动释放。这满足了死锁产生的不可剥夺条件，进一步加剧了死锁的形成。

死锁检测过程

使用工具：在 Python 中，可以使用threading.enumerate()函数来获取当前活动的线程列表，然后通过分析线程的状态和持有锁的情况来判断是否发生死锁。此外，也可以借助一些调试工具，如pstack（在 Linux 系统中）或WinDbg（在 Windows 系统中），来查看线程的堆栈信息，找出死锁的线索。

分析线程状态：通过threading.enumerate()函数获取到线程列表后，检查每个线程的状态。如果发现有线程处于WAITING或BLOCKED状态，并且它们相互等待对方持有的锁，就有可能发生了死锁。例如，在上述案例中，通过查看线程状态，会发现线程 A 和线程 B 都处于BLOCKED状态，线程 A 等待文件 2 的锁，而该锁被线程 B 持有；线程 B 等待文件 1 的锁，而该锁被线程 A 持有，这就明确表明系统发生了死锁。

死锁解决方法

修改加锁顺序：为了避免死锁，可以让线程按照相同的顺序获取锁。例如，让线程 A 和线程 B 都先获取文件 1 的锁，再获取文件 2 的锁。修改后的代码如下：

import threading

import time

file1_lock = threading.Lock()

file2_lock = threading.Lock()

def thread_A():

file1_lock.acquire()

print("线程A获取了文件1的锁")

time.sleep(1)

file2_lock.acquire()

print("线程A获取了文件2的锁")

try:

print("线程A正在写入文件2")

finally:

file2_lock.release()

file1_lock.release()

def thread_B():

file1_lock.acquire()

print("线程B获取了文件1的锁")

time.sleep(1)

file2_lock.acquire()

print("线程B获取了文件2的锁")

try:

print("线程B正在写入文件1")

finally:

file2_lock.release()

file1_lock.release()

thread_a = threading.Thread(target=thread_A)

thread_b = threading.Thread(target=thread_B)

thread_a.start()

thread_b.start()

thread_a.join()

thread_b.join()

通过这种方式，破坏了死锁产生的循环等待条件，从而避免了死锁的发生。

2. 使用超时机制：为锁的获取操作设置一个超时时间，如果在规定时间内未能获取到锁，线程就放弃获取并释放已持有的锁。在 Python 中，可以使用acquire(timeout=)方法来实现超时机制。修改后的代码如下：

import threading

import time

file1_lock = threading.Lock()

file2_lock = threading.Lock()

def thread_A():

if file1_lock.acquire(timeout=5): # 设置超时时间为5秒

print("线程A获取了文件1的锁")

time.sleep(1)

if file2_lock.acquire(timeout=5):

print("线程A获取了文件2的锁")

try:

print("线程A正在写入文件2")

finally:

file2_lock.release()

file1_lock.release()

else:

print("线程A获取文件2的锁超时，释放文件1的锁")

file1_lock.release()

else:

print("线程A获取文件1的锁超时")

def thread_B():

if file2_lock.acquire(timeout=5):

print("线程B获取了文件2的锁")

time.sleep(1)

if file1_lock.acquire(timeout=5):

print("线程B获取了文件1的锁")

try:

print("线程B正在写入文件1")

finally:

file1_lock.release()

file2_lock.release()

else:

print("线程B获取文件1的锁超时，释放文件2的锁")

file2_lock.release()

else:

print("线程B获取文件2的锁超时")

thread_a = threading.Thread(target=thread_A)

thread_b = threading.Thread(target=thread_B)

thread_a.start()

thread_b.start()

thread_a.join()

thread_b.join()

在这个修改后的代码中，如果线程 A 或线程 B 在 5 秒内未能获取到所需的锁，就会放弃获取并释放已持有的锁，从而避免了死锁的发生。这种方法虽然增加了代码的复杂性，但提高了系统的稳定性和可靠性。

总结与展望

操作系统死锁是多进程并发环境下不可忽视的问题，它源于资源竞争和进程推进顺序不当，互斥、请求与保持、不可剥夺、循环等待这四个条件同时满足时就会引发死锁。死锁一旦发生，系统性能下降、资源利用率降低、任务无法完成，对系统和用户都产生严重影响。

为了解决死锁问题，我们探讨了多种检测和解决方法。资源分配图算法和系统工具能够帮助我们及时检测死锁，而死锁预防通过破坏死锁产生的必要条件，从根源上避免死锁；死锁避免如银行家算法，在资源动态分配中确保系统安全；死锁解除则在死锁发生后，通过资源剥夺、进程撤销、进程回退等方式恢复系统正常运行。

随着计算机技术的不断发展，操作系统的复杂度日益增加，死锁问题也将面临新的挑战和机遇。未来，死锁检测算法将朝着更高效、更智能的方向发展，能够实时、准确地检测出死锁状态，减少误报和漏报。死锁预防和避免策略也将更加优化，结合人工智能、机器学习等技术，根据系统的运行状态和资源使用情况，动态地调整资源分配策略，提高系统的稳定性和可靠性。同时，在分布式系统、云计算等新兴领域，死锁问题将变得更加复杂，需要进一步研究和探索适合这些环境的死锁解决方法。作为开发者和系统管理员，我们应深入理解死锁原理，不断学习和应用新的技术，以应对操作系统死锁带来的挑战，确保系统的高效、稳定运行。