【C言語】Dining Philosophersの簡単な解法

はじめに

Dining Philosophers Problemについて、C言語を用いた簡単な解法を書いてみます。

Dining Philosophers Problem とは

日本語では「食事する哲学者の問題」と呼ばれています。設定はこうです。

  • 円卓に哲学者が5人が座っている
  • 哲学者の間にフォークが1本ずつ、計5本ある
  • 哲学者は考える(Thinking)か食事(Eating)をする
  • 哲学者が食事をするときは左右の2本のフォークが必要である
  • 哲学者を飢え死にさせないためにはどうすればよいか

これは並列処理においてエンジニアはどういうプログラムを書けば良いかを教えてくれるいい問題です。最近の情勢上、某ウイルスの懸念があったりとか、いや1つのフォークで食えるやろとか、いろいろ思うところはありますがいったん飲み込むことにします。ここで、以下のようなシチュエーションに陥った場合は、哲学者が飢え死にしてしまいます。

  • 哲学者が一斉に右手のフォークを取り、握りしめている
  • それぞれの哲学者は左手のフォークが空くのを待つ

誰かが諦めて右手のフォークを離してくれない限り永遠に食事が始まることはありません。このように、並列処理において、スレッド等がお互いの処理待ちになり動かなくなってしまうことをデッドロックといいます。P0～P4がスレッドだとすると、以下のような状態がデッドロックになる訳です。

P0P1P2P3P4
1F0を取った
2F1を取った
3F2を取った
4F3を取った
5F4を取った
6F1が欲しい
7ブロックして待つF2が欲しい
8ブロックして待つF3が欲しい
9ブロックして待つF4が欲しい
10ブロックして待つF0が欲しい
11ブロックして待つ
………………

つまり、Dining Philosophers Problemは如何にしてデッドロックを回避するかという問題です。

簡単な解法

結論から言うとフォークなどの資源に対し、ロックを取得する順番を決めてやればいいです。

この状況においてデッドロックを発生させている原因は、5番目の哲学者(P4)にあります。

他の哲学者(P0～P3)はフォークを番号の低い順(F0 → F1 → F2 → F3)で取っているのに対し、P4のみフォークの番号が高い順(F4 → F0)で取ろうとしていることがデッドロックを発生させている原因だったわけです。P5がF0 → F4の順でフォークを取るように修正すれば、デッドロックを回避できます。

mutexを用いたプログラム

はじめにmutex、次にセマフォを用いたプログラムを紹介します。

デッドロックの恐れがあるプログラム

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

#define PHILOS 5
#define DISH 10000

pthread_mutex_t forks[PHILOS];

/*** ランダム時間だけ考える ***/
void think(void)
{
	usleep(rand() % 100);
}

/*** ランダム時間で食事する ***/
void eat(int p_id)
{
	printf("Philosopher[%d] is eating.\n", p_id);
	usleep(rand() % 100);
}

/*** フォークを取得する関数 ***/
void get_forks(int first_fork, int second_fork)
{
	pthread_mutex_lock(&(forks[first_fork]));
	pthread_mutex_lock(&(forks[second_fork]));
}

/*** フォークを手放す関数 ***/
void release_forks(int first_fork, int second_fork)
{
	pthread_mutex_unlock(&(forks[first_fork]));
	pthread_mutex_unlock(&(forks[second_fork]));
}

/*** 哲学者 ***/
void *philosopher(void *arg){
	int p_id = *(int *)arg;	// 哲学者のID
	/*** 右手、左手の順でフォークを取りたい ***/
	int first_fork = p_id;
	int second_fork = (first_fork + 1) % PHILOS;

	for(int k = 0; k < DISH; k++){
		think();
		get_forks(first_fork, second_fork);
		eat(p_id);
		release_forks(first_fork, second_fork);
	}
}

int main(void){
	pthread_t th[PHILOS];
	int p_id[PHILOS];
  
	for(int i = 0; i < PHILOS; i++){
		/*** mutexを初期化する ***/
		pthread_mutex_init(&(forks[i]), NULL);
	}

	for(int i = 0; i < PHILOS; i++){
		/*** PHILOS数だけ哲学者を生み出す ***/
		p_id[i] = i;
		pthread_create(&th[i], NULL, *philosopher, (void *)&(p_id[i]));
	}

	for(int i = 0; i < PHILOS; i++){
		/*** DISH数だけ食べ終わるのを待機する ***/
		pthread_join(th[i], NULL);
	}

	return 0;
}

実際に実行してもらうことでデッドロックを再現できます。デッドロックしない場合はDISHの値を増やすといいと思います。以下のように、コンパイルオプション -pthread もしくは -lpthread をつけてコンパイルします。

gcc dining_philosophers.c -pthread

修正したプログラム

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

#define PHILOS 5
#define DISH 10000

pthread_mutex_t forks[PHILOS];

/*** 値を交換する関数 ***/
void swap(int *a, int *b)
{
	int tmp = *a;
	*a = *b;
	*b = tmp;
}

/*** ランダム時間だけ考える ***/
void think(void)
{
	usleep(rand() % 100);
}

/*** ランダム時間で食事する ***/
void eat(int p_id)
{
	printf("Philosopher[%d] is eating.\n", p_id);
	usleep(rand() % 100);
}

/*** フォークを取得する関数 ***/
void get_forks(int first_fork, int second_fork)
{
	pthread_mutex_lock(&(forks[first_fork]));
	pthread_mutex_lock(&(forks[second_fork]));
}

/*** フォークを手放す関数 ***/
void release_forks(int first_fork, int second_fork)
{
	pthread_mutex_unlock(&(forks[first_fork]));
	pthread_mutex_unlock(&(forks[second_fork]));
}

/*** 哲学者 ***/
void *philosopher(void *arg){
	int p_id = *(int *)arg;	// 哲学者のID
	/*** 右手、左手の順でフォークを取りたい ***/
	int first_fork = p_id;
	int second_fork = (first_fork + 1) % PHILOS;
	/*** 最後の哲学者は左手から先に取らせる ***/
	if (p_id == PHILOS - 1) swap(&first_fork, &second_fork);

	for(int k = 0; k < DISH; k++){
		think();
		get_forks(first_fork, second_fork);
		eat(p_id);
		release_forks(first_fork, second_fork);
	}
}

int main(void){
	pthread_t th[PHILOS];
	int p_id[PHILOS];
  
	for(int i = 0; i < PHILOS; i++){
		/*** mutexを初期化する ***/
		pthread_mutex_init(&(forks[i]), NULL);
	}

	for(int i = 0; i < PHILOS; i++){
		/*** PHILOS数だけ哲学者を生み出す ***/
		p_id[i] = i;
		pthread_create(&th[i], NULL, *philosopher, (void *)&(p_id[i]));
	}

	for(int i = 0; i < PHILOS; i++){
		/*** DISH数だけ食べ終わるのを待機する ***/
		pthread_join(th[i], NULL);
	}

	return 0;
}

11-17、52-53行目を追加しただけです。これにより、いかなる状態でもフォークのロックを昇順に取得します。

Semaphore(セマフォ)を用いたプログラム

mutexをセマフォに変えただけのプログラムです。初期値を1としたバイナリセマフォを用いて実装しています。

デッドロックの恐れのあるプログラム

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

#define PHILOS 5
#define DISH 10000

sem_t forks[PHILOS];

/*** ランダム時間だけ考える ***/
void think(void)
{
	usleep(rand() % 100);
}

/*** ランダム時間で食事する ***/
void eat(int p_id)
{
	printf("Philosopher[%d] is eating.\n", p_id);
	usleep(rand() % 100);
}

/*** フォークを取得する関数 ***/
void get_forks(int first_fork, int second_fork)
{
	sem_wait(&(forks[first_fork]));
	sem_wait(&(forks[second_fork]));
}

/*** フォークを手放す関数 ***/
void release_forks(int first_fork, int second_fork)
{
	sem_post(&(forks[first_fork]));
	sem_post(&(forks[second_fork]));
}

/*** 哲学者 ***/
void *philosopher(void *arg){
	int p_id = *(int *)arg;	// 哲学者のID
	/*** 右手、左手の順でフォークを取りたい ***/
	int first_fork = p_id;
	int second_fork = (first_fork + 1) % PHILOS;

	for(int k = 0; k < DISH; k++){
		think();
		get_forks(first_fork, second_fork);
		eat(p_id);
		release_forks(first_fork, second_fork);
	}
}

int main(void){
	pthread_t th[PHILOS];
	int p_id[PHILOS];
  
	for(int i = 0; i < PHILOS; i++){
		/*** バイナリセマフォで初期化する ***/
		sem_init(&(forks[i]), 0, 1);
	}

	for(int i = 0; i < PHILOS; i++){
		/*** PHILOS数だけ哲学者を生み出す ***/
		p_id[i] = i;
		pthread_create(&th[i], NULL, *philosopher, (void *)&(p_id[i]));
	}

	for(int i = 0; i < PHILOS; i++){
		/*** DISH数だけ食べ終わるのを待機する ***/
		pthread_join(th[i], NULL);
	}

	return 0;
}

修正したプログラム

デッドロックの解決法もmutexと全く同様です。

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

#define PHILOS 5
#define DISH 10000

sem_t forks[PHILOS];

/*** 値を交換する関数 ***/
void swap(int *a, int *b)
{
	int tmp = *a;
	*a = *b;
	*b = tmp;
}

/*** ランダム時間だけ考える ***/
void think(void)
{
	usleep(rand() % 100);
}

/*** ランダム時間で食事する ***/
void eat(int p_id)
{
	printf("Philosopher[%d] is eating.\n", p_id);
	usleep(rand() % 100);
}

/*** フォークを取得する関数 ***/
void get_forks(int first_fork, int second_fork)
{
	sem_wait(&(forks[first_fork]));
	sem_wait(&(forks[second_fork]));
}

/*** フォークを手放す関数 ***/
void release_forks(int first_fork, int second_fork)
{
	sem_post(&(forks[first_fork]));
	sem_post(&(forks[second_fork]));
}

/*** 哲学者 ***/
void *philosopher(void *arg){
	int p_id = *(int *)arg;	// 哲学者のID
	/*** 右手、左手の順でフォークを取りたい ***/
	int first_fork = p_id;
	int second_fork = (first_fork + 1) % PHILOS;
	/*** 最後の哲学者は左手から先に取らせる ***/
	if (p_id == PHILOS - 1) swap(&first_fork, &second_fork);

	for(int k = 0; k < DISH; k++){
		think();
		get_forks(first_fork, second_fork);
		eat(p_id);
		release_forks(first_fork, second_fork);
	}
}

int main(void){
	pthread_t th[PHILOS];
	int p_id[PHILOS];
  
	for(int i = 0; i < PHILOS; i++){
		/*** バイナリセマフォで初期化する ***/
		sem_init(&(forks[i]), 0, 1);
	}

	for(int i = 0; i < PHILOS; i++){
		/*** PHILOS数だけ哲学者を生み出す ***/
		p_id[i] = i;
		pthread_create(&th[i], NULL, *philosopher, (void *)&(p_id[i]));
	}

	for(int i = 0; i < PHILOS; i++){
		/*** DISH数だけ食べ終わるのを待機する ***/
		pthread_join(th[i], NULL);
	}

	return 0;
}