スレッドとミューテックスを使って食事する哲学者の問題をシュミレーションしました.

シュミレーションルール

全ての哲学者が食事をする必要があり, 一人でも一定時間内に食事できない(死亡)とシュミレーションを終了する.
各哲学者は互いに会話することができないため, 他の哲学者が死亡することを予測することはできない.
各哲学者は以下のいずれかの状態でいる.
- eating(フォークを両手に取っている)
- sleeping(フォークは両方置いている)
- thinking(フォークを取ろうとする)
  eating->sleeping->thinking->eating->...の順で状態が変化する.
以下の情報を引数で受け取る, 各時間の単位はms.
- number_of_philosophers : 哲学者(またはフォークの)数
- time_to_die : 最後の食事(またはシュミレーションが始まって)から次の食事までにこの時間を過ぎると哲学者は死亡する
- time_to_eat : 食事にかかる時間
- time_to_sleep : 睡眠にかかる時間
- number_of_times_each_philosopher_must_eat : (オプション)、全ての哲学者がこの回数以上食事をするとシュミレーションは終了する, 指定されなければ誰か一人が死んだ時のみ終了する.
哲学者は1から順に(時計 or 反時計回りで)番号を振られる.
各哲学者の状態が変化する時にはタイムスタンプと共に内容を表示する必要がある.
- timestamp_in_ms X has taken a fork
- timestamp_in_ms X is eating
- timestamp_in_ms X is sleeping
- timestamp_in_ms X is thinking
- timestamp_in_ms X died
哲学者はそれぞれスレッドで動かし, ミューテックスを使ってフォークの取り合いを制御する.

サンプルからの実装例

サンプルプログラムを書きながら実装例まで見ていきます.
各関数や用語の説明は省略します.

スレッド作成

以下のコードでスレッドの作成と挙動を実験します.

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

//スレッドに渡す関数
//引数の中身を出力
void *thread_func(void *thread_data)
{
    int *num;

    num = (int *)thread_data;
    printf("thread_func: %d\n", *num);
    return (thread_data);
}

//thread_funcとnumを引数にスレッド作成
//numをインクリメント後, 中身を出力
int main(void)
{
    int         num;
    pthread_t   thread_id;

    num = 0;
    pthread_create(&thread_id, NULL, &thread_func, &num);//スレッド作成
    while (num < 50000)
        num++;
    printf("main: %d\n", num);
    pthread_join(thread_id, NULL);
    return (0);
}

実行結果

thread_func: 2358
main: 50000

thread_funcの出力結果は毎度変わります.
つまり, main関数のnumインクリメント中に,
別スレッドのthread_func関数の出力が行われいてることが分かります.
実際-g -fsanitize=threadというフラグを付けてコンパイルしてから実行するとデータ競合の発生が分かります.

ミューテックス追加

次にミューテックスを利用してデータ競合を防いでみます.
ポイントはnumの操作・出力の前後にミューテックスのロック・アンロックを挟んでいるところです.

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

pthread_mutex_t mutex;                 //追加

void *thread_func(void *thread_data)
{
    int *num;

    num = (int *)thread_data;
    pthread_mutex_lock(&mutex);        //追加
    printf("thread_func: %d\n", *num);
    pthread_mutex_unlock(&mutex);      //追加
    return (thread_data);
}

int main(void)
{
    int         num;
    pthread_t   thread_id;

    num = 0;
    pthread_mutex_init(&mutex, NULL);  //追加
    pthread_create(&thread_id, NULL, &thread_func, &num);
    pthread_mutex_lock(&mutex);        //追加
    while (num < 50000)
        num++;
    printf("main: %d\n", num);
    pthread_mutex_unlock(&mutex);      //追加
    pthread_join(thread_id, NULL);
    pthread_mutex_destroy(&mutex);     //追加
    return (0);
}

実行結果

main: 50000
thread_func: 50000

今回は出力が同じになり, データ競合も確認できませんでした.
main関数でのnumインクリメント中は, 別スレッドのthread_func関数の処理はミューテックスにより待機していたことが分かります.

実装例

スレッドとミューテックスの使い方がわかったので実装例を書きます.
例でも実際に書くと長くなってしまうので, 超省略版を載せます.
※実際に書くときは各関数のエラー処理も忘れずに

//philosopher(哲学者)のスレッドが使う関数群
void eat()
{
    pthread_mutex_lock(right_fork);
    pthread_mutex_lock(left_fork);
    /* 食事 */
    pthread_mutex_unlock(right_fork);
    pthread_mutex_unlock(left_fork);

}
void sleep() { /* 睡眠 */ }
void think() { /* 思考 */ }

//philosopherのスレッドに渡す関数
void *philo(void *)
{
    while (1)
    {
        eat();
        sleep();
        think();
    }
}

//philosopherのスレッドを(死んでいないか)監視するmonitorスレッドに渡す関数
void *monitor(void *)
{
    if (is_died)
    {
        /* 死亡 */
    }
}

int main(void)
{
    while (number_of_philo)
    {
        pthread_create(philo);
        pthread_create(monitor);
    }
}

まとめ

今回はざっくりとしたお話になってしまいましたが,
スレッドという概念に触れられてとても勉強になりました!!

rakiyama0229のブログ

哲学者に食事をさせましたというお話。

シュミレーションルール

サンプルからの実装例

スレッド作成

ミューテックス追加

実装例

まとめ