哲學家進餐問題（Dining Philosophers Problem）是一個經典的同步問題，最早由計算機科學家Edsger Dijkstra提出，用來說明在多線程環境中如何避免死鎖和資源競爭。

問題描述：

假設有五位哲學家圍坐在一張圓桌旁。每位哲學家面前有一碗飯和一支筷子。哲學家們的生活由兩個狀態組成：思考和進餐。當哲學家要進餐時，他需要同時拿起左邊和右邊的筷子（即兩支筷子）。只有在拿到兩支筷子後，哲學家才能開始進餐。進餐完畢後，哲學家會放下筷子並繼續思考。

問題的挑戰：

• 死鎖：如果每位哲學家都拿起自己左邊的筷子，然後等待右邊的筷子，那麼所有哲學家都無法進餐，系統進入死鎖狀態。
• 資源競爭：哲學家之間需要協調以避免無限等待，確保每位哲學家都有機會進餐。

解決方案：

為了解決這個問題，計算機科學家提出了多種不同的解決方案，例如：

1. 限制最大進餐人數：允許最多四位哲學家同時拿起筷子進餐，這樣至少有一位哲學家可以同時拿到兩支筷子。

2. 奇偶哲學家策略：將哲學家分為奇數和偶數。奇數編號的哲學家先拿左邊的筷子，再拿右邊的筷子，而偶數編號的哲學家則先拿右邊的筷子，再拿左邊的筷子。這樣可以避免死鎖。

3. 優先權策略：給每位筷子編號，哲學家按順序嘗試拿起編號較小的筷子，然後再拿編號較大的筷子。

4. 使用信號量：使用信號量或互斥鎖來控制對筷子的訪問，確保每次只有一位哲學家能成功拿到兩支筷子。

請 AI 提供一個使用C語言實現哲學家用餐問題的範例。這個範例使用POSIX線程（pthread）和互斥鎖（mutex）來解決問題。以下是代碼：

// dining_philosophers.c
#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#include <unistd.h>

#define NUM_PHILOSOPHERS 5
#define THINKING 0
#define HUNGRY 1
#define EATING 2

pthread_mutex_t mutex;
pthread_cond_t cond[NUM_PHILOSOPHERS];
int state[NUM_PHILOSOPHERS];
int phil[NUM_PHILOSOPHERS] = {0, 1, 2, 3, 4};

void *philosopher(void *arg);
void take_forks(int phil_num);
void put_forks(int phil_num);
void test(int phil_num);

int main() {
    int i;
    pthread_t thread_id[NUM_PHILOSOPHERS];
    
    pthread_mutex_init(&mutex, NULL);
    for (i = 0; i < NUM_PHILOSOPHERS; i++)
        pthread_cond_init(&cond[i], NULL);
    
    for (i = 0; i < NUM_PHILOSOPHERS; i++)
        pthread_create(&thread_id[i], NULL, philosopher, &phil[i]);
    
    for (i = 0; i < NUM_PHILOSOPHERS; i++)
        pthread_join(thread_id[i], NULL);
    
    pthread_mutex_destroy(&mutex);
    for (i = 0; i < NUM_PHILOSOPHERS; i++)
        pthread_cond_destroy(&cond[i]);
    
    return 0;
}

void *philosopher(void *arg) {
    int phil_num = *(int *)arg;
    while (1) {
        printf("Philosopher %d is thinking\n", phil_num);
        sleep(rand() % 3 + 1);  // 思考一段隨機時間
        
        take_forks(phil_num);
        
        printf("Philosopher %d is eating\n", phil_num);
        sleep(rand() % 3 + 1);  // 進食一段隨機時間
        
        put_forks(phil_num);
    }
}

void take_forks(int phil_num) {
    pthread_mutex_lock(&mutex);
    state[phil_num] = HUNGRY;
    test(phil_num);
    while (state[phil_num] != EATING)
        pthread_cond_wait(&cond[phil_num], &mutex);
    pthread_mutex_unlock(&mutex);
}

void put_forks(int phil_num) {
    pthread_mutex_lock(&mutex);
    state[phil_num] = THINKING;
    test((phil_num + 4) % NUM_PHILOSOPHERS);
    test((phil_num + 1) % NUM_PHILOSOPHERS);
    pthread_mutex_unlock(&mutex);
}

void test(int phil_num) {
    if (state[phil_num] == HUNGRY &&
        state[(phil_num + 4) % NUM_PHILOSOPHERS] != EATING &&
        state[(phil_num + 1) % NUM_PHILOSOPHERS] != EATING) {
        state[phil_num] = EATING;
        pthread_cond_signal(&cond[phil_num]);
    }
}

這個C語言範例使用了以下概念和技術：

1. POSIX線程（pthread）：用於創建和管理多個哲學家線程。

2. 互斥鎖（mutex）：用於保護共享資源（筷子）的訪問。

3. 條件變量（condition variables）：用於線程之間的同步和通信。

4. 狀態數組：用於跟踪每個哲學家的當前狀態（思考、飢餓或進食）。

5. 迴圈結構：每個哲學家在一個無限迴圈中交替思考和進食。

6. 隨機延遲：使用 sleep() 和 rand() 函數來模擬思考和進食的時間。

主要組件

1. 常數定義：

   • NUM_PHILOSOPHERS：哲學家的數量，這裡設定為5。
   • THINKING、HUNGRY、EATING：用來表示哲學家的狀態。

2. 全域變數：

   • pthread_mutex_t mutex：互斥鎖，用來保護共享資源。
   • pthread_cond_t cond[NUM_PHILOSOPHERS]：條件變量陣列，讓哲學家在等待時可以被喚醒。
   • int state[NUM_PHILOSOPHERS]：用來儲存每位哲學家的當前狀態。
   • int phil[NUM_PHILOSOPHERS]：儲存哲學家的編號。

主函數 main()

1. 初始化：

   • 初始化互斥鎖和條件變量。
   • 創建五個哲學家的執行緒，每個執行緒都執行 philosopher 函數。

2. 等待所有執行緒結束：

   • 使用 pthread_join 等待所有哲學家的執行緒結束。

3. 清理：

   • 銷毀互斥鎖和條件變量。

哲學家函數 philosopher()

1. 無窮迴圈：

   • 每位哲學家不斷地思考和進餐。
   • 使用 sleep 隨機延遲模擬思考和進餐的時間。

2. 獲取筷子：

   • 呼叫 take_forks() 嘗試拿起筷子（獲取資源）。

3. 進餐：

   • 獲取筷子後，進餐並隨機延遲。

4. 放下筷子：

   • 完成進餐後，呼叫 put_forks() 放下筷子。

獲取筷子的函數 take_forks()

1. 鎖定互斥鎖：

   • 確保在修改哲學家的狀態時不會有其他執行緒干擾。

2. 改變狀態：

   • 將哲學家的狀態設為 HUNGRY。(表示有意願進餐)

3. 測試是否可以進餐：

   • 呼叫 test() 函數檢查是否可以進餐。

4. 等待：

   • 如果哲學家不能進餐，則等待條件變量被喚醒。

5. 解鎖互斥鎖：

   • 釋放互斥鎖。

放下筷子的函數 put_forks()

1. 鎖定互斥鎖：

   • 確保在修改狀態時不會有其他執行緒干擾。

2. 改變狀態：

   • 將哲學家的狀態設為 THINKING。(表示無意願進餐)

3. 通知相鄰哲學家：

   • 呼叫 test() 檢查左邊和右邊的哲學家是否可以進餐。

4. 解鎖互斥鎖：

   • 釋放互斥鎖。

測試函數 test()

1. 檢查狀態：

   • 如果當前哲學家是 HUNGRY，並且左右鄰居都沒有在進餐，則可以進餐。

2. 改變狀態：

   • 將哲學家的狀態設為 EATING。

3. 喚醒哲學家：

   • 使用 pthread_cond_signal() 喚醒該哲學家。

Terminal 編譯並執行 (linux)：

gcc -o dining_philosophers dining_philosophers.c -lpthread
./dining_philosophers

這個程序會無限運行，展示哲學家們的思考和進食過程。可以通過按 Ctrl+C 來終止程序。

結果

這個實現使用了一種避免死鎖的策略，確保在任何時候至少有一個哲學家能夠進食。它通過仔細管理資源分配和狀態轉換來實現這一點。