aqs

前提

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

公平锁和非公平锁

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

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

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

先看看公平锁的lock

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


 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;
        }

总结：

非公平锁在lock的时候，在tryAcquire函数里面会CAS获取state,如果恰好成功，那么就直接取得锁啦，不用进行下面的操作了
非公平锁在 CAS 失败后，和公平锁一样都会进入到 tryAcquire 方法，在 tryAcquire 方法中，如果发现锁这个时候被释放了（state == 0），非公平锁会直接 CAS 抢锁，但是公平锁会判断等待队列是否有线程处于等待状态，如果有则不去抢锁，乖乖排到后面。
非公平锁如果两次CAS都不成功，那么接下来的操作和公平锁一样啦！都要进入到阻塞队列等待唤醒。
非公平锁会有更好的性能，因为它的吞吐量比较大。当然，非公平锁让获取锁的时间变得更加不确定，可能会导致在阻塞队列中的线程长期处于饥饿状态。

生产者消费者模式

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

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）,这里先上图看两者的关系。

区别

阻塞队列和条件队列都是node节点，也就是Node的实例。因为条件队列的节点是需要转移到阻塞队列的。
ReentrantLock是可以创建多个Condition实例的，则这里会有condition1和condition2,并且ConditionObject中只有两个和节点有关的属性 firstWaiter和nextWaiter
每个Condition都有一个条件队列与之关联。当调用await()方法的时候，当先线程则会阻塞在当前地方，不会往下执行，然后将当前线程封装成Node节点，添加到条件队列的队尾。
调用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);这步往下走

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

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

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

checkInterruptWhileWaiting返回的值

如果在signal之前已经进行中断,那么返回THROW_IE -1

如果在signal之后已经进行中断,那么返回REINTERRUPT 1

如果返回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;

1
2
3

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的话，如果在竞争锁期间其他线程对其产生中断，那么先先抢得锁再说，中断后面再处理！这就是他们的区别啦！

总结

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

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

前提