计算机操作系统之期末考试复习——银行家算法

基本概率

1. 银行家算法中的数据结构

   为了实现银行家算法，在系统中必须设置这样四个数据结构，分别用来描述系统中可利用的资源、所有进程对资源的最大需求、系统中的资源分配，以及所有进程还需要多少资源的情况。

   (1)

   可利用资源向量Available

   。

   (2)

   最大需求矩阵Max

   。

   (3)

   分配矩阵Allocation

   。

   (4)

   需求矩阵Need

   。

2. 银行家算法

   设 R e q u e s t i Request_i Requesti​是进程Pi的请求向量，如果 R e q u e s t   i [ j ] = K Request i[j]=K Request i[j]=K，表示进程Pi需要K个 R j R_j Rj​类型的资源。当 P i P_i Pi​发出资源请求后，系统按下述步骤进行检查：

   (1) 如果 R e q u e s t   i [ j ] ≤ N e e d [ i , j ] Request i[j]≤Need[i, j] Request i[j]≤Need[i,j]，便转向步骤(2)； 否则认为出错，因为它所需要的资源数已超过它所宣布的最大值。

   (2) 如果 R e q u e s t   i [ j ] ≤ A v a i l a b l e [ j ] Request i[j]≤Available[j] Request i[j]≤Available[j]，便转向步骤(3)； 否则，表示尚无足够资源， P i P_i Pi​须等待。

   (3) 系统试探着把资源分配给进程 P i P_i Pi​，并修改下面数据结构中的数值：

   A v a i l a b l e [ j ] = A v a i l a b l e [ j ]   −   R e q u e s t   i [ j ] ; Available[j] = Available[j] - Request i[j]; Available[j]=Available[j] − Request i[j];

   A l l o c a t i o n [ i , j ] = A l l o c a t i o n [ i , j ]   +   R e q u e s t   i [ j ] ; Allocation[i, j] = Allocation[i, j] + Request i[j]; Allocation[i,j]=Allocation[i,j] + Request i[j];

   N e e d [ i , j ] = N e e d [ i , j ]   −   R e q u e s t   i [ j ] ; Need[i, j] = Need[i, j] - Request i[j]; Need[i,j]=Need[i,j] − Request i[j];

   (4) 系统执行安全性算法，检查此次资源分配后系统是否处于安全状态。若安全，才正式将资源分配给进程 P i P_i Pi​，以完成本次分配；否则，将本次的试探分配作废，恢复原来的资源分配状态，让进程 P i P_i Pi​等待。

具体例题

1. 题目一：

   

题解：

1. 题目二

   

题解：