并发容器之写时拷贝的 List 和 Set

对于一个对象来说,我们为了保证它的并发性,通常会选择使用声明式加锁方式交由我们的 Java 虚拟机来完成自动的加锁和释放锁的操作,例如我们的 synchronized。也会选择使用显式锁机制来主动的控制加锁和释放锁的操作,例如我们的 ReentrantLock。但是对于容器这种经常发生读写操作的类型来说,频繁的加锁和释放锁必然是影响性能的,基于此,jdk 中为我们集成了很多适用于不同并发场景下的优秀容器类,本篇以及接下来的几篇文章,我们将学习这些并发容器类的基本使用以及实现原理。本篇的主要内容如下:

  • 同步容器的几种实现及其核心缺陷
  • 并发容器之 CopyOnWriteArrayList
  • 并发容器之 CopyOnWriteArraySet

一、同步容器的几种实现及其核心缺陷

在介绍并发容器之前,我们想先简单介绍下 jdk 中几种常见的同步容器并通过对比同步容器的缺陷来凸显我们并发容器相对于它的优势点。

//返回一个线程安全的 Collection 集合
public static <T> Collection<T> synchronizedCollection(Collection<T> c)

//返回一个线程安全的 List 集合
public static <T> List<T> synchronizedList(List<T> list)

//返回一个线程安全的 Map 集合
public static <K,V> Map<K,V> synchronizedMap(Map<K,V> m)

这三个容器就隶属于我们的同步容器,它们是线程安全的,区别于原生的 List 和 Map 以及 Collection。当然它的线程安全特性的实现也是粗暴的,我们跟进去看看:

public static <T> Collection<T> synchronizedCollection(Collection<T> c) {
    return new SynchronizedCollection<>(c);
}
static class SynchronizedCollection<E> implements Collection<E>, Serializable {

   final Collection<E> c;  // Backing Collection
   final Object mutex;     // Object on which to synchronize

   SynchronizedCollection(Collection<E> c) {
       this.c = Objects.requireNonNull(c);
       mutex = this;    //信号量指向当前容器对象本身
    }

   SynchronizedCollection(Collection<E> c, Object mutex) {
       this.c = Objects.requireNonNull(c);
       this.mutex = Objects.requireNonNull(mutex);
   }

   public int size() {
       synchronized (mutex) {return c.size();}
   }
   public boolean isEmpty() {
       synchronized (mutex) {return c.isEmpty();}
   }
   public boolean contains(Object o) {
       synchronized (mutex) {return c.contains(o);}
   }
   ..........省略其他方法
}

很明显,Collections 给我们返回的同步容器是 Collections 的子类实现,而在该子类的实现中并没有增加额外的任何一个方法,仅仅将父类中所有方法增加 synchronized 关键字修饰。这样,所有想要访问该容器的线程都需要首先获得该 Collections 实例的锁,进而保证了线程安全。那么这么做也不能完全保证容器的线程安全特性,例如在以下的几种情况下,线程的安全特性是得不到保证的:

  • 复合操作
  • 迭代操作

1、复合操作

//自定义一个类
public class CompoundOperations {
    
    private List list;
    
    public CompoundOperations(List list) {
        this.list = Collections.synchronizedList(list);
    }
    
    public void addIfAbsent(Object obj) {
        int size = list.size();
        if(size == 0) {
            list.add(obj);
        }
    }
}

如上,我们定义了一个 CompoundOperations 类,在该类创建时,我们会为其 list 属性注入一个线程安全的同步容器 List 实例。现在模拟多个线程同时访问同一个 CompoundOperations 实例的 addIfAbsent 方法,原先线程安全的 list,现在还安全吗?

线程 A 和线程 B 同时获取到 list 的 size 属性的值,假设都为 0,然后各自都往容器中添加一个元素,原本要求只有在容器为空的时候才能向其中添加元素,在多线程的情况下,该条件显然已经不足以成为限制。虽然我能保证 list 集合的所有操作都是线程安全的,但是我不能保证你对 list 复合操作下的线程依然安全。这就是复合操作下对同步容器线程安全特性的一个冲击。

2、迭代操作

public static void main(String[] args) {
    List<String> list = Collections.synchronizedList(new ArrayList());
    list.add("single");
    list.add("walker");
    list.add("hello");
    Thread thread1 = new Thread() {
        @Override
        public void run() {
            //迭代容器
            for(String value : list) {
                System.out.println(value);
            }
        }
    };
    Thread thread2 = new Thread() {
        @Override
        public void run() {
            //更改容器结构
            try {
                Thread.sleep(10);
            } catch (InterruptedException e) {}
            list.add("world");
        }
    };
        
    thread1.start();
    thread2.start();
}

程序运行输出的结果如下:

这个 ConcurrentModificationException 异常,我们以前的分析 ArrayList 源码的时候也曾经提及过。这是容器迭代的时候由于其他线程将该容器的内部结构更改导致的,也就是说容器在迭代的时候是不允许发生 add,remove 操作的。显然,无论是我们原生的 List 集合或是这里的同步 List 集合都没有解决这样的一个问题。这是另一个对同步容器线程安全特性的冲击。

上述简单的介绍了同步容器的一些简单的实现原理,以及存在一些不足缺陷,下面我们将详细看看 jdk 中都分别有哪些并发容器,各自又都具有怎样的适用场景。

二、并发容器之 CopyOnWriteArrayList

CopyOnWriteArrayList 是一款基于写时拷贝的并发容器,其基本操作和 ArrayList 一样,我们主要来分析下它是如何支持并发操作的。首先看读取操作:

public E get(int index) {
    return get(getArray(), index);
}
private E get(Object[] a, int index) {
    return (E) a[index];
}

和 ArrayList 一样,内部封装了一个 Object 数组,通过索引可以随机访问集合中的元素。但是与 ArrayList 不同的是,ArrayList 中调用 get 方法将直接返回相应的数组元素,而我们的 CopyOnWriteArrayList 拷贝了一份当前数组并调用另一个 get 方法根据传入的数组及索引进行返回。

也就是说,在 CopyOnWriteArrayList 中,所有的读操作都是先拷贝一份当前数组调用另一个方法进行数据的返回。但是所有的写操作都是需要加锁的,CopyOnWriteArrayList 使用显式锁 ReentrantLock 来加锁所有的写操作。例如:

public E set(int index, E element) {
    final ReentrantLock lock = this.lock;
    lock.lock();
    try {
        Object[] elements = getArray();
        E oldValue = get(elements, index);

        if (oldValue != element) {
            int len = elements.length;
            Object[] newElements = Arrays.copyOf(elements, len);
            newElements[index] = element;
            setArray(newElements);
        } else {
            setArray(elements);
        }
        return oldValue;
    } finally {
        lock.unlock();
    }
}

可以看到,写操作虽然是加了锁了,但是进行更新的时候还是基于整个数组进行更新的。写操作之前,先拷贝一份当前数组:

 Object[] elements = getArray();

写操作完成之时,整体上重置原数组:

setArray(newElements);

那么这样看来,多线程之间可以并发的读取,可以并发的写入,并且多线程之间还可以读写并发进行。

对于同步容器不能保证复合操作下的线程安全的情况,CopyOnWriteArrayList 做了一些解决,但并不彻底。例如,它提供了两个原子性的复合操作:

//如果容器为空才添加元素
public boolean addIfAbsent(E e)
//批量添加c中的非重复元素,不存在才添加,返回实际添加的个数
public int addAllAbsent(Collection<? extends E> c)

这两个方法内部是使用的显式锁进行实现的,所以整体上看这两个方法也是线程安全的。

另外需要说的一点就是 CopyOnWriteArrayList 的迭代器,它的迭代器是不支持修改操作的。例如:

public void remove() {
   throw new UnsupportedOperationException();
}

public void set(E e) {
   throw new UnsupportedOperationException();
}

public void add(E e) {
   throw new UnsupportedOperationException();
}

也就是说,在迭代 CopyOnWriteArrayList 的时候,你只能调用他的 next 方法返回下一个元素的值,而不能进行 add ,remove 等操作。和原生的 ArrayList 不同的是,CopyOnWriteArrayList 直接不支持在迭代的时候对容器进行修改,而 ArrayList 本身的迭代器是支持迭代中更改容器结构的,但是前提是你得调用 iterator 中更改的方法对容器结构进行更改,一旦你调用了 ArrayList 中更改容器结构的方法,那么下一次迭代必然报错,这就是两者的区别。

至于我们未提到的写时拷贝的 Set,Set 的内部是基于我们上述的 CopyOnWriteArrayList ,但是区别在于 Set 中的元素要求不可重复,其他的实现基本类似,此处不再赘述。

最后,我们对这种基于写时拷贝思想的容器做一点小结。写时拷贝在每次写操作的时候都需要完全复制一份原数组,并在写操作完成后重置原数组的引用。这种并发容器只有在写操作不是很频繁的场景下才具有更高的效率,一旦写操作过于频繁,那么程序消耗的资源也是急剧上升的。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏牛肉圆粉不加葱

Spark Task 的执行流程① - 分配 tasks 给 executors

等时机把处于等待状态的 tasks 分配给有空闲资源的 executors,那么这个 “把 task 分配给 executor” 的过程具体是怎样的呢?这就是本...

682
来自专栏余林丰

单例模式

单例模式,顾名思义,在程序运行时有且仅有一个实例存在。最常见的一个应用场景就是网站访问量的计数器,试想如果允许创建多个实例,那还怎么计数,这个时候就得创建有且仅...

1805
来自专栏逆向技术

内核开发知识第二讲,编写Kerner 程序中注意的问题.

什么是函数多线程安全. 简单来说就是 ,一个函数在调用过程中.还没有返回的时候.再次被其他线程调用了.但是函数执行的结果是可靠的.就可以了说这个函数是安全的.

843
来自专栏Java Edge

Java并发编程实战系列5之基础构建模块

1 同步容器类 同步容器类包括Vector和HashTable,二者是早期JDK一部分,此外还包括在JDK 1.2中添加的一些功能相似的类,这些的同步封装器类是...

3305
来自专栏Golang语言社区

Go语言中的管道(Channel)总结

管道(Channel)是Go语言中比较重要的部分,经常在Go中的并发中使用。今天尝试对Go语言的管道来做以下总结。总结的形式采用问答式的方法,让答案更有目的性。...

3296
来自专栏Linyb极客之路

并发编程之同步容器类和并发容器类

一、fail-fast机制 快速报错机制(fail-fast)能够防止多个进程同时修改同一个容器的内容。如果在你迭代遍历某个容器的过程中,另一个进程接入其中,...

2699
来自专栏calmound

多线程-互斥变量

第一个 CreateMutex 函数功能:创建互斥量(注意与事件Event的创建函数对比) 函数原型: HANDLE  CreateMutex(   LPSEC...

2424
来自专栏草根专栏

.NET Core 观察者模式 以及 delegate 和 event

一个气象站, 有三个传感器(温度, 湿度, 气压), 有一个WeatherData对象, 它能从气象站获得这三个数据. 还有三种设备, 可以按要求展示气象站的最...

3978
来自专栏三丰SanFeng

Linux同步机制(二) - 条件变量,信号量,文件锁,栅栏

1 条件变量 条件变量是一种同步机制,允许线程挂起,直到共享数据上的某些条件得到满足。 1.1 相关函数  #include <pthread.h>  pth...

23510
来自专栏草根专栏

C# 7.0 观察者模式 以及 delegate 和 event

观察者模式 这里面综合了几本书的资料. 需求 有这么个项目:  ? 需求是这样的: 一个气象站, 有三个传感器(温度, 湿度, 气压), 有一个WeatherD...

3207

扫码关注云+社区