タグ付きポインター

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アトミックプリミティブ（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万になります。

タグ付きポインターの例

 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 } 

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

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

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

ハザードポインター

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

• まず、現在のハザードポインターの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 , - .

 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)); 

 template <typename T> class MSQueue { struct node { std::atomic<node *> next ; T data; node(): next(nullptr) {} node( T const& v): next(nullptr), data(v) {} }; std::atomic<node *> m_Head; std::atomic<node *> m_Tail; public: MSQueue() { node * p = new node; m_Head.store( p, std::memory_order_release ); m_Tail.store( p, std::memory_order_release ); } void enqueue( T const& data ) { node * pNew = new node( data ); while (true) { node * t = m_Tail.load(std::memory_order_relaxed); //    hazard. HP – thread-private  HP[0] = t; //  ,  m_Tail  ! if (t != m_Tail.load(std::memory_order_acquire) continue; node * next = t->next.load(std::memory_order_acquire); if (t != m_Tail) continue; if (next != nullptr) { // m_Tail     //  m_Tail m_Tail.compare_exchange_weak( t, next, std::memory_order_release); continue; } node * tmp = nullptr; if ( t->next.compare_exchange_strong( tmp, pNew, std::memory_order_release)) break; } m_Tail.compare_exchange_strong( t, pNew, std::memory_order_acq_rel ); HP[0] = nullptr; //  hazard pointer } bool dequeue(T& dest) { while true { node * h = m_Head.load(std::memory_order_relaxed); //  Hazard Pointer HP[0] = h; // ,  m_Head   if (h != m_Head.load(std::memory_order_acquire)) continue; node * t = m_Tail.load(std::memory_order_relaxed); node * next = h->next.load(std::memory_order_acquire); // head->next    Hazard Pointer HP[1] = next; //  m_Head  –    if (h != m_Head.load(std::memory_order_relaxed)) continue; if (next == nullptr) { //   HP[0] = nullptr; return false; } if (h == t) { //   enqueue –  m_Tail m_Tail.compare_exchange_strong( t, next, std::memory_order_release); continue; } dest = next->data; if ( m_Head.compare_exchange_strong(h, next, std::memory_order_release)) break; } //  Hazard Pointers HP[0] = nullptr; HP[1] = nullptr; //       //    . RetireNode(h); } }; 

Hazard Pointer libcds

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

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

 struct retired_ptr { typedef void (* fnDisposer )( void * ); void * ptr ; //   fnDisposer pDisposer; // - retired_ptr( void * p, fnDisposer d): ptr(p), pDisposer(d) {} }; 

 template <typename T> struct make_disposer { static void dispose( void * p ) { delete reinterpret_cast<T *>(p); } }; template <typename T> void retire_ptr( T * p ) { //  p   arrRetired     // ,  arrRetired –    arrRetired.push( retired_ptr( p, make_disposer<T>::dispose )); //    –  scan if ( arrRetired.full() ) scan(); } 

 template <typename T> T protect(size_t nIndex, CDS_ATOMIC::atomic<T> const& toGuard ); template <typename T, class Func> T protect(size_t nIndex, CDS_ATOMIC::atomic<T> const& toGuard, Func f ) template <typename T> T * assign( size_t nIndex, T * p ); template <typename T, int Bitmask> T * assign( size_t nIndex, cds::details::marked_ptr<T, Bitmask> p ); void copy( size_t nDestIndex, size_t nSrcIndex ); void copy( size_t nIndex, Guard const& src ); template <typename T> T * get( size_t nIndex) const; void clear( size_t nIndex); 

Hazard Pointer with Reference Counter

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

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

Pass the Buck

 PTB( size_t nLiberateThreshold = 1024, size_t nInitialThreadGuardCount = 8 ); 

おわりに