Java并发实现原理  JDK源码剖析

核心是一把锁+两个条件

put的时候，若队列满了，则阻塞；take的时候，若队列为空，则阻塞

两把锁+两个条件

和ArrayBlockingQueue区别：1. 为了提高并发度，用2把锁，分别控制队头、队尾的操作。put和take之间不互斥。

因为各自拿了一把锁，所以当需要调用对方的condition的signal时，还必须加上对方的锁，就是signalNotEmpty和signalNotFull()函数。

不仅put会通知take，take也会通知put。当put发现非满的时候，也会通知其他put线程；当take发现非空的时候，也会通知其他take线程。

一把锁+一个条件，没有非满的条件

按照元素的优先级从小到大出队列的。正因为如此，PriorityQueue中的2个元素之间需要可以比较大小，并实现Comparable接口。

用数组实现了一个二叉堆，从而按优先级从小到大出队列。另一个区别是没有notFull条件，当元素个数超过数组长度时，执行扩容操作。

延迟队列，也就是一个按延迟时间从小到大出队的PriorityQueue。

本身没有容量。先调put()，线程会阻塞，直到另外一个线程调用了take()，两个线程才同时解锁，反之亦然。

TransferQueue

TransferStack

读不加锁，写加锁

元素不重复，内部封装的一个CopyOnWriteArrayList

多线程操作多个Segment相互独立，每个Segment都继承自ReentrantLock，Segment的数量等于锁的数量，锁彼此相互独立，即“分段锁“

扩容：在扩容完成之后，把该节点再加入新的Hash表；每次按2倍扩容，如果元素处于第i个位置，当再次hash时，必然处于第i个或者第i+oldCapacity个位置。

get：第一次hash，找到所在的Segment，第二次hash，找到Segment里面对应的下标

没有了分段锁，CAS+链表/红黑树。

构造函数：1.5倍的初始容量+1，再往上取最接近2的整除次方

初始化：如何避免多个线程重复初始化？通过CAS把sizeCtl设置为-1，初始化完成后，再把sizeCtl设置回去。其他线程一直执行while循环，自旋等待。

put：1.整个数组初始化；2.第i个槽的第一个元素初始化；3.槽正在扩容，帮助其扩容；4.元素放入槽内。synchronized(f)f对应数组下标位置的头节点。

扩容：1.新建一个ForwardingNode，即转发节点，在这个节点记录的是新的ConcurrentHashMap的引用，当线程访问到ForwardingNode之后，会去查询新的ConrueentHashMap；2.sizeCtl=-1，表示整个HashMap正在初始化；sizeCtl=其他负数，表示多个线程在对HashMap做并发扩容；sizeCtl=cap时，tab=null，未初始化之前的初始容量，扩容成功后，sizeCtl存储的是下一次扩容的阈值。

存放任务的阻塞队列

对线程池内部各种变量进行互斥访问控制锁

线程集合，每一个线程是一个Worker对象。Worker继承AQS

首先判断corePoolSize，其次判断blockingQueue是否已满，接着判断maxPoolSize，最后使用拒绝策略。

int型的ctl变量，高3位表示线程池状态，低29位表示线程池的个数

线程池的状态迁移：RUNNING（-1）、SHUNDOWN（0）、STOP（1）、TIDYING（2）、TERMINATED（3）

关闭函数shutdown和shutdownNow()，在队列为空，线程池也为空后，进入TIDYING状态，最后执行钩子函数terminated()，进入TERMINATED，线程池才 真正灭亡。

不断调用awaitTermination方法判断是否到达了最终状态。

shutdown和shutdownNow区别：1.前者不会清空任务队列，会等待任务执行完成；后者和会清空任务队列。
2.前者只会中断空闲的线程，后者会中断所有线程。

一个线程在执行一个任务之前，会先加锁。这意味着可以通过是否持有锁，来判断线程是否处于空闲状态。

对于一个Worker来说，不是只执行一个任务，而是源源不断地从队列中取任务执行，这是一个不断循环的过程。

执行任务前要加索。

让调用者在自己的线程里面执行，线程池不做处理

线程池抛异常

线程池直接把任务丢掉，当作什么也没发生

1：并行下载100个网页；

2.通过allOf，等待所有网页下载完毕，收集返回结果；

3.统计在这100个网页中，含有单词”XXX“的网页的个数

正在运行的线程能否强制杀死？答案肯定是不能的。如果强制杀死线程，则线程中所使用的资源，例如文件描述符、网络连接等不能正常关闭。

一旦一个线程运行起来，就不要去强制打断它，合理的关闭办法是让其运行完，干净地释放掉所有资源，然后退出。如果是一个不断循环运行的线程，就需要用到线程间的通信机制，让主线程通知其退出。

C语言中，main(...)函数推出后，整个程序也就退出了，但在Java中不会。

当所有的非守护线程退出后，整个JVM进程就会退出。意思就是“守护线程不算作数”，守护线程不影响整个JVM进程的退出。例如：垃圾回收线程就是守护线程，当开发者的所有前台线程（非守护线程）都退出之后，整个JVM进程就退出了。

判断标志位来退出死循环，开发一般不会这样写

join()方法又等同于：synchronized(thread1)){ thread1.wait();}。

Thread 执行完run()方法会调用notifyAll()方法。

只有声明了会抛出InterruptedException的函数才会抛出异常。比例：sleep()、wait()、join()

能够被中断的阻塞称为轻量级阻塞，对应的线程状态是WAITING或者TIMED_WAITING；而像synchronized这种不能被中断的阻塞称为重量级阻塞，对应的状态是BLOCKED。

t.interrupted() 相当于给线程发送了一个唤醒的信号，所以如果线程此时恰好处于WAITING或者TIMED_WAITING状态，就会抛出一个InterruptedException，并且线程被唤醒。而如果线程此时并没有阻塞，则线程什么都不会做。

这两个函数都是线程用来判断自己是否收到过中断信号的，前者是非静态函数，后者是静态函数。二者的区别在于，前者是读取中断状态，不修改状态；后者不仅读取中断状态，还会重置中断标志位。

对于非静态成员函数，锁其实是加在对象上的；对于非静态函数，锁是夹在Class对象上的。当然，class本身也是对象。

从程序的角度来看，锁其实就是一个“对象”，这个对象要完成一下几件事情：

在Java对象头里，有一块数据叫Mark Word。这64位中有2个重要字段：锁标志位和占用该锁的thread ID。

内存队列本身要加锁，才能实现线程安全。

阻塞。内存队列满，生产者放不进去数据会被阻塞；当内存队列是空的时候，消费者无事可做会被阻塞。

双向通知。消费者被阻塞时，生产者放入新数据，要notify消费者；反之，生产者被阻塞之后，消费者消费了数据，要notify生产者。

如何阻塞？

如何双向通知？

两个线程之间要通信，对于同一个对象来说，一个线程调用该对象的wait()，另一个线程调用该对象的notify()，该对象本身就需要同步！

wait内部的伪代码：1. 释放锁；2. 阻塞，等待被其他线程notify；3. 重新拿锁。

wait()和notify()所作用的对象和synchronized所作用的对象是同一个，只能有以一个对象，无法区分队列空和队列满两个条件。
这正是Condition要解决的问题。

JVM的规范并没有要求64位的long或者double的写入是原子性的。

在32位的机器上，一个64位变量的写入可能被拆分成两个32位的写操作来执行。导致读取到的可能读到”一般的值“。

内存可见性指的是：写完之后立即对其他线程可见。他的反面是”稍后才能可见“。

多线程情况下，一个线程可能拿到另一个未完全初始化/只是实例化的对象。

x86架构的CPU缓存布局：每个核上都有L1、L2缓存，L3缓存为所有核共用。

因为存在CPU缓存一致性协议，例如MESI，多个CPU之间的缓存不会出现不同步的问题，不会有”内存可见性“的问题。

但是，缓存一致性协议对性能有很大的损耗，为了解决这个问题，在计算单元和L1之间加了Store Buffer、Load Buffer等。

L1、L2、L3和主内存之间是同步的，有缓存一致性协议的保证，但是Store Buffer、Load Buffer和L1之间却是异步的。

操作系统视角下的CPU缓存模型：每一个逻辑CPU都有自己的本地缓存。线程的本地缓存和主内存之间是不同步的。

Store Buffer的延迟写入是重排序的一种，称为内存重排序。除此之外，还有编译器和CPU的指令重排序。

CPU指令重排序。在指令级别，让没有依赖关系的多条指令并行。

CPU内存重排序。CPU有自己的缓存，指令的执行顺序和写入主内存的顺序不完全一致。

线程1：X=1，a=Y；线程2：Y=1，b=X。初始化，X=0，Y=0。请问，两个线程执行完毕之后，a、b的正确结果应该是什么？

重排序的原是什么？什么场景下可以重排序？什么场景下不可以重排序？

单线程程序的重排序规则。不管怎么重排序，单线程程序的执行结果不能改变。

多线程程序的重排序规则。编译器会保证每个线程的重排序语义。

描述两个操作之间的内存可见性。

单线程中的每个操作，对应该线程中任意后序操作。

对于volatile变量的写入，对应后续对这个变量的读取。

如果一个变量不是volatile变量，当一个线程读取、一个线程写入时可能有问题。那岂不是说，在多线程程序中，我们要么加锁，要么必须把所有变量都声明为volatile变量？这显然不能，这归功于happen-before的传递性。

若A happen-before B，B happen-before C，则A happen-before C。

C++的某些情况下，C++的代码是不能禁止指令重排的，但在在Java中却是正确的。

编译器的内存屏障，告诉编译器不要对指令进行重排序。编译完成后，内存屏障就消失了。

CPU的内存屏障是CPU提供的指令，由开发者显示调用。

在volatile写操作的前面插入一个StoreStore屏障。保证volatile写操作不会和之前的写操作重排序。

在volatile写操作的后面插入一个StoreLoad屏障。保证volatile写操作不会和之后的读操作重排序。

在volatile读操作的后面插入一个LoadLoad屏障+LoadStore屏障。保证volatile读操作不会和之后的读操作、写操作重排序。

构造对象不是”原子的“，当一个线程正在构造对象时，另外一个线程可以读到未构造好的”一半对象“。

解决办法：加volatile关键字，加synchronized关键字，加final关键字。

同volatile一样，final关键字也有相应的happen-before语义。

单线程中的每个操作，happen-before于该线程中任意后续操作。

对volatile变量的写，happen-before于后续对这个变量的读。

对synchronized的解锁，happen-before于后续对这个锁的加锁。

开发者层面。volatile、final、synchronized

JVM层面。JMM（happen-before规则）

CPU层面。CPU缓存体系、CPU内存重排序、内存屏障。

synchronized、ReentrantLock、MySQL、Redis

所有调用CAS的地方，都会通过objectFieldOffset(Field var1)函数把成员变量转化成偏移量。

执行CAS操作的时候，不是直接操作value，而是操作valueOffset。

这两种策略并不是互斥的，可以结合使用。如果拿不到锁，先自旋几圈，如果自旋还拿不到锁，再阻塞，synchronized关键字就是这样的实现策略。

把赋值和取值操作合二为一，变成原子操作。

如何支持boolean和double类型

在Unsafe类中，提供了三种类型CAS操作：int、long、Object（引用类型）

boolean比较实际上是1和0的比较

double类型的比较依赖提供的一对double类型和long类型互转的函数

ABA问题，不仅比较值，还要比较版本号，而这正是AtomicStampedReference做的事情。

Integer型或者Long型的CAS没有办法同时比较两个变量，于是只能把值和版本号封装成一个对象，然后通过对象引用的CAS实现。

与AtomicStampedReference原理类似，只是Pair里面的版本号是boolean类型的，只是降低了ABA问题的概率

把一个Long型拆成一个base变量外加多个Cell，每个Cell包装了一个Long变量。

多个线程并发累加的时候，如果并发度低，就直接加到base变量上；如果并发度高，冲突大，平摊到Cell上。最后取值的时候，再把base和这些Cell求sum运算。

因为没有double型的CAS操作，所以是通过把double型转化为Long型来实现的。

在sum求和函数中，并没有对cells[]数组加锁。一边有线程对其执行求和操作，一边还有线程修改数组里的值，也就是最终一致性，而不是强一致性。

LongAddr适合高并发的统计场景，而不适合要对某个Long型变量进行严格同步的场景

每个CPU都有自己的缓存。缓存与主内存进行数据交换的基本单位叫Cache Line（缓存行）。在64位x86架构中，缓存行是64字节，也就是8个Long类型的大小。这也意味着当缓存失效，要刷到主内存的时候，至少要刷64个字节。

主内存中有变量X、Y、Z，被CPU1和CPU2分别读入自己的缓存，放在了同一行Cache Line里面。当CPU1修改了X变量，它要失效整行Cache Line，也就是往总线上发消息，通知CPU2对应的Cache Line失效。由于Cache Line是数据交换的基本单位，无法只失效X，要失效就会失效整行的Cache Line，这会导致Y、Z变量的缓存也失效。

解决：分别在X、Y、Z后面加上7个无用的Long型，填充整个缓存行，让X、Y、Z处在三个不同的缓存行中。

synchronized和ReentrantX都是可重入锁，一般锁都要设计成可重入的，否则就会发生死锁。

Lock、ReentrantLock、Sync、NonfairSync、FairSync

常用的方法是lock()/unlock()。lock()不能被中断，lockInterruptibly()可以被中断。

默认非公平锁，为了提高效率，减少线程切换。

Sync的父类AbstractQueuedSynchronizer被称为队列同步器（AQS），这个类非常重要。

实现一把具有阻塞或唤醒功能的锁，需要几个核心要素：1.  需要一个state变量，标记该锁的状态。state变量至少有两个值：0、1。对state变量的操作，要确保线程安全，也就是会用到CAS；2. 需要记录当前是哪个线程持有锁；3. 需要底层支持对一个线程进行阻塞或唤醒操作；4. 需要有一个队列维护所有阻塞的线程。这个队列也必须是线程安全的无锁队列，也需要用到CAS。

①和②：在AQS类中有对应的实现，state取值不仅可以是0、1还可以大于1，为了支持锁的可重入性。Thread exclusiveOwnerThread 记录锁被哪个线程持有。

③：在Unsafe类中，提供了阻塞或唤醒线程的一对操作原语，park/unpark

④：在AQS中利用双向链表和CAS实现了一个阻塞队列。阻塞队列是整个AQS核心中的核心。

非公平锁，一上来就抢锁

公平锁会判断队列有无阻塞的线程

进入acquireQueued()，该线程被阻塞。在该函数返回的一刻，就是拿到锁的那一刻，也就是被唤醒的那一刻，此时会删除队列的第一个元素（head指针前移一个节点）。

release()里面做了两件事情：tryRelease()函数释放锁；unparkSuccessor()函数唤醒队列中的后继者。

因为是排他锁，只有已经持有锁的线程才有资格调用release()，这意味着没有其他线程争抢。所以，对state的修改，不需要CAS操作，直接减1即可。

调用非公平锁的tryAcquire()，对state进行CAS操作，如果操作成功就拿到锁；如果操纵不成功则直接返回false，也不阻塞。

当使用ReadWriteLock的时候，并不是直接使用，而是获得其内部的读锁和写锁，然后分别调用lock/unlock

表面看ReadLock和WriteLock是两把锁。实际上可以理解为一把锁，读线程和读线程不互斥，读线程和写线程互斥，写线程和写线程互斥。

state变量拆成两半，低16位，用来记录写锁。高16位，用来”读“锁。

为什么把一个int类型变量拆成两半，而不是用两个int型变量分别表示读锁和写锁的状态吗？这是因为无法用一次CAS同时操作两个int变量。

当state=0时，说明既没有线程持有读锁，也没有线程持有写锁，当state！=0时，要么线程持有写锁，要么有线程持有写锁，两者不能同时成立。因为读和写互斥。

对于非公平，写线程能抢到锁，前提是state=0，只有在没有其他线程持有读锁或写锁的情况下，他才有机会去强锁。或者state！=0，但持有写锁的线程是它自己，再次重入。写线程是非公平的。

假设当前线程被读线程持有，然后其他读线程还非公平地一直去抢，可能导致写线程永远拿不到锁，所以对于读线程的非公平，要做一些”约束“。当发现队列的第一个元素是写线程的时候，读线程也要阻塞一下。

1. tryAcquire() 实现分析

2. tryRelease() 实现分析

tryAcquireShared()

Condition其功能和wait/notify()类似

ArrayBlockingQueue，核心是：一把锁 + 两个条件，如果队列满了，notFull条件阻塞；反之 notEmpty阻塞。

每一个Condition对象上面，都阻塞了多个线程。因此，在ConditionObject内部也有一个双向链表组成的队列。

线程调用await()的时候，肯定已经拿到了锁。所以，在addConditionWaiter()内部，对这个双向链表的操作不需要执行CAS操作，线程天生天生就是安全的。

在线程执行wait操作之前，必须先释放锁。也就是fullRelease(node)，否则会发生死锁。这个和wait/notify与synchronized的配合机制一样。

与await()不同，awaitUninterruptibly()不会响应中断，其函数的定义中不会有中断异常抛出。

同await()一样，在调用notify()的时候，必须先拿到锁。

读读、读写不互斥、写写互斥

和MySQL高并发的核心机制MVCC，也就是一份数据多个版本，StapmedLock有异曲同工之妙。

一个主线程要等到10个Worker线程工作完毕才退出，就能使用CountDownLatch来实现。

await()调用的是AQS的模板方法。只要state！=0，调用await()方法的线程便会被放入AQS的阻塞队列，进入阻塞状态。

因为是基于AQS阻塞队列来实现的，所以可以让多个线程都阻塞在state=0条件上，通过countDown() 一直累减state，减到0后一次性唤醒所有线程。

10个工程师一起来公司应聘，招聘方式分为笔试和面试。首先，要等人到齐后，开始笔试：笔试结束之后，再一起参加面试。

基于ReentrantLock和Condition实现

CyclicBarrier是可以被重用的。

CyclicBarrier会响应中断。如果有线程收到了中断信号，所有阻塞的线程也会被唤醒，就是上面的breakBarrier()函数。然后count被重置为初始值，重新开始。

回调函数，barrierActioin只会被第10个线程执行1次（在唤醒其他9个线程之前），而不是10个线程每个都执行1次。

Exchanger用于线程之间交换数据。使用代码很简单，是一个exchange(..)函数

Exchanger的核心机制和Lock一样，也是CAS+park/unpark。