JAVA 1.7并发之LinkedTransferQueue原理理解

昨天刚看完BlockingQueue觉得好高级啊,今天扫到1.7就发现了升级版。。。。

如果对内容觉得不够充分,可以去看http://www.cs.rochester.edu/u/scott/papers/2009_Scherer_CACM_SSQ.pdf 

就是作者的论文啦,纯英文。。。比较难啃,但是我觉得逻辑上比看代码容易理解,其实代码什么u啊h啊看得很混

 

LinkedTransferQueue

 

起源: 我觉得是这样的,之前的BlockingQueue是对 读取 或者 写入 锁定整个队列,所以在比较繁忙的时候,各种锁比较耗时

而当时有一个SynchronizedQueue其实不能叫Queue,因为只能放一个物件,要么有一个物件在等人拿,要么有一个空等人放

根据这个原理,诞生了LinkedTransferQueue,利用CompareAndSwap进行一个无阻塞的队列,针对每一个操作进行处理样大家就不用抢得那么辛苦了

 

数据结构

在类的内部保持着一个栈,基本单位是node,根据 hasData区分里面有两种元素,要么是 Data 要么是 Reservation,不会同时存在

并且有一个变量head指向最前面的node,没东西则是null

Node

{

  isData    是不是数据,是的话item放具体东西

  item   如果不是数据则为null

  next   下一个节点

  waiter  如果不是数据则是reservation,有一个线程在等待

}

 

过程:

整个存取过程分成两部分

 1:MATCH(原节点,新节点)

for (;;) {                            // restart on append race

            for (Node h = head, p = h; p != null;) { // 如果头结点为空则跳过,非空进去找第一个可用节点
                boolean isData = p.isData;
                Object item = p.item;
                if (item != p && (item != null) == isData) { // 判断原节点可用性,如data的item应该是数值,如果是null则表明用过了
                    if (isData == haveData)   // 两个节点是相同类型,不用match了,去下一步
                        break;
                    if (p.casItem(item, e)) { // 节点不同类型,match成功,更改原节点item,表明不可用
                        for (Node q = p; q != h;) {//什么,我居然不是head节点了?我要让它指向我!
                            Node n = q.next;  // update by 2 unless singleton
                            if (head == h && casHead(h, n == null ? q : n)) {
                                h.forgetNext();
                                break;
                            }                 // advance and retry
                            if ((h = head)   == null ||
                                (q = h.next) == null || !q.isMatched())
                                break;        // unless slack < 2
                        }
                        LockSupport.unpark(p.waiter);//根据原节点的类型,reservation则叫人收货,data则叫null收货
                        return LinkedTransferQueue.<E>cast(item);//根据原节点的类型,reservation则返回null,data则返回数据
                    }
                }
                Node n = p.next;//下一个节点
                p = (p != n) ? n : (h = head); // Use head if p offlist
            }

  重点是找出第一个可用节点,如果是null则跳过,如果与进来的节点相同(本来就有data,还放data)也跳过,如果不同(本来是data,现在是reservation,返回data值 / 本来是reservation,现在是data,叫人来收货,返回reservation值=空)

 2:处理节点

if (how != NOW) {                 // No matches available
                if (s == null)
                    s = new Node(e, haveData);
                Node pred = tryAppend(s, haveData);//尝试添加新node
                if (pred == null)
                    continue retry;           // 不成功则重试整个过程
                if (how != ASYNC)
                    return awaitMatch(s, pred, e, (how == TIMED), nanos);//根据参数,等不等别人放数据,拿数据,等多久
            }
            return e; // not waiting

  MATCH失败了才会进入这个环节,把新节点放进栈内,并根据参数决定立刻返回或者等待返回

EXAMPLES

1:Head->Data    Input->Data

Match:      根据他们的属性 发现 cannot match ,因为是同类的

处理节点:   所以把新的data放在原来的data后面,然后head往后移一位,Reservation同理

HEAD=DATA->DATA

 

2:Head->Data    Input->Reservation  (取数据)

Match:      成功match,就把Data的item变为reservation的值(null,有主了),并且返回数据。

处理节点:  没动,head还在原地

HEAD=DATA(用过)

 

3:Head->Reservation  Input->Data(放数据)

Match:       成功match,就把Reservation的item变为Data的值(有主了),并且叫waiter来取

处理节点:  没动

HEAD=RESERVATION(用过)

 

总结:LinkedTransferQueue通过CAS尝试放入data或增加reservation。

消耗小于把整个队列锁掉,但是在并发特别高的情况下大家抢着尝试一样会影响速度

至于为什么跨过了1.6到1.7这个类才出现我觉得有点神奇

 

简单用法介绍------------------------------------------------------------------------------------------------------

存:

put();   放元素进去队列,注意队列是可以无限长的

add();   同上

transfer();  这个是重点,如果队列中有人发现有人在等,则直接给那个人(有一个参数waiter指定了在等的线程)

如果没人在等,就放进队列

取:

poll();  立即返回,如果没有元素就是空

take(); 如果没有元素,那就等

PS:最好是用poll然后自己处理空的状况,如果全是take然后又迟迟没有东西,那就一堆内存在等了。

 

 

JAVA 1.7并发之LinkedTransferQueue原理理解,古老的榕树,5-wow.com

郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。