問題タブ [lock-free]

私は、C++ のロックフリー キューについてかなりグーグルで調べてきました。いくつかのコードといくつかの試行を見つけましたが、コンパイルできたものは何もありませんでした。ロックフリーのハッシュも大歓迎です。

要約：これまでのところ、肯定的な答えはありません。「本番対応」のライブラリはなく、驚くべきことに、既存のライブラリのどれも STL コンテナーの API に準拠していません。

カーネル側でメモリ バリアを設定するのは簡単です。マクロ mb、wmb、rmb などは、Linux カーネル ヘッダーのおかげで常に配置されています。

ユーザー側でこれを達成する方法は？

これは、私が現在維持しているいくつかのコードの簡略化されたバージョンです。

lCurrentIndex は別のスレッドによって定期的に更新されます。質問は; m_CurrentIndex のローカル コピーを作成すると、m_someArray への両方のアクセスで同じインデックスが使用されるようになりますか?

これは単純化された例であることに注意してください。ここに示されている正確なコードではなく、ローカル コピーを作成するという概念について考えています。コンパイラが値をレジスタに入れることはわかっていますが、lCurrentIndex から 2 回読み取るのとは対照的に、それは依然としてローカル コピーです。

ありがとう！

編集: 最初の割り当ては安全です。セットアップでは両方とも 32 ビットであることが保証されています。Edit2:そして、それらは32ビット境界に正しく配置されています(それを忘れていました)

データ構造の同期のコンテキストで、誰かが「ロックレス」と「ノンブロッキング」の違いを明確にできますか? これらの用語は、多くの人が同じ意味で使用しているように見えますが、どこかに隠されている微妙な違いがないかどうかはまだわかりません.

つまり、ロックレスは「ロックなし」であり、ノンブロッキングは進行を保証するようなものです。一方が他方を暗示していると思われますが、その逆ではありません。よくわかりません。

参照歓迎。

Sparc上の64ビットSolarisでは、atomic_cas_64（）関数呼び出しはload-link / condition-storeを使用して実装されていますか？

そうでない場合、Solarisがll/scを利用するためのユーザーモードCコード用のAPIを提供しているとしたらどうでしょうか。

そう; v9 準拠の 64 ビット SPARC CPU では、 cas命令が存在することがわかっています。これは、単一の語長の値に作用します。

casx命令への Web 参照も見ましたが、それ以上のことはわかりません。

私は疑問に思っています-これはダブルワードの比較と交換ですか?

そうでない場合、一般的な質問は次のとおりです。ダブルワードの比較と交換はありますか?

単純なポインターインクリメントアロケーターの場合 (正式な名前はありますか?) ロックフリーのアルゴリズムを探しています。些細なことのように思えますが、私の実装が正しいかどうかについてのフィードバックが欲しいです。

非スレッドセーフ実装:

スレッドセーフな実装での私の試み:

whereCMPXCHGは引数付きの連動比較交換で(destination, exchangeValue, comparand)、元の値を返します

私には良さそうです - 別のスレッドが get-current と cmpxchg の間に割り当てを行うと、ループが再試行されます。コメントはありますか？

Clojure にはロックレスの同時実行性があり、これは重要であると言われています。

私は多くの言語を使用してきましたが、それらが舞台裏でロックを実行していることに気づきませんでした。

Clojure (またはこの機能を持つ言語) でこれが利点になるのはなぜですか?

このトピックについて少しだけ読んだだけですが、唯一の利点は競合の問題を回避することですが、ロックフリーのコードは非常に小さく基本的なものであるため、デッドロックの問題には重要な影響を与えません (fifos、 lifos、hash) で、デッドロックの問題が発生しなかったことを確認しました。

パフォーマンスがすべてです。これでよろしいですか？

概要：

それは私には思われる：

1. 論理状態を表すフィールドを単一の不変の消費可能なオブジェクトにラップする
2. への呼び出しでオブジェクトの正式な参照を更新するInterlocked.CompareExchange<T>
3. 更新の失敗を適切に処理する

は、「ロック」構造を不必要にするだけでなく、並行性に関する特定の現実をかわし、結果として多くの新しい問題を引き起こす真に誤解を招くような構造にする一種の並行性を提供します。

問題のディスカッション:

まず、ロックを使用する際の主な問題を考えてみましょう。

1. ロックはパフォーマンス ヒットを引き起こすため、読み取りと書き込みには同時に使用する必要があります。
2. ロックはスレッドの実行をブロックし、並行性を妨げ、デッドロックのリスクを高めます。

「ロック」に触発されたばかげた動作を考えてみましょう。リソースの論理セットを同時に更新する必要が生じた場合、リソースのセットを「ロック」します。これは、関連付けが緩い専用のロック オブジェクトを介して行います。これは、そうでなければ何の役にも立ちません (赤旗 #1)。

次に、「ロック」パターンを使用して、一連のデータ フィールドで論理的に一貫した状態変更が発生するコードの領域をマークオフしますが、フィールドを同じオブジェクト内の無関係なフィールドと混合することで自分自身を撃ちます。それらをすべて可変のままにし、これらのさまざまなフィールドを読み取るときにロックを使用する必要があるコーナー (赤旗 #2) に追い込むことで、一貫性のない状態でそれらをキャッチしないようにします。

明らかに、その設計には深刻な問題があります。ロックオブジェクトの慎重な管理 (ロック順序、ネストされたロック、スレッド間の調整、何かをするのを待っている別のスレッドによって使用中のリソースのブロック/待機など) が必要なため、やや不安定です。コンテキスト。また、デッドロックを回避するのは「難しい」と言う人もいますが、実際には非常に簡単です。あなたのためにレースを走るように頼む予定の人の靴を盗まないでください!

解決：

「ロック」の使用を完全に停止します。 一貫性のある状態またはスキーマを表す、破損しない/不変のオブジェクトにフィールドを適切にロールバックします。おそらく、表示名と内部識別子を相互に変換するための辞書のペアであるか、値と次のオブジェクトへのリンクを含むキューのヘッド ノードである可能性があります。それが何であれ、それを独自のオブジェクトにラップし、一貫性のために封印します。

書き込みまたは更新の失敗を可能性として認識し、それが発生したときにそれを検出し、無期限にブロックするのではなく、すぐに (または後で) 再試行するか、別のことを行うかを状況に応じて決定します。

ブロッキングは、実行する必要があると思われるタスクをキューに入れるための簡単な方法のように思えますが、すべてのスレッドが専用でセルフサービス型であるため、システム全体を危険にさらすリスクを冒してそのようなことを行う余裕があるわけではありません。「ロック」を使用して物事をシリアル化するのが面倒であるだけでなく、書き込みが失敗してはならないふりをしようとすることの副作用として、スレッドをブロック/フリーズするため、スレッドが応答しなくなり、役に立たなくなり、他のすべての責任が放棄されます。自分の責任を果たすために他人を助けることが必要な場合があるという事実を知らずに、自分が以前にやろうとしていたことを達成するのを頑固に待ちます。

独立した自発的なアクションが同時に発生している場合、競合状態は正常ですが、制御されていないイーサネットの衝突とは異なり、プログラマーとして、「システム」(つまり、決定論的なデジタル ハードウェア) とその入力を完全に制御できます。 0 か 1 か?) と出力、およびシステムの状態を格納するメモリであるため、ライブロックは問題にならないはずです。さらに、多数のプロセッサが同時に動作している可能性があるという事実を解決するメモリ バリアを使用したアトミック操作があります。

要約する：

1. 現在の状態オブジェクトを取得し、そのデータを消費して、新しい状態を構築します。
2. 他のアクティブなスレッドがまったく同じことを行っており、あなたを打ち負かす可能性があることを認識してください。ただし、すべてが「現在の」状態を表す信頼できる参照ポイントを観察します。
3. Interlocked.CompareExchange を使用して、作業の基になった状態オブジェクトがまだ最新の状態であるかどうかを同時に確認し、それを新しい状態に置き換えます。それ以外の場合は失敗し (別のスレッドが最初に終了したため)、適切な修正アクションを実行します。

最も重要な部分は、失敗をどのように処理し、馬に戻るかです。これは、私たちがライブロックを避ける場所であり、考えすぎたり、十分なことをしたり、正しいことをしたりしません。ロックは、スタンピードに乗っていても馬から落ちることは決してないという幻想を作り出し、スレッドがそのようなファンタジーの土地で空想にふけっている間、システムの残りの部分はバラバラになり、クラッシュして燃えることができます.

では、CompareExchange と不変の論理状態オブジェクトを使用したロックフリーの実装では、「ロック」コンストラクトが実行できること (より安定した方法で) を達成できないことはありますか?

これはすべて、ロックを集中的に処理した後、私が自分で実現したことですが、別のスレッドで検索した後、ロックフリーのマルチスレッドプログラミングは何かを簡単にしますか? 、何百ものプロセッサを備えた高度に並列なシステムに直面するとき、高度に競合するロックを使用する余裕がない場合、ロックフリープログラミングが非常に重要になるだろうと誰かが述べています。