算法设计（用信号量来解决哲学家问题）

先决条件– 流程同步, 信号量, 使用监视器的餐饮哲学家解决方案
餐饮哲学家的问题–用餐哲学家问题指出, K位哲学家坐在圆桌旁, 每对哲学家之间有一根筷子。每个哲学家之间只有一根筷子。如果一个哲学家可以拿起他旁边的两根筷子, 他可能会吃东西。一根筷子可以由其相邻的任何一个跟随者捡起, 但不能同时被两个捡起。

文章图片
餐饮哲学家的信号量解决方案–
每个哲学家都由以下伪代码表示：

process P[i] while true do{THINK; PICKUP(CHOPSTICK[i], CHOPSTICK[i+1 mod 5]); EAT; PUTDOWN(CHOPSTICK[i], CHOPSTICK[i+1 mod 5])}

哲学家有三种状态：思维, 饥饿和进食。这里有两个信号量：互斥体和哲学家的信号量数组。使用互斥量使得没有两个哲学家可以同时访问取件或取件。该数组用于控制每个哲学家的行为。但是, 由于编程错误, 信号量可能导致死锁。
代码–

#include < pthread.h> #include < semaphore.h> #include < stdio.h> #define N 5 #define THINKING 2 #define HUNGRY 1 #define EATING 0 #define LEFT (phnum + 4) % N #define RIGHT (phnum + 1) % Nint state[N]; int phil[N] = { 0, 1, 2, 3, 4 }; sem_t mutex; sem_t S[N]; void test( int phnum) { if (state[phnum] == HUNGRY & & state[LEFT] != EATING & & state[RIGHT] != EATING) { //state that eating state[phnum] = EATING; sleep(2); printf ( "Philosopher %d takes fork %d and %d\n" , phnum + 1, LEFT + 1, phnum + 1); printf ( "Philosopher %d is Eating\n" , phnum + 1); //sem_post(& S[phnum]) has no effect //during takefork //used to wake up hungry philosophers //during putfork sem_post(& S[phnum]); } }//take up chopsticks void take_fork( int phnum) {sem_wait(& mutex); //state that hungry state[phnum] = HUNGRY; printf ( "Philosopher %d is Hungry\n" , phnum + 1); //eat if neighbours are not eating test(phnum); sem_post(& mutex); //if unable to eat wait to be signalled sem_wait(& S[phnum]); sleep(1); }//put down chopsticks void put_fork( int phnum) {sem_wait(& mutex); //state that thinking state[phnum] = THINKING; printf ( "Philosopher %d putting fork %d and %d down\n" , phnum + 1, LEFT + 1, phnum + 1); printf ( "Philosopher %d is thinking\n" , phnum + 1); test(LEFT); test(RIGHT); sem_post(& mutex); }void * philospher( void * num) {while (1) {int * i = num; sleep(1); take_fork(*i); sleep(0); put_fork(*i); } }int main() {int i; pthread_t thread_id[N]; //initialize the semaphores sem_init(& mutex, 0, 1); for (i = 0; i < N; i++)sem_init(& S[i], 0, 0); for (i = 0; i < N; i++) {//create philosopher processes pthread_create(& thread_id[i], NULL, philospher, & phil[i]); printf ( "Philosopher %d is thinking\n" , i + 1); }for (i = 0; i < N; i++)pthread_join(thread_id[i], NULL); }

注意 -下面的程序只能使用带有信号灯和pthread库的C编译器进行编译。
参考–
餐饮哲学家的解决方案– cs.gordon.edu
【算法设计（用信号量来解决哲学家问题）】餐饮哲学家的解决方案– cs.indiana.edu