futexの内部動作とユーザ空間ロックの実装

futexが解く問題──「速い」ミューテックスとは何か

ミューテックスに求められる性能には、相反する2つの要求があります。競合していないとき（ほぼ毎回）は限りなく軽く、しかし 競合して待つことになったときはCPUを焼かずに眠る こと。

素朴に作ると、このどちらかを諦めることになります。毎回カーネルにロックを依頼すれば確実に眠れますが、システムコール のたびにユーザ／カーネルモード遷移のコストを払い、競合していなくても遅くなります。逆にユーザ空間でひたすら spin すれば軽いものの、長く待つ場合にCPUを無駄に焼き続けます。

futex（fast userspace mutex） は、この対立を「分業」で解きます。発想は単純です。

• ロックの状態そのものは、ユーザ空間の共有メモリ上の1ワード（int）に置く。獲得・解放はアトミック命令（CAS など）でユーザ空間だけで行う。
• カーネルが受け持つのは 「眠る」と「起こす」だけ。すなわち、競合して本当に待たなければならなくなったとき、そのときに限ってシステムコールを呼ぶ。

つまり 非競合パスはユーザ空間で完結し、システムコールは1回も呼ばれません。カーネルは「待ち行列の管理人」に徹し、ロックの値の意味（0が空き、1が保持、など）すら知りません。値の解釈は完全にユーザ空間（libc）側の責任です。

2つのコア操作──FUTEX_WAITとFUTEX_WAKE

futexシステムコールの中心は次の2つです。アドレス uaddr が指すint値を、ユーザとカーネルが共有して見ます。

FUTEX_WAIT(uaddr, expected):
  アトミックに {
    if (*uaddr == expected)   // 期待値とまだ一致しているなら
        この呼び出し元を uaddr のwait queueに入れて眠らせる
    else
        即座に戻る（EAGAIN）   // 値が変わっていた＝寝る必要がない
  }

FUTEX_WAKE(uaddr, n):
  uaddr のwait queueで眠っているスレッドを最大n個起こす

FUTEX_WAIT の expected 引数が、この設計の肝です。これは 「私はさっき値がXだと見て、競合していると判断した。本当にまだXのままなら眠る」 という条件付きの眠りです。なぜこの確認が要るのか——次節の取りこぼし問題が答えです。

カーネル側は uaddr（物理ページ＋オフセットから導く一意なキー）をハッシュして、グローバルなハッシュテーブル上のバケットにある待ち行列へスレッドを並べます。futexごとにカーネル内オブジェクトを常駐させるわけではなく、待ち手が現れて初めてカーネルに記録が作られる のも、軽さの一因です。

非競合パス：システムコールゼロでロックを取る

ここからが本題、ミューテックスの実装です。最小のロックは 1ワードで表せます。0 = 空き、1 = 保持中 とします。

lock():
  if (CAS(&val, 0, 1))   // 0なら1にできた＝獲得成功
      return            // ← ここで終わり。システムコールを呼んでいない
  ... (競合時のslow path) ...

unlock():
  val = 0                // 解放
  ... (待ち手がいれば起こす) ...

競合がなければ lock() は CAS 1発で終わり、カーネルには一切触れません。これが「fast userspace mutex」の名の通り、futexの設計目標がそのまま現れる箇所です。ロックを取る圧倒的多数のケース（競合なし）で、モード遷移のコストがまるごと消えます。アトミックなCASがなぜ単独で正しく働くか、その土台は ロックフリー同期とCAS を参照してください。

問題は 解放側です。上の素朴な unlock() は無条件で FUTEX_WAKE を呼びたくなりますが、それでは「待ち手がいない普通のケース」でも毎回システムコールを撃つことになり、非競合パスの軽さが台無しです。待ち手がいるときだけ起こしたい。 そのために状態をもう1つ増やします。

3状態ミューテックス：0・1・2で「待ち手の有無」を表す

glibc の pthread mutex が採る古典的な実装が 3状態（Drepperの手法として知られる）です。1ワードに次の意味を持たせます。

この1ビットぶんの情報（値が2かどうか）で、解放時に「システムコールを呼ぶべきか」を判定 できます。これが3状態の存在意義です。

lock():
  c = CAS(&val, 0, 1)
  if (c == 0) return               // 非競合：即獲得、syscallなし
  // ここからslow path（競合あり）
  if (c != 2)
      c = xchg(&val, 2)            // 「待ち手あり」を宣言（2に上書き）
  while (c != 0) {
      futex(&val, FUTEX_WAIT, 2)   // val がまだ2なら眠る
      c = xchg(&val, 2)            // 起きたら再び2にして取得を試みる
  }

unlock():
  if (xchg(&val, 0) == 2)          // 解放。直前が2＝待ち手がいた
      futex(&val, FUTEX_WAKE, 1)   // そのときだけ1人起こす

注目すべきは unlock() の条件分岐です。直前の値が2だったときに限り FUTEX_WAKE を呼ぶ。値が1（待ち手なし）で保持していたなら、解放は単なる代入で済み、システムコールはゼロです。つまり 競合がなければ lock も unlock もカーネルに触れません。

条件変数をfutexで組む──待ちの取りこぼしを防ぐ

pthread_cond_t（条件変数）も futex の上に作られますが、ミューテックスより一段繊細です。条件変数は必ず 「ミューテックスを解放しつつ眠り、起こされたら取り直す」 をアトミックに行う必要があり、ここに固有の取りこぼし問題があります。

cond_wait(cond, mutex):
  seq = cond->seq            // ① 現在のシーケンス番号を読む
  mutex_unlock(mutex)        // ② ミューテックスを離す（他者がsignalできるように）
  futex(&cond->seq, FUTEX_WAIT, seq)  // ③ seq がまだ同じなら眠る
  mutex_lock(mutex)          // ④ 起きたらミューテックスを取り直す

cond_signal(cond):
  atomic_inc(&cond->seq)     // シーケンス番号を進める（＝状態が変わった印）
  futex(&cond->seq, FUTEX_WAKE, 1)

肝は シーケンス番号（世代カウンタ） です。cond_wait は②でミューテックスを離した瞬間から③で眠るまでの間に、別スレッドが cond_signal する隙があります。もし単純に眠ると、その signal を取りこぼして永久に眠りえます。そこで ①で読んだ seq を FUTEX_WAIT の expected に渡す。②〜③の間に signal が入れば seq が進んでおり、FUTEX_WAIT は「値が違う」と即座に戻る（EAGAIN）——眠らずに済みます。ミューテックスと条件変数を必ずペアで使う作法は、この原子性を成立させるための前提です。排他の全体像は 排他制御とデッドロック も参照してください。

PI futexとロバストfutex──運用で効く拡張

基本のfutexは「眠る・起こす」しか知らないため、優先度逆転や保持者の死に弱いままです。これを補うカーネル支援の変種があります。

PI futexでは、ロックの値そのものにカーネルが意味を持たせ（待ち手の優先度継承を成立させるため、保持者TIDを値に書く規約になる）、基本futexより踏み込んだ協調が行われます。優先度逆転とその影響は プロセスとスレッド のスケジューリングと併せて押さえると理解が進みます。

まとめ──状態はユーザ空間、待機だけカーネル