Day 7: グレースピリオド ~RCUの動作原理~

RCUの動作原理を知る

今日に至るまで、並行処理の基礎を勉強してきた。これからはRCUのメカニズムを勉強していく。今日はグレースピリオド(Grace Period)という概念から勉強していく。

RCUの概要

RCUの簡易的な説明をする。

• RCUは保護するデータのポインタを持っている
• RCUの読み込み時
  • rcu_read_lock()という関数を呼ぶ(後述)
  • rcu_dereference()でRCUで保護しているポインタを取得する
  • rcu_read_unlock()という関数を呼ぶ(後述)
• RCUの書き込み時
  • 新しいデータを格納するためのメモリを確保する
  • 既存のデータをコピーする
  • データの変更をする
  • 保持している古いポインタと新しいデータのポインタを比較更新操作で更新する^[1]
  • 古いデータはすぐには破棄しない
• RCUの古いデータの扱い(GC)
  • synchronize_rcu()を実行する
    • 古いポインタ(複数でも可)を参照している全ての読み込みスレッドがrcu_read_unlock()を実行するのを待つ関数
  • synchronize_rcu()が終わったら古いデータを解放する

このアニメーションは、RCUがデータを読み書きして古いデータをGCする様子を表す。

リードサイドクリティカルセクション

リードサイドクリティカルセクションとは、RCUを使用してデータを読み取る際に開始される特定のコードブロックのことである。RCUの読み取りが開始することを意味するrcu_read_lock()によってリードサイドクリティカルセクションが開始され、読み取りが終了することを意味するrcu_read_unlock()によって終了する。

複数の読み取りが重なると以下のようなものになる。

グレースピリオドとsynchronize_rcu()

先ほどの図の読み取りが行われている間に、RCUが保持するポインタが新しいデータのポインタとCASでアップデートされ、古いデータとして扱われることになるとする。

その状態で書き込みスレッドが、synchronize_rcu()という関数を実行する。
synchronize_rcu()は全ての読み込みスレッドが古いデータに対しrcu_read_unlock()を実行し終わるのを待つ。

そして、このsynchronize_rcu()の実行期間のことをグレースピリオド(Grace Period)と呼ぶ。

synchronize_rcu()の終了は、「synchronize_rcu()をコールした時点の古いポインタは、もうどのスレッドも参照していない」ということを意味するので、RCUはsynchronize_rcu()の終了を合図にして古いポインタを解放する。ただ、synchronize_rcu()の最中で、CASで最新ポインタと置換されたポインタは解放の対象にならず、またそのあとでsynchronize_rcu()を実行して解放することになっている。

RCUのGC

要するに、RCUのGCは「グレースピリオドが終わったことを見極めること」である。

「rcu_read_lock()したときにポインタを参照するスレッドの数を表すカウンタを++1して、rcu_read_unlock()したときにそのカウンタを--1すれば、カウンタが0になったときに解放できるじゃん」
と思った人もいるだろう。ただこれは考えうるGCの中でも最も遅い実装なのだ。

なぜかは今までの並行処理の基礎の知識を使えば導出できるが、詳細はまとめてこの方法以外のGCの話を明日の記事に書くことにする。

脚注

1. この操作は、rcu_assign_pointer()という関数に該当するが、このブログではその関数名を使って説明することは避けることにした。rcu_assign_pointer()実装はCASであると説明されている記述がなく、Mathieu Desnoyers, Paul E. McKenney, Alan S. Stern, Michel R. Dagenais Jonathan WalpoleによるUser-Level Implementations of Read-Copy Updateという論文でも、ポインタの更新操作の実装を「rcu_assign_pointer() またはそれに相当するポインタ置換関数を呼び出す。」と書いてあったので、このアドベントカレンダーではポインタを更新する操作を「CAS」で統一する。