以下は、２０１６年５月時点の Linux カーネル文書、Documentation/RCU/RTFP.txt、 Read the Fscking Papers! の前半の、kanda.motohiro@gmail.com による訳です。原文と同じ、GPL v2 で公開します。
fsck する論文を読め！
この文書は、RCUに関連する論文について述べます。その後に、対応する bibtex エントリがあります。論文の多くは、http://www.rdrop.com/users/paulmck/RCU/ にあるでしょう。他のものも、ブラウザと検索エンジンを使えば普通は見つかるでしょう。
RCUに似た最初のものは、1980 に論文発表されました。 Kung and Lehman [Kung80] は、実装を簡単にするために、並列二分探索木のノードの破壊を後回しにするためにガーベッジコレクタの使用を勧めました。これは、ガーベッジコレクタのある環境でうまく動きましたが、ほとんどの本番ガーベッジコレクタはかなりなオーバーヘッドを起こしました。
1982 に、 Manber and Ladner [Manber82,Manber84] は、同じく並列二分探索木について、そのとき走っている全てのスレッドが終わるまで破壊を後回しにすることを勧めました。このアプローチは、K42 研究オペレーティングシステムのように短寿命のスレッドを持つシステムではうまく動きます。しかし、Linuxは長寿命のタスクを持ちますから、まだ何かが必要です。
1986 に、 Hennessy, Osisek, and Seigh [Hennessy89] は受動的シリアライゼーションを導入しました。それは、VM/XA ハイパーバイザにおいて、あるデータ要素を参照していないことが保証される「静止状態」の存在に依存するRCUに似た機構です。しかし、この機構は現代的計算機システムに対しては最適化されていませんでした。それは、そのようなオーバーヘッドが80年台半ばにはそれほど高価でなかったことを思うと、驚くことではありません。とは言え、受動的シリアライぜーションは本番で使われた最初の遅延破壊機構であるようです。さらに、関連する特許は失効しました。なので、お望みならば、GPLでないソフトウェアでこのアプローチを使うことができます。(それに対して、RCUの実装は、GPLもしくはLGPLの元でライセンスされるソフトウェアの中に限って許されます。失礼！！！)
1987 に、 Rashid 他 [RichardRashid87a] はレイジーなTLBフラッシュについて書きました。少し見ただけでは、これはRCUとは関係ないようです。しかしそれでもこの論文は、後の DYNIX/ptx でのRCU実装で使われる更新側のまとめを発見する助けとなりました。1988 に、 Barbara Liskov は、Argus の説明を発表しました。そこでは、状況によっては古い値を使うことが許容されることを述べていました。なので、この論文は、古い値を使うことの初期の理論的正当化のいくらかを提供します。
1990 に、 Pugh [Pugh90] は、どのスレッドがあるデータ構造を読んでいるかを明示的に追跡すれば、終わらないスレッドがあっても遅延解放がうまくいくことを示しました。しかし、この明示的追跡は、大きなリード側オーバーヘッドを課し、それは、リードがほとんどの状況では望ましくありませんでした。このアルゴリズムは、ライト側の競合を避け、細粒度のロック設計を提供することで他のライト側のオーバーヘッドを並列化しようとかなりの苦労を実際にしています。しかし、1990 に報告された性能上の優位点のどれほどが、今日でも残っているかを見るのは興味深いことです。
この同じ頃、Andrews [Andrews91textbook] は、``chaotic relaxation'' について、述べました。そこでは、収束する数値計算アルゴリズムの連続する繰り返しの間にある通常のバリアがゆるめられます。その結果、繰り返し $n$ は $n-1$ 回目の繰り返しからのデータあるいは $n-2$ からのものさえ使うことができます。これは誤差を導入し、それは典型的には収束を遅くし、その結果必要な繰り返しを増やします。しかしこの増加は時には、高価なバリア操作の回数が減ることで十分以上に埋め合わせられます。バリアはそうでなければそれぞれの繰り返しの終わりでスレッドを同期するために必要です。不幸にも、chaotic relaxation は、科学計算プログラムで使われる行列のような、高度に構造化されたデータを必要とします。なので、オペレーティングシステムカーネルで使われるほとんどのデータ構造には適用できません。
1992 に、 Henry (今は Alexia) Massalin は、並列プログラマは、もし可能ならば同期を単純にするために、処理を遅延させることを勧める博士論文を完成しました[HMassalinPhD]。RCU はこの助言を最大限に使っています。
1993 に、 Jacobson [Jacobson93] は、口頭で、もしかすると最も単純な、遅延解放テクニックと呼べるものを述べました。遅延解放を待っているブロックを解放する前に、固定時間、単純に待つのです。Jacobson は、SGI の Irix カーネルを使ってこの作業において彼が行ったかもしれないライト側の変更については何も述べませんでした。Aju John は 1995 に、同様のテクニックを発表しました[AjuJohn95]。これは、もし、読んでいるスレッドが参照を保持することのできる時間の長さに、良く定義された上限がある時にはうまくいきます。それは、ハードリアルタイムシステムではそうでしょう。しかし、もしこの時間がたぶん、プリエンプション、多すぎる割り込み、あるいは想定より大きな負荷のために超過したならば、メモリ破壊がおきることがあります。そしてそれは、合理的に診断する方法がありません。なので、Jacobson のテクニックは、本番のオペレーティングカーネルで使うためには不適切です。もしそのカーネルが、全ての操作に対して、ハードリアルタイム保証を提供できない限り。
同様に、1995 に、 Pu 他 [Pu95a] は、Pugh のリード側追跡に似たテクニックを、商用 Unix オペレーティングシステムにおいて、アルゴリズムを入れ替える事を可能とするために適用しました。しかしこの入れ替えは、一度には一つのリーダーしか許しませんでした。翌年、この同じ研究者のグループはそのテクニックを、複数のリーダーを許すように拡張しました[Cowan96a]。彼らのアプローチはメモリバリア（そしてそのためにパイプラインストール）を必要としますが、メモリ遅延、競合、そしてロックオーバーヘッドを減らします。
1995 には、 DYNIX/ptx の RCU 機構の最初の発表 [Slingwine95] もありました。それは、現代的 CPU アーキテクチャに最適化され、DYNIX/ptx カーネルの中の多くの状況で適用され成功しました。それに対応する学術会議論文は、1998 に出ました [McKenney98]。
1999 に、 Tornado and K42 グループは、 "generations" 機構を述べました[Gamsa99]。それは、RCU にとても良く似ていました。これらのオペレーティングシステムは、"existence locks" の代わりに、RCU を広く使っており、それはロック階層を大いに単純にし、デッドロックを防ぐのに役立ちました。
2000 には、RCU のようなもののさらに別の独立した発明につながったかもしれない電子メールのやりとりがありました[RustyRussell2000a,RustyRussell2000b]。その代わり、2001 に、Linux に関する最初の RCU 学会発表が OLS でありました[McKenney01a]。その結果となる多くの RCU パッチは翌年、提供されました[McKenney02a]。そして、dcache における RCU の使用は、その同じ年に述べられました[Linder02a]。
また、2002 に、 Michael [Michael02b,Michael02a] は "hazard-pointer" テクニックを発表しました。それは、ノンブロッキング同期（待ちのない同期、ロックのない同期、妨害のない同期は全て、ノンブロッキング同期の例です）を単純にするために、データ構造の破壊を遅延させます。対応する学術ジャーナル記事は、2004 に現れました[MagedMichael04a]。このテクニックは、ロックを除き、競合を減らし、リーダーのメモリ遅延を減らします。そして、ライターのパイプラインストールとメモリ遅延を並列化します。それでも、メモリバリアという形で、大きなリード側オーバーヘッドを課します。Sun の研究者は、同じ頃、同様の研究を進めていました[HerlihyLM02]。これらの技術は、裏返った参照カウンタと考えることができます。そこでは、カウントは、あるデータ構造を参照するハザードポインタの数で表されます。より伝統的な、データ構造それ自体内のカウンタフィールドではありません。裏返った参照カウンタの鍵となる利点は、それらは、（訳注。削除されうるデータ構造自身ではなく、外部の）不死の変数に格納することができることで、アクセスと削除の競合を避けることができます。
同様に、RCUは「バルク参照カウント」と考えることができます。そこでは、ある種の参照カウンタが、決められた時間枠内でのあるCPUもしくはスレッドの全ての参照をカバーします。この時間枠は、RCUグレースピリオドに関連づいていますが、必ずしもそれと正確に同じ必要はありません。古典的RCUでは、参照カウンタは「ビットマスク」フィールドのCPUごとのビットです。そして、そのようなビットのそれぞれが、前のグレースピリオドの間に対応するCPUが行なった可能性のある全ての参照をカバーします。もちろん、RCUを他の言葉で考えることも可能です。
2003 に、 K42 グループはオペレーティングシステム関数のホットプラグ可能な実装を作るために、RCU をどのように使うことができるかを述べました[Appavoo03a]。その年の後日、System V IPC のRCU 実装を述べる論文が出ました [Arcangeli03] 。（それは、Hugh Dickins [Dickins02a] の提案と、Mingming Cao [MingmingCao2002IPCRCU] による実装に続くものでした。）また、Linux Journal にRCUの紹介も出ました[McKenney03a] 。
2004 には、 Linux-Journal の、dcache での RCU の使用についての記事[McKenney04a]、複数の異なるCPUでのロックとRCUの性能比較、いくつかのオペレーティングシステムカーネルでのRCUの使用を述べた博士論文 [PaulEdwardMcKenneyPhD]、ソフトリアルタイムアプリケーションにとってRCUを安全にする方法を述べた論文[Sarma04c]、そして、RCUがあるときの SELinux 性能を述べる論文 [JamesMorris04b]が出ました。
2005 には、リアルタイム用途への RCUの採用はさらに進みました。RCUリアルタイムクリティカルセクションのプリエンプションが可能となりました [PaulMcKenney05a,PaulMcKenney05b]。
2006 には、 RCU 論文で初めて、最優秀論文賞が出ました [ThomasEHart2006a]。また、プリエンプト可能RCUの効率的実装についての作業もさらに進みました[PaulEMcKenney2006b]。しかし、RCU リード側クリティカルセクションの優先度ブーストはなかなか難しいことがわかりました。リード側クリティカルセクションでの、一般的なブロックを許すRCU実装が現れました[PaulEMcKenney2006c]。Robert Olsson は、 RCU で守られたトライ木とハッシュの組み合わせを述べました[RobertOlsson2006a]。
2007 には、2006 の受賞したRCU論文のジャーナル版が出ました[ThomasEHart2007a]。また、Oleg Nesterov の QRCU への最適化を機械的に証明するために Promela and Spin を使うことを述べる論文[PaulEMcKenney2007QRCUspin]、プリエンプト可能RCUを説明する設計文書[PaulEMcKenney2007PreemptibleRCU]、そして、３部からなるLWN "What is RCU?" 連載記事 [PaulEMcKenney2007WhatIsRCUFundamentally,
PaulEMcKenney2008WhatIsRCUUsage, and PaulEMcKenney2008WhatIsRCUAPI]が出ました。
2009 には、ユーザレベルの RCU アルゴリズム [PaulEMcKenney2009MaliciousURCU] が現れました。それは今は、Mathieu Desnoyers が維持しています [MathieuDesnoyers2009URCU]
[MathieuDesnoyersPhD]。 TINY_RCU [PaulEMcKenney2009BloatWatchRCU] と、expedited RCU [PaulEMcKenney2009expeditedRCU] が現れました。サイズ変更可能な、RCU で守られたハッシュテーブルの問題は、解決される途中でした[JoshTriplett2009RPHash]。アカデミックな研究者の中には、自分の並列問題を解決するために RCU を使うものが何人か現れました[HariKannan2009DynamicAnalysisRCU]。
2010 には、TREE_RCU を元にする、より単純なプリエンプト可能 RCU 実装[PaulEMcKenney2010SimpleOptRCU] 、lockdep-RCU
[PaulEMcKenney2010LockdepRCU]、もう一つのサイズ変更可能な RCU で守られたハッシュテーブル[HerbertXu2010RCUResizeHash] （こちらは、より多くのメモリを消費しますが、ネットワークコードで DoS 攻撃を防ぐために必要とされる、ハッシュ関数を任意に変更する機能を持ちます。）、2009 の、アトミックなノード移動ができる RCU で守られたハッシュテーブルの実現、RCU API の更新 [PaulEMcKenney2010RCUAPI] がありました。
2011 には、 Nick Piggin の完全にロックのない dentry 検索のメインラインへの取り込み
[LinusTorvalds2011Linux2:6:38:rc1:NPigginVFS]、同時実行する更新を防ぐためにソフトウェアトランザクショナルメモリを使った（変な話ですが、本当！） RCU で守られた赤黒木 [PhilHoward2011RCUTMRBTree]、さらにもう一つのRCU で守られたサイズ変更可能なハッシュテーブルの変種[Triplett:2011:RPHash]、3.0 RCU 電車事故[PaulEMcKenney2011RCU3.0trainwreck]、そして Neil Brown の "Meet the
Lockers" LWN 記事 [NeilBrown2011MeetTheLockers]がありました。あるアカデミックな研究は、RCU のデバッグ用途に注目しました[Seyster:2011:RFA:2075416.2075425]。
2012 に、 Josh Triplett は、博士号を受けました。彼の論文は、RCU で守られたサイズ変更可能なハッシュテーブルと、メモリバリアとリード側のトラバース順序の関係を扱いました。もし、更新者がリード側のトラバース順序と逆の方向に変更をしているなら、更新者はメモリバリア命令を実行する必要だけがあります。しかし、もし同じ順序なら、更新者は個々の更新の間に、グレースピリオドだけ待つ必要があります[JoshTriplettPhD]。また、2012 には、１７年に渡る試みの後に、RCU の論文が最高級のアカデミックジャーナル、IEEE Transactions on Parallel and Distributed Systems
[MathieuDesnoyers2012URCU]に載りました。スペインの研究者グループはユーザレベル RCU を群衆シミュレーションに適用しました[GuillermoVigueras2012RCUCrowd]。そして、ヨーロッパの別の研究者グループは、separation logic を元にして、RCU の形式的記述を作成しました[AlexeyGotsman2012VerifyGraceExtended]。それは、2013 European Symposium on Programming [AlexeyGotsman2013ESOPRCU] で発表されました。
訳注。以下は、Bibtex エントリなので、訳は省略します。
以上