初步了解AQS是什么(二)

1,282

前题

在阅读本文之前,建议先阅读我的《初步了解AQS是什么(一)》,毕竟有一些内容是和前文是相通的,如果对AQS熟悉的话,也可以直接往下看,不过还是先建议先看下

公平锁和非公平锁

ReentrantLock默认使用的是非公平锁,除非在构造方法里面传入true就可以变为公平锁啦!

 public ReentrantLock() {
        sync = new NonfairSync();
 }

 public ReentrantLock(boolean fair) {
        sync = fair ? new FairSync() : new NonfairSync();
 }

先看看公平锁的lock

 final void lock() {
            acquire(1);
        }
//----------------------------acquire

 public final void acquire(int arg) {
        if (!tryAcquire(arg) &&
            acquireQueued(addWaiter(Node.EXCLUSIVE), arg))
            selfInterrupt();
    }


//-----------------------------tryAcquire
protected final boolean tryAcquire(int acquires) {
            final Thread current = Thread.currentThread();
            int c = getState();
            if (c == 0) {
                //因为是公平锁,那么到这里如果有线程在等待,就公平而言,肯定是不能抢前面的锁啦!
                //和非公平锁的区别
                if (!hasQueuedPredecessors() &&
                    compareAndSetState(0, acquires)) {
                    setExclusiveOwnerThread(current);
                    return true;
                }
            }
            else if (current == getExclusiveOwnerThread()) {
                int nextc = c + acquires;
                if (nextc < 0)
                    throw new Error("Maximum lock count exceeded");
                setState(nextc);
                return true;
            }
            return false;
        }

非公平锁的lock

 final void lock() {
            if (compareAndSetState(0, 1)) // 非公平锁会先试着去占有这个锁先,如果不行就再获取!
                setExclusiveOwnerThread(Thread.currentThread());
            else
                acquire(1);
        }

//-------------------------acquire
 public final void acquire(int arg) {
        if (!tryAcquire(arg) &&
            acquireQueued(addWaiter(Node.EXCLUSIVE), arg))
            selfInterrupt();
    }

//-----------------------tryAcquire
protected final boolean tryAcquire(int acquires) {
            return nonfairTryAcquire(acquires);
        }

//-----------------------nonfairTryAcquire
  final boolean nonfairTryAcquire(int acquires) {
            final Thread current = Thread.currentThread();
            int c = getState();
            if (c == 0) {
                //如果资源可以抢,非公平锁可不管你前面是否有节点在等待,我先抢了再说!公平锁就等待啦!
                if (compareAndSetState(0, acquires)) {
                    setExclusiveOwnerThread(current);
                    return true;
                }
            }
            else if (current == getExclusiveOwnerThread()) {
                int nextc = c + acquires;
                if (nextc < 0) // overflow
                    throw new Error("Maximum lock count exceeded");
                setState(nextc);
                return true;
            }
            return false;
        }

总结:

  1. 非公平锁在lock的时候,在tryAcquire函数里面会CAS获取state,如果恰好成功,那么就直接取得锁啦,不用进行下面的操作了

  2. 非公平锁在 CAS 失败后,和公平锁一样都会进入到 tryAcquire 方法,在 tryAcquire 方法中,如果发现锁这个时候被释放了(state == 0),非公平锁会直接 CAS 抢锁,但是公平锁会判断等待队列是否有线程处于等待状态,如果有则不去抢锁,乖乖排到后面。

  3. 非公平锁如果两次CAS都不成功,那么接下来的操作和公平锁一样啦!都要进入到阻塞队列等待唤醒。

  4. 非公平锁会有更好的性能,因为它的吞吐量比较大。当然,非公平锁让获取锁的时间变得更加不确定,可能会导致在阻塞队列中的线程长期处于饥饿状态。

生产者消费者模式

在读下面的内容的时候,让我们来先了解一下生产者和消费者的模式,主要有个例子,更好地理解下面的内容!

import java.util.concurrent.locks.Condition;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;

class BoundedBuffer {
    final Lock lock = new ReentrantLock();
    // condition 依赖于 lock 来产生
    final Condition notFull = lock.newCondition();
    final Condition notEmpty = lock.newCondition();

    final Object[] items = new Object[100];
    int putptr, takeptr, count;

    // 生产
    public void put(Object x) throws InterruptedException {
        lock.lock();
        try {
            while (count == items.length)
                notFull.await();  // 队列已满,等待,直到 not full 才能继续生产
            items[putptr] = x;
            if (++putptr == items.length) putptr = 0;
            ++count;
            notEmpty.signal(); // 生产成功,队列已经 not empty 了,发个通知出去
        } finally {
            lock.unlock();
        }
    }

    // 消费
    public Object take() throws InterruptedException {
        lock.lock();
        try {
            while (count == 0)
                notEmpty.await(); // 队列为空,等待,直到队列 not empty,才能继续消费
            Object x = items[takeptr];
            if (++takeptr == items.length) takeptr = 0;
            --count;
            notFull.signal(); // 被我消费掉一个,队列 not full 了,发个通知出去
            return x;
        } finally {
            lock.unlock();
        }
    }
}

上面只是贴个代码,先让读者知道怎么用ReentrantLock和Condition,关于更多的细节,请读者自行百度即可。

ConditionObject

Condition接口的实现类。Condition的方法依赖于ReentrantLock,而ReentrantLock又依赖于AbstractQueueSynchronized类。

内部结构

  private static final long serialVersionUID = 1173984872572414699L;
        /** First node of condition queue. */
        private transient Node firstWaiter;
        /** Last node of condition queue. */
        private transient Node lastWaiter;

条件队列

在AQS中,其中线程等待的队列我们成为阻塞队列,这里先引入条件队列(condition queue),这里先上图看两者的关系。

区别

  1. 阻塞队列和条件队列都是node节点,也就是Node的实例。因为条件队列的节点是需要转移到阻塞队列的。
  2. ReentrantLock是可以创建多个Condition实例的,则这里会有condition1和condition2,并且ConditionObject中只有两个和节点有关的属性 firstWaiter和nextWaiter
  3. 每个Condition都有一个条件队列与之关联。当调用await()方法的时候,当先线程则会阻塞在当前地方,不会往下执行,然后将当前线程封装成Node节点,添加到条件队列的队尾。
  4. 调用Condition.signal()会触发唤醒。但是唤醒的是队头节点。也就是将对应线程的条件队列的对头(firstWaiter指向的节点)移到阻塞队列的队尾,等待获取锁。获取锁之后,await才会返回,然后继续往下执行。

源码分析

await:让线程挂起等待,并交出锁

await():是可以被中断的,调用这个方法的线程会阻塞,直到调用Signal()或者被中断。

awaitUninterruptibly():不可被中断,就是说有中断信号来了但不会响应。

public final void await() throws InterruptedException {
    		//刚开始的时候看看有没有被中断过,如果有就响应呗。
            if (Thread.interrupted())
                throw new InterruptedException();
    		// 把当前线程封装为Node节点,添加到条件队列的队尾。
            Node node = addConditionWaiter();
    		//因为在await之前,这个线程肯定是拥有锁的,所以这里完全释放锁,为什么要完全释放锁,是因为考虑到重入的问题。
    		//这里的saveState返回的是释放锁之前的state值。
            int savedState = fullyRelease(node);
            int interruptMode = 0;
    		//这里判断的await的节点有没有进入到阻塞队列,也叫同步队列。
    		//如果进入,返回true,不会执行while循环
    		//如果没进入,就等着呗,等待其他线程叫醒你或者中断信号来临呗。
            while (!isOnSyncQueue(node)) {
                LockSupport.park(this);
                if ((interruptMode = checkInterruptWhileWaiting(node)) != 0)
                    break;
            }
    		//到了这一步,已经说明node节点在阻塞队列了。那么就争抢资源,也就是AQS的争抢资源的方式。
            if (acquireQueued(node, savedState) && interruptMode != THROW_IE)
                interruptMode = REINTERRUPT;
            if (node.nextWaiter != null) // clean up if cancelled
                unlinkCancelledWaiters();
            if (interruptMode != 0)
                reportInterruptAfterWait(interruptMode);
        }

addConditionWaiter:将条件队列的节点加入阻塞队列

  private Node addConditionWaiter() {
            Node t = lastWaiter; //指向条件队列的尾节点
            // If lastWaiter is cancelled, clean out.
            if (t != null && t.waitStatus != Node.CONDITION) {
                //如果进入到这里,就说明条件队列这时候不为空,但是尾节点取消了
                //因为在尾节点加入的时候,会把ws设施为CONDITION的。
                //先把取消等待的节点清除,然后再找到真正的尾节点
                unlinkCancelledWaiters();
                t = lastWaiter;
            }
      		//之前说过,加入条件队列的时候会把ws设置为CONDITION
            Node node = new Node(Thread.currentThread(), Node.CONDITION);
            if (t == null)//这里说明条件队列为空,也就是说第一次加入
                //设置好头指针
                firstWaiter = node;
            else
                //那么这里就是条件队列不为空呗,那就加入真正尾节点后头就好了
                t.nextWaiter = node;
            lastWaiter = node;
            return node;
        }

在addConditionWaiter中,有一个unlinkCancelledWaiters()方法,顾名思义就是取消不等待的节点,因为条件队列是单向链表,所以涉及到链表的操作。

就是说如果在await的时候,节点取消等待或者是说节点入队的时候,发现最后一个节点已经取消了,那么就调用一次这个方法

// 等待队列是一个单向链表,遍历链表将已经取消等待的节点清除出去
// 纯属链表操作,很好理解,看不懂多看几遍就可以了
private void unlinkCancelledWaiters() {
    Node t = firstWaiter;
    Node trail = null;
    while (t != null) {
        Node next = t.nextWaiter;
        // 如果节点的状态不是 Node.CONDITION 的话,这个节点就是被取消的
        if (t.waitStatus != Node.CONDITION) {
            t.nextWaiter = null;
            if (trail == null)
                firstWaiter = next;
            else
                trail.nextWaiter = next;
            if (next == null)
                lastWaiter = trail;
        }
        else
            trail = t;
        t = next;
    }
}

fullyRelease: 完全释放独占锁

在await方法中,把节点加入到条件队列之后,就需要完全释放锁了。因为考虑到重入的问题,所以必须要完全释放。

例子:condition.await之前,当前节点就已经执行了两次lock()操作,那么state为2,也就是说拥有两把锁。那么fullyRelease就应该设置state为0,返回2,返回没释放锁之前所拥有的锁的数量。然后再进行挂起。当被唤醒的时候,依旧需要两把锁才能进行执行下去。

final int fullyRelease(Node node) {
        boolean failed = true;
        try {
            int savedState = getState();
            if (release(savedState)) {
                failed = false;
                return savedState; //如果完全释放锁成功,那么这里返回的是释放锁之前所用有锁的个数
            } else {
                //到这一步说明释放锁不成功,比如说有个没有锁的线程但是执行了释放锁,那么肯定会到达这一步,所以会跑出异常
                throw new IllegalMonitorStateException();
            }
        } finally {
            if (failed)
                //到达这里说明faile = true,也就是说release(savedState)返回的是false,抛出了异常,说明该节点操作不当,那么就得设置为取消,方便后面有节点加入的时候,触发unlinkCancelledWaiters,把这个节点请出去
                node.waitStatus = Node.CANCELLED;
        }
    }

isOnSyncQueue():判断是否进入阻塞队列

在await方法中,完全释放锁之后,这个方法会判断该线程代表的队列是否在阻塞队列中,注意是阻塞队列

前面我们也说过,在节点加入阻塞队列的时候,会把ws 设置为Node.Condition

final boolean isOnSyncQueue(Node node) {
    	//如果在条件队列的节点被移到阻塞队列,那么waitStatus会被设置为0,也就是在signal的时候,这个后面说
    	//所以,如果当前节点的waitStatus如果还是Condition的话,那么肯定不在阻塞队列中
    	//因为是把条件队列的firstWaiter移动到阻塞队列的,所以firstWaiter的pre是null,那么肯定不在阻塞队列中。
        if (node.waitStatus == Node.CONDITION || node.prev == null)
            return false;
        if (node.next != null) // If has successor, it must be on queue
            //这里很简单理解啦,在上面的前提下,如果next不为null,那么肯定在阻塞队列中啦,因为条件队列用的是nextWaiter,阻塞队列用的是next属性
            return true;
    	//上面曾经试过用node.pre == null  判断不在阻塞队列中,那么node.pre != null就可以判断在阻塞队列中了吗?
    	//答案非也,因为在节点加入AQS的阻塞队列的时候,会先将节点的pre设置为tail,然后再进行CAS操作将当前节点设置为tail节点,如果这个CAS操作失败了,那么此时tail节点并不是当前节点,那么也说明该节点并不在队列中
    	//所以这里有一个从尾节点往前找的函数
        return findNodeFromTail(node);
    }


//这个函数很简单,就是如果没在队列的话,那么t的最终结果为null,返回false,如果找到就返回true呗
//这里的不在队列有种情况,就是上面说的CAS将当前节点设置为tail节点失败,读者可以整理下思路。
private boolean findNodeFromTail(Node node) 
        Node t = tail;
        for (;;) {
            if (t == node)
                return true;
            if (t == null)
                return false;
            t = t.prev;
        }
    }

如果isOnSynchronized返回false的话,那么就先挂起等待呗,也就是等待其他线程signal或者中断 唤醒线程,将这个线程加入阻塞队列!

signal:唤醒线程,让线程得回锁

前面说到线程挂起了,就等待着被唤醒呗!那么这里先说下signal函数,方便后面理解。

唤醒操作一般是由另外一个线程操作的,调用同一个对象的signal对象唤醒就好,其实唤醒的操作就是将节点从条件队列移动到阻塞队列中。

        public final void signal() {
            if (!isHeldExclusively())//如果线程没有拥有排他锁,也就是没有独占锁,抛出异常呗
                throw new IllegalMonitorStateException();
            Node first = firstWaiter;
            if (first != null)
                //到这里就是找到条队列的第一个节点,然后从这个节点找并没有取消等待的线程!因为可能这时候firstWaiter这个节点已经取消等待了呗。
                doSignal(first);
        }

//----------------------------------------doSignal--------------------------------------
//从队友找到第一个加入阻塞队列的节点
//因为之前说过条件队列的节点取消放弃等待
 private void doSignal(Node first) {
            do {
                //将firstWaiter指向first后面一个节点,因为现在这个firstWaiter将要离开队列啦!
                if ( (firstWaiter = first.nextWaiter) == null)
                    //到这里说明如果firstWaiter离开之后条件队列都为空了,那么也lastWaiter指针也置为null啦
                    lastWaiter = null;
                //断开firstWaiter啦!
                first.nextWaiter = null;
            } while (!transferForSignal(first) && //这个while循环就是判断这个first指向的节点是否转移成功,如果返回false的话,那么就是转移不成功,也就是说取消了,那么就查询下一个节点。返回true就是说加入阻塞队列成功啦,那么这个函数就完成使命啦!
                     (first = firstWaiter) != null);
        }



//-----------------------------------------------transferForSignal---------------------
final boolean transferForSignal(Node node) {
       
   //这里之前说过加入条件队列的时候节点的waitStatus会初始化为Condition,如果这里CAS更新失败,说明状态不为Condition,就说明取消了呗。那么返回false,继续寻找下一个想加入阻塞队列的节点。
    //如果更新成功就把节点的ws设置为0,为初始态,就是为了加入阻塞队列。
        if (!compareAndSetWaitStatus(node, Node.CONDITION, 0))
            return false;
		
    //到达这里说明CAS成功,ws也为0,那么说明就可以自旋进入阻塞队列啦!
        Node p = enq(node);//返回加入阻塞队列后的前驱节点。
        int ws = p.waitStatus;
    	//这里是根据前驱节点的状态,如果ws>0,说明就是取消等待啦
    	// 如果ws < 0,就是说该节点没有取消等待进入阻塞队列。就先把加入阻塞队列的节点的ws设置为SIGNAL,这个就不多说啦,具体看上一篇文章即可!
        if (ws > 0 || !compareAndSetWaitStatus(p, ws, Node.SIGNAL))
            //到这里说明节点要么取消,要么CAS想要加入阻塞队列的节点的状态失败,那么就先唤醒,为啥要唤醒呢?后面讲!
            LockSupport.unpark(node.thread);
      	// 不管有没有执行上一个if语句,都说明进入阻塞队列已经成功啦!
        return true;
    }

检查中断状态

在signal之后,线程所代表的node节点肯定已经加入到阻塞队列中啦!然后就准备去获取锁。

之前不是说到线程已经挂起了吗?signal之后或者被中断就已经唤醒啦

int interruptMode = 0;
while (!isOnSyncQueue(node)) {
    // 线程挂起
    LockSupport.park(this);

    if ((interruptMode = checkInterruptWhileWaiting(node)) != 0)
        break;
}

有以下几种情况会让线程从LockSupport.park(this);这步往下走

  1. signal之后进入阻塞队列,等待前驱节点释放锁,释放锁的时候就会调用 LockSupport.unPark(node.thread),也就是被唤醒啦!
  2. 当线程在park的时候,有其他线程对它进行了中断。
  3. 在signal的时候,进行过进队操作,但是前驱节点已经取消等待了或者CAS前驱节点的状态为SIGNAL也失败
  4. 假唤醒。这个也是存在的,和 Object.wait() 类似,都有这个问题

线程被唤醒之后,第一步就是执行checkInterruptWhileWaiting(node)这个函数啦,如果返回非0,就是说await的线程在park期间或者说signal之后(unpark之后)被中断过,所以就要区分到底是signal之前中断还是signal之后中断。

如果返回0,那么就是说线程在park的时候,没有被中断,被unpark就是在阻塞队列正常被唤醒的!


checkInterruptWhileWaiting返回的值

  1. 如果在signal之前已经进行中断,那么返回THROW_IE -1
  2. 如果在signal之后已经进行中断,那么返回REINTERRUPT 1
  3. 如果返回0,那么表示在park期间没有进行中断
 private int checkInterruptWhileWaiting(Node node) {
            return Thread.interrupted() ?
                (transferAfterCancelledWait(node) ? THROW_IE : REINTERRUPT) :
                0;
        }

如何区分signal之前中断还是之后中断

主要在transferAfterCancelledWait这个方法里,我们下面来看一下它的代码

final boolean transferAfterCancelledWait(Node node) {
        if (compareAndSetWaitStatus(node, Node.CONDITION, 0)) {
            //如果进行到这里,那么说明是signal之前就被中断的。因为signal的时候,会把await在条件队列的线程的waitStatus置为0,if判断里面的那个CAS操作就会失败了。所以就说明如果到这里,那么肯定还在条件对了,并且没有被signal
            enq(node);//从条件队列进入阻塞队列,注意这里的nextWaiter并没有置位空,如果后面还有节点,那么也会一起带去阻塞队列
            return true;
        }
        /*
         * If we lost out to a signal(), then we can't proceed
         * until it finishes its enq().  Cancelling during an
         * incomplete transfer is both rare and transient, so just
         * spin.
         */
    	//到达这里说明CAS失败,有两种情况
    	// 1. 是已经signal完成,已经把节点移到阻塞队列中了,就不会进入下面那个while循环
    	// 2. 还没有完全转移到阻塞队列中,那么就进入while循坏咯,自旋等待,直到进入阻塞队列为止,但是这种情况如翻译所示,是非常罕见和稀少的
        while (!isOnSyncQueue(node))
            Thread.yield();
        return false;

所以经过上面的分析,只要是某个线程被中断,那么不管这个线程所代表的node节点是不是firstWaiter,也就是是不是会被signal,都会被唤醒,然后进入阻塞队列。

获取独占锁

我们回到await函数,在上面的while退出之后,也就是我们的节点不管是被signal也好还是被中断也好,都已经进入到阻塞队列了,这点是毋庸置疑的。进入阻塞队列后干嘛呢?当然是为了获取锁啦,那么如何获取锁呢?还记得上一节我们讲的进入阻塞队列之后如何获取锁么?如果不记得就去看看吧!这里放出连接

// acquireQueued上节已经分析过,不再缀诉。这里判断中断是不是signal之后中断的
//如果是signal前的,到后面就直接抛出异常,不会进行这一步。
//如果是signal之后,但是在阻塞队列等待的时候被中断了,也就是说acquireQueued的时候被中断过。前面退出while循环的时候可能是没有中断退出(interruptMode == 0),也可能是中断退出,只要acquireQueued的时候被中断过,并且是signal之后,都要重新设置下interruptMode,这里读者可以好好捋一下!
if (acquireQueued(node, savedState) && interruptMode != THROW_IE) 
                interruptMode = REINTERRUPT;
if (node.nextWaiter != null) // clean up if cancelled
                //如果执行到这里,那么就是说是这个线程时被中断加入阻塞队列的,不是通过signal加入的,因为signal的话的nextWaiter早就已经被设置为null啦!
                unlinkCancelledWaiters();
           
 if (interruptMode != 0) // 如果到这里肯定是被中断啦,管你是signal之前还是之后
     reportInterruptAfterWait(interruptMode);


//-----------------reportInterruptAfterWait------------------------------------------------------+
 private void reportInterruptAfterWait(int interruptMode)
            throws InterruptedException {
            if (interruptMode == THROW_IE) //就是这里,如果signal之前就被中断,抛出异常!!
                throw new InterruptedException();
            else if (interruptMode == REINTERRUPT) //如果是signal之后中断,那么就设置下标志位就好啊!让开发者自己去写外层逻辑去检测!
                selfInterrupt();
        }


//---------------------------selfInterrupt------------------------------------
static void selfInterrupt() {
        Thread.currentThread().interrupt();
    }

AQS 独占锁的取消排队

下面我们来分析下,如何取消锁之间的竞争,当有几个线程想竞争某个锁的时候,我们希望有一个线程不去竞争这个锁了。

在第一篇文章中我们用的lock,如果有中断是不会抛出异常的,只是标记一下状态而已,具体的由外层函数决定。

在ReentrantLock中,有这样的一个lock方法,可以检测到中断并且抛出异常。

public void lockInterruptibly() throws InterruptedException {
        sync.acquireInterruptibly(1);
    }
//------------------------------------------------------------
public final void acquireInterruptibly(int arg)
            throws InterruptedException {
        if (Thread.interrupted())
            throw new InterruptedException();  //如果还没开始竞争就中断,也会抛出异常返回
        if (!tryAcquire(arg))
            doAcquireInterruptibly(arg);
    }

//-------------------------------doAcquireInterruptibly--------------------------------
 private void doAcquireInterruptibly(int arg)
        throws InterruptedException {
        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;
                }
                if (shouldParkAfterFailedAcquire(p, node) &&
                    parkAndCheckInterrupt())
                 // 就是这里,一旦异常,马上结束这个方法,抛出异常。
                // 这里不再只是标记这个方法的返回值代表中断状态
                // 而是直接抛出异常,而且外层也不捕获,一直往外抛到 lockInterruptibly,
                    throw new InterruptedException();
            }
        } finally {
            if (failed)
                cancelAcquire(node);
        }
    }

上面我们看到,acquireInterruptibly里面的doAcquireInterruptibly在竞争锁的时候,一旦其他线程对其产生了中断,那么这个线程就马上结束,不再去竞争。如果是acquired的话,如果在竞争锁期间其他线程对其产生中断,那么先先抢得锁再说,中断后面再处理!这就是他们的区别啦!

总结

  1. 分析ReentrantLock公平锁和非公平锁的源码,理解其中的区别。
  2. 引入条件队列,并且和阻塞队列进行比较,分析他们的关系
  3. 对Condition的底层代码进行了部分的分析,主要是Node节点的await和signal的转换以及如何处理中断的问题
  4. 对AQS消除锁竞争的两种方式进行了源码分析,理解二者的不同

通过写这篇博客,对AQS的源码有了进一步的了解,本文主要花了大量的篇幅去写ConditionObject,主要是为了弄明白Node节点在条件队列和阻塞队列的转换的过程,同时自己由于之前对中断不是很熟悉,所以补了一些知识,起码比之前熟悉了一点,也算是一点小进步吧!后面会继续了解AQS,下次见!