并發程式設計死鎖的産生與範例分析

當兩個以上的運算單元，雙方都在等待對方停止運作，以擷取系統資源，但是沒有一方提前退出時，這種狀況，就稱為死鎖。在多任務作業系統中，作業系統為了協調不同程序，能否擷取系統資源時，為了讓系統運作，就必須要解決這個問題。

程序死鎖是作業系統或軟體運作的一種狀态：在多任務系統下，當一個或多個程序等待系統資源，而資源又被程序本身或其它程序占用時，就形成了死鎖。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

<code>/**</code>

<code> </code><code>* 死鎖範例</code>

<code> </code><code>* 類的靜态變量是各個執行個體共享的，隻配置設定一次，是以對這兩個變量的同步可能會導緻死鎖</code>

<code> </code><code>* 兩個線程在分别占有obj1和obj2後，一直等待obj2和obj1的鎖釋放，進入死鎖狀态不能繼續執行</code>

<code> </code><code>* @author bingyue</code>

<code> </code><code>*</code>

<code> </code><code>*/</code>

<code>public</code> <code>class</code> <code>deadlock </code><code>implements</code> <code>runnable{</code>

<code>    </code> 

<code>    </code><code>int</code> <code>flag;</code>

<code>    </code><code>/**</code>

<code>     </code><code>* 類的靜态變量是各個執行個體共享的，隻配置設定一次，是以對這兩個變量的同步可能會導緻死鎖</code>

<code>     </code><code>*/</code>

<code>    </code><code>private</code> <code>static</code> <code>object obj1 = </code><code>new</code> <code>object();</code>

<code>    </code><code>private</code> <code>static</code> <code>object obj2 = </code><code>new</code> <code>object(); </code>

<code>    </code><code>deadlock(</code><code>int</code> <code>flag){</code>

<code>        </code><code>this</code><code>.flag=flag;</code>

<code>    </code><code>}</code>

<code>    </code><code>public</code> <code>static</code> <code>void</code> <code>main(string[] args){</code>

<code>        </code><code>deadlock thread1=</code><code>new</code> <code>deadlock(</code><code>1</code><code>);</code>

<code>        </code><code>deadlock thread2=</code><code>new</code> <code>deadlock(</code><code>2</code><code>);</code>

<code>        </code> 

<code>        </code><code>new</code> <code>thread(thread1).start(); </code>

<code>        </code><code>new</code> <code>thread(thread2).start();</code>

<code>    </code><code>}   </code>

<code>        </code><code>@override</code>

<code>        </code><code>public</code> <code>void</code> <code>run() {</code>

<code>            </code><code>string name = thread.currentthread().getname();</code>

<code>            </code><code>/**</code>

<code>             </code><code>* 線程1的操作</code>

<code>             </code><code>*/</code>

<code>            </code><code>if</code><code>(flag==</code><code>1</code><code>){</code>

<code>                </code><code>//線程1占有o1,同時請求o2的鎖</code>

<code>                </code><code>synchronized</code> <code>(obj1) { </code>

<code>                    </code><code>try</code> <code>{</code>

<code>                        </code><code>system.out.println(name+</code><code>"占有obj1的同步鎖"</code><code>); </code>

<code>                        </code><code>thread.sleep(</code><code>1000</code><code>);</code>

<code>                    </code><code>} </code><code>catch</code> <code>(interruptedexception e) {</code>

<code>                        </code><code>e.printstacktrace();</code>

<code>                    </code><code>} </code>

<code>                    </code><code>synchronized</code> <code>(obj2) { </code>

<code>                        </code><code>system.out.println(name+</code><code>"繼續執行得到obj2的同步鎖"</code><code>); </code>

<code>                    </code><code>}   }  }</code>

<code>             </code><code>* 線程2的操作</code>

<code>            </code><code>if</code><code>(flag==</code><code>2</code><code>){</code>

<code>                </code><code>//線程2占有o2,同時請求o1的鎖</code>

<code>                </code><code>synchronized</code> <code>(obj2) { </code>

<code>                        </code><code>system.out.println(name+</code><code>"占有obj2的同步鎖"</code><code>); </code>

<code>                        </code><code>thread.sleep(</code><code>500</code><code>);</code>

<code>                    </code><code>synchronized</code> <code>(obj1) { </code>

<code>                        </code><code>system.out.println(name+</code><code>"繼續執行得到obj1的同步鎖"</code><code>); </code>

<code>        </code><code>}</code>

<code>}</code>

　　

如果系統中隻有一個程序，當然不會産生死鎖。如果每個程序僅需求一種系統資源，也不會産生死鎖。不過這隻是理想狀态，在現實中是可遇不可求的。

死鎖的四個條件是：

禁止搶占：no preemption 程序已獲得的資源，在末使用完之前，不能強行剝奪。

持有和等待：hold and wait 一個程序因請求資源而阻塞時，對已獲得的資源保持不放。

互斥：mutual exclusion 一個資源每次隻能被一個程序使用。

循環等待：circular waiting 若幹程序之間形成一種頭尾相接的循環等待資源關系。

預防死鎖就是至少破壞這四個條件其中一項，隻要破壞這四個必要條件中的任意一個條件，死鎖就不會發生。

（1）打破互斥條件。即允許程序同時通路某些資源。但是，有的資源是不允許被同時通路的，像列印機等等，這是由資源本身的屬性所決定的。是以，這種辦法并無實用價值。

（2）打破不可搶占條件。即允許程序強行從占有者那裡奪取某些資源。就是說，當一個程序已占有了某些資源，它又申請新的資源，但不能立即被滿足時，它必須釋放所占有的全部資源，以後再重新申請。它所釋放的資源可以配置設定給其它程序。這就相當于該程序占有的資源被隐蔽地強占了。這種預防死鎖的方法實作起來困難，會降低系統性能。 

（3）打破占有且申請條件。可以實行資源預先配置設定政策。即程序在運作前一次性地向系統申請它所需要的全部資源。如果某個程序所需的全部資源得不到滿足，則不配置設定任何資源，此程序暫不運作。隻有當系統能夠滿足目前程序的全部資源需求時，才一次性地将所申請的資源全部配置設定給該程序。由于運作的程序已占有了它所需的全部資源，是以不會發生占有資源又申請資源的現象，是以不會發生死鎖。但是，這種政策也有如下缺點：

在許多情況下，一個程序在執行之前不可能知道它所需要的全部資源。這是由于程序在執行時是動态的，不可預測的；

資源使用率低。無論所分資源何時用到，一個程序隻有在占有所需的全部資源後才能執行。即使有些資源最後才被該程序用到一次，但該程序在生存期間卻一直占有它們，造成長期占着不用的狀況。這顯然是一種極大的資源浪費；

降低了程序的并發性。因為資源有限，又加上存在浪費，能配置設定到所需全部資源的程序個數就必然少了。

（4）打破循環等待條件，實行資源有序配置設定政策。采用這種政策，即把資源事先分類編号，按号配置設定，使程序在申請，占用資源時不會形成環路。所有程序對資源的請求必須嚴格按資源序号遞增的順序提出。程序占用了小号資源，才能申請大号資源，就不會産生環路，進而預防了死鎖。這種政策與前面的政策相比，資源的使用率和系統吞吐量都有很大提高，但是也存在以下缺點：

限制了程序對資源的請求，同時給系統中所有資源合理編号也是件困難事，并增加了系統開銷；

為了遵循按編号申請的次序，暫不使用的資源也需要提前申請，進而增加了程序對資源的占用時間。

我們也可以嘗試回避死鎖。因為在理論上，死鎖總是可能産生的，是以作業系統嘗試監視所有程序，使其沒有死鎖。

銀行家算法（banker's algorithm）是一個避免死鎖（deadlock）的著名算法，是由艾茲格·迪傑斯特拉在1965年為t.h.e系統設計的一種避免死鎖産生的算法。它以銀行借貸系統的配置設定政策為基礎，判斷并保證系統的安全運作。

在銀行中，客戶申請貸款的數量是有限的，每個客戶在第一次申請貸款時要聲明完成該項目所需的最大資金量，在滿足所有貸款要求時，客戶應及時歸還。銀行家在客戶申請的貸款數量不超過自己擁有的最大值時，都應盡量滿足客戶的需要。在這樣的描述中，銀行家就好比作業系統，資金就是資源，客戶就相當于要申請資源的程序。

  我們首先引入安全序列的定義：所謂系統是安全的，是指系統中的所有程序能夠按照某一種次序配置設定資源，并且依次地運作完畢，這種程序式列{p1，p2，...，pn}就是安全序列。如果存在這樣一個安全序列，則系統是安全的；如果系統不存在這樣一個安全序列，則系統是不安全的。

  安全序列{p1，p2，...，pn}是這樣組成的：若對于每一個程序pi，它需要的附加資源可以被系統中目前可用資源加上所有程序pj目前占有資源之和所滿足，則{p1，p2，...，pn}為一個安全序列，這時系統處于安全狀态，不會進入死鎖狀态。 　

  雖然存在安全序列時一定不會有死鎖發生，但是系統進入不安全狀态（四個死鎖的必要條件同時發生）也未必會産生死鎖。當然，産生死鎖後，系統一定處于不安全狀态。 

  這是一個著名的避免死鎖的算法，是由dijstra首先提出來并加以解決的。　

  一個銀行家如何将一定數目的資金安全地借給若幹個客戶，使這些客戶既能借到錢完成要幹的事，同時銀行家又能收回全部資金而不至于破産，這就是銀行家問題。這個問題同作業系統中資源配置設定問題十分相似：銀行家就像一個作業系統，客戶就像運作的程序，銀行家的資金就是系統的資源。

  一個銀行家擁有一定數量的資金，有若幹個客戶要貸款。每個客戶須在一開始就聲明他所需貸款的總額。若該客戶貸款總額不超過銀行家的資金總數，銀行家可以接收客戶的要求。客戶貸款是以每次一個資金機關（如1萬rmb等）的方式進行的，客戶在借滿所需的全部機關款額之前可能會等待，但銀行家須保證這種等待是有限的，可完成的。

  例如：有三個客戶c1，c2，c3，向銀行家借款，該銀行家的資金總額為10個資金機關，其中c1客戶要借9各資金機關，c2客戶要借3個資金機關，c3客戶要借8個資金機關，總計20個資金機關。某一時刻的狀态如圖所示。

c1 2(7)

c2 2(1)

c3 4(4)

餘額2

餘額4

餘額8

餘額10

    (a)

     (b)

     (c)

     (d)

                                       銀行家算法示意

  對于a圖的狀态，按照安全序列的要求，我們選的第一個客戶應滿足該客戶所需的貸款小于等于銀行家目前所剩餘的錢款，可以看出隻有c2客戶能被滿足：c2客戶需1個資金機關，小銀行家手中的2個資金機關，于是銀行家把1個資金機關借給c2客戶，使之完成工作并歸還所借的3個資金機關的錢，進入b圖。同理，銀行家把4個資金機關借給c3客戶，使其完成工作，在c圖中，隻剩一個客戶c1，它需7個資金機關，這時銀行家有8個資金機關，是以c1也能順利借到錢并完成工作。最後（見圖d）銀行家收回全部10個資金機關，保證不賠本。那麽客戶序列{c1，c2，c3}就是個安全序列，按照這個序列貸款，銀行家才是安全的。否則的話，若在圖b狀态時，銀行家把手中的4個資金機關借給了c1，則出現不安全狀态：這時c1，c3均不能完成工作，而銀行家手中又沒有錢了，系統陷入僵持局面，銀行家也不能收回投資。

  綜上所述，銀行家算法是從目前狀态出發，逐個按安全序列檢查各客戶誰能完成其工作，然後假定其完成工作且歸還全部貸款，再進而檢查下一個能完成工作的客戶，......。如果所有客戶都能完成工作，則找到一個安全序列，銀行家才是安全的。

  從上面分析看出，銀行家算法允許死鎖必要條件中的互斥條件，占有且申請條件，不可搶占條件的存在，這樣，它與預防死鎖的幾種方法相比較，限制條件少了，資源利用程度提高了。

這是該算法的優點。其缺點是：

   〈1〉這個算法要求客戶數保持固定不變，這在多道程式系統中是難以做到的。   

   〈2〉這個算法保證所有客戶在有限的時間内得到滿足，但實時客戶要求快速響應，是以要考慮這個因素。  

    〈3〉由于要尋找一個安全序列，實際上增加了系統的開銷。

最簡單的消除死鎖的辦法是重新開機系統。更好的辦法是終止一個程序的運作。

同樣也可以把一個或多個程序復原到先前的某個狀态。如果一個程序被多次復原，遲遲不能占用必需的系統資源，可能會導緻程序饑餓。