カーネルのRCUと並行データ構造の設計パターン

本当の難所は「更新」ではなく「回収」

ロックフリーなリストやキューを書くとき、ポインタを CAS で差し替えて要素を繋ぐ部分は、実は易しい方です。本当に難しいのは 削除したノードをいつ free してよいか の判断です。あるスレッドがノードへのポインタを読んだ直後に横取り（プリエンプト）され、その隙に別スレッドが同じノードを論理削除して解放したら、再開した最初のスレッドは 解放済みメモリ（use-after-free） を読みます。CAS の差し替え自体は成功していても、回収のタイミングを誤れば構造は壊れます。

この問題を SMR（Safe Memory Reclamation、安全なメモリ回収） と呼びます。本質は「いま誰かがそのノードを参照中かもしれない間は解放できない」こと。GCのある言語なら処理系が肩代わりしますが、カーネルやC/C++ランタイムでは自前で実装します。差し替えの土台となる CAS とABA問題は カーネルのロックフリー同期とCAS を、なぜポインタ参照に順序保証が要るのかは メモリオーダリングとメモリバリア を前提にすると読みやすくなります。

RCU：読み手を限界まで軽くする

RCU（Read-Copy-Update） は、読み取りからロックもアトミック操作も取り除き、コストをすべて更新側へ寄せる手法です。読み手は rcu_read_lock()／rcu_read_unlock() で区間を囲むだけ（多くの構成でほぼノーオペレーション）、更新側は旧ノードを書き換えず新版を作ってポインタ1発で公開し、grace period（全読み手が区間を抜ける猶予期間） の完了を待ってから旧版を解放します。原理の詳細は RCU（Read-Copy-Update）の原理、数百コアでの実装は RCUの実装詳細 を参照してください。

/* 読み手：ほぼ無料 */
rcu_read_lock();
p = rcu_dereference(head);
while (p) { use(p); p = rcu_dereference(p->next); }
rcu_read_unlock();

/* 更新側：差し替え → grace period 待ち → 解放 */
rcu_assign_pointer(prev->next, target->next); /* リストから外す */
call_rcu(&target->rcu, free_node);            /* 後で安全に解放 */

RCUの強みは 読み手が共有状態を一切書かない ことで、コア数に対してほぼ線形にスケールします。代償は回収レイテンシで、grace periodは全CPUの静止を保守的に待つためミリ秒オーダーになりえます。読み多寡が極端でメモリ二重保持を許せる経路に最適です。新旧を共存させる発想は コピーオンライト（CoW） と同じ系譜です。

ハザードポインタ：参照を「宣言」して守る

ハザードポインタ は、回収を正確に行う方向の手法です。各スレッドは「いま参照しているノード」を、グローバルに公開された自分専用のスロット（ハザードポインタ）に書き込んでから アクセスします。回収側はノードを解放する前に、全スレッドのハザードポインタを走査 し、どこからも指されていないと確認できたものだけを解放します。指されているノードは「保留リスト」に積み、後で再走査します。

読み手の手順:
  do {
    p = atomic_load(&head)      # ① 候補を読む
    HP[me] = p                  # ② 「参照中」と宣言（ストア）
    fence(seq_cst)              # ③ 宣言を回収側に確実に見せる
  } while (p != atomic_load(&head))  # ④ 宣言後も同じか再確認（ABA回避）
  use(p)
  HP[me] = NULL                 # 終わったら宣言を取り下げる

正確さの代償は 読み手ごとのコスト です。参照するたびにストアと 逐次一貫フェンス相当 が必要で、RCUのほぼ無料な読み手には及びません。一方で「ノード単位で、不要になった瞬間に近いタイミングで解放できる」ため、回収レイテンシに上限を引け ます。保留ノード数が「スレッド数 × 1スレッドあたりHP本数」で抑えられるのが理論的な美点です。

エポックベース回収：軽さと引き換えに「足を引っ張られる」

エポックベース回収（EBR、Epoch-Based Reclamation） は、RCUのユーザー空間版とも言える中庸の手法です。グローバルな エポックカウンタ（世代番号）を用意し、スレッドはクリティカルセクションに入るとき現在のエポックを自分のローカルに記録（アナウンス）します。削除されたノードは「削除時のエポック」付きで退避され、全アクティブスレッドが、その世代から2つ進んだエポックに到達したら 安全に解放します。読み手のコストはローカル変数の読み書き程度で、RCUに近い軽さです。

ロックフリーキューが回収を必要とする理由

これらの回収手法は、具体的なロックフリー構造と組で初めて意味を持ちます。代表例が Michael-Scott キュー（連結リスト＋ダミーの先頭ノード）で、enqueueは末尾ポインタを、dequeueは先頭ポインタを CAS で進めます。問題はdequeueで外した 旧ダミーノードをいつ解放するか。別スレッドがまさにそのノードのポインタを読んでいる最中かもしれません。ここでRCU／ハザードポインタ／EBRのいずれかを噛ませて初めて、解放が安全になります。「差し替えはロックフリー、回収はSMRに委ねる」が定石の分業です。

三手法の選び分け

選択の軸は2つに集約できます。読み取りをどこまで軽くしたいか と、回収の即時性・上限保証をどこまで求めるか。読み多寡が極端でメモリ二重保持を許せるならRCU。回収レイテンシに上限が要る、あるいはメモリ消費を厳しく抑えたいならハザードポインタ。読み取りの軽さと実装の素直さのバランスを取りたい汎用ランタイムやDBストレージエンジンならEBR、というのが現場の相場観です。

まとめ