← OSと低レイヤのしくみ コース
14. futex — 競合しないロックがシステムコールを呼ばない仕組み
ロックを取るとき、なぜ普段はカーネルに降りなくて済むのかを図で追っていきましょう。
① ロック変数はユーザー空間のただの32bit整数
プロセスのユーザー空間メモリヒープ / スタック / 共有メモリのどこでもよい
その中の4バイトを1つ選ぶ
uint32_t lock;これが futex word
4バイト境界に整列必須この整数の値でロック状態を表す
0 = 空き
1 = 取得中
2 = 取得中+待ち手あり
- ・futex(2): 「On all platforms, futexes are four-byte integers that must be aligned on a four-byte boundary.」
- ・整列していないアドレスを渡すと EINVAL が返ります
- ・0/1/2 という値の割り当ては仕様ではなくライブラリ側の取り決めで、カーネルは値の意味を定めていません
futex のロックは、カーネルが管理する特別なオブジェクトではありません。自分のメモリ上にある普通の32bit整数です。
② 非競合パス — CAS が成功すればそこで終わり
スレッドA が lock() を呼ぶ
CPU の不可分命令だけを使う
CAS(&lock, 0, 1)0 なら 1 に書き換える(compare-and-swap)
x86 なら lock cmpxchg誰も持っていなければ成功
成功 → ロック取得完了呼んだシステムコール: 0回
- ・futex(2): 「When using futexes, the majority of the synchronization operations are performed in user space.」
- ・CAS はCPU命令であり、カーネルへの遷移(モード切替)を一切伴いません
- ・futex(2): ロックの生成・破棄に専用の呼び出しは不要で、「no explicit initialization or destruction is necessary to use futexes」とされています
誰もロックを持っていない普通のケースでは、CAS 命令1つで完結します。カーネルには一度も降りません。これが高速パスです。
③ 競合パス — CAS が失敗して初めてカーネルへ
CAS(&lock, 0, 1)
分岐
成功(lock は 0 だった)高速パス
失敗(lock は 0 でなかった)低速パス
失敗側だけが進む
lock を 2 にして「待ち手あり」を記録
ここで初めてシステムコール
syscall(SYS_futex, &lock, FUTEX_WAIT, 2, NULL)lock が 2 のままなら眠る
- ・futex(2) の SYNOPSIS は可変長引数の形 long syscall(SYS_futex, uint32_t *uaddr, int op, ...); で、実際に渡す引数は op ごとに決まります
- ・FUTEX_WAIT(2const) の形は syscall(SYS_futex, uaddr, FUTEX_WAIT, val, timeout) で、timeout に NULL を渡すと無期限に待ちます
- ・単一プロセス内のロックなら FUTEX_PRIVATE_FLAG(Linux 2.6.22 以降)を op に OR して、プロセス間共有向けの処理を省けます
システムコールは「本当に眠る必要が出たとき」だけ発行されます。競合しない限り、この段には進みません。
④ なぜ FUTEX_WAIT に期待値 val を渡すのか
スレッドA: lock が 2 だと確認
スレッドB: 実行中
この隙間で B が動く
A: まだ眠る前確認済みだが未就寝
B: unlock して lock=0、FUTEX_WAKE 発行
もし val の比較がなかったら
A: ここで眠ってしまう起こす合図はもう過ぎ去った
lost wake-up- ・FUTEX_WAIT(2const): 「The purpose of the comparison with the expected value is to prevent lost wake-ups.」
- ・「値を確認する」と「眠る」が別々の操作だと、その隙間の解放を取りこぼします
- ・これは futex に限らず、条件確認と就寝を分けたすべての同期機構が抱える古典的な競合です
確認と就寝の間に他スレッドが解放すると、起床の合図を逃してしまいます。この穴を塞ぐのが期待値 val です。
⑤ カーネルが「読む・比べる・眠る」を不可分に行う
syscall(SYS_futex, &lock, FUTEX_WAIT, 2, NULL)
カーネル内で、この3つが不可分
1. *uaddr を読む
2. val と比較
3. 一致なら待ち行列へ
比較結果で分岐
*uaddr == 2 → 眠る起床は FUTEX_WAKE / シグナル / timeout
*uaddr != 2 → 眠らず EAGAIN状況が変わったので再挑戦
- ・futex(2): 「The loading of the futex word's value, the comparison of that value with the expected value, and the actual blocking will happen atomically and will be totally ordered with respect to concurrent operations performed by other threads on the same futex word.」
- ・値が val と違えば即座に EAGAIN(EWOULDBLOCK)が返るので、呼び出し側はループで再挑戦します
- ・FUTEX_WAIT(2const): 戻り値 0 は spurious wake-up の可能性があるため、起床後もユーザー空間側の値を見て継続を判断する必要があります
眠る直前にカーネル側でもう一度値を確かめ、変わっていれば眠らず戻ります。これで確認と就寝の隙間が消えます。
⑥ 解放側 — 待ち手がいるときだけ FUTEX_WAKE
unlock(): lock を不可分に 0 にする
直前の値を見て判断
直前が 1(待ち手なし)高速パス
直前が 2(待ち手あり)低速パス
2 のときだけ進む
syscall(SYS_futex, &lock, FUTEX_WAKE, 1)val = 起こす数
起こせた数が返る- ・FUTEX_WAKE(2const) の形は syscall(SYS_futex, uaddr, FUTEX_WAKE, val) で、val は「最大で何人起こすか」を表します
- ・FUTEX_WAKE(2const): 「Most commonly, val is specified as either 1 (wake up a single waiter) or INT_MAX (wake up all waiters).」
- ・値 2 の役割は「待ち手がいるかもしれない」という記録で、これがないと解放のたびに毎回システムコールが必要になります
待ち手がいなければ解放も整数を書き換えるだけ。値 2 が「起こす必要がある」ことを解放側に伝えています。
⑦ なぜこの設計なのか — コストを競合時だけに寄せる
ユーザー空間が担当状態(整数)と、その不可分な更新
カーネルが担当待ち行列と、眠らせる・起こす
結果として
競合なし = 大多数CAS のみ、システムコール0回
競合あり = 少数そのときだけ syscall
設計の要点
カーネルは常時の状態を持たない待ち手がゼロなら管理対象も存在しない
- ・futex(2): カーネルは「only while operations such as FUTEX_WAIT are being performed on a particular futex word」の間だけ内部データを保持します
- ・そのためロックを作る・壊すのに専用のシステムコールが要りません
- ・ユーザー空間側は「不要なとき呼ばない」だけでなく「必要なときは必ず呼ぶ」責任も負います
- ・futex は生のシステムコールとして syscall(SYS_futex, ...) で呼び出す前提で、通常は pthread_mutex_* 等が内部で使います
状態はユーザー空間、待ち行列はカーネル。この分担により、コストが本当に必要な競合時だけに集中します。