type
status
date
slug
summary
tags
category
icon
password
原文
StampedLock
- 读读不互斥，读写不互斥 写写互斥。
- 有乐观读策略(基于版本)，读的时候不加读锁，可以升级为悲观读。
- 提供写锁、悲观读锁、乐观读锁三种锁模式。
- 不可重入性，同一线程不可重入加锁。
- 与MySQL 的 MVCC机制有些相似。
节点
- 读写线程没拿到锁会将到队列中。
- 节点分为读、写节点。
- 写线程中直接加入到主队列中。
- 悲观读线程竞争锁创建节点，如果前驱节点为写节点，直接加入到主队列中。如果为读节点加入到前驱节点的 cowait 的单向链表中。
- 读节点中的 cowait 允许多个读节点共享同一个节点。
cowait
cowait 是把多个读节点聚合在同一个前驱节点下的共享等待链表，实现读线程批量唤醒。
读节点不入主队列，可以减少主队列的长度。
如果读节点也加入主队列，在读多写少的场景下，会造成写线程饥饿。
状态
state
高位 表示版本号，高位57号
第8位 是否有线程占有写锁
0 表示没有线程持有写锁，1 表示锁表示已有线程持有写锁。
低7位 当前几个线程在读
低7位的最大数位 127，超过127溢出了，则使用
readerOverflow来计算读线程。当前是否有线程持有写锁
state 初始值为 256 二进制值为 000…00000001 00000000
ABITS 初始值为 255 二进制值为 000…00000000 11111111 低8读为 1 000…00000001 00000000
&
000…00000000 11111111
= 000…00000000 00000000
state & ABITS == 0L 条件成立表示当前没有写锁竞争
写锁
- CAS + 自适应自旋
- 当前线程没有竞争到锁，则进入等待队列，然后线程进入 WAITING 状态。
writeLock 申请写锁的方法入口，分为快慢路径。如果没有锁直接 CAS 操作一次成功后返回 state。如果当前已有线程占有写锁，则进入acquireWrite方法自适应自旋竞争锁。
(s = state) & ABITS) == 0L 当前没有读/写锁
U.compareAndSwapLong(this, STATE, s, next = s + WBIT)
设置 state ，这里会将写标志为1
1️⃣ 2️⃣ 这 2 个条件为 true，说明当前没有读写锁，直接返回当前的 state。这里可以理解为快速路径。
3️⃣ 当前线程没有拿到锁，则进入 acquireWrite方法等待处理。
acquireWrite 方法有两个自旋
for (int spins = -1;;)自旋一定次数竞争锁、一定次数还没能竞争到锁后则进入等待队列。
for(intspins = -1;;)自旋一定次数，未能竞争到锁，进入休眠。
第一个自旋
开启自旋条件
spins = (m == WBIT && wtail == whead) ? SPINS : 0;
m==WBIT 检查是否有写锁，wtail == whead 队列头尾节点相等表示队列中没有等待线程。写锁已经被占有，没有线程等待竞争锁。
spins 是一定概率进行递减，这样的好处是将所有竞争写锁的线程以不同的时机加入队列，且可以减少线程上下文切换的开销。spins 次数
- 循环的次数是根据当前系统是否具有多个处理器核心。默认 64 次
- 多核环境下允许线程自旋等待，避免立即进入阻塞状态。
- 单核环境下直接放弃自旋，因为单核上无法真正并行执行。
加入队列
执行到这里，说明自旋次数已经耗尽或者不再自旋，判断当前的队列有无初始化，如果队列还没有创建则创建节点，CAS更新刚创建的节点首节点，并向尾节点也指向改节点。如右图。
自旋竞争锁
经过上面的自旋，已经创建了一个当前节点，如果当前节点的前驱节点是头节点，说明当前节点是下一个可能获得锁的线程。
开启自适应自旋去竞争写锁，如果获取到锁整个方法结束。如果spins次数耗尽，未能竞争到锁，则走其他逻辑。
如果拿到锁以后将头节点设置为在第一个自旋创建的 node 节点即当前线程创建的节点。
协同释放读线程
允许多个线程协助完成读线程队列管理工作，避免单个线程承担队列的管理工作，减少读线程的等待时间。
竞争写锁的线程在自旋一定次数后，取出头节点中的 读线程节点，然后修改 h.cowait指向下一个等待节点，如右下图。
h为头节点即将获取锁，提前唤醒这些读线程可以让读线程更快获取锁，避免读线程一直阻塞。
休眠
if(whead == h) 检测头节点在当前线程自旋操作期间没有被其他线程修改，如果此头节点被别的线程修改了，说明链表产生了变化，别的线程已经拿到了写锁，那么当前线程继续自旋，自旋的次数翻倍。
头节点的变化，说明当前线程的节点接近了一点头节点，继续竞争锁的概率会大点。
p 为前驱节点（见图3），自旋期间如果当前节点的前驱节点不是 p，说明在自旋期间链表节点有变化，这里重新将前驱节点的 next指向 当前节点，这里来保证链表的完整性。
链表节点新建的状态为 0（status=0），当前节点需要确保前驱节点知道当前线程在等待锁，在释放锁时才能正确唤醒后续节点。
链表有虚拟头节点，所以只有一个线程竞争写锁，也是可以修改前驱节点的状态。
写锁代码完整注释
写锁释放
修改state
加锁的线程调用加锁成功时返回一个 stamp值，调用写锁释放时传入该值
state != stamp
加锁的时候修改了 state 和传入的 stamp 做版本匹配。这个条件是为了判断加锁和解锁的线程是否为同一线程。
stamp & WBIT==0L
如果此时已经没有写锁，则抛出异常。版本号已经匹配上了，说明当前解锁的线程已经不再持有锁了。
修改 state 值
stamp += WBIT 清除写标志，增加版本号
加锁：
state = 256 + 128 = 384
00000000 10000000 128 WBIT
00000001 00000000 256 初始化值
00000001 10000000 384
写锁标志
释放锁：
state = 384 + 128 = 512
00000000 10000000 128 WBIT
00000001 10000000 384 sate
00000010 00000000 512
版本号+1
(stamp += WBIT) == 0L 如果溢出了则state使用初始化值。
如果头节点不为空， 说明有在竞争写锁的线程在等待锁。
唤醒后续节点
前序遍历可能产生的问题
悲观读锁
- 悲观读为共享锁，可多个线程持有。
- 与写锁互斥
- 悲观读锁的获取流程 尝试获取→竞争失败入列→阻塞等待→唤醒重试。
悲观读锁并不会修改锁标志位，只是增加读计数位，释放锁时读计数减一。
whead == wtail 检查等待队列是否为空(s & ABITS) < RFULL 检查悲观读锁数量是否溢出且没有写锁U.compareAndSwapLong(this, STATE, s, next = s + RUNIT) 读锁+1 这里是 CAS更改 state+1，读锁的标志在低位直接+1 即可。3 个条件为true，当前悲观读的线程可以直接获取读锁，无需进入等待队列等待。
第一个自旋
(m = (s = state) & ABITS) < RFULL
读锁没达到上限且没有写锁
U.compareAndSwapLong(this, STATE, s, ns = s + RUNIT)
悲观读锁+1，悲观读锁在低位直接+1即可，state 修改成功直接返回 stamp。
(m < WBIT && (ns = tryIncReaderOverflow(s)) != 0L)
没有写锁 tryIncReaderOverflow(s) 处理悲观读计数溢出
有写锁的情况下进行自旋
自旋次数耗尽的情况下判断目前等待队列的情况
nh == h && np == p
条件成立 说明在自旋期间链表未产生变化，说明有写线程还在占有锁，还没有线程加入。
(h = nh) != (p = np))
队列非空，有其他线程更改了队列，说明当前线程应该入列。
满足两个条件之一退出内层循环，直接创建节点加入到队列中。
加入队列
自旋结束，则创建节点加入到队列中。
如果队列还没有初始化，则创建一个头节点(WMODE=1写模式)为头节点。
a.在StampedLock 类中常使用header == tail 这个条件。满足这个条件的有 3种情况
- 队列为 null
- 队列刚初始化完成
队列初始化时，会创建一个节点，然后头尾两个节点都指向该节点。
- 队列之中只有一个节点
该条件下说明当前节点最近头节点，如果当前节点插入到队列中可以很快得到锁。
b.p.mode != RMODE p 为前驱节点，如果前节点为写节点，则条件成立。
如果 a 条件 或 b 条件一个为 true，则将当前节点插入到队列中。
再次竞争锁
如果当前节点已经接近header 节点，再尝试竞争锁。
pp 是 p.prev ，p是当前节点的前驱节点。 pp == null 说明当前节点接近头部节点，快轮到当前节点。
h==p 说明链表很短，p.status大于0 说明前驱节点已经被取消了。
这 3 个条件满足其中之一，就将当前节点设置 为 null，也就是删除当前节点，然后继续自旋去竞争锁，因为当前节点离头节点近，拿到锁的概率变大。
第二个自旋
第二个自旋的逻辑同 acquireWrite方法（也就是获取写锁的方法）中的第二个自旋逻辑相同。
悲观读锁释放
悲观读锁只需要将 state 减一
当前的读计数溢出，
readerOverflow 减一。乐观读
- 无锁读取机制，通过版本号判断读取期间是否被修改。
- 读、写不互斥，不阻塞写线程。
- 失败时可降级，发现版本修改可升级悲观读锁。
- 在没有写入并发时，可以保证读到的数据是一致快照，但是在读取过程中有并发写操作，可能发生脏读。
获取版本号
当前有写锁，直接返回 0。无写锁直接返回版本号
验证版本号
U.loadFence() 保证先读取锁状态，再去读共享数据。读指令都是独立的，没有依赖关系，可能会重排序。
为什么要防止重排序
假设指令重排执行的顺序变成如下。
int value = sharedData; (1)
long stamp = lock.tryOptimisticRead(); (2)
(1) 没检查锁状态就去读数据
写线程刚刚获取到锁，修改了数据还没释放锁。
那么读线程也就是当前线程读到的共享数据是旧数据或者正在修改中的数据，会出现“脏读“现象。
- Author:newrain-zh
- URL:https://alex.sh.cn/article/StampedLock
- Copyright:All articles in this blog, except for special statements, adopt BY-NC-SA agreement. Please indicate the source!
