问题
在一个圆桌上坐着五位哲学家,每个哲学家面前有一个碗装有米饭的碗和一个筷子。哲学家的生活包括思考和进餐两个活动。当一个哲学家思考时,他不需要任何资源。当他饿了时,他试图拿起两只相邻的筷子来吃饭。由于碗和筷子不能被共享,因此必须找到一种方法来确保哲学家能够安全地进餐,即不会发生死锁(所有哲学家都在等待筷子)也不会发生饥饿(某些哲学家永远无法拿起筷子)
信号量实现
发生死锁版
#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_table
P(&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_table
V(&mutex_table);
// Thinking
sleep(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);
// Eating
printf("- %d by T%d\n", lhs, id);
printf("- %d by T%d\n", rhs, id);
V(&mutex_chopsticks[lhs]);
V(&mutex_chopsticks[rhs]);
// Thinking
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);
}
}
条件变量实现
#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_table
Lock(&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);
// Eating
sleep(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);
// Thinking
sleep(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);
}
}