高效并发

1. Java内存模型与线程

并发处理的广泛应用是使得Amdahl定律代替摩尔定律成为计算机性能发展源动力的根本原因,也是人类"压榨"计算机运算能力的最有力武器.

1.1 概述

• 多任务处理在现代计算机操作系统中几乎已是一项必备的功能了
• 除了充分利用计算机处理器的能力外,一个服务端同时对多个客户端提供服务则是另一个更具体的并发应用场景
• 服务端是Java语言最擅长的领域之一,不过如何写好并发应用程序却又是服务端程序开发的难点之一,处理好并发方面的问题通常需要更多的编码经验来支持,幸好Java语言和虚拟机提供了许多工具,把并发编码的门槛降低了不少

每秒事务处理数(Transactions Per Second, TPS): 代表一秒内服务端平均能响应的请求总数.

1.2 硬件的效率与一致性

• 绝大多数的运算任务不可能只靠处理器计算就能完成,处理器至少要与内存交互,所以现代计算机系统都不得不加入一层读写速度尽可能接近处理器运算速度的高速缓存来作为内存与处理器之间的缓冲:将运算需要使用到的数据复制到缓存中,让运算能快速运行,当运算结束后再从缓存同步回内存之中,这样处理器就无须等待缓慢的内存读写了
• 基于高速缓存的存储交互很好地解决了处理器与内存的速度矛盾,但是也为计算机系统带来更高的复杂度,因为它引入了一个新的问题:缓存一致性;为了解决一致性的问题,需要各个处理器访问缓存时都遵循一些协议,在读写时要根据协议来进行操作,这类协议有MSI、MESI、MOSI、Synapse、Firefly及Dragon Protocol等
• 本章将会多次提到内存模型一词,可以理解在特定的操作协议下,对特定的内存或高速缓存进行读写访问的过程抽象;不同架构的物理机器可以拥有不一样的内存模型,而Java虚拟机也有自己的内存模型,并且这里介绍的内存访问操作与硬件的缓存访问具有很高的可比性
• 除了增加高速缓存之外,为了使得处理器内部的运算单元能尽量被充分利用,处理器可能会对输入代码进行乱序执行优化,处理器会在计算之后将乱序执行的结果重组,保证该结果与顺序执行的结果是一致的

1.3 Java内存模型

Java虚拟机规范中视图定义一种Java内存模型(Java Memory Model, JMM)来屏蔽掉各种硬件和操作系统的内存访问差异,以实现让Java程序在各种平台下都能达到一致的内存访问效果.

1.3.1 主内存与工作内存

• Java内存模型的主要目标是定义程序中各个变量的访问规则,即在虚拟机中将变量存储到内存和从内存中取出变量这样的底层细节.此处的变量与Java编程中所说的变量有所区别,它包括了实例字段、静态字段和构成数组对象的元素,但不包括局部变量与方法参数,因为后者是线程私有的,不会被共享
• Java内存模型规定了所有的变量都存储在主内存(Main Memory)中,每个线程还有自己的工作内存(Working Memory),线程的工作内存中保存了被该线程使用到的变量的主内存副本拷贝,线程对变量的所有操作都必须在工作内存中进行,而不能直接读写主内存中的变量.不同的线程之间也无法访问对方工作内存中的变量,线程间变量值的传递均需要通过主内存来完成
• 这里所讲的主内存、工作内存与第二章所讲的Java内存区域中的Java堆、栈、方法区等并不是同一个层次的内存划分,这两者基本上是没有关系的

线程、主内存和工作内存的关系如下所示:

1.3.2 内存间交互操作

关于主内存与工作内存之间具体的交互协议,即一个变量如何从主内存拷贝到工作内存、如何从工作内存同步回主内存之类的实现细节,Java内存模型中定义了以下八种操作来完成,虚拟机实现时必须保证下面提及的每一种操作都是原子的、不可再分的(对于double和long类型的变量的某些操作在某些平台允许有例外):

• lock(锁定) : 作用于主内存中的变量,它将一个变量标志为一个线程独占的状态
• unlock(解锁) : 作用于主内存中的变量,解除变量的锁定状态,被解除锁定状态的变量才能被其他线程锁定
• read(读取) : 作用于主内存中的变量,它把一个变量的值从主内存中传递到工作内存,以便进行下一步的load操作
• load(载入) : 作用于工作内存中的变量,它把read操作传递来的变量值放到工作内存中的变量副本中
• use(使用) : 作用于工作内存中的变量,这个操作把变量副本中的值传递给执行引擎.当执行需要使用到变量值的字节码指令的时候就会执行这个操作
• assign(赋值) : 作用于工作内存中的变量,接收执行引擎传递过来的值,将其赋给工作内存中的变量.当执行赋值的字节码指令的时候就会执行这个操作
• store(存储) : 作用于工作内存中的变量,它把工作内存中的值传递到主内存中来,以便进行下一步write操作
• write(写入) : 作用于主内存中的变量,它把store传递过来的值放到主内存的变量

基于理解难度和严谨性考虑,最新的JSR-23文档中,已经放弃采用这八种操作去定义Java内存模型的访问协议了,后面将会介绍一个等效判断原则 -- 先行发生原则,用来确定一个访问在并发环境下是否安全.

在将变量从主内存读取到工作内存中,必须顺序执行read、load;要将变量从工作内存同步回主内存中,必须顺序执行store、write.并且这8种操作必须遵循以下规则:

• 不允许read和load、store和write操作之一单独出现.即不允许一个变量从主内存被读取了,但是工作内存不接受,或者从工作内存回写了但是主内存不接受
• 不允许一个线程丢弃它最近的一个assign操作,即变量在工作内存被更改后必须同步改更改回主内存
• 工作内存中的变量在没有执行过assign操作时,不允许无意义的同步回主内存
• 在执行use前必须已执行load,在执行store前必须已执行assign
• 一个变量在同一时刻只允许一个线程对其执行lock操作,一个线程可以对同一个变量执行多次lock,但必须执行相同次数的unlock操作才可解锁
• 一个线程在lock一个变量的时候,将会清空工作内存中的此变量的值,执行引擎在use前必须重新read和load
• 线程不允许unlock其他线程的lock操作.并且unlock操作必须是在本线程的lock操作之后
• 在执行unlock之前,必须首先执行了store和write操作

1.3.3 对于volatile型变量的特殊规则

关键字volatile可以说是Java虚拟机提供的最轻量级的同步机制

当一个变量定义为volatile之后,它将具备两种特性:

• 第一是保证此变量对所有线程的可见性,这里的可见性是指当一个线程修改了这个变量的值,新的值对于其他线程来说是可以立即得知的,而普通的变量的值在线程间传递均需要通过主内存来完成
• 另外一个是禁止指令重排序优化,普通的变量仅仅会保证在该方法的执行过程中所有依赖赋值结果的地方都能获取到正确的结果,而不能保证变量赋值操作的顺序与程序代码中的执行顺序一致

volatile变量在各个线程的工作内存中不存在一致性问题,但是Java里面的运算并非原子操作,导致volatile变量的运算在并发下一样是不安全的

在不符合以下两条规则的运算场景中,我们仍然要通过加锁(使用synchronized或java.util.concurrent中的原子类)来保证原子性:

• 运算结果并不依赖变量的当前值或者能够确保只有单一的线程修改变量的值
• 变量不需要与其他的状态变量共同参与不变约束

volatile变量读操作的性能消耗与普通变量几乎没有任何差别,但是写操作则可能会慢一些;不过大多数场景下volatile的总开销仍然要比锁低,我们在volatile与锁之中选择的唯一依据仅仅是volatile的语义能否满足使用场景的需求

1.3.4 对于long和double型变量的特殊规则

允许虚拟机将没有被volatile修饰的64位数据的读写操作划分为两次32位的操作来进行,即允许虚拟机实现选择可以不保证64位数据类型的load、store、read和write这4个操作的 原子性,这点就是所谓的long和double的非原子性协定

但允许虚拟机选择把这些操作实现为具有原子性的操作,目前各种平台下的商用虚拟机几乎都选择把64位数据的读写操作作为原子操作来对待

1.3.5 原子性、可见性与有序性

• 原子性(Atomicity):由Java内存模型来直接保证的原子性变量操作包括read、load、assign、use、store和write;在synchronized块之间的操作也具备原子性
• 可见性(Visibility):是指当一个线程修改了共享变量的值,其他线程能够立即得知这个修改;除了volatile之外,Java还有synchronized和final关键字能实现可见性
• 有序性(Ordering):如果在本线程内观察,所有的操作都是有序的;如果在一个线程中观察另一个线程,所有的操作都是无序的;Java语言提供了volatile和synchronized两个关键字来保证线程之间操作的有序性

final域

final类型的域是不能修改的,除了这一点外,在Java内存模型中,final域还有着特殊的语义,final域能确保初始化过程的安全性,从而可以不受限制地访问不可变对象,并在共享这些对象时无须同步.具体而言,就是被final修饰的字段在构造器中一旦被初始化完成,并且构造器没有把"this"的引用传递出去(this引用逃逸是一件很危险的事情,其他线程有可能通过这个引用访问到"初始化了一半"的对象),那么在其他线程中就能看到final字段的值,而且其外、外部可见状态永远也不会改变.它所带来的安全性是最简单最纯粹的.

1.3.6 先行发生原则

先行发生是Java内存模型中定义的两项操作之间的偏序关系,如果说操作A先行发生于操作B,其实就是说在发生操作B之前,操作A产生的影响能被操作B观察到,影响包括了修改了内存中共享变量的值、发送了消息、调用了方法等.

八种"天然的"先行发生关系

• 程序次序规则(ProgramOrderRule):在一个线程内,按照程序代码顺序,书写在前面的操作先行发生于书写在后面的操作.准确地说应该是控制流顺序而不是程序代码顺序,因为要考虑分支、循环等结构
• 管程锁定规则(MonitorLockRule):一个unlock操作先行发生于后面对同一个锁的lock操作.这里必须强调的是同一个锁,而"后面"是指时间上的先后顺序
• volatile变量规则(VolatileVariableRule):对一个volatile变量的写操作先行发生于后面对这个变量的读操作,这里的"后面"同样是指时间上的先后顺序
• 线程启动规则(ThreadStartRule):Thread对象的start()方法先行发生于此线程的每一个动作
• 线程终止规则(ThreadTerminationRule):线程中的所有操作都先行发生于对此线程的终止检测,我们可以通过Thread.join()方法结束、Thread.isAlive()的返回值等手段检测到线程已经终止执行.
• 线程中断规则(ThreadInterruptionRule):对线程interrupt()方法的调用先行发生于被中断线程的代码检测到中断事件的发生,可以通过Thread.interrupted()方法检测到是否有中断发生.
• 对象终结规则(FinalizerRule):一个对象的初始化完成(构造函数执行结束)先行发生于它的finalize()方法的开始
• 传递性(Transitivity):如果操作A先行发生于操作B,操作B先行发生于操作C,那就可以得出操作A先行发生于操作C的结论

As-If-Serial语义 不管怎么重排序(编译器和处理器为了提高并行度),(单线程)程序的执行结果不能被改变.编译器,runtime 和处理器都必须遵守as-if-serial语义. 为了遵守as-if-serial语义,编译器和处理器不会对存在数据依赖关系的操作做重排序,因为这种重排序会改变执行结果.但是,如果操作之间不存在数据依赖关系,这些操作可能被编译器和处理器重排序.

该(指程序次序规则)happens-before关系本质上和as-if-serial语义是一回事:

• as-if-serial语义保证单线程内程序的执行结果不被改变,happens-before关系保证正确同步的多线程程序的执行结果不被改变.
• as-if-serial语义给编写单线程程序的程序员创造了一个幻境:单线程程序是按程序的顺序来执行的.happens-before关系给编写正确同步的多线程程序的程序员创造了一个幻境:正确同步的多线程程序是按happens-before指定的顺序来执行的.
• as-if-serial语义和happens-before这么做的目的,都是为了在不改变程序执行结果的前提下,尽可能地提高程序执行的并行度.

时间先后顺序与先行发生原则之间基本没有太大的关系,所以我们衡量并发安全问题的时候不要受到时间顺序的干扰,一切必须以先行发生原则为准.

1.4 Java与线程

1.4.1 线程的实现

• 线程是比进程更轻量级的调度执行单位,线程的引入可以把一个进程的资源分配和执行调度分开,各个线程既可以共享进程资源又可以独立调度
• Thread类与大部分的Java API有显著的差别,它的所有关键方法都是声明为Native的
• 实现线程主要有三种方式:使用内核线程实现(系统调用代价相对较高、一个系统支持轻量级进程的数量是有限的)、使用用户线程实现(优势在于不需要系统内核支援,劣势在于所有线程操作都需要用户程序自己处理)和使用用户线程加轻量级进程混合实现(用户线程是完全建立在用户空间中,因此用户线程的创建、切换等操作依然廉价,并且可以支持大规模的用户线程并发;而操作系统提供支持的轻量级进程则作为用户线程和内核线程之间的桥梁,这样可以使用内核提供的线程调度功能及处理器映射,并且用户线程的系统调用要通过轻量级线程来完成,大大降低了整个进程被完全阻塞的风险)
• 对于Sun JDK来说,它的Windows版与Linux版都是使用一对一的线程模型实现的,一条Java线程就映射到一条轻量级进程之中,因为Windows和Linux系统提供的线程模式就是一对一的

1.4.2 Java线程调度

线程调度是指系统为线程分配处理器使用权的过程,主要调度方式有两种

• 协同式线程调度(Cooperative Threads-Scheduling): 线程的执行时间由线程本身来控制. 线程把自己的工作执行完之后,要主动通知系统切换到另外一个线程上.最大好处是实现简单,且切换操作对线程自己是可知的,没啥线程同步问题.坏处是线程执行时间不可控制,如果一个线程有问题,可能一直阻塞在那里
• 抢占式线程调度(Preemptive Threads-Scheduling): 线程由系统来分配执行时间. 线程的切换不由线程本身来决定,线程的切换不由线程本身来决定(Java中,Thread.yield()可以让出执行时间,但无法获取执行时间).线程执行时间系统可控,也不会有一个线程导致整个进程阻塞

Java线程调度就是抢占式调度

Java语言一共设置了10个级别的线程优先级(Thread.MIN_PRIORITY至Thread.MAX_PRIORITY),不过线程优先级并不是太靠谱,原因就是操作系统的线程优先级不见得总是与Java线程的优先级一一对应,另外优先级还可能被系统自行改变

1.4.3 状态转换

Java语言定义了五种线程状态,在任意一个时间点,一个线程只能有且只有其中一种状态

• 新建(New): 创建后尚未启动的线程处于这种状态
• 运行(Runnable): Runnable包括操作系统线程状态中的Running和Ready,也就是处于此状态的线程有可能正在执行,也有可能等待CPU为它分配执行时间.线程对象创建后,其他线程调用了该对象的start()方法.该状态的线程位于"可运行线程池"中,变得可运行,只等待获取CPU的使用权.即在就绪状态的进程除CPU之外,其它的运行所需资源都已全部获得
• 无限期等待(Waiting): 该状态下线程不会被分配CPU执行时间,要等待被其他线程显式唤醒.以下方法会让线程陷入无限期的等待状态:
  • 没有设置timeout的object.wait()方法
    • 没有设置timeout的Thread.join()方法
    • LockSupport.park()方法
• 限期等待(Timed Waiting): 不会被分配CPU执行时间,不过无须等待被其他线程显式唤醒,在一定时间之后会由系统自动唤醒.以下方法会让线程进入限期等待状态:
  • Thread.sleep()
  • 设置了timeout的object.wait()
  • 设置了timeout的thread.join()
  • LockSupport.parkNanos()
  • LockSupport.parkUntil()方法
• 阻塞（Blocked）:线程被阻塞了.与等待状态的区别是: 阻塞在等待着获取到一个排他锁,这个事件将在另外一个线程放弃这个锁的时候发生;而等待则在等待一段时间,或唤醒动作的发生.在等待进入同步区域时,线程将进入这种状态
• 结束(Terminated): 线程执行完了或者因异常退出了run()方法,该线程结束生命周期

线程状态转换关系:

阻塞的三种情况

• 等待阻塞: 运行的线程执行wait()方法,该线程会释放占用的所有资源,JVM会把该线程放入"等待池"中.进入这个状态后,是不能自动唤醒的,必须依靠其他线程调用notify()或notifyAll()方法才能被唤醒,即无限期等待
• 同步阻塞: 运行的线程在获取对象的同步锁时,若该同步锁被别的线程占用,则JVM会把该线程放入"锁池"中.
• 其他阻塞: 运行的线程执行sleep()或join()方法,或者发出了I/O请求时,JVM会把该线程置为阻塞状态.当sleep()状态超时、join()等待线程终止或者超时、或者I/O处理完毕时,线程重新转入就绪状态.即限期等待.

2. 线程安全与锁优化

2.1 线程安全

Brian Goetz对线程安全有一个比较恰当的定义: 当多个线程访问一个对象时,如果不用考虑这些线程在运行时环境下的调度和交替执行,也不需要进行额外的同步,或者在调用方进行任何其他的协调操作,调用这个对象的行为都可以获得正确的结果,那这个对象是线程安全的.

2.1.1 Java语言中的线程安全

按照线程安全的程度由强至弱,我们可以将Java语言中各个操作共享的数据分为以下五类: 不可变、绝对线程安全、相对线程安全、线程兼容和线程对立.

• 不可变: 不可变带来的安全性是最简单和最纯粹的,如final的基本数据类型;如果共享的数据是一个对象,那就需要保证对象的行为不会对其状态产生任何影响才行,比如String类的substring、replace方法;Number类型的大部分子类都符合不可变要求的类型,但是AtomicInteger和AtomicLong则并非不可变的
• 线程绝对安全: Java API中标注自己是线程安全的类,大多数都不是绝对的线程安全;比如java.util.Vector,不意味着调用它的是时候永远都不再需要同步手段了
• 线程相对安全: 是我们通常意义上所讲的线程安全,在Java语言中,大部分的线程安全类都属于这种类型
• 线程兼容: 指对象本身并不是线程安全的,但是可以通过在调用端正确地使用同步手段来保证对象在并发环境中可以安全地使用;我们说一个类不是线程安全的,绝大多数时候指的是这一种情况
• 线程对立: 无论调用端是否采取了同步措施,都无法在多线程环境中并发使用的代码,Java语言中很少出现

2.1.2 线程安全的实现方法

• 互斥同步: 同步是指在多个线程并发访问共享数据时,保证共享数据在同一个时刻只被一个线程使用,而互斥是实现同步的一种手段,临界区、互斥量和信号量都是主要的互斥实现方式;Java中最基本的互斥同步手段就是synchronized关键字,它对同一个线程来说是可重入的且会阻塞后面其他线程的进入;另外还可以使用java.util.concurrent包中的重入锁(ReentrantLock)来实现同步,相比synchronized关键字ReentrantLock增加了一些高级功能:等待可中断、可实现公平锁以及锁可以绑定多个条件
• 非阻塞同步: 互斥同步最主要的问题就是进行线程阻塞和唤醒带来的性能问题,其属于一种悲观的并发策略;随着硬件指令集的发展,我们有了另外一个选择即基于冲突检测的乐观并发策略,就是先进行操作,如果没有其他线程争用共享数据那就操作成功了,如果有争用产生了冲突,那就再采取其他的补偿措施(最常见的就是不断重试直至成功),这种同步操作称为非阻塞同步;Java并发包的整数原子类,其中的compareAndSet和getAndIncrement等方法都使用了Unsafe类的CAS操作
• 无同步方案: 要保证线程安全,并不是一定就要进行同步;有一些代码天生就是线程安全的,比如可重入代码和线程本地存储的代码

2.2 锁优化

2.2.1 自旋锁与自适应自旋

互斥同步对性能最大的影响是阻塞的实现,挂起线程和恢复线程的操作都需要转入内核态中完成,这些操作给系统的并发性能带来了很大的压力;另外在共享数据的锁定状态只会持续很短的一段时间,为了这段时间去挂起和恢复线程并不值得,如果让两个或以上的线程同时并行执行,让后面请求锁的那个线程稍等一下,但不放弃处理器的执行时间,看看持有锁的线程是否很快就会释放锁;为了让线程等待,我们只需让线程执行一个忙循环,这些技术就是所谓的自旋锁.

在JDK 1.6已经默认开启自旋锁;如果锁被占用的时间很短自旋等待的效果就会非常好,反之则会白白消耗处理器资源. 在JDK 1.6中引入了自适应的自旋锁,这意味着自旋的时间不再固定,而是由前一次在同一个锁上的自旋时间及锁的拥有者的状态来决定.

2.3.2 锁消除

锁消除是指虚拟机即时编译器在运行时,对一些代码上要求同步,但是被检测到不可能存在共享数据竞争的锁进行消除 锁消除的主要判断依据来源于逃逸分析的数据支持

2.3.3 锁粗化

原则上总是推荐将同步块的作用范围限制得尽量小 -- 只有在共享数据的实际作用域中才进行同步,这样是为了使得需要同步的操作数量尽可能变小,如果存在锁竞争,那等待锁的线程也能尽快拿到锁. 但是如果一系列的连续操作都对同一个对象反复加锁和解锁,甚至加锁操作是出现在循环体中的,那即使没有线程竞争,频繁地进行互斥同步操作也会导致不必要的性能损耗;

2.3.4 轻量级锁

轻量级锁是JDK 1.6之中加入的新型锁机制,它是相对于使用操作系统互斥量来实现的传统锁而言的;它并不是用来代替重量级锁的,它的本意是在没有多线程竞争的前提下,减少传统的重量级锁使用操作系统互斥量产生的性能消耗.

要理解轻量级锁,以及后面会讲到的偏向锁的原理和运作过程,必须从HotSpot虚拟机的对象的内存布局开始介绍; HotSpot虚拟机的对象头分为两部分信息:

• 第一部分用于存储对象自身的运行时数据,如哈希码、GC分代年龄等,这部分官方称之为Mark Word,是实现轻量级锁和偏向锁的关键,
• 另外一部分用于存储指向方法区对象类型数据的指针

Mark Word被设计成一个非固定的数据结构以便在极小的空间存储尽量多的信息,在32位的HotSpot虚拟机中对象未被锁定的状态下,25bit用于存储对象哈希码,4bit用于存储对象分代年龄,2bit用于存储锁标志位,1bit固定为0;在其他状态(轻量级锁定、重量级锁定、GC标志、可偏向)下对象的存储内容如下:

在代码进入同步块的时候,如果此同步对象没有被锁定,虚拟机首先将在当前线程的栈帧中建立一个名为锁记录(Lock Record)的空间,用于存储对象目前的Mark Word的拷贝(官方称之为Displaced Mark Word);然后虚拟机将使用CAS操作尝试将对象的Mark Word更新为指向Lock Record的指针,如果更新成功了那么这个线程就拥有了该对象的锁,并且对象Mark Word的锁标志位将转变为"00",即表示此对象处于轻量级锁定状态;如果这个更新操作失败了,虚拟机首先会检查对象的Mark Word是否指向当前线程的栈帧,如果是就可以直接进入同步块继续执行,否则说明这个锁对象已经被其他线程抢占了;如果有两条以上的线程争用同一个锁,那轻量级锁就不再有效,要膨胀为重量级锁,锁标志的状态值变为"10",Mark Word中存储的就是指向重量级锁的指针,后面等待锁的线程也要进行阻塞状态.

轻量级锁能提升程序同步性能的依据是"对于绝大部分的锁,在整个同步周期内都是不存在竞争的",这是一个经验数据.

2.3.5 偏向锁

偏向锁也是JDK 1.6中引入的一项锁优化,它的目的是消除数据在无竞争情况下的同步原语,进一步提高程序的运行性能;如果说轻量级锁是在无竞争的情况下使用CAS操作去消除同步使用的互斥量,那偏向锁就是在无竞争的情况下把整个同步都消除掉,连CAS操作都不做了.

向锁会偏向于第一个获得它的线程,如果在接下来的执行过程中,该锁没有被其他的线程获取,则持有偏向锁的线程将永远不需要再进行同步.

假设当前虚拟机启动了偏向锁,那么当锁对象第一次被线程获取的时候,虚拟机将会把对象头中的标志位设为"01",即偏向模式;同时使用CAS操作把获取到这个锁的线程ID记录在对象的Mark Word之中;如果CAS操作成功,持有偏向锁的线程以后每次进入这个锁相关的同步块时,虚拟机都可以不再进行任何同步操作;当有另外一个线程去尝试获取这个锁时,偏向模式就宣告结束,根据锁对象目前是否被锁定的状态,撤销偏向后恢复到未锁定或轻量级锁定的状态,后续的同步操作就如上面介绍的轻量级锁那样执行.

偏向锁、轻量级锁的状态转化以及对象Mark Work的关系如下图所示:

偏向锁可以提高带有同步但无竞争的程序性能,它同样是一个带有效益权衡性质的优化.