王道操作系統(tǒng)第2章-進(jìn)程管理-死鎖
第2章-進(jìn)程管理-死鎖
死鎖的概念
死鎖、饑餓、死循環(huán)的區(qū)別
死鎖產(chǎn)生的必要條件
什么時(shí)候會(huì)發(fā)生死鎖
死鎖的處理策略
死鎖的處理策略——預(yù)防死鎖
破壞互斥條件
破壞不剝奪條件
破壞請(qǐng)求和保持條件
破壞循環(huán)等待條件
死鎖的處理策略——避免死鎖
什么是安全序列
銀行家算法
死鎖的處理策略——檢測(cè)和解除
死鎖的檢測(cè)
死鎖的解除
死鎖的概念
在并發(fā)環(huán)境下，各進(jìn)程因競(jìng)爭(zhēng)資源而造成的一種互相等待對(duì)方手里的資源，導(dǎo)致各進(jìn)程都阻塞，都無(wú)法向前推進(jìn)的現(xiàn)象，就是“死鎖”。發(fā)生死鎖后若無(wú)外力干涉，這些進(jìn)程都無(wú)法向前推進(jìn)
死鎖、饑餓、死循環(huán)的區(qū)別
死鎖：各進(jìn)程互相等待對(duì)方手里的資源，導(dǎo)致各進(jìn)程都阻塞，無(wú)法向前推進(jìn)的現(xiàn)象發(fā)生死鎖的進(jìn)程一定處于阻塞態(tài)。
饑餓：由于長(zhǎng)期得不到想要的資源，某進(jìn)程無(wú)法向前推進(jìn)的現(xiàn)象。比如在短進(jìn)程優(yōu)先（SPF）算法中，若有源源不斷的短進(jìn)程到來(lái)，則長(zhǎng)進(jìn)程將一直得不到處理機(jī)，從而發(fā)生長(zhǎng)進(jìn)程“饑餓”。發(fā)生饑餓的進(jìn)程既可能是阻塞態(tài)（如長(zhǎng)期得不到需要的IO設(shè)備），也可能是就緒態(tài)（長(zhǎng)期得不到處理機(jī)）
死循環(huán)：某進(jìn)程執(zhí)行過程中一直跳不出來(lái)某個(gè)循環(huán)的現(xiàn)象。有時(shí)是因?yàn)槌绦騜ug導(dǎo)致的，有時(shí)是程序員故意設(shè)計(jì)的
死鎖產(chǎn)生的必要條件
產(chǎn)生死鎖必須同時(shí)滿足以下四個(gè)條件，只要其中任一條件不成立，死鎖就不會(huì)發(fā)生
互斥條件：只有對(duì)必須互斥使用的資源的爭(zhēng)搶才會(huì)導(dǎo)致死鎖（如哲學(xué)家的筷子、打印機(jī)設(shè)備）。像內(nèi)存、揚(yáng)聲器這樣可以同時(shí)讓多個(gè)進(jìn)程使用的資源是不會(huì)導(dǎo)致死鎖的（因?yàn)檫M(jìn)程不用阻塞等待這種資源）
不剝奪條件：進(jìn)程所獲得的資源在未使用完之前，不能由其他進(jìn)程強(qiáng)行奪走，只能主動(dòng)釋放
請(qǐng)求和保持條件：進(jìn)程已經(jīng)保持了至少一個(gè)資源，但又提出了新的資源請(qǐng)求，而該資源又被其他進(jìn)程占有，此時(shí)請(qǐng)求進(jìn)程被阻塞，但又對(duì)自己已有的資源保持不放
循環(huán)等待條件：存在一種進(jìn)程資源的循環(huán)等待鏈，鏈中的每一個(gè)進(jìn)程已獲得的資源同時(shí)被下一個(gè)進(jìn)程所請(qǐng)求
注意：發(fā)生死鎖時(shí)一定有循環(huán)等待，但是發(fā)生循環(huán)等待時(shí)未必死鎖（循環(huán)等待是死鎖的必要不充分條件）。
如果同類資源數(shù)>1，則即使有循環(huán)等待，也未必發(fā)生死鎖。但如果系統(tǒng)中每類資源都只有一個(gè)，那循環(huán)等待就是死鎖的充分必要條件了。
什么時(shí)候會(huì)發(fā)生死鎖
對(duì)系統(tǒng)資源的競(jìng)爭(zhēng)。各進(jìn)程對(duì)不可剝奪的資源（如打印機(jī)）的競(jìng)爭(zhēng)可能引起死鎖，對(duì)可剝奪的資源（CPU）的競(jìng)爭(zhēng)是不會(huì)引起死鎖的。
進(jìn)程推進(jìn)順序非法。請(qǐng)求和釋放資源的順序不當(dāng)，也同樣會(huì)導(dǎo)致死鎖。例如，并發(fā)執(zhí)行的進(jìn)程P1、P2分別申請(qǐng)并占有了資源R1、R2，之后進(jìn)程P1有緊接著申請(qǐng)資源R2，而進(jìn)程P2又申請(qǐng)資源R1，兩者會(huì)因?yàn)樯暾?qǐng)的資源被對(duì)方占有而阻塞，從而發(fā)生死鎖。
信號(hào)量的使用不當(dāng)也會(huì)造成死鎖。如生產(chǎn)者消費(fèi)者問題中，如果實(shí)現(xiàn)互斥的P操作在實(shí)現(xiàn)同步的P操作之前，就有可能導(dǎo)致死鎖。（可以把互斥信號(hào)量、同步信號(hào)量看做是一種抽象的系統(tǒng)資源）
總之，對(duì)不可剝奪資源的不合理分配，可能導(dǎo)致死鎖
死鎖的處理策略
預(yù)防死鎖。破壞死鎖產(chǎn)生的四個(gè)必要條件中的一個(gè)或幾個(gè)
避免死鎖。用某種方式防止系統(tǒng)進(jìn)入不安全狀態(tài)，從而避免死鎖（銀行家算法）
死鎖的檢查和解除。允許死鎖的發(fā)生，不過操作系統(tǒng)會(huì)負(fù)責(zé)檢測(cè)出死鎖的發(fā)生，然后采取某種措施解除死鎖
死鎖的處理策略——預(yù)防死鎖
破壞互斥條件
互斥條件：只有對(duì)必須互斥使用的資源的爭(zhēng)搶才會(huì)導(dǎo)致死鎖
如果把只能互斥使用的資源改為允許共享使用，則系統(tǒng)不會(huì)進(jìn)入死鎖狀態(tài)，比如SPOOLing技術(shù)。
操作系統(tǒng)可以采用SPOOLing技術(shù)把獨(dú)占設(shè)備在邏輯上改造成共享設(shè)備。比如用SPOOLing技術(shù)將打印機(jī)改造成共享設(shè)備
缺點(diǎn)：并不是所有的資源都可以改造成可共享使用的資源。并且為了系統(tǒng)安全，很多地方還必須保護(hù)這種互斥性。因此很多時(shí)候都無(wú)法破壞互斥條件。
破壞不剝奪條件
不剝奪條件：進(jìn)程所獲得的資源在未使用完之前，不能由其他進(jìn)程強(qiáng)行奪走，只能主動(dòng)釋放
破壞不剝奪條件：
方案1：當(dāng)某個(gè)進(jìn)程請(qǐng)求新的資源得不到滿足時(shí)，它必須立即釋放保持的所有資源，待以后需要時(shí)再重新申請(qǐng)。也就是說，即使某些資源尚未使用完，也需要主動(dòng)釋放，從而破壞了不可剝奪條件
方案2：當(dāng)某個(gè)進(jìn)程需要的資源被其他進(jìn)程所占有的時(shí)候，可以由操作系統(tǒng)協(xié)助，將想要的資源強(qiáng)行剝奪，這種方式一般需要考慮各進(jìn)程的優(yōu)先級(jí)（比如：剝奪調(diào)度方式，就是將處理機(jī)資源強(qiáng)行剝奪給優(yōu)先級(jí)更高的進(jìn)程使用）
這兩種策略的缺點(diǎn)：
實(shí)現(xiàn)起來(lái)比較復(fù)雜
釋放已獲得的資源可能造成前一階段工作的失效。因此這種方法一般只適用于易保存和恢復(fù)狀態(tài)的資源，如CPU
反復(fù)地申請(qǐng)和釋放資源會(huì)增加系統(tǒng)開銷，降低系統(tǒng)吞吐量
若采用方案一，意味著只要暫時(shí)得不到某個(gè)資源，之前獲得的那些資源就都需要放棄，以后再重新申請(qǐng)。如果一直發(fā)生這樣的情況，就會(huì)導(dǎo)致進(jìn)程饑餓
破壞請(qǐng)求和保持條件
請(qǐng)求和保持條件：進(jìn)程已經(jīng)保持了至少一個(gè)資源，但又提出了新的資源請(qǐng)求，而該資源又被其他進(jìn)程占有，此時(shí)請(qǐng)求進(jìn)程被阻塞，但又對(duì)自己已有的資源保持不放
破壞請(qǐng)求和保持條件：
采用靜態(tài)分配法，即進(jìn)程在運(yùn)行前一次申請(qǐng)完它所需要的全部資源，在它的資源未滿足前，不讓它投入運(yùn)行。一旦投入運(yùn)行后，這些資源就一直歸它所有，該進(jìn)程就不會(huì)再請(qǐng)求別的任何資源了
這種策略的缺點(diǎn)：
有些資源可能只需要用很短的時(shí)間，因此如果進(jìn)程的整個(gè)運(yùn)行期間都一直保持著所有資源，就會(huì)造成嚴(yán)重的資源浪費(fèi)，資源利用率極低。另外，該策略也有可能導(dǎo)致某些進(jìn)程饑餓
破壞循環(huán)等待條件
循環(huán)等待條件：存在一種進(jìn)程資源的循環(huán)等待鏈，鏈中的每一個(gè)進(jìn)程已獲得的資源同時(shí)被下一個(gè)進(jìn)程所請(qǐng)求
破壞循環(huán)等待條件：
采用順序資源分配法。首先給系統(tǒng)中的資源編號(hào)，規(guī)定每個(gè)進(jìn)程必須按編號(hào)遞增的順序請(qǐng)求資源，同類資源（即編號(hào)相同的資源）一次申請(qǐng)完原理分析：一個(gè)進(jìn)程只有已占有小編號(hào)的資源時(shí)，才有資格申請(qǐng)更大編號(hào)的資源。按此規(guī)則，已持有大編號(hào)資源的進(jìn)程不可能逆向地回來(lái)申請(qǐng)小編號(hào)的資源，從而就不會(huì)產(chǎn)生循環(huán)等待的現(xiàn)象。也就是說，在任何一個(gè)時(shí)刻，總有一個(gè)進(jìn)程擁有的資源編號(hào)是最大的，那么這個(gè)進(jìn)程申請(qǐng)之后的資源必然暢通無(wú)阻，因此不可能出現(xiàn)所有進(jìn)程都阻塞的死鎖現(xiàn)象
這種策略的缺點(diǎn)：
不方便增加新的設(shè)備，因?yàn)榭赡苄枰匦路峙渌械木幪?hào)
進(jìn)程實(shí)際使用資源的順序可能和編號(hào)遞增順序不一致，會(huì)導(dǎo)致資源的浪費(fèi)
必須按規(guī)定次序申請(qǐng)資源，用戶編程麻煩
死鎖的處理策略——避免死鎖
什么是安全序列
所謂的安全序列，就是指如果系統(tǒng)按這種序列分配資源，則每個(gè)進(jìn)程都能順利完成。只要能找出一個(gè)安全序列，系統(tǒng)就是安全狀態(tài)。當(dāng)然安全序列可能有多個(gè)。
如果分配了資源之后，系統(tǒng)中找不出任何一個(gè)安全序列，系統(tǒng)就進(jìn)入了不安全狀態(tài)。這意味著之后可能所有進(jìn)程都無(wú)法順利地執(zhí)行下去。當(dāng)然如果有進(jìn)程提前歸還了一些資源，那系統(tǒng)也有可能重新回到安全狀態(tài)，不過我們?cè)诜峙滟Y源前總要考慮到最壞的情況。
如果系統(tǒng)處于安全狀態(tài)，就一定不會(huì)發(fā)生死鎖。如果系統(tǒng)進(jìn)入不安全狀態(tài)，就可能發(fā)生死鎖。（處于不安全狀態(tài)未必就是發(fā)生了死鎖，但發(fā)生死鎖時(shí)一定是在不安全狀態(tài)）
可以在資源分配之前預(yù)先判斷此次分配是否會(huì)導(dǎo)致系統(tǒng)進(jìn)入不安全狀態(tài)，以此決定是否答應(yīng)資源分配請(qǐng)求。這也是銀行家算法的核心思想
銀行家算法
在BAT例子中，只有一種類型的資源：錢。但是在計(jì)算機(jī)系統(tǒng)中有多種多樣的資源，應(yīng)該怎么把算法拓展為多種資源的情況呢？可以把單位的數(shù)字拓展為多維的向量。比如：系統(tǒng)中有5個(gè)進(jìn)程P0~P4,3種資源R0~R2，初始數(shù)量為（10,5,7），則某一時(shí)刻的情況可表示如下
具體計(jì)算方法參考王道考研課P40的10分鐘位置
死鎖的處理策略——檢測(cè)和解除
如果系統(tǒng)中既不采取預(yù)防死鎖的措施，也不采取避免死鎖的措施，系統(tǒng)就很可能發(fā)生死鎖。這種情況下，系統(tǒng)應(yīng)當(dāng)提供兩個(gè)算法：
死鎖檢測(cè)算法：用于檢測(cè)系統(tǒng)狀態(tài)，以確定系統(tǒng)中是否發(fā)生了死鎖
死鎖解除算法：當(dāng)認(rèn)定系統(tǒng)中以及發(fā)生了死鎖，利用該算法可以將系統(tǒng)從死鎖狀態(tài)中解脫出來(lái)
死鎖的檢測(cè)
為了能對(duì)系統(tǒng)是否已經(jīng)發(fā)生了死鎖進(jìn)行檢測(cè)
用某種數(shù)據(jù)結(jié)構(gòu)來(lái)保存資源的請(qǐng)求和分配信息
提供一種算法，利用上述信息來(lái)檢測(cè)系統(tǒng)是否已進(jìn)入死鎖狀態(tài)
如果系統(tǒng)中剩余的可用資源數(shù)足夠滿足進(jìn)程的需求，那么這個(gè)進(jìn)程暫時(shí)是不會(huì)被阻塞的，可以順利地執(zhí)行下去。如果這個(gè)進(jìn)程執(zhí)行結(jié)束了把資源歸還給系統(tǒng)，就可能使某些正在等待資源的進(jìn)程被激活，并順利地執(zhí)行下去。相應(yīng)地，這些被激活的進(jìn)程執(zhí)行完了之后又會(huì)歸還一些資源，這樣可能又會(huì)激活另外一些阻塞的進(jìn)程。如果按照上述過程分析，最終能消除所有邊，就稱這個(gè)圖是可完全簡(jiǎn)化的，此時(shí)一定沒有發(fā)生死鎖（相當(dāng)于能找到一個(gè)安全序列）
沒有發(fā)生死鎖的變化圖：
如果最終不能消除所有邊，那么此時(shí)就是發(fā)生了死鎖。最終還連著變的那些進(jìn)程就是處于死鎖狀態(tài)的進(jìn)程
發(fā)生了死鎖的變化圖
死鎖的解除
資源剝奪法：掛起（暫時(shí)放到外存上）某些死鎖進(jìn)程，并搶占它的資源，將這些資源分配給其他的死鎖進(jìn)程。但是應(yīng)放置被掛起的進(jìn)程長(zhǎng)時(shí)間得不到資源而饑餓
撤銷進(jìn)程法（或稱終止進(jìn)程法）：強(qiáng)制撤銷部分、甚至全部死鎖進(jìn)程，并剝奪這些進(jìn)程的資源。這種方式的優(yōu)點(diǎn)是時(shí)間簡(jiǎn)單，但是所付出的代價(jià)可能會(huì)很大，因?yàn)橛行┻M(jìn)程可能已經(jīng)運(yùn)行了很長(zhǎng)時(shí)間了，已經(jīng)接近結(jié)束了，一旦被終止可能功虧一簣
進(jìn)程回退法：讓一個(gè)或多個(gè)死鎖進(jìn)程回退到足以避免死鎖的地步，這就要求系統(tǒng)要記錄進(jìn)程的歷史信息，設(shè)置還原點(diǎn)
如何決定“對(duì)誰(shuí)動(dòng)手”
進(jìn)程優(yōu)先級(jí)
已執(zhí)行多長(zhǎng)時(shí)間
還要多久能完成
進(jìn)程已經(jīng)使用了多少資源
