pthreads (9) 食事をする哲学者の問題

PTH

食事をする哲学者の問題(Dining philosophers problem)という、デッドロックの有名な話があります。

http://msugai.fc2web.com/java/thread/diningPh.html

これをpthreadsで作ってみました。

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <pthread.h>

#define NFORK 5
#define NPHILOSOPHER 5

void act(int *);
void think(void);
void eat(int);

pthread_mutex_t mutex[NFORK];
int thinkmsec=0, eatmsec=0;

int main(int argc, char **argv){
     pthread_t philosopher[NPHILOSOPHER];
     int i;
     
     thinkmsec = atoi(argv[1]);
     eatmsec   = atoi(argv[2]);
     for(i=0; i<NFORK; i++){
          pthread_mutex_init(&mutex[i], NULL);
     }
     for(i=0; i<NPHILOSOPHER; i++){
          pthread_create(&philosopher[i], NULL, (void *)act, &i);
     }
     for(i=0; i<NPHILOSOPHER; i++){
          pthread_join(philosopher[i], NULL);
     }
     return 0;
}

void act(int *p)
{
     int id = *p;
     while(1){
          printf("philosopher %d is thinking.\n", id);
          think();
          printf("philosopher %d is hungry.\n", id);
          eat(id);
     }
}
void think(void)
{
     usleep(thinkmsec * 1000);
}
void eat(int id)
{
     int left=(id+1)%NFORK, right=id;

     pthread_mutex_lock(&mutex[left]);
     printf("philosopher %d gets a left fork %d.\n", id, left);
     usleep(1000000);
     pthread_mutex_lock(&mutex[right]);
     printf("philosopher %d gets a right fork %d.\n", id, right);
     printf("philosopher %d is eating.\n", id);
     usleep(eatmsec * 1000);
     pthread_mutex_unlock(&mutex[right]);
     printf("philosopher %d puts down a right fork %d.\n", id, right);
     pthread_mutex_unlock(&mutex[left]);
     printf("philosopher %d puts down a left fork %d.\n", id, left);
}
philosopher 0 is thinking.
philosopher 1 is thinking.
philosopher 2 is thinking.
philosopher 3 is thinking.
philosopher 4 is thinking.
philosopher 0 is hungry.
philosopher 0 gets a left fork 1.
philosopher 1 is hungry.
philosopher 1 gets a left fork 2.
philosopher 2 is hungry.
philosopher 2 gets a left fork 3.
philosopher 3 is hungry.
philosopher 3 gets a left fork 4.
philosopher 4 is hungry.
philosopher 4 gets a left fork 0.

左手のフォークを取った後にsleepを入れると、全員が左手のフォークをロックした状態でデッドロックが発生してしまいます。それにしても、きれいにデッドロックしたなあ・・・。

回避するには、

  1. タイムアウトさせる
  2. フォークを与える給仕を作る

というのがメジャーなところでしょうか。1はおいといて、2を実装するには、フォークの取得状況を表す変数fork_stateと状態変数を作って、fork_stateをmutexで保護すればよさそう。

おなかがすいた人は

  1. fork_stateをロック
  2. fork_stateをみて、両方取れるようならフォークを取得
  3. ダメならwait

で、食事が終わった人は

  1. fork_stateをロック
  2. fork_stateからフォーク取得を解除
  3. pthread_cond_broadcast()で起こす

とかすればどうでしょう。

極端な話、フォークの位置は無視して「フォーク5本」というカウンターを制御するのが一番パフォーマンスよさそうだけど・・・。問題変わりそう。