线程同步经典问题之哲学家就餐问题

问题描述
由Dijkstra提出并解决的哲学家就餐问题是典型的同步问题。该问题描述的是五个哲学家共用一张圆桌，分别坐在周围的五张椅子上，在圆桌上有五个碗和五只筷子，他们的生活方式是交替的进行思考和进餐。平时，一个哲学家进行思考，饥饿时便试图取用其左右最靠近他的筷子，只有在他拿到两只筷子时才能进餐。进餐完毕，放下筷子继续思考。

用信号量解法：
每只筷子都用一个信号量来表示，一个哲学家通过执行wait()试图获取左边和右边的筷子，它会通过signal()释放筷子。因此：

semaphore  chopstick[5] = {1,1,1,1,1}

// 第i个哲学家的伪码表示为：
while (true) {
     wait(chopstick[i])；
     wait(chopstick[(i+1)%5]);
       // eating
      signal(chopstick[(i+1)%5]);
      signal(chopstick[i]);
}

虽然这一解决方案保证两个邻居不能同时进食，但是它可能导致死锁，因此还是应被拒绝的。假若所有 5 个哲学家同时饥饿并拿起左边的筷子。所有筷子的信号量现在均为 0。当每个哲学家试图拿右边的筷子时，他会被永远推迟。

死锁问题有多种可能的补救措施：

• 允许最多 4 个哲学家同时坐在桌子上。
• 只有一个哲学家的两根筷子都可用时，他才能拿起它们（他必须在临界区内拿起两根 辕子)。
• 使用非对称解决方案。即单号的哲学家先拿起左边的筷子，接着右边的筷子；而双 号的哲学家先拿起右边的筷子，接着左边的筷子。

用互斥量实现哲学家就餐问题

#include<sys/types.h>
#include<unistd.h>
#include<stdlib.h>
#include<stdio.h>
#include<pthread.h>
#include<semaphore.h>
#include<time.h>
#define N 5     //哲学家数量

#define LEFT(i)    (i+N-1)%N  //左手边哲学家编号
#define RIGHT(i)   (i+1)%N    //右手边哲家编号

#define HUNGRY    0     //饥饿
#define THINKING  1     //思考
#define EATING    2     //吃饭

#define U_SECOND 1000000   //1秒对应的微秒数
pthread_mutex_t mutex;     //互斥量

int state[N];  //记录每个哲学家状态
//每个哲学家的思考时间，吃饭时间，思考开始时间，吃饭开始时间
clock_t thinking_time[N], eating_time[N], start_eating_time[N],
        start_thinking_time[N];
// 线程函数
void *thread_function(void *arg);

int main(int argc,char* argv[]) {
  pthread_mutex_init(&mutex, NULL);

  pthread_t a,b,c,d,e;
  //为每一个哲学家开启一个线程，传递哲学家编号
  const char* ch0 = "0";
  const char* ch1 = "1";
  const char* ch2 = "2";
  const char* ch3 = "3";
  const char* ch4 = "4";
  pthread_create(&a,NULL,thread_function, (void*)ch0);
  pthread_create(&b,NULL,thread_function, (void*)ch1);
  pthread_create(&c,NULL,thread_function, (void*)ch2);
  pthread_create(&d,NULL,thread_function, (void*)ch3);
  pthread_create(&e,NULL,thread_function, (void*)ch4);

  //初始化随机数种子
  srand((unsigned int)(time(NULL)));

  while(true) {
    ;
  }
}

void* thread_function(void*arg) {
  char *a = (char *)arg;
  int num = a[0] -'0';
  //根据传递参数获取哲学家编号
  int rand_time;
  while(1) {
    //关键代码加锁
    pthread_mutex_lock(&mutex);
    //如果该哲学家处于饥饿  并且左右两位哲学家都没有在吃饭 就拿起叉子吃饭
    if(state[num] == HUNGRY &&
       state[LEFT(num)] != EATING &&
       state[RIGHT(num)] != EATING) {
      state[num] = EATING;
      //记录开始吃饭时间
      start_eating_time[num] = clock();
      //随机生成吃饭时间
      eating_time[num] = (rand() % 5) * U_SECOND;
      //输出状态
      printf("state: %d %d %d %d %d\n",state[0],state[1],state[2],state[3],state[4]);
      printf("%d is eating\n",num);
    } else if(state[num] == EATING) {
      //吃饭时间已到 ，开始思考
      if(clock() - start_eating_time[num] >= eating_time[num]) {
        state[num] = THINKING;
        printf("state: %d %d %d %d %d\n",state[0],state[1],state[2],state[3],state[4]);
        printf("%d is thinking\n",num);
        //记录开始思考时间
        start_thinking_time[num] = clock();
        //随机生成思考时间
        thinking_time[num] = (rand() % 10 + 10) * U_SECOND;
      }
    } else if(state[num] == THINKING) {
      //思考一定时间后，哲学家饿了，需要吃饭
      if(clock() - start_thinking_time[num] >= thinking_time[num]) {
        state[num] = HUNGRY;
        printf("state: %d %d %d %d %d\n",state[0],state[1],state[2],state[3],state[4]);
        printf("%d is hungry\n",num);
      }
    }
    pthread_mutex_unlock(&mutex);
  }
}