- 如何获取资源(锁)?
- 获取不到资源的线程如何处理?
- 如何释放资源?
- 资源释放后如何让其他线程获取资源?
由此可以得出实现一把锁,应该具备哪些逻辑:
- 锁的标识
需要有个标识或者状态来表示锁是否已经被占用。 - 线程抢锁的逻辑
多个线程如何抢锁,如何才算抢到锁,已经抢到锁的线程再次抢锁如何处理等等。 - 线程挂起的逻辑
线程如果抢到锁自然顺利往下运行了,而那些没有抢到锁的线程怎么处理呢?如果一直处于活跃状态,cpu肯定是吃不消,那就需要挂起。具体又如何挂起呢? - 线程存储机制
没有抢到锁的线程就挂起了,而且被挂起的线程可能有很多个,这些线程总要放在某个地方保存起来等待唤醒,然而这么多被挂起的线程,要唤醒哪一个呢?这就需要一套保存机制来支撑唤醒逻辑。 - 线程释放锁的逻辑
线程在执行完后就要释放锁,跟抢锁逻辑是对应的,其实也是操作锁标识。 - 线程唤醒的逻辑
锁释放后,就要去唤醒被阻塞的线程,这就要考虑唤醒谁,如何唤醒,唤醒后的线程做什么事情。
带着上面的思考,我们来看看AQS是怎么处理的。
AQS由来
在最早期java中的同步机制是通过关键字synchronized实现,这个锁是java原生的,jvm层面实现的。在1.6之前synchronized的性能比较低,是一把纯重量级锁。
后来,Doug Lea开发并引入了java.util.concurrent包,这个包基本涵盖了java并发操作的半壁江山,该包内的并发工具类基本是以AQS为基础的,AQS提高了同步操作的性能,在性能上远超当时的synchronized,后来synchronized做了优化,java1.6及之后两者的性能就差不多了。
AQS是什么
AQS的全称为AbstractQueuedSynchronizer。
AQS其实是一个抽象类,它实现了线程挂起的逻辑,实现了线程存储机制,实现了锁的状态逻辑,实现了线程唤醒的逻辑,却只定义了线程抢锁和释放锁的抽象,这样做的目的是将抢锁和释放锁的逻辑交给子类来实现,这样有助于实现各种不同特性的锁,比如共享锁,独占锁,公平锁,非公平锁,可重入等。并且以模板方法模式将上述上锁流程和释放锁流程封装为固定模板方法。所以AQS就是一个多线程访问共享资源的同步器框架。
AQS实现同步机制有两种模式,一种是独占模式,一种是共享模式。两种模式分别提供提供两个模板方法实现。四个模板方法为acquire,release,acquireShared,releaseShared。
- 独占模式的锁是只允许一个线程持有锁
- 共享模式的锁是允许多余一个的线程持有锁
- 接下来分别介绍这四个方法的逻辑
acquire方法解析
public final void acquire(int arg) {
if (!tryAcquire(arg) &&
acquireQueued(addWaiter(Node.EXCLUSIVE), arg))
selfInterrupt();
}
acquire方法是独占模式上锁的整个逻辑,这个方法是一个模板方法,其中的tryAcquire是获取锁的逻辑,这个方法是一个抽象方法,由具体的子类实现,如何获取锁,怎样才算获取到锁这些问题子类自己决定,AQS不做处理。
addWaiter方法负责是线程存储的逻辑,aqs里面存储机制的核心是两个队列,等待队列和条件队列,它们用来保存被阻塞的线程,在这个方法中通过cas+自旋的方式将线程添加到等待队列中。
先来介绍等待队列,等待队列的结构如下:
图片
等待队列是一个双向链表,每个节点就是一个node对象,node是aqs类中的一个静态内部类,它的属性如下:
- node{thread;prev;next;nextWaiter;waitStatus;}
- thread是当前node节点所绑定的线程;
- prev是前置节点的引用;
- next是后置节点的引用;
- nextWaiter如果是等待队列节点就标示独占模式节点还是共享模式,如果是条件队列节点就作为后置节点指针;
waitStatus是节点的状态,其状态值如下:
- static final int CANCELLED = 1; 出现异常
- static final int SIGNAL = -1;可被唤醒
- static final int CONDITION = -2; 条件等待
- static final int PROPAGATE = -3;传播
AQS类自身也有几个比较重要的属性:
//正在持有锁的线程
private transient Thread exclusiveOwnerThread;
//等待队列的头节点
private transient volatile Node head;
//等待队列的尾节点
private transient volatile Node tail;
//锁标识字段
private volatile int state;
了解了等待队列,接下来具体看看addWaiter方法的逻辑;
- 首先如果队列还没有初始化会先初始化队列,初始化就是先创建一个空的node节点,把aqs里面的head和tail属性指向这个空的node,初始化完成;
图片
- 先创建一个node节点,默认属性如下:
node{ thread=当前线程t1;prev;next;nextWaiter=独占模式;waitStatus=0}
开始入队操作,入队就是cas+自旋的方式将tail指针指向新加入的node节点,并且把新加入的node和head建立双向指针。
图片
cas是保证原子性的,多线程操作的情况下,当前线程可能会操作失败,自旋是为了失败重试,保证一定能够入队成功。
入队成功后,就要挂起线程了,acquireQueued方法就是挂起操作。
这个方法比较核心,线程挂起的逻辑和线程唤醒后的逻辑都在此方法中,源码如下:
final boolean acquireQueued(final Node node, int arg) {
boolean failed = true;
try {
boolean interrupted = false;
for (;;) {
final Node p = node.predecessor();
if (p == head && tryAcquire(arg)) {
setHead(node);
p.next = null; // help GC
failed = false;
return interrupted;
}
if (shouldParkAfterFailedAcquire(p, node) && parkAndCheckInterrupt())
interrupted = true;
}
} finally {
if (failed)
cancelAcquire(node);
}
}
逻辑解析:
- 开启for循环,让线程处于循环中
- node节点已经入队,先拿到node节点的前置节点,然后做如下判断
if (p == head && tryAcquire(arg))
上面介绍了等待队列,等待队列的head节点永远是一个不绑定线程的节点,所以拿到前置节点后判断是否为head节点,如果为head节点才有资格再次获取锁,可以发现如果队列中已经有其他线程处于阻塞等待状态,新入队线程是在这个判断中永远会返回fasle。
这个判断加在这里有什么用处呢?
有两个用处:第一个是入队后挂起前这个时间段中,可能锁已经被释放了,所以这里再次尝试获取锁,这样就不用阻塞挂起了;第二个用处是,这个判断处于循环中,阻塞挂起的动作也是在循环中,当被唤醒后,线程会从被挂起的点继续运行,会再次进入这个判断,从而实现被唤醒的线程再次尝试换取锁的逻辑。
- 如果没有获取到锁,那接下来就会进入这个方法shouldParkAfterFailedAcquire,这个方法的源码如下
private static boolean shouldParkAfterFailedAcquire(Node pred, Node node) {
int ws = pred.waitStatus;
if (ws == Node.SIGNAL)
return true;
if (ws > 0) {
do {
node.prev = pred = pred.prev;
} while (pred.waitStatus > 0);
pred.next = node;
} else {
compareAndSetWaitStatus(pred, ws, Node.SIGNAL);
}
return false;
}
代码逻辑为:获取node节点的前置节点的waitStatus属性;
如果waitStatus为-1返回true;
如果waitStatus>0,根据waitStatus状态可知,大于0的只有1,1代表线程被取消或者线程异常,所以这里的做法是将异常的node节点从队列中移除,采用的方式为从尾节点开始向前遍历判断移除,直到遇到一个非异常节点。返回false。
如果waitStatus小于-1,那就把waitStatus通过cas改为-1,返回false。
如果此方法返回false,因为当前处在循环中,所以会再次进入此方法,此时一定会返回true。
只有将当前node节点的前置节点设置为-1后,此方法才会返回true,从而会进入后面的parkAndCheckInterrupt()方法,这个方法就很简单了,就是调用LockSupport类的park方法将线程阻塞挂起。
private final boolean parkAndCheckInterrupt() {
LockSupport.park(this);
return Thread.interrupted();
}
为什么在阻塞前一定要将当前node节点的前置节点置为-1?
waitStatus为-1代表可唤醒状态,独占模式下,AQS在唤醒被阻塞线程的时候,总是通过判断head节点的waitStatus状态,如果为可唤醒状态代表head后面的节点可以被唤醒,否则不允许唤醒。
这样做的好处是,当head节点后面线程获取到锁并出队后,可以直接将head指针移动到第一个线程节点,然后将此节点上的前置指针删除,将线程属性删除,作为新的head节点。
图片
当线程调用park方法后,线程就阻塞在这里,当被唤醒后,线程也是从这个点继续往下进行,此时依然处在循环中,这个时候会开始新一轮循环,从而再次进入尝试获取锁的判断,如果获取到锁,就出队,否则再次进入阻塞挂起的方法进行挂起操作。
这里的设计是先抢锁,抢到锁后再出队,避免在没有抢到锁的情况下不用再次入队造成的时间消耗。
release方法解析
//独占模式的锁调用的释放锁逻辑
public final boolean release(int arg) {
if (tryRelease(arg)) {
Node h = head;
if (h != null && h.waitStatus != 0)
unparkSuccessor(h);
return true;
}
return false;
}
这个方法也是一个模板方法,tryRelease是释放锁的方法,它是抽象方法,具体由子类来实现。
释放成功后就要唤醒被阻塞的线程,核心逻辑在下面这个方法中,源码如下:
private void unparkSuccessor(Node node) {
int ws = node.waitStatus;
if (ws < 0)
compareAndSetWaitStatus(node, ws, 0);
Node s = node.next;
if (s == null || s.waitStatus > 0) {
s = null;
for (Node t = tail; t != null && t != node; t = t.prev)
if (t.waitStatus <= 0)
s = t;
}
if (s != null)
LockSupport.unpark(s.thread);
}
先看下整体逻辑,这两段代码的逻辑其实很简单:
- head节点的waitStatus属性为-1,才能进入unparkSuccessor进行唤醒逻辑
- 在unparkSuccessor方法中首先会将head节点的waitStatus改为0
- 取head节点的下一个节点next,要判断next节点的waitStatus属性是否大于0,如果大于0表示此节点异常或者被取消属于非正常节点,从尾节点向前遍历直到找到最靠近head节点的正常节点,即为要唤醒的线程。
- 最后调用LockSupport.unpark方法唤醒线程。
逻辑很容能看懂,但是这里有个问题,为什么前面有这段代码
if (h != null && h.waitStatus != 0)
unparkSuccessor(h);
后面unparkSuccessor方法又有这一段代码
if (ws < 0)
compareAndSetWaitStatus(node, ws, 0);
不难看出逻辑是waitStatus不为0进入unparkSuccessor方法,进入方法马上把waitStatus改为0,这是在阻止后续的线程再进来。
那真正的用意是什么呢?
通过上面代码可以知道释放锁逻辑和唤醒逻辑是分开的,看下面的时间抽
- 线程1抢到锁
- 线程1释放锁
- 线程2抢到锁
- 线程1判断head节点waitStatus状态为-1后,进入unparkSuccessor方法执行唤醒操作,该方法第一步是将waitStatus状态改为0
- 线程2释放锁
- 线程2判断head节点waitStatus状态为0后,不会进入unparkSuccessor方法
上面这个场景是非公平锁的场景,公平锁说的是所有线程都要按照顺序排队获取锁,而非公平锁说的是新进来的线程可以和刚被唤醒的线程抢锁。
在非公平锁的场景中,如果代码块中的逻辑执行的足够快就有可能发生上面的情况,线程1和线程2都是都去唤醒同一个线程,所以这里通过将head节点的waitStatus改为0的方式将其他线程拒之门外,这样就保证在head节点后面的线程只会由一个线程去唤醒。
acquireShared方法解析
//共享模式的锁调用的上锁逻辑
public final void acquireShared(int arg) {
if (tryAcquireShared(arg) < 0)
doAcquireShared(arg);
}
此方法同样是一个模板方法,tryAcquireShared方法是抽象方法,供子类实现抢锁的逻辑,doAcquireShared方法则是实现阻塞挂起和入队,doAcquireShared方法源码如下:
private void doAcquireShared(int arg) {
final Node node = addWaiter(Node.SHARED);
boolean failed = true;
try {
boolean interrupted = false;
for (;;) {
final Node p = node.predecessor();
if (p == head) {
int r = tryAcquireShared(arg);
if (r >= 0) {
setHeadAndPropagate(node, r);
p.next = null; // help GC
if (interrupted)
selfInterrupt();
failed = false;
return;
}
}
if (shouldParkAfterFailedAcquire(p, node) &&
parkAndCheckInterrupt())
interrupted = true;
}
} finally {
if (failed)
cancelAcquire(node);
}
}
private void setHeadAndPropagate(Node node, int propagate) {
Node h = head;
setHead(node);
if (propagate > 0 || h == null || h.waitStatus < 0 || (h = head) == null || h.waitStatus < 0) {
Node s = node.next;
if (s == null || s.isShared())
doReleaseShared();
}
}
通过源码会发现doAcquireShared这个方法合并了入队和挂起两个步骤,整体的逻辑基本和独占模式一样,接下来只介绍不同的地方。
第一个不同,入队的时候创建的node节点为共享模式节点,即nextWaiter属性的值不同。
第二个不同,独占模式下线程被唤醒重新获取到锁后,就要出队了,而共享模式下除了出队,还会判断是否资源充足,如果充足就唤醒下一个节点。
releaseShared方法解析
//共享模式的锁调用的释放锁的逻辑
public final boolean releaseShared(int arg) {
if (tryReleaseShared(arg)) {
doReleaseShared();
return true;
}
return false;
}
同样此方法也是模板方法,tryReleaseShared方法是交给子类实现的释放锁的逻辑,doReleaseShared方法则是aqs自己实现的唤醒逻辑,唤醒逻辑和独占模式下的唤醒逻辑大同小异,都是唤醒head节点的下一个节点绑定的线程,不再过多赘述。
总结一下独占和共享模式在aqs中实现的最大不同是被唤醒的线程出队后会在资源充足的情况下顺便唤醒其后面节点的线程。
AQS中的Condition
上面说过,AQS有两个队列,等待队列和条件队列,上面介绍了等待队列,但是条件队列一直未提,那么条件队列是做什么的呢?
先说下条件队列的结构;
AQS内部有一个内部类ConditionObject,其内部维护了一个单向链表(先进先出),这个内部类内有两个属性:firstWaiter和lastWaiter分别指向单向链表的头结点和尾节点,这个单向链表就是条件队列,和等待队列的不同处是它的头节点是绑定线程的,条件队列的结构如下:
图片
这个内部类主要的方法是如下三个,这里直接说每个方法的底层逻辑,源码就不展示了,可以自己去查阅源码。
首先先说下Condition整体的思维逻辑。
- 入队,包括初始化条件队列,队列的节点依然是node对象,利用nextWaiter属性指向下一个节点,waitStatus属性的值默认为-2,代表等待。
- 释放锁,在入队后就要释放锁了。
- 阻塞
- 条件达成后换队。
- 阻塞被唤醒后,按照独占锁的方式去再次尝试抢锁吗,这里和独占模式下的唤醒逻辑是一样的。
await()的逻辑;
- 入队,包括初始化条件队列,队列的节点依然是node对象,利用nextWaiter属性指向下一个节点,waitStatus属性的值默认为-2,代表等待。
- 释放锁,在入队后就要释放锁了。
- 阻塞。
signal()的逻辑;
- 条件达成后换队
- 阻塞被唤醒后,按照独占锁的方式去再次尝试抢锁吗,这里和独占模式下的唤醒逻辑是一样的。
条件达成后换队的意思就是将条件队里的头节点移动到独占模式的等待队列中去,入队的方式和独占模式下入队方式一样,入队之后会将当前节点的前一个节点的waitStatus置为-1,代表可唤醒。
- signalAll()的逻辑
这个方法和上面的方法一样,不同点就是此方法是将条件队列的节点一个一个全部移动到等待队列上去。
看的出来Condition中的条件队列依赖等待队列,具体使用可以参考ReentrantLock。你会发现在ReentrantLock锁里面使用Condition,就相当于在synchronized代码块中使用object类的wait方法和nottfyf。
为了更好的理解Condition,一起看下ArrayBlockingQueue的实现,它是一个数组实现的先进先出的有界阻塞队列,队列满,入队者等待,队列空,出队者等待。
这个队列有两个重要的特点:先进先出和队列有界。
为保证先进先出,需要加锁处理,获取到锁的线程才有资格向队列中放数据或者取出数据。
那如何保证队列有界的情况下等待处理呢?这个时候就用到Condition了,它的逻辑是这样的,所有想向队列添加数据的和所有想从队列取数据的线程一起竞争锁,拿到锁的那个线程才有资格操作,ArrayBlockingQueue维护里两个Condition对象,也就相当于维护两个条件队列,如果是添加数据的某个线程抢到了锁,在操作添加的时候,发现队列已满,此时该线程无法将数据插进去,需要等待有一个数据被取走后才能做添加操作,但是该线程占有锁资源,取数据的线程进不来,所以就无法进行下去,ArrayBlockingQueue的做法是将该线程放入条件队列阻塞挂起,等到有一个数据被取走后,再把条件队列中的挂起的线程搬运到锁的等待队里上去,从而再次获取排队抢锁的资格。
之所以维护两个Condition条件队列是为了将添加数据的线程和取数据的线程分开,根据不同的条件操作不同的条件队列。
有没有发现,这不就是synchronized代码块中的object类的wait方法吗?
但是不同点是调用object类的wait方法阻塞的线程,要么只有一个被释放,要么全部释放。
而Condition就不同了,因为你可以声明多个Condition对象,将不同条件下阻塞的线程放入不同的Condition对象,释放的时候也按照条件释放,这就真正意义上实现了按条件释放。
我说的释放是重新获取排队抢夺资源的资格。
AQS中的中断
不可中断说的是阻塞状态不能被终止。
我们知道synchronized是不可中断的锁,当线程因为竞争资源失败而进入阻塞状态后,唯一能让该线程结束阻塞的方式就是持有锁资源的线程处理完成后,被阻塞的线程被唤醒。
synchronized中的阻塞状态不可中断是因为线程的阻塞唤醒是由操作系统来管理,而AQS中的阻塞之所以支持中断是因为上锁是通过LockSupport类的park方法来实现的,当线程调用park方法阻塞后,如果调用此线程interrupt方法,阻塞状态就会中断,也就是阻塞中的线程会被唤醒。
但是调用acquire上锁的时候如果没有获取到锁就会被阻塞,此时如果调用被阻塞线程的interrupt方法就会唤醒这个线程,但是此时被唤醒的线程处于循环之中,会重新去抢锁,如果获取不到依然会再次阻塞,也就是说acquire方法中被阻塞的线程被中断后只不过会让线程提前加入抢锁,但是并不会增加抢到锁的概率,因为只有阻塞队列的头节点才有资格抢锁。
这里介绍一个知识点:常见的可中断方法sleep,wait,park方法,这三个方法都会使得线程处于静止状态,此时调用interrupt方法,会中断其静止状态,线程从而处于重新被激活的状态,不同的是被激活后的线程的中断状态是不一样的,sleep和wait方法被激活后,线程的中断状态为false,而park方法被激活后,线程的中断状态为true,这是需要注意的。
按照上面的说法AQS虽然支持中断,但是似乎没什么用,其实AQS还有一个相对于acquire方法不那么常用的方法tryAcquireNanos方法。
跟一下这个方法进入doAcquireNanos方法,主要逻辑就在这个方法中,其实和tryAcquireNanos和acquire一样,都是抢锁,入队,阻塞,唤醒那一套逻辑。
不同的是tryAcquireNanos方法还具备两个技能:
- 支持指定阻塞时间,一定时间后线程将会自动唤醒,自动唤醒后的线程的中断状态为false。
- 支持被中断后抛出异常InterruptedException。
private boolean doAcquireNanos(int arg, long nanosTimeout)
throws InterruptedException {
if (nanosTimeout <= 0L)
return false;
final long deadline = System.nanoTime() + nanosTimeout;
final Node node = addWaiter(Node.EXCLUSIVE);
boolean failed = true;
try {
for (;;) {
final Node p = node.predecessor();
if (p == head && tryAcquire(arg)) {
setHead(node);
p.next = null; // help GC
failed = false;
return true;
}
nanosTimeout = deadline - System.nanoTime();
if (nanosTimeout <= 0L)
return false;
if (shouldParkAfterFailedAcquire(p, node) &&
nanosTimeout > spinForTimeoutThreshold)
LockSupport.parkNanos(this, nanosTimeout);
if (Thread.interrupted())
throw new InterruptedException();
}
} finally {
if (failed)
cancelAcquire(node);
}
}
上面的代码可以清楚的看到阻塞操作是通过这段代码实现:
LockSupport.parkNanos(TimeUnit.SECONDS.toNanos(10));
parkNanos方法相对与park方法的区别就是parkNanos方法可以指定阻塞时间。
而下面这段代码实现的就是阻塞被中断的时候主动抛出InterruptedException异常,可以让方法外部捕获到这个异常,从而达到真正的阻塞中断。
if (Thread.interrupted())
throw new InterruptedException();