ロックフリーのデータ構造。 外部から：libcdsの紹介

この記事では、libcdsデータ構造のロックフリーライブラリーの使用方法の概要を説明します。 ここでの実装については説明しません。 外側から見ただけで、図書館利用者の側から見たものです。

libcdsライブラリには、多くの有名なデータ構造に関する独自の視点があります。 これは、ターゲット領域によって部分的に説明されます-ロックフリーのデータ構造は、提供されるメソッドのセットの観点からは最小限です-一部は、標準STLライブラリの制限とソリューションを超えたいという欲求によって。 その結果は、libcdsユーザーが決定する必要があります。

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

Libcdsは、ロックフリーのデータ構造と、ロックフリーの構造のための安全なメモリ再生（SMR）メソッドのC ++ライブラリです。 ほとんどヘッダーのみです。すべてのデータ構造はヘッダー.hファイルで定義され、コアSMRアルゴリズムの実装のみが小さな動的ライブラリに移動されます。

SMRの概要

おそらく、ロックフリーデータ構造を開発する際の最も薄いポイントは、コンテナ要素を安全に物理的に削除できる時点を決定することです。 要素の削除は常に2段階の操作です。最初に、コンテナから要素を除外し、次に要素に割り当てられたメモリを削除（割り当て解除）します。 ロックフリーアプローチでは、2番目のフェーズである物理削除では、削除されたアイテムへのリンク（グローバルまたはローカル）が誰もいない（並列スレッドはない）という完全な確実性が必要です。
安全に削除するには、SMRアルゴリズムが責任を負います。これは、特殊なガベージコレクター（GC）と見なすことができます。 この記事では、特定のSMRアルゴリズムの実装の内部詳細については説明しません。libcdsの使用を開始するのに十分な一般的な説明のみを示します。 今後の記事ですべてのアルゴリズムについて詳しく説明したいと思います。

次のSMRアルゴリズムがlibcdsに実装されています。

• ハザードポインターは、おそらく最初で最も有名なSMRアルゴリズムです。 2002年にマイケル（これは姓）によって発明されました[Mic02、Mic03、Mic04]。 比較的単純で速度が速いことで区別され、コンテナ要素へのローカルリンクの「保護」を目的としています。 欠点-同時に実行されるスレッドの最大数を示す必要があります。 ヘッダーファイル<cds/gc/hp.h> 、クラスcds::gc::HP
• Pass-the-Buck-概念的にはハザードポインターに似ていますが、スレッドの数に依存しません。 2002年にHerlihy、V。Luchangco、およびM. Moirによって提案されました[Her02、Her05]。 スレッドの数が独立しているため、ハザードポインターよりも少し重いです。 ヘッダーファイル<cds/gc/ptb.h> 、クラスcds::gc::PTB
• 参照カウント付きハザードポインターは、HåkanSundell-Gidenstam et al。[Gid05、Gid06]が率いるスウェーデンの学校の代表者によって提案されたハザードポインターアルゴリズムのバリエーションです。 ハザードポインターと同様に、スレッドの数に依存します。 特徴的な機能は、コンテナ要素へのグローバル参照を保護できることです。つまり、イテレータを実装できます。 パフォーマンスの低下とまれな不具合のため、使用は推奨されません（最後までデバッグできません）。 ヘッダーファイル<cds/gc/hrc.h> 、クラスcds::gc::HRC
• RCU（Read-Copy Update） -上記とは異なり、このアルゴリズムは同期アルゴリズムを指します。つまり、要素の削除時にスレッドの実行を一時停止しますが、他の操作の並列実行（貼り付け、検索）を許可します。したがって、まれに削除されるデータ構造に適しています。タイプマップ、セット。 Paul McKenneyによって提案され、Linuxカーネルで積極的に使用されています。 オリジナルのRCUはOSのカーネルにのみ実装できますが、2009年にDesnoyersはアプリケーション用のRCUのバージョン（ユーザースペースRCU、URCU）[Des09、Des11]を提案しました。これはlibcdsに実装されています。 このライブラリは、URCUの5つの実装を提供し、最も効果的なのはバッファリングされたURCUです。 ヘッダーファイル<cds/urcu/general_buffered.h> 、クラスcds::urcu::gc< cds::urcu::general_buffered<> > 。 libcdsでは、URCUはマップと設定にのみ適用されます

すべてのSMRアルゴリズムには、GCを表す単一のオブジェクトが必要です。つまり、GCはシングルトンです。 動的ライブラリであるlibcdsコアには、基本的なSMRアルゴリズムの実装のみが含まれています。

原則として、アプリケーションは1つのSMRアルゴリズムのみを使用する必要があります（libcdsでは複数の異なるGCアルゴリズムを使用できますが、これがすべてのテストの構築方法ですが、同じGCの2つのオブジェクトは使用できません）。 したがって、最初に行うことは、SMRアルゴリズムを選択することです。 libcdsのデータ構造のほとんどのクラスには、最初のテンプレート引数であるメモリ管理アルゴリズムとしてGCがあります。 さらに、各GCクラスには独自のコンテナクラスのテンプレートの特殊化があるため、異なるGCの場合、原則として、コンテナクラスの異なるヘッダーファイルを含める（含める）必要があります。

SMRアルゴリズムを使用するために、GCの内部構造を知る必要はありません。GCと対話するすべてのメカニズムは、コンテナクラス内に隠されています。 ただし、プログラムの開始時、およびGC依存コンテナを使用する各スレッドの開始時に、GCシングルトンオブジェクトを初期化する必要があります。

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関数を呼び出します。これにより、内部構造が解放されます。

スレッドの初期化

多くの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では、コンテナは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 ; 

データ構造クラスのテンプレート引数は次のとおりです。

• GC -SMRアルゴリズムを使用
• Tコンテナに保存されているデータのタイプ
• Options…またはTraits -コンテナーのオプション（ポリシー、戦略）

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

オプション

各コンテナクラスは、データタイプと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種類のオプションがあります。

• 一般オプション-多くのコンテナに適用可能。 そのようなオプションの宣言はcds::opt名前空間にあり、有効なオプション値は名前空間cds::opt::v
• 特別なオプション-特定のコンテナクラスにのみ適用されます。 それらの宣言は、特定のコンテナの名前空間にあります。たとえば、 cds::container::skip_list

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

比較述語

マップのセットタイプの多くのコンテナでは、要素を比較するための述語を指定する必要があります。 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 > ）を比較述部として使用できます。 比較は整数値を返します。

• cmp(a, b) < 0 a < b場合a < b cmp(a, b) < 0
• cmp(a, b) == 0 a == b場合
• cmp(a, b) > 0 a > b場合

メソッド関数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つのプロパティに大きく依存しています。

• 各アロケーターには、メタ関数template <typename Other> struct rebindがあります。これにより、異なるタイプのOtherアロケーターを再構築できます。 すでに述べたように、デフォルトのstd::allocator<int>はstd::allocator<int>です-コンテナーは、 rebind関数を使用してint型を必要な型に変更します
• アロケーターはグローバルオブジェクトです。 この要件は、ロックフリーコンテナ要素の物理的な取り外しが遅延し、コンテナオブジェクト自体の破壊後に発生する可能性があるという事実から生じています。 したがって、STLとは異なり、libcdsコンテナーはアロケーターオブジェクトへの参照を格納することはなく、アロケーターオブジェクトを指定するメソッドもありません。 コンテナメソッド内でメモリを割り当てる必要がある場合、アロケータは一時オブジェクトallocator_type().allocate( 1 )介して呼び出されます。 同様に、 allocator_type().deallocate( p )呼び出すことでメモリが解放されallocator_type().deallocate( p ) 。 リリースが遅延し、コンテナオブジェクト自体がもう存在せず、SMRアルゴリズムから呼び出されたときにすでに発生している可能性があることを再度注目する価値があります。

簡単な仕様

サポートされているコンパイラ：

• GCC 4.3以降
• MS Visual C ++ 2008以降
• Clang 3.0以降（GCC標準ライブラリlibstdc ++を使用）

サポートされているオペレーティングシステムとプロセッサアーキテクチャ：

• Windows x86、amd64
• Linux x86、amd64、Intel Itanium、Sparc
• Solaris Sparc
• HP-UX Intel Itanium

他のオペレーティングシステムまたはプロセッサアーキテクチャのサポートは可能ですが、特にターゲットコンパイラがC ++ 11 atomicサポートしていない場合は簡単ではありません。

おわりに

この記事を読んだ後、libcdsライブラリの使用方法が明確になることを願っています。 さらに、データ構造ライブラリに実装する基本的な原則を明確にすることを試みました。

パフォーマンスの問題にはまったく触れません。 既に述べたように、パフォーマンスは特定のタスクと特定のハードウェアに関連してのみ説明できます。 現代のハードウェアは、ロックフリーアルゴリズムに対して非常に異なる態度を持っています。1つは彼らを支持し、もう1つは長い間説得する必要があるかもしれません。 Lock-free , « »: + , lock-free .

, : (shared) . , .