Lock Free Array Element Swapping

Question

In multi-thread environment, in order to have thread safe array element swapping, we will perform synchronized locking.

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

Is it possible that we can make use of the following API in the above situation, so that we can have a lock free array element swapping? If yes, how?

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

Answer 1

I don't think the AtomicReferenceFieldUpdater is meant for array access, and even if it were, it only provides atomic guarantees on one reference at a time. AFAIK, all the classes in java.util.concurrent.atomic only provide atomic access to one reference at a time. In order to change two or more references as one atomic operation, you must use some kind of locking.

Answer 2

Regardless of API used you won't be able to achieve both thread-safe and lock-free array element swapping in Java.

The element swapping requires multiple read and update operations that need to be performed atomically. To simulate the atomicity you need a lock.

EDIT:

An alternative to lock-free algorithm might be micro-locking: instead of locking the entire array it’s possible to lock only elements that are being swapped.

The value of this approach fully is questionable. That is to say if the algorithm that requires swapping elements can guarantee that different threads are going to work on different parts of the array then no synchronisation required.

In the opposite case, when different threads can actually attempt swapping overlapping elements then thread execution order will matter. For example if one thread tries to swap elements 0 and 1 of the array and the other simultaneously attempts to swap 1 and 2 then the result will depend entirely on the order of execution, for initial {‘a’,’b’,’c’} you can end up either with {‘b’,’c’,’a’} or {‘c’,’a’,’b’}. Hence you’d require a more sophisticated synchronisation.

Here is a quick and dirty class for character arrays that implements micro locking:

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);
    }

}

You’d need to create the SyncCharArray and then pass it to all threads that require swapping:

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);

Hope that makes some sense.

UPDATE:

Some testing demonstrated that unless you have a great number of threads accessing the array simulteniously (100+ on run-of-the-mill hardware) a simple synchronise (array) {} works much faster than the elaborate synchronisation.

Answer 3

The closest you're going to get is java.util.concurrent.atomic.AtomicReferenceArray, which offers CAS-based operations such as boolean compareAndSet(int i, E expect, E update). It does not have a swap(int pos1, int pos2) operation though so you're going to have to emulate it with two compareAndSet calls.

Answer 4

"The principal threat to scalability in concurrent applications is the exclusive resource lock." - Java Concurrency in Practice.

I think you need a lock, but as others mention that lock can be more granular than it is at present.

You can use lock striping like java.util.concurrent.ConcurrentHashMap.

Answer 5

The API you mentioned, as already stated by others, may only be used to set values of a single object, not an array. Nor even for two objects simultaneously, so you wouldn't have a secure swap anyway.

The solution depends on your specific situation. Can the array be replaced by another data structure? Is it also changing in size concurrently?

If you must use an array, it could be changed it to hold updatable objects (not primitive types nor a Char), and synchronize over both being swapped. S data structure like this would work:

public class CharValue {
    public char c;
}

CharValue[] a = new CharValue[N];

Remember to use a deterministic synchronization order for not having a deadlocks (http://en.wikipedia.org/wiki/Deadlock#Circular_wait_prevention)! You could simply follow index ordering to avoid it.

If items should also be added or removed concurrently from the collection, you could use a Map instead, synchronize swaps on the Map.Entry'es and use a synchronized Map implementation. A simple List wouldn't do it because there are no isolated structures for retaining the values (or you don't have access to them).