並行プリミティブ 基礎

並行性バグは 3 つの根本原因を共有する:

• レースコンディション —— 結果がスレッドスケジュールのインタリーブに依存する。 古典:共有カウンタ上の x++ は load → add → store で、 2 スレッドのレースは increment 数より少ないカウンタを生む、それらの読み / 書きがインタリーブしたから。
• アトミック性違反 —— 1 ステップに見えるが実はそうでない操作。 check-then-act(「if (cache.contains(k)) cache.get(k)」)は check と act の間に追い出しが起こり得る。多くの並行性バグは言語の表現的抽象の背後に隠れたアトミック性バグ。
• メモリ可視性問題 —— 1 スレッドが値を書き、別スレッドが後で読み、 古い値(または裂けた中間)を見る。cache-coherence primer がなぜこれがハードウェアレベルで 起こり得るかを扱う;修正は第 4 節のメモリ順序メカニズム。

共有状態問題

同じアドレス空間(process-thread primer)の 2 スレッドはヒープとグローバルメモリの あらゆるバイトを共有する。明示的な同期なしには、カーネルは任意のインタリーブで それらをスケジュールでき、CPU はシングルスレッドプログラム順序が保持される限り、 各スレッド内で命令を並べ替える自由がある。

3 つの対処戦略が現れた:

• 共有を避ける。最もクリーンなアプローチ。 スレッドごとの状態、スレッド間通信のためのチャネル、不変データ構造。 Erlang、Rust(unsafe なしで)、Go(チャネルで)がこれをデフォルトとして推進する。
• 共有状態をロックする。あらゆる読み書きをミューテックスで包む。 書くのは簡単、スケールが難しい(ロック競合)、別種のバグが現れる(デッドロック)。
• ロックフリーアトミック。ハードウェアアトミックプリミティブ(CAS、fetch-add) を使ってロックなしで共有状態を更新する。最高スループット、正しく書くのが最も難しい。 ここでは第 4 節のメモリ順序ルールが避けられない。

なぜ「ただミューテックスを使う」が時に間違いか

ロックは推論しやすい —— クリティカルセクション内には一度に 1 スレッド。 3 つの失敗モードが規模感でそれらを打つ:競合(多くのスレッドが同じロックを待つ、 スケジューラスラッシング)、デッドロック(2 スレッドが各々 1 ロックを保持し 互いのを待つ)、優先度逆転(低優先度スレッドが高優先度スレッドが必要なロックを保持する)。 各々に独自の緩和(ロックフリー、ロック順序、優先度継承ミューテックス)がある、 しかし根本的制約は変わらない:グローバルロックは単一 CPU レイテンシあたり 1 クリティカルセクション完了で スループットを頭打ちにする。

カーネルが助けられること、できないこと

カーネルはスレッドをサスペンドできる(ミューテックス / condvar / sleep 経由)、 カーネルはウェイクアップを配信できる、カーネルは優先度をスケジュールできる。 カーネルはあなたのコードがロックを正しい順序で解放すること、共有メモリを二重解放しないこと、 別スレッドが書く前に値を読まないことを強制できない。それらはアプリケーションが所有する 正確性契約 —— 言語ランタイムはここまでしか助けられない(Rust のボロウチェッカは これらの一部をコンパイル時エラーにする最も積極的な試み)。

ミューテックス

ミューテックス(相互排他ロック)はクリティカルセクション内に 一度に 1 スレッドのみを保証する。操作:lock(取得;他者が保持していればブロック) と unlock(解放)。実装:

• スピンロック —— ロックが空くまでビジーループ。CPU を燃やすが スリープに行く syscall コストを避ける。カーネル内で短いクリティカルセクションに、 またはロックフリーライブラリで非常に短い競合に使われる。
• スリーピングミューテックス(pthread_mutex) —— 取得を試みる (しばしばまずスピン);競合があれば futex(次節)でスリープするためカーネルへ syscall。 標準的なユーザ空間ミューテックス。
• 適応的ミューテックス —— まず数千サイクルスピンし、その後スリープ。 競合が短ければ安い;短くなくても正しい。

ミューテックス競合は単一最頻のスケーリングボトルネック。perf lock、jstack スレッドダンプ分析、または pprof のミューテックスプロファイルのような ツールがどのロックがホットか特定する。

セマフォ

セマフォは N に一般化されたミューテックス —— 一度に最大 N スレッドがクリティカルセクション内にいられる。 操作:wait(カウントをデクリメント;0 ならブロック)とsignal(カウントをインクリメント;ウェイターがいれば 1 つ起こす)。 レート制限(例:遅いサービスへの N 並行接続のみ)、有界バッファ、リソースプールに使われる。

条件変数

condvar は 1 スレッドが別スレッドがシグナルする条件が真になるのを待てるようにする。 重要なのは、それは常にミューテックスとペアになる —— condvar プロトコルは:

// waiter
lock(mtx);
while (!condition) {
    cond_wait(cv, mtx);  // アトミックに mtx を解放してスリープ;
                         // ウェイク時に mtx を再取得
}
// ここで条件は真
unlock(mtx);

// signaller
lock(mtx);
make_condition_true();
cond_signal(cv);  // 1 つの waiter を起こす(または cond_broadcast で全員)
unlock(mtx);

waiter 側の while ループは必須 —— 偽のウェイクアップ (waiter が対応するシグナルなしに起きる)が POSIX で許可されており、 マルチウェイターケースでは、別のスレッドがこちらがチェックする前にシグナルの状態変化を 消費するかもしれない。古典的な「wait、check、sleep、recheck」ループがパターン。

Condvar は Java の BlockingQueue、Go の sync.Cond、 Rust のチャネルのような高レベル構造が背後でどう動くか。

RWLock

リーダ-ライタロックは多くの並行リーダ OR 1 つの排他ライタを許可する。 読みが書きを大幅に上回るとき(キャッシュ、設定)に有用、しかし簿記が普通のミューテックスより 高い —— そして単一ライタが定常的なリーダのストリームに餓死し得る (大半の実装は公平性の措置としてライタを優先する)。

デッドロック

2 スレッドが各々 1 ロックを保持し他方のを必要とするとき、ロック取得はデッドロックし得る。 古典的な 4 条件(Coffman):相互排他、hold-and-wait、プリエンプションなし、循環待機。 標準的な修正はロック順序 —— 常に固定のグローバル順序でロックを取得する。 静的解析ツール(clang-tidy、Java の @GuardedBy アノテーション)が一部のケースを捕捉する; ランタイム検出(gdb のミューテックストラッカ、Java ThreadMXBean)が他を捕捉する。 最もクリーンな修正はロックをまったくネストしないこと。

ハードウェアアトミック操作

CPU は他のコアに対してアトミックにメモリ位置を read-modify-write する小さな操作セットを公開する。 x86 では、大半が LOCK 接頭辞付きの通常命令としてエンコードされる:

• LOCK XADD —— アトミック fetch-and-add。古い値を返し、加算。 アトミックカウンタに使う。
• LOCK CMPXCHG —— アトミック compare-and-swap。メモリが期待と等しければ 新値にセット;スワップが起きたかを返す。あらゆるロックフリーアルゴリズムの基礎。
• LOCK BTS / BTR —— アトミックビットセット / ビットリセット。 一部のロック実装で軽量シグナルとして使われる。
• 適切なアラインメントの MOV —— 自然にアラインされた 1/2/4/8 バイトストアは x86 で既にアトミック(LOCK 不要)、しかし他コアへの可視性のためにメモリ順序アノテーションが まだ必要。

ARM は異なるメカニズムを使う:LDREX(load-exclusive)がキャッシュラインを予約し、STREX が書き込みを試みる —— LDREX 以来他のコアがラインを触っていない場合のみ成功。 CAS は小さなリトライループになる。ARMv8.1 は単純なケースでより速い代替として直接のCASAL / SWPAL 命令を追加した。

コスト(cache-coherence primer):競合なしのアトミック ~10-25 サイクル、競合下バウンスあたり ~100 ns。 ロックフリーは無料ではない。

Futex —— 高速ユーザ空間ミューテックス

Futex(Fast Userspace muTEX)は Linux カーネルプリミティブで、 最小限のカーネル関与でユーザ空間にロックを実装させる。鍵となる洞察: ロックが競合していなければ syscall は不要 —— ユーザ空間でアトミック compare-and-swap をするだけ。 競合時のみカーネルが待機者をスリープさせる必要がある。

Futex syscall(futex(addr, op, val, ...))操作:

• FUTEX_WAIT —— 「アトミックに *addr == val をチェックし、そうならこの addr 上で 起こされるまでスリープ」。アトミックチェックがロストウェイクアップレースを防ぐ。
• FUTEX_WAKE —— この addr で待つ N(典型的に 1)個の待機者を起こす。
• FUTEX_REQUEUE —— 一部を起こし、他を別の futex に移動する。 pthread_cond_broadcast が thundering-herd 問題を回避するために使う。

pthread_mutex はどう futex を使うか

現代の pthread_mutex_lock 実装はおおよそ:

int* state;  // 0 = ロックなし、1 = ロック、2 = ロック-待機者あり

// 高速パス:compare-and-swap 0 → 1
if (CAS(state, 0, 1) == 0) return;  // 競合なし、完了 —— syscall なし

// 競合パス:locked-with-waiters とマークしてスリープ
while (true) {
    int v = atomic_exchange(state, 2);  // 待機者ありとマーク
    if (v == 0) return;                 // 取得した
    futex_wait(state, 2);               // 起こされるまでスリープ
}

// unlock
if (atomic_exchange(state, 0) == 2) {   // 以前 locked-with-waiters だった?
    futex_wake(state, 1);                // 1 つの待機者を起こす
}

高速パスは 1 アトミック命令 —— syscall なし、~10 ns。 低速パスは 1 futex_wait syscall —— ~1 μs。だからミューテックスは競合なしで非常に安く、 競合下でも合理的に安い;最悪ケース(多くのスレッドが常に競合)はステートキャッシュラインの バウンスのコストで支配される。

ロックフリーデータ構造

ロックではなくアトミックプリミティブのみを使ってキュー / スタック / ハッシュテーブルを構築する。 利点:スレッドが遅いピアでブロックされない(デッドロックなし、優先度逆転なし)。 コスト:正しく実装するのは有名なほど難しい、ABA 問題が素朴な CAS ループを誤らせる、 削除されたノードのメモリを回収するのはそれ自体の問題(ハザードポインタ、エポックベースの回収、RCU)。 Java の ConcurrentLinkedQueue、C++ Boost.lockfree、Rust の crossbeam が プロダクション準備の実装。

単一スレッド内では、as-if ルールがプログラムが自分の操作をプログラム順で見ることを保証する —— 観測可能な結果が同じである限りコンパイラは内部でそれらを並べ替えられる。 スレッド間にはそのような保証はない。スレッド B がスレッド A が書いた 2 つの値を読むと、 どちらかの順序、任意のインタリーブで見得る —— 言語と CPU が特定の順序を強制することに 合意していない限り。

知っておくべき 4 つのメモリ順序

• relaxed —— アトミック性のみ、順序保証なし。アトミック操作は単一ステップとして 完了する(裂け読みなし)、しかし CPU とコンパイラは周囲の操作をそれを越えて自由に並べ替えられる。 順序ではなく最終的な合計のみ気にするカウンタに使う。
• acquire —— ロードバリア。このロードが戻った後、このスレッドの後の操作すべては 後に発生することが保証される —— どれも前に並べ替えられない。別のスレッドの release とペアになる。
• release —— ストアバリア。release 前のこのスレッドのすべての操作は、 同じアトミックで acquire するあらゆる他スレッドに可視であることが保証される。release を越えて 並べ替えられない。
• seq_cst(逐次整合) —— 最強で C++ デフォルト。追加:すべてのスレッドの すべての seq_cst 操作が単一グローバル全順序で合意する。必要なまれなケース (Peterson のアルゴリズム、一部のロックフリー構造)で acquire-release より強い。

acquire-release パターン

プロデューサ-コンシューマシナリオが標準的な用途:

// プロデューサ
data = compute();                   // relaxed または非アトミックでよい
flag.store(true, memory_order_release);

// コンシューマ
while (!flag.load(memory_order_acquire)) {}
use(data);                          // プロデューサが書いた data を見る

プロデューサのストアの release + コンシューマのロードの acquire が happens-before 関係を確立する: プロデューサが release 前にしたすべてが acquire 後にコンシューマに可視。 あらゆる参照カウント、あらゆる wait-free シグナリング、あらゆる spsc キューがこの上に構築される。

なぜこれがアーキテクチャで変わるか

x86 は TSO(Total Store Order):無料で、あらゆるロードが acquire 様、 あらゆるストアが release 様 —— 異なるアドレス間のストア-ロード並べ替えのみが許可される。 これは「x86 で動く」ロックフリーコードが ARM で壊れ得ることを意味する、 ARM はずっと弱い。実例:素朴な C++ の data; flag = true; はアトミックなしでも x86 で動くが、ARM ではコンパイラ / CPU が自由に並べ替えられ、コンシューマが data の前に flag を見得る。

seq_cst は x86 で追加コスト(seq_cst ストアあたり MFENCE)、ARM ではより多く (ロードとストアの両方に DMB ISH)。性能認識の選択は、必要な保証を与える最弱の順序を使う: カウンタには relaxed、シグナリングには acquire-release、実際に跨アドレスグローバル順序が 必要なときのみ seq_cst。

古典的な間違い

「速いから」とデフォルトを relaxed にする。Relaxed 順序は他の操作との happens-before 関係を 確立しない。per-thread 統計用の counter.fetch_add(1, relaxed) のようなコードは問題ない; データが準備されたとシグナルする flag.store(true, relaxed) は、 弱順序ハードウェアでコンシューマの data ビューを静かに破壊する。 経験則:他のコードがアトミック前に行われたことに依存するなら release が必要; 後に来るものに依存するなら acquire が必要。

コードレビューの赤旗

• while ループなしの condvar wait。POSIX は偽のウェイクアップを許可する;ループなしでは起きて真でない可能性のある状態で動作する。
• スレッド間シグナリングに memory_order_relaxed を使う。x86 で動き、ARM で壊れる。可視性関係を確立する何かには最低でも acquire-release を使う。
• 異なるパスで異なる順序で取得される複数ロック。デッドロック待ち。グローバルロック順序を確立し文書化する;静的解析でアサートする。
• syscall を跨いでミューテックスを保持。syscall がブロックすると(read、write、ファイル open など)、同じミューテックスを欲しがる 他のすべてのスレッドが遊休する。クリティカルセクションの外で syscall を行うよう再構築する。
• 手作りのロックフリーデータ構造。常にバグ。 ライブラリ(Java の java.util.concurrent、C++ Boost.lockfree、Rust crossbeam)を使うか、 ミューテックスに退化する。