一、引言前一章——Fork/Join框架(1)原理,我们从整体上对Fork/Join框架作了介绍。回顾一下,Fork/Join框架的核心实现类是ForkJoinPool线程池,其它核心组件包括:ForkJoinTask(任务)、ForkJoinWorkerThread(工作线程)、WorkQueue(任务队列)。这一章,我们将深入F/J框架的实现细节,看看ForkJoinPool线程池究竟有何特殊之处,F/J框架的整个任务调度流程又是怎样的。二、任务调度流程在开始之前,先来看下下面这张图:上图包含了F/J框架的整个任务调度流程,这里先简要介绍下,以便读者在有个印象,后续的源码分析将完全按照这张
一、引言算法领域有一种基本思想叫做“分治”,所谓“分治”就是将一个难以直接解决的大问题,分割成一些规模较小的子问题,以便各个击破,分而治之。对于一个规模为N的问题,若该问题可以容易地解决,则直接解决;否则将其分解为K个规模较小的子问题,这些子问题互相独立且与原问题性质相同,递归地解这些子问题,然后将各子问题的解合并得到原问题的解,这种算法设计策略叫做分治法。许多基础算法都运用了“分治”的思想,比如二分查找、快速排序等等。基于“分治”的思想,J.U.C在JDK1.7时引入了一套Fork/Join框架。Fork/Join框架的基本思想就是将一个大任务分解(Fork)成一系列子任务,子任务可以继续往
一、Future模式简介Future模式是Java多线程设计模式中的一种常见模式,它的主要作用就是异步地执行任务,并在需要的时候获取结果。我们知道,一般调用一个函数,需要等待函数执行完成,调用线程才会继续往下执行,如果是一些计算密集型任务,需要等待的时间可能就会比较长。笔者在读书期间曾参与过一个国家电网的复杂水电系统的联合优化调度项目,需要在工业上可接受的时间内计算出整个云南地区近40座大型水电站的日发电计划。在电力系统中日发电计划的制定非常重要,同时又涉及水利学、经济学、电气工程、政治政策等诸多复杂约束条件,工业上基本都是通过混合整数规划、动态规划再结合其它数学规划方法建模求解,模型涉及的变
一、ScheduledThreadPoolExecutor简介在executors框架概述一节中,我们曾经提到过一种可对任务进行延迟/周期性调度的执行器(Executor),这类Executor一般实现了ScheduledExecutorService这个接口。ScheduledExecutorService在普通执行器接口(ExecutorService)的基础上引入了Future模式,使得可以限时或周期性地调度任务。ScheduledThreadPoolExecutor的类继承关系如下图,该图中除了本节要讲解的ScheduledThreadPoolExecutor外,其它部分已经在前2节详
一、ThreadPoolExecutor简介在juc-executors框架概述的章节中,我们已经简要介绍过ThreadPoolExecutor了,通过Executors工厂,用户可以创建自己需要的执行器对象。ThreadPoolExecutor,它是J.U.C在JDK1.5时提供的一种实现了ExecutorService接口的执行器,或者说线程池。ThreadPoolExecutor并没有自己直接实现ExecutorService接口,因为它只是其中一种Executor的实现而已,所以DougLea把一些通用部分封装成一个抽象父类——AbstractExecutorService,供J.U.
一、executors框架简介juc-executors框架是整个J.U.C包中类/接口关系最复杂的框架,真正理解executors框架的前提是理清楚各个模块之间的关系,高屋建瓴,从整体到局部才能透彻理解其中各个模块的功能和背后的设计思路。网上有太多文章讲executors框架,要么泛泛而谈,要么一叶障目不见泰山,缺乏整体视角,很多根本没有理解整个框架的设计思想和模块关系。本文将对整个executors框架做综述,介绍各个模块的功能和联系,后续再深入探讨每个模块,包括模块中的各个工具类。1.1从Executor谈起Executor是JDK1.5时,随着J.U.C引入的一个接口,引入该接口的主要
一、LinkedTransferQueue简介LinkedTransferQueue是在JDK1.7时,J.U.C包新增的一种比较特殊的阻塞队列,它除了具备阻塞队列的常用功能外,还有一个比较特殊的transfer方法。我们知道,在普通阻塞队列中,当队列为空时,消费者线程(调用take或poll方法的线程)一般会阻塞等待生产者线程往队列中存入元素。而LinkedTransferQueue的transfer方法则比较特殊:当有消费者线程阻塞等待时,调用transfer方法的生产者线程不会将元素存入队列,而是直接将元素传递给消费者;如果调用transfer方法的生产者线程发现没有正在等待的消费者线程
一、LinkedBlockingDeque简介LinkedBlockingDeque和ConcurrentLinkedDeque类似,都是一种双端队列的结构,只不过LinkedBlockingDeque同时也是一种阻塞队列,它是在JDK1.5时随着J.U.C包引入的,实现了BlockingDueue接口,底层基于双链表实现:注意:LinkedBlockingDeque底层利用ReentrantLock实现同步,并不像ConcurrentLinkedDeque那样采用无锁算法。另外,LinkedBlockingDeque是一种近似有界阻塞队列,为什么说近似?因为LinkedBlockingDeq
一、DelayQueue简介DelayQueue是JDK1.5时,随着J.U.C包一起引入的一种阻塞队列,它实现了BlockingQueue接口,底层基于已有的PriorityBlockingQueue实现:DelayQueue也是一种比较特殊的阻塞队列,从类声明也可以看出,DelayQueue中的所有元素必须实现Delayed接口:/***一种混合风格的接口,用来标记那些应该在给定延迟时间之后执行的对象。*<p>*此接口的实现必须定义一个compareTo方法,该方法提供与此接口的getDelay方法一致的排序。*/publicinterfaceDelayedextendsCom
一、SynchronousQueue简介SynchronousQueue是JDK1.5时,随着J.U.C包一起引入的一种阻塞队列,它实现了BlockingQueue接口,底层基于栈和队列实现:没有看错,SynchronousQueue的底层实现包含两种数据结构——栈和队列。这是一种非常特殊的阻塞队列,它的特点简要概括如下:入队线程和出队线程必须一一匹配,否则任意先到达的线程会阻塞。比如ThreadA进行入队操作,在有其它线程执行出队操作之前,ThreadA会一直等待,反之亦然;SynchronousQueue内部不保存任何元素,也就是说它的容量为0,数据直接在配对的生产者和消费者线程之间传递,
一、PriorityBlockingQueue简介PriorityBlockingQueue,是在JDK1.5时,随着J.U.C包引入的一种阻塞队列,它实现了BlockingQueue接口,底层基于堆实现:PriorityBlockingQueue是一种无界阻塞队列,在构造的时候可以指定队列的初始容量。具有如下特点:PriorityBlockingQueue与之前介绍的阻塞队列最大的不同之处就是:它是一种优先级队列,也就是说元素并不是以FIFO的方式出/入队,而是以按照权重大小的顺序出队;PriorityBlockingQueue是真正的无界队列(仅受内存大小限制),它不像ArrayBlock
一、LinkedBlockingQueue简介LinkedBlockingQueue是在JDK1.5时,随着J.U.C包引入的一种阻塞队列,它实现了BlockingQueue接口,底层基于单链表实现:LinkedBlockingQueue是一种近似有界阻塞队列,为什么说近似?因为LinkedBlockingQueue既可以在初始构造时就指定队列的容量,也可以不指定,如果不指定,那么它的容量大小默认为Integer.MAX_VALUE。LinkedBlockingQueue除了底层数据结构(单链表)与ArrayBlockingQueue不同外,另外一个特点就是:它维护了两把锁——takeLock
一、ArrayBlockingQueue简介ArrayBlockingQueue是在JDK1.5时,随着J.U.C包引入的一种阻塞队列,它实现了BlockingQueue接口,底层基于数组实现:ArrayBlockingQueue是一种有界阻塞队列,在初始构造的时候需要指定队列的容量。具有如下特点:队列的容量一旦在构造时指定,后续不能改变;插入元素时,在队尾进行;删除元素时,在队首进行;队列满时,调用特定方法插入元素会阻塞线程;队列空时,删除元素也会阻塞线程;支持公平/非公平策略,默认为非公平策略。这里的公平策略,是指当线程从阻塞到唤醒后,以最初请求的顺序(FIFO)来添加或删除元素;非公平策
一、引言从本节开始,我们将介绍juc-collections框架中的“阻塞队列”部分。阻塞队列在实际应用中非常广泛,许多消息中间件中定义的队列,通常就是一种“阻塞队列”。那么“阻塞队列”和我们之前讨论过的ConcurrentLinkedQueue、ConcurrentLinkedDeque有什么不同呢?ConcurrentLinkedQueue和ConcurrentLinkedDeque是以非阻塞算法实现的高性能队列,其使用场景一般是在并发环境下,需要“队列”/“栈”这类数据结构时才会使用;而“阻塞队列”通常利用了“锁”来实现,也就是会阻塞调用线程,其使用场景一般是在“生产者-消费者”模式中,
一、引言在开始讲ConcurrentLinkedDeque之前,我们先来了解下Deque这种数据结构,我们知道Queue是一种具有FIFO特点的数据结构,元素只能在队首进行“入队”操作,在队尾进行“出队”操作。而Deque(double-endedqueue)是一种双端队列,也就是说可以在任意一端进行“入队”,也可以在任意一端进行“出队”:Deque的数据结构示意图如下:我们再来看下JDK中Queue和Deque这两种数据结构的接口定义,看看Deque和Queue相比有哪些增强:1.1Queue接口定义Queue的接口非常简单,一共只有三种类型的操作:入队、出队、读取。上述方法,可以划分如下:
一、ConcurrentLinkedQueue简介ConcurrentLinkedQueue是JDK1.5时随着J.U.C一起引入的一个支持并发环境的队列。从名字就可以看出来,ConcurrentLinkedQueue底层是基于链表实现的。DougLea在实现ConcurrentLinkedQueue时,并没有利用锁或底层同步原语,而是完全基于自旋+CAS的方式实现了该队列。回想一下AQS,AQS内部的CLH等待队列也是利用了这种方式。由于是完全基于无锁算法实现的,所以当出现多个线程同时进行修改队列的操作(比如同时入队),很可能出现CAS修改失败的情况,那么失败的线程会进入下一次自旋,再尝试入
一、CopyOnWriteArraySet简介CopyOnWriteArraySet,是另一类适合并发环境的SET工具类,也是在JDK1.5时,随着J.U.C包一起引入的。我们之前已经介绍过了ConcurrentSkipListSet,ConcurrentSkipListSet底层基于SkipList(跳表)实现,其操作平均时间复杂度均为O(logn)。CopyOnWriteArraySet,从名字上可以看出,也是基于“写时复制”的思想。事实上,CopyOnWriteArraySet内部引用了一个CopyOnWriteArrayList对象,以“组合”方式,委托CopyOnWriteArray
一、CopyOnWriteArrayList简介ArrayList是一种“列表”数据机构,其底层是通过数组来实现元素的随机访问。JDK1.5之前,如果想要在并发环境下使用“列表”,一般有以下3种方式:使用Vector类使用Collections.synchronizedList返回一个同步代理类;自己实现ArrayList的子类,并进行同步/加锁。前两种方式都相当于加了一把“全局锁”,访问任何方法都需要首先获取锁。第3种方式,需要自己实现,复杂度较高。JDK1.5时,随着J.U.C引入了一个新的集合工具类——CopyOnWriteArrayList:大多数业务场景都是一种“读多写少”的情形,C
一、ConcurrentSkipListSet简介ConcurrentSkipListSet,是JDK1.6时J.U.C新增的一个集合工具类,顾名思义,它是一种SET类型。SET类型,在数学上称为“集合”,具有互异性、无序性的特点,也就是说SET中的任意两个元素均不相同(即不包含重复元素),且元素是无序的。是不是感觉和HashMap有点类似?HashMap中的Key也是不能重复,且是无序的。事实上,JDK提供的默认SET实现——HashSet,其实就是采用“组合”的方式——内部引用了一个HashMap对象,以此实现SET的功能。我们来看下ConcurrentSkipListSet的类继承图:可
一、ConcurrentSkipListMap简介1.1类继承结构在正式讲ConcurrentSkipListMap之前,我们先来看下ConcurrentSkipListMap的类继承图:我们知道,一般的Map都是无序的,也就是只能通过键的hash值进行定位。JDK为了实现有序的Map,提供了一个SortedMap接口,SortedMap提供了一些根据键范围进行查找的功能,比如返回整个Map中key最小/大的键、返回某个范围内的子Map视图等等。为了进一步对有序Map进行增强,JDK又引入了NavigableMap接口,该接口进一步扩展了SortedMap的功能,提供了根据指定Key返回最接近
通过上一篇文章——ConcurrentHashMap原理(1),相信读者对ConcurrentHashMap的基本原理有了一个初步认识,但是上一篇中还有一个遗留问题没有讨论到,那就是ConcurrentHashMap的扩容和数据迁移。本文中,我们将会对这两个问题进行讨论。一、扩容的基本思路JDK1.8中,ConcurrentHashMap最复杂的部分就是扩容/数据迁移,涉及多线程的合作和rehash。我们先来考虑下一般情况下,如何对一个Hash表进行扩容。1.1扩容思路Hash表的扩容,一般都包含两个步骤:①table数组的扩容table数组的扩容,一般就是新建一个2倍大小的槽数组,这个过程通
一、ConcurrentHashMap类简介ConcurrentHashMap是在JDK1.5时,J.U.C引入的一个同步集合工具类,顾名思义,这是一个线程安全的HashMap。不同版本的ConcurrentHashMap,内部实现机制千差万别,本节所有的讨论基于JDK1.8。ConcurrentHashMap的类继承关系并不复杂:可以看到ConcurrentHashMap继承了AbstractMap,这是一个java.util包下的抽象类,提供Map接口的骨干实现,以最大限度地减少实现Map这类数据结构时所需的工作量,一般来讲,如果需要重复造轮子——自己来实现一个Map,那一般就是继承Abs
一、Phaser简介Phaser是JDK1.7开始引入的一个同步工具类,适用于一些需要分阶段的任务的处理。它的功能与CyclicBarrier和CountDownLatch有些类似,类似于一个多阶段的栅栏,并且功能更强大,我们来比较下这三者的功能:同步器作用CountDownLatch倒数计数器,初始时设定计数器值,线程可以在计数器上等待,当计数器值归0后,所有等待的线程继续执行CyclicBarrier循环栅栏,初始时设定参与线程数,当线程到达栅栏后,会等待其它线程的到达,当到达栅栏的总数满足指定数后,所有等待的线程继续执行Phaser多阶段栅栏,可以在初始时设定参与线程数,也可以中途注册/
一、Exchanger简介Exchanger——交换器,是JDK1.5时引入的一个同步器,从字面上就可以看出,这个类的主要作用是交换数据。Exchanger有点类似于CyclicBarrier,我们知道CyclicBarrier是一个栅栏,到达栅栏的线程需要等待其它一定数量的线程到达后,才能通过栅栏。Exchanger可以看成是一个双向栅栏,如下图:Thread1线程到达栅栏后,会首先观察有没其它线程已经到达栅栏,如果没有就会等待,如果已经有其它线程(Thread2)已经到达了,就会以成对的方式交换各自携带的信息,因此Exchanger非常适合用于两个线程之间的数据交换。二、Exchanger
一、Semaphore简介Semaphore,又名信号量,这个类的作用有点类似于“许可证”。有时,我们因为一些原因需要控制同时访问共享资源的最大线程数量,比如出于系统性能的考虑需要限流,或者共享资源是稀缺资源,我们需要有一种办法能够协调各个线程,以保证合理的使用公共资源。Semaphore维护了一个许可集,其实就是一定数量的“许可证”。当有线程想要访问共享资源时,需要先获取(acquire)的许可;如果许可不够了,线程需要一直等待,直到许可可用。当线程使用完共享资源后,可以归还(release)许可,以供其它需要的线程使用。另外,Semaphore支持公平/非公平策略,这和ReentrantL
一、CyclicBarrier简介CyclicBarrier是一个辅助同步器类,在JDK1.5时随着J.U.C一起引入。这个类的功能和我们之前介绍的CountDownLatch有些类似。我们知道,CountDownLatch是一个倒数计数器,在计数器不为0时,所有调用await的线程都会等待,当计数器降为0,线程才会继续执行,且计数器一旦变为0,就不能再重置了。CyclicBarrier可以认为是一个栅栏,栅栏的作用是什么?就是阻挡前行。顾名思义,CyclicBarrier是一个可以循环使用的栅栏,它做的事情就是:让线程到达栅栏时被阻塞(调用await方法),直到到达栅栏的线程数满足指定数量要
一、CountDownLatch简介CountDownLatch是一个辅助同步器类,用来作计数使用,它的作用有点类似于生活中的倒数计数器,先设定一个计数初始值,当计数降到0时,将会触发一些事件,如火箭的倒数计时。初始计数值在构造CountDownLatch对象时传入,每调用一次countDown()方法,计数值就会减1。线程可以调用CountDownLatch的await方法进入阻塞,当计数值降到0时,所有之前调用await阻塞的线程都会释放。注意:CountDownLatch的初始计数值一旦降到0,无法重置。如果需要重置,可以考虑使用CyclicBarrier。二、CountDownLatc
一、LongAdder简介JDK1.8时,java.util.concurrent.atomic包中提供了一个新的原子类:LongAdder。根据Oracle官方文档的介绍,LongAdder在高并发的场景下会比它的前辈————AtomicLong具有更好的性能,代价是消耗更多的内存空间:那么,问题来了:为什么要引入LongAdder?AtomicLong在高并发的场景下有什么问题吗?如果低并发环境下,LongAdder和AtomicLong性能差不多,那LongAdder是否就可以替代AtomicLong了?1.1为什么要引入LongAdder?我们知道,AtomicLong是利用了底层的C
一、什么是FieldUpdater在java.util.concurrent.atomic包中,由三个比较特殊的原子类:AtomicIntegerFieldUpdater、AtomicLongFieldUpdater、AtomicReferenceFieldUpdater。通过名称可以看到,这几类的功能大致相同,只是针对的类型有所不同。所谓AtomicXXXFieldUpdater,就是可以以一种线程安全的方式操作非线程安全对象的某些字段。光这么说有点难理解,我们通过一个例子来看下。假设有一个公司账户Account,100个人同时往里面存钱1块钱,那么正常情况下,最终账户的总金额应该是100。
一、Atomic数组简介Atomic数组,顾名思义,就是能以原子的方式,操作数组中的元素。JDK提供了三种类型的原子数组:AtomicIntegerArray、AtomicLongArray、AtomicReferenceArray。这三种类型大同小异:AtomicIntegerArray对应AtomicIntegerAtomicLongArray对应AtomicLongAtomicReferenceArray对应AtomicReference其实阅读源码也可以发现,这些数组原子类与对应的普通原子类相比,只是多了通过索引找到内存中元素地址的操作而已。注意:原子数组并不是说可以让线程以原子方式一