ReentrantReadWriteLock原理

t1 w.lock t2 r.lock

image-20220320145600222

image-20220320145619378

image-20220320145624167

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
+ 读写锁原理
    + 使用的同一个sycn同步器
    + t1 w.lock 写锁
        + 与可重入锁基本相同
        + state低16位写锁，高16位读锁
        + tryacquire
            + 这段看书没懂，现在终于懂了
            + 判断有无：读锁、写锁（非本线程）
    + t2 r.lock
        + 读源码最好的办法是写个小栗子然后通过idea调试阅读，直接读太慢，还容易理解错了
        + 判断有无写锁、当前线程的写锁
        + 阻塞，和独占锁差不多
            + 只是节点类型不同：node类型为shared
            + 判断是否为老二
                + 重试尝试获取
            + 前驱设为-1（哨兵）
            + 再次进入循环，尝试获取
                + 一共三次尝试
            + park阻塞
    + t3 r.lock  t4 w.lock
        + 进入阻塞队列
            + 读锁类型为shared
            + 写锁为独占
            + node state
                + 前面为-1
                + 最后为0
    + t1 w.unlock
        + tryrelease
            + state--
            + 检查是否有读锁
            + 唤醒节点
            + 老二唤醒
                + 非公平锁体现在持有锁的线程释放锁后，外来线程直接去尝试获取锁，而不会去判断队列是否有线程，这时队列中的线程和外来线程争抢锁，就是非公平的
                + 公平锁体现在外来线程要获取锁时，会先判断队列有没有线程阻塞，有就自己去队列排队，不会去尝试获取锁
            + 老二继续循环，tryacquire获取读锁
                + state高位变成1
                + 讲到也不细，必须自己调试源码
                + 关键是思考，多读源码
                + setHead(node)之后的代码的意思是，当阻塞队列中有多个连续的读线程时，会传播式地逐一唤醒，if(s.isShared()){doReleaseShared()}这段代码是关键
            + 拿到下个node，若为shared
                + 把哨兵节点状态改为0
                    + 避免其他线程干扰
                + 继续唤醒shared node
                    + 继续循环，获取锁tryacquire
                    + 读锁计数（高位）+1
                    + 循环唤醒节点方法
                        + 判断下一个node是否为shared
                        ...
    + t2 r.unlock t3 r.unlock
        + tryreleaseshare
            + 状态-1
                + 若不为0，其他读锁继续-1
            + 读state为0
                + 解锁流程
                    + 哨兵节点状态-1改为0
                    + 后继节点唤醒unpark
                        + 循环继续，当前是老二，获取锁tryacquire
                        + 当前node作为哨兵
                        + 写state状态修改

StampedLock

image-20220320145720741

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
+ StamedLock
    + 作用
        + 增加读的性能
        + 配合戳使用
            + 加锁返回戳
            + 用戳解锁
            + 乐观读
                + 验戳，锁升级
    + 演示
        + 乐观读，戳不变，未被修改读取成功
        + 戳改变，锁升级
            + 真正加读锁，与写锁互斥
        + 读读
            + 乐观读等于无锁读取
        + 读写
            + 乐观读锁验证戳失败
            + 加读锁，进入阻塞
            + 写锁释放后，读锁加成功
                + 读取最新值
        + 缺点：
            + 无条件变量
            + 不支持可重入

Semaphore

image-20220320145742093

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
+ Semaphore
    + 作用
        + 信号量
            + 限制同时访问共享资源的线程上限
    + 演示
        + acquire获取信号量
    + 应用
        + 简单限流（单机）
        + 限制线程数，而非资源数
            + 适合一个线程一个连接：数据库连接池
        + 改进数据库连接池
            + 获取连接
                + 获取信号量
                    + 获取成功才能获取连接
                    + 没有信号量，阻塞
            + 归还连接
                + 归还后，release信号量
    + 原理
        + 构造方法
            + 信号量给同步器sync，赋值信号量给state
        + acquire
            + tryacquireshare
                + 获取state
                + 判断state--是否小于0
                    + 无信号量，AQS阻塞队列
                    + 老二try获取，cas
                    + 前驱改为-1
                    + 最后park线程
                + cas修改state--
        + release
            + tryreleaseshare
                + 获取state
                + cas state++
            + doreleaseshare
                + 哨兵节点是否-1
                    + 改为0
                + 唤醒后序节点
                    + 老二 tryacquire，成功
                        + cas state
                    + 自己设为哨兵
                    + 唤醒后序共享节点
                        + 由于信号量不够，又被阻塞
                    + 这里有个双unpark机制，就是运行结束后的线程会释放锁去唤醒，另外一个刚获得释放的锁的线程也会去唤醒，不过被唤醒后的线程不能获得锁还是会park住

CountDownLatch

image-20220320145822476

image-20220320145829350

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
+ CountDownLatch
    + 简介
        + 倒计时锁，线程间同步协作
            + await()等待计数归零，countdown()计数-1
        + aqs同步器
            + acquire：state为0获得锁
            + release：计数-1
        + 主线程等待，其他线程计数减完，主线程继续运行
    + 改进
        + 线程池等不能用join等待线程结束
            + 可以用countdownlatch
    + 应用
        + 等待多线程准备完毕
            + 加载完毕计数-1
            + 计数结束，主线程运行
        + 等待多个远程调用结束
            + CompletableFuture异步编排
            + 倒计时锁
            + 我选择AsyncTool
            + 使用future获取返回值
+ Cyclicbarrier
    + 问题
        + countdownlatch不能被重用
        + Cyclicbarrier
    + 使用
        + await
            + state-1 阻塞
            + 当state为0，全部唤醒继续
        + 当全部执行完，运行参数中的任务
        + 计数为0后，再次调用await又重新开始
    + 注意
        + 线程数要跟计数一样

JUC-Collection

image-20220320145839640

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
+ 线程安全集合类
    + 概述
        + 遗留的
            + hahtable、vector：都用synchronize修饰
        + 修饰的安全集合
            + collections中类的包装
            + 装饰器模式
        + juc安全集合
            + blocking类
                + 大部分基于锁（可重用锁），阻塞方法
            + copyonwrite类
                + 修改时拷贝的方式
                + cow写时复制
            + concurrent类
                + 内部很多采用cas优化，提高吞吐
                + 弱一致性
                    + 遍历时，其他线程修改，迭代器继续运行（旧内容）
                    + 求大小、读取
                    + 这里的弱一致性，其实是安全失败机制（fail-safe）实现原理：获得原集合的一份拷贝，在拷贝而来的集合上进行遍历，原集合发生的改变时，不会抛出CME异常

ConcurrentHashMap

image-20220320145853898

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
+ ConcurrentHashMap
    + 面试的神!CHM
    + 错误用法
        + 统计单词个数
            + 线程不安全
        + hm改为chm
            + 仍然不行
                + 每个方法原子
                + 组合起来非原子
            + 解决：
                + 直接加synchronize重量级锁
                + CAS
    + computeIfAbsent
        + 跟我在极客时间学的一样，哈哈哈哈
        + 这个demo感觉信息量好大，学到很多编程思路和手段
        + 第一次若key不存在，则生成key和累加器（原子性）
        + 后面直接返回累加器，进行累加（原子性）

ConcurrentHashMap原理

image-20220320150154452

image-20220320150213295

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
+ ConcurrentHashMap原理
    + hashmap
        + 回顾
            + 数组+链表+红黑树
            + hash地址冲突，链地址法
                + jdk7放到链表头部
                + jdk8放到链表尾部
            + 超过3/4，扩容，重新计算桶下标
                + 低位的下标不变，高位的加个oldSize就是新下标
                + 为什么数组扩容后，链表长度会减半？因为我们确定桶位置是数组长度与hash进行&操作，长度扩为2倍，桶位置正好会改为2倍
            + 多线程下扩容，并发死链问题
        + 死链
            + 两个线程同时触发扩容
            + 出现环形链表
                + 第一次扩容结束后，线程再进行扩容的时候链表上出现了环。导致程序不能再往下继续运行
            + jdk8，尾插法
                + 仍有其他问题（扩容丢数据）
+ concurrenthashmap-jdk8
    + 原理
        + 属性&内部类&方法
            + 迁移
                + 从后往前处理
                + 处理完加fnode节点
            + 红黑树
                + 扩容到64
                + 链表转换成红黑树
        + 构造
            + 初始容量、负载因子（3/4）、并发度
                + 最少初始容量等于并发度
            + 懒惰初始化
            + 计算容量大小（变成为2的n次方）
        + get
            + 这个地方说的不清楚，看完也不知道为什么不加锁，实际上是用了volatile关键字
            + 不加锁就是volatile带来的好处，即使写操作更新了也可见不会脏读
            + 遍历链表，用equals比较key，返回val
        + put
            + 默认覆盖旧值
            + 不允许null
            + 若table为空
                + cas创建table
            + 若链表无头结点（桶下标不冲突）
                + cas添加链表头
                + 头结点被占，再循环一遍，这个结点会加在刚刚那个头结点的后面
            + 帮忙扩容
                + 锁住当前链表帮忙扩容
            + 桶下标冲突
                + 加锁synchronize，锁住链表头结点
                + 再次校验链表头节点是否被移动
                + 节点hash>0
                    + key找到相同的，更新操作
                        + 更新value
                    + key不存在，添加操作
                        + 已经是最后的节点了
                        + 新增node链表尾插
                + 节点hash<0，判断是否为红黑树
                    + 往红黑树中添加node
                + 释放锁，判断链表长度是否大于树化阈值
            + 计数器计数
        + initTable
            + 懒惰初始化
            + table若没被创建，进入循环
                + 双重校验是否被创建
                    + 第一次并发
                + cas将sizeCtl设为-1（正在创建hash表）
                + 成功cas，准备创建hash表
                    + 根据初始容量sc，创建node数组
                    + sc赋值给sizeCtl，恢复到正数
                + 并发线程都在循环中退出
        + addcount
            + 增加元素计数
            + 多个累加单元，保证多线程效率
            + 没有累加单元，cas向basecount累加
            + 有了累加单元，cas累加++
                + @Contended注解防止数据伪共享
                + 之前讲LongAdder原理的时候讲过，说的是@Contened注解，这个注解是在对象或变量前后加padding，就是占位，为了避免多CPU缓存行伪共享问题
                + 元素个数若大于sizeCtl，进入循环，扩容操作
                    + 校验sc是否为负数
                        + 若newtable已创建
                            + 帮忙扩容
                    + cas将sizeCtl设为负数
                    + cas成功，进入transfer，传入table
        + size
            + 没有竞争发生，basecount累加
            + 有竞争发生，用累加单元计数
                + sum 累加单元的值和basecount
            + 很明显在sumCount计算的过程中无法防止别的线程进行一些累加和删除操作
        + transfer
            + 若nexttable为null，创建nexttable
                + 原有容量<<1
            + 节点搬迁
                + 以链表为单位移动
                + 若链表处理完，替换为forwardingnode
                + 若已经为fwd，处理下一个链表
                + 若链表头有元素
                    + synchronize锁住当前链表
                    + 节点hash>0（普通节点）
                    + 节点hash<0且类型为treebin，树节点搬迁
+ concurrenthashmap-jdk7
    + 结构
        + 维护segment数组（每个继承可重用锁）
            + 多把锁
            + jdk8：锁加在链表头
        + 缺点：
            + 锁数组大小固定
            + 非懒惰初始化
        + 构造时就创建
        + 每个segment（分段锁）对应小的hashentry
            + 不同锁，锁的内容不一样
    + 定位segment
        + 多看两遍，JUC的东西还是连续性很强的
        + 根据hash求segment位置（位运算），获取segment
    + put
        + 计算key的hash，找到segment下标
        + 获取segment，进入segment的put方法
            + 可重入锁加锁
            + hashentry，求桶下标
                + 链表：更新/新增
                    + key找到相等，更新值
                    + 找不到key，新增
                        + 创建node节点
                        + 扩容等
                        + 做为链表头
    + rehash扩容
        + 在外层已经加锁
        + 旧容量移位，创建newtable
        + 遍历搬迁
            + 如果只有头节点，直接搬迁
            + 链表多个节点，遍历链表
                + 记录node改变后位置
                + 把不变的node重用
        + 新增时才rehash
            + 新的node在扩容完才加入new table
    + get
        + unsafe方法保证可见性
        + 定位segment、桶下标
        + 遍历key，找到直接返回value
    + size
        + 循环，遍历segment
            + sum累加count
                + 期间若被修改（不等于上次计数），则重新计数	
                + 最多循环计数三次，加锁处理统计操作
        + 先不加锁计算2次，认为个数正确返回
        + 如果不一样，重试，超过3次，锁住所有segment

LinkedBlockingQueue原理

image-20220320150052835

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
+ LinkedBlockingQueue
    + 入队出队
        + 阻塞队列
        + node（item、next）
        + 初始化链表
            + 指向哨兵节点
        + 节点入队
            + 尾插
        + 节点出队
            + 哨兵节点垃圾回收
            + 获取老二的值，老二变成哨兵节点
            + 占位哨兵在数构设计中的作用是，一开始头有所指，尾有所向。进出队时或者查找，少大约n次的if else
    + 加锁分析
        + 用了两把锁和哨兵
            + 两把锁允许两个线程执行
                + 生产者（队列尾）消费者（队列头）
                + 允许同时get和put
        + 线程安全
            + 节点大于2
                + 队尾队头两把锁（一个哨兵），保证入队出队无竞争
            + 节点等于2
                + 仍然两把锁（一个哨兵），锁两个对象
            + 节点为1
                + 就一个哨兵，队列为空，take会被阻塞
    + put
        + 非空判断
        + 创建node
        + 拿到put锁
            + 若队列满容量，等待
            + 若有空位，入队方法，计数++
            + 若队列容量仍不满，叫醒put线程（signal一个）
        + 解锁
        + 如果队列只有一个元素，通知消费take线程（signal一个）
        + 消费者也会唤醒，只是不是唤醒全部，只会唤醒一个，唤醒完一个后再由生产者自己唤醒生产者
        + 如果有多个元素，那么take线程肯定是在执行的，如果只有一个元素，表示是我这次put进去的，需要唤醒take线程来取
        + take，take锁
            + 为空，等待
            + 出队
            + 队列有容量，叫醒一个消费者
        + 解锁
        + 如果队列只有一个空位，叫醒put生产者线程（signal）
    + vs arrayblockingqueue
        + linked懒惰的，初始不创建
        + linked入队才生成node，array提前创建好的
        + linked两把锁，array一把锁

ConcurrentLinkedQueue

image-20220320150125092

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
+ ConcurrentLinkedQueue
    + 与linked像，两把锁，队列头尾，哨兵
    + 使用cas实现锁
        + cas保证线程安全
+ CopyOnWriteArrayList
    + copyonwrite：写入时拷贝思想
        + 增删改，在新数组上执行
            + 不影响其他线程并发读	
            + 读写分离、读写并发
    + add
        + 加锁（写写互斥）
            + 旧数组拷贝（长度+1）新数组
            + 添加新元素
            + 替换旧数组
    + 读使用旧数组（新数组还未替换完）
    + 读未加锁
    + get弱一致性
        + 线程同时读和remove，仍能读到
        + 迭代器弱一致性
            + 即使remove，迭代器仍拿到旧数组引用
            + 优点
                + 数据库的MVCC都是弱一致性表现
                + 并发度高