fast-fail机制

starlin 1,141 2018-05-17

fast-fail机制,就是快速失败机制,它是java集合的一种错误检测机制,当多个线程对集合进行结构上的改变操作时,就有可能产生fast-fail机制(是有可能,而不是一定)

fast-fail示例

public class FailFastTest {
    private static List<Integer> list = new ArrayList<>();

    /**
     * ThreadOne遍历集合
     */
    private static class ThreadOne extends Thread {
        @Override
        public void run() {
            Iterator<Integer> iterator = list.iterator();
            while (iterator.hasNext()) {
                int i = iterator.next();
                System.out.println("ThreadOne遍历: " + i);
                try {
                    sleep(10);
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
            }
        }
    }

    private static class ThreadTwo extends Thread {
        @Override
        public void run() {
            int i = 0;
            while (i < 6) {
                System.out.println("ThreadTwo run: " + i);
                if (i == 3) {
                    list.remove(i);
                }
                i++;
            }
        }
    }

    public static void main(String[] args) {
        for (int i = 0; i < 10; i++) {
            list.add(i);
        }
        new ThreadOne().start();
        new ThreadTwo().start();
    }

}

运行结果:

ThreadOne遍历: 0
ThreadTwo run: 0
ThreadTwo run: 1
ThreadTwo run: 2
ThreadTwo run: 3
ThreadTwo run: 4
ThreadTwo run: 5
Exception in thread "Thread-0" java.util.ConcurrentModificationException
	at java.util.ArrayList$Itr.checkForComodification(ArrayList.java:901)
	at java.util.ArrayList$Itr.next(ArrayList.java:851)

fast-fail产生原因

通过上面的示例,初步知道fast-fail产生的原因就在于程序对Collection进行迭代时,某个线程对Collection结构上做了修改,这是迭代器就会抛出ConcurrentModificationException异常,从而产生fast-fail。

我们来看看ArrayList中迭代器的源码:

    private class Itr implements Iterator<E> {
        int cursor;       // index of next element to return
        int lastRet = -1; // index of last element returned; -1 if no such
        int expectedModCount = modCount;

        public boolean hasNext() {
            return cursor != size;
        }

        @SuppressWarnings("unchecked")
        public E next() {
            checkForComodification();
            int i = cursor;
            if (i >= size)
                throw new NoSuchElementException();
            Object[] elementData = ArrayList.this.elementData;
            if (i >= elementData.length)
                throw new ConcurrentModificationException();
            cursor = i + 1;
            return (E) elementData[lastRet = i];
        }

        public void remove() {
            if (lastRet < 0)
                throw new IllegalStateException();
            checkForComodification();

            try {
                ArrayList.this.remove(lastRet);
                cursor = lastRet;
                lastRet = -1;
                expectedModCount = modCount;
            } catch (IndexOutOfBoundsException ex) {
                throw new ConcurrentModificationException();
            }
        }

        @Override
        @SuppressWarnings("unchecked")
        public void forEachRemaining(Consumer<? super E> consumer) {
            Objects.requireNonNull(consumer);
            final int size = ArrayList.this.size;
            int i = cursor;
            if (i >= size) {
                return;
            }
            final Object[] elementData = ArrayList.this.elementData;
            if (i >= elementData.length) {
                throw new ConcurrentModificationException();
            }
            while (i != size && modCount == expectedModCount) {
                consumer.accept((E) elementData[i++]);
            }
            // update once at end of iteration to reduce heap write traffic
            cursor = i;
            lastRet = i - 1;
            checkForComodification();
        }

        final void checkForComodification() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
        }
    }

从上面的源码中可以看出在next()、remove()方法中都调用的checkForComodification()方法,该方法主要就是校验modCount 和 expectedModCount是否相等,若不相等则抛出ConcurrentModificationException异常,从而产生fast-fail机制。那我们就有必要了解下为什么会判断modCount 和 expectedModCount是否相等,他们的值在什么时候发生了改变。

expectedModCount 是在Itr中定义的:int expectedModCount = ArrayList.this.modCount;所以他的值是不可能会修改的,所以会变的就是modCount。modCount是在AbstractList中定义的全局变量:

protected transient int modCount = 0;

那么它是什么时候发生改变的了,需要看ArrayList·源码:

    public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }

    private void ensureCapacityInternal(int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }

        ensureExplicitCapacity(minCapacity);
    }

    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;//修改了modCount

        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }


    public E remove(int index) {
        rangeCheck(index);

        modCount++;//修改了modCount
        E oldValue = elementData(index);

        int numMoved = size - index - 1;
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        elementData[--size] = null; // clear to let GC do its work

        return oldValue;
    }

    public void clear() {
        modCount++;//修改了modCount

        // clear to let GC do its work
        for (int i = 0; i < size; i++)
            elementData[i] = null;

        size = 0;
    }

从上面的源码可以看出,Arraylist无论是add,remove,clear方法,只是要是涉及到集合元素个数的方法都会导致modCount改变,所以这里可以初步判断由于expectedModCount 得值与modCount的改变不同步,导致两者之间不等从而产生fast-fail机制。 假设有如下场景:

有两个线程(线程A,线程B),其中线程A负责遍历list、线程B修改list。线程A在遍历list过程的某个时候(此时expectedModCount = modCount=N),线程启动,同时线程B增加一个元素,这是modCount的值发生改变(modCount + 1 = N + 1)。线程A继续遍历执行next方法时,通告checkForComodification方法发现expectedModCount = N ,而modCount = N + 1,两者不等,这时就抛出ConcurrentModificationException 异常,从而产生fast-fail机制。

fast-fail解决办法

通过前面的源码分析,应该基本就了解了fast-fail机制,下面有两种解决方案:

  1. 在遍历过程中所有涉及到modCount改动的地方,全部加上synchronized或者直接用Collection.synchronizedList,这样虽然能解决,但是并不好,因为增删造成的同步锁可能会阻塞遍历操作

  2. 使用CopyOnWriteArrayList来替换Arraylist

  3. 尽量使用局部变量,这样根本上解决线程安全问题,同时在注意下同一线程时迭代器过程中不要对list做修改modcount操作即可

CopyOnWriteArrayList

CopyOnWriteArrayList是什么了?ArrayList的一个线程安全体,其中所有可变操作(add,set)都是通过对底层数组进行一次新的复制来实现的。 该类产生的开销比较大,但是在两种情况下,它非常适合使用。1:在不能或不想进行同步遍历,但又需要从并发线程中排除冲突时。2:当遍历操作的数量大大超过可变操作的数量时。遇到这两种情况使用CopyOnWriteArrayList来替代ArrayList再适合不过了。

那么为什么CopyOnWriterArrayList可以替代ArrayList呢?

1、CopyOnWriterArrayList的无论是从数据结构、定义都和ArrayList一样。它和ArrayList一样,同样是实现List接口,底层使用数组实现。在方法上也包含add、remove、clear、iterator等方法。

2、CopyOnWriterArrayList根本就不会产生ConcurrentModificationException异常,也就是它使用迭代器完全不会产生fast-fail机制。

    static final class COWIterator<E> implements ListIterator<E> {
        /** Snapshot of the array */
        private final Object[] snapshot;
        /** Index of element to be returned by subsequent call to next.  */
        private int cursor;

        private COWIterator(Object[] elements, int initialCursor) {
            cursor = initialCursor;
            snapshot = elements;
        }

        public boolean hasNext() {
            return cursor < snapshot.length;
        }

        public boolean hasPrevious() {
            return cursor > 0;
        }

        @SuppressWarnings("unchecked")
        public E next() {
            if (! hasNext())
                throw new NoSuchElementException();
            return (E) snapshot[cursor++];
        }

        @SuppressWarnings("unchecked")
        public E previous() {
            if (! hasPrevious())
                throw new NoSuchElementException();
            return (E) snapshot[--cursor];
        }

        public int nextIndex() {
            return cursor;
        }

        public int previousIndex() {
            return cursor-1;
        }

        /**
         * Not supported. Always throws UnsupportedOperationException.
         * @throws UnsupportedOperationException always; {@code remove}
         *         is not supported by this iterator.
         */
        public void remove() {
            throw new UnsupportedOperationException();
        }

        /**
         * Not supported. Always throws UnsupportedOperationException.
         * @throws UnsupportedOperationException always; {@code set}
         *         is not supported by this iterator.
         */
        public void set(E e) {
            throw new UnsupportedOperationException();
        }

        /**
         * Not supported. Always throws UnsupportedOperationException.
         * @throws UnsupportedOperationException always; {@code add}
         *         is not supported by this iterator.
         */
        public void add(E e) {
            throw new UnsupportedOperationException();
        }

        @Override
        public void forEachRemaining(Consumer<? super E> action) {
            Objects.requireNonNull(action);
            Object[] elements = snapshot;
            final int size = elements.length;
            for (int i = cursor; i < size; i++) {
                @SuppressWarnings("unchecked") E e = (E) elements[i];
                action.accept(e);
            }
            cursor = size;
        }
    }

CopyOnWriterArrayList的方法根本就没有像ArrayList中使用checkForComodification方法来判断expectedModCount 与 modCount 是否相等,我们以add操作来说明:

    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();
        }
    }

与ArrayList最大区别在于下面的代码:

Object[] arrayOfObject2 = Arrays.copyOf(arrayOfObject1, i + 1);  
arrayOfObject2[i] = paramE;  
setArray(arrayOfObject2);  

就是这三句代码使得CopyOnWriterArrayList不会抛ConcurrentModificationException异常。他们所展现的魅力就在于copy原来的array,再在copy数组上进行add操作,这样做就完全不会影响COWIterator中的array了。

所以CopyOnWriterArrayList所代表的核心概念就是:任何对array在结构上有所改变的操作(add、remove、clear等),CopyOnWriterArrayList都会copy现有的数据,再在copy的数据上修改,这样就不会影响COWIterator中的数据了,修改完成之后改变原有数据的引用即可。同时这样造成的代价就是产生大量的对象,同时数组的copy也是相当有损耗的

参考

fast-fail机制

以上,感谢阅读。End!!!


# Java基础