『壹』 操作系統(死鎖避免)----銀行家演算法解題
死鎖：是指兩個以上的進程都因要求對方已經佔有的資源，導致無法運行下去的現象，死鎖是系統的一種出錯狀態，不僅浪費大量的系統資源，甚至會導纖賀余致整個系統的崩潰，所以死鎖是盡量預防和避免的。
產生死鎖的四個條件：
死鎖的處理
銀行家演算法是死鎖避免的重要演算法。
銀行家算毀滾法：資源==錢；收回資源==收回貸款；收不回資源==不會放貸；
例題：假設系統中有三類互斥資源R1，R2，R3。可用資源分別是9,8,5.在T0時刻系統有P1，P2，P3，P4，P5五個進程，這些進程最大的需求和已分配的資源如下所示，如果按_執行，那麼系統的狀態是安全的。
解：第一步：根據可用資源，可以求得剩餘資源。
R1=9-(1+2+2+1+1)=2
R2=8-(2+1+1+2+1)=1
R3=5-(1+1+0+0+3)=0
第二拍納步：根據剩餘資源求得還需要的資源數。
公式：還需資源（Need）=最大需求（Max）-已分配資源（Allocation）。
第三部，根據剩餘資源數，求出安全序列。
根據剩餘資源可得，p2可以執行（條件：每個值都必須≦剩餘資源）
由此可見安全序列為P2-->p4-->p5-->p1-->p3。
其實安全序列不是唯一的，這是為什麼呢？
大家可以看出來，現有資源要大於需要資源的情況下是有多種選擇的，因此安全序列不唯一。
『貳』 銀行家演算法(操作系統）
1、這是安全狀態：
P1的需求小於可用資源數，先滿足P1的請求，然後回收P1資源：可用資源變為 （3,3,2）＋（2,0,0）＝（5,3,2）；
這時P3可分配，P3結束後回收資源，可用資源為（5,3,2）＋（2,1,1）＝（7,4,3）
這時P0可分配，P0結束後回收資源，可用資源為（7,4,3）＋（0,1,0）＋（7,5,3）
接下來是P2，結束後可用資源為（7,5,3）＋（3,0,2）＝（10,5,5）
最後分配P4，結束後可用資源為（10,5,5）＋（0,0,2）＝（10,5,7）
這樣得到一個安全序列：P1－P3－P0－P2－P4，所以T0狀態是安全的。
2、T0時刻P1請求（1,1,2）<可用資源數（3,3,2），可以直接滿足。
『叄』 銀行家演算法
Dijkstra（1965）提出了一種能夠避免死鎖的調度演算法，稱為銀行家演算法（banker's algorithm），這是6.4.1節中給出的死鎖檢測演算法的擴展。該模型基於一個小城鎮的銀行家，他向一群客戶分別承諾了一定的貸款額度。演算法要做的是判斷對請求的滿足是否會導致進入不安全狀態。如果是，就拒絕請求；如果滿足請求後系統仍然是安全的，就予以分配。在圖6-11a中我們看到4個客戶A、B、C、D，每個客戶都被授予一定數量的貸款單位（比如1單位是1千美元），銀行家知道不可能所有客戶同時都需要最大貸款額，所以他只保留10個單位而不是22個單位的資金來為客戶服務。這里將客戶比作進程，貸款單位比作資源，銀行家比作操作系統。
『肆』 淺析銀行家演算法
作為避免死鎖的一種演算法，銀行家演算法可以說是最為出名的了。這個名字的來源是因為該演算法起初是為銀行系統設計的，以確保銀行在發放現金貸款時，不會發生不能滿足所有客戶需要的情況。在操作系統中也可以用它來實現避免死鎖。
首先我們要了解銀行家演算法的本質也即避免死鎖的原理。避免死鎖作為一種事先預防死鎖的策略，原理是在為各個進程分配資源的過程中不允許系統進去不安全狀態，以此來避免死鎖的發生。所謂安全狀態，是指系統能按某種進程推進順序為每個進程分配其所需資源，直至滿足每個進程對資源的最大需求，使每個進程都可以順利地完成。此時稱該進程推進序列為安全序列，如果無法找到這樣一個安全序列，則稱系統處於不安全狀態。
銀行家演算法中的數據結構。為了實現銀行家演算法，在系統中必須設置這樣四個數據結構，分別用來描述系統中可利用的資源，所有進程對資源的最大需求，系統中的資源分配以及所有進程還需要多少資源的情況。
(1)可利用資源向量Available。這是一個含有m個元表的數組,其中的每一個元素代表一類可利用的資源數目。其數值隨該類資源的分配和回收而動態地改變。如果 Available=K,則表示系統中現有Rj類資源K個。
(2)最大需求矩陣Max。這是一個nxm的矩陣,它定義了系統中n個進程中的每個進程對m類資源的最大需求。如果Max[i,j]=K,則表示進程i需要Rj類資源的最大數目為K。
(3)分配矩陣 Allocation。這也是一個nxm的矩陣,它定義了系統中每一類資源當前已分配給每一進程的資源數。如果Allocation[i,j]=K,表示進程i當前已分得Rj類資源的數目為K。
(4)需求矩陣Need。這也是一個nxm的矩陣,用以表示每一個進程尚需的各類資源數。如果Need[i,j]=K，則表示進程i還需要Rj類資源K個才能完成。
當一個進程發出請求資源的請求後，如果它所請求的資源大於目前系統可利用資源則不予分配。如果小於可利用資源，則系統試探著把資源分配給該進程，並修改分配之後的資源數值。接著系統執行安全演算法，檢查此次資源分配後系統是否處於安全狀態。若安全，才正式將資源分配給該進程，以完成本次分配。否則，將本次的試探分配作廢，恢復原來的資源分配狀態，讓該進程等待。