以前のメモで述べたように、ロックフリーデータ構造を実装する際の主な問題は、ABAの問題とメモリの削除です。 これら2つの問題は関連していますが、私は共有しています。事実は、そのうちの1つだけを解決するアルゴリズムがあるということです。

この記事では、ロックフリーコンテナの安全なメモリ再生として知られている方法の概要を説明します。 Michael-Scottの古典的なロックフリーキュー[MS98]で、このメソッドまたはそのメソッドの使用方法を示します。

タグ付きポインター

タグ付きポインタースキームは、ABAの問題を解決するためにIBMによって提案されました。 おそらくこれは、この問題を解決するための最初の既知のアルゴリズムです。

このスキームによれば、各ポインターは、メモリセルの実際のアドレスとそのタグ（32ビット整数）の分割不可能なペアです。

template <typename T> struct tagged_ptr { T * ptr ; unsigned int tag ; tagged_ptr(): ptr(nullptr), tag(0) {} tagged_ptr( T * p ): ptr(p), tag(0) {} tagged_ptr( T * p, unsigned int n ): ptr(p), tag(n) {} T * operator->() const { return ptr; } };
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

タグはバージョン番号として機能し、ラベル付きポインターでの各CAS操作中に増分され 、 リセットされることはありません 。つまり、厳密に増加します。 アイテムを物理的に削除するのではなく、コンテナからアイテムを削除するときは、アイテムを空きアイテムの空きリストリストに配置する必要があります。 同時に、free-listにあるリモート要素にアクセスする場合は非常に受け入れられます。ロックフリー構造があるため、一方のスレッドがX要素を削除している間、もう一方のスレッドはXへのラベル付きポインターのローカルコピーを持ち、要素のフィールドを参照できます。 したがって、フリーリストは各タイプTごとに分離する必要があり、さらに、フリーリストに要素を配置するときにデータタイプTデストラクタを呼び出すことは多くの場合許可されません（同時アクセスのため、デストラクタ操作中に別のスレッドがこの要素からデータを読み取ることができます）。

タグ付きポインタースキームには、次の欠点があります。

• このスキームは、ダブルワード上のCASアトミックプリミティブ（dwCAS）があるプラットフォームに実装されます。 32ビットの最新プラットフォームでは、dwCASが64ビットワードで動作し、すべての最新のアーキテクチャに64ビット命令の完全なセットがあるため、この要件は満たされます。 ただし、64ビット動作モードの場合、128ビット（または少なくとも96ビット）のdwCASが必要です。これは、すべてのアーキテクチャに実装されているわけではありません。
  
  
  はい、あなたはナンセンスを書いた、私の友人！

  ロックフリーで特に洗練されているのは、タグ付きポインターを実装するために、128ビット（または96ビット）の広いCASを持つ必要がないということに反対するかもしれません。 最新のプロセッサはアドレス指定に48ビットのみを使用しているため、64ビットで対応できます。アドレスの最上位16ビットは無料で、タグカウンターの格納に使用できます。 まあ、確かに、彼らはできます。 これはboost.lockfree
  
  
  
  で行われboost.lockfree
  
  
  
  。
  
  このアプローチには2つの「しかし」があります。
  
  

  • 将来、これらの古い16ビットのアドレスが関係しないことを誰が保証しますか？ メモリチップの分野で次のブレークスルーが到来し、その量が一桁増えるとすぐに、ベンダーはすぐに完全な64ビットアドレス指定の新しいプロセッサをリリースします
  • タグを保持するには16ビットで十分ですか？ このテーマに関する調査が行われ、これらの調査の結果は次のとおりです。16ビットでは不十分であり、オーバーフローが発生する可能性があり、ABAの問題につながる可能性があります。 ただし、32ビットで十分です。
    
    実際、16ビットは0-65535タグの値です。現代のオペレーティングシステムでは、ストリームに割り当てられるタイムスロットは300〜50万のアセンブラー命令（Linux開発者の内部通信から取得）であり、このクォンタムはプロセッサーパフォーマンスの向上によってのみ成長します。 1つのクォンタムでは、CASのような重い操作でも65,000を実行することが可能です（まあ、今日不可能なら、明日も可能です）。 したがって、16ビットのタグを使用すると、ABAの問題が発生する可能性が非常に高くなります。

  
  
  
  
  
  
• 空きリストの実装は、ロックフリースタックまたはロックフリーキューであり、パフォーマンスにマイナスの影響を与えます。つまり、アイテムが空きリストから削除されて追加されたときに、少なくとももう1回CAS呼び出しが行われます。 一方、空きリストが空でない場合は、システムを使用する必要がないため、通常は低速で同期化されたメモリ割り当て機能のため、空きリストが存在すると生産性が向上します。
• 各データ型に個別の空きリストを設定すると、一部のアプリケーションではメモリの使用効率が低下する可能性があるため、贅沢になります。 たとえば、ロックフリーキューに平均で10個の要素が含まれているが、ピーク時にそのサイズが100万に達する可能性がある場合、ピークに達した後のフリーリストのサイズは約100万になります。

したがって、タグ付きポインタースキームは、ABAの問題のみを解決し、メモリを解放する問題を解決しないアルゴリズムの例です。



libcdsライブラリは、現在ロックフリーコンテナを実装するためにタグ付きポインタを使用していません。 比較的単純であるにもかかわらず、このスキームは、各コンテナオブジェクトの空きリストの存在により、メモリ消費の制御されない成長につながる可能性があります。 libcdsでは、dwCASを使用せずに、予測可能なメモリ消費を伴うロックフリーアルゴリズムに焦点を当てました。

タグ付きポインターを使用する良い例は、 boost.lockfree



ライブラリーです。

タグ付きポインターの例

シートのファン（存在する場合）-タグ付きポインターを使用した擬似コードMSQueue



[MS98]。 はい、ロックフリーアルゴリズムは非常に冗長です。

簡単にするために、 std:atomic



使用を省略しました。

 template <typename T> struct node { tagged_ptr next; T data; } ; template <typename T> class MSQueue { tagged_ptr<T> volatile m_Head; tagged_ptr<T> volatile m_Tail; FreeList m_FreeList; public: MSQueue() { //  dummy node // Head & Tail   dummy node m_Head.ptr = m_Tail.ptr = new node(); } }; void enqueue( T const& value ) { E1: node * pNode = m_FreeList.newNode(); E2: pNode–>data = value; E3: pNode–>next.ptr = nullptr; E4: for (;;) { E5: tagged_ptr<T> tail = m_Tail; E6: tagged_ptr<T> next = tail.ptr–>next; E7: if tail == m_Tail { // Tail    ? E8: if next.ptr == nullptr { //       E9: if CAS(&tail.ptr–>next, next, tagged_ptr<T>(node, next.tag+1)) { // ,    E10: break; } E11: } else { // Tail      //   tail    E12: CAS(&m_Tail, tail, tagged_ptr<T>(next.ptr, tail.tag+1)); } } } // end loop //   tail    E13: CAS(&m_Tail, tail, tagged_ptr<T>(pNode, tail.tag+1)); } bool dequeue( T& dest ) { D1: for (;;) { D2: tagged_ptr<T> head = m_Head; D3: tagged_ptr<T> tail = m_Tail; D4: tagged_ptr<T> next = head–>next; // Head, tail  next ? D5: if ( head == m_Head ) { // Queue   tail  ? D6: if ( head.ptr == tail.ptr ) { //  ? D7: if (next.ptr == nullptr ) { //   D8: return false; } // Tail     //   tail D9: CAS(&m_Tail, tail, tagged_ptr<T>(next.ptr, tail.tag+1>)); D10: } else { // Tail  //    CAS,    //  dequeue   next D11: dest = next.ptr–>data; //   head D12: if (CAS(&m_Head, head, tagged_ptr<T>(next.ptr, head.tag+1)) D13: break // ,    } } } // end of loop //   dummy node D14: m_FreeList.add(head.ptr); D15: return true; //  –  dest }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

エンキューおよびデキュー操作のアルゴリズムを詳しく見てみましょう。 それらの例を使用すると、ロックフリー構造を構築するときにいくつかの標準的なトリックを見ることができます。



両方のメソッドにループが含まれていることは注目に値します-操作の実質的な部分全体が成功するまで繰り返されます（または、空のキューからdequeue



するなど、正常に実行できません）。 ループの助けを借りたこのような「スイッティング」は、典型的なロックフリーのプログラミング手法です。



キューの最初の要素（ m_Head



）はダミー要素（ダミーノード）です。 ダミー要素を使用すると、キューの先頭と末尾へのポインタがNULL



ならないことが保証されNULL



。 空のキューの兆候は、 m_Head == m_Tail && m_Tail->next == NULL



という条件m_Head == m_Tail && m_Tail->next == NULL



（行D6-D8）。 最後の条件（ m_Tail->next == NULL



）は必須です。キューに追加するプロセス中にm_Tail



変更しないため 、行E9はm_Tail->next



のみを変更するm_Tail->next



です。 したがって、一見、 enqueue



メソッドはキューの構造に違反しています。 実際、 m_Tail



テールは別のメソッドや別のスレッドでm_Tail



れます。エレメントを追加する前のenqueue



操作は、 m_Tail



が最後のエレメント（つまりm_Tail->next == NULL



）を指すことをチェックします（E8行）そのため、ポインターを最後に移動しようとしています（E12行）。 同様に、「即時の義務」を実行する前のdequeue



操作は、キューの最後を指していない場合、 m_Tail



変更します（行D9）。 これは、ロックフリープログラミングの一般的なアプローチを示しています-スレッド間の相互支援（ 支援 ）：1つの操作のアルゴリズムは、コンテナーのすべての操作に対して「スミア」され、1つの操作は、その操作が（おそらく別の）操作への次の呼び出しを完了するという事実に大きく依存しています多分）別のスレッド。



別の基本的な観察：操作は、操作する必要があるポインターの値をローカル変数に格納します（行E5-E6、D2-D4）。 次に（行E7、D5）、読み取られた値が元の値と比較されます-典型的なロックフリーのトリック、非競合プログラミングには不要です：読み取りから経過した時間の間に、元の値が変更される可能性があります。 コンパイラーがキューの共有データへのアクセスを最適化しないようにするには（そして「スマート」すぎるコンパイラーはE7またはD5の比較行を完全に削除できます）、 m_Head



++ m_Head



とm_Tail



はC ++ 11でatomic



に宣言する必要があります（擬似コードm_Tail



さらに、CASプリミティブはターゲットアドレスの値を指定されたものと検証し、それらが等しい場合、ターゲットアドレスのデータを新しい値に変更することを思い出してください。 したがって、CASプリミティブの場合、常に現在の値のローカルコピーを指定する必要があります。 CAS(&val, val, newVal)



呼び出しはほとんど常に成功しますが、これは私たちにとって間違いです。



次に、 dequeue



メソッドでdequeue



がコピーされたときを見てみましょう（行D11）：アイテムがキューから除外される前 （行D12）。 要素の例外（行D12のm_Head



前進）が失敗する可能性がある場合、データのコピー（D11）を繰り返すことができます。 C ++の観点から見ると、これは、キューに格納されているデータが複雑すぎないことを意味します。さもないと、D11行の代入演算子のオーバーヘッドが大きくなりすぎます。 したがって、高負荷条件下では、CASプリミティブの故障の可能性が高くなります。 D11行をループ外に移動してアルゴリズムを「最適化」しようとすると、エラーが発生します。 next



要素は別のスレッドによって削除される可能性があります。 問題のキューの実装は、要素が削除されることのないタグ付きポインタースキームに基づいているため、この「最適化」により、（D12行の正常な実行時にキューにあったデータではなく） 不正なデータを返すことができます。

エポックベースのレクラメーション

Fraser [Fra03]は、エポックベースのスキームを提案しました。 遅延削除は、削除された要素へのリンクがスレッドに存在しないという完全な確信が得られる安全な瞬間に適用されます。 この保証はエポックによって提供されますnGlobalEpoch



グローバル時代がnGlobalEpoch



、各スレッドはnThreadEpoch



独自のローカル時代でnThreadEpoch



ます。 エポックベースのスキームで保護されたコードを入力すると、フローのローカルエポックは、グローバルエポックを超えない場合に増分されます。 すべてのスレッドがグローバル時代にnGlobalEpoch



、 nGlobalEpoch



増分されます。



スキーマの擬似コード：

 //   static atomic<unsigned int> m_nGlobalEpoch := 1 ; const EPOCH_COUNT = 3 ; // TLS data struct ThreadEpoch { //    unsigned int m_nThreadEpoch ; //      List<void *> m_arrRetired[ EPOCH_COUNT ] ; ThreadEpoch(): m_nThreadEpoch(1) {} void enter() { if ( m_nThreadEpoch <= m_nGlobalEpoch ) m_nThreadEpoch = m_nGlobalEpoch + 1 ; } void exit() { if (     ,   m_nGlobalEpoch ) { ++m_nGlobalEpoch ;  (delete)  m_arrRetired[ (m_nGlobalEpoch – 1) % EPOCH_COUNT ]   ; } } } ;
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

リリースされたロックフリーコンテナ要素は、削除を待機しているアイテムのスレッドローカルリストに配置されますm_arrRetired[m_nThreadEpoch % EPOCH_COUNT]



。 すべてのフローがm_nGlobalEpoch



グローバルエポックを通過するとすぐに、すべてのm_nGlobalEpoch – 1



エポックフローのすべてのリストが解放され、グローバルエポック自体が増分されます。





各ロックフリーコンテナー操作は、クリティカルセクションに非常に似ているThreadEpoch::enter()



およびThreadEpoch::exit()



呼び出しに囲まれています。

 lock_free_op( … ) { get_current_thread()->ThreadEpoch.enter() ; . . . // lock-free  . //    “ ” epoch-based , //     ,     ,   //  . . . . get_current_thread()->ThreadEpoch.exit() ; }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

このスキームは非常に単純で、ローカルリンク（つまり、コンテナー操作内のリンク）を保護して、コンテナー要素をロックフリーにします。 スキームは（コンテナーの操作の外部から）グローバルリンク保護を提供できません。つまり、ロックフリーコンテナーの要素に対するイテレーターの概念は、エポックベースのスキームを使用して実装できません。 このスキームの欠点は、 すべてのプログラムフローが次の時代に移行する必要があることです。つまり、何らかのロックフリーコンテナーに移行する必要があります。 少なくとも1つのスレッドが次の時代に移行しない場合、保留中のポインターの削除は発生しません。 ストリームの優先度が同じでない場合、優先度の低いストリームは、優先度の高いストリームの要素を削除するために、遅延されたストリームのリストを無制限に増大させる可能性があります。 したがって、エポックベースのスキームは、無制限のメモリ消費につながる可能性があります（スレッドの1つがクラッシュした場合、確実につながる）。



libcdsライブラリには、エポックベースのスキームの実装がありません。 理由：すべてのフローがグローバル時代に到達したかどうかを判断するための十分に効果的なアルゴリズムを構築できませんでした。 おそらく読者の一人が解決策をお勧めしますか？..

ハザードポインター

このスキームはMichael [Mic02a、Mic03]によって提案され、ロックフリーデータ構造要素へのローカルリンクを保護することを目的としています。 おそらく、これは最も有名で精巧な遅延削除のスキームです。 アトミックな読み取りと書き込みのみに基づいており、CASのような「重い」同期プリミティブはまったく使用しません。

スキームの基礎は、コンテナのロックフリー要素へのポインタを、データ構造のロックフリー操作内でハザード （危険）として宣言する義務です。つまり、要素へのポインタを操作する前に、現在のストリームのハザードポインタのHP



配列に入れる必要があります。 HP



アレイは、ストリームに対してプライベートです。所有者ストリームのみがストリームに書き込み、すべてのストリームは（ Scan



手順で）読み取ることができます。 さまざまなロックフリーコンテナの動作を注意深く分析すると、 HP



アレイのサイズ（スレッドごとのハザードポインターの数）が3-4を超えないため、回路を維持するためのオーバーヘッドが小さいことに気付くでしょう。





ハザードポインター擬似コード[Mic02]：

 //  // P :   // K :  hazard pointer    // N :   hazard pointers = K*P // R : batch size, RN=Ω(N), , R=2*N // Per-thread : //  Hazard Pouinter  //     - //    void * HP[K] //   dlist ( 0..R) unsigned dcount = 0; //      void* dlist[R]; //   //     dlist void RetireNode( void * node ) { dlist[dcount++] = node; //    –    Scan if (dcount == R) Scan(); } //   //     dlist,    //  Hazard Pointer void Scan() { unsigned i; unsigned p=0; unsigned new_dcount = 0; // 0 .. N void * hptr, plist[N], new_dlist[N]; // Stage 1 –    HP   //    plist   for (unsigned t=0; t < P; ++t) { void ** pHPThread = get_thread_data(t)->HP ; for (i = 0; i < K; ++i) { hptr = pHPThread[i]; if ( hptr != nullptr ) plist[p++] = hptr; } } // Stage 2 –  hazard pointer' //       sort(plist); // Stage 3 –  ,    hazard for ( i = 0; i < R; ++i ) { //  dlist[i]    plist  Hazard Pointer' //  dlist[i]    if ( binary_search(dlist[i], plist)) new_dlist[new_dcount++] = dlist[i]; else free(dlist[i]); } // Stage 4 –     . for (i = 0; i < new_dcount; ++i ) dlist[i] = new_dlist[i]; dcount = new_dcount; }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

ロックなしのpNode



コンテナ要素のRetireNode(pNode)



を削除すると、ストリームj



はdlist



保留（削除が必要）要素のdlist



ローカル（ストリームj



）リストにdlist



ます。 dlist



のサイズがRに達すると（ Rは N = P*K



に匹敵しますが、 Nを超えます。たとえばR = 2N



）、 Scan()



プロシージャが呼び出され、保留中のアイテムの削除が行われます。 条件R > P*K



は必須です。この条件が満たされた場合にのみ、 Scan()



が保留中のデータ配列からすべてを削除できることが保証されます。 この条件に違反すると、 Scan()



は配列から何も削除しない可能性があり、アルゴリズムエラーが発生します。配列は完全にいっぱいですが、サイズを小さくすることはできません。



Scan()



は4つのステージで構成されます。

• まず、現在のハザードポインターのplist
  
  
  
  配列が準備されます。これには、すべてのフローのすべての非null
  
  
  
  ハザードポインターが含まれnull
  
  
  
  。 共有データ（ HP
  
  
  
  ストリームの配列）を読み取るのは最初のステージのみで、残りのステージはローカルデータでのみ機能します。
• ステージ2は、 plist
  
  
  
  配列をソートして、後続の検索を最適化します。 ここで、 plist
  
  
  
  からplist
  
  
  
  要素を削除plist
  
  
  
  こともできplist
  
  
  
  。
• ステージ3-自身の削除：現在のストリームのdlist
  
  
  
  配列のすべての要素が表示されます。 dlist[i]
  
  
  
  要素がplist
  
  
  
  （つまり、一部のスレッドがこのポインターをハザードポインターとして宣言することで機能する場合）、それを削除することはできず、 dlist
  
  
  
  （ new_dlist
  
  
  
  転送されnew_dlist
  
  
  
  ）。 そうしないと、 dlist[i]
  
  
  
  要素が削除される可能性があります-単一のスレッドでは機能しません。
• ステージ4は、削除されていないアイテムをnew_dlist
  
  
  
  からnew_dlist
  
  
  
  にdlist
  
  
  
  ます。 R > N
  
  
  
  , Scan()



dlist
  
  
  
  , - .

Hazard Pointer, , :

 std::atomic<T *> atomicPtr ; … T * localPtr ; do { localPtr = atomicPtr.load(std::memory_order_relaxed); HP[i] = localPtr ; } while ( localPtr != atomicPtr.load(std::memory_order_acquire));
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

atomicPtr



localPtr



( ) HP[i]



HP



hazard- . , , atomicPtr



, , atomicPtr



localPtr



. , HP



( hazard) atomicPtr



. Hazard Pointer' ( hazard), , .



Hazard Pointer (HP-) C++11 memory ordering [Tor08].





Hazard Pointer ? ? , , — . : hazard pointer' K . – hazard pointer – , , , hazard- . , hazard-. – [Har01]. , HP- .

, HP- hazard-. , . libcds , , , HP-. , — Pass the Buck , — Hazard Pointer, hazard-. .

Hazard Pointer libcds

hazard pointer libcds. – Hazard Pointer Manager — , libcds.dll/.so. — Thread HP Manager , — HP hazard pointer' K () Retired R . Thread HP Manager . P . libcds:

• hazard- K = 8
  
  
  
  
• P = 100
  
  
  
  
• ( ) R = 2 * K * P = 1600
  
  
  
  .

libcds HP- :

• – ( cds::gc::hzp
  
  
  
  ). ( T
  
  
  
  ), . , ( , «» – . , – -, – « ». , , – ).
• – , cds::gc::hzp
  
  
  
  . (template) - , (- type erasure).
• (API) – cds::gc::HP
  
  
  
  . , ( ) lock-free libcds, , ( , ) GC
  
  
  
  . cds::gc::HP
  
  
  
  – .

HP- libcds, main()



cds::gc::HP



, , HP-, . , , cds::gc::HP



. API HP-.

Hazard Pointer with Reference Counter

Hazard Pointer , lock-free . , , , , : hazard-.



, , (reference counting, RefCount). Valois – lock-free — . RefCount- , – , . , RefCount-, lock-free fetch-and-add (, , – ).

2005 [GPST05], Hazard Pointer RefCount : Hazard Pointers lock-free , RefCount – . HRC (Hazard pointer RefCounting).

Hazard Pointers / , RefCounting- . , (- , . [GPST05]). Hazard Pointers lock-free , HRC :

 void CleanUpNode( Node * pNode); void TerminateNode( Node * pNode);
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

TerminateNode



pNode



. CleanUpNode



, , pNode



«» ( ) , () ; RefCount- , , CleanUpNode



:

 void CleanUpNode(Node * pNode) { for (all x where pNode->link[x] of node is reference-counted) { retry: node1 = DeRefLink(&pNode->link[x]); //  HP if (node1 != NULL and !is_deleted( node1 )) { node2 = DeRefLink(node1->link[x]); //  HP //  ,       //    node1 CompareAndSwapRef(&pNode->link[x],node1,node2); ReleaseRef(node2); //  HP ReleaseRef(node1); //  HP goto retry; //       ,   } ReleaseRef(node1); //  HP } }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

lock-free ( C++) HRC lock-free . , , CleanUpNode



, , . lock-free , , MultiCAS .

, Hazard Pointers , . Scan



Hazar Pointers ( , CleanUpNode



). : Hazard Pointers ( R > N = P * K



), Scan



- ( , hazard-), HRC Scan



- ( – ). , Scan



, CleanUpAll



: CleanUpNode



, Scan



.

Pass the Buck

lock-free , Herlihy & al Pass-the-Buck (PTB, “ ”) [HLM02, HLM05], HP- ., .

, HP-, PTB- (guarded, hazard pointer HP-). PTB- ( hazard pointer'). (retired) Liberate



— Scan



HP-. Liberate



, . HP-, retired- , PTB- .

guard' (hazard pointer'): , retired-, hand-off (“ ”). Liberate



, retired- guard', retired- hand-off guard'. Liberate



hand-off , guard, , , .



[HLM05] Liberate



: wait-free lock-free. Wait-free dwCAS (CAS ), dwCAS . Lock-free , . (guard' retired-) lock-free Liberate



, (, retired-, ). , PTB- , Liberate



.



, Liberate



PTB-, HP-. PTB libcds HP- hazard- retired-. : «» HP- , PTB, PTB guard'.

おわりに

safe memory reclamation, Hazard Pointer. HP- lock-free .



lock-free . libcds, , (attach) GC



libcds. , Scan()



/ Liberate()



. — .



— RCU, HP-like , — .



UPD 2016: Errandir , Hazard Pointer ( HP).