フューテックスなしでは意味がない

• The Art of Multiprocessor Programming の教科書が フューテックス(futex) の概念を扱っていないのは残念だ、という問題提起
• Futex は現代の並列プログラミングにおける 効率的な同期 の中核要素であり、従来の System V ベースのロックより優れた性能を示す
• フューテックスは ロック獲得と待機/起床機能を分離 し、不要なシステムコールとオーバーヘッドを減らす構造を持つ
• フューテックスを基盤に スピンロック、ミューテックス、再帰ロック などさまざまな並行性プリミティブを直接実装する例と手法の説明が含まれる
• 著者は、この本が実際の エンジニアリング実務に必須の最新同期手法 を扱っておらず、アカデミアと実務の隔たりを指摘している

---

序論

• Phil Eaton が『The Art of Multiprocessor Programming, 2nd Edition』の読書会を始めた
• この本は並列プログラミング分野の権威ある教科書とみなされているが、著者は 内容の実用性の欠如 を指摘する
• 特に、学部4年生と大学院生を対象にしているにもかかわらず、フューテックス(futex)という 中核的な同期手法 を扱っていない点を批判している

フューテックスとは何か — なぜ重要なのか

• フューテックス(futex)は “fast user space mutex” の略だが、実際にはミューテックスというより 現代的なロック実装のための OS 支援同期プリミティブ である
• かつては多くのロックが System V IPC のセマフォをベースに実装されており、効率性とスケーラビリティに限界 があった
• Linux で 2002 年にフューテックスが導入されると、1000 個の同時作業環境で System V ロック比 20〜120 倍高速 という性能を示した
• Windows(2012 年) や macOS(2016 年) など他の OS も同様のメカニズムを導入した
• 今日広く使われている pthreads などのシステムライブラリのロックはフューテックスを利用している

フューテックスの動作原理と違い

• 従来のセマフォはロックと待機を結び付けていたが、フューテックスはロック獲得と待機/起床を分離 する
• これにより 不要な遅延とシステムコール を減らせ、ロック解放時に待機スレッドがいないことが確実ならカーネルに入る必要がない
• フューテックスの待機(wait)呼び出しは「特定のメモリアドレスの値が期待する状態のときだけ待機する」ようになっており、タイムアウトもサポートする
• フューテックスの起床(wake)呼び出しは、特定のメモリアドレスに結び付いた内部待機リストから、望む数のスレッドを起こす
• メモリアドレスの実際の値の検証を要求 するため、すでに状態が変わっている場合の不要な待機を防げる

フューテックスの実用 — 直接実装する

• フューテックスは低レベルのプリミティブであるため、コンパイラおよびハードウェアのメモリ操作順序の問題 を考慮して atomic 型を使う
• Linux では syscall でフューテックスのシステムコールを直接呼ぶ必要があり、macOS では __ulock インターフェースを使う（最近はより簡単な API も追加された）
• 基本的に フューテックス待機は成功時に 0、失敗時にエラーコード（タイムアウトなど） を返す
• フューテックスベースの中核演算:
  • h4x0r_futex_wait_timespec() : 期待値が一致する場合に待機し、タイムアウトを適用可能
  • h4x0r_futex_wake() : 1 個またはすべての待機者を起こす

ミューテックス/スピンロック/再帰ロック実装の実践例

スピンロック

• 最も単純な形のロックで、単一ビット(atomic_fetch_or) のみで動作する
• ロックを得るまで無限ループ（「スピン」）するが、高競合時には CPU の浪費 や誤った解放、再帰呼び出し時のデッドロックの危険など構造的問題がある

ハイブリッドミューテックス（「unsafe」ミューテックス）

• 通常は まずスピンロックで試み、一定回数失敗するとフューテックスに切り替えて効率的なブロッキング を実現する
• 待機者がいなければ不要なシステムコールを避けられ、待機者がいる場合も起床システムコールを最小限にできる
• 厳密な所有権検証や再帰処理は不十分なため、「unsafe」という名称が使われている

待機者カウンタ付きミューテックス

• 1 ビットはロック状態、残りは 待機者数の集計 に使い、不要な起床システムコールの削減を目的とする
• それでも所有権や再帰処理はまだない

所有権管理を含むミューテックス

• pthread_t の値を通じて ロック所有者と状態を明確に追跡 し、誤った unlock や再帰利用時の問題を検出する
• ロック獲得、解放、待機者管理のすべてを 厳密に atomic 演算 で制御する

再帰ロック

• スレッドごとのネスト回数(depth)カウンタ を追加し、同一スレッドによるネストしたロック獲得を可能にする
• unlock 時には depth を減らし、0 になったら実際の unlock と起床を行う
• 各動作は atomic 演算と厳密な所有権チェックで実装される

残された課題と実際のエンジニアリングの現実

• ロック所有スレッドが異常終了・死亡した場合、ロック管理のために 別個の管理リストや終了コールバックなど追加の管理 が必要になる
• プロセス間共有ミューテックスを使う場合でも、状態変化の管理に追加の考慮が必要だ
• POSIX RW ロック は再帰的ネスト動作が定義されておらず実装ごとに異なるため、実際には安全性の確保が難しい
• 著者は、本が実践で本当に重要な並行性の問題（フューテックス、再帰ロック、非同期ランタイムなど） をカリキュラムに含めていない点を批判している

結論

• 『The Art of Multiprocessor Programming』は 歴史的または理論的観点に偏って おり、重要な現代の並列プログラミング実務知識を十分に盛り込めていない
• 実際にシステムで動作する フューテックスなどの中核的な同期要素 を適切に扱わなければ、後進に実質的な害を与える可能性がある
• 著者は、最新概念の反映と実用的内容の補強の必要性を強調している

参考資料

• 全コード例は codeberg で確認できる