Geekly Articles each Day

オブジェクトをスレッドセーフにする

画像

これらの3つの記事では、アトミック操作、メモリバリア、スレッド間の高速データ交換、および「execute-around-idiom」の例を使用して「シーケンスポイント」について詳しく説明し、同時に何かをしようとします。便利-変数または関数を持つメンバーを持つ任意の操作に対して、オブジェクトをスレッドセーフにするスマートポインター。 次に、8〜64コアで高度に最適化されたロックフリーアルゴリズムのパフォーマンスを実現するためにそれを使用する方法を示します。

関連する3つの記事：

  1. オブジェクトをスレッドセーフにする
  2. stdの高速化:: shared_mutexを10倍
  3. スレッドセーフstd ::ロックのないマップパフォーマンスを備えたマップ

→ 私の英語の記事
→ 3つの記事すべての例とテスト

標準C ++ライブラリには、追加のロックなしで複数のスレッドで使用できるスレッドセーフコンテナ（配列、リスト、マップなど）はありません。 マルチスレッド交換の標準コンテナを使用すると、コードセクションの1つをミューテックスで保護するのを忘れたり、誤って別のミューテックスで保護するのを忘れたりする危険があります。

明らかに、開発者は標準的なソリューションの代わりに独自のソリューションを使用すると、より多くの間違いを犯します。 タスクが非常に複雑で、標準に解決策がない場合、それを解決する開発者はエラーにerrorsれます。

「実用性は非の打ちどころのないことよりも重要」（「実用性は純度よりも優れている」）の原則に基づいて、この問題に対する理想的ではなく実用的な解決策を作成しようとします。

この記事では、オブジェクトをスレッドセーフにするスマートポインターを実装します。パフォーマンスは、最適化されたロックフリーコンテナーに劣りません。

そのようなポインターを使用する単純化された最適化されていない例：

int main() { contfree_safe_ptr< std::map<std::string, int> > safe_map_string_int; std::thread t1([&]() { safe_map_string_int->emplace("apple", 1); }); std::thread t2([&]() { safe_map_string_int->emplace("potato", 2); }); t1.join(); t2.join(); std::cout << "apple = " << (*safe_map_string_int)["apple"] << ", potato = " << (*safe_map_string_int)["potato"] << std::endl; return 0; }

アルゴリズムの各ステップで、必要な動作を保証する標準から引用符を付けます。

C ++メモリモデル、スレッド間でデータを同期および交換するためのさまざまな可能なオプションについて詳しく調べます。

2番目の記事では、最適化された「競合のない共有ミューテックス」とそれに基づいた最適化されたポインターcontfree_safe_ptr <>を実装します。 3番目の記事では、contfree_safe_ptr <>の最適な使用例を示し、パフォーマンステストを行います。

開始する


まず、safe_ptr <T>スマートポインターテンプレートの開発から始めましょう。これは、あらゆるタイプTに対してスレッドセーフであり、最適化されたロックフリーアルゴリズムのレベルでマルチスレッドパフォーマンスを示します。

さらに、ロックフリーのデータ構造でもロックを使用する必要があり、永遠のデッドロックが発生する可能性のある複数の異なるオブジェクトを一度にアトミックかつ一貫して処理する機能を備えています。 ただし、デッドロックを処理するための特別な相互排他ロッククラスを開発します。 次に、独自の高性能な競合のないshared-mutexを実装します。これは、標準のstd :: shared_mutexよりもはるかに高速です。 そして、それに基づいて、contfree_safe_ptr <>と呼ばれるセーフポインターsafe_ptr <T>の最適化バージョンを作成します。 最後に、ロックフリーライブラリCDSlibと比較したパフォーマンステストを実施します。 例としてcontfree_safe_ptr <std :: map <>>を使用して、CDSlib（SkipListMapおよびBronsonAVLTreeMap）と同様のパフォーマンスを確認します。

その結果、クラスTをスレッドセーフにするために、時間は必要ありません。次のように書くだけです：contfree_safe_ptr <T> ptr_thread_safe;

また、パフォーマンスは、クラスのメソッドで1か月間ロックフリーアルゴリズムを開発していた場合とほぼ同じです。 さらに、複数のcontfree_safe_ptr <>を一度にアトミックに変更することもできます。 std :: shared_ptr <>と同様に、スマートポインターには参照カウントが含まれます。 コピーできます。最後のコピーを削除すると、動的に割り当てられたメモリは自動的に解放されます。

最後に、safe_ptr.hファイルが1つ提供されます。これは#include“ safe_ptr.h”を介して接続するのに十分なので、このクラスを使用できます。

マルチスレッドデータ交換の基本原則


ご存じのとおり、次の4つの場合にのみ、異なるストリームから同じオブジェクトを読み取って変更できます。

1.ロックベース。 オブジェクトはロックによって保護されています：spin-lock、std（mutex、recursive_mutex、timed_mutex、shared_timed_mutex、shared_mutex ...）： en.cppreference.com/mwiki/index.php?title=Special%3ASearch&search=mutex
2.アトミック。 オブジェクトのタイプはstd :: atomic <T>です。ここで、Tはポインター、ブール、または整数型（std :: is_integral <T> :: value == true）であり、タイプTに対してCPUレベルでアトミック操作が存在する場合のみ： en .cppreference.com / w / cpp / atomic / atomic
2 + 1（ロックベースのアトミック）それ以外の場合、タイプTが簡単にコピー可能なタイプ、つまり 条件を満たすstd :: is_trivially_copyable <T> :: value == true、その後std :: atomic <T>はロックベースとして動作します-ロックは内部で自動的に使用されます
3.トランザクションセーフ。 オブジェクトで動作するように実装された関数は、スレッドセーフなtransaction_safe保証を提供します（トランザクションメモリTS（ ISO / IEC TS 19841：2015 ）-実験的C ++）： en.cppreference.com/w/cpp/language/transactional_memory
4.ロックフリー。 オブジェクトを操作するための関数は、ロックフリーアルゴリズムに基づいて実装されます。 スレッドセーフなロックフリー保証を提供する

スレッドセーフを確保する4つの方法をすべて知っている場合は、この章をスキップできます。

逆順で検討してください：

（4）ロックフリーアルゴリズムは非常に複雑で、多くの場合、各複雑なアルゴリズムを作成するにはいくつかの科学論文が必要です。 コンテナを操作するためのロックフリーアルゴリズムの例：unordered_map、ordered_map、queue ...、および科学作品へのリンクは、ライブラリにあります-Concurrent Data Structures（CDS）ライブラリ： github.com/khizmax/libcds
これらは非常に高速で信頼性の高いマルチスレッドデータ構造ですが、これまではC ++ 17またはC ++ 20標準ライブラリに含める計画はなく、ドラフト標準には含まれていません： www.open-std.org/JTC1/SC22/WG21

（3） C ++標準の実験部分にトランザクションセーフが含まれることが計画されており、すでにISO / IEC TS 19841：2015標準のドラフトがあります： www.open-std.org/jtc1/sc22/wg21/docs/papers/2015/n4514.pdf
ただし、すべてのSTLコンテナでさえ、トランザクションセーフになる予定はありません。 たとえば、コンテナstd ::マップはトランザクション的に安全であるように計画されていません。 トランザクションセーフとして定義されている関数は、begin、end、size、max_size、emptyのみです。 ただし、スレッドセーフ関数として定義されていません：検索、変更、挿入。 また、トランザクションセーフなメンバー関数を使用して独自のオブジェクトを実装することは、決して簡単ではありません。そうでなければ、std :: mapに対して行われます。

（2）アトミック。 このアプローチはすでにC ++ 11で標準化されており、簡単に使用できます。 たとえば、変数std :: atomic shared_val;を宣言するだけです。 次に、リンクまたはそのポインターをいくつかのスレッドに渡し、メンバー関数とstdを介したすべての呼び出し::アトミック演算子はスレッドセーフになります：[3] coliru.stacked-crooked.com/a/9d0219a5cfaa3cd5
メンバー関数、専用メンバー関数： en.cppreference.com/w/cpp/atomic/atomic
アトミック変数で複数の操作を実行する場合、1つの式または複数の式で重要ではなく、別のスレッドがこの変数の値を変更できることを理解することが重要です。 したがって、いくつかの操作のアトミック実行には、CAS関数（Compare-And-Swap）compare_exchange_weak（）に基づくロックフリーアプローチが使用されます-すなわち：アトミック変数からローカル変数（old_local_val）に値を読み取り、必要な操作のセットを実行し、結果を書き込みますローカル変数（new_local_val）に追加し、CAS関数で最後にアトミック変数の現在の値を初期（old_local_val）と比較し、それらが等しくない場合、サイクルを再度実行し、それらが等しい場合、この間に他のスレッドが変更を行わず、次に変更することを意味します原子価 変数を新しい値（new_local_val）に変更します。 さらに、1つの操作compare_exchange_weak（）で比較と割り当てを行います。これはアトミック関数であり、完全に実行されるまで、誰も変数の値を変更できません：[4] coliru.stacked-crooked.com/a/aa52b45150e5eb0a

このサイクルアプローチは、楽観的ブロッキングとして知られています。 悲観的ロックと呼ばれる：スピンロック、ミューテックス...

そして、このサイクルのすべての操作が悲観的ロックなしで実行される場合、そのようなアルゴリズムはロックフリーと呼ばれます。

多くの場合、ポインターはアトミックCAS関数に置き換えられます。つまり、新しいメモリが割り当てられ、可変オブジェクトがそれにコピーされ、そのポインターが取得され、このコピーに対して一連のアクションが実行され、最後に、新しいオブジェクトのポインターへの古いポインターがCAS関数に置き換えられます別のスレッドが古いポインターを変更しなかったとき。 しかし、ポインターが別のスレッドによって変更された場合、すべてが再び繰り返されます。

「 ABA 」と呼ばれる問題がある可能性があります。 他のスレッドがポインタを2回変更し、2回目はポインタが元の値に変更されるが、このアドレスでは他のスレッドがすでにオブジェクトを削除して新しいオブジェクトを作成する場合。 つまり ポインタの値も別のオブジェクトを指しますが、値が変更されていないことがわかり、オブジェクトは置き換えられなかったと思います。 この問題を解決する方法は多数あります。たとえば、LL / SC、RCU、hazard_pointer、ガベージコレクターなどです。

アトミックは、スレッド間でデータを交換する最速の方法です。 さらに、すべてのアトミック操作に対して、より厳しくなく高速なメモリバリアを使用できます。これについては、以下で詳細に検討します。 デフォルトでは、最も安全で厳密な並べ替えバリアが使用されます：std :: memory_order_seq_cst。 しかし、前述したように、アトミック変数を使用して複雑なロジックを実装するには多大な労力が必要です。

（2）-（1）アトミックおよびロックベース。
ただし、複数の変数を一度にアトミックに読み取りまたは変更する必要がある場合は、std :: atomic a、b、c; ロックフリーアルゴリズムを実装してABAの問題を解決したくない場合は、ロックを使用する必要があります。 ほとんどのCPUのアトミックプロセッサCAS機能は、最大64ビット幅の変数が1つだけ変更されたかどうかを確認できますが、その時点で別の変数が変更されている可能性があります。 解決策：std :: atomic <T>を使用すると、T-任意のサイズの構造のタイプに使用できます。

C ++標準では、std :: atomic <T>に型Tを使用する可能性が導入されています。これは、「簡単にコピー可能な型」、つまり std :: is_trivially_copyable <T> :: value == trueの条件を満たす

C ++ 標準ワーキングドラフト、プログラミング言語C ++ N4606の標準2016-07-12の内容 ： www.open-std.org/jtc1/sc22/wg21/docs/papers/2016/n4606.pdf
§29.5/ 1
ジェネリッククラステンプレートatomic <T>があります。 テンプレート引数Tの型は簡単にコピーできるものでなければなりません （3.9）。 [注：静的に初期化することもできない型引数は、使用が難しい場合があります。 -終了ノート]

§3.9/ 9
スカラー型、簡単にコピー可能なクラス型（9項）、そのような型の配列、およびこれらの型のcv修飾バージョン（3.9.3）は、簡単にコピー可能な型と総称されます


しかし、プロセッサーのアトミックCAS関数が、最大64ビット幅の変数が1つだけ変更されたかどうかをチェックでき、それぞれ32ビットの変数が3つある場合、CAS関数はstd :: atomic <T>でどのように機能しますか？ CASおよび他のすべての関数は、T（簡単にコピー可能な型）に対して、std :: atomic <T>の標準実装に含まれるロック（std :: mutexまたはその他）を自動的に使用します。

いくつかの変数のアトミックな変更-変数struct Tから構造体を使用できます{int price、count、total; }; std :: atomic <T>テンプレートの型として。
例：[5] coliru.stacked-crooked.com/a/bdfb3dc440eb6e51
出力例：10、7、70

この例では、ある時点での最後の値70は、最初の2つの値10 * 7-の積に等しくなります。 構造全体は原子的にのみ変化します。

x86用のgccおよびclangのこのコードは、-latomicフラグを使用してコンパイルする必要があります
さらに、std :: atomic <T> shared_valへの各呼び出し。 shared_val.is_lock_free（）== false関数の値から明らかなように、内部でロックが発生します。

つまり グローバルに、オプティミスティックロック（ループ）を使用し、アトミック変数にアクセスするときにローカルで2つのペシミスティックロックを使用しました。古い値を取得してCAS関数を呼び出します。

（1）ロックベース。
ただし、タイプTには必須の簡単にコピー可能な条件があるため、作成したTのタイプにはstd :: atomic <T>を使用できません。すべてのSTLコンテナの中で、std :: array <>のみを使用できます。 たとえば、std :: atomic <std :: map <int、int >>は使用できません。 type std :: map <>は、そのテンプレートの引数に対して、簡単にコピーできません。 また、独自のクラスをstd :: atomic <T>のタイプTとして使用することはできません。

この場合、自分でミューテックスオブジェクトを作成し、共有オブジェクトを使用する前に毎回ブロックし、その後ロック解除する必要があります。 コンセプト： en.cppreference.com/w/cpp/concept/Mutex

C ++には、次のミューテックスがあります。std:: mutex、std :: recursive_mutex、std :: timed_mutex、std :: recursive_timed_mutex、std :: shared_timed_mutex、std :: shared_mutex。 それらの詳細については、 en.cppreference.com / w / cpp / threadを参照してください 。

たとえば、スレッド間で共有されるオブジェクトstd :: map <int、T>を作成し、それを保護するミューテックスを作成して、複数のスレッドでリンクを渡します。 そして、各スレッドで、共有オブジェクト[6] coliru.stacked-crooked.com/a/a97e905d54ae1fbbを使用する前にミューテックスをブロックします。

RAIIイディオムを使用してブロックします。std:: lock_guard <std :: mutex> lock（mtx）; -このオブジェクトを作成すると、そのコンストラクターはミューテックスをブロックし、オブジェクトの寿命が終了すると、デストラクタがミューテックスをロック解除します。 したがって、ロックを解除することを忘れないでしょう。 デストラクタは自動的に呼び出されます。

しかし、まだ4つの主な問題があります。

  1. デッドロック-スレッド1がmtx1をブロックし、スレッド2がmtx2をブロックするようにコードを記述すると、スレッド1のロックを保持している間、mtx2をキャプチャしようとし、スレッド2はmtx1をキャプチャしようとします永遠に。 ロックフリーアルゴリズムではこの問題はありませんが、ロックフリーを使用してロジックを実装することはできません。複数のコンテナの一貫したアトミックな変更の例を使用してこれを示します。
  2. mutexがロックされている間に、std :: lock_guard lockの寿命よりも長い寿命を持つ共有オブジェクトへのリンクをポインターに割り当てる場合、ロック解除後、このポインターによって共有オブジェクトを参照できます-これはデータ競合の問題につながります、つまり 共有オブジェクトの一貫性のない状態、および誤動作またはプログラムのクラッシュ。 共有オブジェクトから受け取ったイテレータがミューテックスのロックを解除した後に使用される場合も同じことが起こります。
  3. ミューテックスを混在させて、別のオブジェクト（データの競合）を保護するミューテックスをブロックできます。
  4. ミューテックスを適切な場所にロックするのを忘れるだけです-データの競合。

ポインターイディオムの周囲で実行


RAIIのイディオムに加えて、別の興味深いイディオムがあります。これは、最後の2つの問題に対処するのに役立つExecute Around Pointerです。

  1. ミューテックスはオブジェクトとマージされ、個別のミューテックスではなく、オブジェクト自体をブロックできます
  2. ミューテックスは、保護されたオブジェクトのクラスのメンバーにアクセスするときに自動的にブロックされます—さらに、式の期間中はブロックされます。

その結果、ミューテックスをロックすることを忘れることができず、ミューテックスを混同することはできません。

オブジェクトをスレッドセーフにする


Execute Around Pointer Idiomは、実行の順序が厳密に定義された有名なイディオムであり、視覚化からロギングまでのさまざまな目的に使用されます。en.wikibooks.org / wiki / More_C%2B%2B_Idioms/ Execute- Around_Pointer
例：[7] coliru.stacked-crooked.com/a/4f3255b5473c73cc

  execute_around<std::vector<int>> vecc(10, 10); int res = my_accumulate(vecc->begin(), vecc->end(), 0);

最初に、execute_around内のmutexをブロックするプロキシタイプの一時オブジェクトが作成されます。次に、begin（）およびend（）関数によって返される反復子が関数に渡され、my_accumulate（）関数が実行されます。 、およびそれらのデストラクタがミューテックスのロックを解除します。

詳細については、記事「 C ++ Patterns Executing Around Sequences」を参照してください。 Kevlin Henney ： hillside.net/europlop/HillsideEurope/Papers/ExecutingAroundSequences.pdf
C ++には、標準§1.9（13）の実行順序を厳密に定義する2つの定義があります。前に順序付けられた後と順序付けられた後です。 以下の標準からの引用では、「前にシーケンス」が2回表示されます。

Execute Around Pointer Idiomのすべてのアクションの実行の原則と順序は、プログラミング言語C ++ N4606 2016-07-12のC ++ Working Draft Standardに厳密に記述されています。www.open-std.org/ jtc1 / sc22 / wg21 / docs / papers / 2016 /n4606.pdf
まず、標準から5つの引用符を付け、次に各引用符がExecute Around Pointer Idiomの動作をどのように説明するかを示します。

1. rawポインター以外のすべてのタイプのTの場合：x-> mは（x.operator->（））-> mと解釈されます。 つまり 式（x-> m）は何回も展開されます（（x.operator->（）。operator->（））-> m生のポインタを取得します。意味式が同じ3つの例：[8] coliru。 stacked-crooked.com/a/dda2474024b78a0b
§13.5.6
operator->は、パラメーターを取らない非静的メンバー関数でなければなりません。 ->を使用するクラスメンバーアクセス構文を実装します。
postfix-expression->テンプレートopt id-expression
後置式->擬似デストラクタ名
式x-> mは、T ::演算子->（）が存在し、演算子が最適一致関数として選択されている場合、タイプTのクラスオブジェクトxに対して（x.operator->（））-> mとして解釈されます。オーバーロード解決メカニズム（13.3）。

2.関数が呼び出されると、たとえそれが「インライン」であっても、関数の引数が計算される式からの計算と効果は、関数の本体が実行される前に絶対に実行されます。
§1.9 / 16
関数を呼び出すとき（関数がインラインであるかどうかに関係なく）、引数式、または呼び出された関数を指定する接尾辞式に関連付けられたすべての値の計算と副作用は、本体のすべての式またはステートメントの実行前にシーケンスされます関数と呼ばれます。

3.一時オブジェクトが破棄される前に、式全体が完全に実行されます。
§1.9 / 10
 void f() { if (S(3).v()) // full-expression includes lvalue-to-rvalue and // int to bool conversions, performed before // temporary is deleted at end of full-expression { } }

4.式全体が完全に実行された後、一時オブジェクトは作成された順序とは逆の順序で破棄されます。
§1.9脚注8
12.2で指定されているように、完全な式が評価された後、一時オブジェクトのデストラクタ関数のゼロ以上の呼び出しのシーケンスが、通常は各一時オブジェクトの構築の逆の順序で行われます。

5.一時オブジェクトが式全体の最後で破棄されない3つのケース-配列の要素が初期化される2つのケース、一時オブジェクトへのリンクが作成される3番目のケース。
§12.2一時オブジェクト
§12.2 / 5
完全な表現の終わりとは異なる時点で一時が破棄される3つのコンテキストがあります。 最初のコンテキストは、デフォルトのコンストラクターが呼び出されて、対応する初期化子がない配列の要素を初期化する場合です（8.6）。 2番目のコンテキストは、配列全体がコピーされている間に配列の要素をコピーするためにコピーコンストラクターが呼び出される場合です（5.1.5、12.8）。 どちらの場合でも、コンストラクターに1つ以上のデフォルト引数がある場合、デフォルト引数で作成されたすべてのテンポラリーの破棄は、次の配列要素（存在する場合）の構築の前にシーケンスされます。 3番目のコンテキストは、参照が一時にバインドされるときです。


たとえば、単純化されたクラスexecute_around <>があります

 template<typename T, typename mutex_type = std::recursive_mutex> class execute_around { std::shared_ptr<mutex_type> mtx; std::shared_ptr<T> p; void lock() const { mtx->lock(); } void unlock() const { mtx->unlock(); } public: class proxy { std::unique_lock<mutex_type> lock; T *const p; public: proxy (T * const _p, mutex_type& _mtx) : lock(_mtx), p(_p) { std::cout << "locked \n";} proxy(proxy &&px) : lock(std::move(px.lock)), p(px.p) {} ~proxy () { std::cout << "unlocked \n"; } T* operator -> () {return p;} const T* operator -> () const {return p;} }; template<typename ...Args> execute_around (Args ... args) : mtx(std::make_shared<mutex_type>()), p(std::make_shared<T>(args...)) {} proxy operator -> () { return proxy(p.get(), *mtx); } const proxy operator -> () const { return proxy(p.get(), *mtx); } template<class Args> friend class std::lock_guard; };

そして、テンプレートクラスexecute_around <>を次のように使用します。例：[45] coliru.stacked-crooked.com/a/d2e02b61af6459f5

 int main() { typedef execute_around<std::vector<int>> T; T vecc(10, 10); int res = my_accumulate(vecc->begin(), vecc->end(), 0); return 0; }

その後、最後の式は、いくつかの変換を通じて次の形式に縮小できます。

1.標準の最初の引用によると、x-> mは（x.operator->（））-> mとして解釈されます。

  int res = my_accumulate( (vecc.operator->())->begin(), (vecc.operator->())->end(), 0);

2.以来 vecc.operator->（）は、一時オブジェクトT :: proxy（）を返します。

  int res = my_accumulate( T::proxy(vecc.p.get(), *vecc.mtx)->begin(), T::proxy(vecc.p.get(), *vecc.mtx)->end(), 0);

3.さらに、引用符2、3、4によると、プロキシタイプの一時オブジェクトは、関数の実行が開始される前に作成され、関数の終了後（式全体の終了後）に破棄されます。

 T::proxy tmp1(vecc.p.get(), *vecc.mtx); // lock-1 std::recursive_mutex T::proxy tmp2(vecc.p.get(), *vecc.mtx); // lock-2 std::recursive_mutex int res = my_accumulate(tmp1->begin(), tmp2->end(), 0); tmp2.~ T::proxy(); // unlock-2 std::recursive_mutex tmp1.~ T::proxy(); // unlock-1 std::recursive_mutex

4.もう一度最初の引用によると：
•tmp1-> begin（）は（tmp1.operator->（））-> begin（）と同等です
•tmp1.operator->（）はpを返します
その結果、pはstd :: vector型のオブジェクトへのshared_ptrポインターです。

 typedef execute_around<std::vector<int>> T; T vecc(10, 10); T::proxy tmp1(vecc.p.get(), *vecc.mtx); // lock-1 std::recursive_mutex T::proxy tmp2(vecc.p.get(), *vecc.mtx); // lock-2 std::recursive_mutex int res = my_accumulate(tmp1.p->begin(), tmp2.p ->end(), 0); tmp2.~ T::proxy(); // unlock-2 std::recursive_mutex tmp1.~ T::proxy(); // unlock-1 std::recursive_mutex


4つのステップで、すべてのイディオムアクションの厳密なシーケンスを説明しました。 標準では、一時変数tmp1とtmp2の作成の相互順序が保証されていないことに注意してください。 tmp2を最初に作成してからtmp1を作成できますが、これによりプログラムのロジックは変更されません。
標準の5番目の引用を参照していないことに注意してください。それは、オブジェクトの削除の時間が与えられたものと異なるかもしれない3つのケースを記述します、そして、我々が見るように、これらのケースのどれも私たちのものに対応することができません。標準引用の最初の2つのケースは、配列の初期化またはコピーであり、一時オブジェクトの寿命を短くし、3番目のケースは、リンクへのリンクの存在による一時オブジェクトの寿命の延長です。

スレッドセーフ連想配列


同意します。任意の型を渡すことができるsafe_ptr <>テンプレートクラスがあれば便利で、その結果、スレッドセーフな結果の型を取得できますか？
safe_ptr <std :: map <std :: string、std :: pair <std :: string、int> >> safe_map_strings;
さらに、連想配列へのポインターを使用してこのオブジェクトを操作できます。std:: shared_ptr <std :: map <std :: string、std :: pair <std :: string、int> >>
しかし、今では安全に作業できます異なるストリームから取得し、個々の式はスレッドセーフになります：

  (*safe_map_strings)["apple"].first = "fruit"; (*safe_map_strings)["potato"].first = "vegetable"; safe_map_strings->at("apple").second = safe_map_strings->at("apple").second * 2; safe_map_strings->find("potato")->second.second++;

スレッドセーフな連想の完全に機能する例を示します：std :: map <>。[9]
coliru.stacked-crooked.com/a/5def728917274b22

 #include <iostream> #include <string> #include <vector> #include <memory> #include <mutex> #include <thread> #include <map> template<typename T, typename mutex_t = std::recursive_mutex, typename x_lock_t = std::unique_lock<mutex_t>, typename s_lock_t = std::unique_lock<mutex_t >> class safe_ptr { typedef mutex_t mtx_t; const std::shared_ptr<T> ptr; std::shared_ptr<mutex_t> mtx_ptr; template<typename req_lock> class auto_lock_t { T * const ptr; req_lock lock; public: auto_lock_t(auto_lock_t&& o) : ptr(std::move(o.ptr)), lock(std::move(o.lock)) { } auto_lock_t(T * const _ptr, mutex_t& _mtx) : ptr(_ptr), lock(_mtx){} T* operator -> () { return ptr; } const T* operator -> () const { return ptr; } }; template<typename req_lock> class auto_lock_obj_t { T * const ptr; req_lock lock; public: auto_lock_obj_t(auto_lock_obj_t&& o) : ptr(std::move(o.ptr)), lock(std::move(o.lock)) { } auto_lock_obj_t(T * const _ptr, mutex_t& _mtx) : ptr(_ptr), lock(_mtx){} template<typename arg_t> auto operator [] (arg_t arg) -> decltype((*ptr)[arg]) { return (*ptr)[arg]; } }; void lock() { mtx_ptr->lock(); } void unlock() { mtx_ptr->unlock(); } friend struct link_safe_ptrs; template<typename mutex_type> friend class std::lock_guard; //template<class... mutex_types> friend class std::lock_guard; // C++17 public: template<typename... Args> safe_ptr(Args... args) : ptr(std::make_shared<T>(args...)), mtx_ptr(std::make_shared<mutex_t>()) {} auto_lock_t<x_lock_t> operator -> () { return auto_lock_t<x_lock_t>(ptr.get(), *mtx_ptr); } auto_lock_obj_t<x_lock_t> operator * () { return auto_lock_obj_t<x_lock_t>(ptr.get(), *mtx_ptr); } const auto_lock_t<s_lock_t> operator -> () const { return auto_lock_t<s_lock_t>(ptr.get(), *mtx_ptr); } const auto_lock_obj_t<s_lock_t> operator * () const { return auto_lock_obj_t<s_lock_t>(ptr.get(), *mtx_ptr); } }; // --------------------------------------------------------------- safe_ptr<std::map<std::string, std::pair<std::string, int> >> safe_map_strings_global; void func(decltype(safe_map_strings_global) safe_map_strings) { //std::lock_guard<decltype(safe_map_strings)> lock(safe_map_strings); (*safe_map_strings)["apple"].first = "fruit"; (*safe_map_strings)["potato"].first = "vegetable"; for (size_t i = 0; i < 10000; ++i) { safe_map_strings->at("apple").second++; safe_map_strings->find("potato")->second.second++; } auto const readonly_safe_map_string = safe_map_strings; std::cout << "potato is " << readonly_safe_map_string->at("potato").first << " " << readonly_safe_map_string->at("potato").second << ", apple is " << readonly_safe_map_string->at("apple").first << " " << readonly_safe_map_string->at("apple").second << std::endl; } int main() { std::vector<std::thread> vec_thread(10); for (auto &i : vec_thread) i = std::move(std::thread(func, safe_map_strings_global)); for (auto &i : vec_thread) i.join(); std::cout << "end"; int b; std::cin >> b; return 0; }

結論：
ポテトは野菜65042、リンゴは果物81762
、リンゴは果物81716、
ポテトは野菜84716、リンゴは果物84720、
ポテトは野菜86645、リンゴは果物86650、
ポテトは野菜90288、リンゴは果物90291、
ポテトは野菜93070、リンゴはフルーツ93071
ジャガイモは野菜93810、リンゴはフルーツ93811
ジャガイモは野菜95788、リンゴはフルーツ95790
ジャガイモは野菜98951、リンゴはフルーツ98952
ジャガイモは野菜100000、リンゴはフルーツ100000
終わり

したがって、2つの結論：

  1. 100000 , 10 -. , , operator -> auto_lock_t auto_lock_obj_t , , - – data-race: [10] coliru.stacked-crooked.com/a/45d47bcb066adf2e
  2. 10000 , , .. . つまり各インクリメント演算子++の前に、ミューテックスがブロックされ、インクリメントの直後にロック解除され、その後、インクリメントを実行した別のスレッドによってミューテックスがブロックされる可能性がありました。各スレッドの開始時に、std :: lock_guard <> を使用して、スレッド関数の実行が終了するまでmutexをすぐにロックできます。また、スレッドが擬似並列ではなく連続して実行された場合、何らかの結果が表示されます： a / cc252270fa9f7a78

どちらの結論も、safe_ptr <T>スマートポインタークラステンプレートが、T型の保護オブジェクトのスレッドセーフを自動的に提供することを確認します。

複数のオブジェクトのスレッド安全性、原子性、一貫性。


一貫性が維持されるように、複数のオブジェクトを一度にアトミックに変更する方法を示します。そして、それがいつ必要になるか、どのように行うか、これが行われない場合に何が起こるかを示します。
簡単な例を次に示します。2つのテーブルがあるとします。

画像
  1. user_accounts（INT user_id、STRING user_name、INT money） -各クライアントの金額を含むテーブル-user_idでソート
  2. cash_flows（INT unique_id、INT src_id、INT dst_id、INT time、INT money） - お金の動きを示すテーブル-各レコードに対して2つの連想配列が参照され、フィールドsrc_idとフィールドdst_idでソートされます

 // 1-st table struct user_accounts_t { std::string user_name; int64_t money; user_accounts_t(std::string u, int64_t m) : user_name(u), money(m) {} }; std::map<uint64_t, user_accounts_t> user_accounts; // 2-nd table struct cash_flows_t { uint64_t unique_id, src_id, dst_id, time; int64_t money; }; std::atomic<uint64_t> global_unique_id; // SQL-sequence std::multimap<uint64_t, std::shared_ptr<cash_flows_t>> cash_flows_src_id; std::multimap<uint64_t, std::shared_ptr<cash_flows_t>> cash_flows_dst_id;

DBMS（RDBMS）に関して：


実際のタスクでは、テーブルに顧客の数百万のレコードとキャッシュフローの数十億のレコードが含まれる場合があります。この場合、フィールドuser_id、src_id、dst_idのインデックスは、それらの検索を数十万回高速化するため、非常に必要です。

3人のユーザーが、3つの並列フローで3つのタスクを実行する要求を受け取ったとします

。1. move_money（） -ストリームは、あるクライアントから別のクライアントに送金します


2. show_total_amount（） -すべての顧客の金額を表示します


3. show_user_money_on_time（） -指定されたuser_idでのクライアントの金額を一度に表示します


たとえば、CPUコアを別のスレッドに提供するために、オペレーティングシステムによってスレッドがいつでも中断される可能性があることがわかっています。最も危険なことは、これが非常にまれに発生することであり、デバッグ中にこれに遭遇することはありませんが、いつかはクライアントで発生し、これがデータ競合につながる場合、金融システムでお金が単純に消失する可能性があります。

したがって、エラーをすぐに確認するために、最も重要な場所でスレッドを数ミリ秒間スリープ状態にする待機関数を意図的に追加します。

safe_ptr <>スレッドセーフを使用してuser_accounts、cash_flows_src_id、cash_flows_dst_idテーブルを作成しますが、これによりプログラム全体がスレッドセーフになりますか？
[12] coliru.stacked-crooked.com/a/5bbba59b63384a2b
<<<でマークされたプログラム出力の「メイン行」を見てみましょう。

初期テーブルsafe_user_accounts：
at = 0 <<<
1 => John Smith、100
2 => John Rambo、150
-start transaction ... show_total_amount（）
1 => John Smith、100
2 => John Rambo、100
結果：すべてのアカウントtotal_amount = 200 <<<

-トランザクションを開始... show_user_money_on_time（）
1 => John Smith、150、at time = 0 <<<

2つのエラーがすぐに表示されます。

  1. 最初は、合計で（2人の）すべてのユーザーが250のお金を持っていて、show_total_amount（）関数は200のみを示し、別の50はどこかに消えました
  2. 時間= 0で、ユーザー1に100のお金があり、show_user_money_on_time（）関数が誤った結果を示しました-ユーザー1には時間= 0で150のお金がありました

問題は、原子性が個々のテーブルとインデックスのレベルでのみ観察され、集計ではないため、一貫性が侵害されることです。解決策は、アトミックに実行する必要があるすべての操作の間、使用されているすべてのテーブルとインデックスをロックすることです。これにより、一貫性が維持されます。

追加された行は黄色で強調表示されます。

画像

正しい例：[13] coliru.stacked-crooked.com/a/c8bfc7f5372dfd0c
プログラムの出力で、<<<のマークが付いた「メインライン」を見てみましょう。
初期テーブルsafe_user_accounts：
at = 0 <<<
1 => John Smith、100
2 => John Rambo、150

結果：すべてのアカウントtotal_amount = 250 <<<

1 => John Smith、100、at = 0 <<<


これですべてが真実になり、すべてのクライアントの合計金額は250であり、クライアント1からの金額は時間0で100でした。

つまり1つのオブジェクトではなく、3つのオブジェクトで即座に操作をアトミックに実行でき、どの操作でもデータの一貫性が維持されました。

ただし、ここでは別の問題が発生する可能性があります。あなたまたは関数のいずれかの別の開発者が異なる順序でコンテナミューテックスをブロックすると、デッドロックと呼ばれる状況が発生する可能性があります。

上記の正しい例では、関数move_money（）とshow_user_money_on_time（）の両方のmutexを同じ順序でブロックしました。


それでは、各関数のコンテナ内のミューテックスを異なる順序でブロックするとどうなるか見てみましょう。
•move_money（）


•show_user_money_on_time（）


move_money（）関数はlock2をロックし、lock3が解放されてロックされるまで待機します。show_user_money_on_time（）関数はlock3をロックし、lock2が解放されてロックされるのを待ちます。そして、彼らは永遠にお互いを待ちます。
例：[14] coliru.stacked-crooked.com/a/0ddcd1ebe2be410b

結論：
初期テーブルsafe_user_accounts：
at = 0 <<<
1 => John Smith、100
2 => John Rambo、150

-start transaction ... move_money（）
-start transaction ... show_total_amount（）

1 => John Smith、100
2 => Johnランボー、150

つまり関数move_money（）およびshow_user_money_on_time（）は完了せず、デッドロック状態で永久に停止しました。
4つの解決策があり

ます。1.すべての機能の開発者は、常に同じ順序でmutexをブロックし、ミスを犯しません-これは非常に信頼できない前提です

2。最初に、アトミックに使用されるすべてのオブジェクトを1つの構造に結合し、構造型struct all_t {std :: map <int、int> m1;の安全なポインターを使用します。 std :: multimap <int、int> m2; ...}; safe_ptr <all_t> safe_all_obj; -ただし、これら2つのコンテナを最初に別々にのみ使用した場合、safe_ptr <map <int、int >> m1; safe_ptr <multimap <int、int >> m2;そして、すでに多くのコードを作成し、それらを1つのmutexで保護された1つの構造に結合することを決定した場合、たとえば（2）のm2->の代わりに、それらを使用するすべての場所を書き換える必要があります; safe_all_obj-> m2.at（5）;が必要です。大量のコードを書き換えることはあまり便利ではありません。

3。一緒に使用されるsafe_ptr <>を組み合わせて、同じ再帰ミューテックスを使用します。その後、ブロックされる順序は関係なく、これらのオブジェクトの一貫性は常に保持され、デッドロックは発生しません。これを行うには、1行追加するだけです-これは非常に便利です。ただし、これによりパフォーマンスが低下する可能性があります。現在、コンテナの1つをブロックすると、それに関連付けられているすべてのコンテナが常にブロックされます。一貫性は必要ない場合でも得られますが、生産性は低下します。例：[15] coliru.stacked-crooked.com/a/2a6f1535e0b95f7b

コード内のすべての変更は、1行だけ

です。

結論-主な行が表示されます：
初期テーブルsafe_user_accounts：
at = 0 <<<
1 => John Smith、100
2 => John Rambo、150

結果：すべてのアカウントtotal_amount = 250 <<<

1 => John Smith、100、at = 0 <<<

4.各mutexをロックするタイムアウト時間を設定して、さまざまなタイプの複数のミューテックスに対してロックを一度に使用できます。この間に少なくとも1つのmutexをロックできない場合、以前にロックされたすべてのmutexのロックが解除され、スレッドはしばらく待機してからすべてのmutexを順番にブロックしようとします。これを行うには、コンテナlock_timed_any_infinity lock_all（safe_cash_flows_src_id、safe_cash_flows_dst_id、safe_user_accounts）を使用する前に1行追加するだけです。コンテナミューテックスをブロックする順序は関係ありません。例：[16] coliru.stacked-crooked.com/a/93206f216ba81dd6
つまり 異なるシーケンスでミューテックスをブロックしても：


画像
したがって、ロック（ロック）の助けを借りて、永遠のデッドロックなしで保証されるComposableの問題を解決しました：https : //en.wikipedia.org/wiki/Lock_ (computer_science) #Lack_of_composability

コンポーザブルとデッドロック


なぜなら上記のスレッドセーフのためにロックを使用し、その後、アルゴリズムはロックベースと呼ばれます。

しかし、ロックフリーコンテナにデッドロックがなく、トランザクションメモリに基づいたアルゴリズムがなく、MSDB（ロックベースのIL）とOracle（マルチバージョン同時実行制御）の最新のDBMSにデッドロックがあり、すべてが本当に優れています。

ロックフリーアルゴリズムでは、いくつかのコンテナをアトミックに変更することはできません。 RDBMS（RDBMS）には、ロックベースのアルゴリズムと同様にデッドロックに関するすべての問題があり、多くの場合、ロックタイムアウトまたはロックグラフを通じて同じ方法で問題を解決します。また、C ++標準の新しいトランザクションセーフセクションでは、std :: map <>などの複雑なアルゴリズムのスレッドセーフな使用が許可されていません。

ロックフリーアルゴリズムには、Composable操作というプロパティがありません-いくつかのロックフリーアルゴリズムのアトミックな使用です。 つまりいくつかのロックフリーデータ構造を一度に変更したり、アトミックに読み取ることはできません。たとえば、libCDSのロックフリー連想配列コンテナを使用できますまた、それらは個別にスレッドセーフになります。ただし、複数のロックフリーコンテナで操作を一度にアトミックに実行し、一貫性を維持する場合は、これを行うことができません。それらのAPIは、複数のコンテナで同時に操作するためのロックフリー機能を提供しません。あるコンテナを変更または読み取り中に、別のコンテナはその時点ですでに変更されています。これを回避するには、ロックを使用する必要があります。この場合、すでにロックに基づいたコンテナになっているため、ロックベースのアルゴリズムのすべての問題、つまりデッドロックの可能性があります。さらに、1つのコンテナのみを使用する場合にロックが使用される場合があります。


MSSQL（ロックベース）やOracle（マルチバージョン同時実行制御）などのトランザクションRDBMSでは、ロックも使用されるため、デッドロックの問題が発生します。これは、たとえば、ロックグラフを作成して周期的な期待値を見つけるか、設定することで自動的に解決できますロック待機タイムアウトtblからcolを選択します。更新待機30のid（....）。タイムアウトが期限切れになった場合、またはロックグラフでデッドロックが見つかった場合、いずれかのトランザクションのロールバック（ロールバック）が発生します。このトランザクションによって既に行われたすべての変更を元に戻し、ブロックされているすべてのロックを解除してから、トランザクションを最初から（そして何度も）実行することができます。


トランザクションメモリは、ロックフリーコンテナとは異なり、多くのコンテナ/データでアトミックに動作できます。 つまりトランザクションメモリには、Composable操作プロパティがあります。内部では、悲観的ロック（デッドロック競合の可能性）または楽観的ロック（競合修正と競合修正の競合の可能性が高い）のいずれかが使用されます。また、競合が発生した場合、トランザクションは自動的にキャンセルされ、最初から繰り返されます。これには、すべての操作の繰り返しが繰り返されます。これには多大なオーバーヘッドが伴います。 CPUレベルでハードウェアトランザクションメモリを作成することでこれらのオーバーヘッドを削減しようとしていますが、これまでのところ、許容できるパフォーマンスを示す実装はありません。 C ++標準では、Transactional Memoryを含めることも約束されていますが、将来的にのみ、これまでは実験的であり、std :: mapの操作をサポートしていません。つまりこれまでのところ、すべては理論的にのみ美しいものです。しかし、将来、これは通常の同期方法を置き換える可能性があります。

合計：

現在の結論：高性能を示すすべてのタイプのアルゴリズムとシステムにデッドロックの問題があり、複数のデータ構造が同時に関与しているため、safe_ptr <>の2つのソリューションを提案しました

  1. static link_safe_ptrs tmp_link（safe_user_accounts、safe_cash_flows_src_id、safe_cash_flows_dst_id）; -複数のコンテナに1つのミューテックスを使用する
  2. lock_timed_any_infinity lock_all（safe_cash_flows_src_id、safe_cash_flows_dst_id、safe_user_accounts）;-ロックタイムアウトを使用し、時間の終わりにすべてをロック解除して、再度ロックを試行します

safe_ptr <>に1つのコンテナと再帰ミューテックスのみが使用されている場合、safe_ptr <>でデッドロックは不可能です。デッドロックには、少なくとも2つの再帰mutex（または1つの非再帰）が必要です。

構成可能なロックベースのアルゴリズム


一般的な場合、ロックベースのプログラムは構成可能ではないと考えられます。 2つのロックベースのデータ構造を取得し、それらを1つずつアトミックに変更するだけでは、常に一貫した状態になりません。

しかし、上記では、3つのロックベースのコンテナーを簡単に配置しましたが、どのように成功しましたか？この点については、わずかに明確化されています-太字で示しています：
Perhaps the most fundamental objection [...] is that lock-based programs do not compose: correct fragments may fail when combined. For example, consider a hash table with thread-safe insert and delete operations. Now suppose that we want to delete one item A from table t1, and insert it into table t2; but the intermediate state (in which neither table contains the item) must not be visible to other threads. Unless the implementor of the hash table anticipates this need, there is simply no way to satisfy this requirement. [...] In short, operations that are individually correct (insert, delete) cannot be composed into larger correct operations.

—ティム・ハリス他、「コンポーザブルメモリトランザクション」、セクション2：背景、ページ2 [6]
www.microsoft.com/en-us/research/wp-content/uploads/2005/01/2005-ppopp- composable.pdf
実際のところ、ロックベースのアルゴリズムは、実装中にそのような機会が定められていない場合はコンパイルされません。つまりロックベースのデータ構造は自動的にコンパイルされませんが、外部のレイアウト操作のためにmutexにアクセスできる場合は、たとえばlock_timed_any_infinityクラスのように手動でコンパイルできます。

ロックベースのsafe_ptr <T>テンプレートクラスを実装し、リンク操作を使用してデッドロックをリンクおよび解決する必要性のために提供したすべてのタイプTに対して、link_safe_ptrs、lock_timed_any_infinity、lock_timed_any_onceを実装しました。

では、なぜロックと悲観的なバージョンを選択したのですか？


アルゴリズムを実装する際に、産業DBMSの豊富な経験を定期的に参照していきます。

safe_ptr.hのSafe_ptr <T>の
例：github.com/AlexeyAB/object_threadsafe/tree/master/any_object_threadsafe

結論：

異なるストリームからの安全なアクセスを自動的に提供するために、Execute Around Pointer Idiomの正確性を証明しました。彼らはその構成可能性の例を示しました。また、スレッドの安全性を確保するために悲観的ロックを使用する利点も示しました。

Source: https://habr.com/ru/post/J328348/

More articles:


All Articles