java array thread-safety

Question

Are there any concurrency problems with one thread reading from one index of an array, while another thread writes to another index of the array, as long as the indices are different?

e.g. (this example not necessarily recommended for real use, only to illustrate my point)

 class Test1
 {
     static final private int N = 4096;
     final private int[] x = new int[N];
     final private AtomicInteger nwritten = new AtomicInteger(0);
     // invariant: 
     // all values x[i] where 0 <= i < nwritten.get() are immutable

     // read() is not synchronized since we want it to be fast
     int read(int index) {
         if (index >= nwritten.get())
             throw new IllegalArgumentException();
         return x[index];
     }
     // write() is synchronized to handle multiple writers
     // (using compare-and-set techniques to avoid blocking algorithms
     // is nontrivial)
     synchronized void write(int x_i) {
         int index = nwriting.get();
         if (index >= N)
             throw SomeExceptionThatIndicatesArrayIsFull();
         x[index] = x_i;
         // from this point forward, x[index] is fixed in stone
         nwriting.set(index+1);
     }     
 }

edit: critiquing this example is not my question, I literally just want to know if array access to one index, concurrently to access of another index, poses concurrency problems, couldn't think of a simple example.

Answer 1

The example has a lot of stuff that differs from the prose question.

The answer to that question is that distinct elements of an array are accessed independently, so you don't need synchronization if two threads change different elements.

However, the Java memory model makes no guarantees (that I'm aware of) that a value written by one thread will be visible to another thread, unless you synchronize access.

Depending on what you're really trying to accomplish, it's likely that java.util.concurrent already has a class that will do it for you. And if it doesn't, I still recommend taking a look at the source code for ConcurrentHashMap, since your code appears to be doing the same thing that it does to manage the hash table.

Answer 2

I am not really sure if synchronizing only the write method, while leaving the read method unsychronized would work. Not really what are all the consequences, but at least it might lead to read method returning some values that has just been overriden by write.

Answer 3

Yes, as bad cache interleaving can still happen in a multi-cpu/core environment. There are several options to avoid it:

• Use the Unsafe Sun-private library to atomically set an element in an array (or the jsr166y added feature in Java7
• Use AtomicXYZ[] array
• Use custom object with one volatile field and have an array of that object.
• Use the ParallelArray of jsr166y addendum instead in your algorithm

Answer 4

Since read() is not synchronized you could have the following scenario:

Thread A enters write() method
Thread A writes to nwriting = 0;
Thread B reads from nwriting =0;
Thread A increments nwriting. nwriting=1
Thread A exits write();

Since you want to guarantee that your variable addresses never conflict, what about something like (discounting array index issues):

int i;
synchronized int curr(){ return i; }
synchronized int next(){ return ++i;}

int read( ) {
         return values[curr()];
     }

void write(int x){
   values[next()]=x;
}

Answer 5

While you will not get an invalid state by changing arrays as you mention, you will have the same problem that happens when two threads are viewing a non volatile integer without synchronization (see the section in the Java Tutorial on Memory Consistency Errors). Basically, the problem is that Thread 1 may write a value in space i, but there is no guarantee when (or if) Thread 2 will see the change.

The class java.util.concurrent.atomic.AtomicIntegerArray does what you want to do.