网站部分网页乱码,苏州网站的优化,页面设计在线,长沙哪里有创建网站的公司哲学家进餐问题
哲学家进餐问题是一个经典的同步问题#xff0c;涉及多个哲学家试图同时用餐#xff0c;但每个哲学家左右两边只有一把叉子。为了避免死锁和饥饿#xff0c;可以使用记录型信号量#xff08;也称为计数信号量#xff09;来管理叉子的使用。
1、利用记录型…哲学家进餐问题
哲学家进餐问题是一个经典的同步问题涉及多个哲学家试图同时用餐但每个哲学家左右两边只有一把叉子。为了避免死锁和饥饿可以使用记录型信号量也称为计数信号量来管理叉子的使用。
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 等待线程实际上在这个例子中是不必要的因为哲学家线程是无限循环的。如果要终止程序可以添加额外的控制逻辑。
2init_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信号量机制解决哲学家进餐问题
1AND信号量要求线程在本例中为哲学家同时获取多个资源叉子才能继续执行。然而标准的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;
}
2sem_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操作确保了索引在有效范围内循环。
