系統模型（System Model）

在作業系統中，核心任務之一是有效地管理和分配有限的資源給多個同時運行的threads或processes。一個良好的系統模型能讓我們理解資源如何在競爭的環境中被請求、使用與釋放。

資源是指任何執行緒在執行過程中可能需要使用的軟硬體元件。它們通常是有限的，這意味著同一時間能被使用的數量是固定的。資源可以大致分為兩類：

第一種，硬體資源（Hardware Resources）：

• CPU (處理器)：執行緒需要 CPU 時間來執行指令。
• 記憶體 (Memory)：執行緒需要記憶體空間來存放程式碼和資料。
• I/O 裝置：例如磁碟機、印表機、掃描器、網路卡等。這些裝置在同一時間通常只能被一個執行緒使用。

第二種，軟體資源（Software Resources）：

• 鎖（Locks）或互斥量（Mutexes）：這些是程式設計師用來保護共享資料結構的同步工具。例如，一個鎖可能保護一個共享的佇列（Queue）或雜湊表（Hash Table），以確保同一時間只有一個執行緒可以修改它，避免資料競爭（data races）和不一致性。

資源使用的基本流程

每個執行緒在與資源互動時，都必須遵循一個標準的三階段生命週期：

第一階段，請求 (Request)

• 執行緒向作業系統發出請求，要求使用某個資源。
• 如果該資源目前是可用的（available），作業系統會立即將其分配給該執行緒。
• 如果該資源已被其他執行緒佔用，請求的執行緒將會進入等待狀態（waiting state），直到資源被釋放。在某些情況下，如果資源可以被多個執行緒同時使用（例如，讀取共享資料），則可能允許多個請求同時成功。

第二階段，使用 (Use)

• 一旦成功獲得資源，執行緒就可以開始使用它。
• 對於硬體資源，這可能意味著執行緒開始在 CPU 上運行、存取記憶體或執行 I/O 操作。
• 對於軟體鎖，這意味著執行緒成功進入了受鎖保護的臨界區（critical section），對共享資料進行獨佔式修改。

第三階段，釋放 (Release)

• 當執行緒完成對資源的使用後，它必須將該資源歸還給作業系統。
• 這通常是透過一個明確的系統呼叫來完成（例如，釋放鎖、關閉檔案）。
• 資源被釋放後，作業系統會檢查是否有其他正在等待該資源的執行緒，並將其中一個從等待狀態轉為就緒（ready）狀態，準備再次執行。

多執行緒程式中的死結（Deadlock in Multithreaded Applications）

死結是多執行緒程式中最難以解決的同步問題之一。當多個執行緒彼此佔有資源並互相等待對方所佔有的資源時，就會發生死結，導致所有執行緒都無法繼續執行。

// 建立了兩把鎖 first_mutex 和 second_mutex
pthread_mutex_t first_mutex;
pthread_mutex_t second_mutex;

// 建立兩個執行緒 thread_one 和 thread_two
pthread_mutex_init(&first_mutex, NULL);
pthread_mutex_init(&second_mutex, NULL);

// 執行緒函數：
// 執行緒一
void *do_work_one(void *param) {
    pthread_mutex_lock(&first_mutex);       // 鎖住第一把鎖
    pthread_mutex_lock(&second_mutex);      // 嘗試鎖住第二把鎖
    // 做一些工作...
    pthread_mutex_unlock(&second_mutex);    // 釋放第二把鎖
    pthread_mutex_unlock(&first_mutex);     // 釋放第一把鎖
    pthread_exit(0);
}

// 執行緒二
void *do_work_two(void *param) {
    pthread_mutex_lock(&second_mutex);      // 鎖住第二把鎖
    pthread_mutex_lock(&first_mutex);       // 嘗試鎖住第一把鎖
    // 做一些工作...
    pthread_mutex_unlock(&first_mutex);     // 釋放第一把鎖
    pthread_mutex_unlock(&second_mutex);    // 釋放第二把鎖
    pthread_exit(0);
}

範例中，有兩把鎖 (first_mutex 和 second_mutex)，以及兩個執行緒 (thread_one 和 thread_two)。死結發生在一個特定的、不幸的執行順序下：

• thread_one 成功鎖住了 first_mutex。
• thread_two 在此時成功鎖住了 second_mutex。
• 此時，thread_one 繼續執行，嘗試鎖住 second_mutex。然而，這把鎖已被 thread_two 持有，因此 thread_one 進入等待狀態。
• 同時，thread_two 繼續執行，嘗試鎖住 first_mutex。這把鎖已被 thread_one 持有，因此 thread_two 也進入等待狀態。

結果是：thread_one 在等待 thread_two 釋放資源，而 thread_two 則在等待 thread_one 釋放資源。兩者都無法前進，形成了無限期的互相等待，這就是死結。

死結的四個必要條件

程式碼之所以會發生死結，是因為它同時滿足了死結發生的四個必要條件：

1. 互斥（Mutual Exclusion）：first_mutex 和 second_mutex 都是互斥資源，一次只能被一個執行緒持有。
2. 佔有且等待（Hold and Wait）：thread_one 在佔有 first_mutex 的同時，等待 second_mutex；thread_two 在佔有 second_mutex 的同時，等待 first_mutex。
3. 不可搶佔（No Preemption）：兩把鎖都不能被強行從持有它的執行緒手中搶走。
4. 循環等待（Circular Wait）：thread_one 等待 thread_two，而 thread_two 等待 thread_one，形成了一個資源等待的循環。

死結為何難以偵測

死結之所以棘手，是因為它不是一個固定的錯誤，而是一種非確定性（non-deterministic）的行為。這使得在開發和除錯過程中很難發現和重現。

第一，非決定性與排程影響：死結的發生完全取決於執行緒的排程順序和相對執行的時間點。如果 thread_one 運行得非常快，在 thread_two 執行前就完成了所有操作，那麼死結就不會發生。反之，如果兩個執行緒在錯誤的時機點交錯執行，就會卡住。

第二，難以重現：由於排程器行為的不可預測性，同樣的程式碼在不同電腦、不同作業系統版本，甚至在同一台電腦的不同運行時間下，都可能表現出不同的行為。這讓程式設計師難以可靠地重現死結，從而無法進行有效的除錯。

第三，除錯困難：當死結發生時，程式不會崩潰或顯示錯誤訊息。它只是**「卡住不動」**，看起來就像是程式反應變慢了。這很容易誤導開發者，讓他們以為是程式效能問題，而不是同步錯誤。

活結（Livelock）

活結（Livelock）是一種特殊的同步問題，它會導致執行緒無法取得進展，但與死結不同的是，執行緒並沒有被阻塞。它們處於一種忙碌的重試循環中，不斷地改變狀態，卻永遠無法完成工作。

活結最核心的特徵是「積極的失敗」。執行緒們沒有在等待，而是在**主動「讓路」**或「重試」，但由於步調一致，導致它們永遠無法突破困境。你的比喻非常生動地描繪了這個情境：在走廊上相遇的兩人，互相閃避卻不斷碰撞，陷入無限的讓路循環。

活結的運作情境

// 活結的情境
while (1) {
    pthread_mutex_lock(&first_mutex);

    if (pthread_mutex_trylock(&second_mutex) != 0) {
        // 嘗試鎖第二把鎖失敗，主動釋放第一把鎖並重試
        pthread_mutex_unlock(&first_mutex);
        continue;  // 再來一次
    }

    // 成功鎖住兩把鎖
    // ... 做一些工作 ...

    pthread_mutex_unlock(&second_mutex);
    pthread_mutex_unlock(&first_mutex);
    break;
}

在這個範例中，一個執行緒會嘗試鎖住兩把互斥鎖。如果第二把鎖被佔用，它會主動釋放已持有的第一把鎖，然後從頭開始重試。假設有兩個執行緒，各自運行著這段程式碼，並在相同的時間點啟動：

1. Thread One 成功鎖住 first_mutex。
2. Thread Two 成功鎖住 second_mutex。
3. Thread One 接著呼叫 pthread_mutex_trylock(&second_mutex)，但因為這把鎖被 Thread Two 持有，trylock 會立即失敗。
4. Thread One 接著會執行 pthread_mutex_unlock(&first_mutex)，並通過 continue 重新進入循環。
5. 在幾乎同一時間，Thread Two 也嘗試呼叫 pthread_mutex_trylock(&first_mutex)，並同樣因為被佔用而失敗。
6. Thread Two 也會解鎖 second_mutex，然後重試。

結果是，兩個執行緒都在不斷地釋放資源、重試、失敗、再釋放，陷入一個不斷變換狀態但沒有任何進展的死循環。它們沒有被阻塞，CPU 佔用率可能很高，但工作卻停滯不前。

活結的解法：加入隨機退避（Random Backoff）

為了打破同步碰撞的循環，常見解法是在重試之間插入隨機延遲（Random Delay / Backoff）。

#include <unistd.h>  // for usleep
#include <stdlib.h>  // for rand

while (1) {
    pthread_mutex_lock(&first_mutex);

    if (pthread_mutex_trylock(&second_mutex) != 0) {
        pthread_mutex_unlock(&first_mutex);

        // 加入隨機等待時間（1ms ~ 5ms）
        int backoff = (rand() % 5 + 1) * 1000;  // 單位：微秒
        usleep(backoff);
        continue;
    }

    // 成功鎖定兩把鎖
    // ... 執行工作 ...

    pthread_mutex_unlock(&second_mutex);
    pthread_mutex_unlock(&first_mutex);
    break;
}

當兩個執行緒都在忙碌重試時，隨機退避機制會讓它們的重試時間錯開。

• 當 Thread One 失敗後，它會隨機等待一段時間。
• 當 Thread Two 失敗後，它也會隨機等待一段時間。
  由於這兩個隨機延遲的時間極不可能完全相同，一個執行緒會比另一個先醒來並再次嘗試。這一次，它成功的機率就高得多，因為它的「競爭對手」還在睡眠中。一旦它成功鎖定了兩把鎖，就能完成工作並釋放資源，從而打破僵局。