上一篇

對死鎖的思考【1】

介紹了什么是死鎖，對于每種類型一個資源和多個資源的檢測，這里會介紹一下

如何從死鎖中恢復

死鎖的避免

死鎖的預防

說明：這不是一篇專業性的文章，只是力求讓讀者能理解、知道什么是死鎖。如果想要更具體深入的知識還需要查閱相關文獻。

從死鎖中恢復

搶占性恢復

從字面上看，搶占性恢復就是強制把已經被占有的資源強制拿過來，分配給需要他的進程，而達到解除死鎖的目的。

在不通知持有資源進程的情況下，將資源強制占用，用完后又還給進程，這和資源本身的特性有關。即有的資源是不可搶占的。

比如說一個正在刻錄光盤的光驅，在它完成之前是不可搶占的。

回滾技術

簡單的說，就是再檢測到死鎖的時候設法回到還沒發生死鎖的狀態。只要記錄下進程執行的每一步（存儲鏡像， 資源狀態），可以把它記錄在磁盤上，當死鎖發生時，根據這個記錄回到還沒發生死鎖的狀態，一般是回到上一個時間點，重新分配資源，就可以避免死鎖的發生。

當進程執行時，一系列的記錄文件會被累計起來，如下圖：

每個進程都會對應自己的記錄，當回退到時間點i 后重新分配資源，接著銷毀 記錄i 以后的記錄。

其實回滾技術也可叫做回退技術。讓執行狀態退回到還沒發生死鎖的狀態，重新分配資源。

通過殺死進程恢復

這就更好理解了，kill 在執行的進程，釋放它的資源，如果它所持有的資源正好是死鎖中某個進程需要的資源，那么死鎖就解除了。不過這有一定的運氣成分。如果運氣不好kill的進程中沒有解除死鎖需要的資源，就要在kill別的進程。

死鎖的避免

死鎖的產生是由于進程之間分配資源的一種不合理性。舉個例子：按照分配方法A最后進程集合發生死鎖，如果能在A方法分配之前能預先知道這樣的分配會最終導致死鎖，那么不按照A方法分配資源，采用別的方法，或許就能避免死鎖的發生。

安全狀態

如果死鎖沒有發生，即使進程集合中的所有進程都請求最大的資源，也存在某種調度次序能使所有進程都執行，那么稱這個狀態是安全的。

看下面的例子：

設這里使用的資源S一共有10個

考慮進程A、B、C。如圖表所示，中間一列（Has）表示進程擁有的資源右邊一列（Max）表示該進程最多可能請求的資源。

圖a)中資源剩余3個。

對于這個進程集合，要讓進程完整的執行，A需要6個資源，B需要2個，C需要5個。

所以可以這樣調度：剩余3個資源，分另個資源你給B，讓它執行，狀態如 b）所示。

B執行后，釋放占有的資源，到達狀態 c) 。這時剩余5個資源，可以執行C、然后執行A。

a)的狀態通過這樣的調度算法，就能讓進程集合中的進程都得到執行，不會出現死鎖。所以a)狀態是安全的。

像這樣存在一種調度方法能讓進程集合中的每個進程都能執行的集合狀態稱為安全狀態。（因為可以避免死鎖）

不安全狀態

和安全狀態想對應，如果不能存在上面說的調度算法，就是不安全狀態。

不論怎樣調度進程執行，都不能讓進程集合中的所有狀態都得到執行的狀態，就是不安全狀態。

理論都是浮云來看一個例子吧：

如圖：

這次不是讓進程B先執行，而是先分配一個資源給A，到達如圖 b)的狀態，因為只剩下2個資源，只能執行B，到狀態 c) ，釋放B，到達狀態d)

到狀態d）以后，剩余資源只有4個，A和C都不夠執行了。這時候進程集合中的進程就不能全部被執行。

可以看出，從b）出發，不論怎樣調度程序和分配資源，最后都不能保證進程結合中的進程都被執行。

所以b)的狀態是不安全狀態。

不安全狀態并不是死鎖

比如d)中，在A請求其他資源之前，可以在自己執行之前釋放一個資源，讓C執行，

安全狀態和不安全狀態的區別是：從安全狀態出發，系統可以保證所有的進程都被執行，而從不安全狀態出發就沒有這樣的保證。

下面介紹關于上文中兩種狀態判斷的銀行家算法，

 

銀行家算法初探

單個資源的銀行家算法

銀行家算法，第一次聽說時也感覺這個名字挺酷的，它是一種能夠避免死鎖的調度算法。是上一篇博文中給出的死鎖檢測方法的一種擴展。

還是嘮叨下吧 ，銀行家算法名字的來歷：

一個小鎮上有一個銀行家，銀行家有錢啊，他借錢給一些人，對于不同的人，有不同的貸款額度，也就是最多能借給他的money。

為了使問題簡單，假設有A、B、C、D四個人向他借錢。但是借錢有個條件，就是每一次有人來借錢了，就要判斷是不是會進入不安全狀態

如果是 ，就不借錢給他，如果借出之后仍是安全的，就借錢給他。

銀行家是聰明的，他知道所有客戶不會同時都需要最大的貸款額度，他擁有10個單位的money，他向客戶承諾的貸款額度綜合是22.

通過他的協調，就能在客戶之間周旋~

看下面的圖：左邊的一列表示客戶，中間的一列表示客戶已有的money，最后一列表示他們的貸款額度。

客戶都有自己的生意，不停的借錢和還錢，假設某時刻的狀態如 b) 所示，剩余兩個資源，銀行家可以推辭除C以外的借錢請求，等C借錢用過之后釋放自己的資源，系統中的剩余資源就編程了4個，這是可以接受來自B 或者 C 的請求。所以b)的狀態是安全狀態

如果銀行家借了一個單元的錢個B，如 c)的 狀態，剩余1個資源，銀行家將不能滿足任何客戶的需求，所以狀態 c)是不安全狀態。

銀行家算法就是對每一個請求進行檢查，如果這一請求能達到安全狀態，就執行，如果不能達到安全狀態，就不讓它執行。

要查看狀態是否安全，銀行家看它是否有足夠的資源滿足其中的一個客戶，如果可以，認為這筆投資是可回收的，一次類推，如果最后所有資源都被回收，那么該狀態是安全的，最初的狀態也被批準。

可見，銀行家算法是檢查每一次的資源請求是否會達到安全狀態，如果是，則批準該請求，否則禁止該請求。

 

死鎖的預防

 資源的分配無時無刻都在發生，所以說要完全杜絕死鎖的出現是不可能的，那么如何預防死鎖呢？

在前一篇對死鎖的思考【1】/thinking in deadlocks中，列出了死鎖發生的四個必要條件，只有這四個條件都同時滿足，才會發生死鎖。

換一個角度，要避免死鎖，只要破壞這四個條件中的一個不就可以了？對！ 是這樣的。請看下文

 破壞互斥條件

如果資源不被獨占，那么死鎖就不會發生。其中一種典型的技術稱為假脫機打印機技術（spolling printer）。資源不被獨占，也就是說可以同時又多個進程使用打印機。基本思想是這樣的：打印機有一個專門 的工作進程，一般稱為守護進程，由于該進程不會請求其它資源，所以不會發生死鎖。

破壞占有和等待條件

只要禁止進程在執行的過程中請求其它資源，就不會發生死鎖。簡單的思路是讓每個進程在執行前就分配好它需要的所有資源。但也有一個問題：許多進程在執行的時候才知道自己需要多少資源，如果事先就知道需要的資源個數， 就可以使用上文中的銀行家算法來避免死鎖。

破壞不可搶占條件

如果一個進程正在使用打印機，如果被其他進程強行搶占，將會引起混亂，然而對于某些特殊的資源，可以使用虛擬化的方式來實現。

如假脫機打印機技術

破換環路等待條件

這里介紹一種簡單的方法：如果進程要請求另外一個資源，則必須放棄前面以請求的資源。這就可以避免環路出現

 

參考資料：

《modern operating system》

http://msdn.microsoft.com/en-us/library/ms178104.aspx

http://en.wikipedia.org/wiki/Deadlock

 

如轉載請注明出處：http://www.rzrgm.cn/yanlingyin/