1、 從進程同步的概念可以知道，當并發進程需求競爭運用資源或需求相互協作向前推進時，假設不采取同步措施，或同步措施不恰當，那么很容易導致并發進程不能向前推進而墮入僵局，即死鎖景象。死鎖是發生在一組相互競爭或協作的進程與線程之間的一個非正常景象。 死鎖是一切操作系統都面臨著的潛在問題，操作系統除了需求預防死鎖、防止死鎖外，還需求可以檢測死鎖，并從死鎖中進展恢復。本章的主要內容如下： 死鎖的產生； 死鎖的預防； 死鎖的防止； 死鎖的檢測和解除； 線程死鎖。5.1 死鎖的產生死鎖的產生5.1.1 死鎖產生的緣由死鎖產生的緣由競爭資源引起死鎖競爭資源引起死鎖 在多道程序系統，多個進程共享系統的資源。系統資

2、在多道程序系統，多個進程共享系統的資源。系統資源分為二類，一類是不可搶占的資源，如打印機、源分為二類，一類是不可搶占的資源，如打印機、磁帶機等。當系統把這類資源分配給某進程后，再磁帶機等。當系統把這類資源分配給某進程后，再不能強行收回，只能在進程用完后自動釋放。另一不能強行收回，只能在進程用完后自動釋放。另一類是可搶占的資源，如類是可搶占的資源，如CPU、內存等。由于系統擁有、內存等。由于系統擁有的不可搶占的資源有限，多個進程共享競爭不可搶的不可搶占的資源有限，多個進程共享競爭不可搶占的資源就能夠引起死鎖。占的資源就能夠引起死鎖。進程推進順序不當引起死鎖進程推進順序不當引起死鎖 在多道程序系統

3、中，并發執行的進程推進序列不可在多道程序系統中，并發執行的進程推進序列不可予測，有些推進順序，進程可以順利完成，這些推予測，有些推進順序，進程可以順利完成，這些推進順序是合法的；而有的推進順序會引起進程無限進順序是合法的；而有的推進順序會引起進程無限期地等待永遠不會發生的條件而不能向前推進，呵期地等待永遠不會發生的條件而不能向前推進，呵斥了死鎖。斥了死鎖。5.1.1 死鎖產生的緣由續死鎖產生的緣由續 進程推進順序不當引起死鎖例： 進程P和Q并發執行，進程P和Q程序如下： Process P Process Q . . Get A Get B . . Get B Get A . . Releas

4、e A Release B . . Release B Release A . . 5.1.1 死鎖產生的緣由續死鎖產生的緣由續PAQB當當P、Q按如下次序執行時：按如下次序執行時：P: GET A Q:GET BP:GET BQ:GET AABCS2S1S3哲學家吃面的問題哲學家吃面的問題A:P(S1)P(S3)EatingV(S3)V(S1)B:P(S2)P(S1)EatingV(S1)V(S2)C:P(S3)P(S2)EatingV(S2)V(S3)A: P(S1), B:P(S2),C:P(S3)A:P(S3) :阻塞阻塞B:P(S1):阻塞阻塞C: P(S2):阻塞阻塞AS1CS3S

5、2B5.1.2 死鎖產生的條件死鎖產生的條件1.1.產生死鎖的必要條件產生死鎖的必要條件 Conditions for Deadlock Conditions for Deadlock 互斥互斥 Mutual exclusion Mutual exclusion 條件：一個資源一次只能被一個條件：一個資源一次只能被一個進程所運用，即是排它性運用。進程所運用，即是排它性運用。不可搶占不可搶占 No preemption No preemption 條件：一個資源僅能被占有它條件：一個資源僅能被占有它的進程所釋放，而不能被別的進程侵占。的進程所釋放，而不能被別的進程侵占。懇求和堅持懇求和堅持 Ho

6、ld-and-wait Hold-and-wait 條件：進程曾經堅持了至少條件：進程曾經堅持了至少一個資源，但又提出了新的資源要求，而該資源又已被其它一個資源，但又提出了新的資源要求，而該資源又已被其它進程占有，此時懇求進程阻塞，但又對曾經獲得的其它資源進程占有，此時懇求進程阻塞，但又對曾經獲得的其它資源堅持不放。堅持不放。環路等待環路等待 Circular wait Circular wait 條件：當每類資源只需一個時，條件：當每類資源只需一個時，在發生死鎖時，必然存在一個進程在發生死鎖時，必然存在一個進程- -資源的環形鏈。如一系資源的環形鏈。如一系統形狀的資源分配圖所示，統形狀的資源

7、分配圖所示，P1P1正在等待一個正在等待一個P2 P2 占用的資源占用的資源R2R2，P2P2正在等待一個正在等待一個P1P1占用的資源占用的資源R1R1。 5.1.2 死鎖產生的條件(續)2. 資源分配圖由結點和邊組成。結點有二類，一類是進程結點，用園圈表示；另一類是資源結點，用小方框表示一類資源，用方框中的小圈表示資源數。邊也有二類，一類是分配邊，它由資源結點指向進程結點，另一類是懇求邊，它由進程結點指向資源結點。前往 R1 R1R2 P1P25.1.2 死鎖產生的條件死鎖產生的條件(續續)3. 3. 處置死鎖的根本方法處置死鎖的根本方法a. a. 死鎖的預防死鎖的預防 靜態方法：在進程執

8、行前采取的措施，經過設置某些限制條靜態方法：在進程執行前采取的措施，經過設置某些限制條件，去破壞產生死鎖的四個必要條件之一，防止發生死鎖。件，去破壞產生死鎖的四個必要條件之一，防止發生死鎖。B.B.死鎖的防止死鎖的防止 動態的方法：在進程執行過程中采取的措施，不需事先采動態的方法：在進程執行過程中采取的措施，不需事先采取限制措施破壞產生死鎖的必要條件，而是在進程懇求資源取限制措施破壞產生死鎖的必要條件，而是在進程懇求資源時用某種方法去防止系統進入不平安形狀，從而防止發生死時用某種方法去防止系統進入不平安形狀，從而防止發生死鎖。鎖。C.C.死鎖的檢測和解除死鎖的檢測和解除 這種方法預先并不采用任

9、何限制措施，允許系統在運轉過這種方法預先并不采用任何限制措施，允許系統在運轉過程中發生死鎖，但可經過系統設置的檢測機構及時檢測死鎖程中發生死鎖，但可經過系統設置的檢測機構及時檢測死鎖的發生，如檢測到死鎖，那么采用吊銷進程等死鎖解除方法的發生，如檢測到死鎖，那么采用吊銷進程等死鎖解除方法使系統正常任務。使系統正常任務。5.2 死死 鎖鎖 預預 防防(Deadlock Prevention) 預防死鎖的方法是破壞四個產生死鎖的必要條件之一。1。破壞互斥條件 互斥運用是資源本身特征所決議的。運用硬軟件結合可改動資源本身特性，例如采用SPOOLing技術可將“獨享 打印機改動為“共享的打印機。2。破壞

10、不可搶占條件 搶占式調度法主要用于處置機和存貯器資源調度，它們的形狀容易保管和恢復。但此法對外部設備和私存數據不宜運用。5.2 死死 鎖鎖 預預 防防(Deadlock Prevention) -13。破壞懇求和堅持條件 系統可采用資源靜態予分配方式來破壞懇求堅持條件。系統要求一切進程一次性地懇求在整個運轉過程中全部資源，假設系統有足夠資源滿足給進程，那么在運轉前，一次性將其所需求的一切資源分配給該進程。這樣該進程在整個運轉期間，便不再提出資源要求，從而摒棄了懇求條件。這種預防死鎖的方法，優點是簡單、易予實現且很平安，但其資源利用率很低，進程也延遲運轉。4。破壞循環等待條件 有序資源運用法 該

11、方法將一切的資源按類型進展線性排隊，并賦予不同的序號。例如令輸入機的序號為1，打印機序號為2，磁盤機序號為3等。5.2 死死 鎖鎖 預預 防防(Deadlock Prevention) -2 一切進程對資源的懇求必需嚴厲按資源序號遞增的次序提出。這樣在所構成的資源分配圖中不能夠再出現環路，因此摒棄了“環路等待條件，在采用這種戰略時總有一個進程占據了較高序號的資源，它繼續懇求的資源必然是空閑的，因此進程可以不斷向前推進。這種預防死鎖的戰略可以提高資源利用率，但在進程運用各類資源的順序與系統規定的順序不同時會呵斥資源浪費的情況。資源按級分配法 該方法是把資源遞增排序成假設干等級如L1、L2.Lm，

12、其中每級可包含幾類資源，要求每個進程在獲得了Lj級中資源之后 ，它才干懇求更高級的LKLKLj級中的資源；假設它還需懇求比LK級低的LI級LI 4 P2 4 2 2 = 4 由于找不到一個平安序列使一切進程順序地一個個地運轉終了，所以T1形狀是不平安形狀，由于實施分配給1臺磁帶機給P3的操作會引起系統形狀由平安形狀T0向不平安形狀下的轉換，所以為了防止死鎖，上述的分配只是平安檢測，檢測后斷定這樣的懇求不能滿足，P3為懇求1臺磁帶機而必需阻塞等待。3.3.利用銀行家算法防止死鎖利用銀行家算法防止死鎖 最具代表的防止死鎖算法是Dijkstra的銀行家算法，這是由于該算法用于銀行系統現金貸款的發放而

13、得名。銀行家算法的數據構造可用資源向量 Available m m為系統中資源種類數，Availablej=k表示系統中第j類資源數為k個。最大需求矩陣Maxn，m n為系統中進程數，Maxi,j=k表示進程i對j類資源的最大需求數為中k。分配矩陣Allocationn，m 它定義了系統中每一類資源當前已分配給每一進程資源數， Allocationi,j=k表示進程i已分得j類資源的數目為k個。3.3.利用銀行家算法防止死鎖利用銀行家算法防止死鎖-1-1需求矩陣Needn,m 它表示每個進程尚需的各類資源數，Needi,j=k 表示進程i還需求j類資源k個。Needi,j=Maxi,j-All

14、ocationi,j銀行家算法假設在進程并發執行時進程i提出懇求j類資源k個后，表示為Requestij=k。系統按下述步驟進展平安檢查： 假設RequestiNeedi那么繼續以下檢查，否那么顯示需求懇求超出最大需求值的錯誤。 假設RequestiAvailable那么繼續以下檢查，否那么顯示系統無足夠資源，Pi阻塞等待。 系統試探把要求的資源分配給進程i并修正有關數據構造的值： Available = Available-Requesti ； Allocationi =Allocationi+Requesti ； Needi=Needi-Requesti ； 3.利用銀行家算法防止死鎖-2

15、 系統執行平安性算法，檢查此次資源分配后，系統能否處于平安形狀，假設平安，才正式將資源分配給進程i，以完本錢次分配；否那么將試探分配作廢，恢復原來的資源分配形狀，讓進程Pi等待。平安性算法平安性算法執行步驟如下：A.初始化設置任務向量Workm表示系統可提供的各類資源數目，用以維護原數據構造有關值。Work = Available，設置完成標志向量 Finishn。Finishi = false 表示i進程尚末完成，如值為true那么表示進程i已完成。B.從進程集合n中找到一個能滿足下述二個條件: Finishi = false和NecdiWork，如找到那么執行步驟C，如找不到同時滿足以上二

16、條件的進程那么執行步驟D。3.3.利用銀行家算法防止死鎖利用銀行家算法防止死鎖-3-3C.當進程i獲得資源后可順利執行直到完成，并釋放出分配給它的資源，表示如下： work = work+Allocationi ； Finishi=true ；轉執行步驟B。D.假設一切的Finishiture，那么表示系統處于平安形狀，否那么系統處于不平安形狀。銀行家算法例：銀行家算法例： 假定系統中有五個進程P0、P1、P2、P3、P4和三種類型資源A、B、C，每一種資源的數量分別為10、5、7。各進程的最大需求、T0時辰資源分配情況如下 所示。 Max Allocation Need Available

17、A B CA B C A B C A B C P0 7 5 3 0 1 0 7 4 3 3 3 2 P1 3 2 2 2 0 0 1 2 2P2 9 0 2 3 0 2 6 0 0P3 2 2 2 2 1 1 0 1 1P4 4 3 3 0 0 2 4 3 1試問： T0時辰能否平安？ P1懇求資源Request1(1,0,2)能否允許？ P4懇求資源Request4(3,3,0)能否允許？ 銀行家算法例銀行家算法例-1-1 T0時辰能否平安？ 從表中可找出一個序列(P1 、 P3、 P4 、 P2 、 P0使各進程順序地一個個地執行完成。 Max Allocation Need Availa

18、ble Available ( 分 配 資 源 前 ) (釋放資源后 A B C A B C A B C A B C A B C P0 7 5 3 0 1 0 7 4 3 = 10 4 7 10 5 7 P1 3 2 2 2 0 0 1 2 2 = 3 3 2 5 3 2 P2 9 0 2 3 0 2 6 0 0 = 7 4 5 10 4 7 P3 2 2 2 2 1 1 0 1 1 = 5 3 2 7 4 3 P4 4 3 3 0 0 2 4 3 1 = 7 4 3 7 4 5 平安序列為P1、P3、P4、P2、P0，T0時辰系統是平安的。 P1懇求資源Request1(1,0,2)可否允許

19、？銀行家算法例銀行家算法例-2-2Request1(1,0,2)Need1(1,2,2)，P1懇求在最大需求范圍內。Request1(1,0,2) Available(3,3,2)，可用資源可滿足P1懇求需求。試探把要求的資源分配給進程P1并修正有關數據構造的數值：Available = Available(3，3，2)Request1(1,0,2)=Available(2,3,0)；Need1 = Need1(1,2,2)Request1(1,0,2)= Need1(0,2,0)；Allocation1 =Allocation1(2,0,0)+Request1(1,0,2)=Allocati

20、on1(3,0,2)；利用平安性算法檢查試探將資源分配后形狀的平安性如下：銀行家算法例銀行家算法例-3-3 Max Allocation Need Available Available (分配資源前) (釋放資源后 A B C A B C A B C A B C A B CP0 7 5 3 0 1 0 7 4 3 = 10 4 7 10 5 7P1 3 2 2 3 0 2 0 2 0 = 2 3 0 5 3 2P2 9 0 2 3 0 2 6 0 0 = 7 4 5 10 4 7P3 2 2 2 2 1 1 0 1 1 = 5 3 2 7 4 3P4 4 3 3 0 0 2 4 3 1 =

21、7 4 3 7 4 5 由于先分配資源給P1進程符合按平安序列P1、P3、P4、P2、P0分配資源，所以試探將資源分配給進程P1后的形狀是平安的，可將資源分配給進程P1。P4懇求資源Request4(3,3,0)能否允許？Request4(3,3,0)Need4(4,3,1)，P4懇求在最大需求范圍內。Request4(3,3,0)Available(2,3,0)不成立，即可用資源暫不能滿足P4懇求資源需求，P4阻塞等待。 5.4 死鎖的檢測和解除死鎖的檢測和解除(Deadlock Detection) 5.4.1 死鎖的檢測死鎖的檢測 死鎖的防止算法添加了系統的開銷，死鎖的檢測采用資源分死鎖

22、的防止算法添加了系統的開銷，死鎖的檢測采用資源分配圖的簡化判別能否發生了不平安形狀。如發現系統處于不配圖的簡化判別能否發生了不平安形狀。如發現系統處于不平安形狀時，即執行死鎖解除的戰略，采用此法開銷相對減平安形狀時，即執行死鎖解除的戰略，采用此法開銷相對減少。少。1.資源分配圖的簡化：資源分配圖的簡化： 系統處于某系統處于某S形狀時可用資源分配圖表示，可用資源分配圖簡形狀時可用資源分配圖表示，可用資源分配圖簡化來判別系統能否處于死鎖形狀。資源分配圖簡化的方法如化來判別系統能否處于死鎖形狀。資源分配圖簡化的方法如下：在資源分配圖中找一個既不阻塞又非孤立的進程結點下：在資源分配圖中找一個既不阻塞又

23、非孤立的進程結點PI如某進程既無已分配的資源也不需懇求資源，即既無分配如某進程既無已分配的資源也不需懇求資源，即既無分配邊又無懇求邊，那么該進程結點是孤立結點，讓它獲得所邊又無懇求邊，那么該進程結點是孤立結點，讓它獲得所需資源而繼續運轉直至終了，再釋放它擁有的一切的資源，需資源而繼續運轉直至終了，再釋放它擁有的一切的資源，這相當于取消這相當于取消PI的分配邊和懇求邊，使它成為孤立結點。的分配邊和懇求邊，使它成為孤立結點。 經過以上簡化，如一切的進程結點都是孤立結點那么稱資源經過以上簡化，如一切的進程結點都是孤立結點那么稱資源分配圖是可完全簡化的。假設不能經過任何過程使該圖完全分配圖是可完全簡化

24、的。假設不能經過任何過程使該圖完全簡化，那么該圖是不可完全簡化的。資源分配圖簡化如以下簡化，那么該圖是不可完全簡化的。資源分配圖簡化如以下圖：圖： R1 R2 R1 R2 。P1 資源分配圖的簡化例：資源分配圖的簡化例：。 。P1P2。 。 。P1P2。 。P2。R1 R1 R2R25.4.1 死鎖的檢測死鎖的檢測-12.2.死鎖定理：死鎖定理： S S為死鎖形狀的充分條件是：尚且僅當為死鎖形狀的充分條件是：尚且僅當S S形狀的資源分形狀的資源分配圖是不可完全簡化的，該充分條件稱為死鎖定理。配圖是不可完全簡化的，該充分條件稱為死鎖定理。3. 3. 死鎖檢測的數據和算法類似于銀行家算法。死鎖檢測

25、的數據和算法類似于銀行家算法。5.4.2 死鎖解除死鎖解除 當檢測死鎖的軟件判別死鎖存在時，就要解除死鎖，使系統從死鎖中恢復。 1利用終了死鎖進程釋放資源 強迫性地從系統中吊銷一個或多個死鎖的進程以斷開循環等待鏈，并收回分配給終止進程的全部資源供剩下的進程運用。借助于吊銷進程來解除死鎖可以運用兩種方法。一種是吊銷全部的死鎖進程，這顯然會斷開死鎖環路，但代價太大。另一種方法是逐個吊銷死鎖的進程直至死鎖環路消除。這里存在一個按照什么原那么進展逐個吊銷進程的問題。目前較適用而又簡便的方法是吊銷那些代價最小的進程。所謂影響一個進程的吊銷代價要素有該進程的優先權，該進程運轉到今的運轉代價包括CPU時間，

26、運用資源的種類和時間等、與相關的作業類型和外部代價等。死鎖的解除死鎖的解除-12利用資源搶占利用資源搶占死鎖恢復的另一種方法是運用一個有效的掛起和解死鎖恢復的另一種方法是運用一個有效的掛起和解除機構來掛起一些死鎖的進程，其本質是從被掛除機構來掛起一些死鎖的進程，其本質是從被掛起的進程那里搶占資源以解除死鎖，許多學者以起的進程那里搶占資源以解除死鎖，許多學者以為在此領域的研討任務比起其它死鎖恢復的方法為在此領域的研討任務比起其它死鎖恢復的方法更為重要。問題：現場包擴更為重要。問題：現場包擴CPU、內存、外設、內存、外設的形狀維護不益處理的形狀維護不益處理3利用回退釋放資源利用回退釋放資源例如一個系統提供了檢查點和重新啟動的便利的話，例