リード・コピー・アップデート

リード・コピー・アップデート（read-copy-update、RCUと略記）とは、オペレーティングシステムにおいて一種の排他制御を実装する同期機構であり、リーダー・ライターロックの代替手段として使われることがある。参照において待ち状態が生じず、極めてオーバーヘッドが低い。しかしRCUにおけるデータ更新は、既存の参照者のために古い版のデータ構造を保持しつつ行うため、時間と空間（メモリ）をより多く必要とする。古い版のデータ構造は、既存の参照者が全てアクセスを完了した後で回収される。

利用

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の単純な実装

RCUのおもちゃ的な実装を考えるとRCUを理解しやすいだろう。ここではそのような簡単な実装を説明する。この実装はプリエンプション不可な環境でのみ動作することに注意。
void rcu_read_lock(void) { }

void rcu_read_unlock(void) { }

void call_rcu(void (*callback) (void *), void *arg)
{
// add callback/arg pair to a list
}

void synchronize_rcu(void)
{
int cpu, ncpus = 0;

for_each_cpu(cpu)
                        schedule_current_task_to(cpu);

                for each entry in the call_rcu list
                        entry->callback (entry->arg);
}
rcu_assign_pointer と rcu_dereference_pointer を無視しても大勢に影響はないが、いずれにしろ、以下のようになる。
#define rcu_assign_pointer(p, v)({ \
smp_wmb(); \
(p) = (v); \
})

#define rcu_dereference_pointer(p)      ({ \
        typeof(p) _value = (p); \
        smp_rmb(); /* not needed on all architectures */ \
        (_value); \
        })
rcu_read_lock と rcu_read_unlock は全く何もしない。プリエンプション不可な古いカーネルでは、このように参照側のオーバヘッドは全く無い（メモリバリアが必要となるのは DEC Alpha だけである）。したがって rcu_read_lock がデッドロック状態になることもなく、リアルタイムプロセスがスケジューリングのデッドラインに陥ることもなく、優先順位の逆転が発生することもなく、ロックの衝突が激しく発生することもない。
synchronize_rcu の実装は、synchronize_cpu を呼び出した者を各CPUに移動させ、全CPUでコンテキストスイッチ可能となるまでブロックさせる。プリエンプション不可なのでRCU参照側クリティカルセクション内でプリエンプションは発生せず、あるCPUで（他のプロセスをスケジュールする）コンテキストスイッチが起きたときにはそれ以前のRCU参照側クリティカルセクションは完了しているはずである。全CPUでコンテキストスイッチが起きたら、既存のRCU参照側クリティカルセクションが全て完了していることを保証できる。

リーダー・ライターロックとの比較

RCUはいろいろな使い方があるが、一般的な使い方はリーダー・ライターロックに近い。以下のふたつのコードはリーダー・ライターロック(左側)とRCU(右側)を同じ処理で使ったものである。
 1 struct el {                           1 struct el {
 2   struct list_head lp;                2   struct list_head lp;
 3   long key;                           3   long key;
 4   spinlock_t mutex;                   4   spinlock_t mutex;
 5   int data;                           5   int data;
 6   /* Other data fields */             6   /* Other data fields */
 7 };                                    7 };
 8 DEFINE_RWLOCK(listmutex);             8 DEFINE_SPINLOCK(listmutex);
 9 LIST_HEAD(head);                      9 LIST_HEAD(head);

 1 int search(long key, int *result)     1 int search(long key, int *result)
 2 {                                     2 {
 3   struct el *p;                       3   struct el *p;
 4                                       4
 5   read_lock(&listmutex);              5   rcu_read_lock();
 6   list_for_each_entry(p, &head, lp) { 6   list_for_each_entry_rcu(p, &head, lp) {
 7     if (p->key == key) {              7     if (p->key == key) {
 8       *result = p->data;              8       *result = p->data;
 9       read_unlock(&listmutex);        9       rcu_read_unlock();
10       return 1;                      10       return 1;
11     }                                11     }
12   }                                  12   }
13   read_unlock(&listmutex);           13   rcu_read_unlock();
14   return 0;                          14   return 0;
15 }                                    15 }

 1 int delete(long key)                  1 int delete(long key)
 2 {                                     2 {
 3   struct el *p;                       3   struct el *p;
 4                                       4
 5   write_lock(&listmutex);             5   spin_lock(&listmutex);
 6   list_for_each_entry(p, &head, lp) { 6   list_for_each_entry(p, &head, lp) {
 7     if (p->key == key) {              7     if (p->key == key) {
 8       list_del(&p->lp);               8       list_del_rcu(&p->lp);
 9       write_unlock(&listmutex);       9       spin_unlock(&listmutex);
                                        10       synchronize_rcu();
10       kfree(p);                      11       kfree(p);
11       return 1;                      12       return 1;
12     }                                13     }
13   }                                  14   }
14   write_unlock(&listmutex);          15   spin_unlock(&listmutex);
15   return 0;                          16   return 0;
16 }                                    17 }
両者の違いは非常に小さい。参照側のロックは rcu_read_lock() と rcu_read_unlock() になり、更新側のロックはリーダー・ライターロックから単純なスピンロックに変更され、kfree()を実行するまえに synchronize_rcu() が呼び出される。
しかし、この場合参照側と更新側が同時に動作する可能性が出てくる。多くの場合はこれは問題とはならないが、使われ方を十分注意する必要がある。たとえば、複数の独立したリストをアトミックに更新しなければならない場合、これをRCUに置き換えるには注意が必要である。
synchronize_rcu() があるということはRCUでは delete() がブロックされる可能性があることを示す。
それが問題となる場合は代わりに call_rcu() を call_rcu (kfree, p) のように使用すればよい。これは参照カウントと組合わせる場合に特に便利である。