ConcurrentLinkedQueue 源码解读
一、介绍ConcurrentLinkedQueue 是一个基于链接节点的无界线程安全队列,它采用先进先出的规则对节点进行排序,当我们添加一个元素的时候,它会添加到队列的尾部;当我们获取一个元素时,它会返回队列头部的元素。 ConcurrentLinkedQueue 采用非阻塞的方式实现线程安全队列,它采用了"wait-free"算法(即CAS算法)来实现。 ConcurrentLinkedQueue 由 head 节点和 tail 节点组成,每个节点(Node)由节点元素(item)和指向下一个节点(next)的引用组成,节点与节点之间就是通过这个 next 关联起来,从而组成一张链表结构的队列。默认情况下head节点存储的元素为 null,tail 节点等于 head 节点。 二、源码解读现在我们有了 head 和 tail 节点,如果按照我们平常的思维,head 节点即头节点,tail 节点即尾节点。那么入队列的时候,将 tail 的 next 节点设置为 newNode,将 newNode 设置为 tail;出队列的时候,将 head 节点元素返回,head 的 next 节点设置为 head。实现代码如下: public boolean offer(E e) { if (e == null) throw new NullPointerException(); Node<E> n = new Node<E>(e); for (; ; ) { Node<E> t = tail; if (t.casNext(null,n) && casTail(t,n)) { return true; } } } 不要怀疑你的思维,这样的做法完全是可行的。 这样的做法 tail 节点永远作为队列的尾节点,head 节点永远为队列的头节点。实现代码量非常少,而且逻辑清晰和易懂。但是,这么做有个缺点,每次都需要使用循环 CAS 更新 tail 节点。所以 doug lea 为了减少 CAS 更新 tail 节点的次数,提高入队的效率,使用增加循环来控制 tail 节点的更新频率,并不是每次节点入队后都将 tail 节点更新成尾节点,而是当 tail 节点和尾节点不一致时(也就是循环两次)才更新 tail 节点。如下图: 想要读懂 ConcurrentLinkedQueue 的源码,最好先搞懂以下特质:
- 入队列public boolean offer(E e) { // 1. checkNotNull(e); final Node<E> newNode = new Node<E>(e); for (Node<E> t = tail,p = t;;) { Node<E> q = p.next; // 2. if (q == null) { // 3. if (p.casNext(null,newNode)) { // 4. if (p != t) casTail(t,newNode); return true; } } // 5. else if (p == q) p = (t != (t = tail)) ? t : head; else // 6. p = (p != t && t != (t = tail)) ? t : q; } }
- 出队列public E poll() { restartFromHead: for (;;) { // 1. for (Node<E> h = head,p = h,q;;) { E item = p.item; // 2. if (item != null && p.casItem(item,null)) { // 3. if (p != h) updateHead(h,((q = p.next) != null) ? q : p); return item; } // 4. else if ((q = p.next) == null) { updateHead(h,p); return null; } // 5. else if (p == q) continue restartFromHead; // 6. else p = q; } } }
三、API 使用
(编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |