面试题：并发与同步：死锁的常见原因及一般性解决方案

Question

请详细阐述操作系统中死锁产生的四个必要条件，并针对每个条件给出至少一种打破该条件以解决死锁的常见方法。

Answer 1

死锁产生的四个必要条件及打破方法

1. 互斥条件
   • 条件阐述：资源在某一时刻只能被一个进程所使用，即进程对所分配到的资源进行排他性使用。
   • 打破方法：
     • 使用可共享资源：例如对于一些数据，可采用多进程可同时读取的方式，只要不进行写操作，避免数据一致性问题，这样多个进程可同时访问该数据资源，打破互斥条件。
     • 采用假脱机技术（SPOOLing）：对于打印机等独占设备，可通过 SPOOLing 技术将数据先输出到磁盘缓冲区，多个进程都可向缓冲区写数据，再由缓冲区按顺序输出到打印机，看似打印机被多个进程同时使用，打破了打印机使用的互斥性。
2. 占有并等待条件
   • 条件阐述：进程已经持有了至少一个资源，但又提出了新的资源请求，而该新资源已被其他进程占有，此时请求进程被阻塞，但对自己已获得的资源保持不放。
   • 打破方法：
     • 资源分配策略调整：采用一次性分配策略，即进程在运行前一次性申请它所需要的所有资源，只有当系统能满足其所有资源需求时，才把资源分配给该进程，这样进程在运行过程中就不会再请求新资源，避免占有并等待情况。例如一个进程需要资源A、B、C，在启动时就申请这三个资源，若系统无法全部满足则不分配，进程等待，直到系统能一次性满足其需求。
     • 剥夺式分配：当一个进程请求新资源得不到满足时，系统可以剥夺该进程已占有的资源。例如对于 CPU 资源，若高优先级进程需要运行，可剥夺低优先级进程的 CPU 使用权，把 CPU 分配给高优先级进程，打破占有并等待条件。
3. 不可剥夺条件
   • 条件阐述：进程已获得的资源，在未使用完之前，不能被其他进程强行剥夺，只能由该进程自己在使用完后主动释放。
   • 打破方法：
     • 引入抢占机制：对于一些资源，如 CPU 资源，操作系统采用时间片轮转调度算法或者优先级调度算法等抢占式调度方式，当高优先级进程到来或者时间片用完时，就抢占当前进程的 CPU 资源，打破不可剥夺条件。
     • 资源协商释放：在某些场景下，可让进程之间进行协商，当一个进程需要另一个进程占有的资源时，可请求对方进程暂时释放该资源，待使用完毕后再归还，从而打破不可剥夺条件。例如两个进程 A 和 B，A 需要 B 占有的资源 R，A 向 B 发送请求，B 若同意则释放资源 R 给 A，A 使用完归还。
4. 循环等待条件
   • 条件阐述：存在一组进程{P1, P2, …, Pn}，其中 P1 等待 P2 占有的资源，P2 等待 P3 占有的资源，…，Pn 等待 P1 占有的资源，形成一个进程资源等待环路。
   • 打破方法：
     • 资源分配图算法（如死锁检测算法）：通过检测系统资源分配图是否存在环路来判断是否存在死锁。若存在环路，则通过剥夺环路上某个进程的资源来打破环路。例如银行家算法就是一种死锁预防算法，同时也可结合死锁检测，若检测到死锁，选择适当进程剥夺其资源，打破循环等待。
     • 资源层次分配：将系统中的资源按某种层次关系进行排序，例如按照资源的重要性或者编号顺序等，规定进程申请资源时必须按照资源层次顺序依次申请。例如有资源 A、B、C，规定进程必须先申请 A，再申请 B，最后申请 C，这样就不会形成循环等待的环路。