三、死鎖預防
3.1 解決死鎖的方法
- 不考慮此問題(鴕鳥算法)
- 不讓死鎖發生
- 死鎖預防。這是一種靜态政策:即設計合理的資源配置設定算法,不讓死鎖發生
- 死鎖避免。這是一種動态政策:以不讓死鎖發生為目标,跟蹤并評估資源配置設定過程,根據評估結構決策是否配置設定
- 讓死鎖發生
死鎖檢測和解除
3.2 死鎖預防(Deadlock Prevention)(重點)
- 定義:在設計系統時,通過确定資源配置設定算法,排除發生死鎖的可能性
- 具體做法:防止産生死鎖的四個必要條件中任何一個條件的發生
3.2.1 破壞“互斥使用/資源獨占”條件
- 資源轉換技術:把獨占資源變為共享資源
-
技術的引入,解決不允許任何程序直接占有列印機的問題。設計一個“守護程序/線程”負責管理列印機,程序需要列印時, 将請求發給該SPooling
,由它完成列印任務。daemon
3.2.2 破壞“占有且等待”條件
- 實作方案1:要求每個程序在運作前必須一次性申請它所有求的所有資源,且僅當該程序所要資源均可滿足時才給予一次性配置設定。當然,這種方案的資源使用率較低,容易出現“饑餓”現象。
- 實作方案2:在允許程序動态申請資源前提下規定,一個程序在申請新的資源不能立即得到滿足而變為等待狀态之前,必須釋放已占有的全部資源,若需要再重新申請。
3.2.3 破壞“不可搶占”條件
- 實作方案
當一個程序申請的資源被其他程序占用時,可以通過作業系統搶占這一資源(兩個程序優先級不同)
局限性:
該方法實作起來比較複雜,要付出很大的代價。
- 反複地申請和釋放資源
- 程序的執行被無限地推遲
隻适用于狀态易于儲存和恢複的對主存資源和處理器資源的配置設定适用于資源。如
cpu
和記憶體等。
3.2.4 破壞“循環等待”條件
- 通過定義資源類型的線性順序實作
- 實施方案:資源有序配置設定法
- 把系統中所有資源編号,程序在申請資源時必須嚴格按資源編号的遞增次序進行,否則作業系統不予配置設定。我們一般根據資源使用的頻繁性來進行編号。例如解決哲學家就餐問題。
-
為什麼資源有序配置設定法不會産生死鎖?
起始就是程序申請的資源編号必須是遞增的,比如程序
申請了資源P1
,而程序1、3、9
需要資源P2
,那麼程序1、2、5
在申請時必須按照P2
的順序來申請,這樣就破壞了環路條件,因為在申請到資源1、2、5
之前,後面的資源是申請不到的。1
存在下述嚴重問題:
限制了新類型裝置的增加。
造成對資源的浪費。
必然會限制使用者簡單、自主地程式設計。
四、死鎖避免
定義:在系統運作過程中,對程序發出的每一個系統能滿足的資源申請進行動态檢查,并根據檢查結果決定是否配置設定資源,若配置設定後系統發生死鎖或可能發生死鎖(不是安全狀态),則不予配置設定,否則(安全狀态)予以配置設定。
安全狀态:如果系統中存在一個所有程序構成的安全序列P1,P2,......,Pn,則稱系統處于安全狀态。安全狀态表示系統一定沒有發生死鎖。
安全序列
一個程序式列{P1,P2,......,Pn}是安全的,如果對于每個程序Pi(1<= i <= n):它以後還需要的資源數量不超過系統目前剩餘資源量與所有程序Pj(j < i)目前占有資源量隻和。
不安全狀态:系統中不存在一個安全序列。一定會導緻死鎖。五、死鎖避免算法:銀行家算法這是Dijkstra在1965年提出的,是仿照銀行發放貸款時采取的控制方式而設計的一種死鎖避免算法。
應用條件
1、在固定數量的程序中共享數量固定的資源。
2、每個程序預先指定完成工作所需的最大資源數量。
3、程序不能申請比系統中可用資源總數還多的資源。
4、程序等待資源的時間是有限的。
5、如果系統滿足了程序對資源的最大需求,那麼,程序應該在有限的時間内使用資源,然後歸還給系統。
- 當程序
提出資源申請時,系統執行下列步驟:Pi
(1)若
Request[i] <= Need[i]
,轉(2);否則,報錯傳回。
(2)若
Request[i] <= Available
,轉(3);否則,報錯傳回。
(3)假設系統配置設定了資源,則有:
Available = Available - Request[i];
Allocation[i] = Allocation[i] + Request[i];
Need[i] = Need[i] = Request[i]
`</pre>
若系統新狀态是安全的,則配置設定完成;若系統新狀态是不安全的,則恢複原來狀态,程序等待。
為了進行安全性檢查,定義了資料結構:
安全性檢查的步驟:
(1)`Work = Available; Finish = false;`
(2)尋找滿足條件的`i`:
如果不存在,則轉(4)
(3)
`Work = Work + Allocationi ;
轉(2)
(4)若對所有
i,Finish[i] == true
,則系統處于安全狀态,否則,系統處于不安全狀态。