public class NotSafeDemo { public static void main(String[] args) { List<String> list = new ArrayList(); for (int i = 0; i < 30; i++) { //多个线程同时对集合进行修改 new Thread(() -> { //向集合中添加内容 list.add(UUID.randomUUID().toString().substring(0, 8)); //从集合中获取内容 System.out.println(list); }, String.valueOf(i)).start(); } } }
运行结果:
运行发生了异常,异常信息是:java.util.ConcurrentModificationException。
如果只有一个线程操作ArrayList,是没有任何问题的。
但是如果多个线程操作 ArrayList,就会报 java.util.ConcurrentModificationException 的(并发修改异常)异常。 ArrayList 在迭代的时候如果同时对其进行修改就会抛出 java.util.ConcurrentModificationException 异常并发修改异常。/** * Appends the specified element to the end of this list. * * @param e element to be appended to this list * @return <tt>true</tt> (as specified by {@link Collection#add}) */ public boolean add(E e) { ensureCapacityInternal(size + 1); // Increments modCount!! 这里会modCount++ elementData[size++] = e; return true; }
可以看到 add() 方法是没有 synchronized,并不能保证线程安全。
在 ArrayList 的内部类 Itr 中这样的一个方法:
final void checkForComodification() { if (modCount != expectedModCount) throw new ConcurrentModificationException(); }
这里判断真正的 modCount 与 期望的 modCount 是否相等,如果不等就会抛出并发修改异常,就是为了防止多个线程对 ArrayList 的操作。
那么如何解决List 类型的线程安全问题呢?
继承结构:
Vector 是矢量队列,它是 JDK1.0 版本添加的类。继承于 AbstractList,实现了 List, RandomAccess, Cloneable 这些接口。 Vector 继承了 AbstractList,实现了 List;所以, 它是一个队列,支持相关的添加、删除、修改、遍历等功能。
Vector 实现了 RandmoAccess 接口,即提供了随机访问功能。RandmoAccess 是 java 中用来被 List 实现,为 List 提供快速访问功能的。在Vector 中,我们即可以通过元素的序号快速获取元素对象;这就是快速随机访问。 Vector 实现了 Cloneable 接口,即实现 clone()函数。它能被克隆。
和 ArrayList 不同, Vector 中的操作是线程安全的。
/** * List集合线程安全案例 */ public class SafeListDemo { public static void main(String[] args) { List<String> list = new Vector<>(); for (int i = 0; i < 30; i++) { //多个线程同时对集合进行修改 new Thread(() -> { //向集合中添加内容 list.add(UUID.randomUUID().toString().substring(0, 8)); //从集合中获取内容 System.out.println(list); }, String.valueOf(i)).start(); } } }
查看 Vector 的 add 方法
/** * Appends the specified element to the end of this Vector. * * @param e element to be appended to this Vector * @return {@code true} (as specified by {@link Collection#add}) * @since 1.2 */ public synchronized boolean add(E e) { modCount++; ensureCapacityHelper(elementCount + 1); elementData[elementCount++] = e; return true; }
add 方法被 synchronized 同步修辞,线程安全!因此没有并发异常。
Collections 提供了方法 synchronizedList 保证 list 是同步线程安全的。
适用于小数据量,保证线程安全。 不仅仅提供了 List 集合了,也提供了其他线程安全集合:
public class SafeListDemo { public static void main(String[] args) { List<String> list = Collections.synchronizedList(new ArrayList<>()); for (int i = 0; i < 30; i++) { //多个线程同时对集合进行修改 new Thread(() -> { //向集合中添加内容 list.add(UUID.randomUUID().toString().substring(0, 8)); //从集合中获取内容 System.out.println(list); }, String.valueOf(i)).start(); } } }
查看方法源码:
/** * Returns a synchronized (thread-safe) list backed by the specified * list. In order to guarantee serial access, it is critical that * <strong>all</strong> access to the backing list is accomplished * through the returned list.<p> * * It is imperative that the user manually synchronize on the returned * list when iterating over it: * <pre> * List list = Collections.synchronizedList(new ArrayList()); * ... * synchronized (list) { * Iterator i = list.iterator(); // Must be in synchronized block * while (i.hasNext()) * foo(i.next()); * } * </pre> * Failure to follow this advice may result in non-deterministic behavior. * * <p>The returned list will be serializable if the specified list is * serializable. * * @param <T> the class of the objects in the list * @param list the list to be "wrapped" in a synchronized list. * @return a synchronized view of the specified list. */ public static <T> List<T> synchronizedList(List<T> list) { return (list instanceof RandomAccess ? new SynchronizedRandomAccessList<>(list) : new SynchronizedList<>(list)); }
可以看到是帮我们创建了一个同步的集合。
以 SynchronizedList 为例:
/** * @serial include */ static class SynchronizedList<E> extends SynchronizedCollection<E> implements List<E> { private static final long serialVersionUID = -7754090372962971524L; final List<E> list; SynchronizedList(List<E> list) { super(list); this.list = list; } SynchronizedList(List<E> list, Object mutex) { super(list, mutex); this.list = list; } public boolean equals(Object o) { if (this == o) return true; synchronized (mutex) {return list.equals(o);} } public int hashCode() { synchronized (mutex) {return list.hashCode();} } public E get(int index) { synchronized (mutex) {return list.get(index);} } public E set(int index, E element) { synchronized (mutex) {return list.set(index, element);} } public void add(int index, E element) { synchronized (mutex) {list.add(index, element);} } public E remove(int index) { synchronized (mutex) {return list.remove(index);} } public int indexOf(Object o) { synchronized (mutex) {return list.indexOf(o);} } public int lastIndexOf(Object o) { synchronized (mutex) {return list.lastIndexOf(o);} } public boolean addAll(int index, Collection<? extends E> c) { synchronized (mutex) {return list.addAll(index, c);} } public ListIterator<E> listIterator() { return list.listIterator(); // Must be manually synched by user } public ListIterator<E> listIterator(int index) { return list.listIterator(index); // Must be manually synched by user } public List<E> subList(int fromIndex, int toIndex) { synchronized (mutex) { return new SynchronizedList<>(list.subList(fromIndex, toIndex), mutex); } } @Override public void replaceAll(UnaryOperator<E> operator) { synchronized (mutex) {list.replaceAll(operator);} } @Override public void sort(Comparator<? super E> c) { synchronized (mutex) {list.sort(c);} } /** * SynchronizedRandomAccessList instances are serialized as * SynchronizedList instances to allow them to be deserialized * in pre-1.4 JREs (which do not have SynchronizedRandomAccessList). * This method inverts the transformation. As a beneficial * side-effect, it also grafts the RandomAccess marker onto * SynchronizedList instances that were serialized in pre-1.4 JREs. * * Note: Unfortunately, SynchronizedRandomAccessList instances * serialized in 1.4.1 and deserialized in 1.4 will become * SynchronizedList instances, as this method was missing in 1.4. */ private Object readResolve() { return (list instanceof RandomAccess ? new SynchronizedRandomAccessList<>(list) : this); } }
这个类中的方法也是通过实现 synchronized 同步锁的方式来实现同步的,效率不高。
首先我们对 CopyOnWriteArrayList 进行学习,其特点如下:
它相当于线程安全的 ArrayList。和 ArrayList 一样,它是个可变数组;但是和ArrayList 不同的时,它具有以下特性:
(1)它最适合于具有以下特征的应用程序: List 大小通常保持很小,只读操作远多于可变操作,需要在遍历期间防止线程间的冲突;
(2)它是线程安全的;
(3)因为通常需要复制整个基础数组,所以可变操作(add()、 set() 和 remove() 等等)的开销很大;
(4)迭代器支持 hasNext(), next()等不可变操作,但不支持可变 remove()等操作;
(5)使用迭代器进行遍历的速度很快,并且不会与其他线程发生冲突。在构造迭代器时,迭代器依赖于不变的数组快照;
public class SafeListDemo { public static void main(String[] args) { List<String> list = new CopyOnWriteArrayList<>(); for (int i = 0; i < 30; i++) { //多个线程同时对集合进行修改 new Thread(() -> { //向集合中添加内容 list.add(UUID.randomUUID().toString().substring(0, 8)); //从集合中获取内容 System.out.println(list); }, String.valueOf(i)).start(); } } }
核心思想:独占锁效率低:采用读写分离思想解决
写线程获取到锁,其他写线程阻塞。
复制思想:
当我们往一个容器添加元素的时候,不直接往当前容器添加,而是先将当前容器进行 Copy,复制出一个新的容器,然后新的容器里添加元素,添加完元素之后,再将原容器的引用指向新的容器。
这时候会抛出来一个新的问题,也就是数据不一致的问题。如果写线程还没来得及写会内存,其他的线程就会读到了脏数据。
这就是 CopyOnWriteArrayList 的思想和原理。
下面从“动态数组” 和“线程安全” 两个方面进一步对CopyOnWriteArrayList 的原理进行说明。
“动态数组” 机制:
(1)它内部有个“volatile 数组”(array)来保持数据。在“添加/修改/删除” 数据时,都会新建一个数组,并将更新后的数据拷贝到新建的数组中,最后再将该
数组赋值给“volatile 数组”, 这就是它叫做 CopyOnWriteArrayList 的原因;
(2)由于它在“添加/修改/删除” 数据时,都会新建数组,所以涉及到修改数据的操作, CopyOnWriteArrayList 效率很低;但是单单只是进行遍历查找的话,效率比较高。
“线程安全” 机制:
(1)通过 volatile 和互斥锁来实现的。
(2)通过“volatile 数组” 来保存数据的。一个线程读取 volatile 数组时,总能看到其它线程对该 volatile 变量最后的写入;就这样,通过 volatile 提供了“读
取到的数据总是最新的” 这个机制的保证。
(3)通过互斥锁来保护数据。在“添加/修改/删除” 数据时,会先“获取互斥锁” ,再修改完毕之后,先将数据更新到“volatile 数组” 中,然后再“释放互斥
锁” ,就达到了保护数据的目的。
(1)不加锁性能提升,出错误;加锁数据一致,性能下降;
(2)CopyOnWriteArrayList 定义:
A thread-safe variant of ArrayList in which all mutative operations (add, set, and so on) are implemented by making a fresh copy of the underlying array.CopyOnWriteArrayList 是 ArrayList 的一种线程安全变体, 其中所有可变操作(add、set等)都是通过生成底层数组的新副本来实现的。 举例:名单签到(边写边读)
(3)CopyOnWrite 理论 看一下 CopyOnWriteArrayList 的 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); return true; } finally { lock.unlock(); } }
分析: CopyOnWrite 容器即写时复制的容器。往一个容器添加元素的时候,不直接往当前容器Object[]添加,而是先将当前容器Object[]进行Copy,复制出一个新的容器Object[] newElements,然后向新的容器Object[] newElements里添加元素。 添加元素后,再将原容器的引用指向新的容器setArray(newElements)。 这样做的好处是可以对 CopyOnWrite 容器进行并发的读,而不需要加锁,因为当前容器不会添加任何元素。 所以CopyOnWrite容器也是一种读写分离的思想,读和写不同的容器。