面试题：操作系统并发与同步：死锁条件及资源分配策略

Question

请阐述死锁产生的四个必要条件，并说明在银行家算法中，是如何通过资源分配来避免死锁的？

Answer 1

死锁产生的四个必要条件

1. 互斥条件：进程对所分配到的资源进行排他性使用，即在一段时间内某资源仅为一个进程所占有。此时若有其他进程请求该资源，则请求进程只能等待。
2. 占有并等待条件：进程已经保持了至少一个资源，但又提出了新的资源请求，而该资源已被其他进程占有，此时请求进程被阻塞，但对自己已获得的资源保持不放。
3. 不可剥夺条件：进程已获得的资源，在未使用完之前，不能被剥夺，只能在使用完时由自己释放。
4. 循环等待条件：在发生死锁时，必然存在一个进程——资源的环形链，即进程集合{P0，P1，P2，···，Pn}中的P0正在等待一个P1占用的资源；P1正在等待P2占用的资源，……，Pn正在等待已被P0占用的资源。

银行家算法避免死锁的方式

1. 数据结构：
   • 可利用资源向量Available：含有m个元素的数组，其中的每一个元素代表一类可利用的资源数目。
   • 最大需求矩阵Max：n×m矩阵，定义了系统中n个进程中的每一个进程对m类资源的最大需求。
   • 分配矩阵Allocation：n×m矩阵，定义了系统中每一类资源当前已分配给每一个进程的资源数。
   • 需求矩阵Need：n×m矩阵，表示每个进程还需要的各类资源数。Need[i, j]=Max[i, j]-Allocation[i, j] 。
2. 资源分配检查：
   • 当进程Pi提出资源请求Requesti时，系统首先检查该请求向量Requesti中的每一个元素是否小于等于当前的需求矩阵Need[i, j] 。如果Requesti[j]≤Need[i, j]，表示进程Pi请求的资源数不超过它所需要的最大值；否则，认为出错，因为它所需要的资源数已超过它所宣布的最大值。
   • 接着检查Requesti中的每一个元素是否小于等于当前的可利用资源向量Available[j] 。如果Requesti[j]≤Available[j]，表示系统中有足够的资源分配给进程Pi；否则，Pi必须等待，因为系统中尚无足够的资源。
   • 若以上两个条件均满足，系统将为进程Pi分配资源，即修改Available、Allocation和Need矩阵：Available[j]=Available[j]-Requesti[j] ；Allocation[i, j]=Allocation[i, j]+Requesti[j] ；Need[i, j]=Need[i, j]-Requesti[j] 。
   • 然后系统执行安全性算法，检查此次资源分配后系统是否处于安全状态。如果系统处于安全状态，则正式将资源分配给进程Pi；否则，撤销此次分配，让进程Pi等待，并恢复Available、Allocation和Need到分配前的状态。
3. 安全性算法：
   • 初始化工作向量Work = Available。
   • 从进程集合中找到一个能满足以下条件的进程：Need[i, j]≤Work[j] ，表示该进程需要的资源数不超过系统当前可利用的资源数。如果找到，则执行下一步；否则，执行第4步。
   • 当进程Pi获得资源后，它可以顺利执行，直至完成，并释放出分配给它的资源，即Work[j]=Work[j]+Allocation[i, j] ，然后返回第2步。
   • 如果所有进程都能找到满足条件的情况（即所有进程都能顺利执行完成），则系统处于安全状态；否则，系统处于不安全状态。银行家算法通过确保每次资源分配后系统都处于安全状态，从而避免死锁的发生。