Philosophers を
理解するためのスライド
作成者：nfukada（nafuka11）
おしながき
2
Philosophersとはどんな課題か
3
Philosophersとはどんな課題か
「食事する哲学者の問題」に似た問題
4
食事する哲学者の問題
円卓に哲学者が座り�食事 → 思考を繰り返す
食事には2本のフォークが必要
フォークは1本ずつしか取れない
食事と思考を続けられるか？
Benjamin D. Esham / Wikimedia Commons, CC 表示-継承 3.0, https://commons.wikimedia.org/w/index.php?curid=56559による
5
食事する哲学者の問題
食事と思考を続けられないパターン
Benjamin D. Esham / Wikimedia Commons, CC 表示-継承 3.0, https://commons.wikimedia.org/w/index.php?curid=56559による
6
42のPhilosophers：ルール
食事 → 睡眠 → 思考
7
42のPhilosophers：引数
引数で以下の情報を与える
オプション引数
例：プログラム名 3 600 300 400
8
42のPhilosophers：哲学者の死
シミュレーション開始時間 or�食事開始時間からの�経過時間が死ぬ時間を超えると�哲学者は死ぬ
哲学者が死ぬと�シミュレーションは終了
哲学者が死ぬ例
9
42のPhilosophers：
ログ出力
タイムスタンプ�哲学者の番号�行動
を標準出力に出力
# ログ出力例
# 3人の哲学者
# 死ぬ時間410ms 食べる時間200ms 考える時間200ms
1619187283000 2 has taken a fork
1619187283000 2 has taken a fork
1619187283000 2 is eating
1619187283001 1 has taken a fork
1619187283200 2 is sleeping
1619187283200 1 has taken a fork
1619187283200 1 is eating
1619187283200 3 has taken a fork
1619187283400 2 is thinking
1619187283400 1 is sleeping
1619187283400 3 has taken a fork
1619187283400 3 is eating
1619187283400 2 has taken a fork
1619187283410 2 died
10
各課題のルール
11
| philo_one | philo_two | philo_three |
複数の処理を並行して 行う方法 | スレッド | スレッド | プロセス |
共有するデータへの�アクセスを制御する方法 | ミューテックス | セマフォ | セマフォ |
フォークの配置 | | | |
⚠️注意
古い課題に沿った内容です
philo_one が現在の philo 相当�philo_three が現在の philo_bonus 相当です
必要な知識
複数の処理を並行して行う方法（並行/並列）
共有するデータへのアクセスを制御する方法（排他処理）
12
並行/並列
13
並行と並列
並行：複数タスクを非逐次的に実行
並列：複数タスクを同時に実行
14
なぜ処理を並行/並列させるか
// 逐次処理もできると思うけど、複雑になってしまう
�if (哲学者1 == 食事状態)
{
if (哲学者2 == 食事状態)
{
// 哲学者2の食事処理
}
else if (哲学者2 == 睡眠状態)
{
// 哲学者2の睡眠処理
}
...
}
15
なぜ処理を並行/並列させるか
タスクごとに並行/並列で実行させると、複雑さを軽減できる
並列実行できる環境なら、逐次処理よりも処理速度が向上する
並行/並列で実行する方法として
マルチプロセス、マルチスレッドがある
16
プロセスとは
実行中のプログラム。psで一覧を見られる
17
PID TTY TIME CMD
61440 ttys001 0:00.14 -zsh
61584 ttys001 0:00.00 -zsh
61585 ttys001 0:00.00 -zsh
.� .
.
マルチプロセス
OSはプロセスごとにCPUを使う時間を割り当てている
�C言語では、fork() を使ってプロセスを複製し、
マルチプロセスなプログラムが作れる
18
forkの使い方
void fork_process(void)
{
pid_t pid;
pid = fork();
if (pid < 0)
エラー処理
if (pid == 0)
複製したプロセス（子プロセス）で行う処理
else
複製元のプロセス（親プロセス）で行う処理
}
19
forkで起こること
メモリ空間、�ファイルディスクリプタテーブル�などがコピーされる
→ 変数の値がコピーされる
親プロセス(1000)が�子プロセスを(1100)をforkした場合
20
スレッドとは
1つのプロセスで複数の処理を�並行/並列に行うための仕組み
21
スレッドとは
プロセスの違い
→ 変数を共有できる
22
スレッドの使い方
スレッドの作成
スレッドの終了：2方法
23
スレッドの使い方
void *do_something(void *arg)
{
printf("do something\n");
sleep(1);
}
int main(void)
{
pthread_t thread;
void *retval;
// スレッドを作成
if (pthread_create(&thread, NULL, do_something, NULL) != 0)
// エラー処理
return (0);
// スレッドの終了方法
// 1. スレッドが終了するまで待つ
pthread_join(thread, &retval);
// 2. スレッドを待たない
pthread_detach(thread);
}
24
変数を共有するときの問題点
複数同時に共有データへ�アクセスすると不整合が発生
共有データへのアクセスを�制限する必要がある
→ 排他制御
例：3本のフォークを2つのスレッド� で1本ずつ減らす
25
排他制御
26
排他制御とは
共有するデータに同時に�アクセスして不整合が�起こらないようにする仕組み
今回は
を使う
27
ミューテックス
pthreadで用意されている排他制御の仕組み
mutex：mutual exclusion (相互排他) の略
ミューテックスにロックをかけることで、�1つの処理だけ通れるようにする
28
ミューテックスの使い方
初期化
リソース解放
ロック（他の処理を制限）
ロック解除
29
セマフォ
排他制御の仕組みの一つ
個数つきミューテックスのような物
ミューテックスと違い、指定個数�だけ同時にロックを獲得できる
30
セマフォの使い方
セマフォの初期化・オープン
セマフォを削除
セマフォをロック（数を1つ減らす）
セマフォのロック解除�（数を1つ増やす）
31
排他制御の注意点
排他制御をかける順序によっては�デッドロックが発生する
デッドロックとは？� それぞれの処理が� それぞれが取得するロックの解除� を待つ状態
デッドロックが発生しないよう、�排他制御をかける順序を工夫する
デッドロックの例
Benjamin D. Esham / Wikimedia Commons, CC 表示-継承 3.0, https://commons.wikimedia.org/w/index.php?curid=56559による
32
Philosophersの実装
33
philo_one
各フォークをミューテックスで表す
アルゴリズム� 右 → 左の順にフォークを持つ
デッドロック対策� 奇数の番号の哲学者だけ� 200μs待つ
34
usleep
🍝
💤
🍝
💤
🍝
philo_one
死亡監視� 監視用スレッドを立てる
35
philo_two
フォークをセマフォ1つで表す
アルゴリズム� ウェイターの許可を得た哲学者� のみ2本のフォークを取れる
死亡監視� 監視用スレッドを立てる
36
🍝
🍝
💤
philo_three
philo_twoとほぼ同じ
プロセスはメモリ空間でデータを�共有できない
プロセスの戻り値を使って�哲学者の死を通知
死亡したら全てのプロセスをkill
37
参考文献・サイト
38
おしながき
39
ありがとうございました！
不明点などありましたら、Discordにてお願いします
40