前言/补充
今天不学习，明天变垃圾
- 本文主要内容：常见锁策略、CAS【面试常见】和synchronized原理。
- 初阶part是工作中常用+面试中常考， 进阶part是工作中很少用+面试中常考
（多线程中最常用的是synchronized！） - 模拟实现【阻塞队列、定时器、线程池】：
Main1-3
（一定要自己实现！！）
4. 描述一下线程池的执行流程和拒绝策略有哪些？【面试题！】
参考：线程池执行流程及拒绝策略
答： ① 线程池执行流程：
当任务来了之后，线程池的执行流程是：先判断当前线程数是否大于核心线程数？如果结果为 false，则新建线程并执行任务；如果结果为 true，则判断任务队列是否已满？如果结果为 false，则把任务添加到任务队列中等待线程执行，否则则判断当前线程数量是否超过最大线程数？如果结果为 false，则新建线程执行此任务，否则将执行线程池的拒绝策略
② 拒绝策略：
当任务过多且线程池的任务队列已满时，此时就会执行线程池的拒绝策略，线程池的拒绝策略默认有以下 4 种：
AbortPolicy：中止策略，线程池会抛出异常并中止执行此任务；
CallerRunsPolicy：把任务交给添加此任务的（main）线程来执行；
DiscardPolicy：忽略此任务，忽略最新的一个任务；
DiscardOldestPolicy：忽略最早的任务，最先加入队列的任务。
默认的拒绝策略为 AbortPolicy 中止策略。
一、常见锁策略
一）乐观锁VS悲观锁
- 实际开发中其实基本不会考虑锁策略，除非你要自己实现一个锁
- 要求：对于锁策略的名词有简单的了解就行，面试的时候也是考察概念（背）
- 乐观锁vs悲观锁：描述的是两种不同的加锁态度
- 乐观锁：预测锁冲突的概率不高，因此做的工作就可以简单一些。
悲观锁：预测锁冲突的概率较高，因此做的工作就会复杂一些。 - 锁冲突：两个线程竞争同一把锁，此时就会产生锁冲突，然后线程就会进入阻塞等待。
- 如果面试中问到也建议多举例子（万全准备 VS 随遇而安）
- synchronized 初始使用乐观锁策略， 当发现锁竞争比较频繁的时候, 就会自动切换成悲观锁策略。
- 乐观锁的一个重要功能就是要检测出数据是否发生访问冲突， 我们可以引入一个 “版本号” 来解决。（“版本号”其实就是修改次数）
二）读写锁VS普通互斥锁
- 普通的互斥锁就如同synchronized，即：两个线程竞争同一把锁，没抢占到锁的线程就会产生等待。
- 读写锁分两种情况：加读锁（访问）、加写锁（修改）
- 多个线程同时读同一个变量是互相不会有影响的，此时也就不必加锁。
- ① 读锁和读锁之间是不会产生竞争的
② 写锁和写锁之间是有竞争的
③ 读锁和写锁之间是有竞争的
（在实际开发中，读的场景往往很多，而写的场景往往更少；所以读写锁相比于普通互斥锁就少了很多的锁竞争，优化了效率。） - 读写锁就是把读操作和写操作区分对待， Java 标准库提供了 ReentrantReadWriteLock 类, 实现了读写锁。
- ReentrantReadWriteLock.ReadLock 类表示一个读锁， 这个对象提供了 lock / unlock 方法进行加锁解锁.
- ReentrantReadWriteLock.WriteLock 类表示一个写锁， 这个对象也提供了 lock / unlock 方法进行加锁解锁.
- 注意, 只要是涉及到 “互斥”, 就会产生线程的挂起等待； 一旦线程挂起, 再次被唤醒就不知道隔了多久了。因此尽可能减少 “互斥” 的机会, 就是提高效率的重要途径。
- 读写锁特别适合于 “频繁读, 不频繁写” 的场景中。 (这样的场景其实也是非常广泛存在的)。
- 注意： synchronized 不是读写锁！
三）重量级锁VS轻量级锁
- 轻量级锁就是加锁解锁的开销比较小；纯型的纯用户态的加锁逻辑就是开销比较小的
- 重量级锁就是加锁解锁的开销比较大；纯型的进入内核态的加锁逻辑就是开销比较大的
- 轻量级锁和重量级锁是站在结果的角度看待的，看最终加锁解锁操作消耗的时间是多还是少；而乐观锁和悲观锁是站在加锁的过程上去看待的，看加锁解锁过程中干的工作是多还是少。
- 通常情况下，干的工作多消耗的时间也较多。所以：乐观锁一般也是比较轻量，而悲观锁一般是比较重量的，但是不绝对。
- 锁的核心特性 “原子性”, 这样的机制追根溯源是 CPU 这样的硬件设备提供的
- CPU 提供了 “原子操作指令”
- 操作系统基于 CPU 的原子指令, 实现了 mutex 互斥锁.
- JVM 基于操作系统提供的mutex互斥锁
JVM实现了 synchronized 和 ReentrantLock 等关键字和类.
注： synchronized 并不仅仅是对 mutex 进行封装, 在 synchronized 内部还做了很多其他的工作。
- 重量级锁: 加锁机制重度依赖了 OS 提供了 mutex。
（大量的内核态、用户态切换； 容易引发线程调度） - 轻量级锁: 加锁机制尽可能不使用 mutex, 而是尽量在用户态代码完成， 实在搞不定了再使用 mutex.
（少量的内核态用户态切换； 不太容易引发线程调度） - synchronized 开始是一个轻量级锁， 如果锁冲突比较严重就会自动变成重量级锁。
四）自旋锁VS挂起等待锁
- 自旋锁是轻量级锁的一种典型实现：自旋就类似于“忙等”，需要消耗大量的CPU反复询问当前的锁是否已经准备就绪；但是能够第一时间知道准备就绪。（自旋锁是纯用户态实现的）
- 挂起等待锁是重量级锁的一种典型实现：此时可能会导致获取到锁的时间没那么及时，但是在等待的时间里CPU可以做别的事情。
- 自旋锁是一种典型的 轻量级锁 的实现方式。
优点: 没有放弃 CPU, 不涉及线程阻塞和调度, 一旦锁被释放, 就能第一时间获取到锁。
缺点: 如果锁被其他线程持有的时间比较久,那么就会持续的消耗 CPU 资源。 (而挂起等待的时候是 不消耗 CPU 的)。
- synchronized 中的轻量级锁策略大概率就是通过自旋锁的方式实现的.
五）公平锁VS非公平锁
- 公平锁：其实就是“先来后到”，就是先来的线程先使用
- 非公平锁：就是不管先后顺序直接去抢占
- 操作系统默认的锁的调度是非公平锁。但是如果要想实现公平锁就需要引入额外的数据结构来记录加锁的顺序，此时就需要一定的额外开销。
- synchronized 是非公平锁。
六）可重入锁VS不可重入锁
- 可重入锁：同一个线程针对同一把锁连续加锁两次，不会死锁
- 不可重入锁：同一个线程针对同一把锁连续加锁两次，会死锁
- 可重入锁（也叫做递归锁），允许同一个线程多次获取同一把锁。
- Java里只要以Reentrant开头命名的锁都是可重入锁，而且JDK提供的所有现成的Lock实现类，包括
synchronized关键字锁都是可重入的。 - 而 Linux 系统提供的 mutex 是不可重入锁。
七）小结（记住概念【面试常见！！】）
1.乐观锁Vs悲观锁
2.普通互斥锁 VS 读写锁
3.轻量级锁VS重量级锁
4.自旋锁VS挂起等待锁
5.公平锁VS非公平锁
6.可重入锁VS不可重入锁
常见面试题
你是怎么理解乐观锁和悲观锁的，具体怎么实现呢？
答： ① 悲观锁认为多个线程访问同一个共享变量冲突的概率较大, 会在每次访问共享变量之前都去真正加锁。
② 乐观锁认为多个线程访问同一个共享变量冲突的概率不大， 并不会真的加锁, 而是直接尝试访问数据。 在访问的同时识别当前的数据是否出现访问冲突。
③ 悲观锁的实现就是先加锁(比如借助操作系统提供的 mutex), 获取到锁再操作数， 获取不到锁就等待。
④ 乐观锁的实现可以引入一个版本号，借助版本号识别出当前的数据访问是否冲突。介绍下读写锁?
答： ① 读写锁就是把读操作和写操作分别进行加锁.
② 读锁和读锁之间不互斥.
③ 写锁和写锁之间互斥.
④ 写锁和读锁之间互斥.
⑤ 读写锁最主要用在 “频繁读, 不频繁写” 的场景中.什么是自旋锁，为什么要使用自旋锁策略呢，缺点是什么？
答： ① 自旋锁即：如果获取锁失败, 立即再尝试获取锁, 无限循环, 直到获取到锁为止。 第一次获取锁失败, 第二次的尝试会在极短的时间内到来； 一旦锁被其他线程释放, 就能第一时间获取到锁。
② 相比于挂起等待锁,
优点: 没有放弃 CPU 资源, 一旦锁被释放就能第一时间获取到锁, 更高效. 在锁持有时间比较短的场景下非常有用。
缺点: 如果锁的持有时间较长, 就会浪费 CPU 资源。synchronized 是可重入锁么？
答： ① 是可重入锁.
② 可重入锁指的就是连续两次加锁不会导致死锁.
③ 实现的方式是在锁中记录该锁持有的线程身份, 以及一个计数器(记录加锁次数)。如果发现当前加锁的线程就是持有锁的线程, 则直接计数自增。
【补】synchronized
对于synchronized：
①既是乐观锁，也是悲观锁
②既是轻量级锁，又是重量级锁
③乐观锁的部分是基于自旋锁实现的，悲观锁的部分是基于挂起等待锁实现的
所以：
synchronized是自适应的：初始使用的时候是乐观锁/轻量级锁/自旋锁，如果锁竞争不激烈就保持上述状态不变；但是如果锁竞争激烈了，synchronized就会自动升级成悲观锁/重量级锁/挂起等待锁。
④不是读写锁，而是普通互斥锁
⑤是非公平锁
⑥是可重入锁
（在标准库中是有另外的其他锁能够实现④⑤的）
二、CAS
一）CAS简介
- CAS【 compare and swap】即比较并交换：把内存中的某个值M和CPU寄存器A中的值进行比较，如果两个值相同，就把另一个寄存器B中的值和内存的值M进行交换（把内存的值M放到寄存器B，同时把寄存器B的值写给内存；其实这是一个“写内存”操作，更关心的是交换后内存值M）
（返回值是是否操作成功） - CAS伪代码：
boolean CAS(address, expectValue, swapValue) {
// address:内存地址
// expectValue:比较寄存器A
// swapValue:交换寄存器B
if (&address == expectedValue) {
&address = swapValue;
//这里的赋值其实就是“交换”。
//但是其实并不关心寄存器B里的是啥，更关心的是内存中是啥！
//所以把交换近似看成是赋值其实也没毛病。
return true;
}
return false;
}
// 以上的这一组操作是通过硬件实现的，一个CPU指令完成的，也就是说是原子性的！
// 则CAS是线程安全的!! 同时还高效。（高效：因为不涉及到锁冲突+线程等待）
// 故：基于CAS实现一些逻辑的时候即使不加锁也是可以实现线程安全的！
- 当多个线程同时对某个资源进行CAS操作，只能有一个线程操作成功，但是并不会阻塞其他线程,其他线程只会收到操作失败的信号.
- CAS 可以视为是一种乐观锁. (或者可以理解成 CAS 是乐观锁的一种实现方式)
二）CAS的实现
针对不同的操作系统，JVM 用到了不同的 CAS 实现原理，简单来讲：
- java 的 CAS 利用的的是 unsafe 这个类提供的 CAS 操作；
- unsafe 的 CAS 依赖了的是 jvm 针对不同的操作系统实现的 Atomic::cmpxchg；
- Atomic::cmpxchg 的实现使用了汇编的 CAS 操作，并使用 cpu 硬件提供的 lock 机制保证其原子性。
简而言之，是因为硬件予以了支持，软件层面才能做到。
三） CAS的应用
- CAS只是在特定场景使用，加锁的适用面更广，并且加锁代码往往比CAS的可读性更好。
- CAS的操作是由CPU的一条指令原子性完成的，所以是线程安全的，效率也较高。（高效是因为没有锁冲突和线程等待）
- CAS最常用的两个场景：
1） 实现原子类：
① 如前面讲过的count++，在多线程环境下线程是不安全的，要想线程安全，就需要加锁，但是加锁后性能就会大打折扣；所以，我们就可以基于CAS操作来实现“原子”的++，从而保证线程的安全和高效。
② 标准库中提供了 java.util.concurrent.atomic 包, 里面的类都是基于这种方式来实现的。
典型的就是 AtomicInteger 类. 其中的 getAndIncrement 相当于 i++ 操作。
③ 伪代码的实现：
class AtomicInteger {
// AtomicYinteger : 这个其实是在标准库中已经封装好的一个类
private int value;
public int getAndIncrement() {
// getAndIncrement() ：这个方法就相当于后置++
int oldValue = value;
// 此处的oldValue相当于是寄存器A，是把内存中的value值读取到寄存器中!
while ( CAS(value, oldValue, oldValue+1) != true) {
// 把(oldValue+1)理解成时另外一个寄存器B的值
// 比较看内存中的value值是否和寄存器A的值相同，如
//果相同就把寄存器B的值给设置到value内存中，同时
//CAS返回true，结束循环；
//如果不相同，就无事发生，CAS返回false，进入循环
//体里，重新读取内value值到寄存器A中。
// 其实就类似于给内存做个标记，使用寄存器A来检查该内存值是不是之前的值，也就是有没有被修改。
//（寄存器A就是标记）！！
oldValue = value;
}
return oldValue;
}
}
④ 注：CAS 是直接读写内存的, 而不是操作寄存器。
2）实现自旋锁：
- 自旋锁是一个纯用户态的轻量级锁，当发现锁被其他线程持有的时候，另外的线程不会挂起等待，而是会反复询问，看当前的锁是否被释放了。（类似于“忙等”）（反复询问其实就是为了抢先执行，节省了进入内核和系统调度的开销）
- 自旋锁伪代码：
public class SpinLock {
private Thread owner = null;
// owner : 当前这把锁是哪个线程获取到的，null就是锁是无人获取的状态/解锁状态。
public void lock(){
// 通过 CAS 看当前锁是否被某个线程持有.
// 如果这个锁已经被别的线程持有, 那么就自旋等待.
// 如果这个锁没有被别的线程持有, 那么就把 owner 设为当前尝试加锁的线程.
while(!CAS(this.owner, null, Thread.currentThread())){
// 比较owner和null是否相同（是否为解锁状态），如果是就进行交换，把当前调用lock的线程的值设置到owner里，相当于此时加锁成功，同时结束循环。
// 如果owner不为null，则CAS不进行交换，返回fasle，会进入循环，此时会立即再次发起判定。
// 也就是如果锁没有线程占用就占用，如果被占用就反复询问，一解锁就及时加锁。
}
}
public void unlock (){
this.owner = null;
}
}
- 自旋锁这种实现是属于消耗CPU资源的，但是换来的是可以第一时间获取到锁。如果当前预期锁的竞争不太激烈的时候（也就是预期在短时间内获取到锁），使用自旋锁就是合适的。
- 自旋锁是一个轻量级锁，也是一个乐观锁。
四）CAS的ABA问题
- CAS的ABA问题【面试的时候谈到CAS，十有八九就会谈到ABA】
1）这是CAS的一个小缺陷
2）在CAS中进行比较的时候，如果此时的寄存器A和内存M的值相同，你无法判定是内存M的值始终不变还是M变了，但是又变回来了
3）CAS的ABA问题其实在大部分情况下也不是事儿，不会出现bug；但是在极端情况下是会出现问题的。
4）ABA在极端情况下是啥效果？
举例：可能会导致一次取钱，两次扣款（也就是在第一个线程完成取款之后，又有人转账，而第二个线程进行CAS检查时候发现数值相同，就进行扣款操作） - 如何解决ABA带来的问题？
只要有一个记录能够记录上内存的变化就可以解决ABA问题了。
那么如何进行记录呢？
——另外搞一个内存，保存内存M的“修改次数”（版本号）或者是“上次修改时间”，通过这两种方法都是可以解决ABA问题的。 - “修改次数”“上次修改时间”都是【只增不减】，也就是说无法再跳回去。
此时比较的就不是寄存器A和内存M了，而是比较版本号/上次修改时间。
相关面试题
- 讲解下你自己理解的 CAS 机制
答：CAS全称 compare and swap, 即 “比较并交换”。 相当于通过一个原子的操作, 同时完成 “读取内存, 比较是否相等, 修改内存” 这三个步骤。本质上需要 CPU 指令的支撑。 - ABA问题怎么解决？
答： ① 给要修改的数据引入版本号。在 CAS 比较数据当前值和旧值的同时, 也要比较版本号是否符合预期。
② 如果发现当前版本号和之前读到的版本号一致, 就真正执行修改操作, 并让版本号自增; 如果发现当前版本号比之前读到的版本号大, 就认为操作失败。
三、【synchronized原理】
【synchronized原理】主要讨论的是synchronized背后做的事情
一）基本特点
- synchronized的效果是“加锁”，当两个线程针对同一个对象加锁的时候就会出现锁竞争；后来尝试加锁的线程就得阻塞等待，直到前一个线程释放锁。
- synchronized 具有以下特性(只考虑 JDK 1.8):
① 开始时是乐观锁, 如果锁冲突频繁, 就转换为悲观锁.
② 开始是轻量级锁实现, 如果锁被持有的时间较长, 就转换成重量级锁.
③ 实现轻量级锁的时候大概率用到的自旋锁策略
④ 是一种不公平锁
⑤ 是一种可重入锁
⑥ 不是读写锁
二） synchronized加锁的具体过程
- JVM 将 synchronized 锁分为 无锁、偏向锁、轻量级锁、重量级锁 状态。会根据情况，进行依次升级。
- synchronized加锁的具体过程：
1）偏向锁：其实就类似于“懒汉模式”，必要的时候才加锁，能不加就不加。（类似于出现锁冲突才真正加锁）
① 偏向锁不是真加锁，而是只是设置了一个状态。（举例：搞暧昧）
② 无竞争，偏向锁；有竞争，轻量级锁； 竞争激烈，重量级锁。（这叫“锁升级/锁膨胀”，这是JVM实现synchronized的时候为了程序员方便而引入的一些优化机制）
2）轻量级锁
① 此处的轻量级锁就是通过 CAS 来实现。
通过 CAS 检查并更新一块内存 (比如 null => 该线程引用)
如果更新成功, 则认为加锁成功
如果更新失败, 则认为锁被占用,继续自旋式的等待(并不放弃 CPU).
② 自旋操作是一直让 CPU 空转, 比较浪费 CPU 资源.
③ 因此此处的自旋不会一直持续进行, 而是达到一定的时间/重试次数, 就不再自旋了。也就是所谓的 “自适应”。
3）重量级锁
① 如果竞争进一步激烈, 自旋不能快速获取到锁状态, 就会膨胀为重量级锁
② 此处的重量级锁就是指用到内核提供的 mutex .
③ 执行过程：
- 执行加锁操作, 先进入内核态；
- 在内核态判定当前锁是否已经被占用； 如果该锁没有占用, 则加锁成功, 并切换回用户态；
- 如果该锁被占用,则加锁失败，此时线程进入锁的等待队列, 挂起。 等待被操作系统唤醒。
- 经历了一系列的沧海桑田, 这个锁被其他线程释放了, 操作系统也想起了这个挂起的线程, 于是唤醒这个线程, 尝试重新获取锁。
- synchronized更多的考虑到降低程序员的使用负担，内部就实现了轻量级锁和重量级锁的“自适应”操作。
如果当前场景中锁竞争不激烈，则是以轻量级锁状态来进行工作（轻量级锁是通过自旋来实现的，可以第一时间拿到锁）；
如果当前场景中锁竞争激烈，则是以重量级锁状态来进行工作的（重量级锁通过挂起等待来实现，可能拿到锁每那么及时，但是节省了CPU的开销）
三）synchronized其他的优化手段
synchronized还有其他的优化手段：（一是锁升级/所膨胀，二是锁消除，三锁粗化）
锁消除
- JVM自动判定此处的代码是否需要加锁，如果JVM判定此处的代码是不需要加锁的，但是你写了synchronized，此时就会自动把synchronized给去掉。
- 如：你只有一个线程 或者是 虽然有多个线程，但是多个线程并不涉及修改同一个变量，如果代码中也写了synchronized，此时synchronized加锁操作也直接会被JVM自动去掉。
- synchronized加锁的时候应该是先偏向锁，只是改个标志位，按理来说操作的开销应该是不大的，但是即使如此，能够消除的时候是连多余一点的开销都不想承担。
- 锁消除是一种编译器优化的行为，但是编译器的判定不是特别准，此时如果不是编译器有十足/100%的把握都是不会进行synchronized的自动消除的。 也就是说：锁消除只是在编译器/JVM有十足的把握的时候才进行。
- 编译器+JVM 判断锁是否可消除. 如果可以, 就直接消除
- 有些应用程序的代码中用到了 synchronized, 但其实没有在多线程环境下. (例如 StringBuffer)此时每个 append 的调用都会涉及加锁和解锁， 但如果只是在单线程中执行这个代码, 那么这些加锁解锁操作是没有必要的, 白白浪费了一些资源开销。所以就会自动去掉锁。
（注：StringBuffer线程安全/自动加锁，StringBuilder线程不安全！！！）
锁粗化
- 锁的粒度：synchronized对应的代码块中包含多少的代码，包含的代码越少则锁的粒度越细；包含的代码越多则锁的粒度越粗。
- 锁粗化：就是把细粒度的加锁变为粗粒度的加锁。（只能是对同一个对象加锁的代码！！）
（锁粗化的前提是粗化前后代码逻辑不变） - 一段逻辑中如果出现多次加锁解锁, 编译器 + JVM 会自动进行锁的粗化
- 实际开发过程中, 使用细粒度锁, 是期望释放锁的时候其他线程能使用锁。但是实际上可能并没有其他线程来抢占这个锁， 这种情况 JVM 就会自动把锁粗化, 避免频繁申请释放锁。
相关面试题
什么是偏向锁?
答： 偏向锁不是真的加锁, 而只是在锁的对象头中记录一个标记(记录该锁所属的线程)。 如果没有其他线程参与竞争锁, 那么就不会真正执行加锁操作, 从而降低程序开销。 一旦真的涉及到其他的线程竞争, 再取消偏向锁状态, 进入轻量级锁状态。synchronized 实现原理 是什么？
答： 参考【synchronized原理】所有内容：特点+加锁过程+优化手段。
THINK
- 描述一下线程池的执行流程和拒绝策略有哪些？【面试题！】
- 常见锁策略 + 面试题
- CAS + CAS的ABA问题 + 面试题
- synchronized原理（特点+加锁过程+优化手段）+面试题！
- 面试题超级重要！！！