デッドロック問題: 食事する哲学者 in C

「食事する哲学者」の問題をCでシミュレーションしてみます。

問題 「食事する哲学者」

同時実行の問題として 「食事する哲学者」(The dining philosophers) というのがあります。

5人の哲学者と5つのフォークを円形に交互に並べます。円卓で、5人で食事すると考えてください。
それぞれの哲学者は、食事をするときに左右のフォーク合計2本をつかって食事をします。
ひとつのフォークは同時に2人以上が使うことができません。

これをコードで表す場合、下の条件でデッドロックになります。

それぞれの哲学者が左のフォークを先に取り、右のフォークを取って食事をする。
もしフォークが使用中であった場合、哲学者はフォークが取得できるようになるまでそのまま待機する。
食事が終わったら、使用していたフォークを手放す。

まさかと思うかもしれませんが、この設定においてフォークは2人と共同で使います。何度も繰り返し使われます。

この問題はダイクストラによって提起され、解決されたといわれています。

デッドロックになるコード

哲学者

哲学者をスレッドとします。
哲学者ですから、考えて、フォークをとって、食べて、フォークをおきます。

    think();
    get_forks(a->index);
    eat();
    put_forks(a->index);

think, eat は一定時間待つ処理にしています。

フォーク

フォークはセマフォです。

sem_t forks[N];

1で初期化します。

for (i = 0; i < N; i++) sem_init(&forks[i], 0, 1);

フォークを取る動作

哲学者がフォークを取得するための関数はいくつかあります。
get_forks が、2つのフォークを取得するようになっており、その他の関数は get_forks を通じて呼び出されます。
デッドロックを起きやすくするため、ひとつめとふたつめのフォークを取得する間は一定時間空けることにします。

int first(int p)  {
  return p;
}

int second(int p) {
  return (p + 1) % N;
}

void get_first_fork(int p) {
  printf("philosopher %d get fork %d", p, first(p));
  sem_wait(&forks[first(p)]);
  printf(" ... DONE\n");
}

void get_second_fork(int p) {
  printf("philosopher %d get fork %d", p, second(p));
  sem_wait(&forks[second(p)]);
  printf(" ... DONE\n");
}

void get_forks(int p) {
  get_first_fork(p);
  wait();
  get_second_fork(p);
}

全体

全体のコードは次のようになります。
マクロで定義している N をかえると 哲学者、フォークの数をかえられます。

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


#define N 5
#define M 100

sem_t forks[N];

typedef struct {
  int index;
} parg;

void wait() {
  usleep(((rand() % 5) + 1) * 1000);
}

int first(int p)  {
  return p;
}

int second(int p) {
  return (p + 1) % N;
}

void get_first_fork(int p) {
  printf("philosopher %d get fork %d", p, first(p));
  sem_wait(&forks[first(p)]);
  printf(" ... DONE\n");
}

void get_second_fork(int p) {
  printf("philosopher %d get fork %d", p, second(p));
  sem_wait(&forks[second(p)]);
  printf(" ... DONE\n");
}

void get_forks(int p) {
  get_first_fork(p);
  wait();
  get_second_fork(p);
}

void put_first_fork(int p) {
  printf("philosopher %d put fork %d", p, first(p));
  sem_post(&forks[first(p)]);
  printf(" ... DONE\n");
}

void put_second_fork(int p) {
  printf("philosopher %d put fork %d", p, second(p));
  sem_post(&forks[second(p)]);
  printf(" ... DONE\n");
}

void put_forks(int p) {
  put_first_fork(p);
  put_second_fork(p);
}

void think() {
  wait();
}

void eat() {
  wait();
}

void *philosopher(void *arg) {
  parg *a = (parg *) arg;
  int i;
  for (i = 0; i < M; i++) {
    think();
    get_forks(a->index);
    eat();
    put_forks(a->index);
  }
  return NULL;
}

int main(int argc, char *argv[]) {
  int i;
  // initialize forks
  for (i = 0; i < N; i++) sem_init(&forks[i], 0, 1);

  // initialize and start philosophers
  pthread_t p[N];
  parg a[N];
  for (i = 0; i < N; i++) {
    a[i].index = i;
    pthread_create(&p[i], NULL, philosopher, &a[i]);
  }

  for (i = 0; i < N; i++) pthread_join(p[i], NULL);

  printf("finished\n");
  return 0;
}

コンパイル

AWS EC2 にて gcc -pthread file.c でコンパイルしました。

出力例

1

$ ./a.out 
philosopher 1 get fork 1 ... DONE
philosopher 4 get fork 4 ... DONE
philosopher 3 get fork 3 ... DONE
philosopher 2 get fork 2 ... DONE
philosopher 0 get fork 0 ... DONE
(DEADLOCK)

2

philosopher 3 get fork 3 ... DONE
philosopher 4 get fork 4 ... DONE
philosopher 0 get fork 1philosopher 3 get fork 4philosopher 1 put fork 1 ... DONE
philosopher 1 put fork 2 ... DONE
 ... DONE
philosopher 2 get fork 2 ... DONE
philosopher 1 get fork 1philosopher 0 put fork 0 ... DONE
philosopher 0 put fork 1 ... DONE
 ... DONE
philosopher 0 get fork 0 ... DONE
(DEADLOCK)

デッドロックとセマフォの値

デッドロックになる場合、たとえば次のような順でセマフォの値が変わっていきます。
すべてのセマフォが0になり、そのあとはどの哲学者もフォークを取れなくなります。

デッドロックを解決するコード

解決方法はいくつかありますが、ここでは5人目の哲学者が右のフォークから手に取るということにしてみます。 次のようにコードを変更します。

int first(int p)  {
  if (p == 4) return (p + 1) / N;
  return p;
}

int second(int p) {
  if (p == 4) return p;
  return (p + 1) % N;
}

これでプログラムがデッドロックになることなく、終了するようになりました。

デッドロックを回避したポイント

5人目がフォークを取る順番を変えただけで解決しました。 これは、全てのフォークについてのロックの優先順位を定めたことになります。 5人目の変更によって、フォークは、インデックスが 0, 1, 2, 3, 4 の順で優先的に取得されることになりました。

複数人がフォークを取る順番を変更したらどうなるか

2〜4人以上がフォークの順番を変更した場合も、優先順位を定めたのと同じことになり、デッドロックは起きなくなります。 実際にどのような優先順位がつけられるのか確認してみます。

L を左のフォークから取る人、 R を右のフォークから取る人とします。 今回考える5人の中には少なくとも1人の L が存在しますから、 その人から順番に左から記載します。 そうすると L, R の順番は次の8通りです。

1. LRRRR
2. LLRRR
3. LRLRR
4. LRRLR
5. LLLRR
6. LLRLR
7. LRLLR
8. LLLLR

哲学者は円卓に座っていますから、3と4、6と7は同一視できます。 また、1と8、2と5、3と7は L,Rを入れ替えたものなので同一視できます。 すると検討が必要なのは次の2つだとわかります。

1. LLRRR
2. LRLRR

それぞれ確認してみます。

2. LLRRR

哲学者 0 は フォーク 0 を先に、 フォーク 1 を次に取ります。
哲学者 1 は フォーク 1 を先に、 フォーク 2 を次に取ります。
哲学者 2 は フォーク 3 を先に、 フォーク 2 を次に取ります。
哲学者 3 は フォーク 4 を先に、 フォーク 3 を次に取ります。
哲学者 4 は フォーク 0 を先に、 フォーク 4 を次に取ります。

フォークの優先順位は 0, 1, 4, 3, 2 とつけられます。

3. LRLRR

哲学者 0 は フォーク 0 を先に、 フォーク 1 を次に取ります。
哲学者 1 は フォーク 2 を先に、 フォーク 1 を次に取ります。
哲学者 2 は フォーク 2 を先に、 フォーク 3 を次に取ります。
哲学者 3 は フォーク 4 を先に、 フォーク 3 を次に取ります。
哲学者 4 は フォーク 0 を先に、 フォーク 4 を次に取ります。

フォークの優先順位は 0, 2, 4, 3, 1, とつけられます。