2

私がSetと別のものを持っているとしましょうQueue。チェックインしたいのですが、setそうでcontains(Element)ない場合はチェックインadd(element)しqueueます。2つのステップをアトミックに実行したいと思います。

明らかな方法の1つは、synchronizedブロックまたはLock.lock()/unlock()メソッドを使用することです。スレッドの競合の下で、これらはコンテキストスイッチを引き起こします。これを非ブロッキング方式で実現するための簡単な設計戦略はありますか？いくつかのアトミックコンストラクトを使用している可能性がありますか？

4

4 に答える 4

1

2つの構造を操作しているという理由だけで、自分で指摘したメカニズムを除いて、どのメカニズムにも頼ることはできないと思います。

1つのデータ構造に対する同時/不可分操作（ConcurrentHashMapの「存在しない場合は置く」など）は適切にサポートされていますが、一連の操作では、ロックまたは同期ブロックのいずれかでスタックします。

于 2012-04-17T17:40:36.690 に答える
1

java.util.concurrent.ConcurrentHashMap必要なセマンティクスを取得するために使用できます。それらにputIfAbsentは、アトミック挿入を行う があります。次に、本質的に要素をマップに追加しようとします。それが成功した場合、挿入を実行したスレッドが唯一のものであることがわかり、アイテムを安全にキューに入れることができます。ここでのもう 1 つの重要なポイントは、ConcurrentMap の操作が「前に発生する」セマンティクスを保証することです。

ConcurrentMap<Element,Boolean> set = new ConcurrentHashMap<Element,Boolean>();
Queue<Element> queue = ...;

void maybeAddToQueue(Element e) {
    if (set.putIfAbsent(e, true) == null) {
        queue.offer(e);
    }
}

ここでは、マップの実際の値の型 (ブール値) は重要ではないことに注意してください。

于 2012-04-17T19:01:45.760 に答える
1

競合ケースは関連するケースであるため、「スピンロック」を確認する必要があります。彼らはCPUを手放すのではなく、フラグがすぐに解放されることを期待してフラグをスピンします。

ただし、通常のスピンロックは非常に優れているため、Java では実際のスピンロックが役立つことはほとんどないことに注意してください。誰かが最初に Java でスピンロックを実装したこのブログLockを参照してください。いくつかの修正後 (つまり、テストを正しく行った後)、スピンロックが標準のものと同等であることがわかりました。

于 2012-04-17T18:06:45.130 に答える
1

一部の操作では、「セーフ シーケンス」と呼ばれるものを使用できます。この場合、同時操作は競合することなく重複する可能性があります。たとえば、同じメンバーを同時に追加する 2 つのスレッドが概念的に互いに競合しないため、(理論的には) 同期する必要なくメンバーをセットに追加できる場合があります。

ただし、1 つのオブジェクトをクエリしてから、条件付きで別のオブジェクトを操作するのは、はるかに複雑なシナリオです。 シーケンスがセットをクエリし、条件付きでメンバーをセットとキューに挿入する場合、クエリと最初の挿入は、ストールせずに同期する「比較とスワップ」操作に置き換えることができます (おそらくメモリ アクセス レベルを除く) 。）、最初の操作の成功に基づいてメンバーをキューに挿入でき、キュー挿入自体を同期するだけで済みます。ただし、このシーケンスでは、別のスレッドが挿入に失敗し、キュー内でメンバーが見つからないというシナリオが残ります。

于 2012-04-17T18:06:55.753 に答える