进程与线程概念

在现代操作系统中，进程支持多线程。

• 进程是资源管理的最小单元，
• 线程是程序执行的最小单元。

线程作为调度和分配的基本单位，进程作为资源分配的基本单位。

一个进程的组成实体可以分为两大部分：线程集和资源集。进程中的线程是动态的对象；代表了进程指令的执行。资源，包括地址空间、打开的文件、用户信息等等，由进程内的线程共享。

多道程序设计模型

计算机采用多道程序设计模型可以显著提高CPU的利用率。

多进程与多线程

多进程：并行实体之间不共享同一个地址空间和所有可用数据。
多线程：并行实体之间共享同一个地址空间和所有可用数据。
1、线程比进程更加轻量级，线程的创建、切换等过程比进程开销小，线程的通信比进程间的通信简单。
2、进程的安全性高于线程，因为不共享。

多线程的实现方式

• 内核线程实现
• 用户线程实现
• 用户线程加轻量级进程混合实现

Java线程实现在linux和windows平台上均采用的是内核线程实现，Java线程与内核线程为一比一的对应关系，也就是说Java线程由内核直接调度。

多线程面临的挑战

• 线程通信
• 上下文切换
• 死锁
• 资源限制
• 线程安全

线程通信

多线程相当于是多个线程为了完成一件“大事”而协同工作，那这多个线程之间如何协同就是线程通信的问题了。
线程间的通信是多线程编程的基础，线程间通信方式有两种：共享内存和消息传递。Java线程间的通信机制为共享内存方式。
线程间通信就要保证通信的可靠性，确保信息的可靠传递。这就涉及到线程安全的问题。

线程安全

线程安全最核心的概念是正确性。

在操作系统中，正确性是指多个线/进程读写共享数据，最后的结果与线/进程运行的精准时序无关，亦即不存在竞争条件。
在Java中，正确性是指：某个类的行为与其规范完全一致。当多个线程访问某个类时，不管运行时环境采用何种调度方式或者这些线程将如何交替执行，并且在主调代码中不需要任何额外的同步或协同，这个类都能表现出正确的行为，那么就称这个类是线程安全的。

可以将Java线程安全按由强到弱分为5类，同时也可以看到线程安全的责任由对象本身向调用者的转移：

1. 不可变
   不可变对象一定是线程安全的，无论是对象的方法还是方法的调用者，都不需要再采取任何的线程安全保障措施。（final关键字的使用）
2. 绝对线程安全
   不管运行时环境如何，调用者都不需要任何额外的同步措施。这个要求非常严格，Java API中大多数都不是绝对线程安全的类。
3. 相对线程安全
   保证对某个对象的单独操作是线程安全的，在调用的时候不需要做额外的同步措施。但是对于同一个对象的特定顺序的连续调用，可能需要在调用端做额外的同步手段（多为扩大同步范围）来保证调用的正确性。Java中大部分线程安全类属于相对线程安全。
4. 线程兼容
   对象本身不是线程安全的，但是可以通过在调用端正确地使用同步手段来保证对象在并发环境下的线程安全性。Java中的普通类。
5. 线程对立
   无论调用端是否采取了同步措施，都无法在并发环境中使用。

多线程编程的出发点

并发编程的基本出发点：先保证正确性，再提高效率。

保证正确性有三种方式：

• 互斥同步
• 非阻塞同步
• 无同步方案

互斥同步由互斥量（操作系统级或者Java语言级）支持，非阻塞同步由CAS指令支持，无同步方案为可重入代码和Java中的ThreadLocal变量。

提高效率中很重要的方式有重排序和减少上下文切换等。

---

互斥同步

先来看一个最基础的支撑技术。

原子操作

原子（atom）本意是“不能被进一步分割的最小粒子”，而原子操作（atomic operation）意为”不可被中断的一个或一系列操作” 。如有些场景下需要将读取变量值，再修改其值，再写入内存合并为一个原子操作完成。

intel处理器使用基于对缓存加锁和总线加锁的方式来实现多处理器之间的原子操作。
总线加锁：使用处理器提供的lock#信号，当一个处理器在总线上输出此信号时，其他处理器的请求将被阻塞，该处理器可以独占共享内存。
缓存加锁：内存区域如果被缓存在处理器的缓存行中，并且在lock操作期间被锁定，那么当处理器执行锁操作回写到内存时，处理器修改内部的内存地址，通过缓存一致性协议来保证操作的原子性和可见性。缓存一致性协议会阻止同时修改由两个一上处理器缓存的内存数据，当处理器回写被锁定的缓存行的数据时，会使其他处理器的缓存行失效，其他处理器在下次读取时将重新从共享内存中读取。
可以看出原子操作的同时也提供了可见性。

再看操作系统如何保证正确性。

临界区

对共享内存进行访问的程序片段成为临界区。
如果可以协调多线/进程不可能同时处于临界区，就能避免竞争条件（即互斥），从而保证正确性。同时在协调机制中也尽可能要求高效，一个好的协调方案，要满足以下4个条件：

• 任何两个进/线程不能同时处于临界区
• 不应对CPU的速度和数量做任何假设（单核、多核、超线程）
• 临界区外运行的进/线程不得阻塞其他进/线程
• 不得使进/线程无限期等待进入临界区

其中前两个条件是对正确性的保证，后两个条件是对效率的保证。

互斥

在原子操作的支撑下，有多种方案可以实现互斥。大体分为两类：

类别	原理	优点	缺点	使用场景
忙等待	定义共享变量，设定某个值表示是否有线程进入临界区。如果已有线程进入，则各线程对该变量进行轮询，自旋等待，直到进入临界区	CPU自旋等待，如果短期内能进入临界区，避免了线程阻塞和上下文切换带来的开销	CPU空转，同时存在优先级反转问题	在有理由认为等待时间是非常短的情况下使用
等待/通知机制	一样定义共享变量，但是如果已有线程进入，则后面的线程将阻塞，当之前的线程出临界区时通知等待的线程进入临界区执行。	不会出现CPU空转，CPU占用极高的情况	线程阻塞将带来线程切换上下文的开销	临界区竞争激烈，且执行时间较长的情况下使用

表格中的共享变量既可以使用信号量也可以使用互斥量，一般使用互斥量。

条件变量

当仅有互斥量时且有线程在临界区时，其他线程将在互斥量上等待，然而很多情况下线程的执行不仅需要进入临界区，而且还需要满足一些其他的条件，当条件不满足时进入临界区线程不能继续执行也没有什么意义。这时候就需要条件变量了。

这时，一个线程运行需要条件变量满足，并且能锁住互斥量。如果锁住了互斥量，然而需要在某个条件变量上等待，线程将释放互斥量（给别的线程机会），进入阻塞态，等待其他线程在条件变量上唤醒自己，转入就绪态继续竞争互斥量。

管程（Monitor）

通过互斥量、条件变量以及相关的原子操作即可保证多线程通信的正确性，不过在多线程中，存在发送给变量的信号可能会丢失的情况，还有可能会出现死锁的情况，如果直接面向这些量编写多线程程序，会不可避免的出现各种奇奇怪怪的问题。为了简化多线程程序的编写，管程出现了。

管程实际上可以理解为是对互斥量、条件变量、以及组织协调多线程进入临界区算法的一个封装。高层代码只需要临界区交给管程管理就好了，管程会保证正确性。

JVM中管程与经典管程有本质区别：Java没有内嵌的条件变量。Java将等待/通知机制提出来作为wait()/notify()供程序员自定义使用，自定义条件变量（如某个对象）。

非阻塞方案

互斥同步最主要的问题就是进行线程阻塞和唤醒带来的性能问题。是一种悲观的同步方案：不管有没有竞争，都要加解锁。
非阻塞方案是一种基于冲突检测的乐观方案：先进行操作，如果没有竞争，则操作就成功了；如果有竞争，产生了冲突，则采取补偿措施（一般即为不断尝试直到成功），这种方案并不需要阻塞线程。

CMPXCHG指令，该指令是原子操作。简单理解，cmpxchg指令接受两个参数，一个是将要修改的变量的预期值，一个是修改值，指令比较预期值与变量的实际值是否一致，如果一致则将修改值赋值给变量。否则不做修改。
由于这个指令是主动比较，一般会放到自旋中，适用于冲突比较少的场景。

无同步方案

如果方法中不涉及共享数据，那么该方法不需要做任何同步。

1. 可重入代码
   可重入代码的特征如不依赖公共数据，不调用非可重入代码等，可重入代码中多为局部变量，不与其他代码共享，也就不存在数据竞争了。
2. 线程本地存储–ThreadLocal

---

重排序

再看提高执行效率的方式：指令重排序。
重排序分三种：1.编译器优化的重排序。2.指令级并行的重排序。3.内存系统的重排序

单线程重排序

数据依赖

如果两个操作访问同一个变量，且两个操作中有一个为写操作（读写/写读/写写），此时这两个操作之间存在数据依赖性。如果对存在数据依赖性的操作重排序，程序执行结果将会改变。因此，编译器和处理器不会改变存在数据依赖性的操作的执行顺序。

as-if-serial模型

as-if-serial：不管怎么重排序，单线程执行的结果不能被改变。
1、对存在数据依赖性的操作重排序非法。
2、对不存在数据依赖性的操作是否重排序不做要求。
as-if-serial为单线程提供了顺序执行的保证。

多线程重排序

冲突访问

多线程中，对同一个共享字段或者数组元素存在两个访问（读或写），且至少有一个访问为写操作，称之为有冲突。

数据竞争

• 冲突访问
• 读写操作没有通过同步来排序

当上述情况发生时，就存在数据竞争。代码中出现数据竞争时，常有可能会出现有违直觉的结果。
那么如何判断程序有没有正确的同步呢？
一个程序是正确同步的：当且仅当所有顺序一致的执行过程中都不存在数据竞争。不论调度系统如何调度，所有可能的执行顺序序列下，都不存在数据竞争。

那么应该如何来组织多线程程序的同步排序呢？

内存模型

给定一个程序和该程序的一串执行轨迹，内存模型描述了该执行轨迹是否是该程序的一次合法执行。内存模型检查执行轨迹中的每次读操作，然后根据特定规则，检验该读操作观察到的写是否合法。
内存模型的一个高级、非正式的概述显示其是一组规则，规定了一个线程的写操作何时会对另一个线程可见。

顺序一致性模型

顺序一致性是程序执行过程中 可见性和顺序的强有力保证。

• 有序性
• 原子性
• 可见性

有序性：在顺序一致的执行过程中，所有动作（如读和写）间存在一个全序关系，与程序的顺序一致。
原子性和可见性：每个动作都是原子的并且立即对所有线程可见。

顺序一致性模型是一个理论参考模型，它在提供了极强的操作有序性、原子性和可见性的同时，使编译器和处理器优化（比如重排序）不再合法。

happens-before规则

JSR-133中对happens-before的定义：
1. 如果一个操作happens-before另一个操作，那么第一个操作的执行结果将对第二个操作可见，并且第一个操作的执行顺序排在第二个操作之前。（有序性和可见性）
2. 两个操作之间存在happens-before关系，并不意味着java平台的具体实现必须要按照happens-before关系指定的顺序来执行。只要结果与按照happens-before关系来执行的一致，编译器和处理器的重排序是合法的。（最大限度的减少对编译器和处理器优化的约束）

1. 程序顺序规则
   在一个线程内，按照程序代码顺序，书写在前面的操作happens-before书写在后面的操作。
2. 管程锁规则
   一个unlock操作happens-before后面对同一个锁的lock操作。
3. volatile变量规则
   对一个volatile变量的写操作happens-before后面对这个变量的读操作。
4. 线程启动规则
   Thread对象的start()方法happens-before此线程的每一个动作。
5. 线程终止规则
   线程中所有操作都happens-before对此线程的终止检测。
6. 线程中断规则
   对线程interrupt()方法的调用happens-before被中断线程的代码检测到中断事件的发生。
7. 对象终结规则
   一个对象的初始化完成（构造函数执行完毕）happens-before它的finalize()方法。
8. 传递性
   A happens-before B,B happens-before C,s.t. A happens-before C.

注意：

• happens-before首先强调了前一个操作对后一个操作的顺序和可见性，但是同时又没有限定具体实现，只要求执行结果要与happens-before一致。那么在实际的代码执行中，happens-before和代码时间上的先行发生并没有直接关系。
• happens-before允许违反因果关系的事情发生。（比如：out of thin air）

happens-before和as-if-serial

• as-if-serial保证单线程内程序的执行结果不被改变。向上向程序员保证程序执行顺序，向下约束编译器和处理器重排序的规则。
• happens-before关系保证正确同步的多线程程序的执行结果不被改变。向上向程序员保证正确同步的多线程程序的执行结果正确性，向下约束编译器和处理器重排序的规则。

---

顺序一致性模型不允许重排序-过于严格，happens-before允许违反因果关系的事情发生-过于宽松，都不适合作为Java内存模型。

Java内存模型

1. Java线程间的通信机制，JMM决定一个线程对共享变量的写入何时对另外一个线程可见。
2. 屏蔽各种硬件和操作系统的内存访问差异，实现java跨平台的一致的内存访问效果
3. 向上向程序员保证正确同步的程序具有顺序一致性
4. 向下向编译器和处理器提供尽可能宽松的重排序约束规则
5. 在happens-before的基础上提供了对因果关系的充分保证

从抽象的角度来看，JMM定义了线程和主内存之间的抽象关系：线程之间的共享变量存储在主内存中，每个线程都有一个私有的本地内存，本地内存中存储了该线程读写共享变量的副本。本地内存是JMM的一个抽象概念，实际并不存在，它涵盖了缓存、寄存器以及其他的硬件和编译器优化。
同时定义了工作内存与主内存的交互操作协议：lock、unlock、read、load、use、assign、store、write共8种原子性操作以及它们之间的操作规则。

Java内存模型的特征

Java内存模型建立在解决三个并发问题的基础上。

• 原子性
• 可见性
• 有序性

对于原子性的保证：有read、load、use、assign、store、write这类数据访问的基本原子性操作，更大范围的可以用lock和unlock操作来保证。
对于可见性的保证：Java内存模型通过主内存作为可见性实现的媒介。写操作刷新回主内存，读操作重新读主内存实现前一个操作对后一个操作的可见性。
对于有序性的保证：happens-before规则保证基本操作的有序性，通过同步来保证其他操作的有序性。

下一篇讲解Java内存模型的具体实现，看Java如何在允许指令重排序的情况下保证正确同步。

现代操作系统
Java并发编程的艺术
深入理解Java虚拟机
Java并发编程实战
JSR-133
并发编程网

JAVA代码在编译后会变成字节码，字节码被类加载器加载到JVM中，JVM执行字节码，最终需要转化为汇编指令在CPU上执行，JAVA中所使用的并发机制依赖于JVM的实现和CPU的指令。

->参考《JAVA并发编程的艺术》

1.volatile的应用

volatile是轻量级的synchronized，它只是用来保证共享变量的可见性，不能保证操纵的原子性。

【引申】–>volatile如何实现内存可见性？

• 深入的说，通过加入内存屏障和禁止重排序优化实现的。
• 对volatile变量执行写操作时，会在写操作后加入一条store屏障指令。
• 对volatile变量执行读操作时，会在读操作前加入一条load屏障指令。

1.1—volatile保证共享变量可见性

有volatile修饰的变量进行写操作的时候会多出一行汇编代码，该行代码会有一个lock指令。

volatile的两条实现原则：

①： Lock前缀指令会引起处理器缓存会写到内存（使处理器独占任何共享内存）。

②：一个处理器的缓存回写会导致其他处理器的缓存无效。

2.synchronized的实现原理和应用

⑴ synchronized实现同步的基础：

①:对于普通方法，锁是当前实例对象。

②：对于静态同步方法，锁是class对象。

③：同步方法块，锁是synchronized后面括号里的对象。

⑵ JVM规范中的实现原理

JVM基于进入和退出Monitor对象实现方法同步和代码块的同步。

⑶Mark Word标记位

synchronized用到的锁是放在JAVA对象头里面的，其中有个Mark Word来存储对象的hashcode、分代年龄和锁标记位，其中锁标记位会产生变化，对应的不同的标记，我们的锁有3种：轻量级锁、重量级锁、偏向锁。

⑷锁的升级与对比

从SE 1.6开始，锁一共有四种状态：无锁状态、偏向锁状态、轻量级锁状态、重量级锁状态。

①：偏向锁

引入原因：大多数情况下，锁仅有某一线程多次获得，为了使获得锁的代价更低而引入偏向锁。

偏向锁的设置：当某一线程访问同步块时，会在对象头和栈帧中的琐记录里存储锁偏向的线程ID，以后该线程在进入该同步块的时候，不需要再次使用CAS原子操作进行加锁和解锁，只需要简单的测试一下对象头中的Mark Word是否存在指向当前线程的偏向锁。如果测试成功，则表示获得锁，否则检测是否设置有偏向锁，如果没有，则使用CAS竞争锁，否则偏向锁指向该线程。

偏向锁的关闭：在6和7中是默认采用的，可以通过JVM参数关闭：UseBiaseLocking=false，此时程序进入轻量级锁的状态。

②：轻量级锁

加锁：线程执行同步块之前，会在线程私有的栈帧中开辟用于存储锁记录的空间，称为Displaced Mark Word。然后线程尝试将对象Mark Word的替换为指向Displaced Mark Word记录的指针，如果成功，那么当前线程获得锁，如果失败，那么使用自旋获得锁。

何为自旋？

轻量级锁解锁： 使用原子的CAS操作将Displaced Mark Word 替换回对象头，如果成功，表示没有竞争发生，否则，说明当前锁存在竞争（从上图可以看出，竞争锁的线程一直在尝试修改Mark Word，这肯定存在竞争），锁就会膨胀成重量级的锁。

因为自旋会消耗CPU，为了避免太多无用的自旋，一旦锁膨胀成重量级的锁，便不会再恢复到轻量级的锁的状态。当锁处于这个状态下，其他线程试图获取锁时就被阻塞住。当锁释放时再唤醒这些线程。此时醒来的线程就会进行一轮新的竞争。

三种锁的比较：

锁	优点	缺点	使用场景
偏向锁	加锁和解锁不需要额外的消耗，和执行非同步方法之间存在纳秒级的差距	线程间存在锁的竞争，会带来额外的锁撤销的消耗	适用于只有一个线程访问同步块的场景
轻量级锁	竞争的线程不会阻塞，提高程序的响应速度	自旋消耗CPU	追求响应时间，同步块执行速度快
重量级锁	线程竞争不使用自旋，不消耗CPU	线程阻塞，响应时间慢	追求吞吐量，同步块执行速度较长

3.原子操作的实现原理

⑴处理器实现原子操作的机制：

第一机制：总线锁（声言Lock信号）

第二机制共享缓存锁（修改内存地址，缓存一致性机制：阻止同时修改由2个以上的处理器缓存的内存区域数据）。

⑵JAVA实现原子操作的机制

第一个是循环CAS：JVM中的CAS操纵是利用了处理器提供的CMPXCHG指令实现的。自旋CAS的基本思路是循环进行CAS操作，直到CAS操作成功了为止。

⑶使用锁机制实现原子操作

锁机制保证只有获得锁的线程才能够操作锁定的内存区域。注意：除了偏向锁，JVM实现锁的方式都用了循环CAS操作（使用循环CAS获取锁，使用循环CAS释放锁）。

前言：

Java 代码在编译后会变成 Java 字节码，字节码被类加载器加载到 JVM 里，JVM 执行字节码，最终需要转化为汇编指令在 CPU 上执行，Java 中所使用的并发机制依赖于 JVM 的实现和 CPU 的指令。本章我们将深入底层一起探索下 Java 并发机制的底层实现原理。

一、volatile 的应用

在多线程并发编程中synchronized和volatile都扮演着重要的角色volatile是轻量级的synchronized，它在多处理器开发中保证了共享变量的“可见性”。可见性的意思是当一个线程修改一个共享变量时，另外一个线程能读到这个修改的值。

如果volatile变量修饰符使用恰当的话，它比synchronized的使用和执行成本更低，因为它不会引起线程上下文的切换和调度。

1.1 volatile 的定义与实现原理

Java 语言规范第3版中对volatile的定义如下：

Java 编程语言允许线程访问共享变量，为了确保共享变量能被准确和一致地更新，线程应该确保通过排他锁单独获得这个变量。

Java 语言提供了volatile，在某些情况下比锁要更加方便。如果一个字段被声明成volatile，Java 线程内存模型确保所有线程看到这个变量的值是一致的。

在了解volatile实现原理之前，我们先来看下与其实现原理相关的CPU术语与说明。

术语	英文单词	术语描述
内存屏障	memory barriers	是一组处理器指令，用于实现对内存操作的顺序限制。
缓冲行	cache line	缓存中可以分配的最小存储单位，处理器填写缓存行时会加载整个缓存行，需要使用多个主内存读周期。
原子操作	atomic operation	不可中断的一个或一系列操作。
缓存行填充	cache line fill	当处理器识别到从内存中读取操作数是可缓存的，处理器读取整个缓存行到适当的缓存（L1，L2，L3 的或所有）。
缓存命中	cache hit	如果进行高速缓存行填充操作的内存位置仍然是下次处理器访问的地址时，处理器从缓存中读取操作数，而不是从内存读取。
写命中	write hit	当处理器将操作数写回到一个内存缓存的区域时，它首先会检查这个缓存的内存地址是否在缓存行中，如果存在一个有效的缓存行，则处理器将这个操作数写回到缓存，而不是写回到内存。
写缺失	write misses the cache	一个有效的缓存行被写入到不存在的内存区域。

volatile 是如何来保证可见性的呢？让我们在 X86 处理器下通过工具获取 JIT 编译器生成的汇编指令来查看对 volatile 进行写操作时，CPU 会做什么事情。

Java代码如下。

instance = new Singleton(); // instance是volatile变量

转变成汇编代码，如下。

0x01a3de1d: movb $0×0,0×1104800(%esi);0x01a3de24: lock addl $0×0,(%esp);

有volatile变量修饰的共享变量进行写操作的时候会多出第二行汇编代码，通过查 IA-32 架构软件开发者手册可知，Lock 前缀的指令在多核处理器下会引发了两件事情。

1. 将当前处理器缓存行的数据写回到系统内存。
2. 这个写回内存的操作会使在其他CPU里缓存了该内存地址的数据无效。

为了提高处理速度，处理器不直接和内存进行通信，而是先将系统内存的数据读到内部缓存（L1，L2或其他）后再进行操作，但操作完不知道何时会写到内存。

如果对声明了volatile的变量进行写操作，JVM 就会向处理器发送一条 Lock 前缀的指令，将这个变量所在缓存行的数据写回到系统内存。

但是，就算写回到内存，如果其他处理器缓存的值还是旧的，再执行计算操作就会有问题。所以，在多处理器下，为了保证各个处理器的缓存是一致的，就会实现缓存一致性协议，每个处理器通过嗅探在总线上传播的数据来检查自己缓存的值是不是过期了，当处理器发现自己缓存行对应的内存地址被修改，就会将当前处理器的缓存行设置成无效状态，当处理器对这个数据进行修改操作的时候，会重新从系统内存中把数据读到处理器缓存里。

volatile的两条实现原则：

1. Lock前缀指令会引起处理器缓存回写到内存。
2. 一个处理器的缓存回写到内存会导致其他处理器的缓存无效。

1.2 volatile 的使用优化

著名的 Java 并发编程大师 Doug lea 在 JDK 7 的并发包里新增一个队列集合类LinkedTransferQueue，它在使用volatile变量时，用一种追加字节的方式来优化队列出队和入队的性能。

LinkedTransferQueue的代码如下。

/** 队列中的头部节点 */
private transient final PaddedAtomicReference<QNode> head;
/** 队列中的尾部节点 */
private transient final PaddedAtomicReference<QNode> tail;
static final class PaddedAtomicReference<T> extends AtomicReference T>{
    // 使用很多4个字节的引用追加到64个字节
    Object p0, p1, p2, p3, p4, p5, p6, p7, p8, p9, pa, pb, pc, pd, pe;
    PaddedAtomicReference(T r) {
        super(r);
    }
}
public class AtomicReference<V> implements java.io.Serializable {
    private volatile V value;
    // 省略其他代码
}

让我们先来看看LinkedTransferQueue这个类，它使用一个内部类类型来定义队列的头节点（head）和尾节点（tail），而这个内部类PaddedAtomicReference相对于父类AtomicReference只做了一件事情，就是将共享变量追加到 64 字节。我们可以来计算下，一个对 象的引用占 4 个字节，它追加了 15 个变量（共占 60 个字节），再加上父类的 value 变量，一共 64 个字节。

为什么追加64字节能够提高并发编程的效率呢？

因为对于英特尔酷睿i7、酷睿、Atom 和 NetBurst，以及 Core Solo 和Pentium M 处理器的 L1、L2 或 L3 缓存的高速缓存行是 64 个字节宽，不支持部分填充缓存行，这意味着，如果队列的头节点和尾节点都不足 64 字节的话，处理器会将它们都读到同一个高速缓存行中，在多处理器下每个处理器都会缓存同样的头、尾节点，当一 个处理器试图修改头节点时，会将整个缓存行锁定，那么在缓存一致性机制的作用下，会导致其他处理器不能访问自己高速缓存中的尾节点，而队列的入队和出队操作则需要不停修改头节点和尾节点，所以在多处理器的情况下将会严重影响到队列的入队和出队效率。

Doug lea 使用追加到64字节的方式来填满高速缓冲区的缓存行，避免头节点和尾节点加载到同一个缓存行，使头、尾节点在修改时不会互相锁定。

那么是不是在使用volatile变量时都应该追加到64字节呢？

不是的。在两种场景下不应该使用这种方式。

1. 缓存行非 64 字节宽的处理器。

   如 P6 系列和奔腾处理器，它们的 L1 和 L2 高速缓存行是 32 个字节宽。

2. 共享变量不会被频繁地写。

   因为使用追加字节的方式需要处理器读取更多的字节到高速缓冲区，这本身就会带来一定的性能消耗，如果共享变量不被频繁写的话，锁的几率也非常小，就没必要通过追加字节的方式来避免相互锁定。

不过这种追加字节的方式在 Java 7 下可能不生效，因为 Java 7 变得更加智慧，它会淘汰或重新排列无用字段，需要使用其他追加字节的方式。

二、synchronized 的实现原理与应用

Java 中的每一个对象都可以作为锁。具体表现 为以下 3 种形式。

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

当一个线程试图访问同步代码块时，它首先必须得到锁，退出或抛出异常时必须释放锁。

那么锁到底存在哪里呢？锁里面会存储什么信息呢？

从 JVM 规范中可以看到synchonized在 JVM 里的实现原理，JVM 基于进入和退出Monitor对象来实现方法同步和代码块同步，但两者的实现细节不一样。代码块同步是使用monitorenter和monitorexit指令实现的，而方法同步是使用另外一种方式实现的，细节在 JVM 规范里并没有详细说明。但是，方法的同步同样可以使用这两个指令来实现。

monitorenter指令是在编译后插入到同步代码块的开始位置，而monitorexit是插入到方法结束处和异常处，JVM 要保证每个monitorenter必须有对应的monitorexit与之配对。任何对象都有一个monitor与之关联，当且一个monitor被持有后，它将处于锁定状态。线程执行到monitorenter指令时，将会尝试获取对象所对应的monitor的所有权，即尝试获得对象的锁。

2.1 Java 对象头

synchronized用的锁是存在 Java 对象头里的。如果对象是数组类型，则虚拟机用 3 个字宽 （Word）存储对象头，如果对象是非数组类型，则用 2 字宽存储对象头。在 32 位虚拟机中，1 字宽等于 4 字节，即 32bit。

Java 对象头的长度：

长度	内容	说明
32/64bit	Mark Word	存储对象的 hashCode 或锁信息
32/64bit	Class Metadata Address	存储到对象类型数据的指针
32/64bit	Array length	数组的长度（如果当前对象是数组）

Java 对象头里的 Mark Word 里默认存储对象的 hashCode、分代年龄和锁标记位。32位 JVM 的 Mark Word 的默认存储结构如表所示。

Java 对象头的存储结构：

锁状态	25bit	4bit	1bit 是否是偏向锁	2bit 锁标志位
无锁状态	对象的 hashCode	对象分代年龄	0	01

在运行期间，Mark Word 里存储的数据会随着锁标志位的变化而变化。Mark Word可能变化为存储以下4种数据，如表所示。

Mark Word 的状态变化：

在64位虚拟机下，Mark Word是64bit大小的，其存储结构如表所示。

Mark Word 的存储结构：

2.2 锁的升级与对比

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

2.2.1 偏向锁

大多数情况下，锁不仅不存在多线程竞争，而且总是由同一线程多次获得，为了让线程获得锁的代价更低而引入了偏向锁。

当一个线程访问同步块并获取锁时，会在对象头和栈帧中的锁记录里存储锁偏向的线程ID，以后该线程在进入和退出同步块时不需要进行 CAS 操作来加锁和解锁，只需简单地测试一下对象头的 Mark Word 里是否存储着指向当前线程的偏向锁。如果测试成功，表示线程已经获得了锁。如果测试失败，则需要再测试一下 Mark Word 中偏向锁的标识是否设置成1（表示当前是偏向锁）：如果没有设置，则使用CAS竞争锁；如果设置了，则尝试使用 CAS 将对象头的偏向锁指向当前线程。

1. 偏向锁的撤销

   偏向锁使用了一种等到竞争出现才释放锁的机制，所以当其他线程尝试竞争偏向锁时，持有偏向锁的线程才会释放锁。

   偏向锁的撤销，需要等待全局安全点（在这个时间点上没有正在执行的字节码）。它会首先暂停拥有偏向锁的线程，然后检查持有偏向锁的线程是否活着，如果线程不处于活动状态，则将对象头设置成无锁状态；如果线程仍然活着，拥有偏向锁的栈会被执行，遍历偏向对象的锁记录，栈中的锁记录和对象头的 Mark Word 要么重新偏向于其他线程，要么恢复到无锁或者标记对象不适合作为偏向锁，最后唤醒暂停的线程。

   图中的线程 1 演示了偏向锁初始化的流程，线程 2 演示了偏向锁撤销的流程。

   

2. 关闭偏向锁

   偏向锁在 Java 6 和 Java 7 里是默认启用的，但是它在应用程序启动几秒钟之后才激活，如有必要可以使用 JVM 参数来关闭延迟：-XX:BiasedLockingStartupDelay=0。如果你确定应用程序里所有的锁通常情况下处于竞争状态，可以通过JVM参数关闭偏向锁：-XX:-UseBiasedLocking=false，那么程序默认会进入轻量级锁状态。

2.2.2 轻量级锁

1. 轻量级加锁

   线程在执行同步块之前，JVM 会先在当前线程的栈桢中创建用于存储锁记录的空间，并将对象头中的 Mark Word 复制到锁记录中，官方称为 Displaced Mark Word。然后线程尝试使用 CAS 将对象头中的 Mark Word 替换为指向锁记录的指针。如果成功，当前线程获得锁，如果失败，表示其他线程竞争锁，当前线程便尝试使用自旋来获取锁。

2. 轻量级锁解锁

   轻量级解锁时，会使用原子的 CAS 操作将 Displaced Mark Word 替换回到对象头，如果成功，则表示没有竞争发生。如果失败，表示当前锁存在竞争，锁就会膨胀成重量级锁。

   下图是两个线程同时争夺锁，导致锁膨胀的流程图。

   
   因为自旋会消耗CPU，为了避免无用的自旋（比如获得锁的线程被阻塞住了），一旦锁升级成重量级锁，就不会再恢复到轻量级锁状态。当锁处于这个状态下，其他线程试图获取锁时，都会被阻塞住，当持有锁的线程释放锁之后会唤醒这些线程，被唤醒的线程就会进行新一轮的夺锁之争。

2.2.3 锁的优缺点对比

锁	优点	缺点	适用场景
偏向锁	加锁和解锁不需要额外的消耗，和执行非同步方法相比仅存在纳秒级的差距。	如果线程间存在锁竞争，会带来额外的锁撤销的消耗。	适用于只有一个线程访问同步块场景。
轻量级锁	竞争的线程不会阻塞，提高了程序的响应速度。	如果始终得不到锁竞争的线程，使用自旋会消耗CPU。	追求响应时间，同步块执行速度非常快。
重量级锁	线程竞争不使用自旋，不会消耗CPU	线程阻塞，响应时间缓慢。	追求吞吐量，同步块执行速度较长。

2.3 原子操作的实现原理

原子（atomic）本意是“不能被进一步分割的最小粒子”，而原子操作（atomic operation）意为“不可被中断的一个或一系列操作”。在多处理器上实现原子操作就变得有点复杂。让我们一起来聊一聊在Intel处理器和Java里是如何实现原子操作的。

2.3.1 CPU 术语定义

术语名称	英文	解释
缓存行	Cache line	缓存的最小单位
比较并交换	Compare and Swap	CAS 操作需要输入两个值，一个旧值（期望操作前的值）和一个新值，在操作期间先比较旧值有没有发生变化，才交换成新值，发生了变化则不交换。
CPU 流水线	CPU pipeline	CPU 流水线的工作方式就像工业生产上的装配流水线，在 CPU 中由 5 ~ 6 个不同功能的电路单元组成一条指令处理流水线，然后将一条 X86 指令分成 5 ~ 6 步后再由这些电路单元分别执行，这样就能实现在一个 CPU 时钟周期完成一条指令，因此提高 CPU 的运算速度。
内存顺序冲突	Memory order violation	内存顺序冲突一般是由假共享引起的，假共享是指多个 CPU 同时修改同一个缓存行的不同部分而引起其中一个 CPU 的操作无效，当出现这个内存顺序冲突时，CPU 必须清空流水线。

2.3.2 处理器如何实现原子操作

1. 使用总线锁保证原子性

   如果多个处理器同时对共享变量进行读改写操作（i++ 就是经典的读改写操作），那么共享变量就会被多个处理器同时进行操作，这样读改写操作就不是原子的，操作完之后共享变量的值会和期望的不一致。举个例子，如果 i=1，我们进行两次 i++ 操作，我们期望的结果是 3，但是有可能结果是 2，如图所示。

   
   原因可能是多个处理器同时从各自的缓存中读取变量 i，分别进行加 1 操作，然后分别写入系统内存中。那么，想要保证读改写共享变量的操作是原子的，就必须保证 CPU1 读改写共享变量的时候，CPU2 不能操作缓存了该共享变量内存地址的缓存。

   处理器使用总线锁就是来解决这个问题的。所谓总线锁就是使用处理器提供的一个 LOCK＃信号，当一个处理器在总线上输出此信号时，其他处理器的请求将被阻塞住，那么该处理器可以独占共享内存。

2. 使用缓存锁保证原子性

   在同一时刻，我们只需保证对某个内存地址的操作是原子性即可，但总线锁定把 CPU 和内存之间的通信锁住了，这使得锁定期间，其他处理器不能操作其他内存地址的数据，所以总线锁定的开销比较大，目前处理器在某些场合下使用缓存锁定代替总线锁定来进行优化。

   频繁使用的内存会缓存在处理器的 L1、L2 和 L3 高速缓存里，那么原子操作就可以直接在处理器内部缓存中进行，并不需要声明总线锁，在 Pentium 6 和目前的处理器中可以使用 “缓存锁定” 的方式来实现复杂的原子性。

   所谓 “缓存锁定” 是指内存区域如果被缓存在处理器的缓存行中，并且在 Lock 操作期间被锁定，那么当它执行锁操作回写到内存时，处理器不在总线上声言 LOCK＃信号，而是修改内部的内存地址，并允许它的缓存一致性机制来保证操作的原子性，因为缓存一致性机制会阻止同时修改由两个以上处理器缓存的内存区域数据，当其他处理器回写已被锁定的缓存行的数据时，会使缓存行无效，在如图所示的例子中，当 CPU1 修改缓存行中的 i 时使用了缓存锁定，那么 CPU2 就不能同时缓存 i 的缓存行。

   但是有两种情况下处理器不会使用缓存锁定。

   第一种情况是：当操作的数据不能被缓存在处理器内部，或操作的数据跨多个缓存行（cache line）时，则处理器会调用总线锁定。

   第二种情况是：有些处理器不支持缓存锁定。对于 Intel 486 和 Pentium 处理器，就算锁定的内存区域在处理器的缓存行中也会调用总线锁定。

针对以上两个机制，我们通过 Intel 处理器提供了很多 Lock 前缀的指令来实现。例如，位测试和修改指令：BTS、BTR、BTC；交换指令 XADD、CMPXCHG，以及其他一些操作数和逻辑指令（如ADD、OR）等，被这些指令操作的内存区域就会加锁，导致其他处理器不能同时访问它。

2.3.3 Java如何实现原子操作

1. 使用循环 CAS 实现原子操作

   JVM 中的 CAS 操作正是利用了处理器提供的 CMPXCHG 指令实现的。自旋 CAS 实现的基本思路就是循环进行 CAS 操作直到成功为止，以下代码实现了一个基于 CAS 线程安全的计数器方法 safeCount 和一个非线程安全的计数器 count。

   public class Counter {
   
       private final AtomicInteger atomicI = new AtomicInteger(0);
       private int i = 0;
   
       public static void main(String[] args) {
           final Counter cas = new Counter();
           List<Thread> ts = new ArrayList<>(600);
           long start = System.currentTimeMillis();
           for (int j = 0; j < 100; j++) {
               Thread t = new Thread(() -> {
                   for (int i = 0; i < 10000; i++) {
                       cas.count();
                       cas.safeCount();
                   }
               });
               ts.add(t);
           }
           for (Thread t : ts)
               t.start();
           for (Thread t : ts)
               try {
                   t.join();
               } catch (InterruptedException e) {
                   e.printStackTrace();
               }
           System.out.println(cas.i); // 984453（不确定）
           System.out.println(cas.atomicI.get()); // 1000000
           System.out.println(System.currentTimeMillis() - start); // 173（不确定）
       }
   
       /**
        * 使用CAS实现线程安全计数器
        */
       private void safeCount() {
           while (true) {
               int i = atomicI.get();
               boolean suc = atomicI.compareAndSet(i, ++i);
               if (suc)
                   break;
           }
       }
   
       /**
        * 非线程安全计数器
        */
       private void count() {
           i++;
       }
   
   }
   

   从 Java 1.5 开始，JDK 的并发包里提供了一些类来支持原子操作，如 AtomicBoolean（用原子方式更新的 boolean 值）、AtomicInteger（用原子方式更新的 int 值）和 AtomicLong（用原子方式更新的 long 值）。这些原子包装类还提供了有用的工具方法，比如以原子的方式将当前值自增 1 和自减 1。

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

   ABA 问题：

   因为 CAS 需要在操作值的时候，检查值有没有发生变化，如果没有发生变化则更新，但是如果一个值原来是 A，变成了 B，又变成了 A，那么使用 CAS 进行检查时会发现它的值没有发生变化，但是实际上却变化了。

   ABA 问题的解决思路就是使用版本号。在变量前面追加上版本号，每次变量更新的时候把版本号加 1，那么 A→B→A 就会变成 1A→2B→3A。

   从 Java 1.5 开始，JDK 的 Atomic 包里提供了一个类 AtomicStampedReference 来解决 ABA 问题。这个类的 compareAndSet 方法的作用是首先检查当前引用是否等于预期引用，并且检查当前标志是否等于预期标志，如果全部相等，则以原子方式将该引用和该标志的值设置为给定的更新值。

   public boolean compareAndSet (
           V expectedReference, // 预期引用
           V newReference, // 更新后的引用
           int expectedStamp, // 预期标志
           int newStamp // 更新后的标志
   )
   

   循环时间长开销大：

   自旋 CAS 如果长时间不成功，会给 CPU 带来非常大的执行开销。如果 JVM 能支持处理器提供的 pause 指令，那么效率会有一定的提升。

   pause 指令有两个作用：第一，它可以延迟流水线执行指令（de-pipeline），使 CPU 不会消耗过多的执行资源，延迟的时间取决于具体实现的版本，在一些处理器上延迟时间是零；第二，它可以避免在退出循环的时候因内存顺序冲突（Memory Order Violation）而引起 CPU 流水线被清空（CPU Pipeline Flush），从而提高CPU的执行效率。

   只能保证一个共享变量的原子操作：

   当对一个共享变量执行操作时，我们可以使用循环 CAS 的方式来保证原子操作，但是对多个共享变量操作时，循环 CAS 就无法保证操作的原子性，这个时候就可以用锁。

   还有一个取巧的办法，就是把多个共享变量合并成一个共享变量来操作。比如，有两个共享变量 i ＝ 2，j = a，合并一下 ij = 2a，然后用 CAS 来操作 ij。从 Java 1.5 开始，JDK 提供了 AtomicReference 类来保证引用对象之间的原子性，就可以把多个变量放在一个对象里来进行 CAS 操作。

3. 使用锁机制实现原子操作

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