操作系统：死锁问题
死鎖發(fā)生的四個(gè)必要條件
?
- 互斥：每個(gè)資源要么已經(jīng)分配給了一個(gè)進(jìn)程，要么就是可用的。
- 占有和等待：已經(jīng)得到了某個(gè)資源的進(jìn)程可以再請(qǐng)求新的資源。
- 不可搶占：已經(jīng)分配給一個(gè)進(jìn)程的資源不能強(qiáng)制性地被搶占，它只能被占有它的進(jìn)程顯式地釋放。
- 環(huán)路等待：有兩個(gè)或者兩個(gè)以上的進(jìn)程組成一條環(huán)路，該環(huán)路中的每個(gè)進(jìn)程都在等待下一個(gè)進(jìn)程所占有的資源。
處理方法
主要有以下四種方法：
-
鴕鳥策略
? ? 把頭埋在沙子里，假裝根本沒發(fā)生問題。
? ? 因?yàn)榻鉀Q死鎖問題的代價(jià)很高，因此鴕鳥策略這種不采取任務(wù)措施的方案會(huì)獲得更高的性能。
? ? 當(dāng)發(fā)生死鎖時(shí)不會(huì)對(duì)用戶造成多大影響，或發(fā)生死鎖的概率很低，可以采用鴕鳥策略。
? ? 大多數(shù)操作系統(tǒng)，包括 Unix，Linux 和 Windows，處理死鎖問題的辦法僅僅是忽略它。
-
死鎖檢測(cè)與死鎖恢復(fù)
? ? 不試圖阻止死鎖，而是當(dāng)檢測(cè)到死鎖發(fā)生時(shí)，采取措施進(jìn)行恢復(fù)。
1. 每種類型一個(gè)資源的死鎖檢測(cè)
（將進(jìn)程和資源視作節(jié)點(diǎn)，畫出資源分配有向圖，基于任意節(jié)點(diǎn)的DFS）
依次以每個(gè)節(jié)點(diǎn)為根節(jié)點(diǎn)進(jìn)行深度優(yōu)先搜索。
如何結(jié)束，即如何判斷有環(huán)（死鎖）？
當(dāng)鏈表中新加入的節(jié)點(diǎn)在之前已經(jīng)加入過，則說明有環(huán)，有死鎖。
維護(hù)一個(gè)鏈表，初始化為空表。以任意節(jié)點(diǎn)為起點(diǎn)出發(fā)，將當(dāng)前節(jié)點(diǎn)加入鏈表表頭，沿著當(dāng)前節(jié)點(diǎn)檢測(cè)是否存在從該節(jié)點(diǎn)出發(fā)的沒有被標(biāo)記的有向邊（一旦有向邊被訪問過，就會(huì)被標(biāo)記），有的話就沿著這條邊找到下一個(gè)節(jié)點(diǎn)，并作為當(dāng)前節(jié)點(diǎn)；如果沒有找到，再若此節(jié)點(diǎn)為根節(jié)點(diǎn)，則沒有環(huán)，算法結(jié)束，若此節(jié)點(diǎn)不是根節(jié)點(diǎn)，說明進(jìn)入了死胡同，因此回退到之前的節(jié)點(diǎn)，并將之前的節(jié)點(diǎn)作為新的起點(diǎn)；如此進(jìn)行。
以上圖為例：（從左到右DFS）
R到A，A到S，進(jìn)入死胡同；S倒退到A，A沒有沒有訪問過的有向邊，A倒退到R；
R到B，B到T，T到E，E到V，V到G，G到U，U到D，D到S，死胡同，S回退到D，D到T，T重復(fù)出現(xiàn)，有環(huán)有死鎖，結(jié)束。
?
2. 每種類型多個(gè)資源的死鎖檢測(cè)
? ? ? ? ? ? ? ? ? ? ? 基于資源矩陣的死鎖檢測(cè)算法
?
?
進(jìn)程起初都是沒有標(biāo)記的，算法開始會(huì)對(duì)進(jìn)程進(jìn)行標(biāo)記，進(jìn)程標(biāo)記后就表明他們能夠被執(zhí)行，不會(huì)進(jìn)入死鎖。當(dāng)算法結(jié)束的時(shí)候，沒有標(biāo)記的進(jìn)程都是死鎖進(jìn)程。
E是現(xiàn)有資源的總和，A是分配給各個(gè)進(jìn)程之后還剩下的可用資源；
C是各個(gè)進(jìn)程所占有的資源，R是各個(gè)進(jìn)程所要請(qǐng)求的資源；每一行代表一個(gè)進(jìn)程，每一列代表一個(gè)資源類型
算法：
1）尋找一個(gè)沒有標(biāo)記的進(jìn)程Pi，它的R矩陣中的第i行向量小于A（說明Pi請(qǐng)求的資源可以被滿足，Pi可以完美運(yùn)行）；
2）如果能找到Pi，那么將C矩陣的第i行向量加到A向量；（Pi成功運(yùn)行完，釋放所占有的資源，A資源向量就會(huì)回爐）；
3）如果沒有這樣的進(jìn)程，那么算法終止；、
?
以上面的圖為例子：
三個(gè)進(jìn)程、四種資源；按照C矩陣三行，從上到下依次稱為進(jìn)程1、進(jìn)程2、進(jìn)程3；
進(jìn)程1顯然不能運(yùn)行，因?yàn)锽lu-rays;
進(jìn)程2顯然也不能運(yùn)行，因?yàn)闆]有掃描儀；
進(jìn)程3可以完美運(yùn)行，運(yùn)行完成之后，釋放資源，此時(shí)A為[2,2,2,0],此時(shí)進(jìn)程2又可以運(yùn)行了，運(yùn)行完成進(jìn)程2釋放資源,此時(shí)A為[4，2，2，1]，進(jìn)程1又可以完美運(yùn)行了；因此三個(gè)進(jìn)程都被標(biāo)記，沒有死鎖進(jìn)程。
?
問題：何時(shí)進(jìn)行檢測(cè)？或者說檢測(cè)的周期怎么確定？
1）每當(dāng)有資源請(qǐng)求的時(shí)候去檢測(cè)，但是會(huì)占用CPU時(shí)間。
2）每隔K分鐘檢測(cè)一次?；蛘咴O(shè)定一個(gè)閾值，當(dāng)CPU的利用率降到了這個(gè)閾值就進(jìn)行死鎖檢測(cè)（因?yàn)?#xff0c;如所有死鎖進(jìn)程，且數(shù)量增多，那么在一定時(shí)間內(nèi)就沒有多少線程在運(yùn)行了，此時(shí)就會(huì)造成CPU空閑，利用率下降）
?
3. 死鎖恢復(fù)
- 利用搶占恢復(fù)
? ?將一個(gè)進(jìn)程所持有的資源臨時(shí)分配給另一個(gè)進(jìn)程，并將當(dāng)前被剝奪資源的進(jìn)程掛起，直到被分配資源的進(jìn)程執(zhí)行完成，歸還資源，被掛起進(jìn)程繼續(xù)執(zhí)行；
選擇掛起那個(gè)進(jìn)程（也就是剝奪那個(gè)進(jìn)程的資源），取決于那個(gè)進(jìn)程所占有的資源比較好回收
- 利用回滾恢復(fù)
類似于數(shù)據(jù)庫里的回滾操作。周期性地將進(jìn)程的當(dāng)前狀態(tài)寫入一個(gè)文件，新的檢查點(diǎn)不應(yīng)該覆蓋舊的檢查點(diǎn)。一旦出現(xiàn)死鎖，可按照文件中的檢查點(diǎn)（回滾點(diǎn)），將進(jìn)程回滾到某個(gè)時(shí)間點(diǎn)。
- 通過殺死進(jìn)程恢復(fù)
最簡(jiǎn)單也是最直接的方法就是，殺死一個(gè)或者若干個(gè)環(huán)內(nèi)進(jìn)程直到破壞死鎖環(huán)?；蛘邭⑺酪粋€(gè)環(huán)外的進(jìn)程，令其釋放資源，讓死鎖解開。但是選擇殺死那個(gè)進(jìn)程需要仔細(xì)斟酌。
?
死鎖預(yù)防(破壞死鎖的四個(gè)必要條件)
在程序運(yùn)行之前預(yù)防發(fā)生死鎖。
1. 破壞互斥條件
例如假脫機(jī)打印機(jī)技術(shù)允許若干個(gè)進(jìn)程同時(shí)輸出，唯一真正請(qǐng)求物理打印機(jī)的進(jìn)程是打印機(jī)守護(hù)進(jìn)程。
2. 破壞占有和等待條件
一種實(shí)現(xiàn)方式是規(guī)定所有進(jìn)程在開始執(zhí)行前請(qǐng)求所需要的全部資源。（缺點(diǎn)：進(jìn)程開始之前，并不能完全確定所有需要的資源）
3. 破壞不可搶占條件
4. 破壞環(huán)路等待
給資源統(tǒng)一編號(hào)，進(jìn)程只能按編號(hào)順序來請(qǐng)求資源。
?
死鎖避免
在程序運(yùn)行時(shí)避免發(fā)生死鎖。
如果進(jìn)程在請(qǐng)求資源的時(shí)候會(huì)導(dǎo)致系統(tǒng)進(jìn)入不安全狀態(tài)，則拒絕分配資源；如果不會(huì)，則分配。
1. 安全狀態(tài)和不安全狀態(tài)
?
圖 a 的第二列 Has 表示已擁有的資源數(shù)，第三列 Max 表示總共需要的資源數(shù)，Free 表示還有可以使用的資源數(shù)。從圖 a 開始出發(fā)，先讓 B 擁有所需的所有資源（圖 b），運(yùn)行結(jié)束后釋放 B，此時(shí) Free 變?yōu)?5（圖 c）；接著以同樣的方式運(yùn)行 C 和 A，使得所有進(jìn)程都能成功運(yùn)行，因此可以稱圖 a 所示的狀態(tài)時(shí)安全的。
定義：如果沒有死鎖發(fā)生，并且即使所有進(jìn)程突然請(qǐng)求對(duì)資源的最大需求，也仍然存在某種調(diào)度次序能夠使得每一個(gè)進(jìn)程運(yùn)行完畢，則稱該狀態(tài)是安全的。反之為不安全狀態(tài)。
安全狀態(tài)的檢測(cè)與死鎖的檢測(cè)類似，因?yàn)榘踩珷顟B(tài)必須要求不能發(fā)生死鎖。下面的銀行家算法與死鎖檢測(cè)算法非常類似，可以結(jié)合著做參考對(duì)比。
?
單個(gè)資源的銀行家算法（迪杰斯特拉提出的）
一個(gè)小城鎮(zhèn)的銀行家，他向一群客戶分別承諾了一定的貸款額度，算法要做的是判斷對(duì)請(qǐng)求的滿足是否會(huì)進(jìn)入不安全狀態(tài)，如果是，就拒絕請(qǐng)求；否則予以分配。
上圖 c 為不安全狀態(tài)，因此算法會(huì)拒絕之前的請(qǐng)求，從而避免進(jìn)入圖 c 中的狀態(tài)。
而 圖 b為安全狀態(tài)，可以CBAD。
多個(gè)資源的銀行家算法
上圖中有五個(gè)進(jìn)程，四個(gè)資源。左邊的圖表示已經(jīng)分配的資源，右邊的圖表示還需要分配的資源。最右邊的 E、P 以及 A 分別表示：總資源、已分配資源以及可用資源，注意這三個(gè)為向量，而不是具體數(shù)值，例如 A=(1020)，表示 4 個(gè)資源分別還剩下 1/0/2/0。
檢查一個(gè)狀態(tài)是否安全的算法如下：
- 查找右邊的矩陣是否存在一行小于等于向量 A。如果不存在這樣的行，那么系統(tǒng)將會(huì)發(fā)生死鎖，狀態(tài)是不安全的。
- 假若找到這樣一行，將該進(jìn)程標(biāo)記為終止，并將其已分配資源加到 A 中。
- 重復(fù)以上兩步，直到所有進(jìn)程都標(biāo)記為終止，則狀態(tài)時(shí)安全的。
可以任意次序分配資源，但是不一定任意次序都是安全的，也就是不一定所有的任意次序的請(qǐng)求都會(huì)被允許
如果一個(gè)狀態(tài)不是安全的，需要拒絕進(jìn)入這個(gè)狀態(tài)。
?
活鎖和饑餓
?
饑餓
線程饑餓是另一種活躍性問題，也可以使程序無法執(zhí)行下去。如果一個(gè)線程因?yàn)樘幚砥鲿r(shí)間全部被其他線程搶走而得不到處理器運(yùn)行時(shí)間，這種狀態(tài)被稱之為饑餓，一般是由高優(yōu)先級(jí)線程吞噬所有的低優(yōu)先級(jí)線程的處理器時(shí)間引起的。
java語言在Thread類中提供了修改線程優(yōu)先級(jí)的成員方法setPriority，并且定義了10個(gè)優(yōu)先級(jí)級(jí)別。不同操作系統(tǒng)有不同的線程優(yōu)先級(jí)，java會(huì)把這10個(gè)級(jí)別映射到具體的操作系統(tǒng)線程優(yōu)先級(jí)上邊。操作系統(tǒng)的線程調(diào)度會(huì)按照自己的調(diào)度策略來輪番執(zhí)行我們定義的線程。
我們所設(shè)置的線程優(yōu)先級(jí)對(duì)操作系統(tǒng)來說只是一種建議，當(dāng)我們嘗試提高一個(gè)線程的優(yōu)先級(jí)的時(shí)候，可能起不到任何作用，也可能使這個(gè)線程過度優(yōu)先執(zhí)行，導(dǎo)致別的線程得不到處理器分配的時(shí)間片，從而導(dǎo)致餓死。所以我們盡量不要修改線程的優(yōu)先級(jí)，具體效果取決于具體的操作系統(tǒng)，并且可能導(dǎo)致某些線程餓死。
舉個(gè)栗子：
我們還可以把處理器想象成皇帝，把各個(gè)線程想象成妃子，皇帝隔幾分鐘就換一個(gè)妃子陪他。我們?cè)O(shè)置線程優(yōu)先級(jí)就像是調(diào)整某個(gè)妃子的好看程度，具體皇帝挑不挑這個(gè)妃子還是具體的皇帝說了算，而且不同的皇帝有不同的口味，最后結(jié)果是啥還真說不準(zhǔn)。如果我們把一個(gè)妃子弄的很好看，一個(gè)皇帝太寵信她，從而使某些妃子得不到寵信，就是傳說中的`饑餓`現(xiàn)象。
?
活鎖
雖然不會(huì)像死鎖那樣因?yàn)楂@取不到資源而阻塞，也不會(huì)像饑餓那樣得不到處理器時(shí)間而無可奈何，活鎖仍舊可以讓程序無法執(zhí)行下去～
比如在一間教室里，狗哥要出去，貓爺要進(jìn)來，門只能容得下一個(gè)人進(jìn)出，而它們?cè)陂T口相遇了，所以狗哥往后退了一步意思是貓爺先進(jìn)，而貓爺也退了一步意思是狗哥先進(jìn)；之后狗哥往前走了一步，貓爺也往前走了一步，倆人又都堵在了門口，所以又都同時(shí)退一步，然后再同時(shí)進(jìn)一步，同時(shí)退一步，同時(shí)進(jìn)一步…..
把狗哥和貓爺都比做一個(gè)線程的話，這兩個(gè)線程雖然都沒有停止運(yùn)行，但是卻無法向下執(zhí)行，這種情況就是所謂的活鎖。
為了解決這個(gè)問題，需要在遇到?jīng)_突重試時(shí)引入一定的隨機(jī)性。比如狗哥和貓爺在門口相遇都后退時(shí)，狗哥隔一秒后再前進(jìn)，貓爺隔兩秒后再前進(jìn)，這樣就不會(huì)有同時(shí)走到門口的尷尬了～
?
總結(jié)：
死鎖主要的點(diǎn)在于：
1）死鎖是什么？
如果一個(gè)進(jìn)程集合中的每一個(gè)進(jìn)程都在等待只能由該集合進(jìn)程中的其它的進(jìn)程才能引發(fā)的事件，那么該進(jìn)程集合就是死鎖的。
2）死鎖的四個(gè)必要條件
3）死鎖發(fā)生之后如何檢測(cè)？如何恢復(fù)？
DFS、基于資源矩陣? ?|||||? ?搶占恢復(fù)、回滾恢復(fù)、殺死進(jìn)程、
4）死鎖在程序運(yùn)行之前如何預(yù)防？
破壞四個(gè)必要條件
5）死鎖在程序運(yùn)行時(shí)如何避免？
單個(gè)資源的銀行家算法? ?多個(gè)資源的銀行家算法
6）活鎖和饑餓？
?
?
?
總結(jié)
- 上一篇： 操作系统：哲学家进餐问题
- 下一篇： Stack:peek、pop、push、