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

 (h4x0r.org)
4 ポイント 投稿者 GN⁺ 2025-08-21 | 1件のコメント | WhatsAppで共有
  • 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 で確認できる

関連記事

1件のコメント

 
GN⁺ 2025-08-21
Hacker News の意見

  • Windows には WaitForMultipleObjects という機能があり、Linux でも 5.16（2021年末）に Futex2 としてこれが導入された。
    関連リンク
    最近は Futex2 にさまざまな改善が加えられてきた。
    NUMA サポートもようやく追加された。
    NUMA 関連リンク1
    NUMA 関連リンク2
    NUMA は性能にとって非常に重要な要素だ。
    io_uring が 6.7（2024年）で futex に適用され、postgresql の aio 性能向上に役立った。
    関連記事
    6.7 では Small requeue と single wait 機能も追加された。
    関連リンク

    • Windows は WaitForMultipleObjects 機能を新たに追加したのではなく、30年以上前から最初から備えていた。
      WaitForMultipleObjects は UNIX に対する Windows NT の利点ではあったが、IBM PL/I にも 1965 年の時点ですでに類似機能があった。
      UNIX の wait 関数は IBM PL/I の wait を単純化した版であり、Multics から受け継いだ多くの機能と同様に、元のモデルより弱いものだった。
      MS の WaitForSingleObject と WaitForMultipleObjects も効率的な実装ではなかったため、結局は Linux の futex に相当する WaitOnAddress を導入せざるを得なかった。
      Linux の futex には 32ビットサイズ制約と、単一イベントしか待てないという限界がある。
      原子的ビット演算を活用すれば複数イベント待機を実装できるが、効率が悪く、そのため 32ビットサイズ問題が大きくなる。
      futex に WaitForMultipleObjects の利点を一部組み合わせようとする試みは歓迎したい。
      これは Windows の後追いではなく、実際には Microsoft よりはるか以前、50年以上前からよく知られている古典的手法を再実装するものだ。

    • いまだに futex_swap 機能がないのは残念だ。
      関連議論1
      関連資料2

    • Futex は WFMO（WaitForMultipleObjects）とは関係がなく、むしろ keyed events に相当する概念だ。
      Linux で WFMO に相当する機能は select/poll/epoll だ。

    • io_uring における futex サポートは本当に良い機能だ。
      Ruby fibers と組み合わせる際、mutex と queue の実装に活用した。
      ソースコード参照

  • 本では、同期構造を自分で実装するより、ライブラリ／言語／システムが提供する構造を使うようにと述べられている。
    本の主な焦点は特定プラットフォームではなく、全般的な concurrency の概念にある。
    記事の筆者がやや誇張した対立構図で書いているのは残念だ。
    この記事は「TAoMP が語らないこと」のような、より協調的な視点で扱われていればもっと良かった。
    このブログが新しく立ち上がり、Phil がこの記事を投稿し、Phil が別の記事も宣伝していた点は目につく。

    • その記事を書いたのは私で、本を読んで失望したので書いた。
      学界でも産業界でも、実際に使える内容を学べない現実が問題だと感じた。
      だから「futex を学ぼう！」という意図ではなかった。
      実際、本に失望したせいで他の記事を後回しにして、これを先に書いた。
      Phil とは以前一緒に働いたことがあって交流はあるが、これまで文章を書く上で読者探しに特に苦労したことはない。

    • 以前、sysv スタイルを恐竜にたとえることすらしないと書いた部分は、言い過ぎだったと思う。
      もう少し謙虚さが必要だった。

  • futex の最もクールな点は、ハンドルレス（handle-less）な構造であることだ。
    syscall による割り当てや解放を必要としない、カーネルベースのメモリ監視機構として非常に有用な基本動作を提供する。
    待機中のスレッドがいなければすべてきれいに片付き、競合がなければカーネルは mutex 自体を認識しない。
    カーネルが futex を高性能に管理している仕組みについて、詳しい分析が気になる。
    futex2 については今日初めて知った。
    関連ドキュメント

    • その通りで、さらにスレッドがロックでブロックされるたびにカーネルの malloc() を呼んでデータを確保するような方式は望ましくない。
      これを避けるため、多くの OS では「queue object」をスレッド生成時ごとに割り当てておき、そのスレッドが競合ロックに遭遇したときにそのオブジェクトをロックへ割り当てる方式を採る。
      つまり、複数スレッドがロックに接続された linked list 形式で queue object を持ち、スレッドが起床するたびに 1 つずつ持っていく。
      スレッド終了時に、自分が最初に作ったオブジェクトを取り戻せる保証はなく、途中でオブジェクトは混ざる。
      solaris が最初にこの構造（turnstile）を導入し、BSD もこの方式を採用している。
      solaris internals 参照
      BSD pdf 資料

    • 初期の Unix カーネル内の待機キューもこの方式だった。

  • 2002年のオリジナル futex 論文でも futex の効率性は明確に示されており、1000 個の並列タスクのテストで sysv ロック比 20〜120 倍高速だった。
    ただし、実際にはベースラインは sysv ロックではない。
    実用上、futex のない環境でロックを実装する場合でも、ほとんどは fast path ではカーネルに入らず、slow path でのみカーネル待機に移るので、futex の改善点はロック待機状態を表すユーザー空間データ構造のサイズが小さくなったことだけだ。
    別の選択肢としては thin locks（JVM で使われる方式）や ParkingLot（完全ユーザーランド実装）があり、これらは OS の futex なしでも動作する。

    • 私の経験では、ほとんどの人は実務で提供される基本 primitive を学ぶので、自分の言語の標準ライブラリが何を提供するかに注目することになる。
      つまり sysv から futex へ移ってきた流れが支配的で、最近ではカスタム方式もあるが主流は futex だ。
      もしユーザーランドで独自スケジューラを作るなら別実装も可能だろうが、多くはファイルディスクリプタに書き込み、自前でキュー管理する方式を使う気がする。
      そのやり方にどれだけ利点があるのかは疑問だ。

    • 実際には、どんな現代的ロックでも結局内部では futex（利用可能なら）を使うことになる。
      Linux では futex が最も効率的な待機方式なので、slow（down）path では常に futex を使うのが望ましい。
      言語の thread.park() のようなものも、結局 futex 上で動いている可能性が高い。

    • JVM が今でも thin lock を使っているのか気になる。
      以前、JVM が futex を呼んでいるという参照を見つけたが、thin lock に移行したのか知りたい。
      Stack Overflow 関連議論

  • [recursive locks] の実装は標準間でも一貫性がなく、これが難しいという理由で定義自体をしていない場合も多い。
    この態度はかなりもどかしい。
    「OS や言語実装者は feature X をうまく実装できないだろうから、アプリケーション開発者に自分で処理させよう」という発想だ。
    結局 downstream の利用者には、ベンダー変更以外に有効な手立てがないことになる。

    • 標準に過度な制約を課すと、より良い実装の可能性を閉ざしてしまうことがある。
      たとえば C++ 標準のハッシュテーブルや正規表現は制約が多く、他社実装よりはるかに遅い。
      特定の制約（たとえば chaining 方式しか使えないようにすること）や機能保証を加えると、代替的な高性能実装が阻害される。
      recursive rwlock も、性能を犠牲にしたりチェックを減らしたりする実装があり得るので、さまざまな方向性を塞ぐ必要はないと思う。

    • 個人的には recursive lock はそもそも使わない方がよいので、わざわざサポート仕様を標準に入れる必要は感じない。

    • worse is better という現象をもっと知りたいなら Wiki を参照。
      あまり好きではないが、避けられない現実だ。

  • Linux で futex が 32bit int しかサポートしない制約が気になって調べてみた。
    64ビット対応の議論で Linus は、ユーザー空間で 64ビット atomic を使い、下位 32ビットだけを futex として使えばよいと述べていた。
    だが C/C++ では mixed-size atomic は undefined behavior と見なされ、実際 glibc の semaphore 実装もそう動いている。
    64ビット整数の high 32 を waiter count、low 32 を semaphore 値として使い、下位 32ビットにだけ futex を使う。
    gcc でこれが定義済み動作なのか、それともプロセス境界（カーネルプロセス）のおかげで問題ないのか、あるいは glibc ですら undefined behavior を使っているのか気になる。

  • Anthony Williams の C++ Concurrency in Action も勧めたい。futex や同期 primitive の直接実装方法は扱わないが、メモリ順序や lock-free 構造に必要な SMR など、より実践に近い内容を扱っている。
    さらにハードウェア寄りの視点が必要なら、Paul McKenney の無料書籍 "Is Parallel Programming Hard, And, If So, What Can You Do About It?" もおすすめだ。
    この本も futex を深く扱ってはいないが、Ulrich Drepper の "Futexes Are Tricky" を案内してくれる。
    TAOMPP は高水準の concurrency 概念を学ぶには適しているが、OS レベルの実装詳細まで含めるものではない。
    いずれにせよ Peterson や bakery lock は実用には向かないが、証明だけでも学べば実践的な並行アルゴリズムの理解に大いに役立つ。

    • bakery lock は spin lock 用としては優秀で、キャッシュフレンドリーだ。
      reader/writer spin lock も実装できるが、厳密な FIFO になる。
      ユーザー空間で bakery lock の spin wait に futex を連動させることはできるが、非常に非効率だ。
      futex はこうした用途（スピン待機）のために設計されたものではない。
      lock-free 構造や hazard pointer、RCU* なども依然として tricky だ。
      wait-free hazard pointer も実際に作れる。
      *RCU の場合、copy-on-write は直感的だが、更新頻度が高いとコストが増える。

  • Windows 8 で futex 類似機構が導入されたように、もともと Win32 の critical section はカーネル semaphore ベースだった。
    では Vista で導入された SRW lock はどんな構造なのか気になる。

    • CRITICAL_SECTION と SRWLock はどちらも競合がなければカーネルに入らない。
      SRWLock は keyed event ベースで、CRITICAL_SECTION は失敗時にも on-demand でカーネルオブジェクトを作って呼び出し、keyed event にフォールバックする。

  • 2014年の Linux futex 実装で Pinkie Pie が発見した脆弱性では、requeue-once ルールは futex_wait_requeue_pi に渡された futex に対してのみ許可される。
    A から B へ、その後さらに B から C へ requeue することはできないが、B から B への再指定は可能だ。
    このとき特定条件を通ると cleanup 関数が呼ばれないバグがあり、ポインタが dangling 状態になる。
    関連事例を確認できる。
    関連イシュー

  • crashed thread によるデータ整合性を気にしない人もいるが、プロセス全体が死なない限り、ロックのクリーンアップ問題は残る。
    そのための解決策が robust lock だ。
    held futex のリストをカーネルに登録し、sys_set_robust_list でスレッド終了時にその bit を処理して待機側を起こす。

    • robust lock 方式の最大の欠点は、ロックが保護していたリソース自体がすでに inconsistent 状態かもしれないことだ。
      スレッドがなぜクラッシュしたのか確信が持てないなら、データの整合性が壊れていて復旧不能な可能性がある。
      そのため、アプリ全体を一緒に落とす方が現実的かもしれない。
      robust lock を用いた cleanup/recovery 機能自体は素晴らしいが、おそらく 95% のエンジニアは robust なデータ構造まできちんと設計しないだろう。
      4% はそのための時間が足りず、残る 1% だけが十分な報酬を得ながら適切に実装するのだと思う。

    • 複数プロセス間で futex（クロスプロセス状態）を使う場合は、watchdog プロセスが各プロセスごとに Unix domain socket（SOCK_STREAM または SOCK_SEQPACKET）を開き、クラッシュを検知してプロセス単位の状態をクリーンアップする方式が使える。

    • 自分も mutex の議論をプロセス境界までに留めたのは、深入りすると議論が際限なく広がるのを懸念したからだ。