上一篇計算機(jī)系統(tǒng)010 - 操作系統(tǒng)之并行中講述了并行中的多進(jìn)程/線程對同一資源的競爭會引發(fā)沖突，導(dǎo)致程序執(zhí)行結(jié)果不可預(yù)測。通過使用信號量蕴坪、管程、消息傳遞等機(jī)制敬锐，可實(shí)現(xiàn)進(jìn)程間的同步和通信背传，達(dá)成互斥基礎(chǔ)上的合作。但事實(shí)上台夺，進(jìn)程運(yùn)行過程中可能同時會同時使用多個資源径玖，假如兩個進(jìn)程在占用對方所需資源的同時，去獲取對方占有資源颤介，就會形成死鎖梳星。

為便于書寫，后續(xù)多進(jìn)程/線程統(tǒng)一視為多線程滚朵，畢竟進(jìn)程本身至少也是以一個主線程的形式執(zhí)行的冤灾。

1. 死鎖 Deadlock

從前面簡短的描述來看，死鎖現(xiàn)象中至少需要如下參與者：

• 兩個進(jìn)程/線程
• 兩個資源

1.1 死鎖的條件

死鎖有三個必要條件：

• 互斥届榄，即每個資源只能供一個線程使用
• 占有且等待，即已占有資源的線程不會釋放資源
• 不可搶占倔喂，即不可搶占已被其他線程占有資源

這三個條件都只是死鎖存在的必要條件铝条，但不是充分條件。死鎖的真正產(chǎn)生還需要第四個條件：

• 循環(huán)等待滴劲，即存在一個封閉的資源環(huán)路攻晒，互不釋放、互相追求

光從理論上來講難免過于空洞班挖，既然說到了死鎖鲁捏，那就不得不說起一個經(jīng)典問題：哲學(xué)家就餐。

1.2 哲學(xué)家就餐問題

有五位哲學(xué)家住在一棟房子里萧芙，在他們面前有一張餐桌给梅，每位哲學(xué)家的生活就是思考和吃飯。通過多年的思考双揪，所有的哲學(xué)家一致同意最有助于他們思考的食物是意大利面條动羽。但由于動手能力有限，每位哲學(xué)家需要兩把叉子來吃面條渔期。

現(xiàn)在的問題是需要設(shè)計一套禮儀（算法）以允許哲學(xué)家就餐运吓，算法必須保證互斥（沒有兩位哲學(xué)家同時使用同一把叉子），同時還要避免死鎖和饑餓疯趟。所謂饑餓拘哨，就是指長時間得不到資源的使用權(quán)而無法完成任務(wù)，只能阻塞住白白浪費(fèi)生命信峻。

對此倦青，通常有如下幾種解法：

• 服務(wù)生解法
  引入第三者服務(wù)生，決策每個哲學(xué)家具體就餐時機(jī)盹舞。實(shí)際上产镐，相當(dāng)于通過全局管理者獲取資源，而不允許線程本身直接去獲取資源踢步。

• 資源分級解法
  為資源（叉子）分配一個偏序或者分級的關(guān)系癣亚，并約定所有資源都按照這種順序獲取，按相反順序釋放获印，且保證不會有兩個無關(guān)資源同時被后一項工作所需要逃糟。描述起來挺復(fù)雜，說到底蓬豁，就是給資源排優(yōu)先級绰咽，要想擁有兩個資源，首先要擁有高優(yōu)先級資源地粪，然后才能去獲取低優(yōu)先級資源取募。這樣一來，多個資源之間的戰(zhàn)爭就轉(zhuǎn)移到了單獨(dú)的高優(yōu)先級資源戰(zhàn)爭蟆技，避免了只拿到低優(yōu)先級的線程魚死網(wǎng)破玩敏。

上述的是通用的解法，雖然解法能解決問題质礼，但授人以魚不如授人以漁旺聚，解法中遵循的原理還需要進(jìn)一步說明。

2. 死鎖解決方法

2.1 預(yù)防

死鎖預(yù)防眶蕉，就是排除發(fā)生死鎖的可能性砰粹，即破壞4個條件之一來避免死鎖的產(chǎn)生。預(yù)防方法可以進(jìn)一步分為兩種：

• 間接預(yù)防：防止三個必要條件之一形成

  • 互斥
    實(shí)際操作系統(tǒng)中造挽，第一個條件通常不能禁止碱璃，畢竟互斥本身提供了對資源的保護(hù)。但某些情況下饭入，如對于文件的讀寫訪問中嵌器，只需要對寫操作進(jìn)行互斥即可，而讀操作不影響數(shù)據(jù)本身可以不要求互斥谐丢。

  • 占有且等待
    為預(yù)防占有且等待的條件爽航，可以要求線程一次性請求所有需要的資源，并阻塞線程直到所有請求同時得到滿足乾忱。也就是說讥珍，如果申請時不能同時獲取到所有必需資源，那么就必須等到可以全部獲取了在執(zhí)行饭耳，避免了既不能執(zhí)行還占有著資源的情況發(fā)生串述。
    不過這樣也就使得線程整體執(zhí)行時間被拉長，且不可預(yù)測寞肖。

  • 不可搶占
    有幾種方法可以預(yù)防這個條件：

    • 占有某些資源的線程進(jìn)一步申請資源被拒絕時纲酗，必須釋放所占有資源匿值，如有必要推正，可再次申請這些資源和其他資源
    • 如一個線程請求被占有的資源，則有操作系統(tǒng)負(fù)責(zé)從另一線程處搶占資源捉邢。而是否搶占的標(biāo)準(zhǔn)需參考優(yōu)先級信息

• 直接預(yù)防：防止充分條件形成
  循環(huán)等待條件可通過定義資源類型的線性順序來預(yù)防琼稻，如果一個線程已獲取到R類型資源吮螺，則之后只能請求排在R類型之后的資源。

從上面我們可以看到，死鎖預(yù)防主要是從資源使用權(quán)本身著手鸠补，破壞四個條件之一來防止死鎖的形成萝风，但由于引入了資源等待，拉長了任務(wù)所需執(zhí)行時長紫岩，造成低效后果规惰。

2.2 避免

為了避免因?yàn)轭A(yù)防死鎖而導(dǎo)致所有線程變慢，死鎖避免采用了與死鎖預(yù)防相反的措施泉蝌。它允許三個必要條件歇万，但通過算法判斷資源請求是否可能導(dǎo)致循環(huán)等待的形成并相應(yīng)決策，來避免死鎖點(diǎn)的產(chǎn)生勋陪。因此贪磺，其前提是知道當(dāng)前資源使用的整體情況，以及申請資源線程本身所占有的資源細(xì)節(jié)诅愚。

判斷和決策中寒锚，主要使用兩種避免方法。

• 線程啟動拒絕
  如果一個線程的請求會引發(fā)死鎖呻粹，則不允許其啟動壕曼。
• 資源分配拒絕
  如果一個線程增加的資源請求會導(dǎo)致死鎖，則不允許此申請等浊。

整體來看腮郊，死鎖避免是從資源和線程相互間關(guān)系著手，避免形成循環(huán)等待是其主要任務(wù)筹燕。

2.3 檢測

相比前面兩種方法的保守轧飞，死鎖檢測就要自信而奔放得多。死鎖檢測中撒踪，盡可能將被請求的資源分配給線程过咬，操作系統(tǒng)會周期性執(zhí)行算法檢測是否有循環(huán)等待的產(chǎn)生。換句話說制妄，就是放手去干掸绞，操作系統(tǒng)罩著你們。

當(dāng)然耕捞，檢查算法執(zhí)行的頻率影響著死鎖被檢測出的靈敏度衔掸，操作系統(tǒng)可以在每次資源請求是檢測，也可以適當(dāng)降低頻率俺抽，減少消耗的CPU時間敞映。檢測到死鎖后，就需要解決死鎖磷斧。目前操作系統(tǒng)中主要采用如下幾種方法：

• 取消所有死鎖相關(guān)線程振愿，簡單粗暴捷犹，但也確實(shí)是最常用的
• 把每個死鎖線程回滾到某些檢查點(diǎn)，然后重啟
• 連續(xù)取消死鎖線程直到死鎖解除冕末，順序基于特定最小代價原則
• 連續(xù)搶占資源直到死鎖解除

2.4 綜合選擇

既然三種方法各有優(yōu)劣萍歉，那就不如海納百川，取其精華去其糟粕栓霜。

• 將資源分成幾組不同的資源類
• 為預(yù)防在資源類之間由于循環(huán)等待產(chǎn)生了死鎖翠桦，可使用線性排序策略
• 在一個資源類中，使用該類資源最適合的算法

翻譯一下胳蛮，就是說先根據(jù)資源特性分類（至于為什么要分類，前面也提過丛晌，分類是為了更細(xì)粒度的控制）仅炊，類和類之間可以通過排優(yōu)先級來約束，而類本身內(nèi)部澎蛛，再通過合適算法來選擇抚垄。

說起資源，順便多提一下谋逻。操作系統(tǒng)中資源通常分為如下兩種：

• 可重用資源
  一次只能供一個線程使用呆馁，并且不會由于使用而耗盡。主要是硬件設(shè)備和一些數(shù)據(jù)結(jié)構(gòu)毁兆，如CPU浙滤、I/O通道、內(nèi)存和外存气堕、設(shè)備纺腊、文件、數(shù)據(jù)庫茎芭、信號量等揖膜。

• 可消耗資源
  指可被創(chuàng)建和銷毀的資源，數(shù)目沒有限制梅桩，但用完后通常就不復(fù)存在壹粟。主要為一些動態(tài)產(chǎn)生的數(shù)據(jù)，如中斷宿百、信號趁仙、消息、I/O緩沖區(qū)中信息等犀呼。

3. 總結(jié)

本篇主要介紹了死鎖的形成條件幸撕、相應(yīng)的解決方法及各解決方法優(yōu)劣之處，相比其他篇內(nèi)容外臂，本篇略顯單薄了一些坐儿，不過還是希望對于一些概念的理解能夠引發(fā)共鳴，留下印象。最近兩篇中講述的是操作系統(tǒng)并行貌矿、死鎖兩個調(diào)度相關(guān)的問題炭菌，接下來就要從內(nèi)存管理部分對進(jìn)程調(diào)度做進(jìn)一步展開。