ロックフリーのデータ構造。 反復可能なリスト

ロックフリーリストは、多くの興味深いデータ構造、ロックフリーリストが衝突リストとして使用される最も単純なハッシュマップ 、 分割順序リスト 、すべてがバケットを分割するための元のアルゴリズム、本質的にはマルチレベルスキップリスト 、リストの階層リスト。 前回の記事では、競合のないコンテナにこのような内部構造を与え、ロックフリーコンテナの動的な世界でスレッドセーフなイテレータをサポートできるようにしました。 わかったように、ロックフリーコンテナーが反復可能になるための主な条件は、内部構造の安定性です。ノードを物理的に削除（削除）してはなりません。 この場合、イテレータは、次の（インクリメント演算子）に移動する機能を持つノードへの単なる（おそらく複合）ポインタです。

このアプローチをロックフリーリストに拡張できますか？..見てみましょう...

通常のロックフリーリストの構造は次のとおりです。

template <typename T> struct list_node { std::atomic<list_node*> next_; T data_; }; 

その中で、データはノードに直接組み込まれるため、キー（データ）を削除するとノード全体が削除されます。

ノードとデータを分離します-ノードが運ぶデータへのポインターを含むようにします：

 template <typename T> struct node { std::atomic<node*> next_; std::atomic<T*> data_; }; 

次に、キーを削除するには、ノードのdata_フィールドをリセットするだけで十分です。 その結果、リストは次の内部構造を取得します。



ノードは決して削除されないので、リストは反復可能です：イテレーターは実際にはノードへのポインターです：

 template <typename T> struct iterator { guarded_ptr<T> gp_; node* node_; T* operator ->() { return gp_.ptr; } iterator& operator++() { //    ,   node_, //      } }; 

別のスレッドがイテレーターが配置されているデータを削除しないことを保証できないため、 guarded_ptr （ハザードポインターで保護されたデータへのポインターを含む）の存在が必要です。 イテレータnode_ nodeにnode_するときのみ、データが含まれていることが保証されます。 保護されたポインターは、イテレーターがnode_ node上にあるnode_ 、そのデータが物理的に削除（削除）されないことを保証します。

これがどのように機能するかを写真で見てみましょう。 リストの走査を開始します-イテレーターは、空でないデータを持つ最初のノードに配置されます。



次に、イテレータをインクリメントします-空のデータを持つノードをスキップします：



他のスレッドがイテレーターが配置されているノードのデータを削除しても、イテレーターのguarded_ptrは、イテレーターがノード上にある間、データが物理的に削除されないことを保証します。



データがリストから削除され、他のデータが同じnode_ nodeに割り当てられるnode_ます。 この場合、イテレーターはnode_ノードに配置されます。 この場合operator ->()イテレータのoperator ->() 異なるデータへのポインタを返すとしたら、奇妙です。 guarded_ptrは、イテレータによって返されるデータの不変性を保証しますが、他のストリームによる変更を完全に防止するわけではありません。



ご覧のとおり、構築された反復可能リストはスレッドセーフイテレータをサポートし、非常に単純なキー（データ）削除操作を持ちます。これは、ノードのdata_フィールドをゼロ化（CASプリミティブを使用）するdata_です。 次の2つのケースが考えられるため、新しいデータを追加insert()操作はやや複雑です。

-空でないデータを含むリストの既存のノード間の新しいノードの挿入：



ノードを挿入するためのこのアルゴリズムは、以前の記事のいずれかですでによく知られています。

-空のprevノードでdata_フィールドを設定する：



2番目のケース（空のdata_再利用する）が2、3の驚きを投げかけない場合、これで記事を終了できます。

最初の驚き

反復可能リストの挿入の最初の（単純な）バージョンは次のようになりました。



linear_search関数はリスト内の通常の線形検索です（まあ、あまり一般的ではありません-競合リストがあるため、アトミック操作とハザードポインターを備えたスクワットが提供されます）、キーが見つかった場合はtrue返し、 trueない場合はfalse返しtrue 。 （ insert_pos型の） pos関数のoutパラメーターは常に入力されます。 少なくとも目的のdataキーが見つかるとすぐに検索が停止しdata 。 挿入については、検索の失敗に関心があります。この場合、 posには挿入位置が含まれます。 pos.curノードpos.cur常に空でpos.curません（または、リストの最後（ tailノード）をpos.prevます）が、 pos.prevの前のノード）は空のノードを指している可能性があります。これは特に重要です。 prevData構造体のprevDataおよびcurDataフィールドはcurそれぞれprevおよびcur insert_pos値です。 また、リストからノードが削除されることはないため、 prevのポインターを保護し、ノードでハザードポインターを無効にする必要がないことにも注意してください。 ただし、データは削除できるため、保護します。

そのため、単純な実装では、前のノードが空の場合（ pos.prevData == nullptr ）、挿入されたデータへのリンクを書き込もうとしています。 競争力のあるリストがあるので（さらに、ロックフリーでも、すぐに修正します）、アトミックCASによってprev.data_ポインターを変更します。成功した場合、他のスレッドは私たちをprev.data_ず、挿入しましたリストに新しいデータ。

ここで最初の驚きがあります。 スレッドAが特定のキーをリストに追加するとします： linear_search()実行され、挿入位置によってinsert_pos構造体が初期化され、スレッドはlink()を呼び出す準備ができましたが、時間が経過するとオペレーティングシステムによってカボチャに置き換えられました。 現時点では、ストリームBはリストを操作しています：



スレッドAの再開時に、リストは認識できないほど変更されましたが、ストリームAで見つかった位置pos観点からは何も変わりませんでした。 prevは空だったため、空のままでした。 したがって、ストリームAはキー30でデータを書き込み、挿入を成功させ、正常に挿入を完了します。これにより、リストの順序が崩れます。

prev->data_がNULLであるため、これはハザードポインターを使用しても解決できないABAの問題の一種です。 検索後にリンクprev > curが変更されていない場合にのみ、新しいデータを空のノードにリンクする権利があります。 さらに、これらのノードのデータは変更されていません。 この問題を解決するために、 マークポインター手法を使用します。ノードデータへのポインターの最下位ビットを「新しいノードが挿入されています」という記号として使用します。 さらに、 prevとcur両方のノードをマークする必要があります。そうしないと、他のスレッドがcurからデータを削除し、リストの順序が再び違反されます（ curノードが常に空でないことを忘れないでください）。 その結果、ノードの構造が変更され、データを追加するためのlink()関数は次の形式になります。

 template <typename T> struct node { std::atomic< node * > next_; std::atomic< marked_ptr< T, 1 >> data_; }; bool link( insert_pos& pos, T& data ) { //   prev  cur if ( !pos.cur->data_.CAS( marked_ptr(pos.curData, 0), marked_ptr(pos.curData, 1))) { //   — -     return false; } if ( !pos.prev->data_.CAS( marked_ptr(pos.prevData, 0), marked_ptr(pos.prevData, 1))) { //   —    //     pos.cur->data_.store( marked_ptr(pos.curData, 0)); return false; } // ,   prev -> cur   if ( pos.prev->next_.load() != pos.cur ) { // -   -   prev  cur pos.prev->data_.store( marked_ptr(pos.prevData, 0)); pos.cur->data_.store( marked_ptr( pos.curData, 0)); return false; } //   ,   if ( pos.prevData == nullptr ) { //       //  ,    store bool ok = pos.prev->data_.CAS( marked_ptr( nullptr, 1 ), marked_ptr( &data, 0 )); //    cur pos.cur->data_.store( marked_ptr( pos.curData, 0)); return ok; } else { //    —  Harris/Michael //    //        } } 

マークされたポインターの導入は、データ削除機能にも影響します（思い出すように、これは単純にdata_フィールドの無効化にdata_ます）：タグなしのデータのみをゼロにする必要がありますが、これは削除手順に複雑さを追加しません。 リスト検索では、マーカーは完全に無視されます。

その結果、反復可能リストはロックフリーではなくなりました：スレッドが少なくとも1つのノードをマークしてから削除された（ link()関数に例外の場所がないlink()場合、ノードは永久に、最後にマークされたままになるため、ロックフリー条件に違反しますいつの日か、ラベル付け解除のための無限のアクティブな待機につながります。 一方、仕事中に小川を殺すのは罪です。これは悪い習慣なので、ここでは特にリスクはありません。

第二の驚き

残念ながら、テストではこれが完全なソリューションではないことが示されています。 デバッグビルドであっても、単純な反復可能なリストがデータの並べ替えの違反を頻繁に示した場合、マークポインターの導入後、テストはリリースビルドでのみまれに違反を示し始めました。 これは、非常に不快な問題があることを示す信号であり、実際には妥当な時間内に再現することはできず、分析的にしか解決できません。

分析が示したように、問題は実際には最初の問題と直交しています。



最初の場合と同様に、スレッドAはlink()に入る前に強制的に削除されます。 Aが再び計画されるまで待機する間、他のスレッドは、スレッドAのlink()関数の前提条件に違反しないが、並べ替えられたリストの違反につながるシーケンスを追加/削除するために、リストでトリックを再生することができます。

解決策は、 link()別の条件を追加することです： prevおよびcurノードをマークした後、新しいノードを挿入する（または空のprev ）後、 挿入位置が変更されていないことを確認する必要があります。 これを確認する方法は1つしかありません。新しいデータに続くノードを見つけて、それがcurあることを確認してください。

 bool link( insert_pos& pos, T& data ) { //   prev  cur // ...    // ,   prev -> cur   // ...    // ,      if ( find_next( data ) != pos.cur ) { // oops!   … pos.prev->data_.store( marked_ptr(pos.prevData, 0)); pos.cur->data_.store( marked_ptr( pos.curData, 0)); return false; } //   ,   // ...    } 

ここで、ヘルパー関数find_next()は、上記のdata最も近いノードを探します。

おわりに

したがって、反復可能な競合リストを作成できます。 その中の検索はロックフリーですが、挿入とその結果の削除はまだロックフリーではありません。 なぜ彼はそんなに必要なのですか？..

まず、いくつかのタスクではスレッドセーフなイテレータが重要です。 第二に、このリストは、その中のキーを削除する操作が挿入よりもはるかに簡単であるという点で興味深いです-ノードのデータへのポインタをリセットするだけです。 削除は通常、はるかに困難です。従来のロックフリーリストからの2段階の削除を参照してください。 最後に、このタスクは個人的には特定の課題でした。それ以前は、競合コンテナでは原則としてイテレータの概念を実現できないと考えていたためです。

このアルゴリズムが役に立つことを願っています。libcdsを参照してください。MichaelSet / MapおよびSplitListSet / MapとIterableListに基づいて実装用のスレッドセーフイテレータをサポートしています。