AQS及其原理

AQS

AQS即AbstractQueuedSynchronizer，是用来构建锁和同步器的基础框架，它使用了一个原子变量state表示同步状态，通过内置的FIFO队列来完成资源获取线程的排队工作。

AQS的设计基于模板方法模式，简化了锁的实现方式，屏蔽了同步状态管理、线程的排队等底层操作，自定义同步组件只需要继承并重写指定的方法，并调用其提供的模板方法。

模板方法：定义一个操作中的算法骨架，而将算法的一些步骤延迟到子类中，使得子类可以不改变该算法结构的情况下重定义该算法的某些特定步骤

public abstract class AbstractQueuedSynchronizer{
  //同步状态
  private volatile int state;
  //提供了3个方法(getState、setState、compareAndSetState)来访问或修改同步状态，保证状态的改变是安全的
  //获取当前同步状态
  protected final int getState() {
    return state;
  }
    //设置当前同步状态
    protected final void setState(int newState) {
    state = newState;
  }
  //使用CAS设置当前状态（这个方法能保证状态设置的原子性）
  protected final boolean compareAndSetState(int expect, int update) {
    return U.compareAndSwapInt(this, STATE, expect, update);
  }
}

CLH队列锁（重点）

CLH队列锁是一种基于链表的可扩展性、高性能、公平的自旋锁。申请线程仅在本地变量上自旋，它不断轮询前驱的状态，发现前驱释放了锁就结束自旋。

CLH队列锁.png

当一个线程需要获取锁时，会创建一个新的QNode，将其中的locked设置为true表示需要获取锁，然后线程对tail域调用getAndSet方法使自己成为队列的尾部，同时获取一个指向其前驱结点的引用myPred，然后该线程就在前驱结点的locked字段上旋转，直到前驱结点释放锁。当一个线程需要释放锁时，将当前结点的locked设置为false，同时回收前驱结点。

CLH队列锁的优点是空间复杂度低（n个线程，L个锁，每个线程每次只获取一把锁，那么存储空间复杂度是O(L+n)，n个线程有n个Node，L个锁有L个tail）

AQS就是基于CLH队列锁来完成同步状态的管理的

//独占锁下获取资源
public final void acquire(int arg) {
  if (!tryAcquire(arg) &&
      acquireQueued(addWaiter(Node.EXCLUSIVE), arg))
    selfInterrupt();
}

acquire(int arg)是模板方法，独占式获取同步状态，首先会先调用tryAcquire(arg)（具体由子类实现）尝试获取资源，如果获取成功，直接返回；如果没有获取到资源，就会执行acquireQueued(addWaiter(Node.EXCLUSIVE), arg))，addWaiter顾名思义就是将结点添加到等待队列，我们看下acquireQueued方法：

final boolean acquireQueued(final Node node, int arg) {
  try {
    boolean interrupted = false;
    //不断自旋
    for (;;) {
      //拿到node的上一个结点
      final Node p = node.predecessor();
      //如果前置结点为head，说明可以尝试获取资源
      if (p == head && tryAcquire(arg)) {
        //获取成功后更新head结点
        setHead(node);
        p.next = null; // help GC
        return interrupted;
      }
      //尝试拿锁失败，根据条件进行park（使用CPU指令停止自旋，进入阻塞状态）
      if (shouldParkAfterFailedAcquire(p, node) &&
          parkAndCheckInterrupt())
        interrupted = true;
    }
  } catch (Throwable t) {
    cancelAcquire(node);
    throw t;
  }
}

ReentrantLock之可重入锁、公平锁、非公平锁分析

可重入锁：指的是任意线程在获取锁之后还能够再次获取该锁而不会被锁所阻塞

• 线程再次获取锁，需要判断占据锁的线程是否为当前线程，如果是则再次成功获取
• 锁的最终释放，线程重复获取锁计数自增，释放锁计算自减，当计数为0表示锁已经完全释放成功

公平锁：多个线程按照申请锁的顺序去获取锁，线程会直接进入队列去排队，永远都是队列的第一位才能获得锁

• 优点：所有线程都能得到资源，不会饿死在队列中
• 缺点：队列中除了第一个线程，其它线程都会阻塞，CPU唤醒阻塞线程开销大

非公平锁：线程去获取锁的时候，会直接取尝试获取，获取不到再进入等待队列

• 优点：CPU唤醒线程的数量会减少，可以减少CPU唤醒线程的开销
• 缺点：可能导致队列中的线程长时间获取不到锁，导致饿死

public class ReentrantLock implements Lock, java.io.Serializable {
  //静态内部类的方式继承AQS（推荐方式）
  abstract static class Sync extends AbstractQueuedSynchronizer {
    
    final boolean nonfairTryAcquire(int acquires) {
      final Thread current = Thread.currentThread();
      //ReentrantLock中state记录锁次数
      int c = getState();
      //state为0表示当前没有线程占用锁
      if (c == 0) {
            //CAS设置state状态
        if (compareAndSetState(0, acquires)) {
          setExclusiveOwnerThread(current);
          return true;
        }
      }
      //如果有线程占用锁，判断持是当前线程占有锁，那么就重入操作
      else if (current == getExclusiveOwnerThread()) {
        //重入一次则state++
        int nextc = c + acquires;
        if (nextc < 0) // overflow
          throw new Error("Maximum lock count exceeded");
        //设置state
        setState(nextc);
        return true;
      }
      return false;
    }
    
    protected final boolean tryRelease(int releases) {
      //释放一次则state--
      int c = getState() - releases;
      //如果当前线程不是占有锁的线程，不允许释放
      if (Thread.currentThread() != getExclusiveOwnerThread())
        throw new IllegalMonitorStateException();
      boolean free = false;
      //如果state为0，那么将锁的占用线程清理掉，最终返回true，表示你完全释放了
      if (c == 0) {
        free = true;
        setExclusiveOwnerThread(null);
      }
            
      setState(c);
      return free;
    }
  }
  //非公平锁
  static final class NonfairSync extends Sync {
    final void lock() {
      if (compareAndSetState(0, 1))
        setExclusiveOwnerThread(Thread.currentThread());
      else
        acquire(1);
    }
        //查询当前状态并判断同步状态是否符合预期，然后再进行CAS设置同步状态
    protected final boolean tryAcquire(int acquires) {
      return nonfairTryAcquire(acquires);
    }
  }
  //公平锁
  static final class FairSync extends Sync {
    final void lock() {
      acquire(1);
    }
    protected final boolean tryAcquire(int acquires) {
      final Thread current = Thread.currentThread();
      int c = getState();
      if (c == 0) {
        //与非公平锁多了!hasQueuedPredecessors()，保证线程按照顺序获取锁
        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;
    }
  }
  //默认构造函数，默认创建非公平锁
  public ReentrantLock() {
    sync = new NonfairSync();
  }
  //有参构造，传入true创建公平锁
  public ReentrantLock(boolean fair) {
    sync = fair ? new FairSync() : new NonfairSync();
  }
}

可以看到，对于非公平锁，只要CAS设置同步状态成功，则表示当前线程获取了锁；公平锁唯一的不同是多了hasQueuedPredecessors()方法的判断，如果head的next结点对应的线程不是当前线程，那么当前线程不能尝试获取锁，这样才能保证所有线程按照顺序公平的获取锁。