計算機操作系統——死鎖（詳細解釋和處理死鎖）

系列文章目錄

計算機操作系統-計算機系統中的死鎖

文章目錄

系列文章目錄
前言
一、資源問題：
- 計算機系統當中的死鎖：
二、死鎖的定義、必要條件和處理方法：
- 1.死鎖的定義：
- 2.產生死鎖的必要條件：
- 3.處理死鎖的方法：
三、避免死鎖：
- 1.系統安全狀態的定義：
- 2.安全狀態的例子：
- 3.不安全狀態的例子：
- 4.利用銀行家算法避免死鎖：
- 5.具體示例：
總結

前言

? ?在第二章中，我們已經涉及到死鎖的概念，例如系統中只有一個掃描儀R1和一臺刻錄機R2，有兩個進程p1和p2，他們都準備將掃描的文檔刻錄在CD光盤上，進程1先請求掃描儀R1并獲得成功，進程2先請求刻錄機R2也獲得成功，后來P1又請求CD刻錄機，因它已被分配給了P2而阻塞，P2又請求掃描儀，也因被分配給了進程1而阻塞，此時兩個進程都被阻塞，雙方都希望對方能釋放出自己所需要的資源，但他們誰都因不能獲得自己所需的資源去繼續運行，從而無法釋放出自己占有的資源，并且一直處于這樣的僵持狀態而形成死鎖，又如，在第二章的哲學家進餐問題中，如果每個哲學家因饑餓都拿起了他們左邊的筷子，當每一個哲學家又試圖去拿起他們右邊的筷子時，將會因為無筷子可拿而無限期地等待，從而產生死鎖問題。接下來我們將對死鎖發生的原因，如何預防和避免死鎖等問題作較詳細的介紹。

一、資源問題：

? 在系統中有許多不同類型的資源，其中可以引起死鎖的主要是，需要采用互斥訪問方法的、不可以被搶占的資源，即前面介紹的臨界資源。系統中這類資源有很多，如打印機，數據文件，隊列，信號量等。

可搶占性資源和不可搶占性資源

（1）可搶占性資源（可剝奪）

? 可把系統中的資源分成兩類，一類是可搶占性資源，是指某進程在獲得這類資源后，該資源可以再被其他進程或系統搶占。例如優先級高的進程可以搶占優先級低的進程的處理機。又如可把一個進程從一個存儲區轉移到另一個存儲區，在內存緊張時，還可將一個進程從內存調出到外存上，即搶占該進程在內存空間，可見，CPU和主存均屬于可搶占性資源。對于這類資源是不會引起死鎖了。

（2）不可搶占性資源（非剝奪）

? ? ? 另一類資源是不可搶占性資源，即一旦系統把某資源分配給該進程，就不能將它強行收回，只能在進程用完后自行釋放。例如，當一個進程已開始刻錄光盤時，如果突然將刻錄機分配給另一個進程，其結果必然會損壞正在刻錄的光盤，因此只能等刻好光盤后由進程自己釋放刻錄機。另外磁帶機，打印機等也都屬于不可搶占性資源。

? 計算機系統中的死鎖：

? ?1.競爭不可搶占性資源引起死鎖

? ? 2.競爭可消耗資源引起死鎖

? ? 3.進程推進順序不當引起死鎖

二、死鎖的定義、必要條件和處理方法：

? ??

1.死鎖的定義：

死鎖指兩個或多個進程在執行過程中，因爭奪資源而陷入相互等待的僵局，若無外力干預，這些進程將無法向前推進。此時，系統處于停滯狀態，資源被無效占用。

2.產生死鎖的必要條件：

? ? 雖然進程在運行過程中可能會發生死鎖，但產生進程死鎖是必須具備一定條件的，綜上所述不難看出，產生死鎖必須同時具備下面四個必要條件，只要其中任一個條件不成立，死鎖就不會發生。

（1）互斥條件：進程對所分配到的資源進行排他性使用，即在一段時間內，某資源只能被一個進程占用。如果此時還有其他進程請求該資源，則請求進程只能等待，直至占用該資源的進程用畢釋放。

（2）請求和保持條件：進程已經保持了至少一個資源，但又提出了新的資源請求，而該資源已被其他進程占有，此時請求進程被阻塞，但對自己已獲得的資源保持不放。

?（3）不可搶占條件：進程已獲得的資源在未使用之前不能被搶占，只能在進程使用完時由自己釋放。

?（4）循環等待條件：在發生死鎖時，必然存在一個進程——資源的循環鏈，即進程集合（p0,p1,p2....pn）中的p0正在等待一個p1占用的資源，p1正在等待p2占用的資源，.....，pn正在等待已被p0占用的資源。

3.處理死鎖的方法：

? （1）預防死鎖

? （2）避免死鎖

? ?（3）檢測死鎖

? ?（4）解除死鎖

上述的四種方法，從(1)到(4)對死鎖的防范程度逐漸減弱，但對應的是資源利用率的提高，以及進程因資源因素而阻塞的頻度下降。

? ?三、避免死鎖：

? ? 在死鎖避免方法中，把系統的狀態分為安全狀態和不安全狀態。當系統處于安全狀態時，可避免發生死鎖。反之，當系統處于不安全狀態時，則可能進入死鎖狀態。

? ? ?

系統安全狀態的定義??

??安全狀態（Safe State）??：
系統存在至少一個??安全序列（Safe Sequence）??，使得所有進程都能按此順序依次獲得所需資源并完成執行，而不會導致死鎖。

??安全序列??：假設進程按順序?P1?,P2?,…,Pn??執行，每個進程?Pi??的資源請求都可以被當前可用資源滿足，且執行完成后會釋放所有資源，從而為后續進程提供更多可用資源。

??不安全狀態（Unsafe State）??：
不存在這樣的安全序列。此時系統可能進入死鎖，但??不安全狀態不一定會導致死鎖??（取決于后續資源請求的實際情況）。

? ?雖然并非所有非安全狀態都必然會轉為死鎖狀態，但當系統進入不安全狀態后，就有可能進入死鎖狀態（不一定）。反之，只要系統處于安全狀態，系統便不會進入死鎖狀態。

? ??

安全狀態的例子??

??場景- ??資源類型??：假設系統有 ??12 個同類型資源?（如內存塊）。

??進程??：3 個進程?P1?,P2?,P3?。
??資源分配狀態??：
進程最大需求（Max）已分配（Allocated）剩余需求（Need = Max - Allocated）
P1 10 5 5
P2 4 2 2
P3 9 2 7
??當前可用資源??：12?(5+2+2)=3。

??判斷安全狀態??

??初始可用資源??：3。
??尋找可進程??：
- ??P2 的剩余需求為 2?? ≤ 可用資源 3 → 可分配。
- 假設分配給 P2，P2 執行完成后釋放資源：可用資源變為?3+2=5。
??更新可用資源后繼續尋找??：
- ??P1 的剩余需求為 5?? ≤ 可用資源 5 → 可分配。
- P1 執行完成后釋放資源：可用資源變為?5+5=10。
??最后處理 P3??：
- ??P3 的剩余需求為 7?? ≤ 可用資源 10 → 可分配。
- P3 執行完成后釋放資源：可用資源變為?10+2=12。

??安全序列??：P2?→P1?→P3?（或其他可行順序）。
??結論??：系統處于安全狀態。

? ??

不安全狀態的例子??

假設在初始狀態下，進程?P3????先請求 1 個資源??：

??資源分配狀態變化??

??已分配資源更新??：P3 的已分配從 2 → 3，剩余需求從 7 → 6。
??可用資源??：12?(5+2+3)=2。

進程	最大需求	已分配	剩余需求
P1	10	5	5
P2	4	2	2
P3	9	3	6

??判斷是否存在安全序列??

??初始可用資源??：2。
??檢查可滿足的進程??：
- P2 需要 2 ≤ 2 → 分配后可用資源變為?2+2=4。
??后續檢查??：
- P1 需要 5 ≤ 4 → ??不滿足??。
- P3 需要 6 ≤ 4 → ??不滿足??。
- 無其他進程可分配。

??結論??：無法找到安全序列 → 系統處于不安全狀態。
此時系統會拒絕 P3 的資源請求，強制其等待，避免進入不安全狀態。

安全狀態的實際意義??

??動態資源分配??：
每次資源分配前，系統通過算法（如銀行家算法）模擬分配后的狀態，僅允許導致安全狀態的請求。
??資源利用率??：
安全狀態確保資源分配不會因過度保守而浪費，也不會因過度冒險導致死鎖。
??應用場景??：
主要用于理論模型或關鍵系統（如某些數據庫管理系統），因實時計算安全狀態可能帶來性能開銷。

? ? ? ?利用銀行家算法避免死鎖：

1.銀行家算法中的數據結構：

? ?為了實現銀行家算法，在系統中必須設置這樣四個數據結構，分別用來描述系統中可利用的資源、所有進程對資源的最大需求，系統中的資源分配，以及所有進程還需要多少資源的情況。

（1）可利用資源向量Available。（可分配的）這是一個含有m個元素的數組，其中的每一個元素代表一類可利用的資源數目，其初始值時系統中配置的該類全部可用資源的數目，其數值隨該類的資源的分配和回收而動態地改變。如果Available[j] = k,則表示系統中現有Rj類資源 K個。

（2）最大需求矩陣Max。這是一個n*m的矩陣，它定義了系統中n個進程中的每一個進程對m類資源的最大需求。如果Max[i,j]=k，則表示進程i需要Rj類資源的最大數目為K。

?（3）分配矩陣Allocation（已經分配的）? 這也是一個n*m的矩陣，它定義了系統中每一類資源當前已分配給每一進程的資源數。如果Allocation[i,j] = k,則表示進程i當前已分得Rj類資源的數目為k。

? ?(4)需求矩陣Need。這也是一個n*m的矩陣，用來表示每一個進程尚需的各類資源數。如果Need[i,j]=k，則表示進程i還需要Rj類資源K個方能完成其任務。

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? Need[i,j] = Max[i,j]-Allocation[i,j]

?處理資源請求??

當進程?Pi??請求資源時，系統執行以下步驟：

??Step 1: 檢查請求合法性??

Request ≤?Need[i]，繼續；否則拒絕（非法請求）。

??Step 2: 檢查可用資源是否足夠??

Request?≤?Available，繼續；否則讓進程等待。

一定要先滿足上面的兩個條件

??Step 3: 模擬分配資源??

臨時更新數據：
- Available=Available?Request
- Allocation[i]=Allocation[i]+Request
- Need[i]=]?Request

??Step 4: 執行安全狀態檢查??

調用安全狀態檢查算法（見下文）。
如果安全 → 正式分配資源；
不安全 → 撤銷模擬分配，讓進程等待

安全狀態檢查算法??

目標：判斷是否存在一個??安全序列??，使得所有進程都能按順序完成。

??Step 1: 初始化??

定義兩個向量：
- Work=Available（當前可用資源副本）
- Finish[1..n]=false（標記進程是否完成）

??Step 2: 尋找可完成的進程??

遍歷所有進程，找到滿足以下條件的進程?Pi?：
- Finish[i]=false
- Need[i]≤Work（即進程的剩余需求 ≤ 當前可用資源）

??Step 3: 模擬進程完成??

若找到?Pi?：
- Work=Work+Allocation[i]（釋放其占有的資源）
- Finish[i]=true
- 重復 Step 2，直到所有進程完成或找不到可完成的進程。

??Step 4: 判斷結果??

如果所有?Finish[i]=true?→ ??系統安全??，存在安全序列；
否則 → ??系統不安全??。

具體示例（三種資源類型）??

假設系統有三種資源 R1、R2、R3，初始狀態如下：

進程	Max (R1, R2, R3)	Allocation (R1, R2, R3)	Need (R1, R2, R3)
P1	(7, 5, 3)	(0, 1, 0)	(7, 4, 3)
P2	(3, 2, 2)	(2, 0, 0)	(1, 2, 2)
P3	(9, 0, 2)	(3, 0, 2)	(6, 0, 0)
P4	(2, 2, 2)	(2, 1, 1)	(0, 1, 1)
P5	(4, 3, 3)	(0, 0, 2)	(4, 3, 1)

??當前可用資源??：Available=(3,3,2)（總資源數減去已分配資源）。

??場景：進程 P1 請求資源 (0, 2, 0)??

??檢查合法性??：
- Request=(0,2,0)≤Need[P1]=(7,4,3)?→ 合法。
??檢查可用性??：
- Request=(0,2,0)≤Available=(3,3,2)?→ 合法。
??模擬分配??：
- Available=(3,3,2)?(0,2,0)=(3,1,2)
- Allocation[P1]=(0,1,0)+(0,2,0)=(0,3,0)
- Need[P1]=(7,4,3)?(0,2,0)=(7,2,3)
??安全狀態檢查??：
- ??Step 1??：初始化?Work=(3,1,2)，Finish=[false,false,false,false,false]。
- ??Step 2??：尋找可完成的進程：
  - ??P4??：Need[P4] = (0, 1, 1) ≤ Work = (3, 1, 2) → 符合條件。
- ??Step 3??：模擬 P4 完成：
  - Work=(3,1,2)+Allocation[P4]=(2,1,1)→(5,2,3)
  - Finish[P4]=true
- ??繼續尋找??：
  - ??P2??：Need[P2] = (1, 2, 2) ≤ Work = (5, 2, 3) → ??不滿足??（R2分量2 > Work的2）。
  - ??P3??：Need[P3] = (6, 0, 0) ≤ Work = (5, 2, 3) → ??不滿足??（R1分量6 > 5）。
  - ??P5??：Need[P5] = (4, 3, 1) ≤ Work = (5, 2, 3) → ??不滿足??（R2分量3 > 2）。
  - ??P1??：Need[P1] = (7, 2, 3) ≤ Work = (5, 2, 3) → ??不滿足??（R1分量7 > 5）。
- ??無法完成所有進程?? → ??系統不安全??，拒絕請求！