この記事では、 libcdsライブラリーを広告する（できれば邪魔にならないように）ことで、ロックフリーのコンテナーを作成する手法を紹介します。



ロックフリーコンテナの安全なメモリ解放のための別の手法、RCUについて説明します。 この手法は、前述のアラハザードポインターアルゴリズムとは大きく異なります。



読み取り-コピー更新（RCU）は、「ほぼ読み取り専用」、つまりめったに変更されないデータ構造用に設計された同期手法です。 このような構造の典型的な例は、マップとセットです。これらのほとんどの操作は検索、つまりデータの読み取りです。 通常のマップでは、呼び出される操作の90％以上がキー検索であると考えられているため、検索操作が最速であることが重要です。 検索の同期は基本的に不要です-ライターのないリーダーは並行して作業できます。 RCUは、読み取り操作に対してのみオーバーヘッドを最小限に抑えます。



Read-Copy Updateという名前はどこから来たのですか？ 当初、このアイデアは非常にシンプルでした。データ構造はめったに変更されません。 変更する必要がある場合は、 コピーを作成し、 コピーで変更（データの追加または削除）を行います。 同時に、パラレルリーダーは元の変更されていない構造で動作します。 ある安全な時点で、読者がいない場合、データ構造を変更されたコピーで置き換えることができます。 その結果、以降のすべてのリーダーには、ライターによって行われた変更が表示されます。





RCUテクノロジーの作成者であり積極的なプロモーターはPaul McKenneyです。 彼は「RCU愛好家」の学校全体を率いており、そこからロックフリーおよび非伝統的な同期スキームの分野で多くの有名な科学者が出てきました。また、彼はLinuxカーネル（Linuxカーネル。





RCUは2002年にLinuxカーネルに導入されて以来、カーネルコードにますます成長しています。右の図を参照してください。 長い間、それはオペレーティングシステムのカーネル専用の同期技術として位置づけられていました。 カーネルはユーザーとシステムの両方のすべてのスレッドを完全に制御するため、カーネル内でデータが変更されたコピーで置き換えられる安全な瞬間を判断するのは非常に簡単です。 しかし、私たちはRCUの応用に興味があります、それは可能ですか？ この質問に答える前に、RCUの理論とそれに使用される用語をより詳細に検討します。

RCUの一般的な説明

RCUの概念に関する上記の説明は非常に単純です。 ご存知のように、アトミック操作があるため、データのコピーを作成することはできませんが、読み取りと並行してデータ構造を「オンザフライ」で変更します。 次に、「リーダー」は、データ構造から要素を削除する以外の操作を実行するスレッドになります。 ライターは、構造から何かを削除するストリームです。 削除されたデータを誰も「踏まない」ときに削除を行う必要があります。そうしないと、ABAの問題からメモリの破損まで、検出が困難な問題が多数発生します。 RCUは、前述のハザードポインタースキームとは異なる方法を使用して、これらすべての問題を解決します。



RCUテクニックの読者は、読み取り側のクリティカルセクションで実行します。 このようなクリティカルセクションに入ると、リーダーはrcu_read_lock()



関数を呼び出し、 rcu_read_lock()



するとrcu_read_lock()



呼び出します。 これらは非常に軽量な機能であり、パフォーマンスにはほとんど影響しません。 Linuxカーネルでは、まったく重量を量りません（ゼロオーバーヘッド）。

ストリームがクリティカル読み取りセクションにない場合、ストリームは静止状態 （静止状態、静止状態）にあると言われます。 各スレッドが少なくとも1回は静止状態にある期間は、 猶予期間と呼ばれます。 猶予期間が終了する前に開始する各重要な読み取りセクションは、猶予期間が終了する前に終了する必要があります。 重要な読み取りセクションは有限であるため、各猶予期間は有限であることが保証されています（スレッドの数は有限であり、優れたプログラマーであり、無限ループやスレッドクラッシュを回避できることが理解されています）。





データ構造から要素を削除するライタースレッドは、構造から要素を除外し、猶予期間の終了を待ちます。 猶予期間の終了とは、削除する要素にアクセスできるリーダーがいないことを意味します（図を参照、その「読み取り」長方形は重要な読み取りセクションです）。 したがって、ライタースレッドはアイテムを安全に物理的に削除できます。

削除は2段階で実行されます。最初の段階である「削除」は、データ構造から要素をアトミックに削除しますが、メモリを物理的に解放しません。 代わりに、ライターは特別なsynchronize_rcu()



プリミティブを呼び出して猶予期間の開始を通知し、終了するのを待ちます。 削除されたアイテムには、ライターと並行して重要な読書セクションを宣言したリーダーのみがアクセスできます（図では、そのようなセクションは灰色で強調表示されています）。 定義により、このような読者はすべて、猶予期間が終了する前に作業を終了します。 猶予期間の終了時、つまり、猶予期間中に開始またはアクティブになったすべての重要な読み取りセクションが完了すると、削除の2番目の段階である「レクラメーション」、つまり要素の下のメモリの物理的な削除が開始されます。



ご覧のとおり、RCUの同期手法は非常に簡単です。 問題は残っています-ユーザーコードで猶予期間の終了を判断する方法は？ 元のRCUは、すべてのスレッドを完全に制御できるため、Linuxカーネルに合わせて大幅に調整されています。 ユーザー空間コードの場合、元のRCUのアプローチは適用できません。

ユーザースペースRCU

この決定は、2009年にP. McKenneyの代表であるM.Desnoyersの論文 （第6章：RCUのUser-Level Implementations）で与えられました。

M.Desnoyersは、ユーザースペースRCU（URCU）の3つのソリューションを提供しています。

• 静止状態ベースのレクラメーションRCUは、読者にとって非常に軽量なスキームですが、クリティカルな読み取りセクション外のスレッドが定期的に 「静止状態になっている」と宣言する必要があります。 このソリューションは、汎用ライブラリーであるlibcdsには適していないため、検討しません。
• 汎用URCUユーザー空間RCUは、一般的な実装に適したアルゴリズムです。これについては以下で説明します。
• 信号処理を介したユーザー空間RCUも興味深い信号ベースのアルゴリズムです（* nixシステムに適していますが、Windowsには適用されません）。 libcdsライブラリに実装されているため、汎用RCUよりもわずかにパフォーマンスが劣っています。 この記事ではそれを考慮しません;興味のある人はM.Desnoyers'aの論文とlibcdsのソースコードを参照します。

汎用URCU

M.Desnoyersは、URCUアルゴリズムを非常に詳細かつ徹底的に解析するため、いくつかの変数と関数の名前のみを変更してlibcdsで採用されているものに対応するようにします。



URCUスキーマは2つの変数を定義します。

 std::atomic<uint32_t> g_nGlobalCtl(1) ; struct thread_record { std::atomic<uint32_t> nThreadCtl; thread_record * pNext; thread_record(): nThreadCtl(0), pNext(nullptr) {} };
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

thread_record



構造体には、スレッドにローカルなデータが含まれ、そのようなすべてのオブジェクトをRCUスレッドのリストにリンクします。

nThreadCtl



の下位31ビットには、URCU呼び出しのネストの深さのカウンターが含まれます（はい、URCUはクリティカルな読み取りセクションのほぼ無制限のネストを許可します）。高ビットは、スレッドがクリティカルな読み取りセクションに入る時点の猶予期間の識別子を決定します。 説明したスキームでは、猶予期間の識別子は2つだけで十分です。

グローバル変数g_nGlobalCtl



の上位ビットには現在の猶予期間の識別子が含まれ、下位ビットはnThreadCtl



スレッドごとの変数を初期化する役割をnThreadCtl



、変更されません。

重要な読み取りセクションから/に出入りするにはaccess_unlock



それぞれ関数access_lock



およびaccess_unlock



使用しaccess_lock



。

 static uint32_t const c_nControlBit = 0x80000000; static uint32_t const c_nNestMask = c_nControlBit — 1; void access_lock() { thread_record * pRec = get_thread_record(); assert( pRec != nullptr ); uint32_t tmp = pRec->nThreadCtl.load( std::memory_order_relaxed ); if ( (tmp & c_nNestMask) == 0 ) { pRec->nThreadCtl.store(g_nGlobalCtl.load( std::memory_order_relaxed ), std::memory_order_relaxed ); std::thread_fence( std::memory_order_acquire ); } else pRec->nThreadCtl.fetch_add( 1, std::memory_order_relaxed ); } void access_unlock() { thread_record * pRec = get_thread_record(); assert( pRec != nullptr ); pRec->nThreadCtl.fetch_sub( 1, std::memory_order_release ); }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

URCUのクリティカルセクションに入ると、呼び出しがネストされているかどうかがチェックされます。 呼び出しがネストされている場合（つまり、下位31ビットのカウンターがゼロではない場合）、ネストカウンターは単純にインクリメントされます。 呼び出しがネストされていない場合、現在のスレッドのnThreadCtl



変数にグローバル変数g_nGlobalCtl



値が割り当てられます。 これは、クリティカルセクションが特定の猶予期間（高ビットg_nGlobalCtl



）に入力されたことを示し、低ビットg_nGlobalCtl



ユニットは現在のストリームのネストカウンターを初期化します。 クリティカルセクションへの最初の最も外部からの入り口では、メモリの獲得バリアが適用されます。 これにより、後続のコードがプロセッサまたはコンパイラによってバリアの上流に移動（「最適化」）されないことが保証されます。 これにより、すべてのプロセッサに対するストリームの現在の猶予期間の可視性が保証されます-この順序に違反すると、URCUアルゴリズムが崩れます。 ネストされたクリティカルセクションに入る場合、現在の猶予期間（高ビット）は変わらないため、バリアは必要ありません。

クリティカルセクション（ access_unlock



）を終了するnThreadCtl



現在のスレッドのnThreadCtl



ネストカウンターが単純に減分されます。 アトミック操作のリリースセマンティクスが適用されます。 実際、ここでリリースバリアが必要になるのは、最上位のクリティカルセクションを離れるとき（ネストカウンターを1から0に移動するとき）、ネストされたクリティカルセクションを離れるとき、リラックスしたセマンティクスで十分です。 ネストカウンターが1から0に移行すると、「ストリームがRCUを使用しなくなった」というアナウンスメントが実際に発生するため、カウンターをリセットするときのリリースバリアが必要です。つまり、猶予期間からの終了はURCUアルゴリズムにとって重要で、コンパイラーまたはプロセッサーによる順序違反アルゴリズムの動作不能につながります。 コード内の状況「0-not 0」を認識するには、条件付き遷移が必要になります。これは、 access_unlock



関数にパフォーマンスを追加する可能性が低く、 access_unlock



クリティカルセクションを使用する主なパターンはネストなしです。



ご覧のとおり、読者側のコードは非常に軽量です。 アトミックな読み取りと書き込みおよびスレッドローカルデータが使用されます。 もちろん、これはゼロオーバーヘッドではありませんが、それでもミューテックスやCASよりもはるかに優れています。



ライタースレッドは、アイテムを物理的に削除する前に、まず猶予期間が完了していることを確認する必要があります。 猶予期間を終了する条件は、次の2つのいずれかです。

• 各スレッドのnThreadCtl
  
  
  
  ビット（ネストカウンター） nThreadCtl
  
  
  
  ゼロに等しい。これは、スレッドがURCUのクリティカルセクションにないことを意味する
• nThreadCtl
  
  
  
  の上位ビットはnThreadCtl
  
  
  
  の上位ビットとnThreadCtl
  
  
  
  しません。これは、猶予期間の開始後にリーダーがクリティカルセクションに入ったことを意味します。

これらの条件は、次の機能によってチェックされます。

 bool check_grace_period( thread_record * pRec ) { uint32_t const v = pRec->nThreadCtl.load( std::memory_order_relaxed ); return (v & general_purpose_rcu::c_nNestMask) && ((( v ^ g_nGlobalCtl.load( std::memory_order_relaxed )) & ~c_nNestedMask )); }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

物理的な削除の前に、ライターは現在の猶予期間の終了を予期するsynchronize



関数を呼び出します。

 std::mutex g_Mutex ; void synchronize() { std::atomic_thread_fence( std::memory_order_acquire ); { cds::lock::scoped_lock<std::mutex> sl( g_Mutex ); flip_and_wait(); flip_and_wait(); } std::atomic_thread_fence( std::memory_order_release ); }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

ここで、 g_Mutex



はURCUアルゴリズムのグローバルミューテックスです（はい、はい！URCUは依然として同期技術であるため、ミューテックスがないため、どこにもありません）。 したがって、1つのライタースレッドのみがsynchronize



入ることができます。 RCUは「ほぼ読み取り専用」のデータ用に配置されることを忘れないでください。したがって、このミューテックスでは特別なクラッシュは想定されていません。

ライターは、 flip_and_wait



関数を呼び出すことにより、猶予期間の終了を予期します。

 void flip_and_wait() { g_nGlobalCtl.fetch_xor( c_nControlBit, std::memory_order_seq_cst ); for (thread_record* pRec = g_ThreadList.head(std::memory_order_acquire); pRec!= nullptr; pRec = pRec->m_pNext ) { while ( check_grace_period( pRec )) { sleep( 10 ); //  10  CDS_COMPILER_RW_BARRIER ; } } }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

この関数は、猶予期間の識別子を変更します。これは、アトミックなfetch_xor



を使用して新しい猶予期間の開始を意味し、すべてのcheck_grace_period



スレッドがこの新しい猶予期間を完了するまで待機します（ fetch_xor



を呼び出しcheck_grace_period



）。 擬似コードでは、待機は10ミリ秒の単純なスリープです。実際のlibcdsコードでは、バックオフ戦略を設定するテンプレートパラメーターが使用されます。



ライターがflip_and_wait



2回呼び出すのflip_and_wait



なぜですか？ 明確にするために、2つのストリームAとBを使用したこの一連のアクションを検討してflip_and_wait



。

• access_lock
  
  
  
  Aはaccess_lock
  
  
  
  呼び出しaccess_lock
  
  
  
  。 この関数の本体では、呼び出しがネストされていないと判断され、グローバルg_nGlobalCtl
  
  
  
  が読み取られますが、これまでnThreadCtl
  
  
  
  変数nThreadCtl
  
  
  
  割り当てられていません（すべてが並行して行われるため、この状況はまったく受け入れられます）
• スレッドBはsynchronize
  
  
  
  呼び出します。 最初のflip_and_wait
  
  
  
  、 flip_and_wait
  
  
  
  の猶予期間識別子ビットが変更されg_nGlobalCtl
  
  
  
  。 現在の猶予期間識別子は1になります
• URCUのクリティカルセクションには誰もいないため（スレッドAが変数nThreadCtl
  
  
  
  値をまだ設定していないことを思い出してnThreadCtl
  
  
  
  ）、スレッドBはsynchronize
  
  
  
  完了します
• nThreadCtl
  
  
  
  Aはその変数nThreadCtl
  
  
  
  割り当てます。 ストリームが、猶予期間の古い値（0に等しい）を読み取ったことを思い出してください。
• access_lock
  
  
  
  Aはaccess_lock
  
  
  
  を終了し、クリティカルセクションで実行を継続しaccess_lock
  
  
  
  
• スレッドBの呼び出しは再度synchronize
  
  
  
  します（明らかに、何かをもう一度削除したい）。 繰り返しますが、現在の猶予期間はg_nGlobalCtl
  
  
  
  にg_nGlobalCtl
  
  
  
  れるため、その識別子は0になります。

ただし、スレッドAは、Bが猶予期間を変更する前に開始したクリティカルセクションにあります。 URCUのセマンティクスへの違反。最終的にはABAからメモリ破損に至るまで、全体的な問題につながります。 リコール： synchronize



は、要素のメモリを物理的に削除する前にライターによって呼び出されます



flip_and_wait



2回、つまり猶予期間の終了を2回待機することで、スレッドの競合的な実行が原因である上記の問題を解決します。

libcdsでのURCU実装

上記のURCUアルゴリズムはすべてのユーザーに適していますが、 各削除の前にかなり重いsynchronize



を呼び出す必要があります。 これを改善する方法はありますか？

はい、ハザードポインターアルゴリズムと同じ方法を使用して、遅延削除を適用できます。 削除する代わりに、要素をバッファに入れます。 バッファーがいっぱいになった場合にのみ、 synchronize



関数を呼び出します。 ハザードポインターとは異なり、URCUでは、バッファーはすべてのスレッドに共通です（一般に、スレッドごとのバッファーを作成できますが、これを妨げるものは何もありません）。

さらに、バッファが一杯になったときにバッファをクリーンアップするために共有したライタの速度を低下させないために、バッファクリーニング機能、つまり実際の削除を別のスレッドに割り当てることができます。



libcdsライブラリには5つの URCU実装があり、それらはすべてcds::urcu



。

• general_instant
  
  
  
  は、説明されているURCUアルゴリズムに完全に準拠した実装です。各削除により、 synchronize
  
  
  
  、バッファリングなしが発生します。 削除が非常に頻繁な操作である場合、つまり、構造が「ほとんど読み取り専用」ではない場合、この実装はかなり遅い
• general_buffered
  
  
  
  は、事前に決められたサイズの一般的なロックフリーバッファを備えた実装です。 Dmitry Vyukovのキューはロックフリーバッファーとして使用されます-cds cds::container::VyukovMPMCCycleQueue
  
  
  
  。 この実装のパフォーマンスは、ハザードポインターに匹敵します。
• general_threaded
  
  
  
  - general_threaded
  
  
  
  と似ていgeneral_buffered
  
  
  
  が、バッファリングは専用スレッドによって行われます。 この実装は、専用ストリームとの追加の同期のため、 general_buffered
  
  
  
  よりわずかに劣りますが、ライターの速度は低下しません。
• signal_buffered
  
  
  
  はgeneral_buffered
  
  
  
  に類似していますが、信号処理URCUに基づいています。 Windowsシステム用ではありません
• signal_threaded
  
  
  
  シグナル処理URCUのgeneral_threadedに類似。 また、Windows用ではありません

このような豊富なURCU実装は、URCUの下でコンテナの特殊化を記述する問題を引き起こします。 実際、URCUスキームのコンテナの実装は、ハザードポインターの実装とは大きく異なります。 したがって、URCUには個別の専門化が必要です。 5つではなく、1つの専門分野が必要です。

URCUでの専門分野の記述を容易にするために、ラッパークラスcds::urcu::gc



が導入されました。

 template <typename RCUimpl> class gc;
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

ここで、 RCUimpl



はRCUimpl



の実装の1つですgeneral_instant



、 general_buffered



など。このようなラッパーがあると、URCUの特殊化を簡単に記述できます。

 template < class RCU, typename Key, typename Value, class Traits > class SplitListMap< cds::urcu::gc< RCU >, Key, Value, Traits > ...
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

libcdsでは、削除時のURCUアルゴリズムの主な機能はsynchronize



ではなく、 retire_ptr



。 この関数は、削除されたアイテムをURCUバッファーに配置し、適切なタイミング（バッファーがいっぱいになったときなど）にsynchronize



呼び出します。 したがって、 synchronize



するための明示的な呼び出しは必要でsynchronize



ませんが、有効です。 さらに、このソリューションはURCUとハザードポインターのインターフェースを統合します。



リストされているすべてのURCUアルゴリズムは、libcdsの典型的な方法で実装されます。それぞれについて、ラッパーオブジェクトコンストラクターcds::urcu::gc<cds::urcu::general_buffered<> >



をmain()



の先頭で呼び出すことで初期化されるグローバルシングルトンオブジェクトがあります、 cds::Initialize()



を呼び出した後cds::Initialize()



：

 #include <cds/init.h> //cds::Initialize  cds::Terminate #include <cds/gc/general_buffered.h> // general_buffered URCU int main(int argc, char** argv) { //  libcds cds::Initialize() ; { //  general_buffered URCU  cds::urcu::gc<cds::urcu::general_buffered<> > gbRCU ; //  main thread  lock-free  // main thread    //   libcds cds::threading::Manager::attachThread() ; // , libcds    //     ... } //  libcds cds::Terminate() ; }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

ハザードポインタースキームと同様に、URCUコンテナーを使用する各スレッドは、特別な方法で初期化する必要があります。

 // cds::threading::Manager #include <cds/threading/model.h> int myThreadEntryPoint(void *) { //     libcds cds::threading::Manager::attachThread() ; //        // lock-free  libcds ... //    libcds cds::threading::Manager::detachThread() ; return 0; }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

libcdsライブラリのURCUコンテナの使用は完全に透過的です。URCUgcでコンテナオブジェクトを宣言するだけです。 URCUを使用した作業の詳細はすべて、コンテナーのURCU特殊化の中に隠されています。 そのようなコンテナにアクセスする場合、外部同期は必要ありません。



libcdsからのURCUの実装に基づいて独自のコンテナクラスを作成する場合は、ライブラリのURCUコンテナの内部デバイスを詳細に理解する必要があります。 原則として、 gc::access_unlock()



なことはありません：メソッドに入るときにgc::access_lock()



をgc::access_unlock()



、終了するときにgc::access_unlock()



をgc::access_unlock()



（ここでgc



はURCU実装の1つです。例外の安全性のために、関数を呼び出す代わりにスコープロックテクニックを使用することをお勧めします） 。 唯一の微妙な点は、要素の削除です：deleteメソッドもクリティカル読み取りセクションにある必要がありますが、 gc::retire_ptr



呼び出すことによる要素の物理的な削除はクリティカルセクションの外側で行う必要があります。そうしないとデッドロックが発生します： gc::retire_ptr



はsynchronize



を呼び出すことができます



Libcdsは、すべてのセットおよびマップクラスのURCU特殊化を定義します。 キューコンテナとスタックコンテナのURCUの特殊化は未定義です。「ほぼ読み取り専用」のコンテナではないため、URCUはそれらに対応していません。