C++ 11のロックフリースタックpush（）関数の混乱

Question

私はAnthony WilliamsのC++ Concurrency in Actionを読んでおり、lock_free_stackクラスのプッシュ実装について理解していません。

void push(T const& data) 
{ 
    counted_node_ptr new_node; 
    new_node.ptr=new node(data); 
    new_node.external_count=1; 
    new_node.ptr->next=head.load(std::memory_order_relaxed) 
    while(!head.compare_exchange_weak(new_node.ptr->next,new_node, std::memory_order_release, std::memory_order_relaxed)); 
} 

正確には7.12をリストだから、2つのスレッド（A、B）はプッシュ機能を呼び出す想像してみてください。どちらもループ中に到達しますが、起動しません。だから両方とも同じ値をhead.load(std::memory_order_relaxed)から読んだ。

その後、我々が起こって、次のものを持っている：

1. Bスレッドが
2. Aスレッドがループを開始し、明らかに成功したスタックに新しいノードを追加何らかの理由のためにスワイプます。
3. Bスレッドはトラックに戻り、ループも開始します。

これは私にとっては興味深いところです。 成功した場合には、std::memory_order_relaxedとcompare_exchange_weak(..., std::memory_order_release, ...)での負荷の操作があったため、スレッド間の同期が全くないように見えます。 std::memory_order_relaxed - std::memory_order_releaseで、ではないことを意味します。std::memory_order_acquire - std::memory_order_releaseです。

したがってBスレッドは単に新しいノードをスタックに追加しますが、スタックにノードがなく、この新しいノードにヘッドをリセットしたときの初期状態になります。

私はすべてこのテーマを中心に私の研究をしていたと私は見つけることができる最高のは、この記事でDoes exchange or compare_and_exchange reads last value in modification order?

そこで質問がありました、それは本当ですか？すべてのRMW関数が最後の値を変更順に参照していますか？どんなにstd::memory_orderを使用しても、RMW操作を使用すると、すべてのスレッド（CPUなど）と同期し、アトミック操作に書き込まれる最後の値を呼び出します。

Answer 1

私はこの質問に対する適切な答えを見つけたと思っている人々の調査といくつかの調査の後、私はそれが誰かに助けになることを願っています。

質問は本当ですか？すべてのRMW機能で最後の 値が変更順に表示されますか？

はい、該当します。

は何があってのstd :: memory_order我々はRMW操作を使用している場合、それが呼び出された時に、それは アトミック操作に書き込まれるすべてのスレッド（CPUおよびなど）と同期して、最後の 値を見つけるだろう、使用しません？

はい、強調表示する必要があるものもあります。

RMW操作は、で動作するアトミック変数だけをと同期させます。私たちの場合、それは頭です。ロード

おそらく、RMWがリラックスしたメモリの順序でも同期を行うには、リリース取得のセマンティクスが必要なのかと尋ねたいと思います。

答えはRMWが同期する変数のみで動作するためですが、RMWより前に発生した他の操作は他のスレッドでは見られない可能性があります。

が再びプッシュ機能を見てみましょう：この例では

void push(T const& data) 
{ 
    counted_node_ptr new_node; 
    new_node.ptr=new node(data); 
    new_node.external_count=1; 
    new_node.ptr->next=head.load(std::memory_order_relaxed) 
    while(!head.compare_exchange_weak(new_node.ptr->next,new_node, std::memory_order_release, std::memory_order_relaxed)); 
} 

を、2つのプッシュスレッドを使用した場合には、それらはある程度相互に同期されることはありませんが、それはここでは許可することができます。

compare_exchange_weak が提供するので、両方のスレッドは常に最新のヘッドを表示します。新しいノードは常にスタックの最上部に追加されます。 しかし、このような値を得ようとすれば*(new_node.ptr->next)この行の後にnew_node.ptr->next=head.load(std::memory_order_relaxed)ものが簡単に醜くなる可能性があります。空のポインタは逆参照される可能性があります。 これは、プロセッサが命令の順序を変更でき、スレッド間で同期がないために、2番目のスレッドが初期化されていたにもかかわらず上位ノードへのポインタを参照できるために発生する可能性があります。

これは、release-acquireセマンティックが助けになるところです。それはリリース操作の前に起こったすべての操作が獲得部分に見られることを確実にします！ 本のリスト5.5と5.8をチェックして比較してください。

また、プロセッサの仕組みについてこの記事を読むことをお勧めします。理解を深めるために必要な情報がいくつかあります。 memory barriers