|
リード・コピー・アップデート（''read-copy-update''、RCUと略記）とは、オペレーティングシステムにおいて一種の排他制御〔RCU は一般的な意味での排他制御の実装ではない。通常の排他制御機構が時間的に排他するのに対して、RCUではデータを更新中もデータの古いバージョンへの参照を同時に行えるようにすることで、空間的な排他を行う。〕を実装する同期機構であり、の代替手段として使われることがある。参照において待ち状態が生じず、極めてオーバーヘッドが低い。しかしRCUにおけるデータ更新は、既存の参照者のために古い版のデータ構造を保持しつつ行うため、時間と空間（メモリ）をより多く必要とする。古い版のデータ構造は、既存の参照者が全てアクセスを完了した後で回収される。 == 概要 == RCUでは「参照側クリティカルセクション」という概念があり、通常 rcu_read_lock() と rcu_read_unlock() で挟まれた部分がそれにあたる。参照側クリティカルセクション内にない文は「不活性状態」と呼ばれ、RCUで保護されたデータ構造への参照を保持することは許されない。データを共有するスレッド間で、少なくとも1つが不活性状態にある期間を「猶予期間」と呼ぶ。定義上、任意のRCU参照側クリティカルセクションが猶予期間の始まりに存在する場合、その猶予期間の終了までにクリティカルセクションが完了しなければならず、それがRCUの提供する根本的保証の前提となっている。この保証が参照側オーバーヘッドを極めて小さくすることがわかっており、実際サーバクラスのLinuxカーネルでの参照側オーバーヘッドはゼロである。 RCUの基本的な考え方は、更新を「削除」と「再利用」のフェーズに分割することである。削除フェーズではデータ構造内のデータへの参照を削除する（それらの参照を別のバージョンのデータ構造への参照に切り替える）。そうすることで参照側クリティカルセクションと並行して更新可能にする。削除フェーズが参照者と並行して動作できるのは、最近のCPUの設計によって参照者が新旧いずれかの版のデータ構造だけを参照することを保証できるためである（参照側クリティカルセクション内で参照するデータ構造の版が入れ替わることがない）。猶予期間が過ぎると、旧版のデータ構造を参照している参照者がいないと断定でき、旧版のデータを構成するアイテムを再利用フェーズで解放（再利用）しても安全である。 更新を削除と再利用のフェーズに分割することで、更新者は削除フェーズを速やかに行い、削除フェーズに入ったときに動作していた全ての参照者が停止するまで、言い換えれば猶予期間が過ぎるまで再利用フェーズを遅らせる〔削除フェーズ中に動作中の参照者のみを考慮する必要がある。削除フェーズ後に動作開始した参照者は削除された旧版のデータへの参照が不可能なためであり、再利用フェーズに影響されることがない。〕。 典型的なRCUにおける更新は以下のような流れとなる。 # RCUで保護されたデータ構造にアクセスする参照者は全てRCU参照側クリティカルセクション内で参照することを保証する。 # データ構造へのポインタを削除して、その後の参照者がそれを参照できないようにする。 # 猶予期間が過ぎるのを待つ。それにより（前のフェーズで削除されたデータ構造へのポインタを持っている可能性のある）全ての参照者がRCU参照側クリティカルセクションを抜けるのを待つ。 # この時点で更新したいデータ構造への参照を持つスレッドはいなくなるので、安全に再利用（たとえば、解放）できる〔可能ならばこのステップでガベージコレクションを行うこともある。〕。 このような手順において、更新者が削除と再利用のステップを実行するが、再利用については全く別のスレッドに任せた方が便利なことが多い。参照カウントを持たせることで、参照者が削除を行うこともできるので、更新ステップ（上記の (2)）と再利用ステップ（上記の (4)）が同じスレッドで行われるとしても、それらを分けて考えた方がわかりやすい。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「リード・コピー・アップデート」の詳細全文を読む スポンサード リンク
|