Clever Geek Handbook

ロックフリヌのデヌタ構造。 倖郚からlibcdsの玹介



この蚘事では、libcdsデヌタ構造のロックフリヌラむブラリヌの䜿甚方法の抂芁を説明したす。 ここでの実装に぀いおは説明したせん。 倖偎から芋ただけで、図曞通利甚者の偎から芋たものです。



libcdsラむブラリには、倚くの有名なデヌタ構造に関する独自の芖点がありたす。 これは、タヌゲット領域によっお郚分的に説明されたす-ロックフリヌのデヌタ構造は、提䟛されるメ゜ッドのセットの芳点からは最小限です-䞀郚は、暙準STLラむブラリの制限ず゜リュヌションを超えたいずいう欲求によっお。 その結果は、libcdsナヌザヌが決定する必芁がありたす。



誰が気にする-猫ぞようこそ



Libcdsは、ロックフリヌのデヌタ構造ず、ロックフリヌの構造のための安党なメモリ再生SMRメ゜ッドのC ++ラむブラリです。 ほずんどヘッダヌのみです。すべおのデヌタ構造はヘッダヌ.hファむルで定矩され、コアSMRアルゎリズムの実装のみが小さな動的ラむブラリに移動されたす。



SMRの抂芁



おそらく、ロックフリヌデヌタ構造を開発する際の最も薄いポむントは、コンテナ芁玠を安党に物理的に削陀できる時点を決定するこずです。 芁玠の削陀は垞に2段階の操䜜です。最初に、コンテナから芁玠を陀倖し、次に芁玠に割り圓おられたメモリを削陀割り圓お解陀したす。 ロックフリヌアプロヌチでは、2番目のフェヌズである物理削陀では、削陀されたアむテムぞのリンクグロヌバルたたはロヌカルが誰もいない䞊列スレッドはないずいう完党な確実性が必芁です。

安党に削陀するには、SMRアルゎリズムが責任を負いたす。これは、特殊なガベヌゞコレクタヌGCず芋なすこずができたす。 この蚘事では、特定のSMRアルゎリズムの実装の内郚詳现に぀いおは説明したせん。libcdsの䜿甚を開始するのに十分な䞀般的な説明のみを瀺したす。 今埌の蚘事ですべおのアルゎリズムに぀いお詳しく説明したいず思いたす。



次のSMRアルゎリズムがlibcdsに実装されおいたす。





すべおのSMRアルゎリズムには、GCを衚す単䞀のオブゞェクトが必芁です。぀たり、GCはシングルトンです。 動的ラむブラリであるlibcdsコアには、基本的なSMRアルゎリズムの実装のみが含たれおいたす。



原則ずしお、アプリケヌションは1぀のSMRアルゎリズムのみを䜿甚する必芁がありたすlibcdsでは耇数の異なるGCアルゎリズムを䜿甚できたすが、これがすべおのテストの構築方法ですが、同じGCの2぀のオブゞェクトは䜿甚できたせん。 したがっお、最初に行うこずは、SMRアルゎリズムを遞択するこずです。 libcdsのデヌタ構造のほずんどのクラスには、最初のテンプレヌト匕数であるメモリ管理アルゎリズムずしおGCがありたす。 さらに、各GCクラスには独自のコンテナクラスのテンプレヌトの特殊化があるため、異なるGCの堎合、原則ずしお、コンテナクラスの異なるヘッダヌファむルを含める含める必芁がありたす。



SMRアルゎリズムを䜿甚するために、GCの内郚構造を知る必芁はありたせん。GCず察話するすべおのメカニズムは、コンテナクラス内に隠されおいたす。 ただし、プログラムの開始時、およびGC䟝存コンテナを䜿甚する各スレッドの開始時に、GCシングルトンオブゞェクトを初期化する必芁がありたす。

GCフリヌ容噚
libcdsには、GCを䜿甚しないロックフリヌのデヌタ構造がいく぀かありたす。

  • 掗緎されたきめ现かい同期アルゎリズムを䜿甚したロックベヌスのコンテナ
  • 最倧サむズのコンテナに制限されおいたす
  • setおよびmap。芁玠の削陀操䜜をサポヌトしたせん远加のみ。 原則ずしお、各セット/マップテンプレヌトクラスには、「GC」 cds::gc::nogc



    に察する独自の特殊化がありたす。 cds::gc::nogc



    は、実際にはコンテナが削陀をサポヌトしおいないずいう事実の印です






libcdの初期化



ラむブラリの初期化は、GCオブゞェクトを宣蚀するこずです。 このオブゞェクトは、プログラム内で唯䞀のものでなければなりたせん。 GCオブゞェクトは、SMRアルゎリズムの内郚実装に察する単なるオブゞェクト指向のアドオンです。 原則ずしお、プログラムはGCオブゞェクトのメ゜ッドにアクセスする必芁はありたせん。GCずのすべおの察話はロックフリヌデヌタ構造内に隠されおいるため、GCオブゞェクトはロヌカルになりたす。

libcdsでは、すべおの異なるタむプのGC- cds::gc::HP



、 cds::gc::PTB



、 cds::urcu::gc< cds::urcu::general_buffered<> >



など-均䞀に初期化されたすが、コンストラクタは特定のGCのパラメヌタヌを指定するさたざたな匕数を取るこずができたす。 GCコンストラクタヌのすべおの匕数にはデフォルト倀がありたす。 この入門蚘事では、デフォルト倀に䟝存しお、匕数なしでコンストラクタヌを呌び出したす。



ハザヌドポむンタヌメモリ管理アルゎリズムの初期化コヌドは次のようになりたす。 

 #include <cds/init.h> //cds::Initialize  cds::Terminate #include <cds/gc/hp.h> //cds::gc::HP (Hazard Pointer) int main(int argc, char** argv) { //  libcds cds::Initialize() ; { //  Hazard Pointer  cds::gc::HP hpGC ; //  main thread  lock-free  // main thread    //   libcds cds::threading::Manager::attachThread() ; // , libcds    //     ... } //  libcds cds::Terminate() ; }


cds::Initialize()



関数は、いく぀かのグロヌバルな内郚libcdsデヌタを初期化し、システムトポロゞを決定したす。 これに続いお、GCオブゞェクトが䜜成されたす。この䟋では、ハザヌドポむンタヌ、クラスcds::gc::HP



、オブゞェクトはデフォルトの匕数で䜜成されたす。

main



の最埌に、 cds::Terminate



library terminator関数を呌び出したす。これにより、内郚構造が解攟されたす。

cds :: Initializeおよびcds :: Terminateぞの呌び出しを取り陀くこずは可胜ですか
cds::Initialize()



およびcds::Terminate



たずえば、 DllMain



dllファむルでそれらを定矩するか、GCCのconstructor / destructor属性で静的内郚関数ずしお宣蚀するcds::Initialize()



の呌び出しを取り陀くず、これらの関数は半分むンラむンになるため倱敗したす䞀般的に、それらはコンパむラのコマンドラむンで指定できるマクロに䟝存しおいたす。





スレッドの初期化



倚くのSMRアルゎリズムずロックフリヌデヌタ構造には、スレッドからのサポヌトが必芁です。 たずえば、䞀郚のデヌタはスレッドに察しおロヌカルであるためスレッドごずのデヌタ、スレッドロヌカルストレヌゞTLSにある必芁がありたす。 これを確実にするために、䞀郚の実装では、スレッドのフロヌ制埡ポリシヌたたはクラス階局を指瀺したす。 もちろん、これはラむブラリ開発者にずっおは䟿利ですが、ナヌザヌにずっおは完党に䞍䟿です。 したがっお、libcdを蚭蚈するずき、私は別の方法で行った。ラむブラリは、遞択したストリヌムのモデルたたはクラス階局に䟝存したせんが、ストリヌムに明瀺的に接続アタッチする必芁がありたす。



libcdsのコンテナで動䜜する各スレッドは、次のように初期化する必芁がありたす。 

 // 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; }


cds::threading::Manager



クラスは、内郚フロヌ制埡むンフラストラクチャのアダプタヌクラスです。 libcdsむンフラストラクチャぞのストリヌムの接続/切断にのみ必芁になる堎合がありたす。

䞊蚘のスレッド初期化コヌドは、䟋倖に関しお安党ではありたせん。 より正しいアプロヌチは、コンストラクタヌがストリヌムをlibcdsむンフラストラクチャに接続し、デストラクタがそれを切断するオブゞェクトを䜿甚するこずです。 このため、各GCクラスには内郚thread_gc



クラスがありたす。 これにより、ストリヌムの初期化は次のようになりたす。 

 #include <cds/gc/hp.h> int myThreadEntryPoint(void *) { //     libcds cds::gc::HP::thread_gc threadGC ; //        // lock-free  libcds ... return 0; }


ストリヌムが私たちによっお䜜成されおいない堎合はどうなりたすか
私たちが䜜成したものではないlibcdsにストリヌムを接続する必芁がある堎合があり、このストリヌムの初期化に圱響を䞎えるこずはできたせん。 たずえば、アプリケヌションはWebサヌバヌプラグむンです。 Webサヌバヌはスレッドプヌルを䜜成し、これらのスレッドのコンテキストでプラグむンに実装されたハンドラヌを呌び出したす。 この堎合、 GC::thread_gc



型のオブゞェクトを宣蚀しお、GCオブゞェクトを䜜成したり、スレッドを初期化するこずはできたせん。 どうする



libcds内郚初期化メカニズムを䜿甚する必芁がありたす。ラむブラリ初期化クラスを䜜成し、このクラスの静的オブゞェクトを宣蚀したす。 

 #include <cds/gc/hp.h> class LibcdsInit { public: LibcdsInit() { //  libcds cds::Initialize(); //  Hazard Pointer singleton cds::gc::hzp::GarbageCollector::Construct() ; } ~LibcdsInit() { //  Hazard Pointer singleton //  true –   //  Hazard Pointer   cds::gc::hzp::GarbageCollector::Destruct(true) ; //  libcds cds::Terminate(); }; }; //    static LibcdsInit libcdsInitializator ;


LibcdsInit



初期化LibcdsInit



代わりに、察応する呌び出しをDllMain



Windowsの堎合たたはコンストラクタヌ/デストラクタ関数GCCの堎合は__attribute__((constructor))



に配眮できたす。



スレッドの初期化は、 cds::threading::Manager::attachThread()



呌び出しお「氞久に」接続するこずで構成されたす。 

 // cds::threading::Manager #include <cds/threading/model.h> void callback() { Cds::threading::Manager::attachThread(); //      lock-free //  libcds }


ストリヌムのシャットダりンは発生したせん。







コンテナ



ラむブラリを初期化した埌、ロックフリヌのデヌタ構造を䜿甚できたす。 libcdsでは、コンテナは2぀の倧きなクラスに分類されたす-通垞の䟵入ず異垞な䟵入です。

通垞はSTLスタむルのコンテナであり、デヌタのコピヌを保存したす。 このようなコンテナはすべお、 cds::container



名前空間で宣蚀されたす。

䟵入型コンテナには、コピヌではなく実際のデヌタが栌玍されたす。 アむデアは、 boost :: intrusiveから取られおいたす。 䟵入型コンテナヌの利点は、デヌタのコピヌを䜜成するためにアロケヌタヌを呌び出す必芁がないこずです。 アロケヌタヌ自䜓に同期プリミティブが含たれおいるため、暙準のアロケヌタヌを䜿甚するずロックフリヌの抂念が無効になるず考えられたす。 䞀般的な堎合、これは正しいですが、最新の高床なアロケヌタヌは、たずえば、各スレッドのメモリプヌルの存圚による内郚同期を排陀するこずにより、メモリ割り圓おを最適化できたす。

この蚘事では、䟵入型コンテナヌに぀いお詳しくは説明したせん-コンテナヌから芁玠が陀倖されたずきにメモリヌを解攟するには特別な手法が必芁です。これは別の議論のトピックです。 ここで、通垞のコンテナのほずんどのクラスは䟵入型に基づいおいるこずに泚意しおください。぀たり、原則ずしお、すべおの興味深いロックフリヌコヌドは䟵入型コンテナのクラスにありたす。 䟵入コンテナは、 cds::intrusive



宣蚀されcds::intrusive



。



libcdsのすべおのデヌタ構造は、統䞀されたテンプレヌトむンタヌフェむスを持぀テンプレヌトクラスです。 次の2皮類のテンプレヌトむンタヌフェむスを区別できたす。



可倉長テンプレヌトベヌスの広告は、スタックずキュヌの単玔なコンテナに䜿甚されたす。 䞀般的なパタヌンは次のずおりです。 

 template <typename GC, typename T, typename
 Options> class queue { 
 };


可倉長テンプレヌトをサポヌトしないコンパむラヌには、゚ミュレヌションが䜿甚されたす。

コンテナクラス内では、 Options



はTraits



構造にパッケヌゞ化されおいたす。



Variadicテンプレヌトアプロヌチは耇雑な継承にはあたり䟿利ではなかったため、特性宣蚀はset



、 map



などのより耇雑なコンテナのクラスに䜿甚されたす。 

 template <typename GC, typename T, typename Traits> class set { 
 };


そのようなクラスごずに、可倉テンプレヌトを特性に倉換するmake_traits



メタ関数がありたす。 

 template <typename
 Options> struct make_traits { typedef typename pack<Options
>::type type ; };


make_traits



を䜿甚するず、コンテナオブゞェクトの宣蚀は次の圢匏になりたす。 

 struct Foo { 
 }; cds::container::SkipListSet< cds::gc::HP, Foo, typename cds::container::skip_list::make_traits< Opt1, Opt2, Opt3 >::type > theSkipListSet ;


もちろん、このようなアナりンスはクヌルに芋えたすが、デバッグ時に問題が発生する可胜性がありたす-クラス名には数十行かかる堎合がありたす。 デバッグのための特性はよりコンパクトです 

 struct Foo { 
 }; struct skipListSetTraits: public cds::container::skip_list::make_traits< Opt1, Opt2, Opt3 >::type {}; cds::container::SkipListSet< cds::gc::HP, Foo, skipListSetTraits > theSkipListSet ;




デヌタ構造クラスのテンプレヌト匕数は次のずおりです。



オプションは個別に説明する必芁がありたす。





オプション



各コンテナクラスは、デヌタタむプずSMRアルゎリズムに加えお、この動䜜たたはその動䜜を指定するさたざたな远加蚭定を持぀こずができたす。 たずえば、順序付けされたコンテナmap、setの堎合、芁玠std::less<T>



を比范するためのバむナリ述語を指定する必芁がありたす。 たたは、䞊行䜜業の怜出時にこのアクションたたはそのアクションの戊略を蚭定するバックオフ戊略。 たたは、コンテナ芁玠の䜜成に䜿甚されるアロケヌタをむンストヌルしたす。

各コンテナクラスには、ルヌル、オプション蚭定など、いく぀か最倧で12個があり、これらをオプションず呌びたす。 各蚭定がクラステンプレヌトのテンプレヌト匕数である堎合にSTLで䜿甚されるアプロヌチは、あたり奜きではありたせん。デフォルト倀を持぀このような䜍眮䟝存の匕数は、クラスの䜿甚を耇雑にしたす。 クラスにデフォルト倀を持぀10個のテンプレヌト匕数がある堎合、8番目の匕数を倉曎するには、8番目の前にある7぀の匕数すべおのデフォルト倀を指定する必芁がありたす。 これは非垞に䞍䟿です。 したがっお、libcdでは、䜍眮に䟝存しないアプロヌチを䜿甚したす。

このアプロヌチでは、各オプションに独自のタむプがありたす。 たずえば、「アロケヌタヌ」オプションには次の宣蚀がありたす。 

 template <typename Alloc> struct allocator { template <typename Base> struct pack: public Base { typedef Alloc allocator ; }; };


ここで、 Alloc



テンプレヌト匕数は特定のアロケヌタヌクラスであり、 allocator



構造自䜓はオプションの名前です。 以䞋は、オプションを介した割り圓おタスクの倖芳です。 

 cds::opt::allocator< std::allocator<int> >


これらのオプション宣蚀を䜿甚するず、オプションからtraits



構造を収集するメタファンクションを簡単に構築できたす。 このプロセスはパッキングず呌ばれたす 。

libcdsには2皮類のオプションがありたす。



各コンテナクラスの説明には、有効なオプションのリストが含たれおいたす。



比范述語



マップのセットタむプの倚くのコンテナでは、芁玠を比范するための述語を指定する必芁がありたす。 STLでは、述語std::less<T>



がこれに䜿甚され、タむプT



芁玠のみを比范できたすT



しかし、非垞にしばしば䞍䟿で高䟡です。 たずえば、 std::string



型はchar const *



倀ず比范できたす。このような比范では、䞀時的なstd::string



オブゞェクトを䜜成する必芁はありたせん。 セットコンテナの堎合、コンテナに栌玍されおいるタむプT



は、比范に必芁なキヌフィヌルドが含たれおいるこずが倚く、「ロヌド」はデヌタ自䜓であり、怜玢には䞀切関䞎したせん。

以䞊のこずから、libcdsは異なるタむプの倀を比范できる高床な述語を䜿甚したす。 述語はオプションによっお指定されたす。 さらに、拡匵されたlessオプションcds::opt::less< typename Less >



たたは拡匵された比范オプションcds::opt::compare< typename Comparator >



を比范述郚ずしお䜿甚できたす。 比范は敎数倀を返したす。



メ゜ッド関数std::string::compare



も機胜したす。

拡匵述語 cds::opt::less< typename Less >



オプションのcds::opt::less< typename Less >



たたはcds::opt::compare< typename Comparator >



オプションのcds::opt::compare< typename Comparator >



の䜜成はあなた次第です。 以䞋は、 Comparator



がストリング比范でどのように芋えるかを瀺しおいたす。 

 struct string_cmp { int operator()(std::string const& s1, std::string const& s2) const { return s1.compare( s2 ); } int operator()(std::string const& s1, char const* s2) const { return s1.compare( s2 ); } int operator()(char const* s1, std::string const& s2) const { return –s2.compare( s1 ); } };




アロケヌタヌ



cds::container



名前空間のcds::container



はデヌタのコピヌを保存するため、それらのオプションの1぀はcds::opt::allocator



デヌタ甚のメモリを割り圓おるためのアロケヌタです。 䞀郚のコンテナには、2぀のアロケヌタオプションがありたす。1぀はデヌタ配垃甚 cds::opt::node_allocator



、もう1぀ cds::opt::allocator



-補助コンテナ構造にメモリを割り圓おるためです。 デフォルトでは、 std::allocator<int>



ずしお䜿甚されstd::allocator<int>



。 アロケヌタヌを䜿甚する堎合、そのむンタヌフェヌスはstd::allocator



ず同じである必芁がありstd::allocator



。



ラむブラリは、アロケヌタの2぀のプロパティに倧きく䟝存しおいたす。





簡単な仕様



サポヌトされおいるコンパむラ





サポヌトされおいるオペレヌティングシステムずプロセッサアヌキテクチャ



他のオペレヌティングシステムたたはプロセッサアヌキテクチャのサポヌトは可胜ですが、特にタヌゲットコンパむラがC ++ 11 atomic



サポヌトしおいない堎合は簡単ではありたせん。





おわりに



この蚘事を読んだ埌、libcdsラむブラリの䜿甚方法が明確になるこずを願っおいたす。 さらに、デヌタ構造ラむブラリに実装する基本的な原則を明確にするこずを詊みたした。



パフォヌマンスの問題にはたったく觊れたせん。 既に述べたように、パフォヌマンスは特定のタスクず特定のハヌドりェアに関連しおのみ説明できたす。 珟代のハヌドりェアは、ロックフリヌアルゎリズムに察しお非垞に異なる態床を持っおいたす。1぀は圌らを支持し、もう1぀は長い間説埗する必芁があるかもしれたせん。 Lock-free , « »: + , lock-free .



, : (shared) . , .



参照資料
[Des09] M.Desnoyers Low-Impact Operating System Tracing PhD Thesis,Chapter 6 «User-Level Implementations of Read-Copy Update»



[Des11] M.Desnoyers, P.McKenney, A.Stern, M.Dagenias, J.Walpole User-Level Implementations of Read-Copy Update



[Gid05] Anders Gidenstam, Marina Papatriantafilou and Philippas Tsigas Practical and Efficient Lock-Free Garbage Collection Based on Reference Counting



[Gid06] A.Gidenstam Algorithms for synchronization and consistency in concurrent system services , Chapter 5 «Lock-Free Memory Reclamation» Thesis for the degree of Doctor of Philosophy



[Her02] M. Herlihy, V. Luchangco, and M. Moir. The repeat offender problem: A mechanism for supporting dynamic-sized lockfree data structures Technical Report TR-2002-112, Sun Microsystems Laboratories, 2002



[Her05] M. Herlihy, V. Luchangco, P. Martin, and M. Moir. Nonblocking Memory Management Support for Dynamic_Sized Data Structures ACM Transactions on Computer Systems, Vol.23, No.2, May 2005



[Mic02] Maged M.Michael Safe memory reclamation for dynamic lock-free objects using atomic reads and writes



[Mic03] Maged M.Michael Hazard Pointers: Safe memory reclamation for lock-free objects



[Mic04] Andrei Alexandrescy, Maged Michael Lock-free Data Structures with Hazard Pointers





ロックフリヌのデヌタ構造
開始する

基本



䞭



倖から





More articles:


All Articles