以 CopyOnWriteArrayList 为例,具体来说就是 JUC 包下的线程安全的 List。

回顾 Vector

首先,单步操作的原子性并不保证其所在方法的原子。

举个例子:

Vector<String> vector = new Vector<>();
vector.add("a");
vector.add("b");
vector.add("c");
vector.add("d");
vector.add("e");
vector.add("f");

new Thread(() -> getLast(vector)).start();
new Thread(() -> deleteLast(vector)).start();
new Thread(() -> getLast(vector)).start();
new Thread(() -> deleteLast(vector)).start();

其中的两个方法定义:

// 得到Vector最后一个元素
public static Object getLast(Vector list) {
int lastIndex = list.size() - 1;
System.out.println("list.get(lastIndex) = " + list.get(lastIndex));
return list.get(lastIndex);
}

// 删除Vector最后一个元素
public static void deleteLast(Vector list) {
int lastIndex = list.size() - 1;
System.out.println("remove lastIndex : " + lastIndex);
list.remove(lastIndex);
}

上面可能会出现 ArrayIndexOutOfBoundsException ,因为上面两个静态方法并不原子。 即使你的 get、remove 单步原子(由 sychronized 修饰)。解决方法是给上面两个方法加锁就可以。

下面尝试在遍历 vector 时做清空操作:

    for (String s : vector) {
new Thread(() -> vector.clear()).start();
System.out.println(s);
}
// 在 for i 里执行 vector.clear(),可能出现 ArrayIndexOutOfBoundsException
// 而在 for each 里执行,出现是 ConcurrentModificationException,想想这是为什么。

使用 for i 遍历:

主线程遍历 Vector,执行 vector.size() 时,发现 Vector 的长度为 6。 此时很有可能存在另一个线程对 Vector 进行 clear() 操作 随后主线程执行vector.get(i)时,抛出异常。

使用 for each 迭代器遍历(这是我们推荐的遍历方式),好处就是简洁、数组索引的边界值只计算一次。 此时会抛出并发修改异常。

解决问题的方法仍然是加锁。这就有效率的问题了。

此时我们需要 COW - Copy On Write - 写时拷贝。

无论是Hashtable –> ConcurrentHashMap,还是说 Vector –> CopyOnWriteArrayList, JUC 下支持并发的容器与老一代的线程安全类相比,总结起来就是加锁粒度的问题。

  • Hashtable、Vector 加锁的粒度大(直接在方法声明处使用 synchronized,即锁 this)
  • ConcurrentHashMap、CopyOnWriteArrayList 加锁粒度小(用各种的方式来实现线程安全,比如我们知道 ConcurrentHashMap用了 CAS 锁、volatile 等方式来实现线程安全..)
  • JUC 下的线程安全容器在遍历的时候不会抛出 ConcurrentModificationException 异常

所以一般来说,我们都会使用JUC包下给我们提供的线程安全容器,而不是使用老一代的线程安全容器。

CopyOnWriteArrayList 实现原理

WikiPedia:

如果有多个调用者(callers)同时请求相同资源(如内存或磁盘上的数据存储),他们会共同获取相同的指针指向相同的资源,直到某个调用者试图修改资源的内容时,系统才会真正复制一份专用副本(private copy)给该调用者,而其他调用者所见到的最初的资源仍然保持不变。优点是如果调用者没有修改该资源,就不会有副本(private copy)被建立,因此多个调用者只是 读取 操作时可以共享同一份资源。

底层通过复制数组的方式来实现, 遍历的时候就不用额外加锁.

看看 add 方法:

/**
* Appends the specified element to the end of this list.
*
* @param e element to be appended to this list
* @return {@code true} (as specified by {@link Collection#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); // 将 volatile Object[] array 的指向替换成新数组
return true;
} finally {
lock.unlock(); // 最后释放锁
}
}
  • 在修改时,复制出一个新数组! 修改的操作在新数组中完成,最后将新数组交由array变量指向。
  • 只有写加锁,读不加锁

CopyOnWriteArrayList 在使用迭代器遍历的时候,操作的都是原数组。

  CopyOnWriteArrayList<String> copyOnWriteArrayList = new CopyOnWriteArrayList<>();
copyOnWriteArrayList.add("a");
copyOnWriteArrayList.add("b");
copyOnWriteArrayList.add("c");
copyOnWriteArrayList.add("d");
copyOnWriteArrayList.add(null); // 可以加 null
copyOnWriteArrayList.add("e");

for (String s : copyOnWriteArrayList){
// CopyOnWriteArrayList 在使用迭代器遍历的时候,操作的都是原数组!
new Thread(copyOnWriteArrayList::clear).start();
System.out.println("cow: s = " + s);
}
System.out.println("copyOnWriteArrayList = " + copyOnWriteArrayList);
// 两种情况,要么为空,要么就是未被 clear的 list!

关于并发修改异常,参考快速失效机制:https://www.hollischuang.com/archives/3542

之所以会抛出 ConcurrentModificationException 异常,是因为我们的代码中使用了增强 for 循环,而在增强 for 循环中,集合遍历是通过 iterator 进行的,但是元素的 add/remove 却是直接使用的集合类自己的方法。这就导致 iterator 在遍历的时候,会发现有一个元素在自己不知不觉的情况下就被删除/添加了,就会抛出一个异常,用来提示用户,可能发生了并发修改