tkokamoの日記

HPCの研究開発なのでそんなことをかきたい

RCU(Read Copy Update)をちゃんと知る（1）-1　ほんとの概要

はじめに

ファイルシステムのrcu-walkを理解するためにRCUの勉強から始めようと思ったので書留ます。
RCUとはざっくりこんなものだ、と分かっている前提での記録です。
予想している流れとしては、

  • 概要（概要）← 今回
  • Linuxでの実装
  • rcu-walk（RCUの応用先）

と考えています。原稿も無いので、次回がいつになるかわかりません（社内勉強会でrcu-walkを語ろうと思っているので完遂はすると思われます）

今回は、wikipediaとかよんでで「？」となった当たりを捕捉。

RCUとは？

図を用いた簡単な理解

複数のタスクで共有するデータの参照/更新をきちんと行う場合、大抵は適切に排他区間をロックによって設けてそれを実現します。
理想的には、タスク間で共有するデータの参照/更新をロックフリーで行えるとよいのですが、一般的にそのようなことを実現する方法は考えられていません。
しかし、特定のデータ構造（※）の参照/更新については、ロックフリーでそれを行うことができます。
RCU（Read Copy Update）とはそのような手法です。

（※）リード・コピー・アップデート - Wikipedia によるとRCUの応用範囲も研究の対象らしいです。


では、RCUはどのようにロックフリーにデータの参照/更新を実現しているのか、ということを知るために以下の図を用いて考えてみます。

f:id:tkokamo:20170816144144p:plain

上図は単方向リストによって構築されているツリー構造を表しています。
（1）ノードAはノードBおよびノードCを指しています。
（2）Cの更新を行いたいタスクは、Cのコピーを作成しそれに対してデータの更新を行います。仮にCを参照中のタスクが他に存在していても、更新を行うタスクはコピー先に対して更新を行うため、参照中のタスクに対して中途半端な状態が見えることがありません。
（3）C'の更新が終わり他のタスクから参照されても問題ない状態になった時、AがもともとCを指していたポインタをC'を指すように更新します。逆に言うと、この時点でCはツリー構造から削除される（※）ことになります。
このため、データを参照するタスクは古いCか新しいC'を参照するのみで、中途半端な状態を参照することは起きません。ポインタから外されたCは参照者が居なくなった時点で解放（※）されます。
（※）リード・コピー・アップデート - Wikipedia には「削除と再利用のフェーズを分ける」とありますが、これは「removal and reclaim」の和訳が適切ではなく「削除と解放（回収）のフェーズを分ける」ということと理解しています。

日本語で詰まったところ

更新前の古いデータCは、Cを参照するタスクが居なくなった時点で解放（reclaim）されます。古いデータを参照するタスクは、新しいデータC'がツリーに追加された後（つまりremoval後）には新規に現れません。（removal後のタスクはC'を参照することになる。）
古いデータの解放タイミングを知るために参照側の把握が必要であり、これがRCUの参照側クリティカルセクションという概念に繋がっているのではないかと考えています。
仮にCを参照するタスクが長いことスリープしたりすると、古いデータがメモリ上にずっと残ってしまうことになります。この期間が長いと、その間にC'が更新されC'‘になり、世代が異るデータがメモリに置かれることとなり容量効率が悪いです。そのため、参照者はスリープやブロックをせず極力参照時間を短く抑える必要があります。
日本語訳で少し不明瞭だった言葉にgrace period（猶予期間）がありますが、これは古いデータCが削除後（AのポインタがC'に更新された後）に回収されるまでの期間を表しています。
参照時間を短くする努力というのは、すなわちgrace periodを短くする努力ということになります。

おわりに

概要ということでかなりざっくりと、主に自分がよくわからんと思ったところを書きとどめました。
次回からLinuxにおける実装を見てみようと思いますが、大体以下の部分を調べていきたいかと思います。