无锁数组元素交换

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

- Cheok Yan Cheng

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个），简单的同步（array）{}比复杂的同步更快。

- Vlad Gudim

---

一些处理器支持对两个（或更多）位置进行锁定操作。java.util.concurrent.atomic不公开这些操作。 - Tom Hawtin - tackline

Tom，我的理解是需要在硬件级别支持原子交换操作。虽然可以通过CAS使用微锁定进行交换，但同步需要延伸到交换操作本身之外，因为交换的顺序很重要。 - Vlad Gudim

Answer 2

  // lock-free swap array[i] and array[j] (assumes array contains not null elements only)
  static <T> void swap(AtomicReferenceArray<T> array, int i, int j) {
    while (true) {
      T ai = array.getAndSet(i, null);
      if (ai == null) continue;
      T aj = array.getAndSet(j, null);
      if (aj == null) {
        array.set(i, ai);
        continue;
      }
      array.set(i, aj);
      array.set(j, ai);
      break;
    }
  }

- Alexey Kudravtsev

Answer 3

正如其他人已经指出的那样，你提到的API只能用于设置单个对象的值，而不能用于数组。甚至不能同时用于两个对象，因此你无法进行安全交换。

解决方案取决于你的具体情况。该数组是否可以被另一种数据结构替代？它是否在同时改变大小？

如果必须使用数组，则可以将其更改为包含可更新对象（不是基本类型或Char），并在交换时同步。像这样的数据结构将起作用：

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不行，因为没有用于保留值的隔离结构（或者您无法访问它们）。

- Chuim

Answer 4

你能找到的最接近的是 java.util.concurrent.atomic.AtomicReferenceArray，它提供了基于 CAS 的操作，例如 boolean compareAndSet(int i, E expect, E update)。但它没有 swap(int pos1, int pos2) 操作，所以你需要用两个 compareAndSet 调用来模拟它。

- Robert Munteanu

---

受锁保护，否则在第一次和第二次调用之间可能会发生不好的事情。 - tucuxi

不需要进行锁定，因为我们正在执行的是“compareAndSet”而不是“set”。尽管逻辑可能会变得复杂。 - Robert Munteanu

@RobertMunteanu - 我不确定这个踩票是为了什么，但我也投了我的票。我对Java相对较新，而AtomicReferenceArray是一个非常有用的类。所以 - 谢谢你！ - Neil C. Obremski

Answer 5

在并发应用程序中，可伸缩性最大的威胁是独占资源锁。——《Java并发编程实践》。

我认为你需要一个锁，但正如其他人所提到的，该锁可以比目前更细粒度。

您可以使用锁条纹化，例如java.util.concurrent.ConcurrentHashMap。

- parkr

Answer 6

我认为AtomicReferenceFieldUpdater并不适用于数组访问，即使它适用，它也只能提供一次一个引用的原子保证。据我所知，java.util.concurrent.atomic中的所有类都只提供对一个引用的原子访问。为了将两个或更多引用作为一个原子操作更改，必须使用某种形式的锁定。

- Avi