32

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.

5 Answers 5

17

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.

7
  • thanks... drat, I wanted to use a byte[] array and it looks like there's no such Atomic animal.... I guess I'll just use synchronized methods and keep it simple.
    – Jason S
    Jul 15, 2009 at 17:24
  • 2
    If you have a lot more reads than writes you might want to look at java.util.concurrent.locks.ReadWriteLock Jul 15, 2009 at 17:32
  • just to make sure I understand: so if the CPU execution order is (1) thread A writes 33 to x[0], (2) thread A sets a "safe flag" saying it's safe to read x[0], (3) thread B reads the "safe flag" saying it's safe to read x[0], (4) thread B reads x[0], there's no guarantee the memory propagation will happen even if I use synchronization on the "safe flag"; I have to use synchronization in a way that includes the read/write of x[0] in the synchronization process?
    – Jason S
    Jul 15, 2009 at 17:41
  • 1
    According to the Memory Consitency Properties (java.sun.com/javase/6/docs/api/java/util/concurrent/…) documentation, if the safe flag is always false until 2, then (1) "happens-before" (2) and (3) "happens-before" (4) because they are in a single thread, and (2) "happens-before" (3) because of synchronization. However, if you are going to use a lock and a boolean for each byte you are better off with an AtomicIntegerArray as you will using about as much space (with less complexity) Jul 15, 2009 at 18:11
  • Another though is to split a large byte array into smaller chunks, but I don't think you will need that many more chunks than you have cores (note: not tested). If a single lock (even a read write lock) on the entire array is too slow you can check this out. Jul 15, 2009 at 18:18
5

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.

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.

2

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
0

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;
}
1
  • 1
    thanks, but not my question & your scenario can't happen (steps 2 and 3 would never occur)
    – Jason S
    Jul 15, 2009 at 17:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.