并发编程的挑战

上下文切换

CPU通过时间片分配算法来循环执行任务，当前任务执行一个时间片后会切换到下一个
任务。但是，在切换前会保存上一个任务的状态，以便下次切换回这个任务时，可以再加载这
个任务的状态。所以任务从保存到再加载的过程就是一次上下文切换。上下文切换会影响多线程的执行速度。

减少上下文切换的方法有无锁并发编程、CAS算法、使用最少线程和使用协程。
·无锁并发编程。多线程竞争锁时，会引起上下文切换，所以多线程处理数据时，可以用一 些办法来避免使用锁，如将数据的ID按照Hash算法取模分段，不同的线程处理不同段的数据。
·CAS算法。Java的Atomic包使用CAS算法来更新数据，而不需要加锁。
·使用最少线程。避免创建不需要的线程，比如任务很少，但是创建了很多线程来处理，这
样会造成大量线程都处于等待状态。
·协程：在单线程里实现多任务的调度，并在单线程里维持多个任务间的切换。

死锁

避免死锁的几个常见方法。

• 避免一个线程同时获取多个锁。
• 避免一个线程在锁内同时占用多个资源，尽量保证每个锁只占用一个资源。
• 尝试使用定时锁，使用lock.tryLock（timeout）来替代使用内部锁机制。
  对于数据库锁，加锁和解锁必须在一个数据库连接里，否则会出现解锁失败的情况。

Java并发机制的底层实现原理

volatile的应用

在多线程并发编程中synchronized和volatile都扮演着重要的角色，volatile是轻量级的 synchronized，它在多处理器开发中保证了共享变量的“可见性”。可见性的意思是当一个线程 修改一个共享变量时，另外一个线程能读到这个修改的值。如果volatile变量修饰符使用恰当 的话，它比synchronized的使用和执行成本更低，因为它不会引起线程上下文的切换和调度。如果一个字段被声明成volatile，Java线程内存模型确保所有线程看到这个变量的值是一致的。

volatile变量自身具有下列特性。

• 可见性。对一个volatile变量的读，总是能看到（任意线程）对这个volatile变量最后的写
  入。
• 原子性：对任意单个volatile变量的读/写具有原子性，但类似于volatile++这种复合操作不
  具有原子性。

synchronized

绍Java SE 1.6中为了减少获得锁和释放锁带来的性能消耗而引入的偏向锁和轻量级锁，以及锁的存储结构和升级过程。

先来看下利用synchronized实现同步的基础：Java中的每一个对象都可以作为锁。具体表现 为以下3种形式。

• 对于普通同步方法，锁是当前实例对象。
• 对于静态同步方法，锁是当前类的Class对象。
• 对于同步方法块，锁是Synchonized括号里配置的对象。

synchronized用的锁是存在Java对象头里的。

锁的升级与对比

Java SE 1.6为了减少获得锁和释放锁带来的性能消耗，引入了“偏向锁”和“轻量级锁”，在 Java SE 1.6中，锁一共有4种状态，级别从低到高依次是：无锁状态、偏向锁状态、轻量级锁状
态和重量级锁状态，这几个状态会随着竞争情况逐渐升级。锁可以升级但不能降级，意味着偏向锁升级成轻量级锁后不能降级成偏向锁。这种锁升级却不能降级的策略，目的是为了提高获得锁和释放锁的效率

原子操作

在Java中可以通过锁和循环CAS的方式来实现原子操作。

循环CAS

JVM中的CAS操作正是利用了处理器提供的CMPXCHG指令实现的。自旋CAS实现的基本 思路就是循环进行CAS操作直到成功为止。
从Java 1.5开始，JDK的并发包里提供了一些类来支持原子操作，如AtomicBoolean（用原子方式更新的boolean值）、AtomicInteger（用原子方式更新的int值）和AtomicLong（用原子方式更 新的long值）。这些原子包装类还提供了有用的工具方法，比如以原子的方式将当前值自增1和 自减1。

CAS实现原子操作的三大问题

1. ABA问题。因为CAS需要在操作值的时候，检查值有没有发生变化，如果没有发生变化 则更新，但是如果一个值原来是A，变成了B，又变成了A，那么使用CAS进行检查时会发现它 的值没有发生变化，但是实际上却变化了。ABA问题的解决思路就是使用版本号。在变量前面 追加上版本号，每次变量更新的时候把版本号加1，那么A→B→A就会变成1A→2B→3A。从 Java 1.5开始，JDK Atomic包里提供了一个类AtomicStampedReference来解决ABA问题。这个 类的compareAndSet方法的作用是首先检查当前引用是否等于预期引用，并且检查当前标志是否等于预期标志，如果全部相等，则以原子方式将该引用和该标志的值设置为给定的更新值。

2. 循环时间长开销大。自旋CAS如果长时间不成功，会给CPU带来非常大的执行开销。如
   果JVM能支持处理器提供的pause指令，那么效率会有一定的提升。pause指令有两个作用：第 一，它可以延迟流水线执行指令（de-pipeline），使CPU不会消耗过多的执行资源，延迟的时间
   取决于具体实现的版本，在一些处理器上延迟时间是零；第二，它可以避免在退出循环的时候 因内存顺序冲突（Memory Order Violation）而引起CPU流水线被清空（CPU Pipeline Flush），从而 提高CPU的执行效率。

3. 只能保证一个共享变量的原子操作。当对一个`共享变量执行操作时，我们可以使用循 环CAS的方式来保证原子操作，但是对多个共享变量操作时，循环CAS就无法保证操作的原子性，这个时候就可以用锁。还有一个取巧的办法，就是把多个共享变量合并成一个共享变量来 操作。比如，有两个共享变量i＝2，j=a，合并一下ij=2a，然后用CAS来操作ij。从Java 1.5开始， JDK提供了AtomicReference类来保证引用对象之间的原子性，就可以把多个变量放在一个对象里来进行CAS操作。

使用锁机制实现原子操作

锁机制保证了只有获得锁的线程才能够操作锁定的内存区域。JVM内部实现了很多种锁 机制，有偏向锁、轻量级锁和互斥锁。有意思的是除了偏向锁，JVM实现锁的方式都用了循环 CAS，即当一个线程想进入同步块的时候使用循环CAS的方式来获取锁，当它退出同步块的时 候使用循环CAS释放锁。

Java内存模型

重排序

在执行程序时，为了提高性能，编译器和处理器常常会对指令做重排序。重排序分3种类型

1. 编译器优化的重排序。编译器在不改变单线程程序语义的前提下，可以重新安排语句
   的执行顺序。
2. 指令级并行的重排序。现代处理器采用了指令级并行技术（Instruction-Level Parallelism，ILP）来将多条指令重叠执行。如果不存在数据依赖性，处理器可以改变语句对应
   机器指令的执行顺序。
3. 内存系统的重排序。由于处理器使用缓存和读/写缓冲区，这使得加载和存储操作看上去可能是在乱序执行。

上述的1属于编译器重排序，2和3属于处理器重排序。这些重排序可能会导致多线程程序 出现内存可见性问题。对于编译器，JMM的编译器重排序规则会禁止特定类型的编译器重排序（不是所有的编译器重排序都要禁止）。对于处理器重排序，JMM的处理器重排序规则会要 求Java编译器在生成指令序列时，插入特定类型的内存屏障（Memory Barriers，Intel称之为 Memory Fence）指令，通过内存屏障指令来禁止特定类型的处理器重排序。

happens-before

从JDK 5开始，Java使用新的JSR-133内存模型（除非特别说明，本文针对的都是JSR-133内 存模型）。JSR-133使用happens-before的概念来阐述操作之间的内存可见性。在JMM中，如果一 个操作执行的结果需要对另一个操作可见，那么这两个操作之间必须要存在happens-before关
系。这里提到的两个操作既可以是在一个线程之内，也可以是在不同线程之间。
与程序员密切相关的happens-before规则如下。

• 程序顺序规则：一个线程中的每个操作，happens-before于该线程中的任意后续操作。
• 监视器锁规则：对一个锁的解锁，happens-before于随后对这个锁的加锁。
• volatile变量规则：对一个volatile域的写，happens-before于任意后续对这个volatile域的
  读。
• 传递性：如果A happens-before B，且B happens-before C，那么A happens-before C。

注意: 两个操作之间具有happens-before关系，并不意味着前一个操作必须要在后一个 操作之前执行！happens-before仅仅要求前一个操作（执行的结果）对后一个操作可见，且前一 个操作按顺序排在第二个操作之前。

数据依赖：如果两个操作访问同一个变量，且这两个操作中有一个为写操作，此时这两个操作之间就存在数据依赖性。编译器和处理器在重排序时，会遵守数据依赖性，编译器和处理器不会改变存在数据依赖关系的两个操作的执行顺序。

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

final域的重排序规则

对于final域，编译器和处理器要遵守两个重排序规则。

1. 在构造函数内对一个final域的写入，与随后把这个被构造对象的引用赋值给一个引用变量，这两个操作之间不能重排序。
2. 初次读一个包含final域的对象的引用，与随后初次读这个final域，这两个操作之间不能重排序。

Java并发编程基础

Java并发容器和框架

ConcurrentHashMap

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

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

ConcurrentHashMap是由Segment数组结构和HashEntry数组结构组成。Segment是一种可重 入锁（ReentrantLock），在ConcurrentHashMap里扮演锁的角色；HashEntry则用于存储键值对数 据。一个ConcurrentHashMap里包含一个Segment数组。Segment的结构和HashMap类似，是一种 数组和链表结构。一个Segment里包含一个HashEntry数组，每个HashEntry是一个链表结构的元 素，每个Segment守护着一个HashEntry数组里的元素，当对HashEntry数组的数据进行修改时， 必须首先获得与它对应的Segment锁

get操作

Segment的get操作实现非常简单和高效。先经过一次再散列，然后使用这个散列值通过散 列运算定位到Segment，再通过散列算法定位到元素.
get操作的高效之处在于整个get过程不需要加锁，除非读到的值是空才会加锁重读。我们 知道HashTable容器的get方法是需要加锁的，那么ConcurrentHashMap的get操作是如何做到不 加锁的呢？原因是它的get方法里将要使用的共享变量都定义成volatile类型，如用于统计当前 Segement大小的count字段和用于存储值的HashEntry的value。定义成volatile的变量，能够在线程之间保持可见性，能够被多线程同时读，并且保证不会读到过期的值，但是只能被单线程写 （有一种情况可以被多线程写，就是写入的值不依赖于原值），在get操作里只需要读不需要写 共享变量count和value，所以可以不用加锁。之所以不会读到过期的值，是因为根据Java内存模 型的happen before原则，对volatile字段的写入操作先于读操作，即使两个线程同时修改和获取 volatile变量，get操作也能拿到最新的值，这是用volatile替换锁的经典应用场景。

put操作

由于put方法里需要对共享变量进行写入操作，所以为了线程安全，在操作共享变量时必 须加锁。put方法首先定位到Segment，然后在Segment里进行插入操作。插入操作需要经历两个 步骤，第一步判断是否需要对Segment里的HashEntry数组进行扩容，第二步定位添加元素的位 置，然后将其放在HashEntry数组里。

1. 是否需要扩容
   在插入元素前会先判断Segment里的HashEntry数组是否超过容量（threshold），如果超过阈 值，则对数组进行扩容。值得一提的是，Segment的扩容判断比HashMap更恰当，因为HashMap
   是在插入元素后判断元素是否已经到达容量的，如果到达了就进行扩容，但是很有可能扩容 之后没有新元素插入，这时HashMap就进行了一次无效的扩容。
2. 如何扩容
   在扩容的时候，首先会创建一个容量是原来容量两倍的数组，然后将原数组里的元素进 行再散列后插入到新的数组里。为了高效，ConcurrentHashMap不会对整个容器进行扩容，而只 对某个segment进行扩容。

size操作

如果要统计整个ConcurrentHashMap里元素的大小，就必须统计所有Segment里元素的大小 后求和。Segment里的全局变量count是一个volatile变量，那么在多线程场景下，是不是直接把
所有Segment的count相加就可以得到整个ConcurrentHashMap大小了呢？不是的，虽然相加时 可以获取每个Segment的count的最新值，但是可能累加前使用的count发生了变化，那么统计结 果就不准了。所以，最安全的做法是在统计size的时候把所有Segment的put、remove和clean方法全部锁住，但是这种做法显然非常低效。

因为在累加count操作过程中，之前累加过的count发生变化的几率非常小，所以 ConcurrentHashMap的做法是先尝试2次通过不锁住Segment的方式来统计各个Segment大小，如 果统计的过程中，容器的count发生了变化，则再采用加锁的方式来统计所有Segment的大小。

那么ConcurrentHashMap是如何判断在统计的时候容器是否发生了变化呢？使用modCount 变量，在put、remove和clean方法里操作元素前都会将变量modCount进行加1，那么在统计size 前后比较modCount是否发生变化，从而得知容器的大小是否发生变化。

ConcurrentLinkedQueue

在并发编程中，有时候需要使用线程安全的队列。如果要实现一个线程安全的队列有两
种方式：一种是使用阻塞算法，另一种是使用非阻塞算法。使用阻塞算法的队列可以用一个锁
（入队和出队用同一把锁）或两个锁（入队和出队用不同的锁）等方式来实现。非阻塞的实现方 式则可以使用循环CAS的方式来实现。

ConcurrentLinkedQueue是一个基于链接节点的无界线程安全队列，它采用先进先出的规
则对节点进行排序，当我们添加一个元素的时候，它会添加到队列的尾部；当我们获取一个元 素时，它会返回队列头部的元素。它采用了“wait-free”算法（即CAS算法）来实现，该算法在 Michael&Scott算法上进行了一些修改。

Java中的阻塞队列

Java 7中提供的 7种阻塞队列

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

Java中的原子操作类

使用原子的方式更新基本类型，Atomic包提供了以下3个类。
·AtomicBoolean：原子更新布尔类型。
·AtomicInteger：原子更新整型。
·AtomicLong：原子更新长整型。

通过原子的方式更新数组里的某个元素，Atomic包提供了以下3个类。

• AtomicIntegerArray：原子更新整型数组里的元素。
• AtomicLongArray：原子更新长整型数组里的元素。
• AtomicReferenceArray：原子更新引用类型数组里的元素。

原子更新基本类型的AtomicInteger，只能更新一个变量，如果要原子更新多个变量，就需 要使用这个原子更新引用类型提供的类。Atomic包提供了以下3个类。

• AtomicReference：原子更新引用类型。
• AtomicReferenceFieldUpdater：原子更新引用类型里的字段。
• AtomicMarkableReference：原子更新带有标记位的引用类型。可以原子更新一个布尔类型的标记位和引用类型。

如果需原子地更新某个类里的某个字段时，就需要使用原子更新字段类，Atomic包提供 了以下3个类进行原子字段更新。

• AtomicIntegerFieldUpdater：原子更新整型的字段的更新器。
• AtomicLongFieldUpdater：原子更新长整型字段的更新器。
• AtomicStampedReference：原子更新带有版本号的引用类型。该类将整数值与引用关联起 来，可用于原子的更新数据和数据的版本号，可以解决使用CAS进行原子更新时可能出现的 ABA问题。