How can CopyOnWriteArrayList be thread safe?

Question

I reviewed the OpenJDK source code 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 it, under JMM, all calls to a variable (both read and write) should be protected by locking or reordering.

For example, the 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, has only return get(getArray(), index); .

In my understanding of JMM, this means that get can observe the array in an inconsistent state if operators 1-4 reorder as 1-2 (new) -4-2 (copyOf) -3.

Do I understand JMM correctly or is there any other explanation why CopyOnWriteArrayList is thread safe?

Answer 1

If you look at the base array reference, you will see it as volatile . When a write operation occurs (for example, in the extraction above), this volatile reference is updated only in the final expression via setArray . Up to this point, any read operations return elements from the old copy of the array.

The important point is that updating the array is an atomic operation , and therefore reading will always see the array in a consistent state.

The advantage of only CopyOnWriteArrayList write operations improves read throughput: this is because write operations for CopyOnWriteArrayList can be very slow because they include copying the entire list.

Answer 2

Getting a reference to an array is an atomic operation. Thus, readers either see the old array or the new array - in any case, the state is consistent. ( set(int,E) computes the new contents of the array before setting the link, so the array is consistent when the assignment is done.)

The reference to the array itself is marked as volatile , so readers do not need to use a lock to view changes in the reference array. (EDIT: In addition, volatile ensures that the assignment will not be reordered, which will lead to the execution of the task when the array may be in an inconsistent state.)

A write lock is required to prevent simultaneous modification, which may cause the array to hold inconsistent data or changes lost.