Java 併发容器和框架

本篇博客主要是纪录对<<Java并发编程的艺术>>的学习心得以及一些知识点的重新整理,因此文章中会有许多引用自该书的文字。同时也借鑑其他相关的技术博客,以完善整个知识框架。

ConcurrentHashMap

ConcurrentHashMap视线安全且高效的HashMap,接下来将介绍该容器是如何保证线程安全的。

为甚麽使用ConcurrentHashMap

在併发编程中使用HashMap可能导致程序死循环。而使用线程安全的HashTable效率又非常低下,基于以上两个原因,便有了ConcurrentHashMap的登场机会。

  1. 线程不安全的HashMap

    在多线程环境下,使用HashMap进行put操作会引起死循环,导致CPU利用率接近100%,所以在併发情况下不能使用HashMap。例如,执行以下代码会引起死循环。

    final Hash<String, String> map = new HashMap<String, String>(2);
    Thread t = new Thread(new Runnable() {
      @Override
      public void run() {
        for (int i = 0; i < 10000; i++) {
          new Thread(new Runnable() {
            @Override
            public void run() {
              map.put(UUID.randomUUID().toString(), "");
            }
          }, "ftf" + i).start();
        }
      }
    }, "ftf");
    t.start();
    t.join();

    HashMap在併发执行put操作时会引起死循环,是因为多线程会导致HashMap的Entry链表形成数据结构,一旦形成环形数据结构,Entru的next节点永远不为空,就会产生死循环获取Entry。

  2. 效率低下的HashTable

    HashTable容器使用synchronized来保证线程安全,但在线程竞争激烈的情况下HashTable的效率非常低下。因为当一个线程访问HashTable的同步方法,其他线程也访问HashTable的同步方法时,会进入阻塞或轮询状态。如线程1使用put进行元素添加,线程2不但不能使用put方法添加元素,也不能使用get方法来获取元素,所以竞争越激烈效率越低。

  3. ConcurrentHashMap的锁分段技术可有效提升併发访问率

    HashTable容器在竞争激烈的併发环境下表现出效率低下的原因是所有访问HashTable的线程都必须竞争同一把锁,假如容器裡有多把锁,每一把锁用于锁容器其中一部份数据,那麽当多线程访问容器裡不同数据段的数据时,线程间就不会存在锁竞争,从而可以有效提高併发访问效率,这就是ConcurrentHashMap所使用的锁分段技术。首先将数据分成一段一段的存储,然后给每一段数据赔一把锁,当一个线程占用锁访问其中一个段数据的时候,其他段的数据也能被其他线程访问。

ConcurrentHashMap的结构

通过ConcurrentHashMap的类图来分析ConcurrentHashMap的结构,如下图所示:

ConcurrentHashMap类图

ConcurrentHashMap是由Segment数组结构和HashEntry数组结构组成。Segment是一种可重入锁(ReentrantLock),在ConcurrentHashMap裡面扮演锁的角色; HashEntry则用于存储键值对数据。一个ConcurrentHashMap裡包含一个Segment数组,每个HashEntry是一个链表结构的元素,每个Segment守护着一个HashEntry数组裡的元素,当对HashEntry数组的数据进行修改时,必须首先获得与他对应的Segment锁。以下是ConcurrentHashMap的结构图:

ConcurrentHashMap结构图

源码分析

详见之后的源码分析。

ConcurrentLinkedQueue

在併发编成中,有时候需要使用现成安全的队列。如果要实现一个现成安全的队列有两种方式: 一种是使用阻塞算法,另一种是使用非阻塞算法。使用阻塞算法的队列可以用一个锁(入队和出队使用同一把所)或两个锁(入队和出队用不同的锁)等方式来实现。非阻塞的方式则可以使用循环CAS的方式来实现。ConcurrentLinkedQueue就是以非阻塞的方式实现的线程安全队列。

ConcurrentLinkedQueue是一个基于链接节点的无界线程安全队列,他採用先进先出的规则对节点进行排序,当我们添加一个元素的时候,他会添加到对列的尾部; 当我们获取一个元素时,它会返回队列头部的元素。它採用了”wait-free”算法(即CAS)来实现。

ConcurrentLinkedQueue的结构

ConcurrentLinkedQueue类图

ConcurrentLinkedQueue由head节点和tail节点组成,没个节点(Node)由节点元素(item)和指向下一个节点(next)的饮用组成,节点与节点之间就是通过这个next关联起来,从而组成一张链表结构的对列。默认情况下head节点存储的元素为空,tail节点等于head节点。

源码分析

详见之后的源码分析。

Java中的阻塞队列

本节将介绍Java中的阻塞队列

甚麽是阻塞队列

阻塞队列(BlockingQueue)是一个支持两个富家操作的队列。这两个富家的操作支持阻塞的插入和移除方法。

  1. 支持阻塞的插入方法: 意思是当队列满十,队列会阻塞插入元素的线程,直到队列不满。
  2. 支持阻塞的移除方法: 意思是在队列为空时,获取元素的线程会等待队列变为非空。

阻塞队列成用于生产者和消费者的场景,生产者是向队列李添加元素的线程,消费者是从队列裡取元素的线程。阻塞队列就是生产者用来存放元素、消费者用来获取元素的容器。

在阻塞队列不可用时,这两个富家操作提供了4种处理方式,如下表所示:

方法/处理方式 抛出异常 返回特殊值 一直阻塞 超时退出
插入方法 add(e) offer(e) put(e) offer(e, time, unit)
移除方法 remove() poll() take() poll(time, unit)
检查方法 element() peek() 不可用 不可用
  • 抛出异常: 当队列满时,如果再往裡面插入元素,会抛出IllegalStateException(“Queue full”)异常。当队列空时,从队列或取元素会抛出NoSuchElementException异常。
  • 返回特殊值: 当网队列插入元素时,会返回元素是否插入成功,成功返回true。如果是移除方法,则是从队列裡取出一个元素,如果没有则返回null。
  • 一直阻塞: 当阻塞队列满时,如果生产者线程往队列裡put元素,队列会一直阻塞生产者线程,直到队列可用或者响应中断退出。当队列为空时,如果消费者线程从队列裡take元素,队列会阻塞住消费者线程,直到队列不为空。
  • 超时退出: 当阻塞队列满时,如果生产者线程往队列裡插入元素,队列会阻塞生产者线程段时间,如果超过了指定时间,生产者线程就会退出。

Java裡的阻塞队列

JDK 7提供了以下7种阻塞队列:

  • ArrayBlockingQueue: 一个由数组结构组成的有界阻塞队列。
  • LinkedBlockingQueue: 一个由链表结构组成的有界阻塞队列。
  • PriorityBlockingQueue: 一个使用优先级排序的无界阻塞队列。
  • DelayQueue: 一个使用优先级队列实现的无界阻塞队列。
  • SynchronousQueue: 一个不存储元素的阻塞队列。
  • LinkedTransferQueue: 一个由链表结构组成的无界阻塞队列。
  • LinkedBlockingDeque: 一个由链表结构组成的双向阻塞队列。

源码分析

详见之后的源码分析。