面试题：进程管理之专家难度：进程死锁的预防与检测优化

Question

假设你正在处理一个复杂的多进程系统，可能出现死锁情况。请阐述死锁产生的四个必要条件，并说明如何从操作系统设计层面预防死锁。同时，如果死锁已经发生，你会采用何种高效的检测算法和恢复策略？

Answer 1

死锁产生的四个必要条件

1. 互斥条件：资源在某一时刻只能被一个进程所使用。例如打印机，同一时间只能有一个进程使用它进行打印任务。
2. 占有并等待条件：进程已经占有了至少一个资源，但又提出了新的资源请求，而该资源已被其他进程占有，此时请求进程被阻塞，但对自己已获得的资源保持不放。比如一个进程已经占用了一个文件的读权限，又请求该文件的写权限，在等待写权限期间不释放读权限。
3. 不可剥夺条件：进程已获得的资源，在未使用完之前，不能被剥夺，只能在使用完时由自己释放。例如一个进程获得了一块内存空间，在它主动释放之前，其他进程不能强行夺走这块内存。
4. 循环等待条件：存在一个进程资源的循环链，链中的每一个进程已获得的资源同时被链中下一个进程所请求。假设有进程P1、P2、P3，P1等待P2占用的资源，P2等待P3占用的资源，P3又等待P1占用的资源，形成循环等待。

从操作系统设计层面预防死锁

1. 破坏互斥条件：在一些情况下，可以允许资源共享来避免死锁。例如对于可重入代码，可以多个进程同时访问。但这种方法对于某些资源不适用，如打印机等需要独占的资源。
2. 破坏占有并等待条件：
   • 静态分配策略：进程在运行前一次性申请它所需要的全部资源，只有当系统能满足进程的所有资源需求时，才把资源分配给该进程，进程在整个运行期间不再提出资源请求。比如一个程序需要使用CPU、内存、磁盘空间等资源，在启动前就一次性分配好这些资源。
   • 动态分配时要求释放已占资源：当进程提出新的资源请求时，若不能立即满足，该进程必须释放已占有的所有资源，待以后需要时再重新申请。例如进程已经占用了部分内存资源，当它申请新的内存块失败时，要先释放已占内存，再重新申请所需全部内存。
3. 破坏不可剥夺条件：
   • 优先级剥夺：当一个进程占有了某些资源，而另一个优先级更高的进程申请这些资源时，系统可以剥夺占有资源的低优先级进程的资源，分配给高优先级进程。例如一个紧急的系统任务（高优先级）需要内存资源，而当前有一个普通应用程序（低优先级）占用了部分内存，系统可剥夺普通应用程序的内存给紧急任务。
   • 资源剥夺与恢复：当一个进程占有资源且不释放，而其他进程因等待这些资源陷入死锁时，系统可以剥夺该进程的资源，并在适当时候恢复该进程。例如进程A占用了一个共享资源导致死锁，系统剥夺该资源给其他进程，然后在合适时机重新给进程A分配资源让其继续运行。
4. 破坏循环等待条件：
   • 资源分配图算法：通过对资源分配图进行算法检查，如使用资源分配图算法（如检测环算法），当发现有循环等待可能时，采取措施打破循环。例如在资源分配图中发现有环，就剥夺环中某个进程的资源来打破循环。
   • 资源分配顺序：对资源进行排序，进程必须按照资源的序号顺序申请资源。比如系统有资源R1、R2、R3，规定进程申请资源顺序只能是先申请R1，再申请R2，最后申请R3，这样可以避免循环等待。

死锁检测算法

1. 资源分配图算法（RAG算法）：
   • 构建资源分配图：用有向图表示系统资源分配情况，图中节点分为进程节点和资源节点，有向边表示资源分配关系。例如进程P1指向资源R1的边表示P1占用R1，资源R2指向进程P2的边表示P2等待R2。
   • 算法执行：
     • 寻找一个非孤立且没有请求边的进程节点（即该进程已经获得了所需的所有资源），将其与它所占用的资源边移除，更新资源分配图。
     • 重复上述步骤，若最终图中所有节点都变为孤立节点，则系统没有死锁；若无法找到这样的进程节点且图中仍存在非孤立节点，则存在死锁。例如图中有进程P1、P2和资源R1、R2，P1占用R1且等待R2，P2占用R2且等待R1，在执行算法时找不到符合条件的进程节点，说明存在死锁。
2. 银行家算法的扩展：
   • 基本银行家算法：主要用于避免死锁，它通过判断系统是否处于安全状态来决定是否分配资源。安全状态是指系统能按照某种顺序为每个进程分配资源，使每个进程都能运行完成。例如系统有进程P1、P2、P3，资源总量为10个，P1已分配2个，最大需求5个；P2已分配3个，最大需求7个；P3已分配1个，最大需求4个。通过计算剩余资源和进程需求，判断系统是否安全。
   • 扩展用于死锁检测：在银行家算法基础上，不断假设分配资源给某个进程，看是否能找到一个安全序列。若找不到安全序列，则存在死锁。例如假设给进程P1分配1个资源后，重新计算剩余资源和各进程需求，看是否能形成安全序列，若不能则可能存在死锁。

死锁恢复策略

1. 资源剥夺法：
   • 选择剥夺对象：选择一个或几个死锁进程，剥夺它们占有的资源分配给其他进程，以打破死锁。例如选择占用资源较少或优先级较低的进程剥夺其资源。
   • 恢复剥夺进程：在其他进程运行完成后，重新给被剥夺资源的进程分配资源，让其继续运行。例如先剥夺进程P3的资源给进程P1和P2，等P1和P2运行结束，再给P3分配资源。
2. 进程终止法：
   • 终止单个进程：选择一个死锁进程，终止它并释放其占有的资源，以打破死锁。例如选择陷入死锁且对系统影响较小的进程终止，如某个用户应用程序进程。
   • 终止多个进程：若终止单个进程不能打破死锁，可选择终止多个死锁进程。例如终止一组相互等待资源形成死锁环的进程。
3. 回滚法：
   • 检查点设置：在进程运行过程中设置检查点，记录进程的状态和资源分配情况。例如每隔一段时间记录进程的内存状态、已分配资源等。
   • 回滚操作：当检测到死锁时，将死锁进程回滚到最近的检查点，释放从检查点之后获得的资源，然后重新执行进程，尝试以不同的资源分配方式运行，避免死锁。例如进程在执行到第10步检测到死锁，回滚到第5步的检查点状态，重新从第5步执行。