操作系統中死鎖問題的研究

摘要:主要研究操作系統進程的死鎖問題。進程死鎖問題是操作系統的主要問題之一，很多學者專家一直在研究怎樣解決這個問題。首先提出了死鎖的概念，死鎖發生的原因及產生死鎖的四個必要條件，然后又討論了破壞死鎖發生的必要條件，就能預防死鎖的發生，最后具體的談論了死鎖避免的最著名的算法—銀行家算法，從而阻止死鎖的發生。

關鍵詞:死鎖;多道程序;死鎖的必要條件;死鎖的預防;銀行家算法

中圖分類號:TP316文獻標識碼:A文章編號:1009-3044(2009)26-7540-03

Research on the Deathlocking Question in the Operating System

QIN Chao

(Graduction College， Shandong University of Science and Technology， Qingdao 266510， China)

Abstract: The “deadlock” of the operating system process is an important question to be researched， and it is also one of the major problems in the operating system， many scholars and experts are keep on researching how to resolve the question. In this thesis， firstly it came up with the concept of deadlock， the cause of the reason and four necessary conditions for deadlock. And then discussed the necessary condition to damage the occurrence of deadlock， based on this， to prevent the occurrence of deadlock. Finally， it have specifically talked about the best-known algorithm of the deadlock’ avoiding - Banker's Algorithm， to prevent the cause of deadlock.

Key words: deadlock; multi-channel process; the necessary conditions for deadlock; deadlock prevention; banker's algorithm

在計算機系統中，系統資源是有限的，但是往往會有進程對有限資源的占用問題，在早期的系統中，由于系統結構、規模以及資源分配等問題都相對簡單，使得操作系統尚未暴露出死鎖問題的嚴重性。但隨著計算機技術的不斷發展，軟件系統變得很復雜，系統資源的種類日益增多，而且許多資源是獨占資源，又由于進程的并發執行和資源的動態申請以及進程之間的相互通信等，使得系統出現死鎖現象的頻率增加。死鎖的出現，使系統無法正常運行，給系統帶來了極大的危害。因此，死鎖問題的研究已成為操作系統理論的重要課題之一。下面就操作系統的死鎖相關問題進行討論

在多道程序設計中，多個進程可能要去競爭有限的資源。進程請求資源，如果當前這些資源不可用，因為它有可能正在被其它的進程使用著，那么該進程就必須進入等待狀態。正在等待的進程可能不會再改變狀態，因為它所請求的資源一直被其它進程所持有。這種情況被稱為死鎖(deadlock)。

1 死鎖產生的原因

1) 競爭資源。當系統中供多個進程共享的資源如打印機、公用隊列等，其數目不足以滿足諸進程的需要時，會引起諸進程對資源的競爭而產生死鎖。

2) 進程間推進順序不合理。進程在運行過程中，請求和釋放資源的順序不當，也同樣會導致產生進程死鎖。

競爭資源引起的死鎖。系統中的資源分成兩類:可剝奪性資源和非可剝奪性資源。可剝奪性資源是指某進程獲得該類資源后，如果有其他的進程或系統請求使用該資源，該資源就可以被其它的進程或系統剝奪。比如優先級高的進程可以剝奪優先級權低的進程的處理機。不可剝性奪資源是指當系統把該類資源分配給某進程后，再不能強行駁回，只能在該進程使用完后自行釋放，比如，磁帶機，打印機等。系統中所配置的非剝奪性資源，當它們的數量不能滿足諸進程運行的需要，會使進程在運行過程中，因爭奪這些資源而陷入僵局。例如系統中只有一臺打印機和一臺CD-ROM，而此時進程A占有CD-ROM，而進程B占有打印機。若A要求使用打印機，則A將被阻塞。若B要求使用CD-ROM，則B也將被阻塞。于是，在A與B之間便形成了僵局，它們都在等待對方釋放自己所需要的資源。但它們又都因為不能獲得自己需要的資源而不能向前推進，也不能釋放出自己已經占有的資源，因此，就會進入死鎖狀態。如圖1所示。

3) 信號量使用不當也會照成死鎖

進程間彼此相互等待對方發來的消息，結果也會使得這些進程間無法繼續向前推進，即發生了死鎖。例如，A進程等待B進程發來的消息，B進程等待C進程發來的消息，C進程又在等待A進程發來的消息，可以看出A、B和C不是因為競爭同一種資源，而是在等待對方的資源陷入死鎖狀態。這種類型的死鎖在基于消息的系統中比較常見。

4) 其他類型的死鎖

在程序設計中，如果程序設計的不合理，也會產生廣義上的死鎖，這種情況經常可以見到，比如，程序中用到的一些變量、數據結構和一些存儲區。并發進程在使用時，一旦程序設計不合理，往往就會以為別的進程在使用，結果彼此都在等待對方使用完后再使用，結果就出現了死鎖。

2 死鎖產生的必要條件

1) 互斥條件:一個資源每次只能被一個進程使用。

2) 請求與保持條件:一個進程因請求資源而阻塞時，對已獲得的資源保持不放。

3) 不剝奪條件:進程已獲得的資源，在末使用完之前，不能強行剝奪。

4) 循環等待條件:若干進程之間形成一種頭尾相接的循環等待資源關系。

這四個條件是死鎖的必要條件，只要系統發生死鎖，這些條件必然成立，而只要上述條件之一不滿足，就不會發生死鎖。

3 死鎖的預防方法

死鎖預防是設法破壞產生死鎖的必要條件之一，從而消除產生死鎖的任何可能性，嚴格地防止死鎖的出現。但方法過于保守，對資源限制嚴格，使資源利用率和進程執行效率大大降低，它是以降低處理速度作為代價的。

3.1 阻止互斥

破壞第一個條件，使資源可以同時訪問而不是互斥使用，這是個簡單的方法，但在進程并發執行的情況下往往有許多資源是不能同時訪問的(寫操作)，所以這種做法不是都可行的。

只能對可共享的資源(如只讀文件)這樣做。

不適合非共享資源，例如，為寫而打開的文件，打印機等。

3.2 破壞“請求與保持”條件

必須保證:當一個進程申請一個資源時，它不能占有其它資源。也既是采用資源的靜態預分配策略，進程在運行之前，一次申請它所需要的所有資源。此時，如果系統有足夠的資源，便把需要的所有資源分配給該進程，因此，該進程在運行期間就不會在提出資源要求，從而就破壞了請求條件。如果在分配資源時，只要有一種資源不能滿足該進程的需要，就不會分配給它任何資源，而是讓它等待，也即破壞了保持條件，從而避免了死鎖的發生。

優點:簡單安全，易于實施;在進程的活動較單一時性能好;無須搶占。

缺點:資源利用率低;啟動進程慢，效率低;有“饑餓”現象存在。

3.3 破壞“不剝奪”條件(允許搶占)

方法1:若擁有某種資源的進程在申請其他資源時遭到拒絕，則它必須釋放其占用的資源，以后若有必要可再次申請上述資源。也就是說某一進程已經占有的資源，在運行過程會被暫時釋放掉，也可以說是被剝奪了，從而破壞了“不剝奪”條件。

方法2:當一進程申請的資源正被其他進程占用時，可通過操作系統搶占該資源，此方法在兩個進程優先級相同時，不能防止死鎖。

優點:對狀態容易保留和恢復的資源較為方便。

缺點:實現困難，恢復現場代價高;導致過多的不必要搶占;易導致循環重啟。

3.4 破壞“循環等待 ”條件

采用資源定序方法，將所有資源按類型進行線性排隊，并按遞增規則編號。例如，把輸入機的序號為1，打印機的序號為2，磁盤的為3.進程只能以遞增方式申請資源，因而不會導致循環等待。

如果進程申請一個資源，它首先必須釋放所有比該資源編號大的資源。

優點:資源的申請與分配逐步進行，比預分配策略的資源利用率高;易實現編譯期間的檢查;無須執行時間，在系統設計階段問題就已解決。

缺點:嚴格限制資源的順序性，不允許增加資源請求;在使用資源的順序與系統規定不一致時，資源利用率降低;不能搶占。

4 銀行家算法

死鎖避免方法并不是嚴格限制產生死鎖必要條件的存在，而只是防止系統進入不安全狀態，從而避免死鎖的發生。死鎖避免算法就是避免系統進入不安全狀態的算法。銀行家(Banker)算法是最著名的死鎖避免算法。

銀行家算法的主要思想是:它是從當前的狀態S出發，逐個檢查各申請者中誰獲得資源能完成其工作，然后假定其完成工作且歸還全部資源，再進一步檢查誰又獲得資源能完成其工作。若所有申請者均能完成工作，則系統狀態是安全的。

如果存在一個安全序列，那么系統處于安全狀態。

存在進程順序 P1、P2、P3、…、 Pn

如果對于每個 Pi ，Pi 申請的資源小于當前可用資源加上所有進程 Pj (其中 j

如果沒有這樣的順序存在，那么系統就處于不安全狀態。

兩個矩陣:Max(進程最大需求量)

其中Max(2，3)元素值為2，表示進程P2對資源R3的最大需求為3個Allocation(進程已分配量)

其中Allocation(2，2)元素值為1，表示系統為進程P2已分配R2資源 1個

進程尚需量:Need=Max-Allocation

銀行家算法如下:

1)if(Request[i]<=Need[i])執行2);

2)if(Request[i]<=Available)執行3);

else wait();表示尚無足夠資源，Pi須等待。

3)系統試探性把要求的資源分給Pi(類似回溯算法)。

并根據分配修改下面數據結構中的值。

Available[i] = Available[i]–Request[i];

Allocation[i] = Allocation[i] + Request[i];

Need[i] = Need[i]-Request[i];

4)執行安全性檢查，檢查此次資源分配后，系統是否還處于安全狀態。若安全，才正式將資源分配給進程;否則，試探方案作廢，恢復原資源分配表，進程Pi等待。

安全性檢測算法:

設置兩個向量:

Free:是一個縱向量，表示系統空閑的各類資源數

Finish:是一個縱向量，表示進程能否得到全部資源使之運行完成。

執行安全算法開始時:

Free = Available，Finish[i]:=1(i=1，2，…，n)

1)從進程集中找一個能滿足下述條件的進程Pi

① Finish[i] = 1(未定) ② Need[i] <= Free (資源夠分)

2)當Pi獲得資源后，認為它完成，回收資源:

Free = Free + Allocation[i] ;Finish[i] = true ;

goto1);

若Finish[1…n]=true，則系統是安全的，可以實施分配，否則系統不安全，撤銷分配。

5 總結

死鎖發生的原因和預防的方法是操作系統的核心問題之一，而如何有效的利用死鎖的充分必要條件去預防，判斷和解除可能存在的死鎖危機，是死鎖問題研究的核心。在一個系統的執行過程中應經常檢測是否發生了死鎖，而一旦發生了死鎖，又應該如何的去解決它。希望本文的討論有利于讀者對死鎖問題的深刻理解，并能進一步研究解決死鎖問題的方法。

參考文獻:

[1] 湯子贏，哲鳳屏，湯小丹.計算機操作系統[M].西安:西安電子科技大學出版社，2006.

[2] 張堯學，史美林.計算機操作系統教程[M].北京:清華大學出版社，1992.

[3] 龐麗萍.操作系統原理[M].3版.武漢:華中科技大學出版社，2004.

[4] 吳企淵.計算機操作系統[M].北京:清華大學出版社，2006.

[5] 左萬歷，王拉柱.銀行家算法的改進[J].吉林大學自然科學學報，1997(1).

[6] 甄志龍，于遠誠.OS 中死鎖問題的狀態模型探討[J].通化師范學院學報，2005(26):23-25.

[7] 劉義常.操作系統原理[M].北京:中國水電出版社，2006.

[8] 陸麗娜.分布式操作系統[M].北京:電子工業出版社，2005.