Lock free array element

Question

In a multi-threaded environment, we will synchronize to replace an array element with thread-safe ones.

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

Is it possible that in the above situation we can use the following API so that we can replace the lock element without locking? If so, how?

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

Answer 1

Regardless of which API you are using, you will not be able to achieve both thread-safe and loose attachment of array elements in 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);

, .

UPDATE:

, , , (100+ ), () {} , .

Answer 2

java.util.concurrent.atomic.AtomicReferenceArray, CAS, boolean compareAndSet(int i, E expect, E update). swap(int pos1, int pos2), compareAndSet.

Answer 3

" ". - Java Concurrency .

, , , , , .

, java.util.concurrent.ConcurrentHashMap.

Answer 4

API, , , . , .

. ? ?

, ( , 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 'es . List , ( ).

Answer 5

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

Answer 6

I don't think AtomicReferenceFieldUpdater is designed to access an array, and even if it is, it only provides atomic guarantees one link at a time. AFAIK, all classes in java.util.concurrent.atomic provide only atomic access to one link at a time. To change two or more links as one atomic operation, you must use some kind of lock.