死鎖是多線程環(huán)境中由于對資源競爭分配不合理而產(chǎn)生的阻塞行為，銀行家算法是一種動態(tài)避免死鎖的策略。
I、死鎖
1.1 死鎖定義
如果一個線程集合中的每個線程都在等待這個集合中另一個線程的執(zhí)行結(jié)果才能繼續(xù)執(zhí)行下去，若無其他外力，它們都無法推進(jìn)，這就形成了死鎖。
1.2 死鎖的4個必要條件
1、互斥條件：一個資源在某時刻內(nèi)只能允許一個線程進(jìn)行訪問；
2、占有且等待：一個線程A占有一部分資源，此時去申請另外的資源，但申請的資源被線程B占有，此時線程A的請求阻塞，但是也不對自己本來的資源進(jìn)行釋放。
3、 不可剝奪條件：線程對已獲得的資源，在未完成使用之前，不可剝奪，只能使用完成后才釋放。
4、 循環(huán)等待：若干個線程之間形成了一種頭尾相連的循環(huán)等待資源關(guān)系。
1.3 死鎖的避免方式
死鎖主要有三種避免方法：
1、 預(yù)防死鎖發(fā)生：通過對死鎖產(chǎn)生的四個必要條件進(jìn)行限制；
2、 檢測與拆除死鎖：這種方式使允許死鎖發(fā)生，檢測死鎖產(chǎn)生，然后解除死鎖；
檢測的具體實施可以維護(hù)兩個資源矩陣，對可用資源和需要資源進(jìn)行比較；
解除死鎖的方式主要可以實施搶占剝奪；kill掉進(jìn)程；回滾系統(tǒng)等；
3、 動態(tài)避免：在資源分配過程中，確保資源請求批準(zhǔn)后系統(tǒng)不會進(jìn)入死鎖或潛在的死鎖狀態(tài)。如銀行家算法。
II、銀行家算法
銀行家算法是仿照銀行發(fā)放貸款時采用的控制方式而設(shè)計的一種死鎖避免算法，該算法的策略是實現(xiàn)動態(tài)避免死鎖。
2.1 算法思想
銀行家算法的基本思想是：分配資源之前，判斷系統(tǒng)是否安全，如果安全才會進(jìn)行資源分配。
我們把操作系統(tǒng)看做是銀行家，操作系統(tǒng)管理的資源相當(dāng)于銀行家的資金，線程向操作系統(tǒng)請求分配資源就是用戶向銀行家要貸款。
算法在每次分配資源前需要要求： request < available && request < needing;
2.2 銀行家算法實例
我們以一個實例來說明銀行家算法：
系統(tǒng)中有R1，R2，R3三種資源，在time0時刻，5個線程T0，T1，T2，T3，T4對資源占用和需求的情況如下表，此時系統(tǒng)的可用資源向量為(3,3,2)。求T0時刻系統(tǒng)是否存在安全序列？
| thread | sum_need | allocated | needing | available |
|---|---|---|---|---|
| T0 | (7,5,3) | (0,1,0) | (7,4,3) | (3,3,2) |
| T1 | (3,2,2) | (2,0,0) | (1,2,2) | |
| T2 | (9,0,2) | (3,0,2) | (6,0,0) | |
| T3 | (2,2,2) | (2,1,1) | (0,1,1) | |
| T4 | (4,3,3) | (0,0,2) | (4,3,1) |
我們假設(shè)每個線程執(zhí)行時間為一個時刻。
1、在time0時刻，available(3,3,2) > T1.needing(1,2,2)； 所以T1可以執(zhí)行，T1執(zhí)行完畢之后available = T1.allocated(2,0,0) + available(3,3,2) = (5,3,2);
| thread | sum_need | allocated | needing | available |
|---|---|---|---|---|
| T0 | (7,5,3) | (0,1,0) | (7,4,3) | (5,3,2) |
| T2 | (9,0,2) | (3,0,2) | (6,0,0) | |
| T3 | (2,2,2) | (2,1,1) | (0,1,1) | |
| T4 | (4,3,3) | (0,0,2) | (4,3,1) |
2、進(jìn)入time1時刻，available(5,3,2) > T3.needing(0,1,1)；所以T3可以執(zhí)行，T3執(zhí)行完畢之后available = T3.allocated(2,1,1)+available(5,3,2) = (7,4,3)；
| thread | sum_need | allocated | needing | available |
|---|---|---|---|---|
| T0 | (7,5,3) | (0,1,0) | (7,4,3) | (7,4,3) |
| T2 | (9,0,2) | (3,0,2) | (6,0,0) | |
| T4 | (4,3,3) | (0,0,2) | (4,3,1) |
3、進(jìn)入time2時刻，available(7,4,3) > T4.needing(4,3,1)；所以T4可以執(zhí)行，T4執(zhí)行完畢之后available = T4.allocated(0,0,2) + available(7,4,3) = (7,4,5)；
| thread | sum_need | allocated | needing | available |
|---|---|---|---|---|
| T0 | (7,5,3) | (0,1,0) | (7,4,3) | (7,4,5) |
| T2 | (9,0,2) | (3,0,2) | (6,0,0) |
4、進(jìn)入time3時刻，available(7,4,5) > T2.needing(6,0,0)；所以T2可以執(zhí)行，T2指向完畢之后available = T2.allocated(3,0,2) + available(7,4,5) = (10,4,7)；
| thread | sum_need | allocated | needing | available |
|---|---|---|---|---|
| T0 | (7,5,3) | (0,1,0) | (7,4,3) | (10,4,7) |
5、進(jìn)入time4時刻，因為available(10,4,7) > T0.needing(7,4,3)；所以執(zhí)行T0。完成安全序列。
上面只是安全序列的一個例子，可能還存在其他安全序列。
【參考】
[1] 《深入理解計算機系統(tǒng)》
[2] 死鎖基礎(chǔ)原理
歡迎轉(zhuǎn)載，轉(zhuǎn)載請注明出處wenmingxing 死鎖&銀行家算法
