ロックフリーのデータ構造。 理論：記憶モデル

前回の記事では、仮想的ではありますが、プロセッサの内部を調べました。 並列コードが正しく実行されるためには、内部の読み取り/書き込みの最適化を実行できる制限をプロセッサに伝える必要があることがわかりました。 これらのヒントは記憶の障壁です。 メモリバリアにより、メモリアクセス（より正確には、キャッシュへのアクセス-プロセッサはキャッシュを介してのみ外部とやり取りします）を合理化できます。 このような順序の「重大度」は異なる場合があります。各アーキテクチャは、「選択」障壁のセット全体を提供できます。 特定のメモリバリアを使用して、さまざまなメモリモデルを構築できます。これは、プログラムに実装される一連の保証です。

この記事では、C ++ 11メモリモデルについて説明します。


C ++は、低レベルのものを高レベルで表現する能力で長い間有名です。 C ++ 11メモリモデルを開発するとき、タスクはこのプロパティに違反することではありませんでした。つまり、プログラマに最大限の柔軟性を与えることでした。 他の言語（主にJava）の既存のメモリモデルと同期プリミティブとロックフリーアルゴリズムの内部構造の典型的な例を分析した後、標準の開発者は1つではなく3つのメモリモデルを提案しました。

• 順次一貫性
• セマンティクスの取得/解放
• 緩和されたメモリの順序付け

これらのメモリモデルはすべて、C ++で1つの列挙std::memory_orderで定義され、次の6つの定数があります。

• memory_order_seq_cst順次整合モデルを指します
• memory_order_acquire 、 memory_order_release 、 memory_order_acq_rel 、 memory_order_consume獲得/解放のセマンティクスに基づいてモデルを参照します
• memory_order_relaxedリラックスしたモデルを示します

これらのモデルを検討する前に、プログラムでメモリモデルを指定する方法を決定する必要があります。 ここで再びアトミック操作に戻る必要があります。
標準のmemory_order標準のアトミック操作への引数として指定されているため、 アトミック性に関する記事で引用した操作は、 memory_order C ++ 11で定義されている操作とは関係ありません。 これには2つの理由があります。

• セマンティック：実際、望ましい順序（メモリバリア）は、実行するアトミック操作を具体的に指します。 読み取り/書き込みアプローチでのバリアの配置は、バリア自体が存在するコードに意味的にまったく関係していないため、シャーマニズムです。これは、同等のものの中の単なる命令です。 さらに、読み取り/書き込みバリアはアーキテクチャに大きく依存しています。
• 実用的：Intel Itaniumには、他のアーキテクチャとは異なり、読み取り/メモリ命令およびRMW操作のメモリ順序を指定する特別な方法があります。 Itaniumでは、順序付けのタイプは、命令自体のオプションのフラグ（取得、解放、またはリラックス）として示されます。 さらに、アーキテクチャに獲得/解放セマンティクスを指定するための個別の命令（メモリバリア）はありません。

atomic<T>操作が実際にどのように見えるかを示しますstd::atomic<T>クラスのすべての特殊化には、少なくとも以下のメソッドが必要です。

 void store(T, memory_order = memory_order_seq_cst); T load(memory_order = memory_order_seq_cst) const; T exchange(T, memory_order = memory_order_seq_cst); bool compare_exchange_weak(T&, T, memory_order = memory_order_seq_cst); bool compare_exchange_strong(T&, T, memory_order = memory_order_seq_cst); 

ご覧のとおり、C ++ 11のデフォルトのメモリモデルは順次一貫性です。 最初に検討します。 しかし、最初に、コンパイラーの障壁について少し説明します。

コンパイラーの障壁

誰が私たちが書いたコードを並べ替えることができますか？ プロセッサがこれを実行できることがわかりました。 しかし、並べ替えの別のソース-コンパイラがあります。
最適化（特にグローバル）およびヒューリスティックの多くの方法が、シングルスレッド実行の仮定（おそらく暗黙的）の下で開発されました（そしてまだ開発中です）。 コードがマルチスレッドであることをコンパイラーが理解するのはかなり難しい（むしろ、理論的には不可能です）。 したがって、コンパイラにはヒントが必要です-障壁。 このようなバリアはコンパイラに伝えます。バリアの前のコードをバリアの後ろのコードに移動（混合）させないでください。 コンパイラバリア自体はコードを生成しません。
MS Visual C ++の場合、コンパイラバリアは擬似関数_ReadWriteBarrier() （この名前は常に私を困惑させました：読み取り/書き込みメモリバリアとの完全な関連付け-最も重いメモリバリア）。 GCCおよびClangの場合、 洗練されたデザインです
__asm__ __volatile__ ( "" ::: "memory" )

アセンブラー__asm__ __volatile__ ( … )挿入は、何らかの方法でGCC / Clangに対する障壁でもあることに注意してください：コンパイラーは、コード内でそれらをスローまたは上下に移動する権利を持ちません（ __volatile__修飾子はこれを言います）。
memory_orderは、プロセッサと同様にC ++ 11をサポートするコンパイラーに影響を与えます。これらはコンパイラーの障壁であり、コンパイラーがコードを並べ替える（つまり最適化する）能力を制限します。 したがって、もちろんコンパイラが新しい標準を完全にサポートしていない限り、特別なコンパイラバリアを指定する必要はありません。

シーケンシャル一貫性

ロックフリースタック（これはロックフリーデータ構造の最も単純なもの）を実装し、コンパイルしてテストしたとします。 そして、剥離（コアファイル）を取得します。 元気？ ロックフリースタックを行ごとに実装し、マルチスレッドをエミュレートして、ストリーム1の行Kとストリーム2の行Nを同時に実行する致命的な組み合わせに疑問を投げかけ、エラーを探し始めます（デバッガーはここでは役に立ちません）。崩壊。 いくつかのエラーを見つけて修正するかもしれませんが、とにかく-ロックフリーのスタックは落ちます。 なんで？
エラーを見つけて、同時に実行されているスレッドについてプログラムの行を比較することを試みることは、 順次一貫性保証と呼ばれます。 これは厳密なメモリモデルであり、プロセッサがプログラムで記述された順序ですべてを正確に実行することを前提としています。 たとえば、次のようなコードの場合：

 // Thread 1 atomic<int> a, b ; a.store( 5 ); int vb = b.load(); // Thread 2 atomic<int> x,y ; int vx = x.load() ; y.store( 42 ) ; 

順次一貫性に有効なのは、 a.store / b.loadとx.load / y.storeを交換するスクリプトを除く、すべての実行スクリプトx.load / y.store 。 このコードでは、load / storeでmemory_order引数を明示的にmemory_orderいないことに注意してください。デフォルトの引数値に依存しています。
コンパイラーにはまったく同じ保証が適用されます：コンパイラーは、 memory_order_seq_cst 後の memory_order_seq_cstがこのバリアの上に移動するようにコードを並べ替えることは禁じられており、その逆も同様です-seq_cst-barrierの前の操作はバリアの下で省略できません。
シーケンシャル整合性モデルは直感的に人間に近いものですが、非常に重大な欠点があります。これは、最新のプロセッサには厳密すぎるということです。 プロセッサが投機的実行を完全に使用することを許可しない、最も厳しいメモリバリアにつながります。 そのため、新しいC ++標準ではこのような妥協案が採用されました。

• 順次一貫性モデルは、厳密さと明確さのために、アトミック操作のデフォルトモデルとして使用する必要があります。
• 他のより弱いメモリモデルをC ++に導入して、最新のアーキテクチャの可能性を実現する

順次一貫性に加えて、取得/解放セマンティクスに基づくモデルが提案されました。

セマンティクスの取得/解放

名前の取得-リリースのセマンティクスから、このセマンティクスはリソースの取得（取得）およびリリース（リリース）に何らかの関係があると結論付けることができます。 確かにそうです。 リソースをキャプチャすると、メモリからレジスタに読み込まれ、解放するとレジスタからメモリに書き込まれます。

 load memory, register ; membar #LoadLoad | #LoadStore ; // acquire- //   acquire/release- ... membar #LoadStore | #StoreStore ; // release- store regiser, memory ; 

ご覧のとおり、このコードでは、重い障壁#StoreLoad 。 また、acquire-barrierとrelease-barrierはどちらもセミバリアであることに気付くことができます。acquireは後続のロード/ストアで以前のストア操作を順序付けせず、releaseは後続のロード/ストアで以前のロードを順序付けしません。 。 これは、プロセッサとコンパイラの両方に適用されます。
取得/リリースは、取得/リリース間に囲まれたすべてのコードに対する障壁です。 獲得バリアがリークする前の一部の操作（プロセッサまたはコンパイラによって並べ替え可能）が獲得/リリースセクション内にあり、リリースバリアが上に移動した後の一部の操作が（再びプロセッサまたはコンパイラによって）獲得/リリース内にある場合がありますセクション。 ただし、acquire-release内で完了した操作はそれを超えることはありません。

おそらく、取得/解放セマンティクスを適用する最も単純な例はスピンロックです。

これは、取得/解放時に最も単純なスピンロックのように見えます（C ++の専門家は、特殊なタイプのatomic_flagを使用してスピンロックを実装する必要があることを指摘しますが、アトミック変数（ブール値ではなく）にスピンロックを構築します-これの観点からはより視覚的です記事）：

 class spin_lock { atomic<unsigned int> m_spin ; public: spin_lock(): m_spin(0) {} ~spin_lock() { assert( m_spin.load(memory_order_relaxed) == 0);} void lock() { unsigned int nCur; do { nCur = 0; } while ( !m_spin.compare_exchange_weak( nCur, 1, memory_order_acquire )); } void unlock() { m_spin.store( 0, memory_order_release ); } }; 

このコードでは、 compare_exchangeが参照によってその最初の引数を受け入れ、CASが失敗した場合にそれを変更するという事実は、本当に私を悩ますことに注意してください！ 空でない本体でdo-whileループを作成するdo-whileます。
lockをマスターするlockメソッドでは、取得セマンティクスを使用し、 unlockメソッドではリリースセマンティクスを使用します（ちなみに、取得/リリースセマンティクスは、同期プリミティブから歴史を取りました。標準の開発者は、さまざまな同期プリミティブの実装を慎重に分析し、取得/リリースパターンを導き出しました。 ）上で書いたように、この場合に置かれた障壁は、 lock()とunlock()間に囲まれたコードが漏れることを許可しません-これが必要なものです！ また、 m_spin変数の原子性により、 m_spin m_spin=1である限り、誰もロックを取得できないことが保証されます。
アルゴリズムでは、 compare_exchange_weakをcompare_exchange_weakていることがわかります。 これは何ですか

弱く強力なCAS

覚えているように、プロセッサアーキテクチャは2つのクラスのいずれかに属することができます。プロセッサは、アトミックプリミティブCAS（比較とスワップ）を実装するか、LL / SCペア（ロードリンク/ストア条件付き）のいずれかです。 LL / SCペアを使用すると、アトミックCASを実装できますが、それ自体は多くの理由でアトミックではありません。 これらの理由の1つは、LL / SC内で実行されているコードがオペレーティングシステムによって中断される可能性があることです。 たとえば、OSが現在のスレッドを混雑させることを決定するのはこの時点です。 したがって、ストア条件付きの場合、再開後は機能しません。 つまり、CASはfalseを返しfalseが、実際にはこのfalseの理由はデータではなく、サードパーティのイベント（スレッドの中断）にある可能性があります。
この考慮事項により、標準の開発者は2つのcompare_exchangeプリミティブ（弱および強）を導入するようになりました。 これらのプリミティブはcompare_exchange_strong compare_exchange_weakおよびcompare_exchange_strongと呼ばれcompare_exchange_strong 。 弱いバージョンは失敗する可能性があります。つまり、変数の現在の値が予想される値と等しい場合でもfalse返しfalse 。 つまり、弱いCASはCASのセマンティクスに違反し、実際にtrueを返す必要がある場合にfalseを返すtrueができtrue （ただし、その逆はできません！）。強力なCASはこれを行えません。CASのセマンティクスに厳密に従います。 もちろん、何か価値があるかもしれません。
弱いCASを使用する必要がある場合と、強力なCASを使用する場合 私はこのルールを思い付きました：CASがループで使用され（これがCASを使用するための主なパターンであり）、ループ内に操作がない場合（つまり、ループの本体が軽い場合）、 compare_exchange_weak -weak CASを使用します。 それ以外の場合、強いcompare_exchange_strong 。

獲得/解放セマンティクスのメモリ順序

上で述べたように、次のmemory_order値は、取得/解放セマンティクスのために定義されています。

• memory_order_acquire
• memory_order_consume
• memory_order_release
• memory_order_acq_rel

読み込み（ロード）の場合、有効な値はmemory_order_acquireおよびmemory_order_consumeです。
書き込み用（ストア） memory_order_releaseのみ。
Memory_order_acq_relはRMW操作fetch_xxx 、 exchange 、 fetch_xxxに対してのみ有効です。 一般に、アトミックRMWプリミティブは、 memory_order_acquire取得セマンティクス、 memory_order_acquireリリースセマンティクスmemory_order_releaseまたはその両方であるmemory_order_acq_relを持つことができます。 RMW操作の場合、read-modify-writeプリミティブがアトミックな読み取りと書き込みを同時に実行するため、これらの定数がセマンティクスを決定します。 意味的には、RMW操作は、取得の読み取り、リリースのレコード、またはその両方と見なすことができます。
RMW操作のセマンティクスは、適用されるアルゴリズムでのみ決定できます。 多くの場合、ロックフリーアルゴリズムでは、スピンロックに多少似ている部分を区別できます。最初に特定のリソースを取得（取得）し、何かを実行（通常は新しい値を計算）し、最後にリソースに新しい値を設定（解放）します。 リソースの取得がRMW操作（通常はCAS）によって実行される場合、そのような操作はセマンティクスを取得する可能性があります。 新しい値の設定がRMWプリミティブ（CASまたはexchange ）によって実行される場合、ほとんどの場合、リリースセマンティクスがあります。 「かなり可能性が高い」という理由が挿入されています。RMW操作に適したセマンティクスを理解するには、アルゴリズムの詳細な分析が必要です。
RMWプリミティブが個別に実行される場合（取得/解放パターンを分離することは不可能です）、セマンティクスの3つのオプションが可能です。

• memory_order_seq_cst -RMW操作はアルゴリズムの重要な要素です。コードを並べ替え、読み取りと書き込みを上下に移動するとエラーが発生する可能性があります
• memory_order_acq_rel - memory_order_seq_cstに似ていmemory_order_seq_cstが、RMW操作は取得/解放セクション内にあります
• memory_order_relaxed -RMW操作（そのロード部分とストア部分）をコードの上下に移動しても（たとえば、操作がそのようなセクション内にある場合、取得/解放セクション内で）エラーになりません

これらのすべてのヒントは、RMWプリミティブに1つまたは別のセマンティクスを掛けるためのいくつかの一般原則を概説する試みとしてのみとるべきです。 各アルゴリズムについて詳細な分析を実行する必要があります。

セマンティクスを消費する

個別の、より弱い、取得セマンティクスの種類があります-消費読み取りセマンティクスです。 このセマンティクスは、DEC Alphaプロセッサの「賛辞」として導入されました。
アルファアーキテクチャには、他の最新のアーキテクチャとは大きな違いがあります。データの依存関係を壊す可能性があります。 このコード例では：

 struct foo { int x; int y; } ; atomic<foo *> pFoo ; foo * p = pFoo.load( memory_order_relaxed ); int x = p->x; 

彼女は、 p->x読みを並べ替えて、実際にp取得できます（これがどのように可能かを聞かないでください-これは Alpha プロパティです。Alphaを操作する必要がないため、確認も拒否もできません）。
この並べ替えを防ぐために、消費セマンティクスが導入されました。 構造体へのポインタのアトミックな読み取りに適用でき、その後に構造体のフィールドを読み取ります。 この例では、 pFooポインターは次のようになります。

 foo * p = pFoo.load( memory_order_consume ); int x = p->x; 

セマンティクスは、読み取りのリラックスしたセマンティクスと獲得したセマンティクスの中間にあります。 多くの現代建築では、リラックスした読書に対応しています。

そして再びCASについて

上記では、2つのCASを使用したatomic<T>インターフェースを示しました-弱いものと強いものです。 実際、CASにはさらに2つのバリアントがあり、追加の引数memory_orderます。

 bool compare_exchange_weak(T&, T, memory_order successOrder, memory_order failedOrder ); bool compare_exchange_strong(T&, T, memory_order successOrder, memory_order failedOrder ); 

この引数failedOrderとは何ですか？
CASは読み取り-変更-書き込みプリミティブであることを思い出してください。 障害が発生した場合でも、アトミック読み取りを実行します。 failedOrder引数は、CASが失敗した場合のこの読み取りのセマンティクスを定義するだけです。 通常の読み取りと同じ値がサポートされています。
実際には、「失敗時のセマンティクス」の表示はほとんど必要ありません。 もちろん、すべてアルゴリズムに依存しています！

緩和されたセマンティクス

最後に、3番目のタイプのアトミック操作モデルは緩和されたセマンティクスであり、これはすべてのアトミックプリミティブ（ロード、ストア、すべてのRMW）に適用可能であり、 ほとんど制限を課さないため、プロセッサーはほぼ完全に並べ替えることができ、そのフルパワーを発揮します。 なぜほとんど？
まず、標準の要件は、リラックスした操作の原子性を観察することです。 つまり、リラックスした操作でさえ、部分的な効果を伴わずに分割できないはずです。
第二に、投機的録音はアトミックリラックス録音の標準では禁止されています。
これらの要件は、いくつかの弱く順序付けられたアーキテクチャでのアトミックな緩和操作の実装に制限を課す場合があります。 たとえば、Intel Itaniumのアトミック変数の緩和されたロードは、 load.acqとして実装されload.acq （読み取りを取得しますload.acq取得とC ++の取得を混同しないでください）。

Happens-before, synchronized-with

, C++11, : « , , — happened before, synchronized-with ?»
– .
C++ Concurrency in Action ( ), . .
– () C++, , . C++.
, , memory_order - lock-free . sequential consistency – - memory_order - . , .
– acquire/release relaxed – .

UPD: cheremin . , sequential consistency , — . : lock-free , , — .

lock-free

— relacy . , . , lock-free relacy ( ? – , , , ). , , memory_order -, production- . lock-free , — , . , . ( «» – , , - ) ( ), — , .
, relacy, , ( – relacy ), Intel – , (relacy - ) . . - safe iterators STL.
Google ThreadSanitizer . data race ( ) , , , . , STL, — (Clang 3.2, GCC 4.8 ).
ThreadSanitizer – , — . libcds , , libcds .

« ...» —

, C++11! , , . - :

 template <typename T> class atomic { template <memory_order Order = memory_order_seq_cst> T load() const ; template <memory_order Order = memory_order_seq_cst> void store( T val ) ; template <memory_order SuccessOrder = memory_order_seq_cst> bool compare_exchange_weak( T& expected, T desired ) ; //    }; 

, , .
, , . [] . , , (, , , release- ). . , :

 extern std::memory_order currentOrder ; std::Atomic<unsigned int> atomicInt ; atomicInt.store( 42, currentOrder ) ; 

C++11. , , , :

• , — , ?
• sequential consistent – « ». currentOrder , ,
• switch/case currentOrder . - . , — release- acquire-

. memory_order . , :

 std::Atomic<int> atomicInt ; atomicInt.store<std::memory_order_release>( 42 ) ; //   : atomicInt.template store<std::memory_order_release>( 42 ) ; 

, , «» , — .
C++11 , , — C. std::atomic C++11 C- atomic_load , atomic_store .
, libcds , C++11 , . , - , libcds C++11.

– .

“ ” – lock-free .