views:

203

answers:

2

I've taken a look into OpenJDK's sources of CopyOnWriteArrayList and it seems that all write operations are protected by the same lock and read operations are not protected at all. As I understand, under JMM all accesses to a variable (both read and write) should be protected by lock or reordering effects may occur.

For example, set(int, E) method contains these lines (under lock):

/* 1 */ int len = elements.length;
/* 2 */ Object[] newElements = Arrays.copyOf(elements, len);
/* 3 */ newElements[index] = element;
/* 4 */ setArray(newElements);

The get(int) method, on the other hand, only does return get(getArray(), index);.

In my understanding of JMM, this means that get may observe the array in an inconsistent state if statements 1-4 are reordered like 1-2(new)-4-2(copyOf)-3.

Do I understand JMM incorrectly or is there any other explanations on why CopyOnWriteArrayList is thread-safe?

+5  A: 

Getting the array reference is an atomic operation. So, readers will either see the old array or the new array - either way the state is consistent. (set(int,E) computes the new array contents before setting the reference, so the array is consistent when the asignment is made.)

The array reference itself is marked as volatile so that readers do not need to use a lock to see changes to the referenced array. (EDIT: Also, volatile guarantees that the assignment is not re-ordered, which would lead to the assignment being done when the array is possibly in an inconsistent state.)

The write lock is required to prevent concurrent modification, which may result the array holding inconsistent data or changes being lost.

mdma
This is not 100% accurate. The atomicity of setting the reference is not enough for guaranteeing consistency, and the Java Memory Model rules address this issue. Out of order writes and re-ordering of instructions may occur, and then a thread can receive a reference pointing to an inconsistent object. This also happens with the double-check-locking pattern (see http://www.ibm.com/developerworks/java/library/j-dcl.html)
Eyal Schneider
It's not the same. reading/writing to a volatile is consisdered a what the JMM terms a 'synchronized action' and defines a barrier on what can be reordered. See http://java.sun.com/docs/books/jls/third_edition/html/memory.html
mdma
@Eyal Schneider: Welcome to 2004 ( see http://www.ibm.com/developerworks/library/j-jtp03304/ ). Read section titled "New guarantees for volatile"
Alexander Pogrebnyak
@mdma: Exactly. But according to your response it looks like the atomicity of reference setting by itself guarantees data integrity.
Eyal Schneider
It's a question of how much detail to put in an answer. But as this has caused confusion for at least one person, I'll update my answer to make this explicit.
mdma
+12  A: 

If you look at the underlying array reference you'll see it's marked as volatile. When a write operation occurs (such as in the above extract) this volatile reference is only updated in the final statement via setArray. Up until this point any read operations will return elements from the old copy of the array.

The important point is that the array update is an atomic operation and hence reads will always see the array in a consistent state.

The advantage of only taking out a lock for write operations is improved throughput for reads: This is because write operations for a CopyOnWriteArrayList can potentially be very slow as they involve copying the entire list.

Adamski
Thank you. I've missed the fact that the array is `volatile`.
Shooshpanchick