用Demo验证ArrayList的线程不安全

10月 17 2018 tech

关于线程安全，有这么一段描述：

A class is thread-safe if it behaves correctly when accessed from multiple threads, regardless of the scheduling or interleaving of the execution of those threads by the runtime environment, and with no additional synchronization or other coordination on the part of the calling code.

即在多线程的环境下，无论线程如何被调度，线程间有怎样的交错，程序都能表现出正确的行为。

但仔细研究ArrayList的源码就会发现，它并不满足这一描述。

源码分析

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
    transient Object[] elementData;
  
    private int size;
}

阅读ArrayList的源码可以发现其内部用一个Object数组来保存元素，同时用size来记录元素个数。

然后注意看它的add()方法，这个方法有很多问题：

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

其中ensureCapacityInternal(size + 1)用来判断数组能否再装下一个元素，不够的话就进行扩容。

而第二步的size++并不是一个原子操作，所以实际上这个方法可以被分解为：

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

在多线程下，这样的设计就有可能会发生错误。

数组越界

现在考虑有两个线程同时访问add()方法，并且数组长度是1，但是里面没有元素，即size为0，这时候刚好能装下一个元素。

其中调度顺序如下：

Time	Thread A	Thread B
T1	调用ensureCapacityInternal()，发现不需要扩容
T2	调用elementData[size] = e，将元素放在elementData[0]的位置
T3		调用ensureCapacityInternal()，发现不需要扩容
T4	调用size = size + 1，将size增加到1
T5		调用elementData[size] = e，这时候size已经被增加到1，因此将元素放在elementData[1]的位置。数组越界。

两个线程在检测数组是否需要扩容时，size的值都是0，这时候是不需要扩容的。两者都通过检测后，线程A却将size增加到了1，从而导致了线程B的数组越界。

赋值失败

现在假设数组是空的，即数组长度和size都为0。同样考虑有两个线程同时访问add()方法，调度顺序如下：

Time	Thread A	Thread B
T1	调用ensureCapacityInternal()，扩容
T2	调用elementData[size] = e，将元素放在elementData[0]的位置
T3		调用ensureCapacityInternal()，扩容
T4		调用elementData[size] = e，将元素放在elementData[0]的位置
T5	调用size = size + 1，size被增加到1
T6		调用size = size + 1，size被增加到2

这时候size()的值是2，但是两个元素都被放到了elementData[0]下，而本该存放第二个元素的elementData[1]里面的值却是空。

容量计算错误

ArrayList还有一个获取容量的方法如下：

1
2
3

public int size() {
    return size;
}

不难想象，这个方法也很容易出现错误：

Time	Thread A	Thread B
T1	调用ensureCapacityInternal()
T2	调用elementData[size] = e
T3		调用size()，返回size
T4	调用size = size + 1，size被增加到1

可以看到，线程B在线程A完成size的自增之前就取到了size的值，导致添加进一个元素后取到的容量值还是保持不变。

Demo

public class ArrayListDemo {
    public static void main(String[] args) throws InterruptedException {
        List<Integer> arrayList = new ArrayList<>();

        new Thread(() ->
        {
            for (int j = 0; j < 2500; j++) {
                arrayList.add(j);
            }
        }).start();

        new Thread(() ->
        {
            for (int j = 0; j < 2500; j++) {
                arrayList.add(j);
            }
        }).start();

        // 确保两个线程都运行完毕
        Thread.sleep(3000);

        // 找出赋值失败的案例
        for (int i = 0; i < 5000; i++) {
            if (null == arrayList.get(i)) {
                System.out.println("Error Found!");
            }
        }
    }
}

多运行几次即可看到上述第一种和第二种错误情况同时发生的情况。

输出

Exception in thread "Thread-1" java.lang.ArrayIndexOutOfBoundsException: 2776
	at java.util.ArrayList.add(ArrayList.java:459)
	at ArrayListDemo.lambda$main$1(ArrayListDemo.java:18)
	at java.lang.Thread.run(Thread.java:745)
Exception in thread "main" java.lang.IndexOutOfBoundsException: Index: 2879, Size: 2879
	at java.util.ArrayList.rangeCheck(ArrayList.java:653)
Error Found!
Error Found!
	at java.util.ArrayList.get(ArrayList.java:429)
	at ArrayListDemo.main(ArrayListDemo.java:27)

#concurrency