Open24

Philo課題メモ

こよdこよd

https://ja.wikipedia.org/wiki/食事する哲学者の問題

哲学（ギリシャ語のphilosophia、文字通り「知恵を愛すること」）とは、存在、知識、価値、理性、心、言語に関する一般的で根本的な問題を研究する学問である。

課題の目的

「食事する哲学者の問題」を、threadという技術を使って、並列処理で解く

概要

  • １人以上の哲学者が円卓に座っている。
  • 哲学者は交互に食べたり、考えたり、眠ったりする。
  • １つの動作の間はそれだけしかしない、それ以外のことをしない。

偉大なる大先輩方のありがたい資料

https://docs.google.com/presentation/d/12-lAykLu-RVACE1gI2aP-uEYZoOaeeFVYGh8W4ttTNw/edit#slide=id.gd4524b1be8_0_288

https://wolframike.notion.site/Rank-03-Philosophers-85ca833a133f4393b24d38af4f8a8cd9

こよdこよd

https://docs.oracle.com/cd/E19455-01/806-2732/6jbu8v6op/index.html
https://qiita.com/ryo_manba/items/e48faf2ba84f9e5d31c8
明示的な合計処理は行なっていないが、両方のスレッドが同じ変数を更新することで、結果として合計が得られる

int				cnt = 0;
pthread_mutex_t	mutex;

void	*routine(void *p)
{
	int	i;
    (void)p;
	i = 0;
	while (i < 10000)
	{
		//pthread_mutex_lock(&mutex);
		cnt++;
		//pthread_mutex_unlock(&mutex);
		i++;
	}
	return (NULL);
}

lock, unlockをしていないと、競合状態が頻繁に発生する。
最終的な cnt の値は期待される20000よりも小さくなる。
実際には、ミューテックスを使用しない場合、最終的な値は実行ごとに異なり、通常は20000未満になる。コメントをして競合状態が発生するようにすると、競合が発生する頻度によって毎回syつ力が変わる。

こよdこよd

http://www.newves.org/~mori/15Programming/PDFs/150619slide.pdf

  • 列挙型知らなかったのでメモ
    • 名前つき整数定数のリスト
  • 定義方法
    • enum タグ名 {列挙リスト};
    • enum color_type {red, green, yellow};
  • 使用時の宣言
    • enum タグ名 変数名;
    • enum color_type mycolor;
  • 定義と宣言を同時
    • enum color_type {red, green, yellow} mycolor;
  • 列挙型の定数に整数が代入される
    • リストの最初が0，後は順に加算
    • 強制的に値を与えることも可能
      • enum color_type {red, green=9, yellow} mycolor; (yellowは10)
typedef enum
{
	THINKING,
	EATING,
	SLEEPING
}					t_state;

typedef struct s_philo
{
	t_state state;
}

みたいに書ける

こよdこよd

どうやって適切に哲学者の食事タイミングをずらすか
→
哲学者の人数 P や、食事時間 E 、そして哲学者の番号 I に基づいて、各哲学者が最初にどの程度の時間待機（usleep）するかを計算する。
複数の哲学者が一斉にフォークを取ろうとすることで発生するデッドロックを避けるために、各哲学者の行動を少しずつずらしてあげないといけない。

  1. P が偶数で I が偶数の場合
  2. P が偶数で I が奇数の場合
  3. P が奇数で I が偶数の場合
  4. P が奇数で I が奇数の場合
こよdこよd

スレッドによる並行処理
https://ota42y.com/blog/2015/06/18/c-thread/

スレッドの作成(pthread_create)

int pthread_create(pthread_t * thread,
pthread_attr_t * attr,
void * (*start_routine)(void *),
void * arg);
thread
スレッド管理用のpthread_t型の変数
attr
スレッドの属性を指定する。
NULLの場合はデフォルトが使われる
(*start_routine)(void *)
別スレッドから呼び出される関数へのポインタ
arg
start_routineの引数として渡すデータのポインタ
元のスレッドからデータを送るのに使う

スレッドの終了を待つ(pthread_join)

int pthread_join(pthread_t th, void **thread_return);
th
待機するスレッドをpthread_t型の変数で指定する
**thread_return
スレッドの戻り値を格納する領域

こよdこよd

https://itpfdoc.hitachi.co.jp/manuals/3020/3020635643/W3560073.HTM#:~:text=ロック回避策-,(1)%20%E3%83%87%E3%83%83%E3%83%89%E3%83%AD%E3%83%83%E3%82%AF%E3%81%AE%E7%99%BA%E7%94%9F%E8%A6%81%E5%9B%A0,%E3%81%A7%E5%A4%9A%E3%81%8F%E7%99%BA%E7%94%9F%E3%81%97%E3%81%BE%E3%81%99%E3%80%82

二つのトランザクションが二つ以上の資源の確保をめぐって互いに相手を待つ状態となり，そこから先へ処理が進まなくなることをデッドロック

https://engineering.mercari.com/blog/entry/2017-12-18-deadlock/

お互いにロック解放待ちをしてしまい、2つのプロセス両方が処理を進められなくなってしまい

https://www.embeddedmulticore.org/2021/09/21/３-デッドロック-deadlock-並列処理の不具合と対策/

問題の解決方法はロック順を揃えることです。
両関数のミューテックス変数ロック・アンロック順を揃えることで、このプログラムが正常に動作するようになりました。複数のミューテックス変数を使う際にロック順を決めておかないと、このような問題が発生します。

例えば、以下のようなシナリオ
2人のお客さん(A さんとB さん)がATMで操作を行っている
A さんは自分の口座から10000円引き出し、同時にB さんの口座に5000円預け入れしようとしている
B さんは自分の口座から20000円引き出し、同時にA さんの口座に20000円預け入れしようとしている
この時、ATMはA さんの口座にロックをかけ、B さんの口座にもロックをかける
A さんの引き出し処理が進行中でB さんの預入れは待機状態になり、
一方で、B さんの引き出し処理が進行中でA さんの預入れは待機状態になる
お互いにロックを解放するのを待っているため、両方の処理が完了できなくなり、デッドロック状態が発生してしまう

このように、お互いの処理が依存し合っている場合、ロックの取得順序によってデッドロックが発生する可能性
この例では、A さんとB さんがお互いの口座を操作しようとしており、処理の順序によってデッドロックが発生してしまった

こよdこよd

デッドロック防止の方法：

フォークを取る順序を固定（小さい番号から取る）
偶数番号の哲学者に初期遅延を導入
リソースの階層化による循環待ちの防止

初期スリープ時間の実装：
偶数番号の哲学者は食事時間の半分待機
奇数番号の哲学者はすぐに開始
これにより、同時にフォークを取ろうとする競合を減少

生命サイクルの実装：
思考→フォーク取得→食事→フォーク返却→睡眠のサイクル
各状態での適切なミューテックス制御
死亡判定と食事回数のチェック
タイムスタンプによる最後の食事時間の管理

安全性の確保：
ミューテックスによる排他制御
死亡フラグのチェック
食事回数の管理

この実装を使用する際の注意点：
必要なメモリの確保とミューテックスの初期化が必要
各哲学者用のスレッド生成が必要
プログラム終了時のリソース解放が必要

こよdこよd

・正しい時間の制御
・オーバーシュートを防ぐ

usleep 関数
手軽に利用できるマイクロ秒単位のスリープ関数だ。 ただし、現在は POSIX から削除されているため、利用すべきではない。 MAN も参照。

#include <unistd.h>
int usleep(useconds_t usec);
引数にはマイクロ秒を指定するため、sleep よりも細かな制御ができる。 指定した時間がスケジューラの精度以下の場合は、その制度の数値に切り上げられる。 すでに POSIX から削除され、過去との互換性のために残されている関数なので、新規には利用すべきではないが、 手元で一度書いて捨ててしまうようなテストに使うのであればよいだろう。

useconds_t 型は 0 ～ 1000000 を表現する形のため、 1000000 以上を指定するとエラーとなるシステムもあるとのことなので注意しよう。
https://www.mm2d.net/main/prog/c/sleep-01.html

こよdこよd
  • 引数:
    • number_of_philosophers 哲学者の人数 (=フォークの数)
    • time_to_die 死ぬまでの時間 (ms)
    • time_to_eat 食事する時間 (ms)
    • time_to_sleep 睡眠する時間 (ms)
    • [optional: number_of_times_each_philosopher_must_eat] プログラムを終了する食事回数
  • 使用可能な外部関数:
    • memset、printf、malloc、free、
      write、usleep、
      gettimeofday、
      pthread_create、
      pthread_detach、
      pthread_join、
      pthread_mutex_init、
      pthread_mutex_destroy、
      pthread_mutex_lock、
      pthread_mutex_unlock
    • Libftの使用: NG
こよdこよd

sequenceDiagram
participant Main
participant Philosophers
participant Monitor

Main->>Main: Initialize data
Main->>Main: Set start_time

rect rgb(200, 200, 255)
    Main->>Philosophers: Create philosopher threads
    Note over Philosophers: All philosophers initialized
end

rect rgb(200, 255, 200)
    Main->>Monitor: Start monitoring thread
    Note over Monitor: Begin death/completion checks
end

rect rgb(255, 200, 200)
    Main->>Philosophers: Wait for completion (join)
    Note over Philosophers: All philosophers complete
end
こよdこよd

スレッドのこと

  • pthread_createでthreadを作成する
    • 第一引数：thread識別用の哲学者のIDを格納するためpthread_t型の変数をポインタで渡す
    • 第二引数：今回使用しないのでNULL
    • 第三引数：作成したスレッドがそれぞれ実行する関数　void *(func)(void *)の型
    • 第四引数：第三引数で渡した関数の引数、void *の型
      -第三引数で指定した関数が実行される
  • pthread_join関数でthreadの終了を待つ
    • 第一引数：pthread_createの第一引数でもらったpthread_t型の変数哲学者のID
    • 第二引数：今回使用しないので無視NULL 
// 哲学者の人数分のスレッド（スレッドを作成する）
if (pthread_create(&data->philo[i].thread,  // 新しい哲学者のID
                 NULL,                      // 特別な指示はなし
                 action,                    // レシピブック（実行する関数）
                 &data->philo[i]))         // 哲学者の担当情報（関数に渡すデータ）

action関数は各哲学者（スレッド）が実行する作業手順：

static void *action(void *arg)
{
   t_philo *philo = (t_philo *)arg;  // 哲学者の担当情報を受け取る
   
   // ここから各哲学者の作業開始
   while (1)
   {
       // 1. 思考
       // 2. フォークを取る
       // 3. 食事
       // 4. フォークを置く
       // 5. 睡眠
   }
   return NULL;
}

各哲学者（スレッド）は同じレシピブック（action関数）を使う
でも、各哲学者は独立して作業を進める
必要な情報は&data->philo[i]で各哲学者に渡される

こよdこよd

全ての哲学者のスレッドを同期的に開始するための関数

同期開始の目的
多数のスレッドを同時に（できるだけ近いタイミングで）開始するため

①スタート時間の設定
info->start_time = get_time(); // 現在の時刻を取得
info->start_time += (long)500; // 500マイクロ秒遅らせる
②哲学者ごとのスレッドを作る
この時点ではまだスレッド動いてない

③同期待機ループ
time = get_time(); //現在の時刻を取得
while (info->start_time > time)
{
usleep(10);
time = get_time();
}
start_time（500マイクロ秒先の時間）になるまで待機
10マイクロ秒ごとに現在時刻を更新
全てのスレッドが同時に（ほぼ同時に）実行を開始する

こよdこよd
flowchart TD
    A[start_dinner() 開始] --> B[現在時刻取得]
    B --> C[start_time = 現在時刻 + 500μs]
    C --> D[全哲学者のスレッド作成]
    D --> E{1人の哲学者?}
    E -->|Yes| F[_one_philo() 実行]
    E -->|No| G[start_timeまで待機]
    G --> H[モニタースレッド作成]
    
    subgraph start_philo() スレッドの同期
    I[スレッド開始] --> J[start_timeまで待機]
    J --> K[最後の食事時間設定]
    K --> L{哲学者数の偶奇}
    L -->|偶数| M[偶数番目に遅延]
    L -->|奇数| N[複雑な遅延計算]
    M --> O[ルーティン開始]
    N --> O
    end
こよdこよd

join_all_threads （全てのスレッドの終了を待機する関数）を呼び出さない場合、以下の問題が発生:

子スレッドやモニタースレッドが途中で中断される。
リソースリークが発生する可能性がある。
プログラムの動作結果が不完全になる。

join_all_threads が必要な理由

  • 同期処理のため:
    メインスレッドがすべての哲学者スレッドとモニタースレッドの終了を確認するまで待つ。
    各スレッドの動作が完了したことを保証。
  • リソースの解放:
    スレッド終了時に pthread_join を使うことで、使用していたリソースを正しく解放。
  • 予期しない終了の防止:
    子スレッドが動作中にプログラム全体が終了することを防ぎ、処理の一貫性を確保。
こよdこよd

食事の関数
実装の全体的な流れ
哲学者の状態を「食事中」に更新し、最後の食事時刻を記録。
指定された時間（time_to_eat）だけスレッドをスリープ（食事動作を模擬的に）
スリープ終了後、哲学者の状態を「食事終了」に更新。
食事回数をインクリメント（必要な場合）。
フォークを解放して次の哲学者が利用できるようにする。

この関数の目的と重要性
哲学者の状態管理: 哲学者が食事中かどうか、最後に食事をした時間などを適切に管理。
同期の確保: ロックを利用してデータ競合を防ぎ、安全に状態を更新。
リソースの共有: 他の哲学者がフォークを使用できるようにする。
モニタースレッドとの連携: 飢餓状態の検知や食事回数の管理に必要な情報を提供。

こよdこよd

./philo 5 800 200 200 5
0 5 is eating
100 3 is eating
200 5 is sleeping
200 1 is eating
300 3 is sleeping
300 4 is eating
400 5 is thinking
400 2 is eating
400 1 is sleeping
500 3 is thinking
500 4 is sleeping
500 5 is eating
600 2 is sleeping
600 1 is thinking
600 3 is eating
700 5 is sleeping
700 1 is eating
700 4 is thinking
800 2 is thinking
800 3 is sleeping
800 4 is eating
900 5 is thinking
900 1 is sleeping
900 2 is eating
1000 3 is thinking
1000 4 is sleeping
1000 5 is eating
1100 1 is thinking
1100 3 is eating
1100 2 is sleeping
1200 5 is sleeping
1200 1 is eating
1200 4 is thinking
1300 2 is thinking
1300 3 is sleeping
1300 4 is eating
1400 5 is thinking
1400 1 is sleeping
1400 2 is eating
1500 4 is sleeping
1500 3 is thinking
1500 5 is eating
1600 1 is thinking
1600 2 is sleeping
1600 3 is eating
1700 5 is sleeping
1700 1 is eating
1700 4 is thinking
1800 2 is thinking
1800 3 is sleeping
1800 4 is eating
1900 5 is thinking
1900 1 is sleeping
1900 2 is eating
2000 3 is thinking
2000 4 is sleeping
2000 5 is eating
2100 1 is thinking
2100 2 is sleeping
2100 3 is eating
2200 4 is thinking
2200 5 is sleeping
2200 1 is eating
2300 3 is sleeping
2300 4 is eating
2300 2 is thinking
2400 1 is sleeping
2400 2 is eating
2400 5 is thinking
2500 4 is sleeping
2500 3 is thinking
2500 5 is eating
2602 1 is thinking
2602 2 is sleeping
2603 3 is eating
2700 4 is thinking
2700 5 is sleeping
2700 1 is eating
2802 2 is thinking
2803 3 is sleeping
2803 4 is eating
2900 5 is thinking
2900 1 is sleeping
2900 2 is eating
3003 3 is thinking
3003 4 is sleeping
3003 5 is eating
3100 2 is sleeping
3100 1 is thinking
3100 3 is eating

こよdこよd

stateDiagram-v2
[*] --> Main: Program Starts

state Main {
    [*] --> CheckArguments
    CheckArguments --> ValidateInput : Valid Arguments
    ValidateInput --> InitTable : Input Validated
    InitTable --> InitPhilosophers : Table Initialized
    InitPhilosophers --> StartTable : Philosophers Initialized
    StartTable --> StartPhilosophers : Table Started
    StartPhilosophers --> MonitorPhilosophers : Philosophers Running
    MonitorPhilosophers --> EndTable : Monitoring Complete
    EndTable --> [*]
}

state StartPhilosophers {
    direction=right
    [*] --> TakeFork
    TakeFork --> Eating
    Eating --> ReleaseFork
    ReleaseFork --> Sleeping
    Sleeping --> Thinking
    Thinking --> TakeFork
}

note right of CheckArguments
    Validate number of 
    arguments and input
end note

note right of InitTable
    Initialize table 
    and mutex resources
end note

note right of InitPhilosophers
    Create philosopher 
    threads and set 
    initial conditions
end note

note right of StartPhilosophers
    Each philosopher 
    starts their lifecycle
end note

note right of MonitorPhilosophers
    Monitor philosopher 
    states and detect 
    potential deadlocks
end note
こよdこよd

https://qiita.com/roge_mega/items/85ddd10a5a6eea9c1d95
よく使うオプション
--leak-check=full：メモリリークに関する詳細な情報を表示します。
--track-origins=yes：未初期化メモリの使用箇所を特定します。
--show-leak-kinds=all：全ての種類のメモリリーク（確保したが解放されていないメモリ、無効な解放など）を表示します。

❯ valgrind --track-origins=yes ./philo 3 800 200 200 2
threadのエラー出力あり
未初期化変数を使用する条件分岐が原因でエラーが発生していた
→初期化を追加したらValgrindのエラーは解消された

初歩的なことで、
VSCodeの自動保存がONだと思い込んでいたら全く保存できていなかった。。。。
気がつくまでに時間かかりすぎた。

こよdこよd

https://qiita.com/chimpan/items/2da70cd6ceaeb5558e3f
valgrind --tool=helgrind ./a.out
実行しても致命的なエラーがなかったので大丈夫そう
WARNING: ThreadSanitizer: lock-order-inversion (potential deadlock) (pid=555115) 潜在的なデッドロックでwarningが出ているだけで、デッドロック自体は確認できなかったので、問題ない
→これは間違いで、デッドロックが起こり得る状況ということが暗に示されているので良くないコード。デッドロックの概念を根本から理解しているのか危ういという判断になりうる。

今回自分が書いたコードだと、デッドロックが起こりうる条件のうちの「循環待機」が発生しているため、ワーニングが出ている。これが良くないし、なんでこれが起こっている状態で良いと思ったのかについて説明ができない。
デッドロックが起こる定義の4つの状態のうち、1つでもその状態が発生しないようにｓればよい。

デッドロックの概念

デッドロックは、一般的に4つの条件（相互排他、保持・待機、不可分性、循環待機）が揃うことで発生します。
これらの条件が同時に満たされる場合にのみ発生する

こよdこよd

フィロコード
フィロコード

哲学の規範が以下の要件に準拠していることを確認し、説明を求めます。

哲学者ごとに 1 つのスレッドがあることを確認します。

哲学者ごとにフォークが 1 つだけあることを確認します。

フォークごとにミューテックスがあり、それがフォーク値の確認や変更に使用されているかどうかを確認します。

出力が混同されていないことを確認してください。

哲学者の死がどのように検証されるか、また哲学者が死ぬと同時に食事を始めるのを防ぐためのミューテックスがあるかどうかを確認します。

はい

いいえ
哲学テスト
哲学テスト

200 人を超える哲学者でテストしないでください。

time_to_die、time_to_eat、time_to_sleep を 60 ミリ秒未満の値に設定してテストしないでください。

テスト 1 800 200 200。哲学者は食べるべきではなく、死ぬべきです。

テスト 5 800 200 200。哲学者は死ぬべきではない。

テスト 5 800 200 200 7. 哲学者は誰も死ぬことはなく、すべての哲学者が少なくとも 7 回食事をしたらシミュレーションは停止します。

テスト 4 410 200 200. 哲学者は死ぬべきではない。

テスト4 310 200 100. 一人の哲学者が死ぬべきだ。

2 人の哲学者でテストし、さまざまな時間をチェックします。10 ミリ秒以上遅れた死は受け入れられません。

任意の値でテストして、すべての要件を確認します。哲学者が適切なタイミングで死ぬこと、フォークを盗まないことなどを確認します。

こよdこよd

どこにsleepが差し込まれても同じように動くコードがよりベター
非同期処理というものについてより理解していれば、
お互いが理想的に動いていることを前提としない場合したコードをかけている
うぇいたー方式を使うとよい