リード・コピー・アップデート（"read-copy-update"、RCUと略記）とは、オペレーティングシステムにおいて一種の排他制御を実装する同期機構であり、の代替手段として使われることがある。参照において待ち状態が生じず、極めてオーバーヘッドが低い。しかしRCUにおけるデータ更新は、既存の参照者のために古い版のデータ構造を保持しつつ行うため、時間と空間（メモリ）をより多く必要とする。古い版のデータ構造は、既存の参照者が全てアクセスを完了した後で回収される。RCUでは「参照側クリティカルセクション」という概念があり、通常 rcu_read_lock() と rcu_read_unlock() で挟まれた部分がそれにあたる。参照側クリティカルセクション内にない文は「不活性状態」と呼ばれ、RCUで保護されたデータ構造への参照を保持することは許されない。データを共有するスレッド間で、少なくとも1つが不活性状態にある期間を「猶予期間」と呼ぶ。定義上、任意のRCU参照側クリティカルセクションが猶予期間の始まりに存在する場合、その猶予期間の終了までにクリティカルセクションが完了しなければならず、それがRCUの提供する根本的保証の前提となっている。この保証が参照側オーバーヘッドを極めて小さくすることがわかっており、実際サーバクラスのLinuxカーネルでの参照側オーバーヘッドはゼロである。RCUの基本的な考え方は、更新を「削除」と「再利用」のフェーズに分割することである。削除フェーズではデータ構造内のデータへの参照を削除する（それらの参照を別のバージョンのデータ構造への参照に切り替える）。そうすることで参照側クリティカルセクションと並行して更新可能にする。削除フェーズが参照者と並行して動作できるのは、最近のCPUの設計によって参照者が新旧いずれかの版のデータ構造だけを参照することを保証できるためである（参照側クリティカルセクション内で参照するデータ構造の版が入れ替わることがない）。猶予期間が過ぎると、旧版のデータ構造を参照している参照者がいないと断定でき、旧版のデータを構成するアイテムを再利用フェーズで解放（再利用）しても安全である。更新を削除と再利用のフェーズに分割することで、更新者は削除フェーズを速やかに行い、削除フェーズに入ったときに動作していた全ての参照者が停止するまで、言い換えれば猶予期間が過ぎるまで再利用フェーズを遅らせる。典型的なRCUにおける更新は以下のような流れとなる。このような手順において、更新者が削除と再利用のステップを実行するが、再利用については全く別のスレッドに任せた方が便利なことが多い。参照カウントを持たせることで、参照者が削除を行うこともできるので、更新ステップ（上記の (2)）と再利用ステップ（上記の (4)）が同じスレッドで行われるとしても、それらを分けて考えた方がわかりやすい。2008年初めごろの段階で、Linuxカーネル内では、ネットワーク・プロトコルスタックやメモリ管理システムなど約2,000箇所で RCU API を利用している。2006年以降、研究者らはRCUや類似の技法をいくつかの問題に適用してきた。例えば、動的解析に使用するメタデータの管理、クラスター型オブジェクトのライフタイム管理、K42研究OSでのオブジェクト管理、ソフトウェアトランザクショナルメモリ実装の最適化などである。DragonFly BSD はRCUによく似た技法を採用しており、Linuxの SRCU 実装に極めて近い。RCUでは、全参照者が参照を終えるのを待つことができ、それによって非常に軽量な同期が可能で、場合よっては同期しないで参照することができる。対照的に一般のロックを使った方式では、参照者はオーバーヘッドの大きな同期機構を使って更新者が使用中のデータ構造を削除するのを防がなければならない。これはロックを使った更新者がその場でデータを更新するためであり、従って参照する者がいないことを保証する必要がある。一方RCUでは現代的CPUでは1つのポインタの書き換えがアトミックになされるという点を利用し、参照者をわずらわせずにデータ構造のリンクをアトミックに挿入・削除・置換する。RCUの参照者は旧版のデータを同時並行的に参照し続けることができ、不可分操作やメモリバリアやキャッシュミス(これらは今日のSMPコンピュータシステムではロックの衝突がなくても性能を低下させる)を排除できる。RCUの参照側の軽量さは単に性能向上、スケーラビリティ、リアルタイム応答性に寄与するだけではない。例えば、デッドロックやライブロック状態を防ぐことにも繋がる。RCUには当然ながら短所もある。例えば、RCUは参照が多く更新が少ない状況に最適な技法であり、更新が頻繁に行われる状況には適していない。また、RCUは参照者と更新者が同時並行的に動作できることで参照側の同期機構を軽量化しているが、参照と更新の並行性がなじまないアルゴリズムも存在する。RCUは10年以上に渡って使われているが、その応用範囲は正確には把握されておらず、今も研究対象となっている。この技術は米国のソフトウェア特許 5,442,758（1995年8月15日、権利者はシークエント・コンピュータ）でカバーされている（他に 5,608,893、5,727,528、6,219,690、6,886,162）。すでに権利失効している特許 4,809,168 も非常に近い技術をカバーしていた。RCU はSCOとIBMの間の訴訟問題でも言及されている。RCUはいくつかのOSで利用可能であり、Linuxカーネルには2002年10月に追加された。liburcu などのユーザーレベルの実装も利用可能である。Linuxカーネル 2.6 でのRCU実装はよく知られており、以下ではそれを元に RCU API について解説する。中核となるAPIは極めて小さい。以下の図は各APIが参照者、更新者、再利用者の間でどう関係しているかを示している。RCUの内部機構は codice_8, codice_9, codice_1, codice_4 が呼び出された順番を記憶し、(1) codice_1 がそれらの呼び出し側への戻りを設定するか、(2) codice_4 のコールバックが呼び出される順番を決定する。効果的な実装としては、各APIのオーバヘッドを減らして、背後でバッチ的に処理するほうがよい。RCUのおもちゃ的な実装を考えるとRCUを理解しやすいだろう。ここではそのような簡単な実装を説明する。この実装はプリエンプション不可な環境でのみ動作することに注意。codice_6 と codice_5 を無視しても大勢に影響はないが、いずれにしろ、以下のようになる。codice_8 と codice_9 は全く何もしない。プリエンプション不可な古いカーネルでは、このように参照側のオーバヘッドは全く無い（メモリバリアが必要となるのは DEC Alpha だけである）。したがって codice_8 がデッドロック状態になることもなく、リアルタイムプロセスがスケジューリングのデッドラインに陥ることもなく、優先順位の逆転が発生することもなく、ロックの衝突が激しく発生することもない。codice_1 の実装は、synchronize_cpu を呼び出した者を各CPUに移動させ、全CPUでコンテキストスイッチ可能となるまでブロックさせる。プリエンプション不可なのでRCU参照側クリティカルセクション内でプリエンプションは発生せず、あるCPUで（他のプロセスをスケジュールする）コンテキストスイッチが起きたときにはそれ以前のRCU参照側クリティカルセクションは完了しているはずである。全CPUでコンテキストスイッチが起きたら、既存のRCU参照側クリティカルセクションが全て完了していることを保証できる。RCUはいろいろな使い方があるが、一般的な使い方はリーダー・ライターロックに近い。以下のふたつのコードはリーダー・ライターロック(左側)とRCU(右側)を同じ処理で使ったものである。両者の違いは非常に小さい。参照側のロックは rcu_read_lock() と rcu_read_unlock() になり、更新側のロックはリーダー・ライターロックから単純なスピンロックに変更され、kfree()を実行するまえに synchronize_rcu() が呼び出される。しかし、この場合参照側と更新側が同時に動作する可能性が出てくる。多くの場合はこれは問題とはならないが、使われ方を十分注意する必要がある。たとえば、複数の独立したリストをアトミックに更新しなければならない場合、これをRCUに置き換えるには注意が必要である。synchronize_rcu() があるということはRCUでは delete() がブロックされる可能性があることを示す。それが問題となる場合は代わりに call_rcu() を codice_20 のように使用すればよい。これは参照カウントと組合わせる場合に特に便利である。この名称はRCUがリンクリストをその場で更新するのに使われていたことに由来する。この場合、以下のような処理の流れとなる。更新を行ったスレッドがカーネルによって起こされたら、安全に古いデータ構造を解放できる。そのため、参照 (read) スレッドは、更新 (update) スレッドがコピー (copy) している間も並行して動作できる。以上から、「リード・コピー・アップデート(read-copy update)」と呼ばれたのである。これを RCU という略称で呼ぶようになったのはLinuxコミュニティである。類似の技術は、例えばでは "passive serialization" あるいは "MP defer" と呼ばれ、やTornadoでは "generations" と呼ばれている。RCUと類似する技法や機構は、歴史上何度も独自に発明されてきた。

出典:wikipedia