银行家算法小笔记

最著名的避免死锁算法：
将操作系统视为银行家，操作系统管理的资源视为银行家管理的资金。

1. 数据结构的描述
   假设n个进程，m类资源，银行家需要定义下面4个数据结构：
   1. 可利用资源向量
   2. 最大需求矩阵
   3. 分配矩阵
   4. 需求矩阵
2. 描述：
   设Requests_i 是进程P-i的请求向量，Request_i[j]=K表示进程P-i需要j类资源K个。当P-i发出资源请求后，系统按照下述步骤进行检查：
   1. 若$Request_i[j] \le Need[i,j]$，则转向步骤2，否则认为出错，因为它所需的资源数已经超过它所宣布的最大值。
   2. 若$Request_i[j]\le Available[j]$，转向步骤3，否则没有足够的资源，进程必须等待
   3. 系统试探着将资源分配给进程P-i，修改下面数据结构中的数值
      $$\begin{aligned}Available &= Available-Request\ Allocation[i,j]&=Allocation[i,j]+Request_i[j]\Need[i,j]&= Need[i,j]-Request_i[j]\end{aligned}$$
   4. 系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。若安全，才正式将资源分配给进程P-i，以完成本次分配；否则，将本次的试探分配作废，恢复原来的资源分配状态，让进程P-i等待。
3. 安全性算法
   设置安全向量，表示系统中的剩余可用资源数目，它有m个元素，在执行安全性算法前，令Work=Available
   1. 初始为空
   2. 从Need矩阵中找出复合下面条件的行：该行对应的进程不在安全序列中，而且该行小于或等于Work向量，找到后，将对应的进程加入安全序列；若找不到，则执行步骤4
   3. 进程P-i进入安全序列后，可顺利执行，直至完成，并释放分配给它的资源，所以应该执行$$Work = Work + Allocation[i]$$其中Allocation[i]是Allocation矩阵中对应的行，返回步骤2
   4. 若此时安全序列中已有所有进程，则系统处于安全状态，否则系统处于不安全状态。