問題タブ [lockless]

x64でのメモリの順序付けに関する Intel のドキュメントを読みました: http://www.multicoreinfo.com/research/papers/2008/damp08-intel64.pdf 。注文。しかし、障壁によって引き起こされる可視性については何もありません。バリアが原因で、他のプロセッサが変数の更新をすぐに確認できるようになるのでしょうか?それとも、更新が指定された順序でのみ、指定された時間ではなく他のプロセッサに伝播されるのでしょうか?

例えば

スレッド 1:

スレッド 2:

スレッド 1 がスレッド 2 の前にそのコードを実行する場合、スレッド 2 は常に flag=true になりますか?

マルチスレッド検索アルゴリズムのロックレスハッシュテーブルでの次の試みを検討してください（この論文に触発されました）

HashEntry構造体は、構造体の 2 つの 64 ビット ワードの XOR 演算された組み合わせを格納するという考え方ですData。2 つのスレッドが struct の 2 つの 64 ビット ワードへの読み取り/書き込みをインターリーブした場合HashEntry、これは読み取りスレッドによって XOR を再度実行し、元の と比較することによって検出できるという考えですkey。そのため、壊れたハッシュ エントリによって効率が低下する可能性がありますが、デコードされた取得キーが元のキーと一致する場合は、正確性が保証されます。

この論文は、それが次の仮定に基づいていると述べています。

この説明の残りの部分では、64 ビット メモリの読み取り/書き込み操作はアトミックである、つまり 64 ビット値全体が 1 サイクルで読み取り/書き込みされると仮定します。

私の質問は次のとおりです。上記のコードはstd::atomic<uint64_t>、C++ 11 でスレッドセーフであることが保証されていることを明示的に使用していませんか? または、同時読み取り/書き込みによって個々の 64 ビット ワードが破損する可能性はありますか? 64 ビット プラットフォームでも？これは古い C++98 標準とどう違うのでしょうか?

規格からの引用は大歓迎です。

更新: 「無害な」データ競合に関する Hans Boehmによるこの驚くべき論文に基づいて、噛まれる簡単な方法は、コンパイラが両方の XOR をキャンセルinsert_data() しdata_is_present()て常に返すことtrueです。たとえば、次のようなローカル コード フラグメントが見つかった場合

Interlocked.Exchangeの正しい使用法を理解しようとしているので、追加および削除機能を備えた単純なソート済みLinkedListを実装しています。

これがスレッドセーフリストではなかった場合、明らかに挿入ポイントを見つけるには、次のようなものを使用して、挿入する正しいポイントを見つけてから、新しいノードを見つける必要があります。

以下は、同時リストに対してこれを行う必要がある方法についての私の見解です。Interlocked.Exchangeが多すぎますか？これがなくても、インサートはスレッドセーフですか？数百または数千のインターロック操作がパフォーマンスの低下を引き起こしますか？

たとえば、curr = curr.nextはアトミック読み取りであることを理解していますが、特定のスレッドがインターロックなしでcurr.nextの最新の値を読み取ることを確認できますか？

Goのバッファリングされたチャネルは、基本的にスレッドセーフなFIFOキューです。（Goのバッファリングされたチャネルをスレッドセーフキューとして使用することは可能ですか？を参照してください。 ）

どのように実装されているのだろうか。「複数の読み取りまたは書き込みスレッド用のロックレスキューなどはありますか？」で説明されているように、ロックフリーですか？？

Goのsrcディレクトリ（grep -r Lock .|grep chan）でgrepを実行すると、次の出力が得られます。

ただし、私のマシン（MacOS、Intel x86_64）をロックすることはありません。これを検証するための公式リソースはありますか？

ソース アーキテクチャとターゲット アーキテクチャが異なると仮定すると、エミュレータはメモリ バリアをどのように効率的に変換するのでしょうか? 一般に、最新のエミュレーターは JIT を使用してソースISAからターゲット ISA に変換することを知っていますが、どのコードが複数のプログラム カウンターによって到達可能であり、どのコードが到達可能でないかを知り、どの命令を並べ替えても安全かを知ることは非常に難しいと思われます。 （ISAの違いにより、JITが効率的なものを生成するために必要になる可能性があります）、そうではないものは非常にトリッキーに思えます。

命令ストリームで明示的なメモリ バリアを見つけることさえ保証されていません。たとえば、x86 の多くの人々は、整列されたワード書き込みがアトミックであることを信頼しています。エミュレーターは保守的に、整列されたすべてのワード書き込みを並べ替えることができないと想定していますか? これは潜在的に巨大なオーバーヘッドのように思われるため、この種の問題に取り組むための既知の分析があるかどうか疑問に思います。

スタックの高度な同時待機なしの実装を使用する必要があるという問題があります。事前にすべてのメモリ（ガベージコレクションやmallocなし）を事前に割り当てる必要があり、スタックのサイズが制限されていることは許容されます（スタックがいっぱいの場合、プッシュはfalseを返す可能性があります）。

私はNirShavitのスタック実装に精通しています：http ：//citeseerx.ist.psu.edu/viewdoc/summary？doi = 10.1.1.156.8728 ...しかし、それはリンクリストとガベージコレクションに依存しています。配列ベースのものが必要です。

ここにACMがあるようです：http ：//dl.acm.org/citation.cfm？id = 1532611ダウンロード率と引用数が少ないことに懐疑的ですが、

理想的な答えは、参照コード（C / C ++）です。単純に盗むことができます:-)

Compare And Swapプログラミングの長所と短所をまとめてくれる人はいますか? (例: マルチコア CPU のパフォーマンス)

Java での例を次に示します。

===編集===

これについては、特にシングル/コア CPU で話してください。

ノード N のツリー T があります。T は、監視しているプログラムによって行われたすべてのメモリ割り当てと割り当て解除の記録を表します。GUI は「count」と「bytes」をチェックします

監視スレッドはツリー マネージャーにスタック トレースのバッチを渡し、ツリー マネージャー (スタックが割り当てとしてラベル付けされている場合) を通過し、スタック トレース内のメソッドごとにツリー上にノードを作成します (ラベル付けされていない場合)。既に存在します)、system32.dll までずっと。これは正常に動作します。

これが完了したら、ツリーを並行して更新しようとしています（機能していません）：

すべてのバッチで、すべてのリーフ ノードに対して、割り当て解除よりも多くの割り当てイベントが発生することが保証されています。しかし、どういうわけか、バッチを処理した後、一部のノードで負のカウントおよび/または負のバイトが発生することがあります。 上記の何かが間違っていますか？

ノート：

更新にはヒステリシスがないため、ロックとミューテックスを避けています。すべてのデータが正しく入力される限り、各バッチの最後に数値が正しくなるはずです。

編集：

受信データにエラーがあったことがわかりました。