面试题：并发与同步之死锁避免算法基础

Question

请阐述银行家算法在死锁避免中的基本原理，并说明该算法是如何检测系统是否处于安全状态的。

Answer 1

银行家算法在死锁避免中的基本原理

银行家算法基于资源分配图算法，将系统比作银行家，资源比作资金，进程比作借款人。

1. 数据结构：
   • Available：表示系统中各类可利用资源的数量。
   • Max：每个进程对各类资源的最大需求。
   • Allocation：每个进程当前已分配到的各类资源数量。
   • Need：每个进程还需要的各类资源数量，即Need[i,j]=Max[i,j] - Allocation[i,j]。
2. 资源请求处理：当一个进程Pi提出资源请求时，系统首先检查该请求是否超过其最大需求（Requesti <= Needi），如果超过则出错。然后检查请求资源数是否超过系统当前可用资源（Requesti <= Available），若超过则进程等待。若以上条件都满足，系统尝试分配资源，即Available = Available - Requesti，Allocationi = Allocationi + Requesti，Needi = Needi - Requesti。之后通过安全性检查来判断此次分配是否会导致系统进入不安全状态，如果不会则正式分配，否则恢复资源分配前的状态，让进程等待。

银行家算法检测系统是否处于安全状态的方法

1. 初始化：设置一个工作向量Work = Available，一个布尔数组Finish，Finish[i]表示进程Pi是否完成，初始值均为false。
2. 寻找安全序列：
   • 遍历所有进程，寻找满足Needi <= Work且Finish[i] == false的进程Pi。
   • 若找到这样的进程Pi，则执行Work = Work + Allocationi，Finish[i] = true，然后回到步骤2继续寻找。
   • 若遍历完所有进程都找不到满足条件的进程，则停止。
3. 判断安全状态：如果所有进程的Finish[i]都为true，则系统处于安全状态，找到的进程执行序列即为安全序列；否则系统处于不安全状态。