死鎖產生的四個必要條件，什麽時候會發生死鎖，發生死鎖之後應該做什麽處理？或者說我們應該怎麽避免死鎖的發生？

其實死鎖這個概念在之前哲學家進餐問題當中就已經提到過，如果五個哲學家進程都并發地執行，

那麽他們有可能依次拿起自己左手邊的筷子。但是之後當他們都嘗試拿起右手邊的筷子的時候，發現右邊那支筷子已經被另一個哲學家就是自己右手邊的哲學家所占領了，

所以這種情況下就會發生這種循環等待的現象。每一個哲學家手裏都持有一支他的左邊那個哲學家想要的筷子，但是他同時又在等待他右邊的那個哲學家手裏的那支筷子，所以在這種情況下所有哲學家都是阻塞狀態，沒有一個哲學家進程可以順利地往下推進，因此這種情況下就稱爲發生了所謂的死鎖現象。

而飢餓這個概念咱們在之前處理機調度的時候提到過，是由於進程長期得不到想要的資源，而無法向前推進的現象。比如說咱們之前介紹短進程優先算法的時候，如果說用短進程優先算法，那麽系統中有源源不斷的短進程到來的話，長進程就會一直得不到處理機這種資源，所以就導致了長進程飢餓的現象。而死循環是指某種進程在執行的過程中因爲遇到一些問題所以一直跳不出某一個循環，比如說while循環或者for循環這樣的現象。當然有時候這個死循環是因爲我們自己程序邏輯的BUG而導致的，有的時候又是程序員故意設計的，比如說之前咱們寫過的那些PV操作的代碼，其實就是故意設計成死循環的。那麽這兒所指的死循環其實特指的是這種程序邏輯BUG導致的死循環，導致了一個進程沒有辦法按照我們期待的那樣順利地往下推進。那這三個概念的共同點在於它們都是進程發生了某種異常的狀況而無法繼續往下推進的這種現象，所以這三個概念其實比較容易在選擇題當中放在一起，對大家進行考察。所以發生死鎖的話肯定至少是有兩個或者兩個以上的進程同時發生死鎖，因爲如果只有一個進程的話那麽怎麽循環等待對方手裏的資源呢？所以由於死鎖的進程是在等待某一種資源的分配，因此發生死鎖的進程肯定是處於阻塞態。而飢餓和死鎖不同，在剛才的短進程優先算法這個分析過程中我們也會發現，即使系統當中只有一個長進程，然後有別的源源不斷的短進程到達，那這個長進程有可能是它自己處於飢餓的狀態，因此如果説發生飢餓的話，可能是只有一個進程發生飢餓，而死鎖的話肯定是兩個或者兩個以上的進程同時死鎖。發生飢餓的進程有可能是長期得不到自己想要的某種資源，比如說I/O設備，但有可能是像上面這兒所提到的這樣，是長期得不到處理機的服務。所以，發生飢餓這種現象的進程，它有可能是處於阻塞態的，也有可能是處於就緒態的。另外，處於死循環這種狀態的進程有可能只有一個。并且死循環狀態的進程它是可以上處理機運行的，這個如果寫過程序的話大家應該也有這種體會。比如說自己寫一個死循環，不斷地輸出Hello World，那麽你會發現那個屏幕上不斷地會有Hello World被打印出來，所以死循環的進程其實是可以上處理機運行的。因此處於這種狀態的進程，它有可能是處於運行態的。而死鎖和飢餓的進程它們肯定不會是運行態。死鎖和飢餓的問題一般來説是由於操作系統分配資源的這種策略不合理而導致的，比如說像剛才咱們提到的飢餓這種現象，就是由於操作系統分配處理機這種資源的策略不合理，所以導致了長進程飢餓。而對於死循環這種現象來説，它是由寫程序的那個人導致的，是由代碼邏輯的錯誤導致的，所以死鎖和飢餓應該是操作系統需要關心、需要嘗試解決的問題。而死循環應該是寫程序的那個應用程序員來關心的問題。所以在操作系統這門課中，有的地方會說怎麽解決死鎖，有的地方說怎麽解決飢餓，但是它從來不説怎麽解決死循環，因爲解決死循環根本就不是操作系統應該來負責處理的問題。所以這就是死鎖、飢餓、死循環這三個概念的聯係和區別。

在發生死鎖的時候一定是會有這種循環等待資源的現象的，但是發生了循環等待資源現象的時候未必就一定發生了死鎖。

因此可以看到，即使發了循環等待資源的現象，但是如果還有別的進程持有一個同類型的、可以替代的資源，那麽死鎖是不一定發生的。但是如果說一個系統當中每一類資源都只有一個，那麽循環等待就是死鎖的充分必要條件了。所以在發生了循環等待現象，同時又滿足系統中每類資源只有一個這個條件的時候，那循環等待就必然是會導致死鎖的。

其實我們可以把互斥信號量和同步信號量也看做一種抽象的系統資源。所以其實上面這麽多東西我們可以總結為一句話，就是說當對不可剝奪的資源的分配不合理的時候，就有可能會導致死鎖。

前面這兩種解決方案，是不會引起死鎖現象的。而第三種解決方案是允許死鎖的發生，但是操作系統會要負責檢查到底有沒有死鎖發生。如果此時發生了，那麽就需要通過某種策略來解除死鎖。

死鎖和飢餓、死循環這幾個比較容易混淆的概念它們有什麽區別，這個大家一定要著重體會，很容易作爲選擇題來作爲考察。介紹了死鎖產生的四個必要條件。其中循環等待條件的這個知識點是比較容易作爲選擇題的陷阱來考察的。循環等待未必導致死鎖，而死鎖一定是會有循環等待現象的。那當然其他的這些條件也需要體會，并且通過課後的習題來進行進一步的鞏固。死鎖處理的三種策略。那麽預防死鎖是要破壞死鎖產生的這四個必要條件。

因为打印机这种资源它是必须互斥使用的资源，同一时刻只能供一个进程使用。而如果采用了SPOOLing技术之后，各个进程对打印机发出的请求会首先被输出进程给接收。同样的，进程2如果也想输出的话，也会直接被输出进程给接收。那么当它们的这些请求被接收并且被响应了之后，这些进程就可以开始顺利地往下执行别的事情了。 

那之后输出进程会根据各个进程的请求把它依次放到打印机上打印输出。

所以其实采用了SPOOLing技术之后，虽然打印机它是一种必须互斥使用的独占设备，但是进程1和进程2它们俩即便是同时想要使用打印机的话，那么它们的请求也可以及时地被接收，也就是被输出进程先暂时被它们保管，然后之后再慢慢地输出。所以从逻辑上看，对于这些进程来说，在它们看来，它们所使用的就并不是一个独占设备，而是一个共享设备，在它们看来是这样的。但其实是操作系统采用了SPOOLing技术，把互斥使用的资源改造成了一个可以共享使用的资源。因此，其实互斥条件是可以破坏的，但是在很多时候其实并不是所有的设备都可以被改造成共享的设备，并且甚至为了系统安全，有很多地方还必须保证这种互斥性，所以破坏互斥条件这个思路其实适用的范围并不广。这是它的缺点。

 那么在CPU资源被剥夺的时候，之前在CPU上运行的那个进程它的CPU寄存器之类的一些中间数据就需要被保存。所以其实从这个角度来看也可以发现，这种方式实现起来其实还是比较复杂的。因此如果一直发生这种全部放弃的这种事情的话，那么这个进程就有可能会一直保持饥饿的状态，它没办法往下推进。那这是破坏不可剥夺条件这种策略的一些缺点。

所以如果發生進程的相互等待的話，那麽只有可能是擁有小編號資源的進程在等待擁有大編號資源的進程。而不可能是擁有大編號資源的進程，反向回來等待擁有小編號資源的進程，因此這就不可能發生循環等待鏈。所以這就是這種方案能可以破壞循環等待條件的原因。那麽我們還可以從另外一個角度來分析，所以不管在什麽時刻，系統當中肯定會有一個進程它所擁有的資源編號是最大的，比如說像這個地方的P3進程，那麽也就意味著大於7號的那些資源，8、9、10號資源，此時肯定是空閑的，沒有被任何進程所占用。所以如果說P3進程繼續往下執行的話，那麽它所申請的資源肯定只可能是大於7號的那些資源，也就是8號、9號、10號，而這些資源肯定可以暢通無阻地全部分配給P3進程。因此至少P3進程是可以順利地獲得所有它所需要的資源并且順利地執行結束的。所以從這個角度來分析，也不可能出現所有的進程都阻塞的這種死鎖現象。如果說一個進程它實際使用資源的順序和這些編號遞增的順序不一致的話，就有可能會導致資源的浪費。比如説P3進程需要使用5號資源打印機，也需要使用七號資源掃描儀，但是實際的使用過程中，P3進程它是需要先使用掃描儀再使用打印機的，但是由於這個編號遞增的這種要求，P3進程又必須先申請占有它暫時用不到的那個資源，也就是打印機，之後打印機會空閑很長一段時間，一直到掃描儀被使用完了，才會回頭再使用打印機這種資源，所以這就造成了打印機資源的長時間空閑，因此就導致了系統資源的浪費。比如說在一個系統當中打印機的編號是5號，掃描儀的編號是7號，那一個用戶程序如果既需要使用打印機又需要使用掃描儀的話，那用戶編程的時候，就需要先編寫申請使用打印機的那個代碼，因爲5號，因爲打印機的編號是更小的，之後再寫申請使用掃描儀的那個代碼。而如果換一個系統，另一個系統對掃描儀和打印機的編號剛好是相反的，掃描儀的編號更小，打印機的編號更大，那麽用戶的程序就需要爲此發生改變。它需要把申請掃描儀資源的代碼，把它放到申請打印機那個代碼之前，所以很顯然，這種方式會造成用戶編程的極大不便。

可以看到，這個小節介紹的預防死鎖的這些策略，或多或少都存在一些缺陷。那這個小節的内容比較容易結合死鎖產生的四個必要條件在選擇題當中進行考查。同學們主要是以理解爲主，不需要死記硬背，當然也需要稍微地記憶一下，大概可以用什麽樣的方法來破壞這些必要條件。另外呢之前咱們在講哲學家進餐問題的時候，講到了三種處理死鎖的方法。那學完這個小節的内容之後，大家可以再回頭去分析一下，那三種方法分別是破壞了哪一個條件。那復習考研的過程中，其實這樣的事情是很關鍵的，需要在學習後面的内容之後，再和前面的内容進行聯係，把所有的這些知識都織成一個網狀，而不是一個獨立的點狀的知識。

在這個小節中我們會介紹死鎖處理的第二種策略，避免死鎖。銀行家算法是用於避免死鎖的最著名的一個算法，那這個算法很容易在小題和大題當中進行考查，所以這個小節的内容是十分重要的。

 所以和之前所説的給B借30億那種情況不同，如果給A借了20億，那這個局并不是一個死局。我們只需要按T-B-A這樣的順序依次給各個企業借錢，那麽這些企業總是可以依次地得到滿足的。

那其實我們還可以換種順序。

比如説，所以如果我們按A->T->B這樣的順序依次滿足各個企業的需求的話，那麽其實這些企業也並不是一個死局。因此經過考慮，A想借20億的這個請求我們是可以答應的，是安全的。

當然，通過之前的分析我們也知道，安全序列有時候并不唯一。那如果分配了資源之後，再也找不到任何一個所謂的安全序列，那麽系統就進入了不安全狀態。所以所有的企業都會被阻塞，於是系統就進入了死鎖的狀態。那如果系統中能找到一個所謂的安全序列，説明系統是處於安全狀態的，在這種情況下一定不會發生死鎖。而如果系統進入了不安全狀態，也就是找不到任何一個安全序列，那麽就有可能會發生死鎖。注意，只是有可能，并不一定發生死鎖。因此，進入不安全狀態未必發生死鎖，但是如果發生了死鎖一定是處於不安全狀態。這個地方很容易作爲選擇題考查，大家一定要理清楚這幾個狀態的關係。那根據之前的這些分析，我們得到了一個新的處理死鎖的思路，我們可以在分配資源之前，預先判斷一下這次分配是不是會導致系統進入不安全的狀態。如果系統會進入不安全狀態，那麽就意味著這次分配之後有可能會發生死鎖，那我們就不應該允許這次分配。如果系統不會進入不安全狀態，那麽就意味著這次分配是安全的，即使進行了分配，那系統也暫時不可能發生死鎖。所以這也是銀行家算法的一個核心思想。

但是在計算機當中，可能會有打印機有掃描儀有攝像頭各種各樣的資源。

那麽我們根據剛才分析的情況，來看一下此時這個系統到底是不是處於安全狀態。

那剛才所説的這個算法就是所謂的安全性算法，我們可以很方便地用代碼來實現上面的這些流程，無非就是一些數組再加上一些循環的邏輯。我們可以每一輪都從編號比較小的這些進程開始檢查。

但實際上如果我們在考試當中，一般來説是用筆算的，可以用一種更快的方法來找到安全序列。

怎麽用安全性算法來判斷系統到底是不是處於安全狀態了？

接下來我們來看一下用代碼應該怎麽實現銀行家算法。

那麽除了這個算法的具體步驟之外，之前提到的不安全狀態，和死鎖還有安全狀態，它們之間的關係也經常容易在選擇題當中進行考查。那這個小節的内容十分重要，大家還需要再回歸課本并且結合課後習題進一步地鞏固。

在這個小節中我們會學習死鎖處理的最後一種策略——死鎖的檢測和解除。

那麽一般來説會用一個矩形來表示一類資源。那矩形當中的這一些小圓就是表示這一類資源有幾個。R2這種資源只有兩個，R1這種資源有三個。請求邊就是用來表示一個進程對某一種資源的請求，那每一條邊對應的就是一個資源，所以在這個情況來看，P1進程此時正在請求被分配一個R2資源，P2進程此時正在請求被分配一個R1資源。分配邊就是表示這種資源已經給各個進程分配了幾個，那同樣的每一條邊也對應一個資源。比如說現在這個系統當中已經給P1進程分配了兩個R1資源，給P2進程分配了一個R1資源。而R2資源只給P2分配了一個。那學習過數據結構的同學可以動手試一下要怎麽定義出這樣一個圖的數據結構。

P1進程它請求一個單位的R2資源，而R2資源現在只被分配出去了一個，它總數是兩個，所以R2資源現在剩餘空閑的還有一個，所以P1進程的這種請求是可以被滿足的。所以P1進程應該不會被阻塞，它可以順利地執行下去。但是P2進程此時請求一個單位的R1資源，而由於R1資源此時已經分配出去了1、2、33個，所以R1資源已經沒有空閑了。因此P2進程的這個請求不能被滿足。而P1進程既然可以順利地執行下去的話，那麽等P1進程順利地執行完了，它就可以把自己現在手裏的資源全部歸還給系統，并且等P1結束之後，它應該也不會再請求使用任何一種資源，所以假設現在P1順利地執行結束了，

那麽我們就可以把和P1相連的所有的這些邊全部幹掉。所以P2進程的這個請求接下來也可以被滿足，所以P2本來是阻塞的，那現在P2就可以被喚醒，然後正常地執行下去。等P2執行完了之後，它也會歸還所有的這些資源，并且不會再對任何一種資源提出請求。

那麽當P2歸還了這些系統資源之後，也有可能會有別的進程被喚醒。只不過在這個圖當中只有兩個進程。所以到這一步爲止，我們就可以認爲，這些進程實際上是可以順利地依次執行結束的。我們還可以從另外一個角度來考慮，其實剛才我們分析的這個過程相當於找到了一個安全序列，優先地把資源分配給P1，那麽P1可以執行結束。等P1執行結束之後，P2也可以執行結束。所以如果按P1->P2這樣的序列來依次執行的話，那麽所有的進程是都可以順利地執行結束的，這就和上小節介紹的安全序列其實是一種原理。

 我們再來看一個不能消除所有邊的情況。

大家可以結合這個圖來分析一下此時是否滿足死鎖發生的四個必要條件，四個必要條件分別又是什麽呢？

這就是死鎖檢測的一個思想。不阻塞的意思是說這個進程申請的這些資源的數量足夠滿足它的需求，比如説像P1進程就是不阻塞的進程。而P2進程申請的R1資源已經沒有足夠的剩餘資源可以分配給它了，所以P2進程是一個阻塞的進程。不是孤點這個條件指的是與這個進程至少有一個邊相連，那麽P1和P2顯然都不是孤點。所以在這個狀態下，滿足既不阻塞又不是孤點的進程就只有P1這個進程。接下來，我們可以消去P1進程所有的請求邊和分配邊，也就是把和P1相連的所有的邊都幹掉，使之成爲孤立的節點。

這就是著名的死鎖定理，感興趣的同學可以上網查一下文獻它是怎么證明的。

那現在我們已經邁出了第一步，我們已經可以有辦法檢測出此時系統是否發生了死鎖，接下來我們就要想辦法怎么解除這個死鎖。

并且搶占它現在持有的這些資源，把这些资源分配给所需要的进程。撤销进程法（终止进程法）这种方式简单粗暴，但是需要付出的代价可能会很大。所以撤销进程法的代价其实是很大的。进程回退法。比如說我們可以讓P1進程一直回退到它只持有一個R1資源的那個時候，那這樣的話就可以空出一個R1資源先分配給P2進程，至少先保證P2進程是可以順利地執行下去的。但是要實現這種所謂的進程回退，操作系統就需要記錄這些進程的執行歷史信息，設置還原點，所以進程回退法其實也不太容易實現。

那接下來我們再來考慮一下我們可以用什麽樣的方式來決定到底要讓哪個進程做出犧牲。比如剝奪它的資源，或者直接把它幹掉，或者讓它回退。可以從這樣一些角度來考慮，比如說進程優先級，那當然進程優先級低的我們可以對它下手。那執行時間越長，説明讓它回退或者是把它撤銷的話那我們付出的代價就會更大，畢竟之後還需要從頭再來嘛，所以我們可以選擇執行時間更少的進程讓它做出犧牲。那顯然我們可以優先讓馬上就可以執行結束的那些進程優先地獲得資源然後犧牲別的那些進程。那如果一個進程持有很多很多個資源的話，那把這個進程給撤銷或者把這個進程的資源給剝奪的話，那就意味著這個死鎖的局面就可以被儘快地解除，所以我們可以優先把擁有更多資源的進程先讓它做出犧牲。交互式的就意味著這些進程是和用戶交互的。如果把交互式的進程幹掉的話，那麽用戶肯定是極其不爽的，而對於批處理式的這些進程來説，它無非就是在做一些計算，用戶對於這種類型的進程的及時反饋其實並不是那麽在意，所以我們可以優先犧牲批處理式的進程。那麽這就是死鎖解除的一些策略。

考試當中比較容易常考的是死鎖檢測相關的部分。需要理解資源分配圖的這兩種節點和兩種邊分別是什麽意義。另外，更需要著重理解並記住死鎖檢測算法。其實我們可以用一種更精簡的語言把死鎖檢測算法把它概括出來。所以如果到後期時間充裕的話，也可以自己嘗試動手實現一下這個死鎖檢測算法，其實也并不複雜。那對於死鎖的解除，一般來説只會在選擇題裏進行考查，稍微有個印象就可以了。