2013-06-04 15 views
5

はのは、この構造体を見てみましょう:C++ 11アトミック:なぜこのコードは機能しますか?

struct entry { 
    atomic<bool> valid; 
    atomic_flag writing; 
    char payload[128]; 
} 

二つのトレッドAとBを同時にこの構造体をこのように(eentryのインスタンスであるとする)アクセス:

if (e.valid) { 
    // do something with e.payload... 
} else { 
    while (e.writing.test_and_set(std::memory_order_acquire)); 
    if (!e.valid) { 
     // write e.payload one byte at a time 
     // (the payload written by A may be different from the payload written by B) 
     e.valid = true; 
     e.writing.clear(std::memory_order_release); 
    } 
} 

を、私はこのコードが正しいことを推測し、問題はありませんが、なぜそれが機能するのか理解したいと思います。 C++標準(29.3.13)を引用

実装は時間の妥当な量以内原子負荷 原子ストアが見えるようにすべきです。

これを念頭に置いて、スレッドAとBの両方がelseブロックに入るとします。このインターリーブは可能ですか?

  1. 両方ABvalidfalse
  2. Aあるwritingフラグ
  3. Aのロックを回転さ
  4. B開始writingフラグを設定するので、else分岐を入力している(validフラグを読み出しfalse)、ifブロック
  5. Aペイロードを書き込みます
  6. A有効フラグにtrueを書き込みます。明らかに、A再度validを読み取る場合は、読み取りなるtrue
  7. A
  8. B
  9. Bwritingフラグは有効フラグ(false)の失効値を読み取り、ifブロックに入る設定writingフラグをクリア
  10. Bペイロードを書き込む
  11. B書いたフラグ
  12. B上はwritingフラグをクリア

私はこれが不可能であるが、それは「それができない理由?」実際に質問に答えるために来るとき、私はよく分からない願っています回答。ここに私の考えがあります。 読み取りに関連する書き込み前に書かれた

アトミック読み出し - 変更 - 書き込み操作が常に(変更の順で)最後の値 を読んでなければならない。(29.3.12)再び標準からの引用

-modify-writeオペレーション。

atomic_flag::test_and_set()は、29.7.5で説明したアトミックリードモディファイライトです。私はvalidフラグの古い値を読み取ることができません私はすべての副作用が原因と見なければならないので、その後、atomic_flag::test_and_set()以来

は常に「新鮮値」を読み、私はstd::memory_order_acquireメモリ順序でそれを呼んでいる、atomic_flag::clear()コール(std::memory_order_releaseを使用)の前にAで指定します。

は私が修正アム?

明確化。私の全体的な推論(が間違っているか正しくは)は29.3.12に依存しています。私が今まで理解したところでは、atomic_flagを無視すれば、validから古くなったデータを読むことはatomicでも可能です。 atomicは、すべてのスレッドに「常にすぐに見える」という意味ではないようです。あなたが読むことができる最大限の保証はあなたが読んだ値の一貫した順序ですが、あなたは新鮮なものを得る前に古いデータを読むことができます。幸運なことに、atomic_flag::test_and_set()とすべてのexchange操作はこの重要な機能を持っています。常に新鮮なデータを読み込みます。したがって、あなたがwritingフラグ(validだけでなく)で取得/解放する場合にのみ、期待される動作が得られます。私のポイントが正しいかどうか分かりますか?


EDIT:私の元の質問は、質問のコアに比べた場合、あまりにも多くの注目を集め、次の数行が含まれています。私は、すでに与えられている回答との一貫性のためにそれらを残していますが、今質問を読んでいるなら、それらを無視してください。

atomic<bool> ないプレーンなboolというvalid内の任意の点はありますか?さらに、それがatomic<bool>であるべきならば、 が発行しないメモリの最小注文制約は何ですか? elsevalidインサイド

+0

C++ 11のメモリモデルは、可視性が最終的に発生する限り、順序が十分であるため、「可視性」ではなく「順序付け」の観点から考えます。 (私はあなたが@Grizzlyとの会話の後でこれを理解していると思うが、ここでそれを繰り返す気がする。) – Nemo

答えて

5

waiting上の操作によって課さ取得/解放の意味論により保護されなければなりません。しかし、これはあなたの分析に最初の行(if (e.valid))を含めるのを忘れてしまったため、validをアトミックにする必要性を忘れることはありません。

validatomic<bool>の代わりにboolの場合、このアクセスは完全に保護されません。したがって、​​が完全に書かれ/表示される前に、validの変更が他のスレッドに見えるようになる可能性があります。これは、スレッドBe.validtrueと評価し、​​がまだ完全に書かれていない間にdo something with e.payloadブランチと入力することを意味します。

それ以外の分析はやや妥当と思われますが、完全に正しいとは限りません。メモリの順序付けで覚えておくべきことは、獲得と解放のセマンティクスがペアになることです。リリース・オペレーションの前に書かれたすべてのものは、同じveriableの取得操作が変更された値を読み取った後、安全に読み取ることができます。これを念頭に置いて、waiting.clear(...)のリリースのセマンティクスでは、writing.test_and_set(...)のループが終了するときに、validへの書き込みが表示されている必要があります。後では、セマンティクスを取得して待機の変更(the write done in waiting.clear(...) `)変更が表示される前にt exitを表示します。

§29.3.12について:コードの正確さには関係しますが、古くなった文章とは関係ありません。validフラグ。クリアの前にフラグを設定することはできません。したがって、アクイジションリリースのセマンティクスは、そこでの正確さを保証します。有効がfalseであるため

  • Aが
  • Bは、書き込み用の古い値を見て書き込みフラグを設定し、

    1. どちらもAとB、他の枝を入力します。§29.3.12次のシナリオからあなたを守りますまた、それがAとBの両方が(偽)有効フラグを読み、もしブロックを入力し、
    を競合状態を作成ペイロードを書き込む
  • 設定します

    編集:最小発注制約のために、店舗の荷物とリリースを取得して仕事をするべきですが、ターゲットハードウェアに応じて順次整合性を保つこともできます。これらのセマンティクスの違いについては、hereを参照してください。

  • +0

    +1オクラホマ、なぜ私は間違いなく原子が有効であるべきかを見ています(実際にはこう書いています)。私はまだあなたが「これまで」と答える両方のことが最後の数行に集中していることは、かなり面白いと思う。実際には、このコード全体がatomic_flag(そしてすべての例外操作のほかにも)の機能のおかげでかなり面白いと感じました:彼らは "新鮮な"値を見ることを強制する唯一のものです – gd1

    +0

    @ gd1:何が欠けていますあなたの意見で答えから?私があなたの記事の最後の数行にない唯一の質問は、「このインターリーブは可能ですか?」です。あなたの分析が大丈夫だと言うと、それに対する答えはかなり明確です。しかし、私は "あまり知られていないatomic_flagの特徴"についてのあなたのコメントを理解していません。取得/解放のセマンティクスのために、コードは機能するはずです。 – Grizzly

    +0

    私の全体的な推論(間違っているか正しい)は、29.3.12に依存しています。たとえ原子的であっても、「有効」から失効したデータを読み取ることは可能です。原子は「すぐに目に見える」という意味ではないようです。あなたが求めることができる最大の保証は、あなたが読んだものの一貫した順序ですが、新鮮なものを得る前に1ヶ月間古いデータを読み取ることができます。 :)幸運なことに、atomic_flag :: test_and_set()と各交換操作にはこの特別な機能があります。常に新しいデータを読み込みます[29.3.12]。したがって、あなたが「書く」(「有効」だけでなく)で取得/解放する場合にのみ、期待される動作を得ることができます。私のポイントが正しいかどうか分かりますか? – gd1

    1

    validがアトミックでない場合、最初の行のe.validの最初の読み取りとe.validの割り当てが競合します。

    いずれかのスレッドがスピンロックを取得する前に、両方のスレッドがすでに読み取りを完了しているという保証はありません。つまり、ステップ1と6は発注されません。

    +0

    これは質問の最後の数行についてです。残りはどう?それは本当ですか? 29.3.12ゲーム全体が機能するようにする?:) – gd1

    +0

    有効なものがアトミックでないか、または未定義の動作をしている場合、残りは無関係です。 e.validでの操作が原子的である理由は、e.writingにread-modify-wrire操作があるからではありません。 –

    +0

    @Jonatan Wakely:有効な*はアトミックでなければならないという事実に同意しますが、 29.3.12で述べられている「特別な」機能を持つe.writingの読み取り - 変更 - 書き込み操作がなければ、なぜ私のリストのポイント9が不可能なのか分かりません。あなたはさらに精緻化できますか? – gd1

    2

    29.3.12項は、このコードが正しいかどうかとは関係がありません。必要なセクション(the draft version of the standard available online)は、第1.10項「マルチスレッド実行とデータ競合」です。 1.10節では、アトミック操作と、アトミック操作に関する非アトミック操作についての発生前関係を定義しています。

    第1.10節では、非アトミックな操作が2つあり、発生前の関係を特定できない場合、データ競合があると言います。さらに、データ競合のあるプログラムは未定義の振る舞いを持つと宣言している(パラグラフ21)。

    e.validがアトミックでない場合、コードの最初の行とe.valid=trueの間にデータ競合があります。したがって、else句の動作についてのあなたの推論はすべて正しくありません(プログラムには定義された動作がないため、理由はありません)。

    一方、e.validへのすべてのアクセスがアトミック操作e.writingelse句があなたの全体のプログラムだった場合のように)あなたの推論は正しいでしょう。あなたのリストのイベント9は起こり得ませんでした。理由はセクション29.3.12ではありません。セクション1.10では、非アトミック操作ではと表示されます。

    使用しているパターンはdouble checked locking‌​です。 C++ 11以前では、二重チェックロックを移植可能に実装することは不可能でした。 C++ 11では、二重チェックロックを正しく、移植可能にすることができます。あなたがそれを行う方法は、validatomicと宣言することです。

    +1

    しかし、 'valid' *は' atomic'と宣言されています。 – celtschk

    +0

    私は元の質問の最後の数行を書きませんでした。 :)しかし、この答えは* exacly *私が探していたものです。私はセクション1.10、特に1.10.21を読んでいます。実際には「mutexesとmemory_order_cstを使用して、すべてのデータ競合が操作が...単純にインターリーブされているかのように動作するプログラム」は、「データ型がない場合、非アトミック操作は順次一貫しているように見えます」一貫性のある並べ替えは、即時の可視性を意味するものではなく、29.3.12のトピックのようです。 – gd1

    +0

    私は、スタンダードでは、全体的に一貫した注文があると言います。しかし、1)memory_order_seq_cstを使用し、2)あなたがその注文を取得しても、「合理的な時間量」が意味するものであれば、1か月後に新しいデータを得ることができるので、古いデータを見ることができます。第29.3.12項、特に「最後の値を読んでください」という言葉は、atomic_flagの最後の値を読み込み、std :: memory_order_acquireを選択すると、対応するリリースの前に同じatomic_flagに書き込まれています。 – gd1

    1

    ストアへのe.validはリリースが必要で、条件内のロードは取得する必要があります。それ以外の場合、コンパイラ/プロセッサは、ペイロードを書き込む上でe.valid設定を自由に注文することができます。 このようなコードをC/C++ 11のメモリモデルに対して検証するためのオープンソースツールCDSCheckerがあります。

    +0

    興味深いツール、ありがとう – gd1

    関連する問題