3

マルチスレッド環境では、スレッドセーフな配列要素のスワッピングを行うために、同期ロックを実行します。

// a is char array.
synchronized(a) {
    char tmp = a[1];
    a[1] = a[0];
    a[0] = tmp;
}

上記の状況で次の API を使用して、ロックフリーの配列要素のスワッピングを行うことはできますか? はいの場合、どのように？

http://java.sun.com/j2se/1.5.0/docs/api/java/util/concurrent/atomic/AtomicReferenceFieldUpdater.html#compareAndSet%28T,%20V,%20V%29

4

6 に答える 6

5

使用する API に関係なく、Java でスレッドセーフとロックフリーの両方の配列要素のスワッピングを実現することはできません。

要素のスワッピングには、アトミックに実行する必要がある複数の読み取り操作と更新操作が必要です。原子性をシミュレートするには、ロックが必要です。

編集：

ロックフリー アルゴリズムに代わるものとして、マイクロロックがあります。配列全体をロックする代わりに、スワップされている要素だけをロックすることができます。

このアプローチの価値は完全に疑問です。つまり、要素の交換を必要とするアルゴリズムが、異なるスレッドが配列の異なる部分で動作することを保証できる場合、同期は必要ありません。

逆の場合、異なるスレッドが実際に重なり合う要素の交換を試みることができる場合、スレッドの実行順序が重要になります。たとえば、1 つのスレッドが配列の要素 0 と 1 を交換しようとし、もう 1 つのスレッドが同時に 1 と 2 を交換しようとすると、結果は完全に実行順序に依存します。 '} 最終的に {'b','c','a'} または {'c','a','b'} のいずれかになります。したがって、より高度な同期が必要になります。

以下は、マイクロ ロックを実装する文字配列の簡易クラスです。

import java.util.concurrent.atomic.AtomicIntegerArray;

class SyncCharArray {

    final private char array [];
    final private AtomicIntegerArray locktable;

    SyncCharArray (char array[])
    {
      this.array = array;

      // create a lock table the size of the array
      // to track currently locked elements 
      this.locktable = new AtomicIntegerArray(array.length);
      for (int i = 0;i<array.length;i++) unlock(i);

    }

    void swap (int idx1, int idx2)
    {
      // return if the same element
      if (idx1==idx2) return;

      // lock element with the smaller index first to avoid possible deadlock
      lock(Math.min(idx1,idx2));
      lock(Math.max(idx1,idx2));

      char tmp = array[idx1];
      array [idx1] = array[idx2];
      unlock(idx1);
      array[idx2] = tmp;
      unlock(idx2);

    }

    private void lock (int idx)
    {
      // if required element is locked when wait ...
      while (!locktable.compareAndSet(idx,0,1)) Thread.yield();
    }

    private void unlock (int idx)
    {
      locktable.set(idx,0);
    }

}

SyncCharArray を作成し、それをスワッピングが必要なすべてのスレッドに渡す必要があります。

char array [] = {'a','b','c','d','e','f'};
SyncCharArray sca = new SyncCharArray(array);

 // then pass sca to any threads that require swapping
 // then within a thread

sca.swap(15,3);

それが理にかなっていることを願っています。

アップデート：

いくつかのテストでは、多数のスレッドが配列に同時にアクセスする (ありふれたハードウェアで 100 以上) 場合を除き、単純な同期 (配列) {} が複雑な同期よりもはるかに高速に動作することが示されました。

于 2009-08-05T09:53:17.347 に答える
0

あなたが言及したAPIは、他の人がすでに述べたように、配列ではなく単一のオブジェクトの値を設定するためにのみ使用できます。同時に2つのオブジェクトであっても、安全なスワップはありません。

解決策は、特定の状況によって異なります。配列を別のデータ構造に置き換えることはできますか? 同時にサイズも変化していますか？

配列を使用する必要がある場合は、更新可能なオブジェクト (プリミティブ型でも でもないChar) を保持するように配列を変更し、スワップされている両方を同期させることができます。次のような S データ構造が機能します。

public class CharValue {
    public char c;
}

CharValue[] a = new CharValue[N];

デッドロックが発生しないように、決定論的な同期順序を使用することを忘れないでください ( http://en.wikipedia.org/wiki/Deadlock#Circular_wait_prevention )! それを避けるために、単にインデックスの順序に従うことができます。

コレクションからアイテムを同時に追加または削除する必要がある場合は、Map代わりに を使用し、その上でスワップを同期しMap.Entry、同期された Map 実装を使用できます。List値を保持するための分離された構造がないため (またはそれらにアクセスできないため)、単純な人はそれを行いません。

于 2009-08-06T13:25:21.003 に答える
0

「並行アプリケーションのスケーラビリティに対する主な脅威は、排他的なリソース ロックです。」- 実際の Java 同時実行。

ロックが必要だと思いますが、他の人が言うように、ロックは現在よりも細かくすることができます。

java.util.concurrent.ConcurrentHashMap のようなロック ストライピングを使用できます。

于 2009-08-06T09:45:15.283 に答える
0

最も近いのはjava.util.concurrent.atomic.AtomicReferenceArrayで、 などの CAS ベースの操作を提供しますboolean compareAndSet(int i, E expect, E update)。ただし、操作がないため、2 つの呼び出しswap(int pos1, int pos2)でエミュレートする必要があります。compareAndSet

于 2009-08-05T11:12:04.910 に答える
-1

AtomicReferenceFieldUpdater は配列アクセスを意図したものではないと思います。たとえそうであったとしても、一度に 1 つの参照に対してアトミックな保証しか提供しません。私の知る限り、 java.util.concurrent.atomic のすべてのクラスは、一度に 1 つの参照へのアトミック アクセスのみを提供します。2 つ以上の参照を 1 つのアトミック操作として変更するには、何らかのロックを使用する必要があります。

于 2009-08-05T08:50:20.297 に答える