死锁预防与避免策略解析

# 死锁预防与避免策略解析 ## 1. 死锁问题概述 在缺乏检测和恢复死锁的算法时，系统可能陷入死锁却无法察觉。未被检测到的死锁会使系统性能下降，因为资源被无法运行的线程持有，且随着更多线程请求资源，会有更多线程陷入死锁，最终系统停止运行，需手动重启。尽管这种忽视死锁的方法看似不可行，但由于成本较低，且在许多系统中死锁发生频率较低，所以多数操作系统仍会采用。此外，一些用于解决其他活性问题（如活锁）的方法也可用于死锁恢复。 ## 2. 死锁预防 死锁的发生需要四个必要条件同时满足，通过确保至少一个条件不成立，就可以预防死锁。下面分别对这四个必要条件进行分析。 ### 2.1 互斥条件 互斥条件必须成立，即至少有一个资源是非共享的。共享资源不需要互斥访问，因此不会导致死锁，例如只读文件。但一般情况下，不能通过否定互斥条件来预防死锁，因为有些资源本质上就是非共享的，如互斥锁。 ### 2.2 占有并等待条件 为确保系统中不会出现占有并等待条件，要保证线程请求资源时不持有其他资源。可以采用以下两种协议： - **协议一**：每个线程在开始执行前请求并分配所有所需资源。但由于资源请求的动态性，这种方法对大多数应用来说不切实际。 - **协议二**：线程只有在没有资源时才能请求资源。线程可以请求并使用一些资源，在请求其他资源之前，必须释放当前分配的所有资源。 这两种协议有两个主要缺点：一是资源利用率可能较低，因为资源可能被分配但长时间未使用；二是可能会发生饥饿现象，需要多个热门资源的线程可能会无限期等待。 ### 2.3 不可抢占条件 死锁的第三个必要条件是已分配的资源不能被抢占。为确保该条件不成立，可以使用以下协议： - 如果线程持有某些资源并请求另一个无法立即分配的资源（即线程必须等待），则该线程当前持有的所有资源将被抢占，这些资源会被添加到线程等待的资源列表中。只有当线程能够重新获得其原有资源以及请求的新资源时，才会重新启动。 - 当线程请求资源时，先检查资源是否可用。如果可用，则分配；如果不可用，检查资源是否被其他等待额外资源的线程持有。若是，则从等待线程中抢占资源并分配给请求线程；若资源既不可用也未被等待线程持有，请求线程必须等待。在等待过程中，其部分资源可能会被其他线程请求时抢占，线程只有在获得请求的新资源并恢复被抢占的资源后才能重新启动。 这种协议通常适用于状态容易保存和恢复的资源，如 CPU 寄存器和数据库事务，但一般不适用于互斥锁和信号量等容易发生死锁的资源。 ### 2.4 循环等待条件 前面三种死锁预防方法在大多数情况下不实用，但循环等待条件为解决死锁问题提供了一个可行的方案。可以通过对所有资源类型进行全序排序，并要求每个线程按递增顺序请求资源来避免循环等待。 设资源类型集合为 $R = \{R_1, R_2, ..., R_m\}$，为每个资源类型分配一个唯一的整数，定义一个一对一的函数 $F: R \to N$（$N$ 为自然数集）。可以通过为系统中的所有同步对象建立一个顺序来实现该方案。例如，在 Pthread 程序中，锁的顺序可以定义为： ```plaintext F(first mutex) = 1 F(second mutex) = 5 ``` 预防死锁的协议如下： - 每个线程只能按递增顺序请求资源。即线程可以先请求资源 $R_i$，之后只有当 $F(R_j) > F(R_i)$ 时才能请求资源 $R_j$。 - 线程请求资源 $R_j$ 时，必须释放所有满足 $F(R_i) \geq F(R_j)$ 的资源 $R_i$。如果需要同一资源类型的多个实例，必须一次性请求。 通过反证法可以证明，如果使用这两个协议，循环等待条件将不成立。但需要注意的是，建立资源顺序本身并不能预防死锁，需要应用开发者编写遵循该顺序的程序。而且，在有大量锁的系统中建立锁顺序可能很困难，许多 Java 开发者采用 `System.identityHashCode(Object)` 方法来确定锁的获取顺序。此外，如果锁可以动态获取，强制锁顺序并不能保证预防死锁。 下面是一个死锁示例代码： ```java void transaction(Account from, Account to, double amount) { mutex lock1, lock2; lock1 = get_lock(from); lock2 = get_lock(to); acquire(lock1); acquire(lock2); withdraw(from, amount); deposit(to, amount); release(lock2); release(lock1); } ``` 当两个线程同时调用 `transaction` 函数，交换不同账户时，可能会发生死锁。 ## 3. 死锁避免 死锁预防算法通过限制资源请求来防止死锁，但可能导致设备利用率低和系统吞吐量下降。死锁避免的另一种方法是要求获取更多关于资源请求的信息，系统根据这些信息决定线程是否应该等待，以避免未来可能的死锁。下面介绍几种死锁避免算法。 ### 3.1 Linux Lockdep 工具 虽然确保资源按正确顺序获取是内核和应用开发者的责任，但可以使用一些软件来验证锁的获取顺序。Linux 提供了 `lockdep` 工具，用于验证内核中的锁顺序。该工具具有丰富的功能，例如： - 系统动态维护锁的获取顺序，如果检测到锁的获取