← OSと低レイヤのしくみ コース
16. 読み手を待たせない同期 — seqlockとRCU
読み手にロックを取らせない2つの仕組み、seqlockとRCUを図で追っていきましょう。
① 通常のロックでは読み手が止まる
共有データstruct foo
アクセスするには必ずロック取得
spin_lock()1つだけ通す門
1度に1人だけ通過
読み手A通過中
読み手B待ち
書き手待ち
- ・読み手同士は本来ぶつからないのに、同じ門で待たされます
- ・読み手が圧倒的に多いデータでは、この待ちが支配的なコストになります
読むだけの処理まで排他の列に並ぶのが、通常のロックの弱点です。ここを外す発想が seqlock と RCU です。
② seqlock: 書き手がカウンタを+1して足跡を残す
seqcount = 100偶数 = 更新していない
write_seqlock() が内部の spinlock 取得 と +1
seqcount = 101奇数 = 更新中
新旧が混ざりうる状態データ本体を書き換える
共有データを更新複数フィールドを順に書く
write_sequnlock() が +1 と spinlock 解放
seqcount = 102偶数 = 更新完了
- ・カウンタは更新の開始時と終了時に+1され、値は単調に増えます
- ・奇数か偶数かで「今まさに更新中か」が読み手から判別できます
- ・seqlock_t は書き手直列化用の spinlock を内蔵するため、書き側は自動的に直列化され非プリエンプティブになります
- ・spinlock を持たない seqcount_t を使う場合は、書き手同士の排他を呼び出し側が別途用意します
更新の前後で+1することで、カウンタが「更新中フラグ」と「世代番号」を兼ねます。
③ seqlock: 読み手は前後のカウンタを見比べるだけ
read_seqbegin()開始時のカウンタを控える
seq = 100ロックを取らずにそのまま読む
データを読むローカル変数にコピー
read_seqretry() で再確認
seq が開始時と一致読んだ値を採用
seq が変化している最初からやり直し
- ・読み手は共有メモリに書き込まないため、読み手が書き手や他の読み手を待たせることはありません
- ・ただし読んでいる間に書き手が来た場合、読み手の側がやり直しを迫られます
- ・読み手は何度でもやり直せる必要があるので、読み側の処理に副作用を持たせられません
- ・読み手が割り込み文脈で走る場合、書き側は write_seqlock_irqsave() で割り込みを抑止します
「読んだ後に、読んでいる最中に壊されなかったか」を事後確認する方式です。壊れていたら読み直します。
④ RCU: 更新側は新しいノードを作って差し替える
旧ノード読み手が参照中かもしれない
既存ノードは書き換えず、複製して編集
新ノードを確保kmalloc して値を設定
rcu_assign_pointer() でポインタを差し替え
以後の読み手 → 新ノードrcu_dereference() で取得
参照中の読み手 → 旧ノードまだ生きている
- ・rcu_assign_pointer() は新ノードの初期化がポインタ公開より先に見えることを保証します
- ・rcu_dereference() は読み手側で対応するメモリ順序を保証します
- ・切り替えの瞬間、新旧2つのバージョンが同時に存在することを許容する設計です
既存データを壊さず新しい版を公開するので、読み手は途中経過を見ることがありません。
⑤ RCU: 猶予期間が待つのは「呼んだ時点の読み手」だけ
読み手Arcu_read_lock() 済み
旧ノードを参照中読み手Brcu_read_lock() 済み
旧ノードを参照中ここでポインタ差し替え後に synchronize_rcu() を呼ぶ
猶予期間 開始AとBの終了を待つ
読み手C呼び出し後に開始
新ノードしか見えないAとBが rcu_read_unlock() したら終了
猶予期間 終了旧ノードを見る者はもういない
ここで初めて安全
kfree(旧ノード)call_rcu() なら非同期に同じことをする
- ・synchronize_rcu() が待つのは進行中の読み側クリティカルセクションだけで、呼び出し後に始まるものは待ちません
- ・呼び出し後に始まる読み手は必ず新ノードを見るため、待つ必要がありません
- ・待たずに先へ進みたい場合は call_rcu() でコールバック登録し、猶予期間後に解放させます
「全読み手を待つ」のではなく「呼んだ時点にいる読み手だけを待つ」設計です。待つ相手が increasing しないので猶予期間は前へ進めます。
⑥ RCU の読み側は止まってはいけない
rcu_read_lock()区間の開始を宣言
この中でやってよいこと / いけないこと
OK: rcu_dereference()参照して値を読む
NG: ブロックする処理待ちに入ると猶予期間が延びる
rcu_read_unlock()
区間の終了ここで解放側が前へ進める
- ・読み側クリティカルセクション内で自発的にブロックすることは許されません
- ・CONFIG_PREEMPT_RCU のカーネルでは読み側区間がプリエンプトされ得ますが、ブロックしてよいという意味ではありません
- ・ブロックが許されるのは spinlock が眠れるロックになる CONFIG_PREEMPT_RT のような構成に限られます
- ・読み手が長居するほど旧バージョンの解放が遅れ、メモリを圧迫します
読み手のコストがほぼゼロなのは、区間が短く必ず終わることを前提にしているからです。
⑦ なぜこの設計なのか — 手間の押し付け先
読み手ロックを取らない / 他者を待たせない
共通の狙いそのしわ寄せを誰が引き受けるか
seqlock読み手がやり直す + 書き手を直列化
データは常に1つRCU解放側が猶予期間を待つ
新旧2版が併存向く場面
小さく再読しやすい値時刻など短い構造体
ポインタで差し替えられる構造リストやツリーのノード
- ・どちらも読み手を止めない代わりに、書き手側または解放側がコストを負います
- ・seqlock は読み手のやり直しを許せる処理に、RCU は古い版を一時的に見られても困らない処理に向きます
- ・共通の前提は「読みが圧倒的に多く、書きが稀」というアクセス比です
読み手優先という結論は同じでも、代償の払い方が違います。データの形で選び分けます。