futex: ユーザー空間ロックの待機とウェイクアップ

futexは、Linuxが提供する低レベルの待機・ウェイクアップメカニズムです。一般的なミューテックスは、競合がないパスをユーザー空間に留め、ブロックやウェイクアップが必要になった場合にのみカーネルに入ります。futexは完全なロックそのものではなく、すべての言語、プラットフォーム、あるいはすべての同期プリミティブにとって唯一の実装経路でもありません。

同期プロトコルを設計する際には、以下の点を明確に答える必要があります：リソースを誰が保持するか、データをどのように公開するか、誰がスリープすべきか、状態が変更された後に誰をウェイクアップすべきか。futexは、主に後2つの項目と共有状態の間の接続を解決します。

なぜ単純にチェックしてからスリープするだけではダメなのか

Wがreadyが0であることを確認し、スリープしようとしていると仮定します。その後、Pがreadyを1に変更してウェイクアップを試みますが、この時点ではWはまだキューに入っていません。もしWが無条件にスリープし、その後に通知がない場合、既に発生した変化を見逃すことになります。

FUTEX_WAITは、futex wordを読み取り、expectedと比較し、待機に入るという一連の操作を原子性のある「比較してブロック（compare-and-block）」として実行します。もし値が既に異なっていれば、EAGAINを返してスリープしません。FUTEX_WAIT

これには、公開側がまず状態を変更し、その後プロトコルに従ってウェイクアップを行う必要があります。観測可能な状態を残さずにWAKEだけを呼び出しても、まだ待機していないスレッドを確実に通知することはできません。値が同じ値に戻って繰り返される場合、代数、シーケンス番号、またはより完全なプロトコルを使用して世代を区別する必要があり、1回の比較ですべてのABA問題が解消されるわけではありません。

2つの基本操作

従来のfutex wordは、64ビットプラットフォームで実行されていても、4バイト境界に整列された32ビット値です。通常のWAITはユーザーのロック状態を変更せず、WAKEはロックの所有権を渡すものでもなく、一般的なFIFOの公平性の保証もありません。futex(2)

WAITが0を返すのは、今回の待機がウェイクアップされたことを示すだけで、これに基づいてすぐにクリティカルセクションに入ることができるわけではありません。EAGAINは比較時に状態が変更されたことを示し、EINTRはシグナルによって中断されたことを示し、タイムアウトはビジネス条件が成立しないことを必ずしも意味しません。これらのパスでは、すべて同期プロトコルに戻って処理する必要があります。

FUTEX_WAITのtimeoutは相対時間ですが、他の操作では絶対的な期限を使用する場合があります。相対待機を再試行する際、毎回元の期間を完全に与えると、総タイムアウトが予期せず延長される可能性があります。同じ期限に基づいて残り時間を計算するか、適切な絶対時間インターフェースを使用すべきです。

ウェイクアップが保存されていない場合、WAITはどうしてスリープを見逃さないのか？

まず公開してからWAKEする場合、ウェイクアップ数は0になり得ます。その後、WAITがword=1と比較して、EAGAINを返してスリープしません。逆に、まずWAITしてから公開とWAKEを行う場合、待機者はキューから外れます。WAKEのみを行い、公開を行わない場合も可能です：待機者は目覚めますが、wordは依然として0であり、これはウェイクアップと条件の成立が別物であることを意味します。

3状態の一般的なミューテックスモデル

以下はアルゴリズムを説明するための擬似コードであり、pthread_mutex_tの内部レイアウトや、libcの実装を直接置き換えるものではありません。状態0は空き、1はロック済みで待機マークなし、2はロック済みで待機者が存在する可能性があることを示します。

lock:
    CAS_acquire(state, 0, 1) が成功した場合：戻る
    ループ：
        old = exchange_acquire(state, 2)
        old == 0 の場合：戻る
        WAIT(state, expected=2)
        戻り値に応じてエラー処理を行い、再競争する

unlock:
    old = exchange_release(state, 0)
    old == 2 の場合：WAKE(state, 1)

状態を2にマークするのは、解放者がウェイクアップが必要かもしれないことを知るためであり、待機者の正確な数を統計するためではありません。ウェイクアップされたスレッドが0から2への変更に成功し、マークを保持することで、後続の解放が他の待機者を押し進めることができます。新しく到着したスレッドは、ウェイクアップされたスレッドよりも先にロックを獲得する可能性があるため、このモデルは公平性を保証しません。

解放がWAITの前に発生した場合、比較の不一致によりスリープを見逃しません。待機が先にキューに入ると、後続のWAKEによって呼び出されます。このアルゴリズムには、アドレスのライフサイクル、キャンセル、タイムアウト、異常終了、境界エラーの処理も必要です。これこそが、アプリケーションが通常、成熟したpthreadや言語標準ライブラリのロックを使用する理由です。

ウェイクアップされた側が、新しく到着したスレッドに負ける可能性がある

解放者がまずstateを0に書き込み、Wをウェイクアップします。Wがまだスケジュールされる前に、新しいスレッドNがCAS(0, 1)に成功します。Wが実行されると、state=1を見て、再競争する必要があり、WAITが0を返したからといってすぐにクリティカルセクションに入れるわけではありません。

状態2の価値は、「後続の解放で通知が必要かもしれない」という情報を保持することにあります。これはWの所有権証憑でもなく、現在の待機者数でもありません。このスケジューリングは、通常のfutexロックが良好なスループットを持つ可能性がある一方で、待機の公平性や最悪の待機時間を直接約束できない理由を説明しています。

比較が一致しない場合、WAITはスリープしない

ここでは、単一スレッドのfutexインターフェースの比較と戻り値のみを検証し、並行ロックは実装しません。wordは既に1ですが、値0を待とうとしています。タイムアウトポインタがNULLであっても、直ちにEAGAINを得るはずです。

#define _GNU_SOURCE
#include <errno.h>
#include <linux/futex.h>
#include <stdint.h>
#include <stdio.h>
#include <sys/syscall.h>
#include <unistd.h>
int main(void) {
    _Alignas(4) uint32_t word = 1;
    errno = 0;
    long result = syscall(SYS_futex, &word, FUTEX_WAIT_PRIVATE,
                          0, NULL, NULL, 0);
    int saved = errno;
    printf("mismatch=%d\n", result == -1 && saved == EAGAIN);
    return !(result == -1 && saved == EAGAIN);
}

futex-mismatch.cとして保存し、コンパイルして実行すると、mismatch=1が期待されます。この例ではlibcのsyscallを使用しているため、-1とerrnoが表示されます。通常のuint32_tの並行変更はありません。これをマルチスレッドプロトコルに拡張する場合、以下の原子オブジェクトとメモリ順序の制約を再満たす必要があります。WAITの比較セマンティクス

原子変数のメモリ順序は省略できない

ロックで保護されたデータは通常、unlockのreleaseと成功したlockのacquireの間に同期関係を作成します。futexのキューの原子性は、言語メモリモデルにおけるデータ公開プロトコルを代替できず、通常の共有整数の並行読み書きを自動的に有効な原子操作に変えることもできません。

volatileは特定の設定のコンパイラによるアクセスセマンティクスに影響を与えるのみで、スレッド間の原子性やacquire/releaseを代替できません。futexラッパーを直接実装する場合、原子オブジェクトのサイズ、アラインメント、ロックフリーサポート、およびターゲットABIとカーネルインターフェースの互換性を確認する必要があります。

PRIVATEフラグは、待機する両方が同じアドレス空間でそのオブジェクトを使用していることを示し、カーネルによる検索の最適化を許可します。プロセス間で共有されるオブジェクトには、共有マップに適した操作を使用する必要があり、PRIVATEを無条件により高速なオプションとして扱うことはできません。futexアドレスの破棄、マップ解除、または再利用の前には、古い操作がそれを参照していないことを確実にする必要があります。

PIとrobustは異なる問題を解決する

優先度継承（PI）は、低優先度のロック保持者が中優先度のタスクによって絶えずプリエンプトされ、高優先度の待機者が進めなくなる状況に対処します。カーネルは待機チェーンに沿って保持者の有効優先度を上げ、クリティカルセクションの完了を助けます。PIには特定の所有者エンコーディングと操作プロトコルが必要であり、通常のWAIT/WAKEで適当に実装することはできません。

pthreadインターフェースでは、ミューテックス属性を通じてPTHREAD_PRIO_INHERITを選択します。これはデッドロックを解決するものでもなく、クリティカルセクション自体を短縮するものでもなく、任意のスケジューリング条件下でデッドラインを達成することを保証するものでもありません。

Robust mutexは、ロック保持スレッドの死亡に対処します。次のpthread_mutex_lockはEOWNERDEADを返す可能性があり、この場合、呼び出し元はロックを獲得していますが、保護されたデータが一貫していない可能性があります。アプリケーションはデータを修復し、pthread_mutex_consistentを呼び出してロックを解除する必要があります。一貫性が回復されていない状態でロックを解除すると、後続の操作でENOTRECOVERABLEを得る可能性があります。

EOWNERDEADを単に「ロック取得失敗、ロックを獲得していない」として扱うことはできず、データをチェックせずに一律にconsistentとマークすることもできません。カーネルは異常な所有者状態を提供しますが、ビジネス修正を自動的にロールバックしません。Robust mutex

完全な回復の例：コミット済みコピーを使用して未完了の更新を回復

以下は、プロセス内で作業スレッドを1つ作成する例です。正常な不変条件はworking == committedです。作業スレッドはロックを取得してworkingを99に変更した後、直接終了し、コミットされていない更新をシミュレートします。回復側は「コミットされていない内容を破棄」を選択し、workingをcommitted=7に戻してから一貫性をマークします。

#define _POSIX_C_SOURCE 200809L
#include <errno.h>
#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>
static pthread_mutex_t mutex;
static int committed = 7, working = 7;
static void require(int result) { if (result != 0) abort(); }
static void *unfinished(void *unused) {
    (void)unused;
    require(pthread_mutex_lock(&mutex));
    working = 99;
    return NULL;  /* 意図的にrobust mutexを保持したままスレッドを終了。 */
}
int main(void) {
    pthread_mutexattr_t attr;
    require(pthread_mutexattr_init(&attr));
    require(pthread_mutexattr_setrobust(&attr, PTHREAD_MUTEX_ROBUST));
    require(pthread_mutex_init(&mutex, &attr));
    require(pthread_mutexattr_destroy(&attr));
    pthread_t thread;
    require(pthread_create(&thread, NULL, unfinished, NULL));
    require(pthread_join(thread, NULL));
    int result = pthread_mutex_lock(&mutex);
    if (result != EOWNERDEAD) abort();
    if (working != 99 || committed != 7) abort();
    working = committed;
    require(pthread_mutex_consistent(&mutex));
    require(pthread_mutex_unlock(&mutex));
    require(pthread_mutex_lock(&mutex));
    int recovered = working == 7 && working == committed;
    require(pthread_mutex_unlock(&mutex));
    require(pthread_mutex_destroy(&mutex));
    printf("recovered=%d\n", recovered);
    return !recovered;
}

robust-demo.cとして保存し、cc -Wall -Wextra -pthread robust-demo.c -o robust-demoでコンパイルします。期待される結果はrecovered=1であり、回復後の次のlockは正常に0を返します。Robust mutex 回復プロトコル

この例では、コミット済みコピーは異常なスレッドによって変更されていないため、回復ルールは明確です。複雑なオブジェクトの場合、部分的な書き込み、リンクリスト構造、外部副作用などが関与する可能性があります。もしcommitted自体が不完全である可能性がある場合、単純な代入は有効な回復とはなりません。検証可能な不変条件と回復データを事前に定義し、いつconsistentを呼び出すかを決定する必要があります。

EOWNERDEAD：ロックは獲得したが、データはまだ修復されていない

まず終了をシミュレートしてからlockすることで、EOWNERDEADと「回復スレッドがロックを保持」の両方を同時に確認できます。2つの後続パスを比較します：直接unlockすると回復不能状態に入ります。workingを修復し、consistentを宣言してからunlockすると、次のlockが正常に成功します。データの修復と一貫性の宣言は2つの操作であり、後者を省略しても回復プロトコルは完了しません。

その他の操作とfutex2の境界

FUTEX_REQUEUEなどの操作は待機キューを移動でき、一部の状態変数パターンにおけるスプーリング（驚群）を削減します。FUTEX_WAKE_OPは、2番目のwordに対する原子操作と条件付きウェイクアップを結合します。これは「原子加算の後にWAITを行う」ものではなく、FUTEX_OPは操作をエンコードするマクロです。FUTEX_WAKE_OP

futex_waitvは比較対象となるwordのセットを受け取り、そのいずれかがウェイクアップされるのを待機します。これは複数の待機ソースに適しています。あるインデックスで戻ったとしても、ビジネス状態を確認する必要があり、複数のロックを同時に獲得したことを意味しません。このインターフェースは絶対タイムアウトと指定されたクロックを使用します。

「futex2」には多项拡張の構想が含まれていましたが、提案書にあるすべての幅、NUMA、スケジューリング特性が6.xカーネルですでに備わっている事実として記述することはできません。本文で確認したカーネルのfutex2ドキュメントは、waitvに対してFUTEX_32を明確に要求しており、構造体フィールドは拡張のためにスペースを残しています。カーネル futex2 ドキュメント

パフォーマンスをどう理解するか

競合がないパスではシステムコールがない場合もありますが、原子読み書きには依然としてキャッシュ一貫性のオーバーヘッドが発生します。競合時には、スピニング、キュー操作、コンテキストスイッチ、スケジューリング遅延、NUMA間のデータ転送が含まれる可能性があります。「20ns」という固定値や、競合時に毎回必ずWAITとWAKEが1回ずつ行われるという普遍的な結論は存在しません。

ロックが遅い場合、保持時間、待機時間、争奪頻度、およびスケジューリングの影響を区別して観察します。関数エントリから戻りまでの追跡方法については、ftraceとbpftraceを参照してください。

キーワード：futex, compare and block, lost wakeup, FUTEX_WAIT, FUTEX_WAKE, acquire release, PI, robust mutex, EOWNERDEAD, futex_waitv