Day 9: Quiescent State Based Reclamation ~RCUの動作原理~
QSBR
昨日では、RCUのGCのデザインパターンについて軽く勉強した。今日はGCの実装方法の一つであるQSBR(Quiescent State Based Reclamation)を勉強する。
QSBRとは
まず、QSBR(Quiescent State Based Reclamation)とは、各読み取りスレッドが自発的に「静止状態(quiescent state)」に達したこと（すなわち、リードサイドクリティカルセクションを抜け、古いデータ構造を参照していないこと）を明示的に報告させることで、古いデータが誰からも参照されなくなったことを保証し、安全な解放を可能にするアプローチである。「静止状態」はrcu_quiescent_state()などの呼び出しによって通知される。
QSBRでは、グローバルなカウンタとスレッドごとのローカルなカウンタを同期的に見比べることで、全スレッドが一度は静止状態を経験したことを確認する。[1]たとえば、synchronize_rcu()を呼ぶと、その時点のグローバルなカウンタ値を基準として値をインクリメントし、全スレッドのローカルカウンタが新しいグローバルカウンタ値と同等になるまで待機する。言い換えると、「synchronize_rcu()を呼んだ時におけるグローバルカウンタ」を目標値として、すべてのスレッドがその値に追いつく（全スレッドが一度はrcu_quiescent_state()を通過する）まで待ち続ける。これが完了すれば、遅延解放リストに登録していたコールバック関数を呼び出し、古くなったデータを安全に解放できるようになる。
つまりQSBRは、「スレッドが能動的にリードサイドクリティカルセクションから抜けたことを適宜知らせる」ことを前提として、そのタイミングを元に「もう古いデータにはどのスレッドも触れていないはず」と判断する手法である。シンプルな実装では、各スレッドは読み取りアクセス時にrcu_read_lock()で開始点を記録(そのスレッドのローカルカウンタをグローバルカウンタ値へと同期)し、読み取り終了後または所定の間隔でrcu_quiescent_state()を呼び出すことで、システムに「クリティカルセクションを抜けた」と知らせる。
rcu_quiescent_state()呼び出し時には、そのスレッドのローカルカウンタをグローバルカウンタ値へと追いつかせる（同期させる）処理が行われる。 これにより、「このスレッドは現在のグレース期間における静止状態を一度通過した」という事実が明確になる。
この繰り返しによって、定期的に古いデータを安全に片付けることが可能となる。
よく文章を読むとrcu_read_lock()とrcu_quiescent_state()は同じ実装をすることがわかる。
書き換え(更新)を行う側は、データを新しいバージョンに置き換えた後に、synchronize_rcu()を呼び出して、すべての読み取りスレッドが前述のグローバルカウンタの更新に追いつくまで待ち、その後、どのスレッドからも参照されていない古い領域をコールバックで解放する。これがQSBRによるGCの仕組みである。
実装の詳細は「 Day 14: synchronize_rcu() ~RCUの実装~」で触れる。
後日アニメーションを入れる。
-
これはEBRも同じ ↩︎
Discussion