并发容器之写时拷贝的 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 条评论
登录 后参与评论

相关文章

来自专栏魂祭心

原 What Every Dev need

2748
来自专栏编程之旅

数据结构——队列

我们在使用手机的时候,偶尔都会碰到过卡住的时候,比如一个地方怎么点都没有用,屏幕也卡住不显示其他东西,但当你把卡住的App关闭掉之后,手机的操作显示就又恢复正常...

1131
来自专栏Jimoer

Java设计模式学习记录-组合模式

今天要介绍的设计模式是组合模式,组合模式也是结构型设计模式的一种,它主要体现了整体与部分的诶关系,其典型的应用就是树形结构。组合是一组对象,其中的对象可能包含一...

1043
来自专栏java一日一条

50个常见的 Java 错误及避免方法(第二部分)

System.out.println("Whatdo you want to do?");

983
来自专栏博客园

Core官方DI剖析(1)--ServiceProvider类和ServiceCollection类

Replace(替换方法) 由新的ServiceDescriptor对象替换ServiceType的第一个ServiceDescriptor对象

2043
来自专栏编码小白

ofbiz实体引擎(四) ModelReader的作用

public class ModelReader implements Serializable { public static final Stri...

2758
来自专栏博客园

Core官方DI剖析(1)--ServiceProvider类和ServiceCollection类

前段时间看了蒋老师的Core文章,对于DI那一块感觉挺有意思,然后就看了一下Core官方DI的源码,这也算是第一个看得懂大部分源码的框架,虽然官方DI相对来说特...

501
来自专栏强仔仔

JavaScript中为空判断

JavaScript和Java不一样的地方是,Java中判断是否为空只要判断是否等于null就可以了,可是在JavaScript中却不能这样,因为还存在在这另外...

1966
来自专栏炸天帮2

tensorflow源码解析之common_runtime-executor-下

在执行器的执行图计算的时候,需要一个结构来保存当前计算的即时信息,TF为此设计了类ExecutorState,它被用来保存每一个对ExecutorImpl::R...

400
来自专栏尾尾部落

[剑指offer] 表示数值的字符串

请实现一个函数用来判断字符串是否表示数值(包括整数和小数)。例如,字符串”+100″,”5e2″,”-123″,”3.1416″和”-1E-16″都表示数值。 ...

932

扫码关注云+社区