futex: ユーザー空間ロックの核心

カバー範囲: futex(FUTEX_WAIT/FUTEX_WAKE) → pthread_mutex 内部 → PI futex → robust futex → futex2 (6.x) 対象: Linux ユーザー空間, glibc pthread, 任意のランタイム

概要

futex (Fast Userspace muTEX) は、Linux 上のすべてのユーザー空間同期プリミティブの基盤です。pthread_mutex、セマフォ、バリア、Rust の std::sync::Mutex、Go ランタイムのセマフォ——これらすべてが futex を基盤としています。その核心思想は、⁠競合が少ない場合はユーザー空間で解決し（アトミックな CAS）、本当に待機/通知が必要な場合のみカーネルに入ることです。

futex システムコール

#include <linux/futex.h>
#include <sys/syscall.h>

// futex(uaddr, futex_op, val, timeout, uaddr2, val3);

// 待機: *uaddr == val の場合 → 待機してスリープ
syscall(SYS_futex, uaddr, FUTEX_WAIT, val, NULL, NULL, 0);

// 通知: uaddr で待機中のスレッドを最大 val 個まで通知
syscall(SYS_futex, uaddr, FUTEX_WAKE, val, NULL, NULL, 0);

// 待機 + アトミック操作 (FUTEX_OP):
//   *uaddr2 == val3 の場合 → uaddr2 += op → その後 uaddr で FUTEX_WAIT

pthread_mutex 内部: futex の古典的パターン

// glibc: nptl/pthread_mutex_lock.c (簡略化)
// 状態: 0=空闲, 1=ロック済み (待機者なし), 2=ロック済み (待機者あり)

void pthread_mutex_lock(pthread_mutex_t *m) {
    // 高速パス: CAS でロックを取得 (ユーザー空間, システムコールなし!)
    int old = 0;
    if (atomic_compare_exchange_strong(&m->__lock, &old, 1))
        return;  // ロック取得済み! システムコールゼロ

    // 低速パス: 誰かがロックを保持中
    // ロックを 2 に設定 (unlock に通知: 待機者がいるため futex_wake が必要)
    if (atomic_exchange(&m->__lock, 2) == 0)
        return;  // ロックが交換時に空闲になった → 取得成功

    // 本当に待機が必要:
    while (atomic_exchange(&m->__lock, 2) != 0) {
        // FUTEX_WAIT_PRIVATE: 同じプロセス内 → mm_struct の検索不要
        futex_wait(&m->__lock, 2, NULL);
    }
}

void pthread_mutex_unlock(pthread_mutex_t *m) {
    // ロックが 1 の場合 → 0 に戻す (待機者なし) → futex_wake 不要!
    if (atomic_exchange(&m->__lock, 0) == 1)
        return;  // アンロック成功! システムコールゼロ

    // 待機者がいる (ロックは 2) → 通知が必要
    futex_wake(&m->__lock, 1);  // 待機中のスレッドを 1 つ通知
}

分析

競合なし: lock + unlock で全体として 2 回の atomic CAS → ~20ns → システムコールゼロ!
軽度の競合: lock が低速パス、unlock に待機者なし → 1 サイクルあたり 1 回の futex_wake
重度の競合: lock が常に待機状態 → 1 サイクルあたり 1 回の futex_wait + 1 回の futex_wake

これが「ロックは遅い」のではなく「ロック競合が遅い」理由です

PI futex: プライオリティ継承

// 問題: 高優先度スレッドがロックを待っている → 低優先度のロック保持者が中優先度スレッドにプリエンプトされる
//       → プライオリティインバーション (Mars Pathfinder 1997)

// PI futex: ロック保持者を、待機者の中で最も高い優先度に一時的に昇格
pthread_mutexattr_setprotocol(&attr, PTHREAD_PRIO_INHERIT);
// → カーネルの futex(PI) メカニズムが自動的にプライオリティを管理 → リアルタイムシステムに適している

Robust futex: ロック保持者のクラッシュ保護

// 問題: スレッドがロックを保持したままクラッシュ → ロックが永遠に解放されない → 他のスレッドがデッドロック

// Robust mutex:
pthread_mutexattr_setrobust(&attr, PTHREAD_MUTEX_ROBUST);
pthread_mutex_lock(&m);
// EOWNERDEAD が返された場合:
//   → 前のロック保持者がクラッシュした → ロックが「ダーティ」状態
//   → データ構造を確認して修復する必要がある → pthread_mutex_consistent(&m)

futex2: 新世代 (6.x)

// 現在の futex の問題点:
//   - 32-bit の futex word のみ (64-bit が必要な場合は追加のロックが必要)
//   - NUMA を認識しない (通知がリモート NUMA ノードの CPU で発生する可能性がある)
//   - デッドライン対応の待機がない

// futex2 (6.x, 5.x から議論開始):
//   - 8/16/32/64-bit の futex word をサポート
//   - NUMA 対応の通知 (ローカルノードの待機者を優先して通知)
//   - FUTEX_WAIT_MULTIPLE (複数の futex を同時に待機、select に類似)

参考

man: futex(2), pthread_mutex(3)
ソースコード⁠: kernel kernel/futex/, glibc nptl/pthread_mutex_lock.c
LWN: "Futexes are tricky", "The futex2 proposal"
論文⁠: "Fuss, Futexes and Furwocks: Fast Userlevel Locking in Linux" (2002)

キーワード: futex, FUTEX_WAIT, FUTEX_WAKE, pthread_mutex, CAS, PI futex, robust futex, futex2