面试题：并发与同步：死锁检测与预防机制深度剖析

Question

假设你正在开发一个大型多线程应用程序，描述你会采用哪些策略来检测和预防死锁。详细说明每种策略的原理、适用场景以及可能存在的局限性。

Answer 1

死锁检测策略

1. 原理：
   • 资源分配图算法：通过构建资源分配图，该图由进程节点和资源节点组成。进程对资源的请求和分配关系通过有向边表示。定期检查此图是否存在环，若存在环则可能存在死锁。例如，进程P1请求资源R1，资源R1当前被进程P2占用，而P2又请求P1占用的资源R2，形成环就可能导致死锁。
   • 超时检测：为每个资源请求设置一个超时时间。当一个进程请求资源超过这个时间仍未获取到，就认为可能发生死锁。例如，进程请求一个锁，如果在10秒内没有获取到，就触发检测机制。
2. 适用场景：
   • 资源分配图算法：适用于资源类型和进程数量相对稳定且可清晰建模的场景，如数据库事务处理系统，其中资源类型（如数据表锁）和进程（事务）相对明确。
   • 超时检测：适用于对响应时间有一定要求，且资源竞争情况不是特别复杂的场景，例如网络服务器处理请求时，对每个请求资源的操作设置超时时间。
3. 局限性：
   • 资源分配图算法：对于大规模复杂系统，资源分配图的构建和环检测计算成本高。而且，即使检测到环，也不一定真正发生死锁，可能只是潜在死锁情况，存在误判。
   • 超时检测：超时时间设置困难，设置过短可能导致正常的资源等待被误判为死锁；设置过长则不能及时发现死锁。同时，它无法检测出多个进程互相等待但未超时的死锁情况。

死锁预防策略

1. 原理：
   • 破坏死锁的四个必要条件：
     • 互斥条件：使资源可共享使用，不满足互斥条件。但很多资源本身特性决定不能共享，如打印机。
     • 占有并等待条件：要求进程在开始执行前一次性申请所有需要的资源，避免在占有部分资源时等待其他资源。例如，一个进程需要资源A、B、C，开始就申请这三个资源，若不能全部获取则不占用任何资源。
     • 不可剥夺条件：允许操作系统剥夺进程已占有的资源。当一个进程申请资源得不到满足时，系统可从其他进程剥夺相应资源分配给该进程。
     • 循环等待条件：对资源进行排序，规定进程只能按照递增顺序申请资源。例如，资源按字母顺序排序，进程只能先申请A再申请B，以此类推。
2. 适用场景：
   • 破坏占有并等待条件：适用于资源需求可提前预知的场景，如批处理任务，在任务启动前能确定所需全部资源。
   • 破坏不可剥夺条件：适用于对数据一致性要求不是非常严格，允许资源临时剥夺的场景，如分时操作系统，可暂时剥夺某个进程的CPU资源分配给其他更紧急进程。
   • 破坏循环等待条件：适用于资源类型相对固定且数量有限的场景，如操作系统内存管理，对不同内存区域进行编号排序，进程按序申请。
3. 局限性：
   • 破坏占有并等待条件：可能导致资源利用率低，因为进程可能长时间占用资源但未全部使用，其他进程无法使用这些闲置资源。
   • 破坏不可剥夺条件：可能导致进程执行的不确定性，被剥夺资源的进程可能需要重新执行部分操作，影响系统性能和程序正确性。
   • 破坏循环等待条件：资源排序可能不合理，某些进程可能因资源排序限制，即使其他资源闲置也无法获取所需资源，导致资源浪费和进程饥饿。