面试题：操作系统并发与同步之下死锁预防策略分析

Question

死锁是并发系统中常见的问题。请阐述死锁产生的四个必要条件，并详细说明至少两种死锁预防策略，分析每种策略如何破坏死锁产生的条件，同时指出这些策略可能存在的局限性。

Answer 1

死锁产生的四个必要条件

1. 互斥条件：资源在某一时刻只能被一个进程所占有，其他进程若请求该资源，则需等待直到资源被释放。
2. 占有并等待条件：进程已经占有了至少一个资源，但又提出了新的资源请求，而该新资源已被其他进程占有，此时请求进程会等待，但同时又不会释放自己已占有的资源。
3. 不可剥夺条件：进程所获得的资源在未使用完之前，不能被其他进程强行夺走，只能由该进程自己主动释放。
4. 循环等待条件：存在一组进程{P1, P2, …, Pn}，其中P1等待P2所占有的某一资源，P2等待P3所占有的某一资源，……，Pn等待P1所占有的某一资源，形成一个进程等待环路。

死锁预防策略

1. 破坏互斥条件
   • 策略：允许资源共享使用。例如在一些文件系统中，允许多个进程同时对文件进行读操作。
   • 破坏条件方式：通过让多个进程可同时访问资源，打破了资源只能被一个进程占有的互斥条件。
   • 局限性：对于某些资源，其本身特性决定了无法共享，如打印机在打印时，必须独占使用，否则会导致打印混乱。而且共享资源可能带来数据一致性等其他问题。
2. 破坏占有并等待条件
   • 策略：
     • 静态分配策略：进程在启动前一次性申请其所需的全部资源，若资源不能满足则不启动，直到所有资源都能分配给该进程。
     • 动态分配策略：进程在申请新资源前，先释放自己已占有的所有资源，然后重新申请所需的全部资源。
   • 破坏条件方式：静态分配策略使得进程在运行过程中不会再请求新资源，避免了占有并等待新资源的情况；动态分配策略则通过要求进程释放已占资源再重新申请，打破了占有并等待的条件。
   • 局限性：静态分配策略可能导致资源长时间闲置，因为有些进程可能很长时间才使用某些资源，但却一直占用着。动态分配策略可能导致进程多次申请和释放资源，增加系统开销，而且如果进程在释放资源后重新申请资源时，由于其他进程抢占，可能导致进程饥饿。
3. 破坏不可剥夺条件
   • 策略：当一个进程占有了某些资源，而又申请新资源且不能满足时，系统可以剥夺该进程已占有的资源分配给其他进程。例如，操作系统可以暂停一个优先级较低的进程，将其占有的资源分配给优先级较高且急需该资源的进程。
   • 破坏条件方式：通过允许系统剥夺进程已占资源，打破了不可剥夺条件。
   • 局限性：对于一些对数据完整性要求较高的资源，剥夺操作可能会导致数据不一致等问题。而且频繁的剥夺和恢复资源会增加系统开销，同时可能导致进程饥饿，低优先级进程的资源不断被剥夺。
4. 破坏循环等待条件
   • 策略：资源分配图算法，为每个资源类型分配一个唯一的序号，进程只能按照序号递增的顺序请求资源。例如，进程要申请资源R1和R2，若R1序号小于R2，进程必须先申请R1，再申请R2。
   • 破坏条件方式：通过这种有序申请资源的方式，避免了进程之间形成循环等待的环路。
   • 局限性：资源序号的分配可能不太合理，导致一些进程为了遵循顺序，需要先申请一些暂时不需要的资源，造成资源浪费。而且这种方法要求程序员在编写程序时严格按照资源序号顺序申请资源，增加了编程的复杂性。