哲学家就餐问题

问题

在一个圆桌上坐着五位哲学家，每个哲学家面前有一个碗装有米饭的碗和一个筷子。哲学家的生活包括思考和进餐两个活动。当一个哲学家思考时，他不需要任何资源。当他饿了时，他试图拿起两只相邻的筷子来吃饭。由于碗和筷子不能被共享，因此必须找到一种方法来确保哲学家能够安全地进餐，即不会发生死锁（所有哲学家都在等待筷子）也不会发生饥饿（某些哲学家永远无法拿起筷子）

信号量实现

发生死锁版

#include <pthread.h>
#include <semaphore.h>
#include <vector>
#include <unistd.h>
#include <iostream>#define N 5
#define P(x) sem_wait(x)
#define V(x) sem_post(x)sem_t mutex_table;
std::vector<sem_t> mutex_chopsticks(N);void* T_philosopher(void* arg) {int id = *((int*)arg);// id哲学家吃饭需要的2根筷子int lhs = (id + N - 1) % N;int rhs = id % N;while (true) {P(&mutex_chopsticks[lhs]);printf("+ %d by T%d\n", lhs, id);P(&mutex_chopsticks[rhs]);printf("+ %d by T%d\n", rhs, id);// Eat.// Philosophers are allowed to eat in parallel.printf("- %d by T%d\n", lhs, id);printf("- %d by T%d\n", rhs, id);V(&mutex_chopsticks[lhs]);V(&mutex_chopsticks[rhs]);sleep(0.5);}
}int main() {for (int i = 0; i < N; i++) {sem_init(&mutex_chopsticks[i], 0, 1);}std::vector<pthread_t> threads(N);std::vector<int> ids(N);for (int i = 0; i < N; i++) {ids[i] = i + 1;pthread_create(&threads[i], nullptr, &T_philosopher, &ids[i]);}for (int i = 0; i < N; i++) {pthread_join(threads[i], nullptr);}
}

限制人数版

限制最多只能4人同时上桌, 则可以保证至少有一个人可以同时拿起两根筷子

#include <pthread.h>
#include <semaphore.h>
#include <vector>
#include <unistd.h>
#include <iostream>#define P(x) sem_wait(x)
#define V(x) sem_post(x)const int N = 5;sem_t mutex_table;
std::vector<sem_t> mutex_chopsticks(N);void* T_philosopher(void* arg) {int id = *((int*)arg);// id哲学家吃饭需要的2根筷子int lhs = (id + N - 1) % N;int rhs = id % N;while (true) {// Come to mutex_tableP(&mutex_table);P(&mutex_chopsticks[lhs]);printf("+ %d by T%d\n", lhs, id);P(&mutex_chopsticks[rhs]);printf("+ %d by T%d\n", rhs, id);// Eating// Philosophers are allowed to eat in parallel.printf("- %d by T%d\n", lhs, id);printf("- %d by T%d\n", rhs, id);V(&mutex_chopsticks[lhs]);V(&mutex_chopsticks[rhs]);// Leave mutex_tableV(&mutex_table);// Thinkingsleep(0.5);}
}int main() {// 保证任何实际最多只有4个人在桌子上// 这样至少有1个人可以拿到2根筷子sem_init(&mutex_table, 0, N - 1);for (int i = 0; i < N; i++) {sem_init(&mutex_chopsticks[i], 0, 1);}std::vector<pthread_t> threads(N);std::vector<int> ids(N);for (int i = 0; i < N; i++) {ids[i] = i + 1;pthread_create(&threads[i], nullptr, &T_philosopher, &ids[i]);}for (int i = 0; i < N; i++) {pthread_join(threads[i], nullptr);}
}

规定取筷顺序

规定每个人, 先拿编号小的筷子, 再拿编号大的筷子

#include <pthread.h>
#include <semaphore.h>
#include <vector>
#include <unistd.h>
#include <iostream>#define P(x) sem_wait(x)
#define V(x) sem_post(x)const int N = 5;sem_t mutex_table;
std::vector<sem_t> mutex_chopsticks(N);void* T_philosopher(void* arg) {int id = *((int*)arg);// id哲学家吃饭需要的2根筷子int lhs = (id + N - 1) % N;int rhs = id % N;while (true) {// 规定每个人, 先拿编号小的筷子, 再拿编号大的筷子if (lhs < rhs) {P(&mutex_chopsticks[lhs]);P(&mutex_chopsticks[rhs]);} else {P(&mutex_chopsticks[rhs]);P(&mutex_chopsticks[lhs]);}printf("+ %d by T%d\n", lhs, id);printf("+ %d by T%d\n", rhs, id);// Eatingprintf("- %d by T%d\n", lhs, id);printf("- %d by T%d\n", rhs, id);V(&mutex_chopsticks[lhs]);V(&mutex_chopsticks[rhs]);// Thinkingsleep(0.5);}
}int main() {for (int i = 0; i < N; i++) {sem_init(&mutex_chopsticks[i], 0, 1);}std::vector<pthread_t> threads(N);std::vector<int> ids(N);for (int i = 0; i < N; i++) {ids[i] = i + 1;pthread_create(&threads[i], nullptr, &T_philosopher, &ids[i]);}for (int i = 0; i < N; i++) {pthread_join(threads[i], nullptr);}
}

条件变量实现

#include <pthread.h>
#include <vector>
#include <unistd.h>
#include <iostream>#define Lock(x) pthread_mutex_lock(x)
#define UnLock(x) pthread_mutex_unlock(x)const int N = 5;pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;
pthread_cond_t cond = PTHREAD_COND_INITIALIZER;
std::vector<int> available(N, true);void* T_philosopher(void* arg) {int id = *((int*)arg);// id哲学家吃饭需要的2根筷子int lhs = (id + N - 1) % N;int rhs = id % N;while (true) {// Come to mutex_tableLock(&mutex);while (!(available[lhs] && available[rhs])) {pthread_cond_wait(&cond, &mutex);}printf("+ %d by T%d\n", lhs, id);printf("+ %d by T%d\n", rhs, id);available[lhs] = available[rhs] = false;UnLock(&mutex);// Eatingsleep(0.5);printf("- %d by T%d\n", lhs, id);printf("- %d by T%d\n", rhs, id);available[lhs] = available[rhs] = true;pthread_cond_broadcast(&cond);// Thinkingsleep(0.5);}
}int main() {std::vector<pthread_t> threads(N);std::vector<int> ids(N);for (int i = 0; i < N; i++) {ids[i] = i + 1;pthread_create(&threads[i], nullptr, &T_philosopher, &ids[i]);}for (int i = 0; i < N; i++) {pthread_join(threads[i], nullptr);}
}