一文搞懂 ReentrantLock 的公平锁和非公平锁
什么是 ReentrantLock
reentrant
翻译为可重入的,因此从字面上翻译为可重入锁,我们知道可重入是指:同一个线程对于已经获得到的锁,可以多次继续申请到该锁的使用权。ReentrantLock 在调用 lock()
方法时,已经获取到锁的线程,能够再次调用lock()
方法获取锁而不被阻塞。
如果要实现该特性,则需要解决以下两个问题:
线程再次获取锁。锁需要去识别获取锁的线程是否为当前占据锁的线程,如果是,则再次成功获取。
锁的最终释放。线程重复 n 次获取了锁,随后在第 n 次释放该锁后,其他线程能够获取到该锁。锁的最终释放要求锁对于获取进行计数自增,计数表示当前锁被重复获取的次数,而锁被释放时,计数自减,当计数等于 0 时表示锁已经成功释放。
再谈 AQS
之前写过一篇关于AQS的文章,AQS 全称队列同步器 AbstractQueuedSynchronizer
,它是一个队列,用来构建锁或者其他同步组件的基础框架。
我们可以 AQS 和 ReentrantLock 的关系理解为:
锁是面向使用者的。它定义了使用者与锁交互的接口(比如可以允许两个线程并行访问),隐藏了实现细节。
同步器面向的是锁的实现者。它简化了锁的实现方式,屏蔽了同步状态管理、线程的排队、等待与唤醒等底层操作。
它既然是一个队列,那其中必然维护了一个链表内部类,并且是一个双向链表,我们可以看看它的结构:
其中 Node 中各属性如下:
属性很多,但我们大致只需要记住每个 Node 里面最主要的 3 个:
我们知道 AQS 的设计是基于模板方法模式的,其中定义了一系列的方法让实现者自己去实现,就好比定义一个支付的方法,但是其具体的实现包括微信支付,支付宝支付,银行卡支付等等。而 AQS 中主要的模板方法如下:
而对于其中方法涉及到的状态,AQS 内部提供了一个state
属性,因为这是一个会被并发访问的属性,为了防止出现可见性问题要用volatile
进行修饰,并且提供了如下 3 个方法来访问或修改同步状态:
getState()
:获取当前同步状态。setState(int newState)
:设置当前同步状态。compareAndSetState(int expect,int update)
:使用 CAS 设置当前状态,该方法能够保证状态设置的原子性。
另外,AQS 还拥有首节点(head)和尾节点(tail)两个引用,一个指向队列头节点,而另一个指向队列尾节点(头节点没有前驱,尾结点没有后继)。
注意:因为首节点 head 是不保存线程信息的节点,仅仅是因为数据结构设计上的需要,在数据结构上,这种做法往往叫做空头节点链表。对应的就有非空头结点链表。
因此,一个 AQS 我们大致可以抽象为:
ReentrantLock 和 AQS
ReentrantLock
是基于 AQS
实现的,在ReentrantLock
内部有一个内部类Sync
,其继承关系如下:
其中具体的方法在之前的文章有讲过,可以自行参考,这里主要是讲非公平锁和公平锁的加锁流程。
非公平锁
加锁流程
一、未加锁
在没加锁之前 AQS 的状态:
二、第一个线程 t1 加锁
1、ReentrantLock()。根据ReentrantLock
的默认构造方法可知,当new ReentrantLock()
,默认为非公平锁。
2、lock()。当第一个线程去获取锁,从Lock.lock()
方法开始。
3、NonfairSync.lock()。进入非公平锁的实现方法中,并且获取锁。
4、compareAndSetState()。在获取锁之前先通过CAS
的方式将AQS
中的状态state
,
state == 0
, 表示该锁不被任何线程持有。state == 1
,表示线程恰好持有该锁 1 次(未重入)。state > 1
,表示锁被线程重入 state 次。
当第一个线程获取锁时,state
的默认值为 0 ,通过 CAS 将state
的状态改为 1,并且通过setExclusiveOwnerThread()
把当前线程设为独占锁,然后返回成功的结果。
此时 AQS 的状态为:
三、第二个线程 t2 加锁
当第二个线程来加锁,此时存在两种情况,一是是t1
已经释放锁了 ,第二t1
线程已经还持有锁未释放。
5、若t1
已经释放锁,此时 AQS 就是处于未加锁的状态,此时t2
来加锁和线程t1
的步骤相同。
由此可得出结论,ReentrantLock 如果线程之间没有竞争,那么其效率非常高,甚至队列都没有初始化。这也是为什么t1
进来就通过 CAS 获取锁的原因。
当然,既然使用到锁了,那必然是为了高并发场景做准备的。
6、acquire()。若t1
未释放锁,此时t2
想来获取锁,那么 CAS 就会失败,从而进入acquire()
方法。
该方法主要的逻辑都在 if 判断条件中,这里面有 3 个重要的方法tryAcquire()
,addWaiter()
和acquireQueued()
,这三个方法中分别封装了加锁流程中的主要处理逻辑,理解了这三个方法到底做了哪些事情,整个加锁流程就清晰了。
7、tryAcquire()。当前线程尝试获取锁,若获取成功返回 true,否则 false。它是 AQS 中定义的模板方法,ReentrantLock 在公平和非公平模式下对此有不同实现,非公平模式的实现如下:
底层调用了nonfairTryAcquire()
,从方法名上我们就可以知道这是非公平模式下尝试获取锁的方法,具体方法实现如下:
这里为什么不直接返回 false,主要原因是存在一个时间差,假如在t2
刚进入nonfairTryAcquire()
方法,t1
就释放了,那它就可以立马拿取锁,效率高,因为少了那些没必要的判断。
8、acquireQueued()。当tryAcquire()
失败,即返回 false 之后才会执行。该方法主要是将获取锁失败的线程安全的加入同步队列。
该方法调用了addWaiter()
,且传入了一个空的节点Node.EXCLUSIVE = null
,其代码实现如下:
由于第一次加锁队列还没有初始化,因此第二次加锁的时候tail = null
,所以直接走enq()
方法,其中 for(;;)
和while(true)
效果一致。
按照步骤分析:
①if (t == null)
,说明队列未初始化,先初始化一个空的节点,CAS 方式设置为队列首元素,当head==null
时更新成功,并把尾指针指向首结点。
② 当第二次循环t != null
,即已经被初始化过,将 node 结点的 prev 连接到尾结点,CAS 比较结点 t 是否为尾结点,若是则将尾结点设置为 node,然后把原尾结点的 next 指针指向当前结点 node。
我们可以写一段代码去查看对象的赋值情况。
初始化之后
此时,AQS 的队列为:
在死循环中只有通过 CAS 将节点设置成为尾节点之后,当前线程才能从该方法返回,否则,当前线程不断地尝试设置。节点进入同步队列之后,在回头看acquireQueued()
方法:
在第一个 if 语句中,先会判断前驱结点是否是头结点,如果是则尝试获取锁,获取锁成功则会设置当前结点为头结点(更新头指针)。**为什么必须前驱结点为头结点才尝试去获取锁?**先不管我们先看第二个 if 判断。
第二个 if 语句中,
shouldParkAfterFailedAcquire()
,字面意思挺好理解,在获取资源失败之后是否需要阻塞,代码如下:
这个方法我们可以理解为只有当该节点的前驱结点的状态为SIGNAL
时,才可以对该结点所封装的线程进行 park 操作。否则,将不能进行 park 操作。其中各属性如下:
int CANCELLED = 1
,即waitStatus
值为 1 ,表示该线程节点已释放(超时、中断),已取消的节点不会再阻塞。int SIGNAL = -1
,即waitStatus
为 -1 ,表示前驱节点已经设置了SIGNAL
,闹钟已经设好,现在我可以安心睡觉(阻塞)了。如果前驱变成了 head,并且 head 的代表线程 exclusiveOwnerThread 释放了锁,就会来根据这个 SIGNAL 来唤醒自己。int CONDITION = -2
,即waitStatus
为 -2 ,表示该线程在Condition
队列中阻塞(Condition 有使用)int PROPAGATE = -3
,即waitStatus
为 -3,表示该线程以及后续线程进行无条件传播(CountDownLatch
中有使用)共享模式下,PROPAGATE
状态的线程处于可运行状态 。
再看parkAndCheckInterrupt()
方法,源码如下:
使用 LockSupport.park 挂起当前线程变成 WATING 状态,关于 LockSupport 可以查看这篇文章:LockSupport功能简介及原理浅析
Thread.interrupted()
,返回当前线程是否被其他线程触发过中断请求,也就是Thread.interrupt()
, 如果有触发过中断请求,那么这个方法会返回当前的中断标识 true,并且对中断标识进行复位标识已经响应过了中断请求。如果返回 true,意味着在 acquire()
方法中会执行 selfInterrupt()
。
因此,selfInterrupt()
执行的前提是 acquireQueued(addWaiter(Node.EXCLUSIVE), arg)
方法返回 true。这个方法返回的是线程在获取锁的过程中是否发生过中断,返回 true 则证明发生过中断。所以 acquire()
中的 selfInterrupt()
其实是对获取锁的过程中发生过的中断的补充。
怎么理解?为什么 park
之后要调用Thread.interrupted()
以及selfInterrupt()
。
当调用了 LockSupport 的 park 后,该线程从 park 方法返回的情况有两种:
一种是其他线程释放了资源,调用了该线程的
unpark
方法。
如果是被调用了unpark
方法,那么 Thread.interrupted()
将返回 false,然后进入循环代码继续尝试获取锁,这一步就是正常情况。
另外一种就是该线程被某些线程给中断了,但是如果是因为线程被中断而返回,那么
Thread.interrupted()
将返回 true,如果此时线程从循环中获取到了资源,那么最终会调用selfInterrupt()
这个方法,此时又会中断该线程。
问题来了,为什么获取到锁后要进行一次中断?个人觉得这一步主要是为了该线程的中断信息不被吃掉,当调用 park 方法阻塞后,如果被中断了,那么继续回去获取锁,获取锁后,会再次中断自己,让上层调用者获取到自己被中断的信息,由上层调用者决定是否对中断处理,而不是悄悄把中断信息吃掉。因为我们知道lock()
方法是不能被中断的。
可以参考 lockInterruptibly()
这个方法,这里面唯一的区别就是调用 park 后,如果线程发生了中断,则直接抛出中断异常,而不是去获取锁了。
9、cancelAcquire()
。然后在acquireQueued()
的 final 块中还有一个方法cancelAcquire()
,该方法完成的功能就是取消当前线程对资源的获取,即设置该结点的状态为 CANCELLED,一般来说条件比较苛刻,而且对加锁过程影响不是很大,至少我没看出什么影响,并且暂时没想到什么场景去适配,所以这里不在细究。
其中对于unparkSuccessor
函数,其主要目的就是为了唤醒 node 节点的后继结点。也就是当前节点拿到锁释放之后,回去唤醒后继结点,所以此时把首节点指向了释放锁后的下一节点。源码如下:
然后再回到上面遗留的问题,**为什么必须前驱结点为头结点才尝试去获取锁?**原因有两个:
因为头结点表示当前正占有锁的线程。我们想想头结点有什么?头节点代表第一个进入队列的线程,注意是进入队列的线程,不是指上面例子的
t1
,上面的例子t2
线程才是第一个进入队列的线程,如果t1
这时候释放了锁且同时没有其他线程来竞争锁,那么它将直接拿到锁,并成功获取到同步状态state
,即头节点是成功获取到同步状态的节点,如果这个时候第二个线程进入队列,那么它会去看它的前驱节点是否是头结点,因为头结点有同步状态state
,如果刚好释放那么他就立刻获取锁,否者排队阻塞。维护同步队列的 FIFO 原则。当线程获取到同步状态后,让首节点这个引用指向自己所在节点。当同步状态获取成功后,当前线程就从 acquire 方法返回了。如果同步器实现的是锁,那就代表当前线程获得了锁。
因此,进入队列和排队是两回事,也就是说我进入队列了我并不一定就是在排队(park),举个例子:
比如我们去火车站买票,如果说我们看到售票窗口处于空闲状态,即没人排队买票,那这个时候你就直接去买就行,如果有人在排队,一般来说排队的时候我们可能就会玩玩手机,但不是一定排队就会去玩手机,你会看看前面那个人是不是第一个人,如果是第一个人的话,那可能马上就轮到你了,你就不用掏出手机来玩了,如果不是得话,你才掏出手机玩直到你前面只有一个人的时候才收起手机。
小结
总结一下非公平锁获取锁的流程:
第一次去获取锁的时候,会去尝试去加锁。
如果加锁失败,则去看为什么失败(是否锁被人持有了)。
在判断的过程中如果锁没有被持有,非公平锁就会去直接加锁(不会判断是否有人排队),成功则进入同步块,失败则进入队列。
进入队列后如果前面获取锁的节点是头结点 head 则再次尝试加锁,成功则执行同步代码块,失败则
park()
(真正的排队)。
解锁流程
解锁流程就比较简单。
1、unlock()
2、release()
该方法在 if 语句中调用了tryRelease()
,源码如下:
tryRelease()
的作用是将线程持有锁的次数减 1 ,即将 state 值减 1,若减少后线程将完全释放锁(state==0
),则该方法将返回 true,否则返回 false。由于执行该方法的线程必然持有锁,故该方法不需要任何同步操作,等待流程走完即可。若当前线程已经完全释放锁,即锁可被其他线程使用,则还应该唤醒后续等待线程。
若tryRelease()
尝试释放锁返回 true,则需要满足 if 语句中的 2 个条件:
head != null
。防止队列为空队列,若头节点为 null,则说明队列中没有其他线程处于队列中,当然也就无需执行唤醒操作。h.waitStatus != 0
。是为了防止队列中虽有线程,但该线程还未阻塞,由前面的分析知,线程在阻塞自己前必须设置前驱结点的状态为 SIGNAL,否则它不会阻塞自己。如果没阻塞那也就不需要被唤醒。
如果上述 2 个条件都满足,则需要通过unparkSuccessor()
去唤醒后继节点,该方法的源码如下:
一般情况下只要唤醒后继结点的线程就行了,但是后继结点可能已经取消等待,所以从队列尾部往前回溯,找到离头结点最近的正常结点,并唤醒其线程。
主要注意的是,因为这里是非公平锁,所以唤醒不等于拥有锁,因为在高并发场景下如果有外部的线程也来获取锁,那么此时的同步状态已经改为了 0,CAS 成功获取锁,而s.thread
被唤醒后还是也需要通过tryAcquire()
方法去竞争,如果竞争失败则继续阻塞,等着获取的线程再次唤醒自己。
当然,如果使用的是公平锁(fair),那么它就一定会被唤醒,因为其他来的线程不会首先去获取锁,而是直接被放到队尾。
公平锁
加锁流程
对于公平锁我们依旧通过入口lock()
分析:
1、lock()
。FairSync
类的方法。
2、acquire()
。
3、tryAcquire()
。FairSync
类的方法。
对比非公平锁的tryAcquire()
发现不同点,多了一个hasQueuedPredecessors()
方法:
先理解字面意思,该方法是判断队列中是否有优先级更高的等待线程,队列中哪个线程优先级最高?由于头结点是当前获取锁的线程,那么队列中的第二个结点代表的线程优先级最高。
因此,我们需要判断队列中的第二个节点是否存在以及这个节点是否为当前线程。
先把上面 return
的代码分解开来分析:
h != t
当它们为
fasle
说明头节点和尾结点指向同一节点,即上个节点获取锁的节点是头结点 head,然后 CAS 尝试加锁,否者走下面的判断。(s = h.next) == null || s.thread != Thread.currentThread()
第二个节点不存在:
这个不存在并不是真的不存在,只是由于 CPU 上下文切换的原因,通过对非公平锁的入队
enq()
方法我们可以知道节点入队有三步:① 将待插入结点的 prev 指针 连接到原尾结点。
② CAS 更新尾指针。
③ 把原尾结点的 next 指针指向待插入结点。
因此
s = h.next
的作用是用来判断 ② 刚执行完成,但是还未执行 ③ 这种情况,如果是这种情况直接返回 true,即s = h.next ==null = true
,那么hasQueuedPredecessors()
返回 true,tryAcquire()
返回 false,然后进入队列乖乖排队。第二个节点存在且是否代表当前线程:
如果
s = h.next == null = false
,此时第二个节点已经完全插入到队列中,通过s.thread != Thread.currentThread()
进行判断,如果为 true,说明不是当前线程,队列中前面还有未执行的线程,所以进入队列乖乖排队。否则,说明队列没有排队的线程了,直接获取锁。
解锁流程
公平锁的释放同非公平锁的释放。
面试题
1、什么是非公平锁,什么是公平锁?
非公平锁:
第一次去获取锁的时候,会去尝试去加锁。
如果加锁失败,则去看为什么失败(是否锁被其他线程持有了)。
在判断的过程中如果锁没有被持有,非公平锁就会去直接加锁(不会判断是否有线程排队),成功则进入同步块,失败则进入队列(并不等于排队)。
进入队列后如果前面获取锁的节点是头结点 head 则再次尝试加锁,成功则执行同步代码块,失败则
park()
(真正的排队)。
公平锁:
第一次去获取锁的时候,不会去尝试加锁,会去看一下前面有没有线程在排队(
hasQueuedPredecessors
),如果有,则进入队列(并不等于排队)。然后还不死心,再次看一下我有没有拿锁的资格(前面那个人是否为 head,同非公平锁),如果有资格(前面节点刚好为 head)则继续拿锁,成功则执行同步块,失败则 park(排队)。
记住一句话:一朝排队,永远排队。
2、在解锁过程中,为什么unparkSuccessor()
方法中 for 循环是从 tail 开始而不是 head?
为什么呢?Doug Lea 为什么这么设计?其必然是为了解决某些问题?而这个问题就出在入队过程的enq()
方法:
可以看到在初始化队列后,else
代码块中是没有利用任何手段来保证线程安全的。若有其他线程入队,在入队之前的队列状态为:
若线程 A 到来则先执行
node.prev = t
,然后并通过 CAS 把当前节点设置为尾节点,此时正常情况下将执行t.next = node
,如下:在正常情况下上面是没问题的,我们知道 CAS 是基于 CPU 的,在高并发场景下,如果此时线程 B 也到来,即当 A 还没有执行完
t.next = node
这一步时,CPU 发生上下文切换,把时间片给了 B,那么此时线程 B 则开始执行enq()
入队操作,不管线程 B 是否执行完成,但此时对于上图中的node
节点来说:node.next = null
。然后 CPU 发生上下文切换,把时间片给了线程 C ,线程 C 是解锁线程调用
unparkSuccessor()
方法,如果此时是从头到尾的方式,则发现node.next = null
,会发现没后后继节点了。但此时再次发生上下文切换,时间片交由线程 A,A 执行
t.next = node
,则此时node.next = nodeA
。所以问题就来了:对于线程 C 来说,后续没有 nodeA 及后续节点,但是对于其它线程来说,却有这个节点。
那么为什么从尾部遍历不会出现这种问题呢?
是因为node.prev = t
先于 CAS 执行,也就是说,你在将当前节点置为尾部之前就已经把前驱节点赋值了,自然不会出现prev = null
的情况。
所以,Doug Lea 有多牛逼不用说了吧。
参考:https://blog.csdn.net/foxException/article/details/108917338
3、为什么选择非公平锁?
一切为了效率。
版权声明: 本文为 InfoQ 作者【Ayue、】的原创文章。
原文链接:【http://xie.infoq.cn/article/e6ff008acd8918f209222eeba】。文章转载请联系作者。
评论