关于Java并发包上AQS队列的一点点看法

关于Java并发包下AQS队列的一点点看法
    No-Blocking算法（简称NB）作为科研的主题已经有20年了，但直到1.5才被大量线上应用；
    我们第一次见到CAS估计都是从那个++引入的：用AtomicInteger和带synchronized关键字的++比看谁加到1000用的时间更少，于是凭借这个小小的volatile int变量我们也就达到了把锁的粒度降到最低、进而达到高并发的目的，然而如果没有CLH队列的保证n个线程疯抢一把对象锁也是很悲剧的。
    进队出队也需要CAS操作，但是没那么简单了.......昨天在看AbstractQueuedSynchronizer源码时发现了一个问题，特此拿出来讨论讨论：

private Node addWaiter(Node mode) {        Node node = new Node(Thread.currentThread(), mode);//构造代表入队线程的节点        Node pred = tail;//读取CLH队列最后一个节点（尾指针）        if (pred != null) {            node.prev = pred;//CLH是双向链表，但此步不足以入队//如果从行3到这里尾指针没被其他线程碰过就把尾指针指向入队的那个节点            if (compareAndSetTail(pred, node)) {                pred.next = node;//此步足以入队                return node;            }        }        enq(node);//如果能执行到这里我就有话要说了，且听下文分解        return node;    }

    如果哪个线程抢锁失败就不得不执行addWaiter方法了：排队吧~。

private Node enq(final Node node) {        for (;;) {            Node t = tail;//再次读取最后一个节点            if (t == null) { //当且仅当CLH是空的时候t才会为null                Node h = new Node(); //传说中的头结点（其实是个傀儡节点）                h.next = node;                node.prev = h;//入队的节点排在头结点之后                if (compareAndSetHead(h)) {                    tail = node;                    return h;                }            }            else {                node.prev = t;                if (compareAndSetTail(t, node)) {                    t.next = node;                    return t;                }            }        }    }

    当执行到13行的时候就是亮点了！为什么会执行到这里？因为CLH不为空，再进一步，上一段代码第7行CAS失败了，为什么失败了？因为有个手脚更快的线程抢先一步入队了，尾指针被改变了，这时候就必须把那个手脚快的节点作为尾节点来参照了，剩下的代码就跟上一段的功能一模一样了。
    先撇开Doug Lea的做法不说，要是让你设计插入到队尾怎么设计？当然是经典入队的方法：先把最后一个节点跟新的节点互插：

lastNode.next=newNode;newNode.pre=lastNode;

然后再让尾指针指向新来的节点；
但是我们看看Doug Lea是怎么搞的，他先在第一段代码的第7行判定能不能把尾指针指向新节点，第8行再把新节点和老节点互插，这看起来是不是有点别扭啊？
    根据我这几年的经验，别扭的流程一般都不会获得最速度的执行，我左思右想终于发现Doug Lea设计的缺陷了：一旦addWaiter方法第七行CAS失败那这个方法也就废了，所有任务都将抛给enq方法去执行，这段流程也就没有意义了，而且enq方法的设计是CAS使用的大忌：在while(true)这样的死循环里进行CAS比较，完全违背了建立CLH队列的初衷——防止线程的恶性竞争。
    对此我提出了一个淫蛋一点的方法：在最开始的时候，先作如下判断：

if(tail.next==null){...

可能这时候有人会喷我了，这个用判断吗？别急，如果此判断为true，那我就放心大胆的按常规思路先走第一步，新老节点互插，完成入队，接着尾指针指向新节点；如果为false，这就说明此队列处于不一致状态，那我就先把他置为一致状态再说，下面呈上代码：

public Node addWaiter(Node newNode) {        while (true) {            if (tail.next == null) {//看起来很“废”的判断                if (tail.next.CAS(null, newNode)) {//完成入队                    CAStail(tail, newNode);//刷新尾指针                    return newNode;                }            }else{                CAStail(tail,tail.next);//让队列回到一致状态            }        }}

如果看了上述代码仍不能理解不一致状态，那我就贴上图了
可能有人要问了，你这里不也是把CAS放到while(true)里面吗？没错，我是这么做了，但是我的这个粒度要比Doug Lea的小得多，他的addWaiter第七行在高并发情况下很容易失败，一旦失败就要全部重来(经典入队的两大步)，而我的至少能保证第一步很容易完成，第二步无需完成(刷新尾指针的任务其他线程可以智能地帮我完成)。
  jdk1.7已经发布了，我的发现注定赶不上这班车了，但我希望1.8能考虑一下这个小小的发现......

查看更多 下一篇