How can CopyOnWriteArrayList be thread-safe?

Question

I've taken a look into OpenJDK source code 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?

Solution 1

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.

Solution 2

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.