fail-fast mechanism

In JDK Collection we often see words similar to this:

For example, ArrayList:

注意，迭代器的快速失败行为无法得到保证，因为一般来说，不可能对是否出现不同步并发修改做出任何硬性保证。快速失败迭代器会尽
最大努力抛出 ConcurrentModificationException。因此，为提高这类迭代器的正确性而编写一个依赖于此异常的程序是错误的做法：迭
代器的快速失败行为应该仅用于检测 bug。

HashMap:

注意，迭代器的快速失败行为不能得到保证，一般来说，存在非同步的并发修改时，不可能作出任何坚决的保证。快速失败迭代器尽最大
努力抛出 ConcurrentModificationException。因此，编写依赖于此异常的程序的做法是错误的，正确做法是：迭代器的快速失败行为应
该仅用于检测程序错误。

repeatedly mentioned "fail fast" in these two paragraphs. So what is the "fail fast" mechanism?

"Fast failure" is fail-fast, which is an error detection mechanism for Java collections. When multiple threads perform structural changes to the collection, a fail-fast mechanism may occur. Remember it's possible, not certain. For example: Suppose there are two threads (Thread 1, Thread 2). Thread 1 is traversing the elements in set A through Iterator. At some point, thread 2 modifies the structure of set A (it is a modification of the structure, not a simple Modify the content of the collection element), then the program will throw a ConcurrentModificationException exception at this time, resulting in a fail-fast mechanism.

1. Example of fail-fast

public class FailFastTest {
    private static List<Integer> list = new ArrayList<>();
 
    /**
     * @desc:线程one迭代list
     * @Project:test
     * @file:FailFastTest.java
     * @Authro:chenssy
     * @data:2014年7月26日
     */
    private static class threadOne extends Thread{
        public void run() {
            Iterator<Integer> iterator = list.iterator();
            while(iterator.hasNext()){
                int i = iterator.next();
                System.out.println("ThreadOne 遍历:" + i);
                try {
                    Thread.sleep(10);
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
            }
        }
    }
 
    /**
     * @desc:当i == 3时，修改list
     * @Project:test
     * @file:FailFastTest.java
     * @Authro:chenssy
     * @data:2014年7月26日
     */
    private static class threadTwo extends Thread{
        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();
    }
}

Run result:

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(Unknown Source)
    at java.util.ArrayList$Itr.next(Unknown Source)
    at test.ArrayListTest$threadOne.run(ArrayListTest.java:23

2. Cause of fail-fast

Through the above examples and explanations, I initially know that the reason for fail-fast is that when the program iterates the collection, a thread makes structural modifications to the collection. At this time, the iterator ConcurrentModificationException exception information will be thrown, resulting in fail-fast.

To understand the fail-fast mechanism, we must first understand the ConcurrentModificationException exception. This exception is thrown when a method detects concurrent modification of an object but does not allow such modification. At the same time, it should be noted that this exception will not always indicate that the object has been modified concurrently by different threads. If a single thread violates the rules, it may also throw an exception.

It is true that the fail-fast behavior of iterators cannot be guaranteed, and it does not guarantee that this error will occur, but the fail-fast operation will do its best to throw a ConcurrentModificationException exception, so in order to improve the accuracy of such operations It is a mistake to write a program that relies on this exception. The correct approach is: ConcurrentModificationException should only be used to detect bugs. Below I will use ArrayList as an example to further analyze the reasons for fail-fast.

We know from the front that fail-fast is generated when operating iterators. Now let's take a look at the source code of the iterator in ArrayList:

private class Itr implements Iterator<E> {
        int cursor;
        int lastRet = -1;
        int expectedModCount = ArrayList.this.modCount;
 
        public boolean hasNext() {
            return (this.cursor != ArrayList.this.size);
        }
 
        public E next() {
            checkForComodification();
            /** 省略此处代码 */
        }
 
        public void remove() {
            if (this.lastRet < 0)
                throw new IllegalStateException();
            checkForComodification();
            /** 省略此处代码 */
        }
 
        final void checkForComodification() {
            if (ArrayList.this.modCount == this.expectedModCount)
                return;
            throw new ConcurrentModificationException();
        }
    }

From the above source code we can see that the iterator always calls the checkForComodification() method when calling the next() and remove() methods. , this method is mainly to detect modCount == expectedModCount? If not, a ConcurrentModificationException exception will be thrown, thus generating a fail-fast mechanism. So to figure out why the fail-fast mechanism occurs, we must figure out why modCount != expectedModCount and when their values ​​changed.

expectedModCount is defined in Itr: int expectedModCount = ArrayList.this.modCount; so its value cannot be modified, so what will change is modCount. modCount is defined in AbstractList and is a global variable:

 protected transient int modCount = 0;

So when does it change and for what reason? Please look at the source code of ArrayList:

public boolean add(E paramE) {
    ensureCapacityInternal(this.size + 1);
    /** 省略此处代码 */
}

private void ensureCapacityInternal(int paramInt) {
    if (this.elementData == EMPTY_ELEMENTDATA)
        paramInt = Math.max(10, paramInt);
    ensureExplicitCapacity(paramInt);
}

private void ensureExplicitCapacity(int paramInt) {
    this.modCount += 1;    //修改modCount
    /** 省略此处代码 */
}

public boolean remove(Object paramObject) {
    int i;
    if (paramObject == null)
        for (i = 0; i < this.size; ++i) {
            if (this.elementData[i] != null)
                continue;
            fastRemove(i);
            return true;
        }
    else
        for (i = 0; i < this.size; ++i) {
            if (!(paramObject.equals(this.elementData[i])))
                continue;
            fastRemove(i);
            return true;
        }
    return false;
}

private void fastRemove(int paramInt) {
    this.modCount += 1;   //修改modCount
    /** 省略此处代码 */
}

public void clear() {
    this.modCount += 1;    //修改modCount
    /** 省略此处代码 */
}

From the above source code, we can see that regardless of the add, remove, or clear methods in ArrayList, as long as they involve changing the number of ArrayList elements, modCount will change. So here we can preliminarily judge that the expectedModCount value and the change of modCount are out of sync, resulting in an inequality between the two, resulting in a fail-fast mechanism. Knowing the root cause of fail-fast, we can have the following scenario:

There are two threads (thread A, thread B), among which thread A is responsible for traversing the list and thread B modifies the list. At some point while thread A is traversing the list (at this time expectedModCount = modCount=N), the thread starts, and at the same time thread B adds an element, which means the value of modCount changes (modCount 1 = N 1). When thread A continues to traverse and execute the next method, it notifies the checkForComodification method that expectedModCount = N and modCount = N 1, which are not equal to each other. At this time, a ConcurrentModificationException exception is thrown, resulting in a fail-fast mechanism.

So, up to this point we have fully understood the root cause of fail-fast. Once you know the reason, it's easier to find a solution.

3. Fail-fast solution

Through the previous examples and source code analysis, I think you have basically understood the mechanism of fail-fast. Below I will generate reasons and solutions. There are two solutions here:

Solution 1: During the traversal process, add synchronized to all places that involve changing the modCount value or use Collections.synchronizedList directly, which can solve the problem. However, it is not recommended because synchronization locks caused by additions and deletions may block traversal operations.

Option 2: Use CopyOnWriteArrayList to replace ArrayList. This solution is recommended.

The above is the detailed content of fail-fast mechanism. For more information, please follow other related articles on the PHP Chinese website!