面试题：进程管理之PCB复杂应用（高级难度）

Question

假设在一个多进程并发执行的系统中，由于资源竞争出现了死锁情况。请从进程控制块（PCB）的角度分析，如何利用PCB中的信息来检测死锁，并给出一种基于PCB实现死锁解除的策略思路。

Answer 1

检测死锁

1. 资源分配图算法：
   • 每个进程在其PCB中记录它当前已分配的资源和请求的资源。
   • 可以构建一个资源分配图，图中的节点分为进程节点（对应PCB）和资源节点。
   • 从PCB中的资源分配信息，将已分配的资源与对应的进程用边相连；从PCB中的资源请求信息，将请求资源与对应的进程用边相连。
   • 通过对资源分配图进行算法分析（如简化资源分配图算法），若经过一系列简化后图中仍存在不可简化的环，则表明存在死锁。在简化过程中，从PCB中获取进程是否持有可释放资源（用于打破环）以及进程请求资源状态等信息。
2. 等待资源链表：
   • 在PCB中维护一个等待资源链表，记录该进程正在等待的资源。
   • 系统可以遍历所有进程的PCB等待资源链表，若发现存在进程相互等待对方持有的资源，形成循环等待，则检测到死锁。例如，进程A等待进程B持有的资源R1，进程B等待进程C持有的资源R2，进程C又等待进程A持有的资源R3，这就构成了死锁。

死锁解除策略思路

1. 终止进程：
   • 选择死锁环中的一个或多个进程终止。从PCB的优先级字段获取进程优先级信息，优先选择优先级低的进程终止。例如，系统中有实时进程和普通进程，优先终止普通进程。
   • 查看PCB中的资源占用信息，选择占用资源少的进程终止，以减少资源浪费。比如，进程A占用10个资源，进程B占用5个资源，优先终止进程B。
   • 终止进程后，回收其PCB中记录的已分配资源，供其他进程使用，从而打破死锁环。
2. 剥夺资源：
   • 根据PCB中的资源分配和请求信息，从死锁环中的某个进程剥夺部分资源给其他进程。优先选择从PCB中记录的可剥夺资源字段为“是”的进程剥夺资源。例如，某些进程的资源是可剥夺的（如虚拟内存资源），而有些进程的资源不可剥夺（如正在使用的打印机）。
   • 查看PCB中的进程恢复能力字段，若该字段表明进程有较好的恢复能力（如进程可以较容易地重新获取被剥夺的资源并继续执行），则优先从该进程剥夺资源。剥夺资源后，调整PCB中的资源分配信息，被剥夺资源的进程进入等待状态，等待重新获取资源。