Linux下用pthread_mutex解決哲學家進餐死鎖問題

Linux下用pthread_mutex解決哲學家進餐死鎖問題

問題描述

經典同步問題：6位哲學家圍桌而坐，每人左右各有一根筷子（共6根）。進餐需同時拿左右兩根筷子。若所有人同時拿左邊筷子，則每人只有一根，無限等待 → 死鎖。

死鎖避免策略：資源有序分配

對筷子編號0~5。規定：
偶數號哲學家：先拿右手筷子（編號小），再拿左手筷子（編號大）
奇數號哲學家：先拿左手筷子（編號大），再拿右手筷子（編號小）

這打破了循環等待條件（死鎖四條件之一），確保至少一人能拿到兩根筷子進餐。

完整C代碼實現

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <errno.h>
#include <pthread.h>

#define NUM_P 6

typedef struct {
    pthread_mutex_t chopsticks[NUM_P];  // 6根筷子互斥鎖
    int num;                            // 哲學家編號
    pthread_mutex_t num_lock;           // 編號傳遞同步鎖
} Phi;

void* philosopher(void* arg) {
    Phi* sp = (Phi*)arg;
    int id, next_id;
    
    // 安全讀取編號：主線程創建後解鎖
    pthread_mutex_lock(&sp->num_lock);
    id = sp->num;
    pthread_mutex_unlock(&sp->num_lock);
    
    printf("No.%d philosopher has come\n", id);
    next_id = (id + 1) % NUM_P;  // 右邊筷子編號
    sleep(5);  // 等待所有線程就緒
    
    if (id % 2 == 1) {  // 奇數：先大後小
        pthread_mutex_lock(&sp->chopsticks[next_id]);
        pthread_mutex_lock(&sp->chopsticks[id]);
    } else {            // 偶數：先小後大
        pthread_mutex_lock(&sp->chopsticks[id]);
        pthread_mutex_lock(&sp->chopsticks[next_id]);
    }
    
    printf("No.%d philosopher has eaten!\n", id);
    
    pthread_mutex_unlock(&sp->chopsticks[next_id]);
    pthread_mutex_unlock(&sp->chopsticks[id]);
    return NULL;
}

int main(void) {
    pthread_t tid[NUM_P];
    Phi phis = {0};
    int err;
    
    // 初始化鎖
    for (int i = 0; i < NUM_P; i++)
        pthread_mutex_init(&phis.chopsticks[i], NULL);
    pthread_mutex_init(&phis.num_lock, NULL);
    
    // 創建哲學家線程
    for (int i = 0; i < NUM_P; i++) {
        pthread_mutex_lock(&phis.num_lock);  // 鎖定，等待子線程讀取
        phis.num = i;
        err = pthread_create(&tid[i], NULL, philosopher, &phis);
        if (err) { fprintf(stderr, "create: %s\n", strerror(err)); exit(1); }
    }
    
    // 等待所有線程結束
    for (int i = 0; i < NUM_P; i++) {
        pthread_join(tid[i], NULL);
        printf("Main: thread %d returned\n", i);
    }
    
    // 清理
    for (int i = 0; i < NUM_P; i++)
        pthread_mutex_destroy(&phis.chopsticks[i]);
    pthread_mutex_destroy(&phis.num_lock);
    return 0;
}

關鍵技術點解析

1. 編號傳遞同步（num_lock）

主線程循環創建線程時，若不加同步，子線程可能讀到下一輪的num值。解決：主線程設置num後鎖定num_lock，子線程讀取後解鎖num_lock，主線程才能進入下一輪。這是典型的生產者-消費者單槽位同步。

2. 死鎖預防：資源有序獲取

編號偶/奇決定獲取順序，確保不會形成環路等待。這比銀行家算法、超時重試更簡潔高效。

3. 互斥鎖初始化與銷毀

靜態初始化PTHREAD_MUTEX_INITIALIZER僅適用於靜態分配的鎖。動態分配（結構體成員、malloc）必須用pthread_mutex_init/destroy。

運行結果示例

No.0 philosopher has come
No.1 philosopher has come
...
No.5 philosopher has come
No.0 philosopher has eaten!
No.2 philosopher has eaten!
No.4 philosopher has eaten!
No.1 philosopher has eaten!
No.3 philosopher has eaten!
No.5 philosopher has eaten!
Main: thread 0 returned
...
Main: thread 5 returned

可見偶數號（0,2,4）優先進餐，之後奇數號（1,3,5）依次進行，無死鎖發生。

擴展思考

• 公平性：當前方案可能導致飢餓（某哲學家長期搶不到鎖），可引入信號量限制並發數（最多5人同時嘗試拿筷子）
• 性能：細粒度鎖（每根筷子一把鎖）比單一大鎖並發度高
• 避免活鎖：若加入隨機退避重試，需防止活鎖

這個例子展示了如何用最基礎的pthread_mutex_t，通過巧妙的資源排序策略，優雅地解決經典並發問題。