リーダ・ライタロックとシーケンスロックの内部

なぜ単純な相互排他では足りないのか

ミューテックスは「常にただ1人だけがクリティカルセクションに入れる」という強い保証を与えます。しかし多くの実世界のデータ構造は、読み取りが圧倒的に多く、書き換えは稀です。ルーティングテーブル、設定値、システムクロックの読み出し――こうした対象に毎回ミューテックスを使うと、互いに干渉しないはずの複数のリーダまで直列化され、本来取れたはずの並列性を捨てることになります。

そこで「読み取り同士は同時に走ってよい。書き換えだけが排他を必要とする」という観察を制度化したのが リーダ・ライタロック（rwlock） であり、さらに「読み取りはロックすら取らない」と踏み込んだのが シーケンスロック（seqlock） です。両者は同じ「read-mostly」を狙いますが、達成手段と適用条件がまるで違います。本稿はその内部設計を原理から扱います。土台となる排他制御の全体像は 排他制御とデッドロック を参照してください。

rwlockの不変条件と状態

rwlockが守る不変条件は1つだけです。「ライタが1人いるなら、他のライタもリーダも1人もいない。リーダは何人いてもよいが、その間ライタは0人」。これを満たすため、内部状態はおおむね次のように表せます。

状態 = リーダ数（read count） と ライタフラグ の組
  read_lock():   ライタが0なら read count を +1（複数リーダ同時可）
  read_unlock(): read count を -1
  write_lock():  read count==0 かつ ライタ0 のときだけ取得（完全排他）
  write_unlock(): ライタフラグを下ろす

リーダ取得は本質的にアトミックなインクリメント、ライタ取得は「カウンタが0であることの確認＋占有」です。この単純な定義の裏に、設計上の難問が隠れています。ライタを待たせている間に、新しいリーダの到着を許すか否かです。ここがrwlockの性格を決定づけます。アトミックな増減の土台は アトミック命令とリード・モディファイ・ライトの原理 を参照してください。

リーダ優先とライタ優先――2つの設計の分岐

両者の違いは「ライタが write_lock() を待っている最中に、後から来たリーダを通すか」の一点に集約されます。リーダ優先は後続リーダを無条件に通すため、リーダの流入が途切れないとカウンタが0に戻らず、ライタは永久に取得できません。これが ライタ飢餓（writer starvation） です。

逆に ライタ優先は、待機中のライタがいる間は新規リーダをブロックします。これでライタは確実に進めますが、ライタが1人現れるたびに読み取りの並列パイプラインが一時的に止まり、read-mostlyで得たいはずのスループットが削られます。

seqlock――リーダがロックを取らない楽観的読み取り

rwlockのリーダはなおカウンタを書き換えます。seqlock（sequence lock） はそれすら捨て、リーダを完全に受動的にします。中心にあるのは シーケンスカウンタ（世代番号） ひとつです。

ライタ側:
  write_lock():
    spin_lock(&lock)     // ライタ同士は通常のロックで排他
    seq++                // 偶数 → 奇数（更新中の印）
    smp_wmb()            // 以降の書き込みがカウンタ更新の後に見えるよう順序付け
  write_unlock():
    smp_wmb()
    seq++                // 奇数 → 偶数（更新完了の印）
    spin_unlock(&lock)

リーダ側（ロックを一切取らない）:
  do {
    s = seq             // ① 開始時のカウンタを読む
    smp_rmb()
    ... 保護対象データを読んでローカルにコピー ...
    smp_rmb()
  } while (s が奇数) または (seq != s)   // ② 開始時と一致し、かつ偶数なら成立

設計の核心は2つです。第一に、カウンタの偶奇が状態を表すこと。偶数は「安定」、奇数は「ライタが書き換え中」を意味します。リーダは開始時に奇数を見たら、更新の真っ最中なので即座に再試行します。

第二に、リーダは読み取りの前後でカウンタを2回読み、値が一致するかを確認すること。途中でライタが入って seq を進めていれば、前後の値が食い違い、リーダは「読んだ値が引き裂かれている（torn read）かもしれない」と判断して、データを破棄しループの先頭からやり直します。リーダはライタを一切ブロックせず、ライタもリーダを待ちません。

メモリバリアがseqlockの生命線

seqlockの正しさは、カウンタの更新とデータの読み書きの順序に決定的に依存します。もしコンパイラやCPUがリオーダリングして、リーダが「データを読む前に終了時カウンタを読む」あるいはライタが「データを書く前にカウンタを偶数へ戻す」ことが起きれば、不一致検出のロジックが丸ごと崩壊します。

そのため擬似コードの smp_wmb／smp_rmb は飾りではなく必須です。ライタは「データ書き込み」と「カウンタを偶数に戻す」の間に書き込みバリアを置き、リーダは「カウンタ読み」と「データ読み」の間に読み込みバリアを置きます。この順序保証がなければ楽観的読み取りは成立しません。なぜバリアが要るのか、アーキテクチャごとの強弱は メモリオーダリングとメモリバリア を参照してください。

読み書き比率からの選択――原理で決める

3つの手段は「読みと書きの比率」「クリティカルセクションの長さ」「守る対象がコピー可能か」で住み分けます。

原理から導けば、判断はこう流れます。書き込みが頻繁、または区間が長いなら、楽観的再試行のコストが嵩むためseqlockは不利で、rwlockかミューテックスが妥当です。読みが圧倒的に多く、書きが稀で短く、守る値が小さくコピー可能なら、リーダをブロックしないseqlockが最も速い。そして 同じ read-mostly でも、守る対象がリンクリストやツリーのようなポインタ連結構造なら、コピーで持ち出せないためseqlockは使えず、RCUへ進みます。

まとめ――同じread-mostlyを別の角度から攻める