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 node
if (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;
}
}