読み取り-コピー-更新

コンピュータサイエンスにおいて、読み取り・コピー・更新（RCU）は、複数のスレッドがポインターを介してリンクされ、共有データ構造（リンクリスト、ツリー、ハッシュテーブルなど）に属する要素を同時に読み取り、更新する際に、ロックプリミティブの使用を回避する同期メカニズムです。^[1]

スレッドが共有メモリ内のデータ構造の要素を挿入または削除するときは常に、すべてのリーダーは古い構造または新しい構造のいずれかを参照して走査することが保証されるため、不整合（たとえば、ヌルポインタの逆参照）を回避できます。^[1]

これは、読み取りのパフォーマンスが極めて重要である場合に使用され、スペースと時間のトレードオフの例であり、より多くのスペースを犠牲にして高速な操作を可能にします。これにより、すべてのリーダーは同期が関与していないかのように処理を進めるため、高速になりますが、更新も困難になります。

この名前は、RCU を使用してリンク構造をその場で更新する方法に由来しています。これを実行するスレッドは、次の手順に従います。

• 新しい構造を作り、
• 古い構造体から新しい構造体にデータをコピーし、古い構造体へのポインタを保存します。
• コピーした新しい構造を修正し、
• 新しい構造体を参照するようにグローバルポインタを更新し、
• オペレーティングシステムカーネルが古い構造体を使用しているリーダーが残っていないと判断するまでスリープします。たとえば、Linuxカーネルではsynchronize_rcu()を使用します。
• カーネルによって起動されると、古い構造の割り当てを解除します。

したがって、構造は、更新を行うためにスレッドのコピーと同時に読み取られるため、「読み取りコピー更新」という名前が付けられています。略語「RCU」は、Linux コミュニティによる多くの貢献の 1 つです。同様の技術の他の名前には、VM/XAプログラマーによるパッシブ シリアル化やMP 遅延、 K42および Tornado プログラマー による生成などがあります。

RCU の重要な特性は、更新中のデータ構造でも、リーダーがデータ構造にアクセスできることです。RCU 更新者は、リーダーをブロックしたり、アクセスの再試行を強制したりすることはできません。この概要では、まず、同時リーダーが存在する場合でも、リンクされた構造にデータを安全に挿入したり、リンクされた構造からデータを削除したりする方法を示します。右側の最初の図は、左から右に時間が進む 4 つの状態の挿入手順を示しています。

最初の状態は、最初はNULLであるgptrという名前のグローバル ポインタを示しています。赤色で表示され、いつでもリーダーによってアクセスされる可能性があるため、更新者が注意する必要があります。新しい構造体にメモリを割り当てると、2 番目の状態に移行します。この構造体は不確定な状態 (疑問符で示される) ですが、リーダーからはアクセスできません (緑色で示される)。構造体はリーダーからアクセスできないため、更新者は同時実行中のリーダーを中断することを恐れずに、必要な操作を実行できます。この新しい構造体を初期化すると、構造体のフィールドの初期化された値を示す 3 番目の状態に移行します。この新しい構造体への参照をgptrに割り当てると、4 番目の最後の状態に移行します。この状態では、構造体はリーダーからアクセス可能であるため、赤色で表示されます。 rcu_assign_pointerプリミティブは、この割り当てを実行するために使用され、同時読み取りがNULLポインターまたは新しい構造体への有効なポインターのいずれかを参照し、2 つの値の混合を参照しないという意味で割り当てがアトミックであることを保証します。rcu_assign_pointer の追加プロパティについては、この記事の後半で説明します。

この手順は、挿入前、挿入中、挿入後にリーダーがデータ構造を同時に走査している場合でも、リンクされたデータ構造に新しいデータを挿入する方法を示しています。右側の 2 番目の図は、4 つの状態の削除手順を示しており、ここでも時間は左から右に進みます。

最初の状態は、要素A、B、およびCを含む連結リストを示しています。3 つの要素はすべて赤色で表示され、RCU リーダーがいつでもそれらのいずれを参照する可能性があるかを示しています。list_del_rcu を使用してこのリストから要素B を削除すると、2 番目の状態に遷移します。要素 B から C へのリンクはそのまま残され、現在要素B を参照しているリーダーがリストの残りを走査できるようになっていることに注意してください。要素Aからリンクにアクセスするリーダーは、要素Bまたは要素Cへの参照を取得しますが、いずれにしても、各リーダーは有効で正しくフォーマットされた連結リストを参照します。要素Bは黄色で表示され、既存のリーダーは要素Bへの参照をまだ持っている可能性があるが、新しいリーダーは参照を取得する方法がないことを示しています。リーダー待ち操作は 3 番目の状態に遷移します。このリーダー待ち操作は、既存のリーダーを待つだけで、新しいリーダーを待つ必要がないことに注意してください。要素Bは緑色で表示され、リーダーがそれを参照できなくなったことを示しています。したがって、アップデーターは要素B を安全に解放できるようになり、4 番目の最終状態に移行します。

2 番目の状態では、異なるリーダーが要素B の有無にかかわらず、2 つの異なるバージョンのリストを見ることができることを繰り返し強調することが重要です。言い換えると、RCU は、空間 (リストの異なるバージョン) と時間 (削除手順の異なる状態) の調整を提供します。これは、時間では調整できても空間では調整できない、 ロックやトランザクションなどのより伝統的な同期プリミティブとはまったく対照的です。

この手順は、削除前、削除中、削除後にリーダーが同時にデータ構造を走査している場合でも、リンクされたデータ構造から古いデータを削除する方法を示しています。挿入と削除を考慮すると、RCU を使用してさまざまなデータ構造を実装できます。

RCU のリーダーは、通常rcu_read_lockとrcu_read_unlockによって区切られる読み取り側クリティカルセクション内で実行されます。RCU 読み取り側クリティカルセクション内にない文は、静止状態にあると言われ、そのような文は、RCU 保護データ構造への参照を保持することは許可されておらず、読み取り待ち操作は、静止状態のスレッドを待つ必要はありません。各スレッドが少なくとも 1 回は静止状態にある期間を 猶予期間と呼びます。定義により、与えられた猶予期間の開始時に存在している RCU 読み取り側クリティカルセクションは、その猶予期間の終了前に完了する必要があります。これは、RCU によって提供される基本的な保証を構成します。さらに、読み取り待ち操作は、少なくとも 1 つの猶予期間が経過するまで待機する必要があります。この保証は、極めて小さな読み取り側のオーバーヘッドで提供できることが分かりました。実際、サーバークラスのLinuxカーネルビルドによって実際に実現される限界ケースでは、読み取り側のオーバーヘッドは正確にゼロです。^[2]

RCU の基本的な保証は、更新を削除フェーズと回収フェーズに分割することで使用できます。削除フェーズでは、データ構造内のデータ項目への参照が削除され (おそらく、これらのデータ項目の新しいバージョンへの参照に置き換えられます)、RCU の読み取り側クリティカル セクションと同時に実行できます。削除フェーズを RCU リーダーと同時に実行しても安全な理由は、現代の CPU のセマンティクスにより、リーダーは部分的に更新された参照ではなく、データ構造の古いバージョンまたは新しいバージョンのどちらかを参照することが保証されるためです。猶予期間が経過すると、古いバージョンを参照するリーダーは存在しなくなるため、回収フェーズでは、その古いバージョンを構成していたデータ項目を解放 (回収) しても安全です。^[3]

更新を削除フェーズと再利用フェーズに分割すると、更新者は削除フェーズをすぐに実行し、削除フェーズ中にアクティブなすべてのリーダーが完了するまで、つまり猶予期間が経過するまで、再利用フェーズを延期することができます。^{[注 1]}

したがって、典型的なRCU更新シーケンスは次のようになります。^[4]

1. RCU で保護されたデータ構造にアクセスするすべてのリーダーが、RCU 読み取り側クリティカル セクション内から参照を実行することを確認します。
2. データ構造へのポインターを削除して、後続のリーダーがデータ構造への参照を取得できないようにします。
3. 猶予期間が経過するまで待機します。これにより、以前のすべてのリーダー (前の手順で削除されたデータ構造へのポインターがまだ保持されている可能性があります) が RCU 読み取り側クリティカル セクションを完了します。
4. この時点では、データ構造への参照を保持しているリーダーは存在しないため、安全に再利用（たとえば、解放）できます。^{[注 2]}

上記の手順 (前の図と一致します) では、アップデーターが削除と再利用の両方のステップを実行していますが、まったく別のスレッドが再利用を実行すると便利な場合がよくあります。参照カウントを使用すると、リーダーが削除を実行できるため、同じスレッドが更新ステップ (上記のステップ (2)) と再利用ステップ (上記のステップ (4)) の両方を実行する場合でも、それらを別々に考えると便利な場合がよくあります。

RCU は、おそらく共有データ構造のための最も一般的な非ブロッキング アルゴリズムです。RCU は、任意の数のリーダーに対して完全に待機フリーです。シングル ライター実装の RCU は、ライターに対してもロックフリーです。 ^[5] RCU の複数のライター実装の中には、ロックフリーのものもあります。^[6] RCU の他の複数のライター実装は、ロックを使用してライターをシリアル化します。^[7]

^{2008年初頭までに、Linuxカーネル[8]}内でRCU APIが2,000回近く使用され、ネットワークプロトコルスタック^[9]やメモリ管理システム^[10]も含まれていました。 2014年3月現在^{[アップデート]}、使用回数は9,000回を超えています。^[11] 2006年以来、研究者はRCUや類似の技術を、動的分析で使用されるメタデータの管理、^[12]、クラスター化されたオブジェクトの有効期間の管理、^{[13] 、} K42研究オペレーティングシステムでのオブジェクトの有効期間の管理、 ^{[14] [15] 、}ソフトウェアトランザクションメモリ実装の最適化など、さまざまな問題に適用してきました。^{[16] [17]} Dragonfly BSDは、LinuxのSleepable RCU (SRCU)実装に最も近いRCUに似た技術を使用しています。

すべてのリーダーが終了するまで待つことができるため、RCU リーダーははるかに軽量な同期を使用できます。場合によっては、まったく同期を使用しなくても済みます。対照的に、より一般的なロックベースのスキームでは、更新者がデータ構造を削除しないように、リーダーは重量同期を使用する必要があります。その理由は、ロックベースの更新者は通常、データをその場で更新するため、リーダーを除外する必要があるためです。対照的に、RCU ベースの更新者は通常、単一の整列ポインタへの書き込みが最新の CPU ではアトミックであるという事実を利用し、リーダーを中断することなく、リンクされた構造内のデータのアトミックな挿入、削除、および置換を可能にします。その後、同時実行 RCU リーダーは古いバージョンにアクセスし続けることができ、ロック競合がない場合でも、最新のSMPコンピューター システムで非常にコストがかかるアトミックな読み取り-変更-書き込み命令、メモリ バリア、およびキャッシュ ミスを省くことができます。 ^{[18] [19]} RCU の読み取り側プリミティブの軽量な性質は、優れたパフォーマンス、スケーラビリティ、およびリアルタイム応答以外にも、追加の利点を提供します。たとえば、ほとんどのデッドロックやライブロック状態に対する耐性を提供します。^{[注 3]}

もちろん、RCU にも欠点があります。たとえば、RCU は、読み取りがほとんどで更新が少ない状況で最も効果的に機能する特殊な手法ですが、更新のみのワークロードにはあまり適していません。別の例として、RCU のリーダーとアップデータが同時に実行できるという事実は、RCU の読み取り側プリミティブの軽量な性質を可能にするものですが、一部のアルゴリズムは読み取り/更新の同時実行に適さない場合があります。

RCU の経験は 10 年以上ありますが、その適用範囲の正確な範囲は依然として研究対象となっています。

この技術は、1995 年 8 月 15 日に発行され、Sequent Computer Systemsに譲渡された米国 ソフトウェア 特許 5,442,758のほか、米国特許 5,608,893 (2009 年 3 月 30 日に失効)、米国特許 5,727,209 (2010 年 4 月 5 日に失効)、米国特許 6,219,690 (2009 年 5 月 18 日に失効)、および米国特許 6,886,162 (2009 年 5 月 25 日に失効) でカバーされています。現在失効している米国特許4,809,168 は、密接に関連する技術をカバーしています。RCU は、SCO 対 IBM訴訟の 1 つの請求の対象でもあります。

RCUは多くのオペレーティングシステムで利用可能であり、 2002年10月にLinuxカーネルに追加されました。liburcuなどのユーザーレベルの実装も利用可能です。^[20]

Linuxカーネルバージョン2.6のRCU実装は、よく知られているRCU実装の1つであり、この記事の残りの部分でRCU APIのインスピレーションとして使用されます。コアAPI（アプリケーションプログラミングインターフェース）は非常に小さいです。^[21]

• rcu_read_lock(): RCU で保護されたデータ構造をマークして、そのクリティカル セクションの全期間にわたって再利用されないようにします。
• rcu_read_unlock(): リーダーが RCU 読み取り側クリティカル セクションを終了していることをリクレーマに通知するために使用します。RCU 読み取り側クリティカル セクションはネストされている場合や重複している場合があることに注意してください。
• synchronize_rcu(): すべての CPU 上の既存の RCU 読み取り側クリティカル セクションがすべて完了するまでブロックします。後続の RCU 読み取り側クリティカル セクションが完了するまで必ずしも待機するわけでsynchronize_rcuはないことに注意してください。たとえば、次の一連のイベントを考えてみましょう。

	         CPU 0 CPU 1 CPU 2
	     ---------- ------------------------ -------- -------
	 1. rcu_read_lock()
	 2. synchronize_rcu() に入る
	 3. rcu_read_lock()
	 4. rcu_read_unlock()
	 5. synchronize_rcu() を終了する
	 6. rcu_read_unlock()

は、読み取りが完了したかどうか判断する必要がある API であるためsynchronize_rcu、その実装が RCU の鍵となります。読み取りが集中する状況を除くすべての状況で RCU が有用であるためには、synchronize_rcuのオーバーヘッドも非常に小さくなければなりません。

あるいは、ブロックする代わりに、 synchronize_rcu は、進行中のすべての RCU 読み取り側クリティカル セクションが完了した後に呼び出されるコールバックを登録することもできます。このコールバック バリアントは、call_rcuLinux カーネルで呼び出されます。

• rcu_assign_pointer(): アップデータは、この関数を使用して、RCU 保護されたポインタに新しい値を割り当て、アップデータからリーダーに値の変更を安全に伝えます。この関数は新しい値を返し、特定の CPU アーキテクチャに必要なメモリ バリア命令も実行します。おそらくもっと重要なのは、どのポインタが RCU によって保護されているかを文書化するのに役立つことです。
• rcu_dereference(): リーダーは、rcu_dereferenceRCU 保護ポインタを取得するために使用します。このポインタは、安全に逆参照できる値を返します。また、コンパイラまたは CPU が必要とするディレクティブも実行します。たとえば、gcc の volatile キャスト、C/C++11 の memory_order_consume ロード、または古い DEC Alpha CPU が必要とするメモリバリア命令などです。 によって返される値は、rcu_dereference囲む RCU 読み取り側クリティカルセクション内でのみ有効です。 と同様にrcu_assign_pointer、 の重要な機能はrcu_dereference、どのポインタが RCU によって保護されているかを文書化することです。

右側の図は、各 API がリーダー、アップデーター、リクレーマー間でどのように通信するかを示しています。

rcu_read_lockRCU インフラストラクチャは、、、rcu_read_unlockおよび呼び出しの時間シーケンスを観察して、(1)呼び出しが呼び出し元に戻るタイミングと (2)コールバックが呼び出されるタイミングを決定します。RCU インフラストラクチャの効率的な実装ではsynchronize_rcu、対応する API の多くの使用にわたってオーバーヘッドを償却するために、バッチ処理を多用します。 call_rcusynchronize_rcucall_rcu

RCUには、RCUの理解を助ける非常に単純な「おもちゃ」の実装があります。このセクションでは、非プリエンプティブ環境で動作するそのような「おもちゃ」の実装の1つを紹介します。^[22]

void rcu_read_lock ( void ) { }   

void rcu_read_unlock ( void ) { }   

void call_rcu ( void ( * callback ) ( void * ), void * arg ) { // コールバック/引数のペアをリストに追加}      

    


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

        

    各CPUに対して、 CPUの現在のタスクをCPUにスケジュールします。 
        

    call_rcuリストの各エントリに対して、 entry -> callback ( entry - > arg ); }      
         

コード サンプルでは、rcu_assign_pointer​​およびはrcu_dereference無視しても大きな問題はありません。ただし、有害なコンパイラ最適化を抑制し、CPU がアクセスを並べ替えるのを防ぐために、これらが必要です。

#define rcu_assign_pointer(p, v) ({ \ 
    smp_wmb(); /* 前回の書き込みを順序付けます。 */ \ 
    ACCESS_ONCE(p) = (v); \ 
})

#define rcu_dereference(p) ({ \ 
    typeof(p) _value = ACCESS_ONCE(p); \ 
    smp_read_barrier_depends(); /* ほとんどのアーキテクチャでは nop */ \ 
    (_value); \ 
})

rcu_read_lockと は何もしないことに注目してくださいrcu_read_unlock。これが、非プリエンプティブカーネルにおける古典的な RCU の大きな強みです。リード側のオーバーヘッドは、DEC Alpha CPUsmp_read_barrier_depends()以外では空のマクロと同様に、正確にゼロです。 ^{[23] [検証失敗]}そのようなメモリバリアは、最近の CPU では不要です。マクロは、ほとんどの場合、追加のコードを生成しない volatile キャストです。そして、 がデッドロックサイクルに参加したり、リアルタイムプロセスがスケジュール期限に間に合わなかったり、優先度の逆転を招いたり、高いロック競合を引き起こしたりするような方法はありません。しかし、このおもちゃの RCU 実装では、RCU リード側クリティカルセクション内でブロックすることは違法であり、純粋なスピンロックを保持している間にブロックすることも違法です。 ACCESS_ONCE()rcu_read_lock

の実装はsynchronize_rcusynchronize_cpu の呼び出し元を各 CPU に移動し、すべての CPU がコンテキストスイッチを実行できるようになるまでブロックします。これは非プリエンプティブな環境であり、RCU 読み取り側クリティカルセクション内でのブロックは違法であり、RCU 読み取り側クリティカルセクション内にプリエンプションポイントは存在できないことを思い出してください。したがって、特定の CPU がコンテキストスイッチを実行する場合 (別のプロセスをスケジュールするため)、この CPU は先行するすべての RCU 読み取り側クリティカルセクションを完了している必要があります。すべての CPU がコンテキストスイッチを実行すると、先行するすべての RCU 読み取り側クリティカルセクションが完了します。

RCUはさまざまな方法で使用できますが、RCUの非常に一般的な使用法は、リーダーライターロックに類似しています。次のコードを並べて表示すると、リーダーライターロックとRCUがいかに密接に関連しているかがわかります。^[24]

   /* リーダーライターロック */ /* 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 /* その他のデータフィールド */ 6 /* その他のデータフィールド */ 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 0を返す; 14 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 1を返す; 12 } 13 } 13 } 14 } 14 write_unlock ( & listmutex ); 15 spin_unlock ( & listmutex ); 15 0を返す; 16 0を返す; 16 } 17 }                         
                                         
                                   
                                         
                     
               
                                  
                               
                       
                                                
                                     
                                       
                                           
                                         
                 
                                   
                                       

2 つのアプローチの違いは非常に小さいです。読み取り側のロックはrcu_read_lockおよびに移動しrcu_read_unlock、更新側のロックはリーダー/ライター ロックから単純なスピンロックに移動し、 がsynchronize_rcuに先行しますkfree。

ただし、潜在的な問題が 1 つあります。読み取り側と更新側のクリティカル セクションが同時に実行できるようになったことです。多くの場合、これは問題にはなりませんが、いずれにしても慎重に確認する必要があります。たとえば、複数の独立したリスト更新を 1 つのアトミック更新として扱う必要がある場合、RCU への変換には特別な注意が必要です。

また、 の存在は、synchronize_rcuの RCU バージョンがdeleteブロックできることを意味します。これが問題になる場合は、の代わりにcall_rcuのように使用できます。これは、参照カウントと組み合わせると特に便利です。 call_rcu (kfree, p)synchronize_rcu

RCUに似た技術やメカニズムは、これまで何度も独立して発明されてきました。^[25]

1. HT KungとQ. Lehmanは、ガベージコレクターを使用してバイナリ検索木へのRCUのようなアクセスを実装することを説明しました。^[26]
2. ウディ・マンバーとリチャード・ラドナーは、クンとレーマンの研究を非ガベージコレクション環境に拡張し、削除時に実行中のすべてのスレッドが終了するまで回収を延期することで、長寿命スレッドを持たない環境でも機能するようにした。^[27]
3. リチャード・ラシッドらは、すべてのCPUがTLBをフラッシュするまで仮想アドレス空間の再利用を延期する遅延変換ルックアサイドバッファ（TLB）実装について説明しました。これは、一部のRCU実装と精神的に似ています。^[28]
4. James P. Hennessy、Damian L. Osisek、Joseph W. Seigh, IIは1989年に米国特許4,809,168を取得しました（現在は失効）。この特許はIBMメインフレームのVM/XAで使用されていたと思われるRCUのようなメカニズムについて説明しています。^[29]
5. ウィリアム・ピューは、読者による明示的なフラグ設定に依存するRCUのようなメカニズムを説明した。^[30]
6. Aju Johnは、RCUのような実装を提案した。これは、読み取り側が一定時間内にすべて完了するという仮定の下、更新側が一定時間待機するだけというものであり、ハードリアルタイムシステムでは適切かもしれない。^[31] Van Jacobsonは1993年に同様の方式を提案した（口頭によるコミュニケーション）。
7. J. SlingwineとPE McKenneyは1995年8月に米国特許5,442,758を取得しました。この特許では、 DYNIX/ptxと後にLinuxカーネルに実装されたRCUについて説明しています。 ^[32]
8. B. Gamsa、O. Krieger、J. Appavoo、M. Stummは、トロント大学のTornado研究用オペレーティングシステムと、それに密接に関連するIBM Research K42研究用オペレーティングシステムで使用されているRCUに似たメカニズムについて説明しました。^[33]
9. Rusty RussellとPhil Rumpfは、Linuxカーネルモジュールのアンロードを処理するためのRCUのような技術について説明しました。^{[34] [35]}
10. D. Sarma は 2002 年 10 月に Linux カーネルのバージョン 2.5.43 に RCU を追加しました。
11. ロバート・コルビンらは、RCUに似た遅延並行リストベースセットアルゴリズムを正式に検証した。^[36]
12. M. Desnoyersらはユーザー空間RCUの記述を公開した。^{[37] [38]}
13. A. Gotsmanらは分離論理に基づいてRCUの形式意味論を導出した。^[39]
14. イラン・フレンケル、ローマン・ゲラー、ヨラム・ランバーグ、ヨラム・スニールは2006年に米国特許7,099,932を取得しました。この特許は、読み取り/書き込みの一貫性を強制し、読み取り/書き込みの同時実行を可能にする方法でディレクトリサービスを使用してサービス品質ポリシー管理情報を取得および保存するためのRCUのようなメカニズムを説明しています。^[40]

• 同時実行制御
• コピーオンライト
• ロック（コンピュータサイエンス）
• ロックフリーおよび待機フリーのアルゴリズム
• マルチバージョン同時実行制御
• プリエンプティブマルチタスク
• リアルタイムコンピューティング
• リソース競合
• 資源不足
• 同期

Bauer, RT、(2009 年 6 月)、「相対論的プログラムの運用検証」PSU 技術レポート TR-09-04 (http://www.pdx.edu/sites/www.pdx.edu.computer-science/files/tr0904.pdf)

• Paul E. McKenney、Mathieu Desnoyers、Lai Jiangshan: ユーザー空間 RCU。Linux Weekly News。
• Paul E. McKenney と Jonathan Walpole: 「RCU とは、根本的に何ですか?」、「RCU とは? パート 2: 使用法」、および「RCU パート 3: RCU API」。Linux Weekly News。
• ポール・E・マッケニーの RCU ウェブページ
• Hart、McKenney、および Demke Brown (2006)。ロックレス同期の高速化: メモリ再利用のパフォーマンスへの影響。RCUのパフォーマンスを他のロックレス同期メカニズムと比較した IPDPS 2006 最優秀論文。 ジャーナル バージョン(著者として Walpole を含む)。
• 米国特許 5,442,758 (1995) 「実行履歴とスレッド監視を利用して、マルチプロセッサ システムで相互排他制御のオーバーヘッドを削減し、一貫性を維持するための装置および方法」
• Paul McKenney: スリープ可能な RCU。Linux Weekly News。