哲学家进餐问题
哲学家进餐问题是一个经典的同步问题,涉及多个哲学家试图同时用餐,但每个哲学家左右两边只有一把叉子。为了避免死锁和饥饿,可以使用记录型信号量(也称为计数信号量)来管理叉子的使用。
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);
}
注意:
- 代码中使用了信号量和条件变量来同步对共享资源的访问,以避免竞态条件和死锁。
- 通过
mutex
信号量保护对state
数组的访问,确保在检查和修改哲学家状态时不会发生数据竞争。 - 通过
s[i]
和s_try[i]
信号量以及条件变量cond[i]
来协调哲学家获取和释放叉子的过程。 - 代码中的
% N
操作确保了索引在有效范围内循环。