java-并发-并发容器(3)

同样注意内层的第一个for循环,里面有语句int c = segments[i].count; 但是c却从来没有被使用过,即使如此,编译器也不能做优化将这条语句去掉,因为存在对volatile变量count的读取,这条语句存在的唯一目的就是保证segments[i].modCount读取到几乎最新的值。关于containsValue方法的其它部分就不分析了,它和size方法差不多。

跨段方法中还有一个isEmpty()方法,其实现比size()方法还要简单,也不介绍了。最后简单地介绍下迭代方法,如keySet(), values(), entrySet()方法,这些方法都返回相应的迭代器,所有迭代器都继承于Hash_Iterator类(提交时居然提醒我不能包含sh It,只得加了下划线),里实现了主要的方法。其结构是:

abstract class Hash_Iterator{
    int nextSegmentIndex;
    int nextTableIndex;
    HashEntry<K,V>[] currentTable;
    HashEntry<K, V> nextEntry;
    HashEntry<K, V> lastReturned;
}  

nextSegmentIndex是段的索引,nextTableIndex是nextSegmentIndex对应段中中hash链的索引,currentTable是nextSegmentIndex对应段的table。调用next方法时主要是调用了advance方法:

final void advance() {
    if (nextEntry != null && (nextEntry = nextEntry.next) != null)
        return;  

    while (nextTableIndex >= 0) {
        if ( (nextEntry = currentTable[nextTableIndex--]) != null)
            return;
    }  

    while (nextSegmentIndex >= 0) {
        Segment<K,V> seg = segments[nextSegmentIndex--];
        if (seg.count != 0) {
            currentTable = seg.table;
            for (int j = currentTable.length - 1; j >= 0; --j) {
                if ( (nextEntry = currentTable[j]) != null) {
                    nextTableIndex = j - 1;
                    return;
                }
            }
        }
    }
}  

不想再多介绍了,唯一需要注意的是跳到下一个段时,一定要先读取下一个段的count变量。

这种迭代方式的主要效果是不会抛出ConcurrentModificationException。一旦获取到下一个段的table,也就意味着这个段的头结点在迭代过程中就确定了,在迭代过程中就不能反映对这个段节点并发的删除和添加,对于节点的更新是能够反映的,因为节点的值是一个volatile变量。
结束语

ConcurrentHashMap是一个支持高并发的高性能的HashMap实现,它支持完全并发的读以及一定程度并发的写。ConcurrentHashMap的实现也是很精巧,充分利用了最新的JMM规范,值得学习,却不值得模仿。
1.8 的版本,与JDK6的版本有很大的差异。实现线程安全的思想也已经完全变了,它摒弃了Segment(锁段)的概念,而是启用了一种全新的方式实现,利用CAS算法。它沿用了与它同时期的HashMap版本的思想,底层依然由“数组”+链表+红黑树的方式思想,但是为了做到并发,又增加了很多辅助的类,例如TreeBin,Traverser等对象内部类。CAS算法实现无锁化的修改值的操作,他可以大大降低锁代理的性能消耗。这个算法的基本思想就是不断地去比较当前内存中的变量值与你指定的一个变量值是否相等,如果相等,则接受你指定的修改的值,否则拒绝你的操作。因为当前线程中的值已经不是最新的值,你的修改很可能会覆盖掉其他线程修改的结果。这一点与乐观锁,SVN的思想是比较类似的。

List类型的CopyOnWriteArrayList

对应的非并发容器:ArrayList
目标:代替Vector、synchronizedList
原理:利用高并发往往是读多写少的特性,对读操作不加锁,对写操作,先复制一份新的集合,在新的集合上面修改,然后将新集合赋值给旧的引用,并通过volatile 保证其可见性,当然写操作的锁是必不可少的了。
CopyOnWriteArrayList采用写入时复制的方式避开并发问题。这其实是通过冗余和不可变性来解决并发问题,在性能上会有比较大的代价,但如果写入的操作远远小于迭代和读操作,那么性能就差别不大了。
应用它们的场合通常在数组相对较小,并且遍历操作的数量大大超过可变操作的数量时,这种场合应用它们非常好。它们所有可变的操作都是先取得后台数组的副本,对副本进行更改,然后替换副本,这样可以保证永远不会抛出ConcurrentModificationException移除。
CopyOnWriteArrayList容器是Collections.synchronizedList(List list)的替代方案,CopyOnWriteArrayList在某些情况下具有更好的性能,考虑读远大于写的场景,如果把所有的读操作进行加锁,因为只有一个读线程能够获得锁,所以其他的读线程都必须等待,大大影响性能。CopyOnWriteArrayList称为“写时复制”容器,就是在多线程操作容器对象时,把容器复制一份,这样在线程内部的修改就与其他线程无关了,而且这样设计可以做到不阻塞其他的读线程。从JDK1.5开始Java并发包里提供了两个使用CopyOnWrite机制实现的并发容器,它们是CopyOnWriteArrayList和CopyOnWriteArraySet。
CopyOnWriteArrayList源码
先说说CopyOnWriteArrayList容器的实现原理:简单地说,就是在需要对容器进行操作的时候,将容器拷贝一份,对容器的修改等操作都在容器的拷贝中进行,当操作结束,再把容器容器的拷贝指向原来的容器。这样设计的好处是实现了读写分离,并且读读不会发生阻塞。下面的源码是CopyOnWriteArrayList的add方法实现:

public void add(int index, E element) {
        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
            Object[] elements = getArray();
            int len = elements.length;
            if (index > len || index < 0)
                throw new IndexOutOfBoundsException("Index: "+index+
                                                    ", Size: "+len);
            Object[] newElements;
            int numMoved = len - index;
            //1、复制出一个新的数组
            if (numMoved == 0)
                newElements = Arrays.copyOf(elements, len + 1);
            else {
                newElements = new Object[len + 1];
                System.arraycopy(elements, 0, newElements, 0, index);
                System.arraycopy(elements, index, newElements, index + 1,
                                 numMoved);
            }
            //2、把新元素添加到新数组中
            newElements[index] = element;
            //3、把数组指向原来的数组
            setArray(newElements);
        } finally {
            lock.unlock();
        }
    }

上面的三个步骤实现了写时复制的思想,在读数据的时候不会锁住list,因为写操作是在原来容器的拷贝上进行的。而且,可以看到,如果对容器拷贝修改的过程中又有新的读线程进来,那么读到的还是旧的数据。读的代码如下

public E get(int index) {
        return get(getArray(), index);
    }

final Object[] getArray() {
       return array;
   }

CopyOnWrite并发容器用于读多写少的并发场景。比如白名单,黑名单,商品类目的访问和更新场景
从CopyOnWriteArrayList的实现原理可以看到因为在需要容器对象的时候进行拷贝,所以存在两个问题:内存占用问题和数据一致性问题。

内存占用问题

因为需要将原来的对象进行拷贝,这需要一定的开销。特别是当容器对象过大的时候,因为拷贝而占用的内存将增加一倍(原来驻留在内存的对象仍然在使用,拷贝之后就有两份对象在内存中,所以增加了一倍内存)。而且,在高并发的场景下,因为每个线程都拷贝一份对象在内存中,这种情况体现得更明显。由于JVM的优化机制,将会触发频繁的Young GC和Full GC,从而使整个系统的性能下降。

数据一致性问题

CopyOnWriteArrayList不能保证实时一致性,因为读线程在将引用重新指向原来的对象之前再次读到的数据是旧的,所以CopyOnWriteArrayList只能保证最终一致性。因此在需要实时一致性的厂几个CopyOnWriteArrayList是不能使用的
CopyOnWriteArrayList适用于读多写少的场景
在并发操作容器对象时不会抛出ConcurrentModificationException,并且返回的元素与迭代器创建时的元素是一致的
容器对象的复制需要一定的开销,如果对象占用内存过大,可能造成频繁的YoungGC和Full GC
CopyOnWriteArrayList不能保证数据实时一致性,只能保证最终一致性。
CopyOnWriteArrayList容器是Collections.synchronizedList(List list)的替代方案,CopyOnWriteArrayList在某些情况下具有更好的性能,考虑读远大于写的场景,如果把所有的读操作进行加锁,因为只有一个读线程能够获得锁,所以其他的读线程都必须等待,大大影响性能。CopyOnWriteArrayList称为“写时复制”容器,就是在多线程操作容器对象时,把容器复制一份,这样在线程内部的修改就与其他线程无关了,而且这样设计可以做到不阻塞其他的读线程。从JDK1.5开始Java并发包里提供了两个使用CopyOnWrite机制实现的并发容器,它们是CopyOnWriteArrayList和CopyOnWriteArraySet。
CopyOnWriteArrayList容器使用示例

import java.text.DateFormat;
import java.text.SimpleDateFormat;
import java.util.Date;
import java.util.List;
import java.util.concurrent.CopyOnWriteArrayList;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.atomic.AtomicLong;

/**
 * Created by rhwayfun on 16-4-8.
 */
public class CopyOnWriteArrayListDdemo {

    /**
     * 内容编号
     */
    private static AtomicLong contentNum;

    /**
     * 日期格式器
     */
    private static DateFormat format;

    /**
     * 线程池
     */
    private final ExecutorService threadPool;

    public CopyOnWriteArrayListDdemo() {
        contentNum = new AtomicLong();
        format = new SimpleDateFormat("HH:mm:ss");
        threadPool = Executors.newFixedThreadPool(10);
    }

    public void doExec(int num) throws InterruptedException {
        List<String> list = new CopyOnWriteArrayList<>();
        for (int i = 0; i < num; i++){
            list.add(i,"main-content-" + i);
        }
        //5个写线程
        for (int i = 0; i < 5; i++){
            threadPool.execute(new Writer(list,i));
        }
        //启动10个读线程
        for (int i = 0; i < 10; i++){
            threadPool.execute(new Reader(list));
        }
        //关闭线程池
        threadPool.shutdown();
    }

    /**
     * 写线程
     *
     * @author rhwayfun
     */
    static class Writer implements Runnable {

        private final List<String> copyOnWriteArrayList;
        private int i;

        public Writer(List<String> copyOnWriteArrayList,int i) {
            this.copyOnWriteArrayList = copyOnWriteArrayList;
            this.i = i;
        }

        @Override
        public void run() {
            copyOnWriteArrayList.add(i,"content-" + contentNum.incrementAndGet());
            System.out.println(Thread.currentThread().getName() + ": write content-" + contentNum.get()
                    + " " +format.format(new Date()));
            System.out.println(Thread.currentThread().getName() + ": remove " + copyOnWriteArrayList.remove(i));
        }
    }

    static class Reader implements Runnable {

        private final List<String> list;

        public Reader(List<String> list) {
            this.list = list;
        }

        @Override
        public void run() {
            for (String s : list) {
                System.out.println(Thread.currentThread().getName() + ": read " + s
                        + " " +format.format(new Date()));
            }
        }
    }

    public static void main(String[] args) throws InterruptedException {
        CopyOnWriteArrayListDdemo demo = new CopyOnWriteArrayListDdemo();
        demo.doExec(5);
    }
}

首先启动5个写线程,再启动10个读线程,运行该程序发现并没有出现异常,所以使用写时复制容器效率很高。代码的运行结果如下:
先说说CopyOnWriteArrayList容器的实现原理:简单地说,就是在需要对容器进行操作的时候,将容器拷贝一份,对容器的修改等操作都在容器的拷贝中进行,当操作结束,再把容器容器的拷贝指向原来的容器。这样设计的好处是实现了读写分离,并且读读不会发生阻塞。下面的源码是CopyOnWriteArrayList的add方法实现:

public void add(int index, E element) {
        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
            Object[] elements = getArray();
            int len = elements.length;
            if (index > len || index < 0)
                throw new IndexOutOfBoundsException("Index: "+index+
                                                    ", Size: "+len);
            Object[] newElements;
            int numMoved = len - index;
            //1、复制出一个新的数组
            if (numMoved == 0)
                newElements = Arrays.copyOf(elements, len + 1);
            else {
                newElements = new Object[len + 1];
                System.arraycopy(elements, 0, newElements, 0, index);
                System.arraycopy(elements, index, newElements, index + 1,
                                 numMoved);
            }
            //2、把新元素添加到新数组中
            newElements[index] = element;
            //3、把数组指向原来的数组
            setArray(newElements);
        } finally {
            lock.unlock();
        }
    }

上面的三个步骤实现了写时复制的思想,在读数据的时候不会锁住list,因为写操作是在原来容器的拷贝上进行的。而且,可以看到,如果对容器拷贝修改的过程中又有新的读线程进来,那么读到的还是旧的数据。读的代码如下:

public E get(int index) {
        return get(getArray(), index);
    }
    final Object[] getArray() {
        return array;
    }
时间: 2024-10-27 15:54:52

java-并发-并发容器(3)的相关文章

Java 高并发五:JDK并发包1详细介绍_java

在[高并发Java 二] 多线程基础中,我们已经初步提到了基本的线程同步操作.这次要提到的是在并发包中的同步控制工具. 1. 各种同步控制工具的使用 1.1 ReentrantLock ReentrantLock感觉上是synchronized的增强版,synchronized的特点是使用简单,一切交给JVM去处理,但是功能上是比较薄弱的.在JDK1.5之前,ReentrantLock的性能要好于synchronized,由于对JVM进行了优化,现在的JDK版本中,两者性能是不相上下的.如果是简

java 集合并发操作出现的异常ConcurrentModificationException_java

如Java中的容器Map: for(Person person : pList){ if(person.getGender()==Gender.MALE){ pList.remove(person); //不能在遍历期间进行 remove这个操作 } } Map在遍历时候通常 现获得其键值的集合Set,然后用迭代器Iterator来对Map进行遍历. 注意在遍历的过程中,只能对Map中的元素进行相应的处理,不能把Map元素增加或者把Map元素减少,也就是说,不能改变Map的size大小,就会出现

解决Java多线程并发的计数器问题

问题描述 解决Java多线程并发的计数器问题 3C public class Counter { public static int count = 0; public synchronized static void inc() { count++; } public static void main(String[] args) { //同时启动1000个线程,去进行i++计算,看看实际结果 for (int i = 0; i < 1000; i++) { new Thread(new Ru

《Java 7并发编程实战手册》第六章并发集合

由人民邮电出版社出版的<Java 7并发编程实战手册>终于出版了,译者是俞黎敏和申绍勇,该书将于近期上架.之前并发编程网组织翻译过此书,由于邮电出版社在并发网联系他们之前就找到了译者,所以没有采用并发网的译稿,但邮电出版社将于并发网展开合作,发布该书的样章(样章由并发网挑选,你也可以回帖告诉我们你想看哪一章的样章),并组织赠书活动回馈给活跃读者.活动详情请时刻关注并发网的微博和微信(微信号:ifeves),最后祝各位用餐愉快!:) 本章将介绍下列内容: 使用非阻塞式线程安全列表 使用阻塞式线程

Java 高并发十: JDK8对并发的新支持详解_java

1. LongAdder 和AtomicLong类似的使用方式,但是性能比AtomicLong更好. LongAdder与AtomicLong都是使用了原子操作来提高性能.但是LongAdder在AtomicLong的基础上进行了热点分离,热点分离类似于有锁操作中的减小锁粒度,将一个锁分离成若干个锁来提高性能.在无锁中,也可以用类似的方式来增加CAS的成功率,从而提高性能. LongAdder原理图: AtomicLong的实现方式是内部有个value 变量,当多线程并发自增,自减时,均通过CA

Java 高并发九:锁的优化和注意事项详解_java

摘要 本系列基于炼数成金课程,为了更好的学习,做了系列的记录. 本文主要介绍: 1. 锁优化的思路和方法 2. 虚拟机内的锁优化 3. 一个错误使用锁的案例 4. ThreadLocal及其源码分析 1. 锁优化的思路和方法 在[高并发Java 一] 前言中有提到并发的级别. 一旦用到锁,就说明这是阻塞式的,所以在并发度上一般来说都会比无锁的情况低一点. 这里提到的锁优化,是指在阻塞式的情况下,如何让性能不要变得太差.但是再怎么优化,一般来说性能都会比无锁的情况差一点. 这里要注意的是,在[高并

Java 高并发八:NIO和AIO详解_java

IO感觉上和多线程并没有多大关系,但是NIO改变了线程在应用层面使用的方式,也解决了一些实际的困难.而AIO是异步IO和前面的系列也有点关系.在此,为了学习和记录,也写一篇文章来介绍NIO和AIO. 1. 什么是NIO NIO是New I/O的简称,与旧式的基于流的I/O方法相对,从名字看,它表示新的一套Java I/O标 准.它是在Java 1.4中被纳入到JDK中的,并具有以下特性: NIO是基于块(Block)的,它以块为基本单位处理数据 (硬盘上存储的单位也是按Block来存储,这样性能

《Java 7并发编程实战手册》第五章Fork/Join框架

感谢人民邮电大学授权并发网发布此书样章,新书已上市,购买请进当当网 本章内容包含: 创建Fork/Join线程池 合并任务的结果 异步运行任务 在任务中抛出异常 取消任务 5.1 简介 通常,使用Java来开发一个简单的并发应用程序时,会创建一些Runnable对象,然后创建对应的Thread 对象来控制程序中这些线程的创建.执行以及线程的状态.自从Java 5开始引入了Executor和ExecutorService接口以及实现这两个接口的类(比如ThreadPoolExecutor)之后,使

java多线程并发问题求解

问题描述 java多线程并发问题求解 父类中定义了几个成员变量String类型 a,b,c,这个父类被几个子类共同继承了, 各个子类中在构造器内初始化了a,b,c变量,问多线程调用每一个子类时会 产生并发问题吗? 父类: 解决方案 首先,需要看你的这类是如何设计的,如果只是提供 了构造函数来初始化这几个成员变量,而没有提供外界修改方法如setA...等方法的话,那么你这个类就是线程安全的,因为对象的信息不可能被外界改变. 如果提供了修改方法,那么对于同一个对象,置于多线程访问条件下,就有可能出现

Java 高并发六:JDK并发包2详解_java

1. 线程池的基本使用 1.1.为什么需要线程池 平时的业务中,如果要使用多线程,那么我们会在业务开始前创建线程,业务结束后,销毁线程.但是对于业务来说,线程的创建和销毁是与业务本身无关的,只关心线程所执行的任务.因此希望把尽可能多的cpu用在执行任务上面,而不是用在与业务无关的线程创建和销毁上面.而线程池则解决了这个问题,线程池的作用就是将线程进行复用. 1.2.JDK为我们提供了哪些支持  JDK中的相关类图如上图所示. 其中要提到的几个特别的类. Callable类和Runable类相似,