JUC source code analysis CopyOnWriteList

JUC source code analysis CopyOnWriteList

According to JDK8 source code

Memory consistency effect: a thread inserts (updates and inserts) elements into the List and its previous actions happens-before subsequent access or removal actions of other threads (people say: I only need to insert elements, other threads do Can be accessed and deleted.)

Resources shared by multiple threads: reference to array

    /** The lock protecting all mutators */
    final transient ReentrantLock lock = new ReentrantLock();

    /** The array, accessed only via getArray/setArray. */
    private transient volatile Object[] array;

 

Weak consistency of get operations

    /**
     * {@inheritDoc}
     *
     * @throws IndexOutOfBoundsException {@inheritDoc}
     */
    public E get(int index) {
        return get(getArray(), index);
    }
    
    final Object[] getArray() {
        return array;
    }
    
    private E get(Object[] a, int index) {
        return (E) a[index];
    }

 

The get operation is not synchronized, which may result in an element that was deleted or updated.

The operation of obtaining elements is divided into 2 steps, the first step is to obtain an array. This step is because the volatile variable establishes synchronization, so other threads write to the array during this period is visible. The latest value of array can be read.

The second step is to index the array. If other threads delete this element after the first step and before the second step (that is, modify the array). Then it is invisible. Because the old array is taken. Therefore, a deleted element is read.

This is the weak consistency problem under the get operation

Add element

   public boolean add(E e) {
        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
            Object[] elements = getArray();
            int len = elements.length;
            Object[] newElements = Arrays.copyOf(elements, len + 1);
            newElements[len] = e;
            setArray(newElements);
            return true;
        } finally {
            lock.unlock();
        }
    }

 

Add elements to copy the original array to the new array. Synchronization through locks ensures atomicity and visibility

Modify elements

    public E set(int index, E element) {
        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
            Object[] elements = getArray();
            E oldValue = get(elements, index);

            if (oldValue != element) {
                int len = elements.length;
                Object[] newElements = Arrays.copyOf(elements, len);
                newElements[index] = element;
                setArray(newElements);
            } else {
                //Not quite a no-op; ensures volatile write semantics
                setArray(elements);                                  //1
            }
            return oldValue;
        } finally {
            lock.unlock();
        }
    }
 

Pay attention to the first part of statement here, if the old value is the same as the new value, you can return directly without operation. Need to use setArray (elements) to write volatile to establish a Happens before relationship with subsequent access. Can this be removed here? ? ?

Update: JDK 11 has removed setArray() when the elements are the same. So it can be removed.

Delete element

    public E remove(int index) {
        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
            Object[] elements = getArray();
            int len = elements.length;
            E oldValue = get(elements, index);
            int numMoved = len - index - 1;
            if (numMoved == 0)
                setArray(Arrays.copyOf(elements, len - 1));
            else {
                Object[] newElements = new Object[len - 1];
                System.arraycopy(elements, 0, newElements, 0, index);
                System.arraycopy(elements, index + 1, newElements, index,
                                 numMoved);
                setArray(newElements);
            }
            return oldValue;
        } finally {
            lock.unlock();
        }
    }
 

summary

  1. In order to ensure performance, get the elements in the List without locking. The simple use of volatile to synchronize leads to weak consistency problems (if the element of get is deleted or updated, the reader thread will not know)
  2. Modify the List, such as adding elements, deleting elements, and modifying elements. Because we adopt the copy-on-write strategy, modifying the List consists of obtaining array references, copying the original array to the new array, and writing the new array reference to the array. To ensure atomicity. We must lock up.

Ref

  1. stackoverflow.com/questions/2...