多线程与高并发思维导图模板_ProcessOn思维导图、流程图

容器

Collection

List

ArrayList

LinkedList

CopyOnWriteArrayList

线程安全，适用于读多写少的情况

Set

HashSet

TreeSet

Queue

BlockingQueue

ArrayBlockingQueue

有界，数组实现

入队出队单锁

LinkedBlockingQueue

可以有界，链表实现

入队出队两个锁

SynchronizedQueue

不存储元素，来一个必须取走才能再来

LinkedTransferQueue

相当于多窗口的SynchronizedQueue

DelayQueue

内部使用PriorityQueue实现

PriorityQueue

Map

HashMap

1.7与1.8

1.7

数组+链表

拉链法解决hash冲突

链表采用头插法，多线程扩容的情况可能会产生死循环

1.8

数组+链表+红黑树

链表采用尾插法

树化

当链表长度大于8，数组长度大于等于64时树化，否则只触发扩容操作

退化

resize时当链表长度小于6，退化为链表

remove时判断树比较小时退化为链表

8和6通过泊松分布得出

当size<=8时，链表整体的插入查询效率高于红黑树

优势：链表过长导致查询效率降低，可通过红黑树优化查询速度

红黑树优势

比普通的二叉树

树高更加均匀，不会出现单链情况

比AVL树

不需要完全平衡，不会牺牲太多的插入性能，插入和查找性能更加平均

线程不安全

多线程环境下可能会产生元素覆盖问题，1.8以前还可能在扩容时死循环

装载因子0.75

空间与时间的权衡

扰动函数

将hash的高16位右移进行异或运算，使得高16位和低16位都参与到定位运算中，减少hash冲突

容量为2^n原因

2^n可以使用位与运算代替取模，提高效率

加快扩容之后的元素移动

延迟初始化数组

当put第一个元素的时候才初始化

扩容

hash直接&oldCap，得出位置不变还是在原位置+oldCap

所以挨个运算后，直接生成两个链表，平移链表和扩容链表

TreeMap

ConcurrentHashMap

1.7

size

先不加锁计算三次，任意连续两次结果相同就返回，否则所有segment加锁计算<br>（个人感觉没有必要这么搞，即使算准确了，返回的那一刻可能已经发生改变了）

segment

锁定segment，segment即并发度

默认大小为16，一旦构建完成，后续不可更改

基本依赖lock和CAS保证线程安全

在lock前会尝试自旋一定次数调用trylock，并在自旋时做一些遍历操作

扩容

小细节

在生成两个链表的时候保留链表尾部将在同一链表部分，直接复用

扩容的对象是segment中的小map

即多个segment之间扩容互不干扰

其他同HashMap

1.8

size

已支持更多元素到long，推荐使用mappingCount替代size方法

计数系统详见LongAdder

基本依赖sychronized和CAS保证线程安全

synchronized的对象是链表头结点或者Treebin

扩容

扩容的时候还没有移动或者没有被锁定的Node可以正常使用

迁移单个Node的时候，对该Node加锁

迁移链表类似1.7

迁移树节点，对与其并存的双向链表进行操作，分组后判断是否小于等于6，是则退回链表，否则构建红黑树

协助扩容

如果hash得到的位置被标记为FWD或者多个线程同时进入扩容操作，则尝试协助扩容

扩容的时候会按照容量和CPU核数计算单个线程的步长，最小为16

每个线程通过CAS对sizeCtl进行加1，成功则进入协助扩容，退出时CAS对sizeCtl减1，如果sizeCtl变为原始值，说明所有Node都迁移完毕

ConcurrentSkipListMap

使用跳表实现

三要素

原子性

可见性

有序性

as if serial

单线程

happens before

多线程

8原则

单线程as if serial

volatile

monitor lock

thread start

thread terminate

thread interrupt

object finalizer

传递性

JMM<br>

为了屏蔽各操作系统及硬件的区别，Java定义了JMM

8个原子操作

lock

unlock

read

load

use

assign

store

write

volatile

如何保证可见性和有序性

JVM层面

规定use之前必须load

即读之前必须先从主内存同步数据

规定assign之后必须store

即写之后必须马上同步回主内存

规定volatile的8个操作不能指令重排序

内存屏障实现

写

storestore屏障

volatile写

storeload屏障

读

storeload屏障

volatile读

loadstore屏障

CPU层面

指令lock addl

缓存一致性协议

总线锁

mesi协议

M(Modified)

E(Exclusive)

S(Shared)

I(Invalid)

DCL单例

对象初始化过程

new 分配一块内存

执行初始化

将内存赋值到引用

需要加volatile修饰，因为对象初始化过程中可能发生指令重排序，即初始化和赋值引用重排序，导致其他线程读到未初始化完成的对象

对象结构

从上到下依次为

MarkWord（32位4字节，64位8字节）

klass pointer（压缩指针4字节）

数据区

padding

需要补齐8字节对齐

压缩指针

32G内存失效

原因：压缩指针4字节32位，即4G，由于8字节对齐，所以压缩指针最大只能表示32G

并发工具类

CountDownLatch

countDown方法不阻塞，await方法阻塞

内部类继承自AQS框架，实现share相关方法

不可重复使用，一般用于某些线程等一堆线程操作

CyclicBarrier

循环栅栏，可循环使用，一般用于多个线程互相等待

也可实现CountDownLatch功能，在初始化的时候多加一个Runnable参数

使用lock和condition实现

Semaphore

信号量Java实现

内部类继承自AQS框架，实现share相关方法

与锁类似，只不过不记录获取的线程

Exchanger

需两个线程访问，如果只有一个线程，会阻塞等待另一个线程到来

内部实现：CAS+park

atomic包

简单类

AtomicInteger

AtomicLong

AtomicBoolean

内部转换为Integer，true为1

内部使用Unsafe类的CAS操作，底层指令lock cmpxchg

数组类

AtomicIntegerArray

AtomicLongArray

AtomicReferenceArray

引用类

AtomicReference

AtomicStampedReference

可用来解决CAS的ABA问题

内部使用Pair将Reference和stamp包装起来

字段类

AtomicIntegerFieldUpdater

AtomicLongFieldUpdater

AtomicReferenceFieldUpdater

adder

LongAdder

将并发操作拆分到多个cell，提高并发度

缓存行

单个cell为一个long的包装，使用了@sun.misc.Contended注解，保证该long变量占用单独的一个缓存行

由于高速缓存的操作单元为一个缓存行，而缓存行上其他元素的invalid会导致当前元素一同invalid，从而降低并发度，单独一个缓存行可避免此问题

细节

有一个普通变量base可计数，CAS失败后使用cell数组

通过线程生成随机数，定位cell数组位置

定位到的cell数组位置不为null，则可以尝试CAS增加当前cell

初始化cell数组、填充新的cell元素、扩容cell数组三个操作互斥，会使用CAS乐观锁竞争cellbusy

竞争失败或者CAS失败可以尝试其他方式，比如说重新生成随机数再次定位，或者CAS操作base变量

多次失败则触发cell数组扩容操作，进一步提高并发度

DoubleAdder

超高并发使用，分为多个cell分别进行累加，get的时候将cell的值加一起

锁

synchronized

1.6优化

无锁

MarkWord: 对象hashcode和分代年龄

偏向锁

MarkWord: 偏向线程ID，偏向时间，分代年龄

如果锁标记为可偏向状态，则尝试使用CAS替换对象头的markWord为当前线程id

当有另一个线程尝试获取这个锁时，则升级为轻量级锁<br>

轻量级锁

MarkWord: 指向轻量锁记录的指针

超过N个线程竞争或者自旋超过一定次数，则膨胀为重量级锁

线程数量N和自旋次数由自适应自旋决定，即通过复杂的算法得出

重量级锁

MarkWord: 指向重量级锁的指针

涉及用户态到核心态的切换

流程

获取锁失败则添加到阻塞队列

锁释放后通知阻塞队列中的一个线程抢占锁

锁消除

编译器检测到不会涉及到多线程竞争，则会把锁消除

锁粗化

编译器检测到相邻代码多个小锁，则会粗化为一个大锁

可重入

不可中断

只有一个等待队列

wait、notify

必须在synchronized中使用

wait会释放锁，notify不释放锁

流程

调用wait后将线程放入等待队列，并释放当前锁

调用notify后，会把线程从等待队列移动到阻塞队列，可重新竞争锁

lock

ReentrantLock

可重入锁

在已经被锁定状态，判断是否是当前线程持有，如果是则将state加1

可以实现公平锁

非公平锁性能更好，但可能造成饥饿

可以实现可中断锁

可以有多个等待队列

ReentrantReadWriteLock

读写锁

读读之间共享锁，可以提高读的效率

通过state的前16位和后16位区分写锁还是读锁

写锁可降级为读锁，读锁不能升级为写锁

StampedLock

有同样读写锁的实现

添加优化读

如果读的时候没有写，则可以不加读锁，提高效率

在读之前使用validate验证是否有写入，如果有则需要继续获取读锁

Condition

await类似wait

signal类似notify

CAS

需要配合自旋，如果竞争激烈，比较耗费cpu

linux对应指令: lock cmpchx

AQS源码

volatile int state

充当了信号量，用CAS操作成功表示获取成功

CLH队列

当获取锁失败，需要将线程加入阻塞队列

双端队列

加入队列时，先判断head是否为null，如果为null，则先用CAS添加哨兵节点，如果不为null，则用CAS将当前节点置尾结点

出队时，将head指向当前节点，并清空线程等数据，作为新的哨兵节点

condition队列

调用await方法加入等待队列，并释放锁

调用signal方法将该节点移到阻塞队列中

线程池

ThreadPoolExecutor

参数

corePoolSize

maxPoolSize

keepAliveTime

timeUnit

blockingQueue

threadFactory

rejectedHandler

提交任务

execute

无返回值

submit

有返回值

ForkJoinPool

可窃取工作模式

在当前线程完成给定队列中的任务后，尝试从别的队列尾窃取任务

ThreadLocal

hash冲突

使用线性探测法处理

在线程里有ThreadLocalMap存储相应的值

key为ThreadLocal本身，为弱引用WeakReference

当强引用断开后，该threadLocal变量即可被回收

这样会造成Map中key为null，而value有值，属于内存泄漏

threadLocal在set和get的时候会顺带着检测是否有null的key，如果碰到了就清除掉

即使有清除策略，也只能清除一部分，所以需要在使用完后手动remove掉

value为强引用

初始化长度为16，当容量达到1/2时触发扩容，会将原所有元素重新填入