面试题：并发与同步：多核环境下死锁对系统性能的影响及缓解策略

Question

分析多核环境下死锁是如何影响系统整体性能的，包括对 CPU 利用率、任务执行效率等方面。针对这些影响，提出至少两种有效的缓解死锁的策略，并阐述其原理。

Answer 1

死锁对系统整体性能的影响

1. CPU 利用率：
   • 死锁发生时，参与死锁的线程或进程会一直占用 CPU 资源但无法推进执行，导致 CPU 资源被浪费。例如，两个线程互相等待对方释放资源，它们会持续占用 CPU 时间片，却不能完成任何有用的工作，使得 CPU 有效工作时间减少，利用率降低。
   • 其他正常可运行的任务可能因为 CPU 被死锁进程占用而得不到足够的 CPU 时间，进一步降低了系统整体的 CPU 利用率。
2. 任务执行效率：
   • 死锁会使得涉及死锁的任务完全停滞，无法完成。例如一个多线程的应用程序，若部分线程发生死锁，依赖这些线程结果的后续任务也无法执行，导致整个任务链的执行效率大幅下降。
   • 即使是未直接参与死锁的任务，由于系统资源（如 CPU、内存等）被死锁进程占用，其执行也会受到影响，可能会出现长时间等待资源的情况，从而降低了整体任务执行效率。

缓解死锁的策略及原理

1. 资源分配图算法（如银行家算法）：
   • 原理：银行家算法通过模拟银行系统的资源分配方式来避免死锁。系统将资源视为银行的资金，进程申请资源如同客户贷款。算法会在每次资源分配前检查系统是否处于安全状态，即是否存在一种资源分配序列，使得所有进程都能运行完成。若分配后系统仍处于安全状态，则进行分配；否则拒绝分配。例如，假设有三个进程 P1、P2、P3，系统有一定数量的资源 R1、R2。当 P1 申请资源时，银行家算法会检查将资源分配给 P1 后，是否能找到一种顺序（如 P2 先获取剩余资源运行完，然后 P3 运行完，最后 P1 运行完）使所有进程都能正常结束。如果能找到这样的顺序，则分配资源，否则拒绝 P1 的申请，从而避免死锁的发生。
2. 死锁检测与恢复：
   • 原理：系统定期检测是否存在死锁。检测方法通常基于资源分配图算法，通过检查资源分配图是否存在环来判断是否发生死锁。若检测到死锁，系统需要采取恢复措施。例如，可以选择终止一个或多个死锁进程，释放它们占用的资源，使其他进程能够继续运行。另一种恢复方式是剥夺死锁进程占用的资源，分配给其他进程，以打破死锁状态。例如，在一个数据库系统中，若检测到两个事务发生死锁，系统可以选择回滚其中一个事务，释放其占用的锁资源，让另一个事务能够继续执行，从而恢复系统的正常运行。
3. 资源分配顺序策略：
   • 原理：为所有资源类型分配一个唯一的序号，进程按照资源序号递增（或递减）的顺序申请资源。这样可以避免循环等待资源的情况，从而防止死锁。例如，假设有资源 A、B、C，分别赋予序号 1、2、3。进程在申请资源时，若需要 A、C 资源，必须先申请 A，再申请 C，而不能先申请 C 再申请 A。这样就不会出现进程 P1 持有 A 等待 C，进程 P2 持有 C 等待 A 的死锁情况。