因网站建设关闭的公告,网站上的验证码怎么做的,app公司,合肥瑶海区小学排名ConcurrentLinkedQueue的源码解析#xff08;基于JDK1.8#xff09;
ConcurrentLinkedQueue是Java集合框架中的一种线程安全的队列#xff0c;它是通过CAS#xff08;Compare and Swap#xff09;算法实现的并发队列。在并发场景下#xff0c;ConcurrentLinkedQueue能够…ConcurrentLinkedQueue的源码解析基于JDK1.8
ConcurrentLinkedQueue是Java集合框架中的一种线程安全的队列它是通过CASCompare and Swap算法实现的并发队列。在并发场景下ConcurrentLinkedQueue能够保证队列的线程安全性同时性能也很不错。
数据结构
ConcurrentLinkedQueue是基于链表实现的队列内部维护一个head节点和tail节点head和tail都是指向链表中的节点。
入队操作
ConcurrentLinkedQueue的入队操作通过CAS算法实现它的核心代码如下
public boolean offer(E e) {checkNotNull(e);final NodeE newNode new NodeE(e);for (NodeE t tail, p t;;) {NodeE 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 timecasTail(t, newNode); // Failure is OK.return true;}// Lost CAS race to another thread; re-read next}else if (p q)// 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;}
}
它的流程如下
首先创建一个新节点newNode。获取tail节点和tail节点的下一个节点p。如果p为空则说明当前节点p是队列中的最后一个节点这时候尝试通过CAS将新节点newNode插入到链表中。如果CAS操作成功则表示插入成功并且将tail指针指向新的节点newNode。如果CAS操作失败则说明有其他线程已经修改了tail指针需要重新获取tail指针。如果p不为空则需要判断p和tail是否指向同一个节点如果是则说明tail指针已经落后了需要重新获取tail指针。如果p和tail不是同一个节点则需要将p指向p的下一个节点。重复上述过程直到插入成功为止。
出队操作
ConcurrentLinkedQueue的出队操作也是通过CAS算法实现它的核心代码如下
public E poll() {restartFromHead:for (;;) {for (NodeE h head, p h, q;;) {E item p.item;if (item ! null p.casItem(item, null)) {// Successful CAS is the linearization point// for item to be removed from this queue.if (p ! h) // hop two nodes at a timeupdateHead(h, ((q p.next) ! null) ? q : p);return item;}else if ((q p.next) null) {updateHead(h, p);return null;}else if (p q)continue restartFromHead;elsep q;}}
}
它的流程如下
首先获取head节点和head节点的下一个节点p。如果p为空则说明队列为空直接返回null。如果p不为空则尝试通过CAS将p节点的元素item设置为null。如果CAS操作成功则表示当前节点p被成功出队并且返回出队的元素item。如果CAS操作失败则说明有其他线程已经修改了当前节点p的元素item需要重新获取head节点。如果p的下一个节点q为空则需要更新head节点为p并返回null。如果p和p的下一个节点q是同一个节点则说明head节点已经落后了需要重新获取head节点。如果p和p的下一个节点q不是同一个节点则将p指向q。重复上述过程直到出队成功为止。
总结
ConcurrentLinkedQueue是一种高效的并发队列它通过CAS算法实现了线程安全的入队和出队操作。在并发场景下ConcurrentLinkedQueue能够保证队列的线程安全性同时性能也很不错。因此在Java并发编程中ConcurrentLinkedQueue是一种常用的数据结构。
