futexがなければ、無駄である

2025年8月19日原文(h4x0r.org)

概要

The Art of Multiprocessor Programming 第2版の書評と実用性への疑問
futex （Fast Userspace Mutex）の重要性と従来のSystem Vロックとの違い
futexの 仕組み・API設計 ・各OSでの実装例
mutex /スピンロックの基礎・futexを使った実装例
書籍に不足する 実践的な内容 の補完

The Art of Multiprocessor Programming 第2版書評とfutexの重要性

Phil Eaton's book club で扱う書籍は業界評価が高く、2021年にアップデートされた最新版
著者も有名で、 並行プログラミング経験者 としても学びが多いと期待していた
しかし、 futex に一切触れていない点に強い疑問
futexは単なるmutexではなく、 現代の高性能な並行処理の基盤 となるプリミティブ
System V時代の セマフォ中心のロック機構 はスケーラビリティに難あり
Linuxが futex を導入（2002年）、以降Windows（2012年）、macOS（2016年）なども追随
現代のpthread等のシステムライブラリは futexベース の実装が主流

futexの基本と従来ロックとの違い

futex は「fast user-space mutex」の略だが、mutexそのものではなく 並行プリミティブのビルディングブロック
従来（System V IPC）のロックは セマフォ でロックと待機が一体化していた
futexは ロック操作と待機/起床操作を分離 し、柔軟性とパフォーマンス向上を実現
無駄なシステムコール回避 が容易になり、ユーザー空間で完結できる操作が増加
例えば、 unlock時に待機スレッドがなければカーネル呼び出し不要 （System Vでは必須）

futexのAPIと動作概要

futex_wait() ：指定した状態（値）でなければ即失敗、合致すればカーネル内の待機リストにスレッドを登録しブロック
futex_wake() ：指定したメモリアドレスの待機リストからスレッドを起こす。基本は1または全スレッドを起床
WindowsのAPI名「 WaitOnAddress」は本質をよく表現
待機対象は32bit整数（もしくは64bit）。値の意味はOSは関知しない
待機時に 現在値を明示 することで、既に状態変化があった場合に無駄な待機を防止

futexの実装例（Linux/macOS）

atomicな32bit整数型 をfutexとして利用
Linux ではglibcにラッパーがないため、syscallで直接呼び出し
- futex_wait_timespec：状態一致時に待機、タイムアウトも指定可能
- futex_wake：1スレッドまたは全スレッドを起床
macOS では__ulock_wait2/__ulock_wakeを利用（新APIもあり）
- ほぼ同様の機能を提供

mutex/スピンロックの基礎とfutex実装例

書籍は「mutual exclusion」の概念やスピンロックに多く紙面を割く

スピンロック は以下のようにatomic操作で簡単に実装可能

#include <stdatomic.h>
#include <stdint.h>
typedef _Atomic uint32_t h4x0r_spin_lock_t;
static inline void h4x0r_spin_lock_init(h4x0r_spin_lock_t *lock) {
  atomic_store(lock, 0);
}
static inline void h4x0r_spin_lock_acquire(h4x0r_spin_lock_t *lock) {
  while (atomic_fetch_or(lock, 1)) ;
}
static inline void h4x0r_spin_lock_release(h4x0r_spin_lock_t *lock) {
  atomic_store(lock, 0);
}

futexベースのmutex を自作することで、無駄なCPU消費やシステムコールを減らせる

書籍に欠けている実践的内容

futex のような現代的プリミティブの解説不足
実装例やAPIの使い方 に踏み込んだ説明がほぼ皆無
基礎理論と現実世界のギャップ を埋める知識の重要性
理論だけでなく、 OS・ハードウェア・コンパイラの最適化や落とし穴 にも注意が必要

まとめ

The Art of Multiprocessor Programming は理論面で優れているが、 現代的な並行プログラミングの実践 には不十分
futex のような重要プリミティブの理解と活用が不可欠
実装例を通じた学習 が、より現実的な並行処理設計の力につながる

Hackerたちの意見

futexの一番クールなところは、ハンドルがないってことだよね。syscallを使ってメモリの割り当てや解放をする必要がなくて、カーネルベースのメモリウォッチャーがあって、これがすごく便利なプリミティブになってる。待機者がいなくなると、すべてがきれいに片付くし、カーネルは競合がないミューテックスすら見ない。だけど、カーネルがこれをパフォーマンスよく管理する方法について、技術的に深掘りしてみたいな。追記：futex2についても今日学んだよ！ https://docs.kernel.org/userspace-api/futex2.html

└

その通り！同時に、スレッドがロックでブロックされるたびにカーネルの内部malloc()を呼び出したくないよね。そのために、多くのOSはスレッドが作成されるときに「キューオブジェクト」を割り当てて、スレッドオブジェクトからそれにポインタをつけるんだ。スレッドが競合するロックに遭遇したとき、そのキューオブジェクトをそのロックに「寄付」することになる。つまり、1人以上の待機者がいるロックには「キューオブジェクト」のリンクリストがついてることになる。スレッドが起こされると、それぞれがそのオブジェクトを持って出て行く。でも、自分のキューオブジェクトが戻ってくる保証はないし、シャッフルされるかもしれない！だから、スレッドが終了する頃には、そのオブジェクトの1つを解放するけど、それが自分が作ったものとは限らない。最初にこの方法を使ったOSはSolarisだったと思う。そこで彼らはこれを「ターンスタイル」と呼んでた。BSDも同じアプローチを採用して、同じ名前を使ってる。 https://www.oreilly.com/library/view/solaristm-internals-cor... https://www.bsdcan.org/2012/schedule/attachments/195_locking...

└

元々のUnixのカーネル内待機キューもそんな感じだったよ。

はっきりさせておこう。あの本はマルチプロセッサプログラミングを理解するためのもので、いろんなサブドメインに応用できるスキルを育てることを目的にしてる。多くのところで、自分で構造を実装するのは避けて、ライブラリや言語、システムが提供する構造を使うべきだって言ってる。特にミューテックスについてはそう言及されてる。あの本は明らかに並行性についてのもので、特定のプラットフォーム向けじゃない。この記事の著者は、futexについてのまあまあ興味深い記事を書くために、ストローマンを作り上げてると思う。個人的には、このアプローチはちょっと不快だな。誇張された対立の視点からのプレゼンは疲れるし、混乱を招く可能性が高い。この記事は「TAoMPが教えてくれないこと」という視点から書かれてもよかったのに、もっと協力的に受け取られたはずだ。もちろん、このブログは新しいもので、この記事はPhilが投稿したし、Philは以前に他の記事を宣伝してたことも知ってる。

└

この記事を書いたのは僕だよ。読んでた本に触発されて書いたんだけど、僕の見積もりでは、あの本は学者にも実務者にもあまり向いてない。今のアカデミアの大部分に共通する問題だと思うし、業界からも、もっと準備が整った状態で大学を出てほしいという声があるし、マスターの学生からも、自分がなりたいスキルを学べてないって話を聞く。だから、これは「おい、futexについて学ぼう！」っていうストローマンを作るつもりではなかった（他の不満があることからも明らかだよ）。実際、僕はその本にかなり失望したから、別の投稿を保留にしたくらい。Philとは数年前に一緒に仕事をしたことがあって、彼は僕の書いたものを読んでる。僕はただ書き始めたわけじゃないし、過去にオーディエンスを見つけるのに問題はなかったよ、Philがどうこう関係なく。

└

そうそう、前のsysvスタイルを恐竜って呼ばないのは、かつては強かったって意味になるから、まるで巨人の肩に乗ってその頭にうんこしてるみたいだよね。ちょっとした謙虚さが必要なんだよ。

記事にもある通り、WindowsはWindows 8でfutexに似たものを導入したんだよね。元々のWin32クリティカルセクションはカーネルレベルのセマフォに基づいてるって知ってるけど、Vistaで導入されたSRWロックはどうなんだろう？

└

CRITICAL_SECTIONもSRWLockも、競合がないときはカーネルに入らないんだよね。（SRWLockはキー付きイベントに基づいてるし、CRITICAL_SECTIONは最近カーネルオブジェクトを必要に応じて作成するけど、失敗したらキー付きイベントに戻るんだ。）

実際、一般的な実装の間での[再帰ロックの]動作は全く一貫性がない。これが未定義のままにされているのには良い理由がある – それはちょっと難しいから。正直言って、ほとんどの標準が持っているこういう立場は非常にイライラする。「まあ、OSや言語の実装者が機能Xを信頼性高く実装できるとは期待できないから、アプリケーションプログラマーに任せよう；彼らは、結局、素晴らしいスキルセットを持っているし、簡単に回避できるだろう」とか。「まあ、実際に標準を実装する人たちに機能Xを強制することはできない（彼らはこの委員会のメンバーだから）、でも下流のユーザーにその機能がないことに対処させるのも簡単じゃないから、正直言って、あの人たちに何ができるっていうの？ベンダーを切り替えるの？」

└

過剰に仕様を決めると、より良い実装の扉を閉ざしてしまう。例えば、C++の標準ハッシュテーブルや正規表現は、サードパーティ製のものよりも1桁遅いのはそのため。標準は「std::unordered_mapをチェーンバケットと追加のメモリ割り当てを持つハッシュテーブルとして実装しなければならない」とは言わなかったけど、いくつかの保証を指定していて、それがオープンアドレッシングのハッシュテーブルを実装するのを非常に難しくしてる。指定する制約は、より良い実装を排除する可能性がある。再帰的rwlockには、実装方法がたくさんある。エラーチェックを少なくする高性能な実装を排除したいの？

└

この現象についてもっと知りたいなら、こちらを見てね: https://en.wikipedia.org/wiki/Worse_is_better 嫌いだけど、事実だよね。

└

その一部は、再帰ロックを使うべきじゃないってことだと思うから、サポートを指定する意味があるのかな？私の意見だけど。

Hacker Newsで議論の続きを見る

ハクソク