計算機作業系統之期末考試複習——銀行家算法

基本機率

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. 題目二

   

題解：