论坛首页 Java企业应用论坛

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

浏览 3497 次
精华帖 (0) :: 良好帖 (1) :: 新手帖 (0) :: 隐藏帖 (0)
作者 正文
   发表时间:2011-09-01  
    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能考虑一下这个小小的发现......
   发表时间:2011-09-01  
我感觉你的分析有点模糊,最好是搞点实际的测试数据,用数据说话更有说服力。
0 请登录后投票
   发表时间:2011-09-01  
baoxin.zhangbx 写道
我感觉你的分析有点模糊,最好是搞点实际的测试数据,用数据说话更有说服力。

1.我讨论的是Doug Lea在设计节点入队的优缺点
2.要想保证成功进入CLH队列而不用悲观锁必须使用while(true)式的死循环才行(当然CAS成功就会跳出这个循环)
3.要想保证性能就要减少循环次数,循环里面无非完成两大步(经典入队的两大步),必须两个要同时成功才算成功,否则回滚(有点像事务),否则队列将处于不一致状态,这是Doug Lea的设计思路;而我的思路是可以让一次入队不保证事务的完整性:具体来说就是先跟最后一个节点互插(完成第一步),刷新尾指针(第二步)不要求完成,但是如果又来了一个节点要入队,他肯定会发现此时队列处于不一致状态(如贴图所示),那它第一件事肯定是把那个tail指针指向最新的尾节点呀,接下来的动作就跟前面那个节点入队一模一样了。
    Doug Lea是按照事务的完整性来设计的,我的是在保证不出错的前提下打破了事务完整性,性能肯定会压倒前者啊
0 请登录后投票
论坛首页 Java企业应用版

跳转论坛:
Global site tag (gtag.js) - Google Analytics