1. 定義

死鎖是指兩個或多個進程（或線程）在執行過程中，因爭奪資源而造成的一種僵局，每個進程都無限期地等待其他進程釋放它們所持有的資源。在這種情況下，沒有任何進程能夠繼續執行，除非有外部干預。

2. 死鎖的必要條件

根據Dijkstra的理論，死鎖的發生必須同時滿足以下四個必要條件：

1. 互斥條件（Mutual Exclusion）：

   • 資源不能被共享，一次只能被一個進程使用。例如，打印機、磁帶機等資源在使用時不能被多個進程同時占用。

2. 請求與保持條件（Hold and Wait）：

   • 一個進程已經持有一個資源，但又請求新的資源。如果新資源被其他進程占用，請求進程將被阻塞，但它仍然保持對已有資源的占用。

3. 不可剝奪條件（No Preemption）：

   • 資源不能被強制剝奪，只能由占用它的進程主動釋放。例如，內存資源不能被強制從一個進程轉移到另一個進程。

4. 循環等待條件（Circular Wait）：

   • 存在一個進程序列 P1?,P2?,…,Pn?，使得 P1? 等待 P2? 持有的資源，P2? 等待 P3? 持有的資源，……，Pn? 等待 P1? 持有的資源，形成一個等待環路。

3. 死鎖的示例

哲學家進餐問題

哲學家進餐問題是死鎖的經典示例。五位哲學家圍坐在一張圓桌旁，每位哲學家面前有一支叉子，左右各一支。哲學家需要同時拿起左右兩支叉子才能進餐。如果每位哲學家都先拿起左邊的叉子，然后等待右邊的叉子，最終會導致所有哲學家都餓死，因為每個人都持有一支叉子并等待另一支叉子。

銀行家算法

銀行家算法是一種預防死鎖的算法，通過資源分配圖來檢測系統是否處于安全狀態。如果系統處于安全狀態，銀行家算法會分配資源；否則，它會等待，直到系統進入安全狀態。銀行家算法通過確保系統不會進入不安全狀態來預防死鎖。

4. 死鎖的處理策略

1. 預防死鎖（Deadlock Prevention）：

   • 通過破壞死鎖的必要條件之一來預防死鎖的發生。例如：

     • 資源分級：對資源進行編號，哲學家總是先拿起編號較小的叉子，再拿起編號較大的叉子，從而破壞循環等待條件。

     • 限制資源分配：限制同時請求資源的數量，確保系統不會進入死鎖狀態。

2. 避免死鎖（Deadlock Avoidance）：

   • 動態地檢查資源分配是否會導致死鎖。例如：

     • 銀行家算法：通過資源分配圖來檢測系統是否處于安全狀態，只在安全狀態下分配資源。

3. 檢測死鎖（Deadlock Detection）：

   • 定期檢查系統是否處于死鎖狀態。如果檢測到死鎖，采取措施解決。例如：

     • 資源分配圖：通過資源分配圖檢測循環等待條件。

     • 超時機制：如果某個進程等待資源的時間超過某個閾值，認為系統可能進入死鎖狀態。

4. 恢復死鎖（Deadlock Recovery）：

   • 當檢測到死鎖時，采取措施恢復系統。例如：

     • 資源剝奪：強制剝奪某些進程持有的資源，使其能夠繼續執行。

     • 進程終止：終止某些進程，釋放其持有的資源。

5. 死鎖的示例代碼

以下是一個簡單的C語言示例，展示如何通過資源分級來預防死鎖。

?

#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#include <semaphore.h>
#include <unistd.h>#define NUM_PHILOSOPHERS 5sem_t forks[NUM_PHILOSOPHERS];void* philosopher(void* arg) {int id = *(int*)arg;int left_fork = id;int right_fork = (id + 1) % NUM_PHILOSOPHERS;while (1) {// 思考printf("Philosopher %d is thinking\n", id);sleep(1);// 餓了，嘗試拿起叉子printf("Philosopher %d is hungry\n", id);// 確保先拿起編號較小的叉子if (left_fork < right_fork) {sem_wait(&forks[left_fork]);printf("Philosopher %d picked up left fork %d\n", id, left_fork);sem_wait(&forks[right_fork]);printf("Philosopher %d picked up right fork %d\n", id, right_fork);} else {sem_wait(&forks[right_fork]);printf("Philosopher %d picked up right fork %d\n", id, right_fork);sem_wait(&forks[left_fork]);printf("Philosopher %d picked up left fork %d\n", id, left_fork);}// 吃飯printf("Philosopher %d is eating\n", id);sleep(1);// 放下叉子sem_post(&forks[right_fork]);printf("Philosopher %d put down right fork %d\n", id, right_fork);sem_post(&forks[left_fork]);printf("Philosopher %d put down left fork %d\n", id, left_fork);}
}int main() {pthread_t philosophers[NUM_PHILOSOPHERS];int ids[NUM_PHILOSOPHERS];// 初始化信號量for (int i = 0; i < NUM_PHILOSOPHERS; i++) {sem_init(&forks[i], 0, 1);}// 創建哲學家線程for (int i = 0; i < NUM_PHILOSOPHERS; i++) {ids[i] = i;pthread_create(&philosophers[i], NULL, philosopher, &ids[i]);}// 等待線程結束for (int i = 0; i < NUM_PHILOSOPHERS; i++) {pthread_join(philosophers[i], NULL);}// 清理信號量for (int i = 0; i < NUM_PHILOSOPHERS; i++) {sem_destroy(&forks[i]);}return 0;
}

代碼說明

• 資源分級：哲學家總是先拿起編號較小的叉子，再拿起編號較大的叉子，從而破壞循環等待條件。

• 信號量：使用信號量來控制叉子的獲取和釋放，確保資源的互斥訪問。

總結

死鎖是并發系統中一個常見的問題，通過理解死鎖的必要條件和采取適當的處理策略，可以有效地預防和解決死鎖問題。資源分級是一種簡單而有效的預防死鎖的方法，通過打破循環等待條件，確保系統不會進入死鎖狀態。