避免死锁之银行家算法

关于前置知识不再赘述，直接讲解算法

算法思想

银行家算法是一种避免死锁的算法，它的基本思想是：如果系统当前处于安全状态，那么就允许进程申请资源；否则，进程必须等待，直到系统处于安全状态时才能申请资源。

算法描述

银行家算法的描述如下：

  1. 当一个进程需要一些资源时，它必须先申请，然后才能得到分配。
  2. 进程得到所有需要的资源后，它必须在有限的时间内使用完毕，然后归还所有资源。
  3. 当一个进程不能在有限的时间内使用完毕，那么它必须释放所有资源。
  4. 当一个进程不能得到所需要的所有资源时，它可以释放已经得到的资源，然后重新申请。

数据结构

可利用资源向量（Available）

这是一个含有 m 元素的数组，其中 m 是系统中资源的种类数。如果 Available[j]=k，那么就表示系统中当前有 k 个可用的资源 Rj。

最大需求矩阵（Max）

这是一个 n*m 的矩阵，其中 n 是进程数，m 是系统中资源的种类数。如果 Max[i][j]=k，那么就表示进程 Pi 需要 k 个资源 Rj。

分配矩阵（Allocation）

这是一个 n*m 的矩阵，其中 n 是进程数，m 是系统中资源的种类数。如果 Allocation[i][j]=k，那么就表示进程 Pi 当前已经分配到了 k 个资源 Rj。

需求矩阵（Need）

这是一个 n*m 的矩阵，其中 n 是进程数，m 是系统中资源的种类数。如果 Need[i][j]=k，那么就表示进程 Pi 还需要 k 个资源 Rj 才能完成任务。

小结,矩阵存在下列关系：

Need[i][j]=Max[i][j]-Allocation[i][j]
Available[j]=sum(Allocation[i][j])+Available[j]

算法实现