ConcurrentLinkedQueue
单向链表
无锁的,通过CAS来实现线程安全,不用切换线程上下文,但是再并发大的时候会导致线程一直自旋使CPU飙高
内部维护了一个head和一个tail两个node节点,其中再添加元素的时候tail节点不是每次添加玩都会去移动,是每入队两次tail才移动一次,这样减少了tail的移动次数,tail.next == null 那么tail就是真正的尾节点(如果tail直接指向尾节点的话因为设置tail是CAS操作,性能上不如两次移动一次)
public boolean offer(E e) {checkNotNull(e);final Node<E> newNode = new Node<E>(e);for (Node<E> t = tail, p = t;;) {Node<E> q = p.next;if (q == null) {// p is last nodeif (p.casNext(null, newNode)) {// Successful CAS is the linearization point// for e to become an element of this queue,// and for newNode to become "live".if (p != t) // hop two nodes at a time// 这里设置移动tail节点,第一次p == t 就不会设置tail节点casTail(t, newNode); // Failure is OK.return true;}// Lost CAS race to another thread; re-read next}else if (p == q) // p.next = p 并发下可能会p.next = p// We have fallen off list. If tail is unchanged, it// will also be off-list, in which case we need to// jump to head, from which all live nodes are always// reachable. Else the new tail is a better bet.p = (t != (t = tail)) ? t : head;else// Check for tail updates after two hops.p = (p != t && t != (t = tail)) ? t : q;}}
