Philo課題メモ
こよd
哲学（ギリシャ語のphilosophia、文字通り「知恵を愛すること」）とは、存在、知識、価値、理性、心、言語に関する一般的で根本的な問題を研究する学問である。
課題の目的
「食事する哲学者の問題」を、threadという技術を使って、並列処理で解く
概要
- １人以上の哲学者が円卓に座っている。
- 哲学者は交互に食べたり、考えたり、眠ったりする。
- １つの動作の間はそれだけしかしない、それ以外のことをしない。
偉大なる大先輩方のありがたい資料
こよd-
thredとmutexについて理解する
-
超ざっくりの流れ
プロセスを作る
スレッドを作る
それぞれが勝手に動くようにする
死んでいないかを見ておく
出力は各１人ずつ io_lock
if死んでいたら何も出力しないで終わり
こよdgcc -fsanitize=thread
nm -u philo
valgrind --leak-check=full
gcc -fsanitize=threadが必ず失敗する（linuxに移行してから？）
setarch $(uname -m) -R ./philo ...
って実行する
こよd明示的な合計処理は行なっていないが、両方のスレッドが同じ変数を更新することで、結果として合計が得られる
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
- 列挙型知らなかったのでメモ
- 名前つき整数定数のリスト
- 定義方法
- 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どうやって適切に哲学者の食事タイミングをずらすか
→
哲学者の人数
複数の哲学者が一斉にフォークを取ろうとすることで発生するデッドロックを避けるために、各哲学者の行動を少しずつずらしてあげないといけない。
-
P I -
P I -
P I -
P I
こよdgettimeofday()
#include <sys/time.h>
こよdスレッドによる並行処理
スレッドの作成(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[DEBUG] ***Starting to create threads. Number of philosophers: 6
[DEBUG] ***Starting time: 1730202547159
...
[DEBUG] ***Philosopher 4 first meal time 1730202547359
哲学者の作成と、哲学者のそれぞれのスタート時間をずらすことができていそう?
こよdhttps://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
二つのトランザクションが二つ以上の資源の確保をめぐって互いに相手を待つ状態となり，そこから先へ処理が進まなくなることをデッドロック
お互いにロック解放待ちをしてしまい、2つのプロセス両方が処理を進められなくなってしまい
問題の解決方法はロック順を揃えることです。
両関数のミューテックス変数ロック・アンロック順を揃えることで、このプログラムが正常に動作するようになりました。複数のミューテックス変数を使う際にロック順を決めておかないと、このような問題が発生します。
例えば、以下のようなシナリオ
2人のお客さん(A さんとB さん)がATMで操作を行っている
A さんは自分の口座から10000円引き出し、同時にB さんの口座に5000円預け入れしようとしている
B さんは自分の口座から20000円引き出し、同時にA さんの口座に20000円預け入れしようとしている
この時、ATMはA さんの口座にロックをかけ、B さんの口座にもロックをかける
A さんの引き出し処理が進行中でB さんの預入れは待機状態になり、
一方で、B さんの引き出し処理が進行中でA さんの預入れは待機状態になる
お互いにロックを解放するのを待っているため、両方の処理が完了できなくなり、デッドロック状態が発生してしまう
このように、お互いの処理が依存し合っている場合、ロックの取得順序によってデッドロックが発生する可能性
この例では、A さんとB さんがお互いの口座を操作しようとしており、処理の順序によってデッドロックが発生してしまった
こよdデッドロック防止の方法：
フォークを取る順序を固定（小さい番号から取る）
偶数番号の哲学者に初期遅延を導入
リソースの階層化による循環待ちの防止
初期スリープ時間の実装：
偶数番号の哲学者は食事時間の半分待機
奇数番号の哲学者はすぐに開始
これにより、同時にフォークを取ろうとする競合を減少
生命サイクルの実装：
思考→フォーク取得→食事→フォーク返却→睡眠のサイクル
各状態での適切なミューテックス制御
死亡判定と食事回数のチェック
タイムスタンプによる最後の食事時間の管理
安全性の確保：
ミューテックスによる排他制御
死亡フラグのチェック
食事回数の管理
この実装を使用する際の注意点：
必要なメモリの確保とミューテックスの初期化が必要
各哲学者用のスレッド生成が必要
プログラム終了時のリソース解放が必要
こよd・正しい時間の制御
・オーバーシュートを防ぐ
usleep 関数
手軽に利用できるマイクロ秒単位のスリープ関数だ。 ただし、現在は POSIX から削除されているため、利用すべきではない。 MAN も参照。
#include <unistd.h>
int usleep(useconds_t usec);
引数にはマイクロ秒を指定するため、sleep よりも細かな制御ができる。 指定した時間がスケジューラの精度以下の場合は、その制度の数値に切り上げられる。 すでに POSIX から削除され、過去との互換性のために残されている関数なので、新規には利用すべきではないが、 手元で一度書いて捨ててしまうようなテストに使うのであればよいだろう。
useconds_t 型は 0 ～ 1000000 を表現する形のため、 1000000 以上を指定するとエラーとなるシステムもあるとのことなので注意しよう。
こよ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
-
こよdsequenceDiagram
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
死亡を検出したときに、シミュレーションがまだ終了していない場合 (simulation_end == false):
cCopyif (!philo->data->simulation_end)
{
// 最初に死亡条件を満たした哲学者
philo->data->simulation_end = 1;
// 死亡メッセージを表示
printf("%lld %d died\n", ...);
return (1);
}
「最初の」死亡検出をしたら、
シミュレーション全体を終了させる
死亡メッセージを1回だけ表示
他の哲学者に終了を通知
死亡を検出したときに、シミュレーションが既に終了している場合 (simulation_end == true):
cCopy// 別の哲学者が既に死亡している場合
pthread_mutex_unlock(&philo->data->sim_end_mutex);
他の哲学者が既に死亡しているときは、
追加の死亡メッセージは表示しない
そのまま終了処理に移行
理由；
死亡メッセージは1回だけ表示される
複数の哲学者が同時に死亡条件を満たしても混乱しない
シミュレーション終了は1回だけ
全ての哲学者が同じ終了条件を参照
最初の死亡検出後、他の哲学者も順次終了
全てのスレッドが適切に終了処理を実行