基础

八种基本类型

类型	占用存储空间	表示范围	例子
byte	1 字节 = 8bit 位	-128 ~ 127
boolean	1 字节
char	1 字符 = 2 字节
short	2 字节	- 2^15 ~ 2^15 - 1 （- 32768 ~ 327688 -1）
int	4 字节	- 2^31 ~ 2^31 -1( 约21亿 )
float (F)	4 字节		111F
long (L)	8 字节	- 2^63 ~ 2^63 - 1	999L
double	8 字节

数值精度顺序：double > float > long > int > short > byte

重载 & 重写

方法签名：方法名 + 依次参数类型（返回值不属于方法签名）。是一个方法在一个类中的唯一标识
一个类中如果定义了名字相同，签名不同的方法，就叫做方法的重载
使用和父类方法签名一样，并且返回值一样（或是子类关系）的方法，可以让子类重写父类的方法

hashCode & equals

hashCode：哈希码或者散列码。应该是一个表示对象的特征值的 int 整数
hashCode() 的默认行为是对堆上的对象产生独特值。如果没有重写 hashCode()，则该 class 的两个对象无论如何都不会相等（即使这两个对象指向相同的数据）
equals() 应该用来判断两个对象从逻辑上是否相等
hashCode & equals 是我们最常覆盖的两个方法，覆盖的原则是：equals 为 true，hashCode 就应该相等（即equals 为 true，是 hashCode 相等的充分非必要条件）

== 和 equals()

对于基本类型来说，== 比较的是值是否相等
对于引用类型来说，== 比较的是两个引用是否指向同一个对象地址（两者在内存中存放的地址（堆内存地址）是否指向同一个地方）
对于引用类型来说，equals() 如果没有被重写，比较它们的地址是否相等

单继承 & 多继承

Java 是单继承，但可以实现多个接口
多继承的优缺点

优点：对象可以调用多个父类中的方法
缺点：如果派生类所继承的多个父类有相同的父类（也就是一个菱形继承结构），而派生类对象需要调用这个祖先类的方法，就会容易出现二义性。

利用继承机制，新的类可以从已有的类中派生。那些用于派生的类称为这些特别派生出的类的“基类”

容器

概览

容器主要包括 Collection 和 Map 两种，Collection 存储着对象的集合，而 Map 存储着键值对的映射表。

List

LinkedList

概览

LinkedList 基于双向链表实现，只能顺序访问，但是可以快速地在链表中间插入和删除元素

JDK1.6 之前为循环链表，JDK1.7 取消了循环

LinkedList 可以用作栈、队列和双向队列
LinkedList 实现了 Deque 接口，也具有队列的特性
LinkedList 线程不安全，如果想使它变成线程安全的，可以调用 Collections 类中的 synchronizedList()

List list=Collections.synchronizedList(new LinkedList(...));

使用 Node 存储链表结点信息

private static class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;
}

每个链表存储了 first 和 last 指针

transient Node<E> first;
transient Node<E> last;

Vector

Vector 线程安全
Vector 的构造函数可以传入 capacityIncrement 参数，它的作用是在扩容时使容量 capacity 增长 capacityIncrement。如果这个参数的值小于等于 0 ，扩容时每次都令 capacity 为原来的 2 倍。
调用没有 capacityIncrement 的构造函数时，capacityIncrement 值被设置为 0

Map

key：无序、不可重复，使用 Set 存储所有的 key，所在类要重写 equals( ) 和 hashCode( )，以实现对象相等规则，即：相等的对象必须具有相等的哈希值
value：无序、可重复，使用 Collection 存储所有的 value，所在类要重写 equals( )
一个键值对构成了一个 Entry 对象
Entry：无序、不可重复，使用 Set 存储所有的 Entry

HashMap

概览

默认的扩容方式：当超出临界值并且存放数据的数组非空，则扩容为原来容量的 2 倍，并将原有的数据复制过来
HashMap 可以插入键为 null 的 Entry
使用键计算 hashCode
HashMap 不能保证随着时间的推移 Map 中的元素次序是不变的
jdk7 底层结构：数组 + 链表
jdk8 底层结构：数组 + 链表 + 红黑树

jdk8中：当数组的某一个索引位置上以链表形式存在的数据个数 > 8 并且当前数组的长度 > 64 时，此索引位置上的所有数据改为使用红黑树存储

put()

在实例化以后，底层创建了长度是 16 的一维数组 Entry[] table

hashMap.put(k1, v1)时，先调用 k1 所在类的 hashCode() 得到哈希值，此值经过某种算法后得到在 Entry 数组中的存放位置
如果此位置上的数据为空，此时 k1 - v1 添加成功
如果此位置上的数据不为空，则 k1 和已经存在的数据比较哈希值
- 如果不相同，此时 k1 - v1 添加成功
- 如果有相同，则继续用 k1 所在类的 equals() 比较
  - 为 false，此时 k1 - v1 添加成功
  - 为 true，使用 v1 替换 v2
    以上 put() 是基于 jdk7 的分析 jdk8 相较于 jdk7 有不同
    - 在首次调用 put() 时，底层才能创建长度为 16 的数组
    - 数组是 Node[] 类型，Node 实现了 Entry

// jdk7
static class Entry<K,V> implements Map.Entry<K,V> {
    final K key;
    V value;
    Entry<K,V> next;
    int hash;
}
// jdk8
static class Node<K,V> implements Map.Entry<K,V> {
    final K key;
    V value;
    Node<K,V> next;
    final int hash;
}

源码中的重要常量

DEFAULT_INITIAL_CAPACITY = 1 << 4;    // HashMap 的默认容量
MAXIMUM_CAPACITY = 1 << 30;            // HashMap 的最大支持容量
DEFAULT_LOAD_FACTOR = 0.75f;        // HashMap 的默认负载因子
TREEIFY_THRESHOLD = 8;                // Bucket  中链表长度大于该默认值，转化为红黑树(条件之一)
UNTREEIFY_THRESHOLD = 6;            // Bucket  中红黑树存储的 Node 小于该默认值，转化为链表
MIN_TREEIFY_CAPACITY = 64;            // Bucket  中的 Node 被树化时最小的 hash 表容量
table        存储元素的数组，总是 2 的 n 次幂
entrySet    存储具体元素的集
size        HashMap 中存储的键值对的数量
modCount    HashMap 扩容和结构改变的次数
threshold    扩容的临界值 = 容量 * 负载因子
loadFactor    负载因子

LinkedHashMap

概览

LinkedHashMap 继承自 HashMap
对于频繁的遍历操作，LinkedHashMap 效率高于HashMap
LinkedHashMap 通过 双向链表 实现有序
可以设置两种遍历顺序，通过构造器中设置 accessOrder 参数控制，true 为访问顺序遍历，false 为插入顺序遍历

// 对访问顺序做实验
public static void main() {
    LinkedHashMap<String, Integer> hashMap = new LinkedHashMap<>(10, 0.75f, true);
    hashMap.put("0", 0);
    hashMap.put("1", 1);
    hashMap.put("2", 2);
    hashMap.put("3", 2);
    hashMap.get("1");
    Iterator<Map.Entry<String, Integer>> iterator = hashMap.entrySet().iterator();
    while (iterator.hasNext()) {
        Map.Entry<String, Integer> next = iterator.next();
        System.out.println(next.getKey());
        // 0 2 3 1
    }
}

TreeMap

概览

底层结构是：红黑树 ( 自平衡的排序二叉树 )
要求 key 必须是由同一个类创建的对象
TreeMap 实现了 NavigableMap 接口，让 TreeMap 有了对集合内元素的搜索的能力
TreeMap 实现了 SortedMap 接口，让 TreeMap 有了对集合中的元素根据键排序的能力。默认是按 key 的升序排序，不过我们也可以指定排序的比较器
TreeMap 排序时比较特殊

自然排序时：比较两个对象是否相同的标准为：compareTo( )方法，不再是equals( )

类实现 Comparable 接口，重写 compareTo()
定制排序时：比较两个对象是否相同的标准为：compare( )方法，不再是equals( )

TreeSet set = new TreeSet( Comparator 的对象 )

Hashtable

概览

底层结构是：数组 + 链表
Hashtable 和 HashMap 类似，但 HashTable 是线程安全的。但它是遗留类，不应该去使用它，而是使用 ConcurrentHashMap 来支持线程安全，ConcurrentHashMap 的效率会更高，因为ConcurrentHashMap 引入了分段锁。

创建时不指定容量初始值，Hashtable 默认初始大小为 11，之后每次扩充，容量变为原来的 2n + 1
创建时给定了容量初始值，那么 Hashtable 会直接使用你给定的大小

Set
Set 接口中没有额外定义新的方法，使用的都是 Collection中声明过的方法

HashSet
HashSet 底层采用 HashMap 保存元素
HashSet 使用成员对象来计算 hashcode 值

LinkedHashSet
LinkedHashSet 是 HashSet 的子类
LinkedHashSet 底层采用 LinkedHashMap 保存元素

TreeSet
TreeSet 底层采用 TreeMap 保存元素

Queue

PriorityQueue
PriorityQueue 是在 JDK1.5 中被引入的, 其与 Queue 的区别在于元素出队顺序是与优先级相关的，即总是优先级最高的元素先出队。
PriorityQueue：基于堆结构 (特殊的完全二叉树) 实现，可以用它来实现优先队列
PriorityQueue 的底层结构：Object[] 数组
其相关的一些要点：
PriorityQueue 利用了二叉堆的数据结构来实现的，底层使用可变长的数组来存储数据
PriorityQueue 通过堆元素的上浮和下沉，实现了在 O(logn) 的时间复杂度内插入元素和删除堆顶元素。
PriorityQueue 是非线程安全的，且不支持存储 NULL 和 non-comparable 的对象。
PriorityQueue 默认是小顶堆，但可以接收一个 Comparator 作为构造参数，从而来自定义元素优先级

ArrayDeque
双端队列，在队列的两端均可以插入或删除元素
ArrayQueue 的底层结构：Object[] 数组 + 双指针
ArrayDeque 也可以用于实现栈

常见问题

为什么使用集合
即 集合的优势 or 好处
数组一旦声明之后，长度就不可变了；但是集合可以灵活扩容
数组存储的数据有序、可重复，特点及结构单一；集合提高了数据存储的灵活性，特点及结构复杂多样

如何选用集合
主要根据集合的特点来选用
当需要根据键值获取到元素值时就选用 Map 接口下的集合，需要排序时选择 TreeMap，不需要排序时就选择 HashMap。需要保证遍历顺序 (插入顺序、访问顺序) 时选择 LinkedHashMap。需要保证线程安全就选用 ConcurrentHashMap
当我们只需要存放元素值时，就选择实现 Collection 接口的集合，需要保证元素唯一时选择实现 Set 接口的集合比如 TreeSet 或 HashSet，不需要就选择实现 List 接口的比如 ArrayList 或 LinkedList，然后再根据实现这些接口的集合的特点来选用
List，Set，Queue，Map 的区别
List：存储的元素是有序的、可重复的。(对付顺序的好帮手)
Set：存储的元素是无序的、不可重复的。(注重独一无二的性质)
Queue：存储的元素是有序的、可重复的。按特定的排队规则来确定先后顺序。(实现排队功能的叫号机)
Map：使用键值对 ( key - value ) 存储。key 是无序的、不可重复的，value 是无序的、可重复的，每个键最多映射到一个值。(用 key 来搜索的专家)

有序或无序是指：是否按照其添加的顺序来存储对象。 List 是按照元素的添加顺序来存储对象。而 Set 的实现类都有一套自己的排序算法，每添加一个元素，都会按照其内部算法将元素添加到合适的位置，所以不能保证内部存储是按元素添加的顺序而存储的

ArrayList & LinkedList 的区别

ArrayList 基于动态数组实现
LinkedList 基于双向链表实现
ArrayList 和 LinkedList 的区别可以归结为数组和链表的区别：

数组支持随机访问，但插入删除的代价很高，需要移动大量元素，适用频繁的查找工作
链表不支持随机访问，但插入删除只需要改变指针，适用频繁的插入删除工作

ArrayDeque & LinkedList 的区别
ArrayDeque 和 LinkedList 都实现了 Deque 接口，两者都具有队列的功能
ArrayDeque 是基于可变长的数组和双指针来实现，而 LinkedList 则通过双向链表来实现。
ArrayDeque 不支持存储 NULL 数据，但 LinkedList 支持。
ArrayDeque 是在 JDK1.6 才被引入的，而 LinkedList 早在 JDK1.2 时就已经存在。
ArrayDeque 插入时可能存在扩容过程，不过均摊后的插入操作依然为 O(1)。虽然 LinkedList 不需要扩容，但是每次插入数据时均需要申请新的堆空间，均摊性能相比更慢。

从性能的角度上，选用 ArrayDeque 来实现队列要比 LinkedList 好。

Comparable & Comparator 的区别

Comparable 接口，它有一个 compareTo(Object obj) 用来排序
Comparator 接口，它有一个 compare(Object obj1, Object obj2) 用来排序

一般需要对一个集合使用自定义排序时，我们就要重写 compareTo() 或 compare()。当我们需要对某一个集合实现两种排序方式，比如一个 song 对象中的歌名和歌手名分别采用一种排序方法的话，我们可以重写compareTo() 和使用自制的 Comparator 。或者以两个 Comparator 来实现歌名排序和歌星名排序 ```java // Comparator 匿名内部类重写 compare() 实现排序 Collections.sort(arrayList, new Comparator() { @Override public int compare(Integer o1, Integer o2) {
```
  return o2.compareTo(o1);
```
} });

// 实现 Comparable 接口，重写 compareTo() 实现排序 public class Person implements Comparable { private String name; private int age;

// 构造器、get()、set() 省略
@Override
public int compareTo(Person o) {
    if (this.age > o.getAge()) {
        return 1;
    }
    if (this.age < o.getAge()) {
        return -1;
    }
    return 0;
}

}

<a name="c219J"></a>
### 无序性 & 不可重复性 的理解
**无序性** 不等于随机性，无序性是指： 存储的数据在底层数组中并非按照数组索引的顺序添加 ，而是由数据的哈希值决定的  <br />**不可重复性**是指：添加的元素根据 equals() 和 hashCode() 判断是否相等
> TreeMap 比较特殊，是根据 compareTo() 判断
<a name="JwVSL"></a>
### HashMap 多线程操作导致死循环问题
<a name="fRdl3"></a>
# 并发编程
<a name="e2d6d0e3"></a>
## 基本概念 
<a name="dd5625fe"></a>
### 进程 & 线程
**进程**
- 程序由指令 和 数据组成，但这些指令要运行，数据要读写，就必须将指令加载至 CPU，数据加载至内存。在指令运行过程中还需要用到磁盘、网络等设备
- 进程就是用来加载指令、管理内存、管理 IO 的
- 当一个程序被运行，从磁盘加载这个程序的代码至内存，这时就开启了一个进程
- 进程就可以视为程序的一个实例。大部分程序可以同时运行多个实例进程，也有程序只能启动一个实例进程
**线程**
-  一个进程之内可以分为一到多个线程
-  一个线程就是一个指令流，将指令流中的一条条指令以一定的顺序交给 CPU 执行
-  在 windows 中进程是不活动的，只是作为线程的容器
**二者对比**
- **线程作为最小调度单位，进程作为资源分配的最小单位**
- 进程基本上相互独立的，而线程存在于进程内，是进程的一个子集
- 进程拥有共享的资源，如内存空间等，供其内部的线程共享 
   - 进程间通信较为复杂，同一台计算机的进程通信称为 IPC (Inter-process communication)
   - 不同计算机之间的进程通信，需要通过网络，并遵守共同的协议，例如 HTTP
- 线程通信相对简单，因为它们共享进程内的内存，一个例子是：多个线程可以访问同一个共享变量
- 线程更轻量，线程上下文切换成本一般上要比进程上下文切换低
<a name="88dbde4f"></a>
### 并发 & 并行
**并发**是一个 CPU 在不同的时间去不同线程中执行指令。一般会将：不同线程轮流使用 CPU 的做法称为并发<br />**并行**是多个 CPU 同时处理不同的线程。多核 CPU 下，每个 核 (core) 都可以调度运行线程，这时候线程可以是并行的<br />引用 Rob Pike 的一段描述：
- 并发（concurrent）是同一时间**应对**（dealing with）多件事情的能力
- 并行（parallel）是同一时间**动手做**（doing）多件事情的能力
<a name="cbb1815e"></a>
### 同步 & 异步
从方法调用的角度来讲，如果
- 需要等待结果返回，才能继续运行是**同步**
- 不需要等待结果返回，就能继续运行是**异步**
<a name="f26456f0"></a>
## 线程的创建
<a name="3e870e83"></a>
### 查看进程线程的方法
**windows**
- 任务管理器可以查看进程和线程数，也可以用来杀死进程
- `tasklist` 查看进程 `taskkill` 杀死进程
**linux**
- `ps -fe` 查看所有进程
- `ps -fT -p <pid>` 查看某个进程 (PID) 的所有线程
- `kill` 杀死进程
- `top` 按大写 H 切换是否显示线程
- `top -H -p`  查看某个进程 (PID) 的所有线程
**Java**
- jps 命令查看所有 Java 进程
- `jstack` 查看某个 Java 进程 (PID) 的所有线程状态
- `jconsole` 来查看某个 Java 进程中线程的运行情况 (图形界面)
jconsole 远程监控配置
- 需要以如下方式运行你的 java 类
```java
java -Djava.rmi.server.hostname=`ip地址` -Dcom.sun.management.jmxremote -
Dcom.sun.management.jmxremote.port=`连接端口` -Dcom.sun.management.jmxremote.ssl=是否安全连接 -
Dcom.sun.management.jmxremote.authenticate=是否认证 java类

修改 /etc/hosts 文件将 127.0.0.1 映射至主机名

如果要认证访问，还需要做如下步骤

复制 jmxremote.password 文件
修改 jmxremote.password 和 jmxremote.access 文件的权限为 600 即文件所有者可读写
连接时填入 controlRole (用户名)，R&D (密码)

线程的状态

五种状态
这是从 操作系统 层面来描述的
【初始状态】仅是在语言层面创建了线程对象，还未与操作系统线程关联（例如线程调用了start() ）
【可运行状态】也可称【就绪状态】指该线程已经被创建，与操作系统线程关联，可以由 CPU 调度执行
【运行状态】指获取了 CPU 时间片运行中的状态
- 当 CPU 时间片用完，会从【运行状态】转换至【可运行状态】，会导致线程的上下文切换
【阻塞状态】
- 如果调用了阻塞 API，如 BIO 读写文件，这时该线程实际不会用到 CPU，会导致线程上下文切换，进入【阻塞状态】
- 等 BIO 操作完毕，会由操作系统唤醒阻塞的线程，转换至【可运行状态】
- 与【可运行状态】的区别是，对【阻塞状态】的线程来说只要它们一直不唤醒，调度器就一直不会考虑调度它们
【终止状态】表示线程已经执行完毕，生命周期已经结束，不会再转换为其它状态

六种状态
这是从 Java API 层面来描述的
根据 Thread.State 枚举，分为六种状态
new 线程刚被创建，但是还没有调用 start()
runnable 当调用了 start() 之后，注意，Java API 层面的 runnable 状态涵盖了操作系统层面的【可运行状态】、【运行状态】、【阻塞状态】（由于 BIO 导致的线程阻塞，在 Java 里无法区分，仍然认为是可运行状态）
blocked，waiting，timed_waiting都是 Java API 层面对【阻塞状态】的细分，如 sleep 为 timed_waiting，join 为 waiting 状态
terminated 线程代码运行结束

共享模型 - 管程

synchronized

synchronized，即俗称的 对象锁，它采用互斥的方式，让同一时刻至多只有一个线程能持有对象锁，其它线程再想获取这个对象锁时就会阻塞住。这样就能保证拥有锁的线程可以安全的执行临界区内的代码，不用担心线程上下文切换
可以保证共享变量的原子性、可见性、有序性

synchronized(对象) {
    //临界区
}

synchronized 加在方法上

public class Demo {
    //在方法上加上 synchronized 关键字
    public synchronized void test() { }
    //等价于
    public void test() {
        synchronized(this) { }
    }
}

加在静态方法上

public class Demo {
    //在静态方法上加上 synchronized 关键字
    public synchronized static void test() { }
    //等价于
    public void test() {
        synchronized(Demo.class) { }
    }
}

变量的线程安全分析

成员变量和静态变量是否线程安全

如果它们没有共享，则线程安全
如果它们被共享了，根据它们的状态是否能够改变，又分两种情况
- 如果只有读操作，则线程安全
- 如果有读写操作，则这段代码是临界区，需要考虑线程安全

局部变量是否线程安全

局部变量是线程安全的，每个方法都在对应线程的栈中创建栈帧，不会被其他线程共享
但局部变量引用的对象则未必 (要看该对象是否被共享且被执行了读写操作)
- 如果该对象没有逃离方法的作用范围，它是线程安全的
- 如果该对象逃离方法的作用范围，需要考虑线程安全
  Monitor
  Java 对象头
  JVM 中对象头的形式有以下两种 (以 32 位 JVM 为例)

普通对象

|--------------------------------------------------------------|
|                     Object Header (64 bits)                  |
|------------------------------------|-------------------------|
|        Mark Word (32 bits)         |    Klass Word (32 bits) |
|------------------------------------|-------------------------|

数组对象

|---------------------------------------------------------------------------------|
|                                 Object Header (96 bits)                         |
|--------------------------------|-----------------------|------------------------|
|        Mark Word(32bits)       |    Klass Word(32bits) |  array length(32bits)  |
|--------------------------------|-----------------------|------------------------|

JVM 中对象头的组成

Mark Word

这部分主要用来存储对象自身的运行时数据。Mark Word 的位长度为 JVM 的一个 Word 大小，也就是说：32位 JVM 的 Mark Word 为 32 位，64 位 JVM 为 64 位。为了让一个字大小存储更多的信息，JVM 将字的最低两个位设置为标记位，不同标记位下的 Mark Word 示意如下：

原理 - Monitor

Monitor 被翻译为监视器或管程。每个 Java 对象都可以关联一个 Monitor 对象，如果使用 synchronized 给对象上锁 (重量级) 之后，该对象头的 Mark Word 就被设置指向 Monitor 对象的指针
Monitor 结构如下 图片.png

当线程执行到临界区代码时，如果使用了 synchronized，会先查询 synchronized 中所指定的对象 (obj) 是否绑定了 Monitor
- 如果没有绑定，则会先去去与 Monitor 绑定，并将 Owner 设为当前线程
- 如果已经绑定，则会去查询该 Monitor 是否已经有了 Owner
  - 如果没有，则 Owner 与将当前线程绑定
  - 如果有，则当前线程放入 EntryList，进入阻塞状态 (blocked)
当 Monitor 的 Owner 将临界区中代码执行完毕后，Owner 便会被清空，此时 EntryList 中处于阻塞状态的线程会被叫醒并竞争，此时的竞争是非公平的

注意：

对象在使用了 synchronized 后与 Monitor 绑定时，会将对象头中的 Mark Word 置为 Monitor 指针
每个对象都会绑定一个唯一的 Monitor
原理 - Synchronized
```java static final Object lock = new Object(); static int counter = 0;

public static void main(String[] args) { synchronized (lock) { counter++; } }

 对应的字节码为
```java
public static void main(java.lang.String[]);
    descriptor: ([Ljava/lang/String;)V
    flags: ACC_PUBLIC, ACC_STATIC
    Code:
        stack=2, locals=3, args_size=1
            0: getstatic #2 // <- lock引用 （synchronized开始）
            3: dup
            4: astore_1 // lock引用 -> slot 1
            5: monitorenter // 将 lock对象 MarkWord 置为 Monitor 指针
            6: getstatic #3 // <- i
            9: iconst_1 // 准备常数 1
            10: iadd // +1
            11: putstatic #3 // -> i
            14: aload_1 // <- lock引用
            15: monitorexit // 将 lock对象 MarkWord 重置, 唤醒 EntryList
            16: goto 24
            19: astore_2 // e -> slot 2 
            20: aload_1 // <- lock引用
            21: monitorexit // 将 lock对象 MarkWord 重置, 唤醒 EntryList
            22: aload_2 // <- slot 2 (e)
            23: athrow // throw e
            24: return
        Exception table:
            from  to target type
              6   16   19   any
              19  22   19   any

轻量级锁

轻量级锁用于优化 Monitor 这类的重量级锁
轻量级锁的使用场景：当一个对象被多个线程访问，但访问的时间是错开的，即不存在竞争，此时就可以使用轻量级锁来优化

static final Object obj = new Object();
public static void method1() {
    synchronized( obj ) {
        // 同步块 A
         method2();
    }
}
public static void method2() {
    // 锁重入
    synchronized( obj ) {
        // 同步块 B
    }
}

创建锁记录 (Lock Record) 对象。每个线程的栈帧都会包含一个锁记录的结构，内部可以存储锁定对象的 Mark Word，记录锁对象的地址（不再一开始就使用 Monitor，锁记录是 JVM 层面的）
让锁记录中的 Object reference 指向锁对象，并尝试用 cas 替换锁对象的 Mark Word，将 Mark Word 的值存入锁记录
- 如果 cas 替换成功，对象头中存储锁记录地址和状态 00 ，表示由该线程给对象加锁，这时图示如下
- 如果 cas 失败，有两种情况
  - 如果是其它线程已经持有了该对象的轻量级锁，表明有竞争，进入锁膨胀过程
  - 如果是自己执行了 synchronized 锁重入，那么再添加一条锁记录作为重入的计数
当退出 synchronized 代码块（解锁时）如果有取值为 null 的锁记录，表示有重入，这时重置锁记录，表示重入计数减一
当退出 synchronized 代码块（解锁时）锁记录的值不为 null，这时使用 cas 将 Mark Word 的值恢复给对象头
- 成功，则解锁成功
- 失败，说明轻量级锁进行了锁膨胀或已经升级为重量级锁，进入重量级锁解锁流程
  锁膨胀
如果在尝试加轻量级锁的过程中，cas 操作无法成功，存在一种情况是：有其它线程为此对象加上了轻量级锁，这时需要进行锁膨胀，将轻量级锁变为重量级锁
当 Thread-1 进行轻量级加锁时，Thread-0 已经对该对象加了轻量级锁
此时便会进入锁膨胀流程，给对象加上重量级锁 (使用 Monitor)
- 即为锁对象申请 Monitor 锁，让 Object 指向重量级锁地址 (将 Mark Word 改为 Monitor 的地址，并且状态改为10)
- 并且该线程放入 Monitor 的 EntryList 中，进入阻塞状态 (blocked)
当 Thread-0 退出同步块解锁时，使用 cas 将 Mark Word 的值恢复给对象头，失败。这时会进入重量级解锁流程，即按照 Monitor 地址找到 Monitor 对象，设置 Owner 为 null，唤醒 EntryList 中 blocked 线程

图片.png 自旋优化

重量级锁竞争的时候，还可以使用自旋来进行优化，如果当前线程自旋成功（即这时候持锁线程已经退出了同步块，释放了锁），这时当前线程就可以避免阻塞。
自旋会占用 CPU 时间，单核 CPU 自旋就是浪费，多核 CPU 自旋才能发挥优势。
在 Java 6 之后自旋锁是自适应的，比如对象刚刚的一次自旋操作成功过，那么认为这次自旋成功的可能性会高，就多自旋几次；反之，就少自旋甚至不自旋，总之，比较智能。
Java 7 之后不能控制是否开启自旋功能，由 JVM 底层掌管

偏向锁
用于优化轻量级锁重入
轻量级锁在没有竞争时（就自己一个线程），每次重入（该线程执行的方法中再次锁住该对象）仍然需要执行 CAS 操作。Java 6 中引入了偏向锁来做进一步优化：
只有第一次使用 CAS 将线程 ID 设置到锁对象的 Mark Word 头，之后发现这个线程 ID 是自己的就表示没有竞争，不用重新 CAS
以后只要不发生竞争，这个对象就归该线程所有

偏向状态
Normal：一般状态，没有加任何锁，前面62位保存的是对象的信息，最后2位为状态（01），倒数第三位表示是否使用偏向锁（未使用：0）
Biased：偏向状态，使用偏向锁，前面54位保存的当前线程的ID，最后2位为状态（01），倒数第三位表示是否使用偏向锁（使用：1）
Lightweight：使用轻量级锁，前62位保存的是锁记录的指针，最后两位为状态（00）
Heavyweight：使用重量级锁，前62位保存的是Monitor的地址指针，后两位为状态(10)
如果开启了偏向锁（默认开启），在创建对象时，对象的 Mark Word 后三位应该是101
偏向锁默认是有延迟的，不会在程序一启动就生效，而是会在程序运行一段时间（几秒之后），才会对创建的对象设置为偏向状态
如果想避免延迟，可以加 VM 参数 - XX:BiasedLockingStartupDelay=0 来禁用延迟
如果没有开启偏向锁，对象的 Mark Word 后三位应该是001
如果想禁用偏向锁，可以加 VM 参数 -XX:-UseBiasedLocking

偏向锁被撤销的情况
调用对象的 hashCode() 方法，会将偏向锁升级为重量级锁
- 偏向锁的对象 MarkWord 中存储的是线程 id
- 轻量级锁会在锁记录中记录 hashCode
- 重量级锁会在 Monitor 中记录 hashCode
当有其它线程使用偏向锁对象时，会将偏向锁升级为轻量级锁
调用了 wait() / notify()（调用 wait() 会导致锁膨胀而使用重量级锁）

批量重偏向
如果锁对象虽然被多个线程访问，但是线程间不存在竞争，这时偏向 T1 线程的锁对象仍有机会重新偏向 T2 线程。重偏向会重置Thread ID
当撤销超过20次（阈值）后，JVM 就会在给对象加锁时，重新偏向至加锁线程

批量撤销

当撤销偏向锁超过 40 次（阈值）后，JVM 就会将整个类的所有对象都改为不可偏向的

wait() / notify()

原理
锁对象调用 wait()，就会使当前线程进入WaitSet 中，变为 waiting 状态
处于 blocked 和 waiting 状态的线程都为阻塞状态，不占用 CPU 时间片。但是两者有区别：
- blocked 状态的线程是在竞争对象时，发现 Monitor 的 Owner 已经是别的线程了，此时就会进入EntryList 中
- waiting 状态的线程是获得了对象的锁，但是锁对象调用了wait() 而进入了 WaitSet 中
blocked 状态的线程会在锁被释放时被唤醒，但是处于 waiting 状态的线程只有当锁对象调用 notify() / notifyAll()，才会被唤醒
但唤醒后并不意味者立刻获得锁，仍需进入 EntryList 重新竞争

同步模式 - 保护性暂停
wait()、notify() 的应用

定义
即 Guarded Suspension，用一个线程等待另一个线程的执行结果
有一个结果需要从一个线程传递到另一个线程，让他们关联同一个 GuardedObject
如果有结果不断从一个线程到另一个线程那么可以使用消息队列
JDK 中，join()、Future 的实现，采用的就是保护性暂停模式
因为要等待另一方的结果，因此归类到同步模式

join() 源码，使用了保护性暂停模式

实现

class GuardedObject {
  private Object response;
  private final Object lock = new Object();
  public Object get() {
      synchronized (lock) {
          // 条件不满足则等待，避免虚假唤醒
          while (response == null) {
              try {
                  lock.wait();
              } catch (InterruptedException e) {
                  e.printStackTrace();
              }
          }
          return response;
      }
  }
  public void complete(Object response) {
      synchronized (lock) {
          // 条件满足，通知等待线程
          this.response = response;
          lock.notifyAll();
      }
  }
}

带超时判断的实现

class GuardedObjectV2 {
  private Object response;
  private final Object lock = new Object();
  public Object get(long millis) {
      synchronized (lock) {
          // 开始时间
          long begin = System.currentTimeMillis();
          // 经历的时间
          long timePassed = 0;
          while (response == null) {
              // 这一轮循环应该等待的时间
              long waitTime = millis - timePassed;
              // 经历的时间超过了最大等待时间时，退出循环
              if (waitTime <= 0) {
                  break;
              }
              try {
                  lock.wait(waitTime);
              } catch (InterruptedException e) {
                  e.printStackTrace();
              }
              timePassed = System.currentTimeMillis() - begin;
          }
          return response;
      }
  }
  public void complete(Object response) {
      synchronized (lock) {
          this.response = response;
          lock.notifyAll();
      }
  }
}

多任务版 GuardedObject
如果需要在多个类之间使用 GuardedObject 对象，作为参数传递很不方便，因此设计一个用来解耦的中间类，这样不仅能够解耦【结果等待者】和【结果生产者】，还能够同时支持多个任务的管理

class GuardedObject {
  // 新增 id 用来标识 GuardedObject
  private int id;
  public GuardedObject(int id) {
      this.id = id;
  }
  public int getId() {
      return id;
  }
  // 结果
  private Object response;
  // 获取结果。timeout 表示要等待多久
  public Object get(long millis) {
      synchronized (this) {
          long begin = System.currentTimeMillis();
          long timePassed = 0;
          while (response == null) {
              long waitTime = millis - timePassed;
              if (waitTime <= 0) {
                  break;
              }
              try {
                  this.wait(waitTime);
              } catch (InterruptedException e) {
                  e.printStackTrace();
              }
              timePassed = System.currentTimeMillis() - begin;
          }
          return response;
      }
  }
  // 产生结果
  public void complete(Object response) {
      synchronized (this) {
          this.response = response;
          this.notifyAll();
      }
  }
}

中间解耦类

class Mailboxes {
  private static Map<Integer, GuardedObject> boxes = new Hashtable<>();
  private static int id = 1;
  // 产生唯一 id
  private static synchronized int generateId() {
      return id++;
  }
  public static GuardedObject getGuardedObject(int id) {
      return boxes.remove(id);
  }
  public static GuardedObject createGuardedObject() {
      GuardedObject go = new GuardedObject(generateId());
      boxes.put(go.getId(), go);
      return go;
  }
  public static Set<Integer> getIds() {
      return boxes.keySet();
  }
}

业务相关类 ```java class People extends Thread { @Override public void run() {

  // 收信
  GuardedObject guardedObject = Mailboxes.createGuardedObject();
  log.debug("开始收信 id:{}", guardedObject.getId());
  Object mail = guardedObject.get(5000);
  log.debug("收到信 id:{}, 内容:{}", guardedObject.getId(), mail);

} }

class Postman extends Thread { private int id; private String mail;

public Postman(int id, String mail) {
    this.id = id;
    this.mail = mail;
}
@Override
public void run() {
    GuardedObject guardedObject = Mailboxes.getGuardedObject(id);
    log.debug("送信 id:{}, 内容:{}", id, mail);
    guardedObject.complete(mail);
}

}

public static void main(String[] args) throws InterruptedException { for (int i = 0; i < 3; i++) { new People().start(); } Thread.sleep(1); for (Integer id : Mailboxes.getIds()) { new Postman(id, “内容” + id).start(); } }

<a name="7ffb91a4"></a>
### park() / unpark()
<a name="AnPqz"></a>
#### 基本使用
park() / unpark() 都是 LockSupport 类中的的方法
```java
//暂停线程运行
LockSupport.park;
//恢复线程运行
LockSupport.unpark(threadName);

与 wait() / notify() 对比

wait()，notify() 必须配合 Object Monitor 一起使用，而 park() / unpark() 不必
park() / unpark() 是以线程为单位来阻塞和唤醒线程，而 notify() 只能随机唤醒一个等待线程，notifyAll() 是唤醒所有等待线程
park() / unpark() 可以先 unpark() 再 park()，然后继续执行，不暂停线程运行。而 wait() / notify() 不能
park() 不会释放锁，而 wait() 会释放锁

原理
每个线程都有一个自己的 Parker 对象，该对象由 _counter，_cond，__mutex 三部分组成
故事便于理解原理
线程就像一个旅人，Parker 就像他随身携带的背包，条件变量就好比背包中的帐篷。_counter 就好比背包中的备用干粮（0 为耗尽，1 为充足）
调用 park() 就是要看需不需要停下来歇息
- 如果备用干粮耗尽，那么钻进帐篷歇息
- 如果备用干粮充足，那么不需停留，继续前进
调用 unpark()，就好比令干粮充足
- 如果这时线程还在帐篷，就唤醒让他继续前进
- 如果这时线程还在运行，那么下次他调用 park 时，仅是消耗掉备用干粮，不需停留继续前进
  - 因为背包空间有限，多次调用 unpark 仅会补充一份备用干粮

先调用 park() 再调用 unpark() 时

线程运行时，会将 Park 对象中的 _counter 值设为 0
调用 park() 后，会先检查 _counter 的值是否为 0，如果为 0，获得 _mutex 互斥锁，线程进入 _cond 条件变量 (阻塞队列) 阻塞
放入阻塞队列中后，会再次将 _counter 设置为 0
调用 unpark() 后，会将 _counter 值设置为 1
唤醒 _cond 条件变量 (阻塞队列) 中的线程
线程恢复运行，并将 _counter 值设为 0

先调用 unpark()，再调用 park()

调用 unpark()，会将 _counter 设置为 1（线程运行时为 0 ）
调用 park()
- 查看counter是否为 0
- 因为 unpark() 已经把 _counter 设置为 1，所以此时将 _counter 设置为 0，但不放入阻塞队列 _cond 中
  线程状态转换

new –> runnable

调用 t.start()

runnable <–> waiting

情况1： t 线程用 synchronized(obj) 获取了对象锁后
- 调用 obj.wait()，t 线程从 runnable –> waiting
- 调用 obj.notify()、obj.notifyAll() ， t.interrupt() 时
  - 竞争锁成功，t 线程从 waiting –> runnable
  - 竞争锁失败，t 线程从 waiting –> blocked
情况2：
- 当前线程调用其他线程的 t.join()，当前线程从 runnable –> waiting（注意是当前线程在 t 线程锁对象的监视器上等待）
- t 线程运行结束，或调用了当前线程的 interrupt() 时，当前线程从 waiting –> runnable

runnable <–> timed_waiting

情况1：t 线程用 synchronized(obj) 获取了对象锁后
- 调用 obj.wait(long n) 方法时，t 线程从 runnable –> timed_waiting
- t 线程等待时间超过了 n 毫秒，或调用 obj.notify()、obj.notifyAll()、t.interrupt() 时
  - 竞争锁成功，t 线程从 timed_waiting –> runnable
  - 竞争锁失败，t 线程从 timed_waiting –> blocked
情况2：
- 当前线程调用其他线程的 t.join(long n)，当前线程从 runnable –> timed_waiting（注意是当前线程在 t 线程锁对象的监视器上等待）
- 当前线程等待时间超过了 n 毫秒，或 t 线程运行结束，或调用了当前线程的 interrupt() 时，当前线程从 timed_waiting –> runnable
情况3：
- 当前线程调用 Thread.sleep(long n) ，当前线程从 runnable –> timed_waiting
- 当前线程等待时间超过了 n 毫秒，当前线程从 timed_waiting –> runnable
情况4：
- 当前线程调用 LockSupport.parkNanos(long nanos) 或 LockSupport.parkUntil(long millis) 时，当前线程从 runnable –> timed_waiting
- 调用 LockSupport.unpark(目标线程) 或调用了线程的 interrupt() ，或是等待超时，会让目标线程从 timed_waiting –> runnable

runnable <–> blocked
- t 线程用 synchronized(obj) 获取了对象锁时，如果竞争失败，从 runnable –> blocked
- 持对象锁线程的同步代码块执行完毕，会唤醒该对象上所有 blocked 的线程重新竞争，如果其中 t 线程竞争成功，则该线程从 blocked –> runnable ，其它失败的线程仍然是 blocked
runnable <–> terminated
- 当前线程所有代码运行完毕，进入 terminated
  活跃性
  一个并发应用程序能及时执行的能力称为活跃性
  死锁
  死锁是指：两个或两个以上的进程（或线程）在执行过程中，由于竞争资源或者彼此通信而造成的一种互相等待的现象。若无外力作用，它们都将无法推进下去，此时称系统处于死锁状态或系统产生了死锁
  发生死锁的必要条件

互斥条件：进程对资源的使用是排他性的使用，某资源只能由一个进程使用，其他进程需要使用只能等待
请求保持条件：进程至少保持一个资源，又提出新的资源请求，新资源被占用，请求被阻塞，被阻塞的进程不释放自己保持的资源
不可剥夺条件：进程获得的资源在未完成使用前不能被剥夺，获得的资源只能由进程自身释放
环路等待条件：发生死锁的时候，必然存在进程-资源环形链

定位死锁的方法

jps + jstack ThreadID：在 Java 控制台中的 Terminal 中输入 jps 指令查看运行中的线程 ID，使用 jstack ThreadID 查看线程状态
cmd 命令 jconsole 检测死锁
如果由于某个线程进入了死循环，导致其它线程一直等待，对于这种情况 linux 下可以通过 top 先定位到 CPU 占用高的 Java 进程，再利用 top -Hp 进程 id 来定位是哪个线程，最后再用 jstack 排查

预防死锁的方法

摒弃请求保持条件：系统规定进程运行之前，一次性申请所有需要的资源，进程在运行期间不会提出资源请求，从而摒弃请求保持条件
摒弃不可剥夺条件：当一个进程请求新的资源得不到满足时，必须释放占有的资源，进程运行时占有的资源可以被释放，意味着可以被剥夺

摒弃环路等待条件：可用资源线性排序，申请必须按照需要递增申请，线性申请不再形成环路

活锁

活锁常出现在两个线程互相改变对方的结束条件的情况，谁也无法结束

public class TestLiveLock {
  static volatile int count = 10;
  static final Object lock = new Object();
  public static void main(String[] args) {
      new Thread(() -> {
          // 期望减到 0 退出循环
          while (count > 0) {
              Thread.sleep(2000);
              count--;
          }
      }, "t1").start();
      new Thread(() -> {
          // 期望超过 20 退出循环
          while (count < 20) {
              Thread.sleep(2000);
              count++;
          }
      }, "t2").start();
  }
}

避免活锁的方法：在线程执行时，中途给予不同线程不同的间隔时间

饥饿

一个线程由于优先级太低，始终得不到 CPU 调度执行，也不能够结束
在使用顺序加锁时，可能会出现饥饿现象

ReentrantLock

ReentrantLock 比 Synchronized 厉害的方面

在等待获取锁的过程中可打断
可以设置获得锁等待超时时间
可以设置为公平锁（先到先得）
支持多个条件变量（具有多个 waitset）
共同点：都支持可重入

ReentrantLock 基础用法

// 获取 ReentrantLock 对象
ReentrantLock lock = new ReentrantLock();
// 加锁
lock.lock();
try {
    // 需要执行的代码
} finally {
    // 释放锁
    lock.unlock();
}

可重入

可重入是指：同一个线程如果首次获得了这把锁，那么因为它是这把锁的拥有者，因此有权利再次获取这把锁
如果是不可重入锁，那么第二次获得锁时，自己也会被锁挡住

可打断

如果某个线程处于阻塞状态，可以调用其 interrupt() 让其停止阻塞，获得锁失败
就是：处于阻塞状态的线程，被打断了就不用阻塞了，直接停止运行。也可以打断正在运行的线程
获取锁的方法必须使用 lock.lockInterruptibly()

锁超时

使用 lock.tryLock() 会返回获取锁是否成功。成功返回 true，反之返回false
使用 lock.tryLock(long timeout, TimeUnit unit) 指定等待时间，不指定则立即返回结果
使用 tryLock() 就是：获取失败了、获取超时了或者被打断了，不再阻塞，直接停止运行

公平锁

ReentrantLock 默认是不公平的
ReentrantLock lock = new ReentrantLock(true) 参数 true，设置为公平锁
公平锁一般没有必要，会降低并发度

条件变量

synchronized 中也有条件变量，就是 waitSet，当条件不满足时进入 waitSet 中等待
ReentrantLock 的条件变量比 synchronized 强大，它是支持多个条件变量的
- 这就好比 synchronized 是那些不满足条件的线程都在一间休息室等消息
- 而 ReentrantLock 支持多间休息室，有专门等烟的休息室、专门等早餐的休息室、唤醒时也是按休息室来唤醒
使用要点：
- await() 前需要获得锁
- await() 执行后会释放锁，进入 conditionObject 等待
- await() 的线程被唤醒（或打断、或超时）去重新竞争 lock 锁
- 竞争 lock 锁成功后，从 await() 后继续执
```
static ReentrantLock lock = new ReentrantLock();
// 条件变量
static Condition waitCigaretteQueue = lock.newCondition();
// 阻塞
waitCigaretteQueue.await();
// 唤醒
waitCigaretteQueue.signal();
```
  同步模式 - 顺序控制
  固定运行顺序
  比如，必须先 2 后 1 打印

固定运行顺序 - wait() / notify() 实现

static final Object LOCK = new Object();
// 判断先执行的内容是否执行完毕
static Boolean judge = false;
public static void main(String[] args) {
  new Thread(()->{
      synchronized (LOCK) {
          while (!judge) {
              try {
                  LOCK.wait();
              } catch (InterruptedException e) {
                  e.printStackTrace();
              }
          }
          System.out.println("2");
      }
  }).start();
  new Thread(()->{
      synchronized (LOCK) {
          System.out.println("1");
          judge = true;
          // 执行完毕，唤醒所有等待线程
          LOCK.notifyAll();
      }
  }).start();
}

固定运行顺序 - park() / unpark() 实现 ```java Thread t1 = new Thread(() -> { try { Thread.sleep(1000); } catch (InterruptedException e) { } // 当没有『许可』时，当前线程暂停运行；有『许可』时，用掉这个『许可』，当前线程恢复运行 LockSupport.park(); System.out.println(“1”); });

Thread t2 = new Thread(() -> { System.out.println(“2”); // 给线程 t1 发放『许可』（多次连续调用 unpark 只会发放一个『许可』） LockSupport.unpark(t1); });

t1.start(); t2.start();

<a name="fINTY"></a>
#### 交替输出
线程 1 输出 a 5 次，线程 2 输出 b 5 次，线程 3 输出 c 5 次。现在要求输出 abcabcabcabcabc
- 交替输出 - wait() / notify() 实现
```java
public static void main(String[] args) {
    SyncWaitNotify syncWaitNotify = new SyncWaitNotify(1, 5);
    new Thread(() -> {
        syncWaitNotify.print(1, 2, "a");
    }, "t1").start();
    new Thread(() -> {
        syncWaitNotify.print(2, 3, "b");
    }, "t1").start();
    new Thread(() -> {
        syncWaitNotify.print(3, 1, "c");
    }, "t1").start();
}
class SyncWaitNotify {
    // 线程的执行标记：1->a 2->b 3->c
    private int flag;
    // 输出 abc 的循环次数
    private int loopNumber;
    public SyncWaitNotify(int flag, int loopNumber) {
        this.flag = flag;
        this.loopNumber = loopNumber;
    }
    public void print(int waitFlag, int nextFlag, String str) {
        for (int i = 0; i < loopNumber; i++) {
            synchronized (this) {
                while (this.flag != waitFlag) {
                    try {
                        this.wait();
                    } catch (InterruptedException e) {
                        e.printStackTrace();
                    }
                }
                System.out.print(str);
                this.flag = nextFlag;
                this.notifyAll();
            }
        }
    }
}

交替输出 - await() / signal() 实现 ```java public class Uninterruptible { static AwaitSignal awaitSignal = new AwaitSignal(); static Condition conditionA = awaitSignal.newCondition(); static Condition conditionB = awaitSignal.newCondition(); static Condition conditionC = awaitSignal.newCondition();

public static void main(String[] args) throws InterruptedException {

  new Thread(() -> {
      awaitSignal.print("a", conditionA, conditionB);
  },"t1").start();
  new Thread(() -> {
      awaitSignal.print("b", conditionB, conditionC);
  },"t2").start();
  new Thread(() -> {
      awaitSignal.print("c", conditionC, conditionA);
  },"t3").start();
  Thread.sleep(1000);
  awaitSignal.lock();
  try {
      conditionA.signal();
  } finally {
      awaitSignal.unlock();
  }

} }

class AwaitSignal extends ReentrantLock {

private int loopNumber = 5;
public void print(String str, Condition condition, Condition nextCondition) {
    for (int i = 0; i < loopNumber; i++) {
        this.lock();
        try {
            //全部进入等待状态
            condition.await();
            System.out.print(str);
            nextCondition.signal();
        } catch (InterruptedException e) {
            e.printStackTrace();
        } finally {
            this.unlock();
        }
    }
}

}


- 交替输出 - park() / unpark()
```java
public class Uninterruptible {
    public static void main(String[] args) {
        SyncPark syncPark = new SyncPark();
        Thread t1 = new Thread(() -> {
            syncPark.print("a");
        });
        Thread t2 = new Thread(() -> {
            syncPark.print("b");
        });
        Thread t3 = new Thread(() -> {
            syncPark.print("c");
        });
        syncPark.setThreads(t1, t2, t3);
        syncPark.start();
    }
}
class SyncPark {
    private int loopNumber = 5;
    private Thread[] threads;
    public void setThreads(Thread... threads) {
        this.threads = threads;
    }
    public void start() {
        for (Thread thread : threads) {
            thread.start();
        }
        LockSupport.unpark(threads[0]);
    }
    public void print(String str) {
        for (int i = 0; i < loopNumber; i++) {
            LockSupport.park();
            System.out.print(str);
            LockSupport.unpark(nextThread());
        }
    }
    private Thread nextThread() {
        Thread current = Thread.currentThread();
        int index = 0;
        for (int i = 0; i < threads.length; i++) {
            if (threads[i] == current) {
                index = i;
                break;
            }
        }
        if (index < threads.length - 1) {
            return threads[index + 1];
        } else {
            return threads[0];
        }
    }
}

共享模型 - 内存

Java 内存模型

JMM 即 Java Memory Model，它定义了主存（共享内存）、工作内存（线程私有）抽象概念，底层对应着 CPU 寄存器、缓存、硬件内存、 CPU 指令优化等
JMM 体现在以下几个方面

原子性 - 保证指令不会受到线程上下文切换的影响
可见性 - 保证指令不会受 cpu 缓存的影响
有序性 - 保证指令不会受 cpu 指令并行优化的影响

volatile
易变关键字
它可以用来修饰成员变量和静态成员变量（放在主存中的变量），它可以避免线程从自己的工作缓存中查找变量的值，必须到主存中获取它的值，保证了可见性

可见性 & 原子性
可见性保证的是：在多个线程之间，一个线程对 volatile 变量的修改对另一个线程可见，volatile 不能保证原子性，volatile 仅用在一个写线程，多个读线程的情况。
synchronized 语句块既可以保证代码块的原子性，也保证代码块内变量的可见性。但 synchronized 属于重量级操作，性能相对较低

同步模式 - 犹豫模式
犹豫模式 (Balking) 用在一个线程发现另一个线程或本线程已经做了某一件相同的事，那么本线程就无需再做了，直接结束返回
用一个标记来判断该任务是否已经被执行过了
```
@Service
@Slf4j
public class MonitorService {
  private volatile boolean stop;
  // 标记是否执行过 start()
  private volatile boolean starting;
  private Thread monitorThread;
  public void start() {
      synchronized (this) {
          if (starting) {
              return;
          }
          starting = true;
      }
      // 由于上面代码实现的 balking 模式，以下代码只可能被一个线程执行，因此无需互斥
      monitorThread = new Thread(() -> {
          while (!stop) {
              report();
              sleep(2);
          }
          log.info("监控线程已停止...");
          starting = false;
      });
      stop = false;
      log.info("监控线程已启动...");
      monitorThread.start();
  }
  public synchronized void stop() {
      stop = true;
      monitorThread.interrupt();
  }
}
```
有序性
JVM 会在不影响正确性的前提下，可以调整语句的执行顺序。这种特性称之为『指令重排』，多线程下『指令重排』会影响正确性。
volatile 修饰的变量，可以禁用指令重排。禁止的是加 volatile 关键字变量之前的代码被重排序

原理 - volatile
volatile的底层实现原理是内存屏障，Memory Barrier (Memory Fence)
对 volatile 变量的写指令后会加入写屏障
对 volatile 变量的读指令前会加入读屏障

内存屏障
可见性
写屏障 (sfence) 保证在该屏障之前的，对共享变量的改动，都同步到主存中
读屏障 (lfence) 保证在该屏障之后的，对共享变量的读取，加载的是主存中的数据

有序性

写屏障会确保指令重排序时，不会将写屏障之前的代码排在写屏障之后
读屏障会确保指令重排序时，不会将读屏障之后的代码排在读屏障之前

但是不能解决指令交错问题

写屏障仅仅是保证之后的读能够读到新的结果，但不能保证读跑到它前面去
而有序性也只是保证了本线程内相关代码不被重排序
happens - before 规则
happens - before 规定了对共享变量的写操作对其它线程的读操作可见，它是可见性与有序性的一套规则总结，抛开以下 happens - before 规则，JMM 并不能保证一个线程对共享变量的写，对于其它线程对该共享变量的读可见

变量都是指成员变量或静态成员变量

线程解锁 m 之前对变量的写，对于接下来对 m 加锁的其它线程对该变量的读可见

static int x;
static Object m = new Object();
new Thread(() -> {
    synchronized (m) {
        x = 10;
    }
}, "t1").start();
new Thread(() -> {
    synchronized (m) {
        System.out.println(x);
    }
}, "t2").start();

线程对 volatile 变量的写，对接下来其它线程对该变量的读可见

volatile static int x;
new Thread(()->{
    x = 10;
},"t1").start();
new Thread(()->{
    System.out.println(x);
},"t2").start();

线程 start() 前对变量的写，对该线程开始后对该变量的读可见

static int x;
x = 10;
new Thread(()->{
    System.out.println(x);
},"t2").start();

线程结束前对变量的写，对其它线程得知它结束后的读可见（比如其它线程调用 t1.isAlive() 或 t1.join()等待它结束）

static int x;
Thread t1 = new Thread(()->{
     x = 10;
},"t1").start();
t1.join();
System.out.println(x);

线程 t1 打断 t2 (interrupt) 前对变量的写，对于其他线程得知 t2 被打断后对变量的读可见（通过 t2.interrupted 或 t2.isInterrupted）

static int x;
public static void main(String[] args) {
    Thread t2 = new Thread(()->{
        while(true) {
            if(Thread.currentThread().isInterrupted()) {
                log.debug("{}",x);
                break;
            }
        }
    },"t2").start();
    new Thread(()->{
        try {
            Thread.sleep(1000);
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
        x = 10;
        t2.interrupt();
    },"t1").start();
    while(!t2.isInterrupted()) {
        Thread.yield();
    }
    log.debug("{}",x);
}

对变量默认值（0，false，null）的写，对其它线程对该变量的读可见
具有传递性，如果 x hb-> y 并且 y hb-> z 那么有 x hb-> z ，配合 volatile 的防指令重排，有下面的例子

volatile static int x;
static int y;
public static void main(String[] args) {
    new Thread(() -> {
        y = 10;
        x = 20;
    }, "t1").start();
    new Thread(() -> {
        // x=20 对 t2 可见, 同时 y=10 也对 t2 可见
        System.out.println(x);
    }, "t2").start();
}

共享模型 - 无锁

使用原子整数 AtomicInteger ，可无锁解决线程安全问题。其中的关键是 compareAndSet（比较并设置值），它的简称就是 CAS（也有 Compare And Swap 的说法），它必须是原子操作

class AccountCas implements Account {
    //使用原子整数
    private AtomicInteger balance;
    public AccountCas(int balance) {
        this.balance = new AtomicInteger(balance);
    }
    @Override
    public Integer getBalance() {
        // 得到原子整数的值
        return balance.get();
    }
    @Override
    public void withdraw(Integer amount) {
        while(true) {
            // 获得修改前的值
            int prev = balance.get();
            // 获得修改后的值
            int next = prev-amount;
            // 比较并设值
            if(balance.compareAndSet(prev, next)) {
                break;
            }
        }
    }
}

CAS

CAS 的工作流程

当一个线程要去修改 Account 对象中的值时，先用 get() 获取值prev，然后再将其设置为新的值 next（调用 CAS 方法）。在调用 CAS 方法时，会将 prev 与 balance 进行比较

如果两者相等，就说明该值还未被其他线程修改，可以进行修改操作
如果两者不相等，就不设置值，重新调用 get() 获取值 prev，然后再将其设置为新的值 next（调用cas方法），直到修改成功为止

CAS 的特点
结合 CAS 和 volatile 可以实现无锁并发，适用于线程数少、多核 CPU 的场景下
- CAS 必须借助 volatile 才能读取到共享变量的新值，来实现比较并交换的效果
CAS 体现的是无锁并发、无阻塞并发
- 因为没有使用 synchronized，所以线程不会陷入阻塞，这是效率提升的因素之一
- 一般情况下，使用无锁比使用加锁的效率更高
- 但如果竞争激烈，可以想到重试必然频繁发生，反而效率会受影响
CAS 的底层是 lock cmpxchg 指令（X86 架构），在单核 CPU 和多核 CPU 下都能够保证比较 - 交换的原子性
在多核状态下，某个核执行到带 lock 的指令时，CPU 会让总线锁住，当这个核把此指令执行完毕，再开启总线。这个过程中不会被线程的调度机制所打断，保证了多个线程对内存操作的准确性，是原子的

原子整数
JUC 并发包提供了
AtomicBoolean
AtomicInteger
AtomicLong

以 AtomicInteger 为例

AtomicInteger i = new AtomicInteger(0);
// 获取并自增（i = 0, 结果 i = 1, 返回 0），类似于 i++
i.getAndIncrement();
// 自增并获取（i = 1, 结果 i = 2, 返回 2），类似于 ++i
i.incrementAndGet();
// 自减并获取
i.decrementAndGet();
// 获取并自减
i.getAndDecrement();
// 获取并加值（i = 0, 结果 i = 5, 返回 0） 
i.getAndAdd(5);
// 加值并获取
i.addAndGet(-5);
// 获取并更新（i = 0, p 为 i 的当前值, 结果 i = -2, 返回 0） 
// 其中函数中的操作能保证原子，但函数需要无副作用
// 如果在 lambda 中引用了外部的局部变量，要保证该局部变量是 final 的 
i.getAndUpdate(p -> p - 2);
// 更新并获取
i.updateAndGet(p -> p + 2);
// 获取并计算（i = 0, p 为 i 的当前值, x 为参数1, 结果 i = 10, 返回 0） 
// 可以通过 参数1 来引用外部的局部变量，但因为其不在 lambda 中因此不必是 final 的
i.getAndAccumulate(10, (p, x) -> p + x);
// 计算并获取
i.accumulateAndGet(-10, (p, x) -> p + x);

原子引用

AtomicReference
AtomicMarkableReference
AtomicStampedReference
```
BigDecimal initialValue = new BigDecimal(1);
AtomicReference<BigDecimal> balance = new AtomicReference<>(initialValue);
```
ABA问题
主线程仅能判断出共享变量的值与初值 A 是否相同，不能感知到这种从 A 改为 B 又改回 A 的情况，如果主线程希望：只要有其它线程动过共享变量，那么自己的 cas 就算失败，这时，仅比较值是不够的，需要再加一个版本号。
AtomicStampedReference 可以给原子引用加上版本号，追踪原子引用整个的变化过程，通过 AtomicStampedReference，我们可以知道，引用变量中途被更改了几次
但有时，并不关心引用变量更改了几次，只关心是否更改过，所以就有了 AtomicMarkableReference
AtomicStampedReference & AtomicMarkableReference 的区别
AtomicStampedReference 需要我们传入整型变量作为版本号，来判定是否被更改过
AtomicMarkableReference 需要我们传入布尔变量作为标记，来判断是否被更改过

原子数组
AtomicIntegerArray
AtomicLongArray
AtomicReferenceArray

字段更新器
AtomicReferenceFieldUpdater // 域字段
AtomicIntegerFieldUpdater
AtomicLongFieldUpdater

利用字段更新器，可以针对对象的某个域（Field）进行原子操作，只能配合 volatile 修饰的字段使用，否则会出现异常

AtomicIntegerFieldUpdater fieldUpdater =
    AtomicIntegerFieldUpdater.newUpdater(Test5.class, "field");
private volatile int field;

原子累加器

视频有需要再看

原理 - LongAdder

原理 - 伪共享

Unsafe

Unsafe 对象提供了非常底层的，操作内存、线程的方法，Unsafe 对象不能直接调用，只能通过反射获得

public class UnsafeAccessor {
    static Unsafe unsafe;
    static {
        try {
            Field theUnsafe = Unsafe.class.getDeclaredField("theUnsafe");
            theUnsafe.setAccessible(true);
            unsafe = (Unsafe) theUnsafe.get(null);
        } catch (NoSuchFieldException | IllegalAccessException e) {
            throw new Error(e);
        }
    }
    static Unsafe getUnsafe() {
        return unsafe;
    }
}
public static void main(String[] args) {
    Unsafe unsafe = UnsafeAccessor.getUnsafe();
    Field id = Student.class.getDeclaredField("id");
    Field name = Student.class.getDeclaredField("name");
    // 获得成员变量的偏移量
    long idOffset = UnsafeAccessor.unsafe.objectFieldOffset(id);
    long nameOffset = UnsafeAccessor.unsafe.objectFieldOffset(name);
    Student student = new Student();
    // 使用 cas 方法替换成员变量的值，返回 boolean 类型的值
    UnsafeAccessor.unsafe.compareAndSwapInt(student, idOffset, 0, 20); 
    UnsafeAccessor.unsafe.compareAndSwapObject(student, nameOffset, null, "张三");
}

共享模型 - 不可变

如果一个对象不能够修改其内部状态（属性），那么它就是线程安全的，因为不存在并发修改
在 web 阶段学习时，设计 Servlet 时为了保证其线程安全，都会有这样的建议：不要为 Servlet 设置成员变量，这种没有任何成员变量的类是线程安全的。因为成员变量保存的数据也可以称为状态信息，因此没有成员变量就称之为【无状态】
final 的使用

属性用 final 修饰，保证了该属性是只读的，不能修改
类用 final 修饰，保证了该类中的方法不能被覆盖，防止子类无意间破坏不可变性

通过创建副本对象来避免共享的手段称之为【保护性拷贝（defensive copy）】

原理 - final

设置 final 变量的原理

获取 final 变量的原理

共享模型 - 并发工具

线程池

下面学习 ThreadPoolExecutor 图片.png 下面学习 ThreadPoolExecutor

线程池状态

状态名称	高3位的值(二进制)	描述
running	111 (-1)	接收新任务，同时处理任务队列中的任务
shutdowm	000 (0)	不接受新任务，但是处理任务队列中的任务
stop	001 (1)	中断正在执行的任务，同时抛弃阻塞队列中的任务
tidying	010 (2)	任务执行完毕，活动线程为 0，即将进入终结阶段
terminated	011 (3)	终结状态

ThreadPoolExecutor 使用 int 的高 3 位来表示线程池状态，低 29 位表示线程数量
这些信息存储在一个原子变量 ctl 中，目的是：将线程池状态与线程个数合二为一，这样就可以用一次 cas 原子操作进行赋值

// c 为旧值， ctlOf 返回结果为新值
ctl.compareAndSet(c, ctlOf(targetState, workerCountOf(c))));
// rs 为高 3 位代表线程池状态， wc 为低 29 位代表线程个数，ctl 是合并它们
private static int ctlOf(int rs, int wc) { return rs | wc; }

构造方法

public ThreadPoolExecutor(int corePoolSize,                        // 核心线程数
                          int maximumPoolSize,                    // 最大线程数
                          long keepAliveTime,                    // 救急线程空闲时的生存时间
                          TimeUnit unit,                        // 救急线程的时间单位
                          BlockingQueue<Runnable> workQueue,    // 阻塞队列（存放任务）
                          ThreadFactory threadFactory,            // 线程工厂（可以给线程取名字）
                          RejectedExecutionHandler handler)        // 拒绝策略
{}

补充说明

阻塞队列的种类：
- 有界阻塞队列 ArrayBlockingQueue
- 无界阻塞队列 LinkedBlockingQueue
- 最多只有一个同步元素的 SynchronousQueue
- 优先队列 PriorityBlockingQueue
jdk 提供了 4 种实现拒绝策略
- AbortPolicy：让调用者抛出 RejectedExecutionException 异常，这是默认策略
- CallerRunsPolicy：让调用者运行任务
- DiscardPolicy：放弃本次任务
- DiscardOldestPolicy：放弃队列中最早的任务，本任务取而代之
其他著名框架实现的拒接策略
- Dubbo 的实现：在抛出 RejectedExecutionException 异常之前会记录日志，并 dump 线程栈信息，方便定位问题
- Netty 的实现：创建一个新线程来执行任务
- ActiveMQ 的实现：带超时等待 (60s) 尝试放入队列
- PinPoint 的实现：使用了一个拒绝策略链，会逐一尝试策略链中每种拒绝策略
  工作方式
线程池中刚开始没有线程，当一个任务提交给线程池后，线程池会创建一个新线程来执行任务
当线程数达到核心线程数，并没有线程空闲，这时再加入任务，新加的任务会被加入阻塞队列排队，直到有空闲的线程
如果队列选择了有界队列，那么任务超过了队列大小时，会创建 maximumPoolSize - corePoolSize 个线程来救急，救急线程用完以后，超过生存时间后会被释放

如果线程到达最大线程数，但仍然有新任务，这时会执行拒绝策略

创建线程池的工厂

根据构造方法，JDK 的 Executors 类中提供了众多工厂方法来创建各种用途的线程池
newFixedThreadPool

public static ExecutorService newFixedThreadPool(int nThreads) {
  return new ThreadPoolExecutor(nThreads, nThreads,
                                0L, TimeUnit.MILLISECONDS,
                                new LinkedBlockingQueue<Runnable>());
}

特点

核心线程数 == 最大线程数
即没有救急线程被创建，因此无需超时时间
阻塞队列是无界，可以放任意数量的任务
适用于任务量已知，相对耗时的任务

newCachedThreadPool

public static ExecutorService newCachedThreadPool() {
    return new ThreadPoolExecutor(0, Integer.MAX_VALUE,
                                  60L, TimeUnit.SECONDS,
                                  new SynchronousQueue<Runnable>());
}

特点

核心线程数是 0，最大线程数是 Integer.MAX_VALUE，救急线程的空闲生存时间是 60s，意味着全部都是救急线程（60s 后可以回收）
救急线程可以无限创建
整个线程池表现为：线程数会根据任务量不断增长，没有上限，当任务执行完毕，空闲 1分钟后释放线程。
适合任务数比较密集，但每个任务执行时间较短的情况
队列采用了 SynchronousQueue 实现
- 特点是：它没有容量，没有线程来取是放不进去的，只有当线程取任务时，才会将任务放入该阻塞队列中（一手交钱、一手交货）

newSingleThreadExecutor

public static ExecutorService newSingleThreadExecutor() {
    return new FinalizableDelegatedExecutorService
        (new ThreadPoolExecutor(1, 1,
                                0L, TimeUnit.MILLISECONDS,
                                new LinkedBlockingQueue<Runnable>()));
}

使用场景：希望多个任务排队执行。当任务数多于 1 时，会放入无界队列排队。任务执行完毕，这唯一的线程不会被释放。
和单线程及 newFixedThreadPool 的区别

自己创建一个单线程串行执行任务，如果任务执行失败而终止，那么没有任何补救措施。而线程池还会新建一个线程，保证池的正常工作
Executors.newSingleThreadExecutor() 线程个数始终为1，不能修改
FinalizableDelegatedExecutorService 类应用的是装饰器模式，只对外暴露了 ExecutorService 接口，因此不能调用 ThreadPoolExecutor 中特有的方法
Executors.newFixedThreadPool(1) 线程个数初始时为 1，以后还可以修改。对外暴露的是 ThreadPoolExecutor 对象，可以强转后调用 setCorePoolSize 等方法进行修改
```
// 强转为ThreadPoolExecutor
ThreadPoolExecutor threadPool = (ThreadPoolExecutor) Executors.newFixedThreadPool(1);
// 改变核心线程数
threadPool.setCorePoolSize(2);
```
提交任务
```java // 执行任务 void execute(Runnable command);

// 提交任务，用返回值 Future 获得任务执行结果

Future submit(Callable task);

// 提交 tasks 中所有任务

List> invokeAll(Collection<? extends Callable> tasks);

// 提交 tasks 中所有任务，带超时时间

List> invokeAll(Collection<? extends Callable> tasks, long timeout, TimeUnit unit);

// 提交 tasks 中所有任务，哪个任务先成功执行完毕，返回此任务执行结果，其它任务取消

T invokeAny(Collection<? extends Callable> tasks);

// 提交 tasks 中所有任务，哪个任务先成功执行完毕，返回此任务执行结果，其它任务取消，带超时时间

T invokeAny(Collection<? extends Callable> tasks, long timeout, TimeUnit unit);

<a name="OJCxS"></a>
#### 关闭线程池
```java
// 线程池状态变为 shutdowm，此方法不会阻塞调用线程的执行
void shutdown();
// 线程池状态变为 stop，会将队列中的任务返回
List<Runnable> shutdownNow();
// 不在 running 状态的线程池，此方法就返回 true
boolean isShutdown();
// 线程池状态是否是 terminated
boolean isTerminated();
// 调用 shutdown 后，由于调用线程并不会等待所有任务运行结束，因此如果它想在线程池 terminated 后做些事情，可以利用此方法等待
boolean awaitTermination(long timeout, TimeUnit unit);

任务调度线程池

在『任务调度线程池』功能加入之前，可以使用 java.util.Timer 来实现定时功能
Timer 的优点在于简单易用，但由于所有任务都是由同一个线程来调度，因此所有任务都是串行执行的，同一时间只能有一个任务在执行，前一个任务的延迟或异常都将会影响到之后的任务
Timer测试

public static void main(String[] args) {
    Timer timer = new Timer();
    TimerTask task1 = new TimerTask() {
        @Override
        public void run() {
            log.debug("task 1");
            Thread.sleep(2000);
        }
    };
    TimerTask task2 = new TimerTask() {
        @Override
        public void run() {
            log.debug("task 2");
        }
    };
    // 使用 timer 添加两个任务，希望它们都在 1s 后执行。但由于 timer 内只有一个线程来顺序执行队列中的任务，因此『任务1』的延时，影响了『任务2』的执行
    timer.schedule(task1, 1000);
    timer.schedule(task2, 1000);
}
// 输出结果
20:46:09.444 c.TestTimer [main] - start... 
20:46:10.447 c.TestTimer [Timer-0] - task 1 
20:46:12.448 c.TestTimer [Timer-0] - task 2

ScheduledExecutorService 测试

public static void main(String[] args) {
    ScheduledExecutorService pool = Executors.newScheduledThreadPool(2);
    // 添加两个任务，希望它们都在 1s 后执行
    pool.schedule(() -> {
        System.out.println("任务1，执行时间：" + new Date());
        Thread.sleep(2000);
    }, 1000, TimeUnit.MILLISECONDS);
    pool.schedule(() -> {
        System.out.println("任务2，执行时间：" + new Date());
    }, 1000, TimeUnit.MILLISECONDS);
    // 间隔是 上一个任务开始 <-> 延时 <-> 下一个任务开始
    pool.scheduleAtFixedRate();
    // 间隔是 上一个任务结束 <-> 延时 <-> 下一个任务开始
    pool.scheduleWithFixedDelay();
}
// 输出结果
任务1，执行时间：Thu Jan 03 12:45:17 CST 2019
任务2，执行时间：Thu Jan 03 12:45:17 CST 2019

整个线程池表现为：线程数固定，任务数多于线程数时，会放入无界队列排队。任务执行完毕，这些线程也不会被释放。用来执行延迟或反复执行的任务

Java 基础

基础

八种基本类型

重载 & 重写

hashCode & equals

== 和 equals()

单继承 & 多继承

容器

概览

List

LinkedList

概览

Vector

Map

HashMap

概览

put()

源码中的重要常量

LinkedHashMap

概览

TreeMap

概览

Hashtable

概览

Set

HashSet

LinkedHashSet

TreeSet

Queue

PriorityQueue

ArrayDeque

常见问题

为什么使用集合

如何选用集合

List，Set，Queue，Map 的区别

ArrayList & LinkedList 的区别

ArrayDeque & LinkedList 的区别

Comparable & Comparator 的区别

线程的状态

五种状态

六种状态

共享模型 - 管程

相关的概念

synchronized

变量的线程安全分析

Monitor

Java 对象头

原理 - Monitor

原理 - Synchronized

轻量级锁

锁膨胀

偏向锁

偏向状态

偏向锁被撤销的情况

批量重偏向

wait() / notify()

原理

同步模式 - 保护性暂停

定义

实现

与 wait() / notify() 对比

原理

线程状态转换

活跃性

死锁

活锁

饥饿

ReentrantLock

同步模式 - 顺序控制

固定运行顺序

共享模型 - 内存

Java 内存模型

volatile

可见性 & 原子性

同步模式 - 犹豫模式

有序性

原理 - volatile

内存屏障

happens - before 规则

共享模型 - 无锁