🎓

Philoメモ

2025/01/14に公開

まえがき

私たちが日常的に使用するシステムの多くで、スマートフォンでの複数アプリケーションの同時実行や、Webサーバーでの複数リクエストの同時処理など、並行処理が活用されています。
今回は、古典的なマルチプロセスの同期(排他制御)問題について取り上げた課題「Philosophers」について
調べたことなどをまとめようと思います。
https://ja.wikipedia.org/wiki/食事する哲学者の問題

課題の目標

  • 哲学者の問題をスレッドとミューテックスを使って実装する。
  • 必須部分の具体的なルールは以下の通り:

概要

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

実装の制約

  • 各哲学者は1つのスレッドを用意する。
  • 各哲学者の間には1本のフォークを用意する。
  • 複数の哲学者がいる場合、各哲学者の左側に1本のフォーク、右側にも1本のフォークがある。もし1人の哲学者しかいない場合、テーブルには1本のフォークしかない。
  • 哲学者がフォークを重複して使用しないようにするため、各フォークの状態を保護するためにそれぞれにミューテックスを使用する。

偉大なる大先輩方の資料

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

最初にこちらの記事を読むことで、実装のイメージができました。
https://wolframike.notion.site/Rank-03-Philosophers-85ca833a133f4393b24d38af4f8a8cd9

ミューテックスってなに

映画館の予約システムを例に、マルチスレッドの概念を理解しました。
マルチスレッドの状況・・・複数の顧客が同時に予約しようとする状況
例えば、
顧客A:映画館のWebページから席を予約しようとしている
顧客B:映画館の専用端末から席を予約しようとしている
顧客C:スマートフォンアプリから予約しようとしている

この状況における重要な要素として、3つあります。

  • クリティカルセクション
  • ミューテックス
  • スレッド

それぞれは、図でいうと以下のような要素です。

  • クリティカルセクション:座席表を確認・更新する処理
  • ミューテックス:座席予約処理の実行権限
  • スレッド:予約をしようとしている人それぞれ

各要素の詳細説明

  • クリティカルセクション
    https://programming.pc-note.net/winapi/criticalsection.html

    並行処理によるデータの不整合の「危険」がある箇所

    • 一度に1つのスレッドしかアクセスできない共有リソース
    • 具体例:共有メモリ、ファイル、データベースなど
  • ミューテックス

    • 排他制御を実現する仕組み(鍵としての機能を提供する)
    • 鍵の獲得(lock)と解放(unlock)を管理する
    • クリティカルセクションへのアクセスを一度に1つのスレッドに制限する
  • スレッド

    • 共有リソースにアクセスする実行単位(例:個室を使いたい人)
    • 待機と実行の状態遷移

参考に調べたサイトで、
https://daeudaeu.com/c_mutex/

Mutex とはクリティカルセクションを1つのスレッドしか進入できない「鍵付きの個室」として扱うことで排他制御を実現する仕組みです。

とありますが、「鍵付きの個室」としての表現は誤解を招きやすいので注意したいです。
ミューテックスとクリティカルセクションが一体化したものと勘違いしやすいからです。
「鍵付き」という表現が、ミューテックスとクリティカルセクションが常に一緒になっているような印象を与えてしまいそう。
実際には、ミューテックス(鍵)とクリティカルセクション(個室)は別個の概念で、
独立した概念であるため、別々に管理します。

たとえば、
「ミューテックスで保護された共有リソース」
「ミューテックスによって制御されるクリティカルセクション」
「鍵(ミューテックス)によって保護される個室(クリティカルセクション)」
と表現したいと思います。

分離して考える必要がある理由としては、
同じクリティカルセクションに対して異なるミューテックスを使用できる
一つのミューテックスで複数のクリティカルセクションを保護することもできる
デッドロック防止など、より複雑な制御を理解する際に概念の分離が重要
が考えられる。

デッドロックってなに

ミューテックスによる排他制御は必要不可欠ですが、使い方を誤るとシステムが停止してしまう危険性があります。

最近でも、デッドロックによる通信障害が発生しニュースになっていたりします。
https://xtech.nikkei.com/atcl/nxt/news/18/06864/

デッドロックの説明と、その予防方法について紹介します。

例えば、
座席の予約には「座席の確認」と「決済処理」の2つのステップが必要とします。
これらのステップは必ずこの順番で実行する必要があります。
各ステップでシステムリソースをロックする必要があります。

ここで、2人の顧客が同時に以下のような操作を行った場合を想像してみます。
顧客A:座席情報をロックし、確認中
顧客B:決済システムをロックし、処理準備完了
顧客A:次に決済処理に進もうとするが、Bによってロックされているため待機
顧客B:座席情報の確認に進もうとするが、Aによってロックされているため待機

この状態で、両者とも永遠に待ち続けることになります。
「デッドロック」と呼ばれる状態です。

https://www.issoh.co.jp/tech/details/4122/#:~:text=デッドロックは、一般的,ことで発生します。

デッドロックは、一般的に4つの条件(相互排他、保持・待機、不可分性、循環待機)が揃うことで発生します。

デッドロックが発生するためには、以下の4つの条件が同時に満たされる必要があります。

  • 相互排他:リソースは一度に1つのプロセス(哲学者)しか使えない
  • 保持と待機:既に持っているリソースを離さずに、新しいリソースを待つ
  • 横取り禁止:他のプロセスが使用中のリソースを強制的に奪えない
  • 循環待ち:プロセス間で循環的な待ち状態が発生している

今回は課題の制約で、使用可能な外部関数が定められています。

  • 使用可能な外部関数:
    - memsetprintfmallocfree
    writeusleep
    gettimeofday
    pthread_create
    pthread_detach
    pthread_join
    pthread_mutex_init
    pthread_mutex_destroy
    pthread_mutex_lock
    pthread_mutex_unlock

そのため、4つの条件のうち3つの状況を発生させることができません。

そのため、本課題においてデッドロックを発生させないようにするためには
4つのうち1つの条件を確実に満たさない実装を行えばよいということになります。
そこで今回は、哲学者ごとに持っているフォークミューテックスで循環的な待ち状態が発生しないような実装を行いました。

デッドロック防止の実装

並列プログラミングにおいて、
今回の実装では、フォークの取得において順序付けによる解決を行いました。
フォークを取得する関数で、1人だけ異なる順序でフォークを取ることで、循環待ちを防ぐことができます。

フォークの場合、例えば以下のような状況で発生します。
①各哲学者が左のフォークを取った後、右のフォークを取ろうとする
②すべての哲学者が同時に左フォークを取ると、右フォークを取得できなくなり、全員が待ち状態になる
③誰も右フォークを取れないため、プログラムが停止(デッドロック!)
1人だけ異なる順番でフォークを取ることで、依存関係が崩れる=デッドロックの原因を排除できていると言えます。

使用禁止関数を使うなら

本課題で使用が禁止されている関数を使うと、強制的なリソース解放が可能な場合があります。

  • pthread_mutex_consistent()
    mutexを不整合状態から回復させる
    ただし、mutex所有者のプロセスが異常終了した場合のみ使用可能

  • pthread_cancel()
    他のスレッドを強制終了させる
    スレッド終了時に自動的にmutexが解放される

  • pthread_kill()
    特定のスレッドにシグナルを送信
    シグナルハンドラでmutexを解放可能

  • pthread_mutex_trylock()
    ノンブロッキングでのmutex取得を試みる
    ただしmutexが既にロックされている場合は取得できない

これらの関数が使用禁止となっているため:
他のスレッドのリソースを強制的に奪うことは不可能
mutexのロック取得は必ずブロッキング操作となる
デッドロック発生時に外部から解決することができない

実装の流れ

全体の実装の流れを図式すると以下のようになります。
(AIに書いてもらったものを修正しました。)
きちんと設計してから、実装に移らないとだめだなーと反省しました。。。

まとめ

この課題では、新しく学ぶ概念について理解することが最初のハードルでした。
課題をクリアした方と話をして、まだまだ理解が浅いなと実感しました。
この課題の特徴として、レビュー項目をクリアすることだけではこの課題の本質部分がクリアされているとは言えないとこが昔から問題になっているようです。
本課題について、学者が死なないようにする実装部分はそれほど重要ではなく、deadlockの回避、dataraceが起こらないようにする原理手法を学ぶこがこの課題の目的であると思いました。
どこまでを考慮して実装するかは実装者自身に委ねられており、課題の要件だけをクリアするために課題を実装することも可能なため、レビューする側によって見る観点が全然違うなと感じた課題でした。
実際のところ、今までシステムの持続可能性や安全性について考えたことはなかったのですが、
並列処理における問題を知ったうえでこの課題に取り組むことは、今後のシステム設計において非常に重要だと感じました。

参考

https://qiita.com/yohhoy/items/00c6911aa045ef5729c6
https://zenn.dev/yohhoy/articles/multithreading-toolbox#🚦セマフォ(semaphore)

Discussion