面试题：并发与同步：如何解决锁带来的死锁问题

Question

在操作系统中，锁的使用可能会导致死锁。请描述死锁产生的四个必要条件，并详细说明至少两种预防死锁的策略，以及每种策略的原理和优缺点。

Answer 1

死锁产生的四个必要条件

1. 互斥条件：资源在某一时刻只能被一个进程所使用。例如打印机，在打印一份文件时，不能同时被另一个进程用于打印另一份文件。
2. 占有并等待条件：一个进程已经占有了至少一个资源，但又申请新的资源，而新资源被其他进程占有，此时该进程会等待新资源，且不会释放已占有的资源。比如进程A已经持有资源R1，又申请资源R2，而R2被进程B持有，A就会等待R2且不释放R1。
3. 不可剥夺条件：进程所获得的资源在未使用完毕之前，不能被其他进程强行夺走，只能由获得该资源的进程自己释放。例如进程C获得了磁带机资源，在其使用完磁带机前，其他进程无法强行获取该磁带机。
4. 循环等待条件：存在一组进程{P1, P2, …, Pn}，其中P1等待P2占有的资源，P2等待P3占有的资源，……，Pn等待P1占有的资源，形成一个循环等待链。

预防死锁的策略

1. 破坏互斥条件
   • 原理：允许系统资源都能共享使用，即打破资源只能被一个进程独占的情况。
   • 优点：从根本上消除了死锁产生的可能性，因为死锁的四个必要条件之一被破坏。
   • 缺点：并不是所有资源都能实现共享使用，比如打印机这种设备，若允许多个进程同时使用，会导致打印结果混乱，所以此策略适用场景有限。
2. 破坏占有并等待条件
   • 原理：要求进程在开始运行前一次性申请它所需要的全部资源，只有在系统能满足进程所需的全部资源时，才把这些资源分配给该进程，这样进程在运行过程中就不会再申请资源。
   • 优点：简单且容易实现，能有效预防死锁。
   • 缺点：资源利用率低，因为进程可能会很长时间占用着它申请的所有资源，但实际可能并不是同时需要使用这些资源，造成部分资源的浪费；另外，可能会导致一些进程长时间得不到运行，因为系统可能无法一次性满足其所需的全部资源。
3. 破坏不可剥夺条件
   • 原理：当一个已经占有了某些资源的进程，在申请新的资源不能得到满足时，必须释放它已经占有的所有资源，待以后需要时再重新申请。
   • 优点：可以动态地分配资源，提高资源利用率，相对来说能较好地避免死锁。
   • 缺点：实现起来复杂，需要系统记录进程资源的使用情况，而且在进程释放资源时，可能导致其之前的工作成果部分或全部失效，需要重新执行某些操作，增加了系统开销；另外，频繁地剥夺和重新申请资源，也会降低系统的性能。
4. 破坏循环等待条件
   • 原理：对系统中的所有资源类型进行线性排序，并规定每个进程必须按照资源序号递增的顺序请求资源。如果进程需要多个资源，必须先请求序号小的资源，再请求序号大的资源。这样就不会形成循环等待的资源分配链。
   • 优点：实现相对简单，资源利用率和系统吞吐量比破坏占有并等待条件要好。
   • 缺点：进程实际使用资源的顺序可能与资源序号递增顺序不一致，可能导致资源浪费，比如进程需要先使用序号大的资源，再使用序号小的资源，按照此策略就需要先申请序号小的资源，即使暂时不用也要占用，降低了资源的使用效率；而且对资源序号的排序需要合理规划，否则可能影响进程正常运行。