銀行家演算法

"安全狀態" 為 P[1..n] 之中尋找一排列，使資源 R[1..m] 可以按此排列順序 分配，不會產生不足的問題。若此排列存在，則是目前狀態視為安全。在窮舉法 的情況之下，在所有排列中找出滿足者需要 O(n)，銀行家演算法則以 O(mn^2) 解決，但前提是每一程序需給定最多要求的資源量 Max[1..n][1..m]，(或者在 某些網路上的範例稱為 Claim[1..n][1..m])。目前每種資源所剩的數目則為 Available[1..m] 。 由定義可知，Need[i][1..m] = Max[i][1..m] - Allocated[i][1..m]。

銀行家演算法分為兩部份： "安全演算法" 與 "資源分配演算法"，後者包括了 前者，基本概念十分簡單：如果 P[i] 目前需要的資源數目 Need[i][1..m] 少 於 Available[1..m] ，表示 P[i] 可以順利完成工作，結束執行; 此時便讓 P[i] 結束執行 (Finished[i] = 1)，釋出目前佔用資源，再另找一新程序 P[i'] 進行同樣的測試步驟。如果到最後每個 P[1..n] 都執行完畢，則目前狀 態安全。如果有些程序尚未結束執行，其 Need[j][1..m] 卻多於 Available[1..m] ，表示此程序 j 所需之資源太多，使其無法成為安全狀態。

資源分配演算法的概念在於："試試看，如果所需資源被分配之後仍為安全狀態， 則允許此一資源之分配"。

若不知道 Max[1..n][1..m] ，則無法以 O(mn^2) 完成。

範例: http://www.cs.mcgill.ca/~cs310/2000B/docs/class/safestate.html