哲學家進餐問題

哲學家進餐問題是一個經(jīng)典的同步問題，涉及多個哲學家試圖同時用餐，但每個哲學家左右兩邊只有一把叉子。為了避免死鎖和饑餓，可以使用記錄型信號量（也稱為計數(shù)信號量）來管理叉子的使用。

1、利用記錄型信號量解決哲學家進餐問題

（1）信號量初始化：使用?sem_init?初始化每把叉子的信號量，初始值為1，表示可用。

哲學家線程：每個哲學家線程嘗試拿起左邊的叉子（sem_trywait），如果失敗則繼續(xù)思考。如果成功拿起左邊的叉子，再嘗試拿起右邊的叉子。如果失敗，則放下左邊的叉子并繼續(xù)思考。如果成功拿起兩把叉子，則哲學家開始吃飯，吃完后放下兩把叉子。

輸出控制：使用互斥鎖?print_mutex?控制輸出順序，避免輸出混亂。

線程創(chuàng)建和等待：創(chuàng)建哲學家線程，并使用?pthread_join?等待所有線程完成（實際上這是一個無限循環(huán)程序，所以不會真正退出）。

資源清理：銷毀信號量和互斥鎖。

#include <stdio.h>  
#include <stdlib.h>  
#include <pthread.h>  
#include <semaphore.h>  
#include <unistd.h>  #define NUM_PHILOSOPHERS 5  
#define THINK_TIME 1  
#define EAT_TIME 2  sem_t forks[NUM_PHILOSOPHERS];  // 每把叉子一個信號量  
pthread_mutex_t print_mutex;    // 控制輸出順序的互斥鎖  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(THINK_TIME);  // 嘗試拿起左邊的叉子  if (sem_trywait(&forks[left_fork]) == -1) {  // 拿起左邊的叉子失敗，繼續(xù)思考  continue;  }  // 嘗試拿起右邊的叉子  if (sem_trywait(&forks[right_fork]) == -1) {  // 拿起右邊的叉子失敗，放下左邊的叉子并繼續(xù)思考  sem_post(&forks[left_fork]);  continue;  }  // 拿起兩把叉子，開始吃飯  printf("Philosopher %d is eating.\n", id);  sleep(EAT_TIME);  printf("Philosopher %d has finished eating.\n", id);  // 放下叉子  sem_post(&forks[left_fork]);  sem_post(&forks[right_fork]);  }  pthread_exit(NULL);  
}  int main() {  pthread_t threads[NUM_PHILOSOPHERS];  int ids[NUM_PHILOSOPHERS];  // 初始化信號量，每把叉子的初始值為1，表示可用  for (int i = 0; i < NUM_PHILOSOPHERS; i++) {  sem_init(&forks[i], 0, 1);  }  // 初始化互斥鎖，用于控制輸出順序  pthread_mutex_init(&print_mutex, NULL);  // 創(chuàng)建哲學家線程  for (int i = 0; i < NUM_PHILOSOPHERS; i++) {  ids[i] = i;  pthread_create(&threads[i], NULL, philosopher, &ids[i]);  }  // 等待所有線程完成（實際上，這是一個無限循環(huán)程序，所以這里不會退出）  for (int i = 0; i < NUM_PHILOSOPHERS; i++) {  pthread_join(threads[i], NULL);  }  // 銷毀信號量和互斥鎖  for (int i = 0; i < NUM_PHILOSOPHERS; i++) {  sem_destroy(&forks[i]);  }  pthread_mutex_destroy(&print_mutex);  return 0;  
}

注意：

• sem_trywait?是非阻塞的，如果信號量的值大于0，則減一并返回，否則立即返回-1并設置errno為EAGAIN。
• 使用?pthread_join?等待線程實際上在這個例子中是不必要的，因為哲學家線程是無限循環(huán)的。如果要終止程序，可以添加額外的控制邏輯。

（2）init_random()：初始化隨機數(shù)生成器。

think(int philosopherNumber)：模擬哲學家思考的過程，打印消息并隨機睡眠一段時間。

eat(int philosopherNumber)：模擬哲學家吃飯的過程，打印消息并隨機睡眠一段時間。

*philosopher(void *arg)：哲學家的線程函數(shù)，包含無限循環(huán)，不斷執(zhí)行思考和吃飯的過程。在拿起叉子前使用互斥鎖保護，成功后釋放互斥鎖，吃飯后放下叉子。

#include <stdio.h>  
#include <stdlib.h>  
#include <pthread.h>  
#include <semaphore.h>  
#include <unistd.h> // 包含sleep函數(shù)所需的頭文件  
#include <time.h>  #define PHILOSOPHERS_COUNT 5  sem_t forks[PHILOSOPHERS_COUNT];  
sem_t mutex;  // 初始化隨機數(shù)生成器  
void init_random() {  srand(time(NULL));  
}  void think(int philosopherNumber) {  printf("Philosopher %d is thinking.\n", philosopherNumber);  // 模擬思考時間  int sleepTime = rand() % 5 + 1;  sleep(sleepTime);  
}  void eat(int philosopherNumber) {  printf("Philosopher %d is eating.\n", philosopherNumber);  // 模擬吃飯時間  int sleepTime = rand() % 5 + 1;  sleep(sleepTime);  
}  void *philosopher(void *arg) {  int philosopherNumber = *((int *)arg);  while (1) { // 注意：這里的無限循環(huán)可能導致程序永遠不退出  think(philosopherNumber);  // 使用互斥鎖保護對叉子的訪問  sem_wait(&mutex);  // 嘗試拿起左右兩邊的叉子  int leftFork = philosopherNumber;  int rightFork = (philosopherNumber + 1) % PHILOSOPHERS_COUNT;  sem_wait(&forks[leftFork]);  sem_wait(&forks[rightFork]);  // 釋放互斥鎖，因為已經(jīng)成功拿起了兩把叉子  sem_post(&mutex);  eat(philosopherNumber);  // 放下叉子  sem_post(&forks[leftFork]);  sem_post(&forks[rightFork]);  }  return NULL;  
}  int main() {  pthread_t philosophers[PHILOSOPHERS_COUNT];  int philosopherNumbers[PHILOSOPHERS_COUNT];  // 初始化隨機數(shù)生成器  init_random();  // 初始化信號量  sem_init(&mutex, 0, 1);  for (int i = 0; i < PHILOSOPHERS_COUNT; i++) {  sem_init(&forks[i], 0, 1);  }  // 創(chuàng)建哲學家線程  for (int i = 0; i < PHILOSOPHERS_COUNT; i++) {  philosopherNumbers[i] = i;  pthread_create(&philosophers[i], NULL, philosopher, &philosopherNumbers[i]);  }  // 注意：這里使用pthread_join會導致程序永遠等待，因為哲學家線程是無限循環(huán)的  // 如果需要程序退出，應該實現(xiàn)某種退出機制，比如使用全局變量和條件變量  for (int i = 0; i < PHILOSOPHERS_COUNT; i++) {  pthread_join(philosophers[i], NULL);  }  // 清理資源（在實際應用中，應該在確保所有線程都正確退出后再進行）  for (int i = 0; i < PHILOSOPHERS_COUNT; i++) {  sem_destroy(&forks[i]);  }  sem_destroy(&mutex);  // 注意：由于使用了無限循環(huán)，下面的代碼將不會被執(zhí)行  // 這里只是為了展示如何清理資源  // 在實際應用中，應在程序退出前確保所有線程都正確終止  return 0;  
}

注意：由于while (1)循環(huán)的存在，pthread_join和信號量銷毀的代碼在實際應用中不會被執(zhí)行。在實際應用中，您需要實現(xiàn)一種機制來安全地終止線程并清理資源。這通常涉及到使用全局變量、條件變量或其他線程間通信機制來協(xié)調線程的終止。?

2、利用AND信號量機制解決哲學家進餐問題

（1）AND信號量要求線程（在本例中為哲學家）同時獲取多個資源（叉子）才能繼續(xù)執(zhí)行。然而，標準的POSIX信號量API并不直接支持AND信號量，但我們可以通過使用互斥鎖（mutex）和計數(shù)信號量（counting semaphore）的組合來模擬這種機制。

#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#include <semaphore.h>
#include <unistd.h>
#include <stdbool.h>
#include <time.h>#define PHILOSOPHERS_COUNT 5
#define THINK_TIME 1 // 思考時間（秒）
#define EAT_TIME 1  // 吃飯時間（秒）sem_t forks[PHILOSOPHERS_COUNT]; // 每只叉子一個信號量
pthread_mutex_t mutex;          // 互斥鎖，用于保護對退出標志的訪問
bool should_exit = false;        // 退出標志// 初始化隨機數(shù)生成器（雖然在這個示例中未直接使用 rand，但保留以備將來需要）
void init_random() {srand(time(NULL));
}// 哲學家線程函數(shù)
void *philosopher(void *arg) {int philosopher_number = *((int *)arg);while (!should_exit || /* 另一個條件，用于確保在退出前完成當前循環(huán) */(should_exit && (philosopher_number % 2 == 0 || /* 可選的：讓偶數(shù)編號的哲學家先完成 */(sem_trywait(&forks[philosopher_number]) == 0 && sem_trywait(&forks[(philosopher_number + 1) % PHILOSOPHERS_COUNT]) == 0)))) {// 思考printf("Philosopher %d is thinking.\n", philosopher_number);sleep(THINK_TIME);// 嘗試拿起左右兩邊的叉子（模擬 AND 信號量）pthread_mutex_lock(&mutex); // 保護對叉子信號量的操作if (sem_trywait(&forks[philosopher_number]) == 0 &&sem_trywait(&forks[(philosopher_number + 1) % PHILOSOPHERS_COUNT]) == 0) {// 成功拿起兩把叉子pthread_mutex_unlock(&mutex); // 釋放互斥鎖，因為已經(jīng)成功拿起了叉子// 吃飯printf("Philosopher %d is eating.\n", philosopher_number);sleep(EAT_TIME);// 放下叉子sem_post(&forks[philosopher_number]);sem_post(&forks[(philosopher_number + 1) % PHILOSOPHERS_COUNT]);} else {// 未能同時拿起兩把叉子，釋放互斥鎖并繼續(xù)思考pthread_mutex_unlock(&mutex);}// 檢查退出標志pthread_mutex_lock(&mutex);if (should_exit) {pthread_mutex_unlock(&mutex);break; // 直接跳出循環(huán)}pthread_mutex_unlock(&mutex);}return NULL;
}int main() {pthread_t philosophers[PHILOSOPHERS_COUNT];int philosopher_numbers[PHILOSOPHERS_COUNT];// 初始化隨機數(shù)生成器（雖然在這個示例中未直接使用）init_random();// 初始化信號量和互斥鎖pthread_mutex_init(&mutex, NULL);for (int i = 0; i < PHILOSOPHERS_COUNT; i++) {sem_init(&forks[i], 0, 1); // 初始值為 1，表示叉子可用}// 創(chuàng)建哲學家線程for (int i = 0; i < PHILOSOPHERS_COUNT; i++) {philosopher_numbers[i] = i;pthread_create(&philosophers[i], NULL, philosopher, &philosopher_numbers[i]);}// 讓哲學家們運行一段時間，然后設置退出標志sleep(10); // 這里只是為了演示，實際中可能使用其他條件來觸發(fā)退出pthread_mutex_lock(&mutex);should_exit = true;pthread_mutex_unlock(&mutex);// 等待哲學家線程退出for (int i = 0; i < PHILOSOPHERS_COUNT; i++) {pthread_join(philosophers[i], NULL);}// 清理資源for (int i = 0; i < PHILOSOPHERS_COUNT; i++) {sem_destroy(&forks[i]);}pthread_mutex_destroy(&mutex);return 0;
}

（2）sem_t mutex;：用于保護對共享資源（如state數(shù)組和meals_eaten數(shù)組）的訪問。

sem_t s[N];：表示左右叉子的可用性。如果s[i]為0，則第i位哲學家的右叉子（或第(i-1)%N位哲學家的左叉子）不可用。

sem_t s_try[N];：用于在哲學家嘗試獲取叉子時同步。

int state[N];：表示每位哲學家的當前狀態(tài)（思考、饑餓、就餐）。

int meals_eaten[N];：記錄每位哲學家吃過的飯的數(shù)量。

pthread_cond_t cond[N];：條件變量，用于在哲學家無法獲取叉子時等待

#include <stdio.h>
#include <pthread.h>
#include <semaphore.h>
#include <unistd.h>
#include <stdbool.h>#define N 5
#define THINKING 0
#define HUNGRY 1
#define EATING 2
#define MAX_MEALS 10 sem_t mutex;
sem_t s[N];
sem_t s_try[N];
int state[N];
int meals_eaten[N];pthread_cond_t cond[N];void *philosopher(void *num);
void take_forks(int);
void put_forks(int);
void test(int);void debug_print(int philosopher_num, const char *message) {printf("Philosopher %d: %s\n", philosopher_num, message);
}int main() {pthread_t thread_id[N];sem_init(&mutex, 0, 1);for (int i = 0; i < N; i++) {sem_init(&s[i], 0, 0);sem_init(&s_try[i], 0, 0);meals_eaten[i] = 0;pthread_cond_init(&cond[i], NULL);}for (int i = 0; i < N; i++) {pthread_create(&thread_id[i], NULL, philosopher, (void *)(long long)i);}for (int i = 0; i < N; i++) {pthread_join(thread_id[i], NULL);}return 0;
}void *philosopher(void *num) {long long int i = (long long int)(num);for (int meal = 0; meal < MAX_MEALS; meal++) {// 思考{sem_wait(&mutex);state[i] = THINKING;sem_post(&mutex);debug_print(i, "Thinking");}// 嘗試獲取叉子take_forks((int)i);// 吃飯{sem_wait(&mutex);state[i] = EATING;sem_post(&mutex);debug_print(i, "Eating");}// 放下叉子put_forks((int)i);}return NULL;
}void take_forks(int i) {sem_wait(&mutex);state[i] = HUNGRY;debug_print(i, "Hungry");test(i);if (state[i]!= EATING) {pthread_cond_wait(&cond[i], &mutex);}sem_post(&mutex);sem_wait(&s_try[i]);sem_wait(&s[i]);
}void put_forks(int i) {sem_wait(&mutex);state[i] = THINKING;debug_print(i, "Put down forks");meals_eaten[i]++;test((i + 4) % N);test((i + 1) % N);sem_post(&mutex);sem_post(&s[(i + 4) % N]);sem_post(&s[(i + 1) % N]);pthread_cond_signal(&cond[(i + 4) % N]);pthread_cond_signal(&cond[(i + 1) % N]);
}void test(int i) {sem_wait(&mutex);if (state[i] == HUNGRY && state[(i + 4) % N]!= EATING && state[(i + 1) % N]!= EATING) {state[i] = EATING;sem_post(&s_try[i]);sem_post(&s[i]);pthread_cond_signal(&cond[i]);}sem_post(&mutex);
}

注意：

• 代碼中使用了信號量和條件變量來同步對共享資源的訪問，以避免競態(tài)條件和死鎖。
• 通過mutex信號量保護對state數(shù)組的訪問，確保在檢查和修改哲學家狀態(tài)時不會發(fā)生數(shù)據(jù)競爭。
• 通過s[i]和s_try[i]信號量以及條件變量cond[i]來協(xié)調哲學家獲取和釋放叉子的過程。
• 代碼中的% N操作確保了索引在有效范圍內(nèi)循環(huán)。