作業系統學習筆記7 | 程序同步與合作

多程序影象除了需要實現切換，還需要處理程序之間的相互影響。本部分介紹程序之間的合作如何變得合理有序。將要涉及號誌、臨界區、死鎖等經典概念的理解。

參考資料：

課程：哈工大作業系統（本部分對應 L16 && L17 && L18 && L19）
實驗：作業系統原理與實踐_Linux - 藍橋雲課 (lanqiao.cn)
筆記：作業系統學習導引 · 語雀 (yuque.com)

感覺這部分理解的還是不夠深入，需要多複習這部分，在實驗五中體會體會。

1. 程序同步與號誌

總的來說，作業系統通過 !號誌! 實現程序同步

1.1 案例引入

兩個程序如果需要共同完成一個任務（即程序合作），需要訊號來溝通。正如司機需要等待售票員關門後發出訊號才可啟動車輛。

等待是程序同步的核心，程序同步的基本結構如下：

程序A執行到某個環節時，發現某個條件不符合，則不繼續向下執行，而是停下來等待；

直到程序B執行到一定程度後產生這個條件，向程序A傳送訊號，程序A繼續向下執行。

如上圖所示，生活中訊號的例子有很多，那麼要說的號誌是什麼？（從訊號到號誌）

發明號誌的迪傑斯特拉因此拿了圖靈獎。此外他還發明瞭程序排程中非常著名的多級反饋佇列演演算法。

前面筆記中提到過生產者-消費者範例，我們繼續以此為例。

這是一個典型的多程序合作的程式典例，生產者在緩衝區滿的時候就不應該繼續像緩衝區輸入了，所以通過while(counter==BUFFER_SIZE); 進行阻塞，生產者程序開始等待

直到消費者程序執行至緩衝區有空餘，生產者才繼續執行；同理緩衝區空了，消費者要等待緩衝區中有內容才能繼續：

多程序的合作合理有序的關鍵就是要判斷那些地方停（阻塞），哪些地方走（執行）。通過走走停停實現合作有序。

1.2 訊號到號誌

然而，上文介紹的訊號，其本身的資訊量還不能解決全部問題。

如果是一個消費者兩個生產者的情況：
- 如下圖，所有消費者生產者共用一個緩衝區，緩衝區已滿；
- 生產者1 生產了一個item，但由於緩衝區已滿counter == BUFFER_SIZE，所以進入休眠 sleep()
- 由於緩衝區是公共的，此時如果再來一個生產者2，生產一個item，counter == BUFFER_SIZE，生產者2也進入休眠
- 由於counter ≠ 0，消費者持續進行，counter-1，這時應當喚醒生產者：wakeup();這時喚醒了一個生產者1；
- 消費者持續迴圈，此時 counter == BUFFER_SIZE-2，不觸發喚醒條件，因此生產者2持續 sleep
補充一個 while 引起的等待跟鎖之間的聯絡：
- while並不一定就是自旋鎖，自旋鎖要看while內部的程式碼怎麼寫，如果內部有排程那就是無等待鎖，如果內部沒有排程那就是忙鎖，也就是自旋鎖
- 使用while不會釋放對cpu的所有權所以叫自旋，阻塞會釋放對cpu的所有權
- 使用while不會釋放對cpu的所有權所以叫自旋，阻塞會釋放對cpu的所有權
這樣問題就是 生產者2 永遠休眠。
此處舉例也並沒有複雜到多個生產者與多個消費者，所以僅用 counter 來進行語意判斷是不夠的，我們需要再用一個量記錄有幾個生產者程序在休眠。

如果我們能夠記錄有兩個生產者程序在休眠，消費者程序執行至符合要求時，就可以根據該資訊的提醒喚醒兩個程序，而不產生遺漏。
號誌：能夠記錄一些資訊，並根據資訊決定程序的休眠和執行。

下圖PPT是在說訊號的不足，需要引入號誌。

1.3 號誌的工作過程

緩衝區滿，生產者1執行，生產者1休眠，賦 sem=-1；
生產者2執行，生產者2休眠，賦 sem=-2；
消費者一次迴圈， wakeup 生產者1，賦 sem=-1；

相當於阻塞佇列，喚醒先阻塞的。這個演演算法也可以自己設計。
消費者第2次迴圈，wakeup 生產者2，賦 sem=0；
這裡 sem 就是號誌，根據號誌來進行程序的等待喚醒。很顯然較於counter（訊號）表達了更多的資訊。
消費者第3次迴圈，賦值 sem = 1；
生產者3 執行，sem > 0 ，表明緩衝區還有一個空位；不需要休眠，賦值 sem=0；
...（如果接下來還有生產者執行，則 sem <0 ，阻塞）

講道理，視訊這裡的彈幕水準相當低。邏輯很簡單，非要過度發揮！

1.4 號誌的定義/實現

號誌的核心理念是用量來記錄必要資訊，用訊號來管理程序是否等待/阻塞。下面是一個具體實現。

號誌的定義：semaphore結構體
- 1個 int 型別的 value，用於記錄資源個數（緩衝區空餘）；
- 1個 PCB 佇列，記錄等待在該號誌上的程序；
程序（對應上文生產者）呼叫 P 函數判斷是否需要等待

P 的意思就是 test，等價於上面1.3 中手動賦值 sem-- 並據此判斷的過程
- P 函數中 value - 1，對應上文的 sem - 1；
- 如果 value < 0，資源不夠則程序 s 休眠，放入阻塞佇列。

程序（對應上問消費者）呼叫 V 函數來喚醒程序；

V 的意思就是 increment，等價於上面1.3 中手動賦值 sem ++ 並據此判斷的過程

V 的程式碼應當為：

V(semaphore s) {
	s.value++;
    if (s.value <= 0) {
    	wakeup(s.queue);
    }
}

// 或者
V(semaphore s) {
    if (s.value < 0) {
    	wakeup(s.queue);
    }
	s.value++;
}
//注意前後加減的區別，並不難理解

1.5 用號誌解決生產者-消費者問題

講到現在，我們是否能用號誌對 1.2 中分析出的 counter 的不足進行改進呢？

我們需要分析程序 」停「 的含義，給出正確的號誌（0為臨界）：

生產者當緩衝區為滿時，生產者停，哪一個值為0？
- 於是設計 empty 初值為 BUFFER_SIZE，當 empty 為 0 則滿；
- 生產者程序每次進行時呼叫P函數測試empty：P(empty);
- 對應使 empty 增加的程序就是消費者，對應在消費者程序寫: V(empty);
消費者當緩衝區空時，消費者停，哪一個值為0？
- 於是設計 full 初值為 0，當 full = 0 時緩衝區空；
- 消費者程序每次進行時呼叫 P 函數測試 full：P(full);
- 對應使 full 增加的程序就是生產者，對應在生產者程序寫：V(full);
緩衝區如何定義：
- 可以是一個檔案：buffer.txt
- 由於是對檔案進行操作，同一時間只能一個程序進行操作（互斥）
  
  具體我此前有過體會：即Linux環境下開啟某個普通檔案，再次開啟（非管理員許可權）時會顯示唯讀，如果修改會有提示。
- 需要定義一個新的號誌 mutex，初值為1，當 mutex = 0 表示有程序正在修改檔案/讀寫緩衝區；
- 這個號誌應當對生產者和消費者其同樣的效用；同時在生產者消費者程序加入：
```
P(mutex);//將要使用緩衝區, 1->0;
V(mutex);//將要釋放使用權, 0->1
```

提到了實驗五，可以開始做了，linux0.11沒有提供號誌，需要在核心中實現號誌的系統呼叫

2. 號誌臨界區保護

上一部分講到通過對號誌的存取和修改，可以實現程序的同步、有序推進，但是我們還需要對號誌進行保護。

2.1 為什麼保護號誌？

上述邏輯看上去已經非常完美，哪裡還有問題呢？

正如學習筆記4中多程序影象實現過程需要解決的問題中的舉例2，我們的號誌必須要 !正確!

如果號誌的含義不對，那麼對於程序同步的指揮只會一團糟。
重複一下筆記4 中提到的那個號誌可能出錯的例子：
- 由於程序任務正執行時時間片用完等因素，作業系統進行了本不應該進行的 reschedule，使得多程序影象出現了錯誤的執行序列：
- 如下圖所示；作業系統每兩行進行一次切換的話：
- empty初始值為 -1，P1執行，P1.register=-2；
- 而在第二行結束切出，P2執行，P2.register 在-1 的基礎上-1 == -2；而本應該累加為 -3
  
  這就出現了錯誤
這就是一種競爭條件，這種排程會讓共用資料（empty）發生錯誤：
- 類似的，核心中的共用資料，如果不做保護，在多程序時間片輪轉的排程策略下，就會出現人無法控制與預料的錯誤；
- 這不是一種程式設計錯誤，而是共用資料沒有保護帶來的語意錯誤。
如下圖，左側第 i 次執行會發生錯誤，第 j 次執行則正確。

2.2 解決競爭條件的直觀想法

那就是給號誌上鎖：

當程序存取號誌並準備修改號誌時，上鎖阻止其他程序存取。
當該程序修改完號誌切換出去後，方可解鎖，讓其他程序進行同樣操作。

這種只能一次做完，不能做一半停下來的工作，OS中就稱為 原子操作，突出一個不可分割。

2.3 臨界區

!臨界區! 是指：一次只允許一個程序進入的某程序的那一段程式碼。比如讀寫、修改號誌的那段程式碼一定是臨界區。

如何標記臨界區、實現臨界區的預期效果呢？

在計算機中就是用程式碼來實現（進入區和退出區）
下面會介紹三個方法；

2.4 臨界區保護原則

臨界區保護的原則：

基本原則：互斥進入；

如果一個程序在臨界區中執行，則其他程序不能進入；
有空讓進：臨界區空閒的時候，應儘快選擇出一個程序進入臨界區（不能所有人卡著門口，結果一個人都進不去）
有限等待：程序發出請求進入臨界區的等待時間必須是有限的，不能出現飢餓問題（不能總是讓別人進，我也要儘快進去）

2.5 臨界區保護方法

2.5.1 輪換法

像值日一樣，輪到程序A（turn==0），程序A就進入臨界區，輪不到則使用 while(turn!=0)；自旋空轉；當程序A 退出臨界區，則 turn=1，輪到下一個程序使用。

下面分析一下這種方法：

滿足互斥進入，一次只能進入一個程序；
不滿足有空讓進，如果P0退出臨界區，P1不進入臨界區，則turn還是1，P0再度想進入臨界區，就會被拒絕。但此時臨界區使用者為空。
輪換法也不一定滿足有限等待，如果P0完成一次臨界區操作後，P1在剩餘區死迴圈，那麼P0就永遠進不去臨界區了，產生了飢餓

2.5.2 標記法

輪換法的弊病主要在於有空不讓進，就像值日，如果看見有垃圾，但不是自己沒有值日的許可權，就只能視而不見。

如何改進？還有一種直觀的想法。

下圖的例子是生活中夫妻買牛奶的情境，如果採用輪換法，如果輪換時間是10分鐘，夫妻二人都會像下圖一樣去買牛奶，導致買多。
標記法就是類似於留一個便條，3：00時丈夫發現沒有牛奶決定去買時，就留下便條，讓妻子知道自己去買了。

標記法是如何運作的？

看看程式碼：
P0 要進臨界區，就先標記自己，flag[0]=true，然後判斷 P1 的標記，如果 P1 已經標記，就等待;

同理其他程序也是，進臨界區之前先標記自己為true，然後等待別的程序的標記變為false

下面分析這種方法：

互斥性：滿足，兩個程序不可能同時進入臨界區。
有空讓進：也不滿足，如果程序P0執行第一句， flag[0]=true，接著P1 進行第一句 flag[1]=true，再切換回P0執行while時進入自旋空轉了。同理切回 P1的while也發生自旋空轉。誰也進不去臨界區。

相當於在某段時間內夫妻二人都看到了沒有奶，都留下了便條，又都看見彼此的便條（可能某人標記完回頭看了一眼便條，發現對方留了便條），所以都沒有去買。
有限等待：這樣也不滿足有限等待。
所以實際上，我們應當讓夫妻二人有一人更勤勞--非對稱標記。也就是在一個程序中做更多的考慮：

舉個例子，讓丈夫做更多的考慮：

當妻子看到有便條，則不必再考慮買奶；當丈夫看到有便條，等待一段時間後再檢視是否有奶，如果還是沒有，則更勤勞地去買奶。如下圖所示：

2.5.3 Peterson演演算法

標記和輪轉的結合。

其實輪轉（值日）就是非對稱標記的，在負責的時間內考慮更多的事情。嘗試上面兩個基本考慮結合起來。

依然打標記
```
flag[0]=true;
flag[1]=true;
```
加上值日/輪轉，給程序P0的 turn 初值賦1；P1的 turn 初值賦0；

視訊彈幕的主要問題是：不理解左右兩個turn是一個變數，這麼寫並不衝突，只是在防止上文兩者卡死的情況出現
達到的效果是：
- 對於程序P0，如果P1標記了，並且輪到了P1（turn=1），則P0自旋空轉，讓P1進入臨界區；
- 當P1退出臨界區，turn = 0；那麼P0就可以結束while空轉，進入臨界區。

下面分析這種方法：

互斥性：滿足。可用反證法假設兩個程序都進入，turn=0=1，不可能。
有空讓進：滿足。有空，假設程序P1不在臨界區，即flag[1]=false，那麼P0就不會在while處空轉，直接進入臨界區。
有限等待：滿足。這是因為turn只能取0/1，兩者不會同時停在while。

如下圖右邊所示，使用這樣的處理（紅色）：

進入臨界區時，置位flag[i]=true, turn=j，如果 j 程序的flag==true，則空轉，
否則進入臨界區執行修改號誌的操作；
退出臨界區時將flag[i]=false;

就不會使 empty 出現語意錯誤。這個演演算法是正確的。

2.5.4 方法A：多程序，麵包店演演算法

多程序情況下，採用麵包店演演算法；是 Peterson演演算法的擴充套件與改進。

標記：
- 每個程序進入時取一個非零序號
  
  進入時獲得的非零序號是當前最大的序號 +1，保證有序。
- 程序離開時置序號位為0，
  
  不為0的序號就算為打上標記
輪轉：在多個程序都有標記（非零）時，序號最小的進入

這保證了非對稱性，總有一個優先。
具體程式碼實現如下圖:
進入時，除了取號（最大值+1），還需要設計一個 choosing 陣列，來確保每次挑選序號的程序只有一個。如果有人正在選號:while(choosing[j]);則等待。
退出時將標記/序號置為0 ：num[i]=0;

下面分析一下這個演演算法：

互斥性：滿足。因為由於取號的限制，最小的只有一個。
有空讓進：如果沒有程序在臨界區，最小序號程序一定進入。
有限等待：離開臨界區的程序再次進入一定排在最後，所以等待有限時間即可被執行。

但是這種演演算法還是太麻煩，並且不斷取號，序號會有溢位風險，我們還需要設定機制來避免溢位。

2.5.5 方法B：硬體指令

上面的演演算法是在軟體層次上做的，比較複雜，下面兩種方法都是在硬體上實現的。

臨界區：只允許一個程序進入；換言之是此時阻止其他程序被排程。
程序排程依靠的是中斷，硬體層面關了中斷，就不會有別的程序插入了，也就不會有指令交錯的問題
cli 命令就是關閉中斷的指令；
sti 命令開啟中斷
- schedule() 是主動的程式排程，不使用中斷，而檢查程式時間片是否用完了進行的排程涉及時鐘中斷，所以這裡的關中斷是防止發生不受控制的時鐘中斷，從而引起程式排程
- 更細緻版本：cli() 與 sli() 修改的是 IF 中斷標誌位，其位於 EFLAGS 暫存器中，schedule() 切換到下一程序後馬上會執行iret，此時會將核心棧中的EFLAGS 彈棧，再次開啟中斷

但是這種方法在多CPU、多核的情況下效果不好：

中斷的原理：CPU上有一箇中斷暫存器INTR，如果置為1（比如時鐘中斷來臨時），則代表需要中斷，引起排程；
而多核CPU上，我們只能控制當前CPU的INTR，不能管理別的CPU的中斷與否。

實驗五號誌的實現可以使用這種方案，工大的模擬器模擬出來的計算機是單CPU的。

2.5.6 方法C：硬體原子指令法

再來思考一件事情：為了使得只有一個程序進入臨界區工作，我們要對於號誌、臨界區上鎖，什麼是鎖呢？

可以考慮用一個號誌/一個整數來描述鎖的狀態，就像上文1.5中的 mutex
但是這種想法顯然不成熟，因為我們使用了號誌來保護號誌
這就意味著不可行嗎？不妨考慮一下前面提到的原子性。
如果把修改 mutex 的指令做成 原子指令

即中途不可能打斷，要麼執行，要麼不執行，

那麼執行時也就自動上鎖.
用硬體原子指令修改一個整型變數，根據這個變數，再來判斷應不應當進入臨界區
下圖是一種程式碼實現：

通過 TestAndSet 原子性操作，實現 while(TestAndSet(&lock));的一次執行，不會被打斷。

這裡彈幕的問題主要是不理解 X 和 lock 是公用的一塊記憶體，因為傳遞的引數是地址。

2.6 總結

一句話：用臨界區保護號誌，用號誌實現程序同步。

3. 號誌程式碼實現

號誌原理複雜，但程式碼實現較為精簡。

號誌的用途：

使用者程式可以使用號誌實現同步

OS內部也要使用大量號誌程式碼來完成程序同步

3.1 生產者-消費者

下面還是以生產者-消費者為例，

在核心中使用系統呼叫，申請一個號誌
- 多個程序都可見，所以號誌應當在核心中。
- sem.c 原始碼如下圖左下角；它規定了號誌的相關內容，比如下面程式碼中定義了20個號誌，一個name陣列存放其名字，然後是它們的 value 和 PCB 佇列。
  
  sys_sem_open 系統呼叫完成的工作就是：在上面name[]表中找到對應名字（如 empty）的號誌，如果已經有這個號誌，那麼直接返回即可，沒有則建立並設初值；
- 申請的號誌，各程序都可見，據此決定如何進行工作。
fd 是檔案，這裡假設生產者向檔案中依次輸出 1~5 這 5 個數，每個數佔 4 個位元組，每次寫之前，都要呼叫 sem_wait(sd)，來判斷空餘狀態；

sem_wait() 根據傳入的 sd 找到對應的 value，如果value-- < 0，說明沒有空餘位置，應當阻塞自己，將自己放入等待佇列;

注意：這裡後--；是先執行判斷再減1 即前提是if為true才會減value。

放入等待佇列後進行 schedule，切換下一個程序就緒.

這裡的不完整程式碼就是實驗五需要完成的內容之一。
本部分假定與LInux 0.11 適配，使用單CPU，可以使用2.5.5 中的硬體指令關中斷的方法。
在臨界區前後加入 cli() 和 sti() 保護號誌。

3.2 借鑑 Linux 0.11

Linux 0.11 的核心中沒有上述號誌的設計，如何實現程序間同步呢？

例子：使用者程式發出read系統呼叫，在核心中最終呼叫bread，到磁碟上讀磁碟塊；

具體細節會在後面講檔案系統的時候講；

首先獲得一個空閒的記憶體bh用於緩衝資料，bh的資料型別是 buffer_head；採用DMA將磁碟塊內容逐步讀進來。
ll_rw_block(READ, bh)，啟動磁碟讀；
wait_on_buffer(bh)，在緩衝區bh上等待，即啟動磁碟讀之後睡眠，等待磁碟讀完由相關中斷喚醒。
bh中有類似號誌的資料：bh->b_lock; 各個程序根據這個lock決定如何工作；

同樣需要對其進行保護，新增 cli() 和 sti().
讀取磁碟時，lock_buffer() 中的 b_lock=1，表示已經鎖上了；那麼當前程序 sleep_on(&bh->b_wait);

當讀完後通過中斷會解鎖。

這裡的機制跟前面號誌機制不同的是：
- 這裡用的是 while(1) （而不是if）
- 為什麼是while 看下面：

while(號誌) 的工作機制：

我們需要從 sleep_on 這裡看起，看看程序如何「睡」、如何喚醒（喚醒時就能看出 while 的機制）
如下圖右側程式碼所示：
```
struct task_struct *tmp;
tmp=*p;
*p=current;
```
這是很隱蔽的佇列，就是把當前程序放入阻塞佇列
將自己的狀態改為阻塞狀態，呼叫 schedule 切換程序；後面被喚醒，再排程切換回來時，會從這裡恢復執行
f (tmp) temp->state=0; 當前程序被喚醒了，那麼佇列中的下一個程序也被喚醒；

上文所說的隱祕佇列到底長什麼樣子呢？

sleep_on 的函數引數應當是一個佇列，所以按照以前的知識，我們應當傳入隊首的指標，而這裡**p是隊首指標的指標。
tmp 是區域性變數，使其指向 task_struct.
再將 *p 指向 current，移向了當前（正要入隊）的 task_struct；按照資料結構的知識，這裡是新來的放到了隊首。
按照資料結構的頭插法，task_struct 應該有一個 next 指標，讓當前程序的 task_struct->next 指向 tmp，佇列連結就完成了
但是設計者考慮了核心的特性，這裡的tmp區域性變數，已經儲存在了核心棧中
tmp 區域性變數的作用，就是用於指向佇列中下一個程序的 task_struct，作用相當於 next 指標，如下圖中的虛線所示

解釋為什麼 tmp 可以作為 next 指標：

區域性變數tmp是放在棧中，程式碼在核心態執行，tmp是放在核心棧。

當前程序的核心棧在當前程序中能找到，切換時核心棧會跟著切換，所以切換後可以找到當前程序的核心棧，當前程序的核心棧中可以找到當前程序的tmp

而當前程序的tmp指向了下一個程序的PCB，下一個程序的PCB中可以找到下一個程序的核心棧，下一個程序的核心棧中可以找到也可以找到下一個程序的tmp，下一個程序的tmp指向再下一個程序的PCB，以此迴圈

如何將放入 sleep_on 的程序喚醒呢？

執行磁碟中斷時，會執行 end_request(1)
end_request(1) 會執行 unlock_buffer()；
unlock_buffer() 會將 lock 置為0，並wake_up;
wake_up 在佇列不空的情況下（p&&*p）將隊首的PCB的state置為0，即為就緒態，此時喚醒了隊首程序

程序A被喚醒，應當從哪裡執行？

很顯然，從進入睡眠前停止的地方進行。
回看上面 sleep_on 的程式碼，state設為阻塞態，schedule到其他程序切換
所以喚醒後繼續執行 :
```
if(tmp){
    tmp -> state = 0;
}
```
這兩行程式碼喚醒了隊首程序的下一個程序B；同樣這個程序B會執行相同的兩行程式碼喚醒B的下一個程序C。依次遞推，將阻塞佇列中的全部程序喚醒。
- 注意這裡的「喚醒」，只是它們能夠被排程，並不意味著已經被排程。
- 接下來會用排程演演算法去找優先順序最高的下一個程序X，排程執行。
- 該程序X執行後進入臨界區，會把lock 鎖上（=1）；這時其他程序依次while，把自己休眠掉。

到這裡其實就解釋了 3.2 最開始 lock_buffer 中，為什麼使用的是 while 迴圈，因為這裡會把阻塞佇列中的所有程序喚醒，而接下來只有一個程序能夠進入臨界區並上鎖，剩下的程序需要再次sleep

而 if 只喚醒阻塞佇列中第一個。

為什麼要將所有程序都喚醒？我們前面介紹的 if 方案只需要喚醒一個。

if 方案中排在前面的程序一定先執行，但是後來的程序優先順序可能更高；
在阻塞佇列中，你不能確定剩下的程序的優先順序是否更高，所以乾脆全部喚醒，讓 schedule() 來決定到底切換給誰
回看前面的while迴圈：
```
lock_buffer(buffer_head *bh){
    cli();
    while(bh->b_lock){
        sleep_on(&bh->b_wait);
    }
    bh -> b_lock = 1;
    sti();
}
```
可見這裡的while迴圈是對所有喚醒的程序進行判斷的過程，讓高優先順序的進入，其他的經過迴圈判斷後睡眠。

3.3 對比

while(lock) 和前面 if(signal) 有什麼異同？

前者不需要負數，不需要記要記錄阻塞佇列中有多少程序在等待。因為它每次都把所有都喚醒，通過 while 判斷將不能進入臨界區的程序休眠。
前者喚醒阻塞佇列中全部程序，按照優先順序排程；
後者喚醒阻塞佇列中的第一個，按照（也只能按照）先後順序排程；後者的想法很直觀，但是缺點明顯。

推薦用 if 這個直觀想法實現實驗五，再用 while 實現。

4. 死鎖處理

這部分是關於程序的最後一部分。死鎖也是多程序影象可能會發生的問題。

4.1 死鎖來源

再回到生產者-消費者這個例子；回到 1.5 Part.

如果調換一下號誌的使用順序，如下圖，就會產生死鎖：

因為是使用者程式，使用者完全可以這樣調換（預設使用者不知情）；即先申請mutex後申請empty。
執行一下：
- 生產者 A 程序（左）執行mutex ，原為1，賦值為0；
- A程序執行 empty，0，表示緩衝區滿了，執行完後變為-1，阻塞；
- 消費者 B程序執行，mutex 0變為-1，阻塞；
- 而 A 程序鎖在 empty，必須 B程序執行V(empty)方可解鎖；而 V(empty) 依賴於 P(mutex);
- B 的 P(mutex) 依賴於 A 的 V(mutex)，而後者已經卡住了。

死鎖：多個程序由於互相等待對方持有的資源而造成誰都無法執行的情況

設想再來一個程序C，想要申請 mutex，也會死鎖，與之關聯的程序可能也會死鎖。這樣就像感染一樣，牽連到的程序越來越多。電腦變得很慢，卡死。

4.2 死鎖的成因

關於死鎖，有一個很形象的圖，下圖右側，A的前進被B阻礙，B的前進被C阻礙，C的前進被D阻礙，D的前進被A阻礙...

具體成因歸納：

有一些資源（如號誌）互斥使用，佔用後別人無法使用；
程序X佔用了這種資源，不釋放，又去申請其他資源；
恰巧申請的資源正被程序N佔用，程序X會等待；
如果程序N正好要申請 X 佔用的互斥資源，則進入死鎖。

再簡要一點，死鎖的必要條件：

4.3 死鎖處理方法

聯絡生活，處理一個問題也就如下幾個方面：

死鎖忽略：死鎖還是一個小概率事件，假如個人PC機宕機了，則可以重啟來解決；但另外一些比較重要的場景，例如衛星上的作業系統，銀行的作業系統就肯定不能死鎖忽略了。

死鎖忽略就不在下面處理方法詳細探討的範疇內了

參考資料：死鎖的處理策略—預防死鎖、避免死鎖、檢測和解除死鎖-麵包板社群 (eet-china.com)

4.3.1 死鎖預防

死鎖預防的基本想法是在程序執行前，破壞死鎖出現的必要條件，有兩種考慮：

在程序執行前，一次性申請所有需要的資源，這就不會出現佔有資源的同時還要申請其他資源。（破壞請求和保持條件）
- 缺點：
  1. 需要預知未來，程式設計困難；
    
    比如有一些資源是通過if來決定是否申請的，這種方法需要編譯時列出全部需要資源，全部申請。
  2. 申請全部資源意味著一些分配到的資源很長時間後才會被使用，資源利用率低；
順序資源分配，首先給系統中的資源編號，規定每個程序必須按編號遞增的順序請求資源，同類資源（即編號相同的資源）一次申請完。（破壞迴圈等待條件）

這個不太好理解：

一個程序只有已佔有小編號的資源時，才有資格申請更大編號的資源。按此規則，已持有大編號資源的程序不可能逆向地回來申請小編號的資源，從而就不會產生迴圈等待的現象。
- 缺點：需要對程序排序，還是浪費資源