锁定自由数组元素交换

Question

在多线程环境中,为了进行线程安全的数组元素交换,我们将执行同步锁定.

// 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

Answer 1

无论使用哪种API,您都无法在Java中实现线程安全和无锁数组元素交换.

元素交换需要多个需要以原子方式执行的读取和更新操作.要模拟原子性,你需要锁定.

编辑:

无锁算法的替代方案可能是微锁定:不是锁定整个数组,而是只能锁定正在交换的元素.

这种方法的价值完全值得怀疑.也就是说,如果需要交换元素的算法可以保证不同的线程将在阵列的不同部分上工作,则不需要同步.

在相反的情况下,当不同的线程实际上可以尝试交换重叠元素时,线程执行顺序将很重要.例如,如果一个线程尝试交换数组的元素0和1而另一个线程同时尝试交换1和2,那么结果将完全取决于执行的顺序,对于初始{'a','b','c '}你最终可以使用{'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多个),否则简单的同步(数组){}的工作速度比精心设计的同步要快得多.