当前位置：首页 > news >正文

C语言实现操作系统经典的进程同步问题（2）

news 2025/8/3 2:26:02

哲学家进餐问题

哲学家进餐问题是一个经典的同步问题，涉及多个哲学家试图同时用餐，但每个哲学家左右两边只有一把叉子。为了避免死锁和饥饿，可以使用记录型信号量（也称为计数信号量）来管理叉子的使用。

1、利用记录型信号量解决哲学家进餐问题

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

哲学家线程：每个哲学家线程尝试拿起左边的叉子（sem_trywait），如果失败则继续思考。如果成功拿起左边的叉子，再尝试拿起右边的叉子。如果失败，则放下左边的叉子并继续思考。如果成功拿起两把叉子，则哲学家开始吃饭，吃完后放下两把叉子。

输出控制：使用互斥锁 print_mutex 控制输出顺序，避免输出混乱。

线程创建和等待：创建哲学家线程，并使用 pthread_join 等待所有线程完成（实际上这是一个无限循环程序，所以不会真正退出）。

资源清理：销毁信号量和互斥锁。

#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) {  // 拿起左边的叉子失败，继续思考  continue;  }  // 尝试拿起右边的叉子  if (sem_trywait(&forks[right_fork]) == -1) {  // 拿起右边的叉子失败，放下左边的叉子并继续思考  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);  // 创建哲学家线程  for (int i = 0; i < NUM_PHILOSOPHERS; i++) {  ids[i] = i;  pthread_create(&threads[i], NULL, philosopher, &ids[i]);  }  // 等待所有线程完成（实际上，这是一个无限循环程序，所以这里不会退出）  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 等待线程实际上在这个例子中是不必要的，因为哲学家线程是无限循环的。如果要终止程序，可以添加额外的控制逻辑。

（2）init_random()：初始化随机数生成器。

think(int philosopherNumber)：模拟哲学家思考的过程，打印消息并随机睡眠一段时间。

eat(int philosopherNumber)：模拟哲学家吃饭的过程，打印消息并随机睡眠一段时间。

*philosopher(void *arg)：哲学家的线程函数，包含无限循环，不断执行思考和吃饭的过程。在拿起叉子前使用互斥锁保护，成功后释放互斥锁，吃饭后放下叉子。

#include <stdio.h>  
#include <stdlib.h>  
#include <pthread.h>  
#include <semaphore.h>  
#include <unistd.h> // 包含sleep函数所需的头文件  
#include <time.h>  #define PHILOSOPHERS_COUNT 5  sem_t forks[PHILOSOPHERS_COUNT];  
sem_t mutex;  // 初始化随机数生成器  
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) { // 注意：这里的无限循环可能导致程序永远不退出  think(philosopherNumber);  // 使用互斥锁保护对叉子的访问  sem_wait(&mutex);  // 尝试拿起左右两边的叉子  int leftFork = philosopherNumber;  int rightFork = (philosopherNumber + 1) % PHILOSOPHERS_COUNT;  sem_wait(&forks[leftFork]);  sem_wait(&forks[rightFork]);  // 释放互斥锁，因为已经成功拿起了两把叉子  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];  // 初始化随机数生成器  init_random();  // 初始化信号量  sem_init(&mutex, 0, 1);  for (int i = 0; i < PHILOSOPHERS_COUNT; i++) {  sem_init(&forks[i], 0, 1);  }  // 创建哲学家线程  for (int i = 0; i < PHILOSOPHERS_COUNT; i++) {  philosopherNumbers[i] = i;  pthread_create(&philosophers[i], NULL, philosopher, &philosopherNumbers[i]);  }  // 注意：这里使用pthread_join会导致程序永远等待，因为哲学家线程是无限循环的  // 如果需要程序退出，应该实现某种退出机制，比如使用全局变量和条件变量  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);  // 注意：由于使用了无限循环，下面的代码将不会被执行  // 这里只是为了展示如何清理资源  // 在实际应用中，应在程序退出前确保所有线程都正确终止  return 0;  
}

注意：由于while (1)循环的存在，pthread_join和信号量销毁的代码在实际应用中不会被执行。在实际应用中，您需要实现一种机制来安全地终止线程并清理资源。这通常涉及到使用全局变量、条件变量或其他线程间通信机制来协调线程的终止。

2、利用AND信号量机制解决哲学家进餐问题

（1）AND信号量要求线程（在本例中为哲学家）同时获取多个资源（叉子）才能继续执行。然而，标准的POSIX信号量API并不直接支持AND信号量，但我们可以通过使用互斥锁（mutex）和计数信号量（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;        // 退出标志// 初始化随机数生成器（虽然在这个示例中未直接使用 rand，但保留以备将来需要）
void init_random() {srand(time(NULL));
}// 哲学家线程函数
void *philosopher(void *arg) {int philosopher_number = *((int *)arg);while (!should_exit || /* 另一个条件，用于确保在退出前完成当前循环 */(should_exit && (philosopher_number % 2 == 0 || /* 可选的：让偶数编号的哲学家先完成 */(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); // 释放互斥锁，因为已经成功拿起了叉子// 吃饭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 {// 未能同时拿起两把叉子，释放互斥锁并继续思考pthread_mutex_unlock(&mutex);}// 检查退出标志pthread_mutex_lock(&mutex);if (should_exit) {pthread_mutex_unlock(&mutex);break; // 直接跳出循环}pthread_mutex_unlock(&mutex);}return NULL;
}int main() {pthread_t philosophers[PHILOSOPHERS_COUNT];int philosopher_numbers[PHILOSOPHERS_COUNT];// 初始化随机数生成器（虽然在这个示例中未直接使用）init_random();// 初始化信号量和互斥锁pthread_mutex_init(&mutex, NULL);for (int i = 0; i < PHILOSOPHERS_COUNT; i++) {sem_init(&forks[i], 0, 1); // 初始值为 1，表示叉子可用}// 创建哲学家线程for (int i = 0; i < PHILOSOPHERS_COUNT; i++) {philosopher_numbers[i] = i;pthread_create(&philosophers[i], NULL, philosopher, &philosopher_numbers[i]);}// 让哲学家们运行一段时间，然后设置退出标志sleep(10); // 这里只是为了演示，实际中可能使用其他条件来触发退出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数组和meals_eaten数组）的访问。

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

sem_t s_try[N];：用于在哲学家尝试获取叉子时同步。

int state[N];：表示每位哲学家的当前状态（思考、饥饿、就餐）。

int meals_eaten[N];：记录每位哲学家吃过的饭的数量。

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);
}