AQS初探

1.AQS(AbstractQueuedSychronizer)简述

 1.AbstractQueuedSychronizer是java.util.concurrent包下同步器类的灵魂组件,很多同步组件都是基于它实现的,比如
   CountDownLatch、CyclicBarrier、ReentrantLock、ReentrantReadWriteLock和ConcurrentHashMap.
 2.同步工具类通用的核心的操做为(主要分为独占操作和共享操作):
    a.阻塞直到获取指定资源数
    b.可中断限时等待直到获取指定的资源数
    c.直接尝试获取指定资源数
    d.释放指定资源数

2.独占和共享的方法调用

AQS

说明: 图中分为左右两大矩形框,左边代表着独占访问的操作,右边代表着共享访问操作,其中小矩形框都代表AQS里面的方法.其中蓝色的小矩形
     框代表着AQS中默认已经实现了的方法,而红色小圆角矩形框代表着需要你自己去实现并覆盖的方法.箭头表示方法的调用次序.如果没有实现
     红色圆角矩形框的方法确间接调用了,将会抛出著名的UnsupportedOperationException异常.

3.CLH锁(自旋锁)简述

它使用队列的方式来解决n个线程来争夺m把锁的问题,每当一个新的线程需要获取锁,为其创建一个节点并放到队尾,如果该线程是队列中的第一个节点,
则节点的locked设置成false,如果不是队列的第一个节点,则它的节点的prev指向原来的队尾节点,并不断的自旋查看prev指向节点的locked属性,
如果该值变为false,那表示轮到它来尝试获取锁了.如果获取成功并最终用完释放后,则将自己的locked设置成false,如果获取失败则locked值不变,
还是true,并不断的尝试获取锁.

4.MSC锁(自旋锁)简述

MSC锁和CLH锁不同的是它对自己的节点的locked属性进行自旋,这意味着prev节点释放锁后需要去主动改变它的后继next的locked的状态.对比可以看出,
CLH用的是隐士的队列,因为节点不需要关心它的prev节点是谁,关心的只是prev节点的locked属性,而MSC需要主动通知next节点的locked属性.

5.AQS锁的设计

AQS参考了CLH锁的设计,但AQS没有采用CLH中的自旋来查看前驱(prev)节点的状态,因为在多核处理器的时代,对volatitle变量的自旋有可能是高代价的,
AQS提供了诸如共享锁、独占锁的获取和释放的语义,既然AQS的名称中就有队列关键字Queued,可见队列是其使用的核心数据结构之一.

6. AQS静态内部类Node类的属性

static final Node SHARED = new Node();
static final Node EXCLUSIVE =null;
volatitle int waitStatus;
volatitle Node prev;
volatitle Node next;
// Node上绑定的线程,由构造函数传入,用完后需要set null
volatitle Thread thread;
// 如果是独占模式,则nextWaiter指向的是下一个等待该条件的Node
// 如果是共享模式,则nextWaiter会被设置成一个特殊值:SHARED
Node nextWaiter;
// 通过nextWaiter的值来判断Node是出于独占模式还是共享模式
final boolean isShared(){
    return nextWaiter==SHARED;
}
说明:因为是双向链表,所以有prev和next,还有一个thread(用来记录该节点对应的线程),还有一个表示该节点的状态waitStatus,它有四种状态:
     a.SIGNAL,值为-1,表示当前节点的next节点需要获取资源数,也就是需要unpark
     b.CANCELLED,值为1,表示当前线程被取消
     c.CONDITION,值为-2,表示当前节点在等待condition,也就是在condition队列中
     d.PROPAGATE,值为-3,表示当前场景下后续的acquireShared能够执行
     e.0,新建的Node的状态都是0,表示初始状态

7.AQS中资源数

private volatitle int state;
说明:这里并没有使用AtomicInteger,而是使用了保证可见性却不保证一致性的volatitle关键字,这是为了减少对其他并发类AtomicInteger的依赖,
     所以在AQS中更新state字段和AtomicInteger中的语意是一样的,使用的都是unsafe.compareAndSwapInt.

8.共享下阻塞知道获取指定资源数分析

 1.从上面的独占和共享的方法调用图中可以看出,对应的是acquireShared方法
 2.acquireSharedInterruptibly和acquireShared的区别就是acquireSharedInterruptibly在操作之前会先去检查当前线程的中断标记,如果已经
    被中断了,则直接抛出InterruptedException,所以acquireSharedInterruptibly就比acquireShared多了如下两行代码:
            if(Thread.interrupted){
                throw new InterruptedException();
            }
 3.acquireShared内部实现:
    public final void acquireShared(int arg){
        if(tryAcquireShared(arg)<0){
            doAcquireShared(arg);
        }
    }
 4.tryAcquireShared就是我们自己需要实现的方法之一,如果返回值小于0,表示获取资源数失败.如果获取成功(返回值大于或等于0),该方法直接返回,如果
    获取失败(返回值小于0),则直接调用doAcquireShared方法.如果当前线程调用了获取资源数的阻塞方法,它会一直等,因为acquireShared即不会接受中
    断信号,也没有超时时间,它能做的事情就是“等待机会”.AQS中有两个Node类型的属性,用来指向头和尾队列:
    private transient volatitle Node head;
    private transient volatitle Node tail;
    每个由于获取资源数而被阻塞的线程都会“化身”成一个Node节点而被添加到这head和tail之间的队列中,这也是Node类中有个Thread类型的成员属性thread的原因.

##9.分析doAcquireShared方法条件:假设当前被阻塞的线程不止一个,也就是说该队列会有多个Node节点.就在这时,又一个线程threand-n(这里的n表示队列中已经被阻塞了n-1个线程,也就是说已经有n-1个Node节点了) 来通过调用acquireShared来以阻塞获取资源数,此时我们自定义实现的tryAcquireShared方法返回值小于0(因为真的没有可用的资源数,其他线程还未释放),所以进入到了 doAcquireShared方法中 doAcquireShared方法中几个大体的步骤: 步骤1.创建一个Node变量node-n,将node-n.thread指向线程thread-n,node-n.nextWaiter指向SHARED,node-n.waitStatus值为0; 步骤2.不断进行CAS(unsafe.compareAndSwapObject)操作,直到成功将node-n添加到队尾(如果head=tail,则会先创建一个Node作为头节点,使head和 tail同时指向该节点)即tail指向node-n.此时状态是原来的尾节点node-(n-1).next指向node-n,而node-n.prev指向node-(n-1),并且tail 指向新的尾节点node-n.之所以要不断的CAS,是因为有可能有多个线程在进行此操作; 步骤3.获取node-n的前一个节点,这里是node-(n-1).如果node-(n-1)是头节点(即head指向的节点),则将会再一次尝试获取资源数(调用tryAcquireShared), 如果成功(tryAcquireShared返回值大于等于0),则进入步骤4;如果获取资源数失败或者node-(n-1)根本就不是头节点,则进入步骤5 步骤4.将node-n设置成新的头节点,并将node-n.waitStatus设置成0,node-n.thread设置成null.从队尾开始向队头遍历,找到一个最接近队头的并且waiteStatus 是SIGNAL,CONDITION,PROPAGATE之一的Node,将其解除阻塞状态(LockSupport.unpark(s.thread);),最后结束整个调整; 步骤5.如果node-(n-1).waitStatus为0(新建的Node该值都是0),则尝试将其设置成SIGNAL(值为-1,设置成SIGNAL就相当于当前节点的next节点需要获取资源数,注意,这里也是通过一次CAS操作去设值,是否设值成功并不重要,重要的是至少有一个线程将其设置成功);如果node-(n-1).waitStatus为SIGNAL,则阻塞自己( LockSupport.park(this)),因为你的上游Node还没有获取到资源数,所以需要等待; 步骤6.不断重复步骤3-5,直到在步骤5中阻塞自己. ##10.分析doReleaseShared方法步骤1:通过head取得头节点node-0,如果node-0.waiteStatus为SIGNAL,则使用CAS尝试将node-0.waitStatus设置成0,如果成功则进入步骤2.如果node-0.waitStatus为0, 则通过CAS尝试将node-0.waitStatus设置成PROPAGATE,如果成功则退出,否则再进行第一步; 步骤2:获取node-0的下一个节点node-1,如果node-1.waitStatus不是CACELLED和0,则直接解放node-1的线程(LockSupport.unpark(s.thread)).否则从尾节点开始向节点 node-1遍历,找到最靠近节点node-1的且waitStatus不是CACELLED的节点node-x,如果存在node-x,则解放node-x的线程 ##11.doAcquireShared和doReleaseShared概述从上述获取资源数和释放资源数的步骤看出,1.能直接获取到资源的线程是不会进入队列中的;2.头节点要么是初始化时新建的空Node,要么是上一个已经获取到资源数后线程离开后的Node; 3.node-n“关心”的只是节点node-(n-1)的状态;4.如果node-x相比node-y更靠近head,且这两个node状态都是SIGNAL而且没有超时时间,那么node-x一定node-y先获取到资源数. ##12.通过如下步骤来观察AQS中队列的情况 ###12.1 步骤1 thread-a来获取8把锁,因为有10把,所以他成功了 state:10 当前可用state:2 head=tail=null ###12.2 步骤2 thread-b来获取5把锁,因为只剩2把,所以只能等待 AQS ###12.3 步骤3 thread-c来获取3把锁,因为只剩2把,所以只能等待 AQS ###12.4 步骤4 thread-d来获取2把锁,即使现在有2把可用的锁,但队列中thread-b和thread-c排在前面,所以thread-d也只能等 AQS ###12.5 步骤5 thread-a此时释放了5把锁,于是thread-b成功获取了这5把锁,thread-b的Node成为了新的头节点 AQS ###12.6 步骤6 thread-a和thread-b此时释放了所有的锁,于是thread-c和thread-d都成功获取到了锁,thread-b的Node成为了新的头节点 AQS