LoginSignup
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

@42yliu

philosopherとは何だったのか

Last updated at Posted at 2025-01-21

この記事は、並列プログラミングにおける古典的な有名問題である食事する哲学者の問題をとある学校の課題の制約下で解く際に行った思考を列挙したものです。
タイトルのphilosopherというのは本来、哲学者という一般名詞の英語ですが、ここでは某学校で課された課題名を指しています。

※この記事は某校の在校生向けです。一般に食事する哲学者の問題に関しての参考になる可能性は低いです。
※この記事でのデットロックはリソースデットロック(resource deadlock)を指します。

よくある誤解について

  • 競合とデットロック
    • データ競合(data race)と競合状態(race condition)とデットロック(deadlock)は全く異なる概念です。コードはかけているのにも関わらず混同しているケースがありました
  • プログラムを手で動かしてちゃんと動いたので問題なし
    • そうとは限りません
    • 将来的に重大なバグを発生させる可能性があります
  • valgrind等のツールで確認してエラーが無かったので問題なし
    • そうとは限りません
    • 将来的に重大なバグを発生させる可能性があります
  • valgrind等のツールで確認してエラーが出たので問題あり
    • そうとは限りません
  • あまりよく理解できていないけどコードが完成したのでとりあえずレビュー出す
    • クリアしたレビュワー側も理解していないケースが散見されます
    • なんとなくパスしてしまい、実りのないレビューの悪循環に加担してしまう可能性があります

この記事の目標

  • 並列プログラミングにまつわるいくつかの概念や注意点を断片的に学ぶ

思考の列挙

スレッドという新概念
復習として、プログラムはHDDなどの二次記憶からメモリ上に呼び出され実行されますが、その時の実行単位をプロセスと呼びます。
pthread_create()という関数はスレッドというプロセスに内包される実行単位を作成します。１プロセス内で複数のスレッドを作成することができ、それらは複数の処理を同時に並列実行できます。すごい。しかしその反面純粋な疑問も湧きます。

  • 並列実行とは何なのか？
  • 同一データ領域へのアクセス（読み込み・書き込み）はどうなるのか？

一つずつ見ていきます。

  • 並列実行とは何なのか？

OSにより複数のスレッドから実行されるスレッドが選ばれ、そのスレッドの一部又は全部が実行された後、実行処理が中断し、別のスレッドの一部又は全部が実行されるという流れ（スケジューリング）を繰り返すことです。

  • 同一データ領域へのアクセス（読み込み・書き込み）はどうなるのか？

よくなさそうです。ここでのアクセスは少なくとも１つが書き込みであるとします。実際、何も対策をせずに実行するとWARNING: ThreadSanitizer: data race (pid=21584)のような毒々しいエラーが出現したりします(しなかったりします)。

そこで使うのが同期プリミティブ1です。まずはmutexと呼ばれる、最も基本的な同期プリミティブの１つを見てみます。mutexはmutual exclusionの略で文字通り排他制御に使います。一番簡単な使い方として、以下のように同一のデータ領域へのアクセスが発生する箇所を、pthread_mutex_lockという関数とpthread_mutex_unlockという関数で挟んであげるとデータ競合は解決します。トイレに鍵をかけるイメージです。引数にはpthread_mutex_init関数によって初期化したmutex変数のポインタをとりますが、とりあえず気にしなくて大丈夫です。

pthread_mutex_lock(mutex);
// 同一データ領域へのアクセス
pthread_mutex_unlock(mutex);

ここで、データ競合(data race)とは同一データ領域への複数のスレッドによる並列アクセスが発生することを指します。
クリティカルセクションとはpthread_mutex_lockとpthread_mutex_unlockに挟まれたコードセクションを指します。
mutexは不可分なコード実行を強制し、データ競合を防いでいます。このアトミック性はデータ競合以外にもスレッドの競合状態を防げます。アトミック性とは他のスレッド処理が割り込まないことをいいます。スレッドが競合状態(race condition)にあるとは、より広い概念でスレッドの実行順番の非決定性によって特に複数の異なる実行結果が発生しうる状態を指します。
競合状態が発生しても実装上問題無いと判断しているか、意図せずに競合状態を発生させてしまっているかは違います。

競合状態の例
bool safe_is_game_running(t_info *i)
{
    pthread_mutex_lock(i->mutex);
    bool is_game_running = i->is_game_running;
    pthread_mutex_unlock(i->mutex);
    return (is_game_running);
}

void hogehoge() // executed in multi threads
{
    ...
    if (safe_is_game_running(t_info *i))
    {
        // execute under false condition of game running
    }
    ...
}

if文の中のコードの実行中、is_game_running == trueが真とは限りません。共有リソースのis_game_runningが別のコード上で変更されているかもしれないからです。その競合状態を許容するかどうかはコードの内容によります。許容しなければクリティカルセクションをmutexで保護します。
ここまでで、mutexの基本的な使い方を理解できたと思います。もう少しmutexについて考えてみます。

  • 意識の持ち方として、mutex変数はスレッドを保護すべき？コードセクション（クリティカルセクション）を保護すべき？共有リソース（変数やデータ構造）へのアクセスを保護すべき？

スレッド全体の実行をmutexで保護しているコードを見かけました。mutex変数は何を保護しているという意識を持ったほうが認識として良さそうなのでしょうか。個人的にはクリティカルセクションの保護と共有リソースへのアクセスだと思っています。mutexとは不可分な実行という取り決めであり、並列実行を損なう処理をしています。よって、クリティカルセクションは必要最小限であるべきです。これによって競合状態を避けられます。一方で、共有リソースへのアクセス以外の処理にmutexは不要です。よって、ある共有リソースに対応するmutexを構造体で定義する、というのが一般的には良いプラクティスだと思いました。

実際、東京大の田浦先生の「オペレーティングシステム」のスライドにも構造体を使った記述があるのを教えてもらったので同期を隠ぺいしたデータ構造はとても良いプラクティスだという確信が高まりました。

typedef struct {
    int x;             // 更新される変数
    pthread_mutex_t m; // x を守るための mutex
} counter_t;

実際はさらに汎用ポインタを使ってGo言語のイベントで習ったようなChannel型もどきの簡素なAPIを作りました。

  • mutex変数とその制御対象変数はどこに保存するのが良いか

スレッド作成時に呼び出すpthread_create()にはそのスレッド開始時実行される関数ポインタに加え、その関数の引数となる汎用ポインタを指定します。この汎用ポインタに構造体を定義し、そのフィールドにmutexの制御対象変数を定義する人が多いです。しかし、この制御対象変数は共有リソースの顔があることを考えるとこの配置は少し不自然です。共有リソースであるからには別のスレッドからも参照されるからです。これはこうもり問題に近いと思いました。
さらにmutexの制御対象変数にも二種類ありそうだと感じました。具体的には哲学者が使用するフォークであれば、まったく同一の働きをする異なるスレッドからのアクセスが発生するため、それぞれのスレッドから見ても中立的な共有リソースです。しかし、実装にもよりますが哲学者が食べた回数などの共有リソースは、哲学者スレッドと、死亡を検知するためのモニタースレッドのような存在とでは、アクセスパターンが異なります。この場合、フォークと違って、どちらかのスレッドがその変数を所有している、という感覚になりがちです。例えば、哲学者の食べた回数は哲学者スレッドに関連する構造体に所属していそう、などがそうです。しかし、これは変数が別スレッドからアクセスされうるという共有リソースの特徴からして間違いが発生しやすい定義だと思いました。
結果的には、共有リソースはどのスレッドにも関連しない構造体の共有リソース用のフィールドに定義することとしました。

  • pthread_create()の作成時間が気になる

pthread_create()自体も当然時間コストがあります。スレッド数が多いとナイーブな実装では哲学者スレッドの実行開始にズレが生じます。これは本来想定していた動きではないです。これを解決する同期プリミティブがバリア同期です。mutexだけでもsemaphoreだけでも擬似的なバリア同期を作れます。処理の開始を実行時間を１秒後とかに闇雲に設定するより確実です。並列処理っぽいプラクティスであり、並列の課題に取り組んでる感がでます。

  • 一通り完成したけど隣接する哲学者がどちらもthinking状態に入るようなテストケースで死ぬ可能性がある

公平なリソース分配に関する問題です。現状の非決定的で人間から見たら次に実行されるスレッドを予測するのは難しいコードではなく、プログラム自体にスレッドの優先順位を決めると解決しそうです。具体的にはChandy/misraの解法やcourteous philosopher's algorithmなどが参考になります。リソースに追加の属性を加え、その値をチェックすることで前回使用者の哲学者が隣接哲学者を差し置いて処理を続行しないようにする仕組みです。
一番簡易な解決方法は隣接する哲学者のうち、先にthinking状態に入った哲学者が先にforkを取得できるように、後からthinking状態に入った哲学者が一定時間のusleepすることです。つまり、どの哲学者もsleeping状態後に、さらにある程度の時間だけusleepを追加で行うというものです。これは恣意的な解決法ですが、課題をパスするのには有効です。しかしこれは分散型のアルゴリズムっぽくはなく、中央集権的な解決法でもあります。

  • これでデットロックは防止されている（？）

デットロックの防止に自信があるなら以下のリンクの５問はすぐ解けると思います。
https://shinh.hatenablog.com/entry/20140601/1401561716

デットロックがこれによって防がれると主張するケースがありました。デットロックの防止(prevension)とは無関係です。デットロックの回避(avoidance)と勘違いしている可能性もあります。この辺りを整理します。まずデットロックの発生の必要条件を調べると以下の４つが全て成立しているとあります。

  • Mutual Exclusion
    • 一度に1つのプロセスのみがリソースを使用できる
  • Hold and Wait
    • なにか一つのリソースを保持したまま他のリソースを待つ
  • No preemption
    • リソースの横取りができない
  • Circular wait
    • リソースの保持待ちが循環している。あるP1がP2によって保持されているリソースを待ち、P2がP3に保持されているリソースを待ち...が循環する。破るにはリソースの階層化を目指す。グラフ理論の閉路の有無の問題に帰着できそう

これはCoffman's conditions(Coffman et al. (1971))として知られています。
必ず発生するわけではなく、この４つが全て成立しているとデットロックが発生しうる条件のことです。よって、冒頭に書いたように、「ツールでデットロックが検知されないから」や「テストを動かして問題なく動作したから」はデットロックが発生しないことの説明にはなりません。
今回の課題の制約上このうち２つの条件しか破れません。逆に言えばその条件以外の部分がデットロックの防止に関係することはありえません。
俯瞰するとデットロックへの対策はいくつかに分類できます。

  • 対処分類
    • 発生させない
      • 防止（理論的に発生させない）
        • Coffman conditionのいずれかを破壊
      • 回避（理論的には発生しうる）
        • Banker's Algorithmなど
    • 検知する
      • 発生後にシステム側で対処する
    • 検知しない
      • Ostrich Algorithmの一種
        • 発生頻度が低い場合に効率的でオーバーヘッドが少ない
        • アプリケーション側の責任とする
        • 発生したら最終的にシステムが停止し再起を要する

基本的には上に行くほど望ましい対策だと思っています。デットロックの回避に使われるbanker's algorithmをもう少し詳しく見てみます。これはデットロックを起こさないプロセスの実行順序、安全列(safe sequence)を決定するものです。少なくとも一つの安全列が存在するならば安全状態(safe state)と呼び、安全状態であればデットロックは回避できるとしています。わかりやすい例として、インスタの広告とかによく出てくる小さい順に数字のついた魚とか敵を取り込んでキャラクターを成長させるゲームはリソースが１種類の安全列の探索だと見なせます。魚の数値を必要リソースとし、自キャラの数値を使用可能リソース、使用可能リソースが許容できる必要リソースを要求するプロセス(魚)から処理していくとします。解放されたリソースを吸収することで使用可能リソースが増え、より大きな魚を処理できます。これがbanker's algorithmです。その名の通り、銀行が資金繰りに詰まらずに融資を行うイメージです。
デットロックの対策として防止と回避は違う概念です。この２つを混同しているケースが多かったです。これは例えるならば、数学関数における定義域エラーおよび値域エラーを防止または検出するにおける、定義域エラー(や極エラー)と値域エラーに対する対応の違いに相当します。

定義域エラーや極エラーを防ぐ方法は、数学関数を呼び出す前に引数の範囲検査を慎重に行い、範囲を超える場合にはそれに対処することである。

値域エラーは通常、未然に防ぐことができない。なぜならば浮動小数点数や使用する関数の実装に依存するからである。 値域エラーを未然に防ぐよりもその発生の検知に努め、値域エラーが発生した際には別の対応を行うべきである。

デットロックを防止したコードでなければ、デットロックが必ず起きないということを証明することは困難です。デットロックの回避はあくまで実行上行われるものであり、実行時に回避できない可能性もありえます。つまり、発生頻度を低くするのがデットロックの回避であり、発生可能性をゼロにはしません。並列プログラミングについて調べていると、何千回は正常動作したコードが突然動かなくなり調べてみるとデットロックによるものだったというケースがあります。よって、デットロックを回避するのではなく、防止するのが望ましい向き合い方であり、防止ができない場合、回避（や検知）しているコードであることを強く認識する必要があると思います。
この部分の確認がレビュー項目になかったり、在校生同士の情報交換において曖昧だったりしているのはあまり良く無いと思っています。並列プログラミングにおけるデットロックはおそらく重箱の隅のような知識ではなく一丁目一番地のようなとても重要な概念のように感じられるからです。

  • bonusでのデットロック

デットロックの話題ついでにbonusのデットロックについてはここに書いておきます。bonusでデットロックが防止されていないコードも多いです。Coffman's conditionsの循環待機の構造が見えにくいのも原因の一つだと思います。mandatoryの古典的な食事する哲学者の問題では、循環待機をそのまま可視化したような問題設定だったのでかなりわかりやすくなっていて、それが古典的な有名問題たる所以なのかと思いました。この課題を調べる前は、奇妙な問題設定だと思っていただけに、循環待機やCoffman's conditionsを理解してからは腑に落ちました。より複雑な並列プログラミングにおけるデットロックを防止するためにResource Allocation GraphやDeadlock Trajectory Graphを描いたりするのでしょうか。あまり詳しくは無いです。

原因はデッドロック、データが滞留して停止--JALシステム障害
https://japan.zdnet.com/article/35080846/

この例のように２者が２つのリソースでデットロックを起こすことをHacker's Dictonaryでは死の抱擁（deadly embrace）と呼んでいます。

DEADLY EMBRACE n. Same as DEADLOCK (q.v.), though usually used only when exactly two processes are involved. DEADLY EMBRACE is the more popular term in Europe; DEADLOCK in the United States.

  • ライブロック

他にもライブロックがあります。知っておく必要があります。ざっくり言うと、デットロックは状態遷移が発生しないことで、ライブロックは状態遷移が無限に周期性のある遷移をし続けた結果、リソース飢餓を起こすことです。今回ライブロックを発生させるにはpthread_mutex_trylockの使用が不可欠ですが、使用可能関数ではありません。ビジーウェイトを使って、"spinlock_mutex_trylock"のような機構を作っている人もいました。これを使うと発生しそうです。その代わり、公平なリソース分配に関する問題に対して、非中央集権的な解法を与えることができそうです。

  • リソース飢餓（リソーススタベーション）

デットロック以外による理由で永遠にリソースを取得できないプロセスが存在することをいいます。デットロックと区別せずに語る人もいるようですが、区別した方が良さそうです。

Modern Operating Systemから抜粋

6.7.4 Starvation
It is worth mentioning that some people do not make a distinction between starvation and deadlock because in both cases there is no forward progress. Others feel that they are fundamentally different because a process could easily be programmed to try to do something n times and, if all of them failed, try something else. A blocked process does not have that choice.

  • デットロック、ライブロック、リソーススタベーション周りのまとめ

まとめると、デットロックは怖い話なので慎重に学ぶ必要があると思います。Modern Operating Systemによると2010年代あたりの理論研究のトレンドとしては分散デットロック"検知"らしいです。つまり、現実世界では必ずしもデットロック防止のみに対策の焦点が当たっているわけではなさそうです。

bonusの話に入ります。bonusではセマフォが使用可能になります。

  • 今回使用するPOSIX名前付きセマフォはファイル

まずPOSIXの名前付きセマフォの実態はファイルなので、heredocの実装時と同様open直後にunlinkするのが良いプラクティスだと思いました。
またプログラム開始時のopen前にとりあえずunlinkしているコードがありました。プログラムが環境に変更を加えようとしている挙動であり、あまり良くは無いと思いました。
またopenオプションの設定で上書き作成になっているコードがありました。これも同様の理由であまり良くは無いと思いました。

  • バイナリセマフォはmutexと同じか

セマフォの初期値が1で必ずsem_wait()とsem_post()を順番に呼び出すとmutexと同じ振る舞いを作ることができます。これをバイナリセマフォと呼びます。mutexとバイナリセマフォは本質的に同一ではありません。同じ振る舞いをすることがセマフォにはオーナー属性はありません(microsoftはオーナー属性ではなくthread affinity(thread親和性)と呼んでいるようです)。オーナー属性とは同期プリミティブにロック操作(pthread_mutex_lock,sem_wait)を行ったスレッドの情報が付随していることです。いいかえると、ロック操作を行なったスレッドのみがアンロック操作を行えます。セマフォにオーナー属性はありません。セマフォの方が自由度が高いです。セマフォはIPCです。IPCは通信です。通信は送受信の二者に非対称性があります。mutexでは排他制御が目的であることから順序、依存関係の情報をもてません。mutexでこれを説明すると、いきなりアンロックを呼び出すことができ、別スレッドのロックを解除できるということです。実際にはmutexでは不可能ですが、セマフォならできます。よってまとめるとバイナリセマフォはコードの書き方次第でmutexと同じふるまいを可能にする、という理解がよさそうです。

  • bonusでvalgrindによりセマフォが正常に破壊されていないとエラーが出る

実装によりますが、例えで言うとプロセスの終了は家の解体作業であり、セマフォなどの内部のリソースの解放忘れや意図的な未解放は冷蔵庫のドアが開いたままになっている状態に似ていると考えています。状況によってはリソース消費が問題になるケースとそうで無いケースがあるのではと思います。

  • ポーリング(ビジーウェイト)は避けられないのか？

今回、mandatory,bonus両方で、課題要件を確実にクリアするためにビジーウェイトを多用しました。イベント駆動ではないことから個人的には違和感があります。ビジーウェイトはCPUリソースの消費電力増加するからです。あまりスマートではありません。よって、ビジーウェイトによるポーリングを回避するために他の方法を探しました。偶然、知識として条件変数(conditional variable)という同期プリミティブを知っていました。mutexが共有リソースとペアで使うように、条件変数は共有リソースとmutexの３つのペアで使用します。共有リソースの状態変化を検知することができます。哲学者が死んだか一定時間検知するpthread_cond_timedwait()があれば、ビジーウェイトによるポーリングをせずに実現できそうです。しかし、条件変数を作る方法は分かりませんでした。上記の議論からmutexはセマフォで作ることができるのは自明です。a little book of semaphoreという本によるとセマフォから様々な同期プリミティブ（バリア同期など）を作れるらしいということがわかりました。しかし、その中に条件変数はありませんでした。田浦先生のスライドによると、

多くの同期のためのデータ構造（有限バッファ, バリア同期, セマフォ）は「排他制御 + 条件変数」で実現できる

とあります。この命題は、「排他制御 + 条件変数」でセマフォが作れることを示せれば、a little book of semaphoreに書かれている内容と照らし合わせることで、真と言えそうです。そしてそれは、それほど難しくはなさそうです。

一方、条件変数はセマフォと不可分更新命令という低レイヤーの命令から作れるらしいことがわかりました。課題の制約下で、無理やりインラインアセンブリを使えば不可分更新命令とセマフォで条件変数が作れそうではありますが、それはpthread_cond_wait()に過ぎず、pthread_cond_timedwait()には結局busy waitに近いwhile loopが必要そうという結論になりました。

おわりに

  • この文章には定義の循環参照が含まれているという指摘を受けました。
    循環待機のようなものです（？）。どの箇所でしょう。2

  • 当方、コンピュータサイエンスを学んでる途中の素人です。間違いがあればご指摘お願いします。

参考資料

  1. (basic) synchronization patternとも呼ばれ、他にも様々な仲間がいます。バリア同期、条件変数... ↩

  2. クリティカルセクションの定義が循環参照しています。クリティカルセクションは正しくは同一データ領域にアクセスが発生するコードセクションを指し、この部分をmutexで保護する必要がある、という理解が正確です。 ↩

0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?