学习ConcurrentLinkedQueue

简介: 原因:学习ConcurrentLinkedQueue是看到akka框架的默认邮箱是使用ConcurrentLinkedQueue实现的。   1. ConcurrentLinkedQueue在java.

 

原因:学习ConcurrentLinkedQueue是看到akka框架的默认邮箱是使用ConcurrentLinkedQueue实现的。

 

1. ConcurrentLinkedQueue在java.util.concurrent包中(java 版本是1.7.0_71),类间集成关系如下:

public class ConcurrentLinkedQueue<E> extends AbstractQueue<E>
        implements Queue<E>, java.io.Serializable

ConcurrentLinkedQueue继承了抽象类AbstractQueue,AbstractQueue抽象类中的几个实现方法也都是利用Queue接口中的方法实现的。

Queue接口中定义的抽象方法有:

package java.util;

public interface Queue<E> extends Collection<E> {

    // 向队列中插入元素e,不验证队列空间限制条件下插入一个元素。如果队列有剩余空间,直接插入;如果队列满了,就抛出IllegalStateException异常
    boolean add(E e);
    
    // 同样是向队列中插入元素e。如果队列有空间限制,同add;如果队列没有空间限制,比如ConcurrentLinkedQueue,总是可以插入进去
    boolean offer(E e);
    
    // 返回并删除队列头部的第一个元素,remove()与poll()方法的不同在于,如果队列为空,remove()方法会抛出异常,而poll()方法是返回null
    E remove();
    
    // 返回并删除队列头部的第一元素,如果队列空,返回null
    E poll();
    
    // 返回但是不删除队头元素,element()方法与peek()方法的不同在于,如果队列为空,element()方法会抛出NoSuchElementException,而peek()方法返回null
    E element();
    
    // 返回队头元素,如果队列为空,返回null
    E peek();
} 

队列的操作无非就是上述的插入和删除操作,从上述方法的定义来看,优先使用offer()和poll(),因为不抛异常的方法比较容易处理。

 

2. ConcurrentLinkedQueue是什么?

    ConcurrentLinkedQueue是基于链接节点实现的无界的线程安全的先进先出的非阻塞的队列。其链接节点的结构为:

    private static class Node<E> {
        volatile E item;
        volatile Node<E> next;
    }

   每一个链接节点(Node)包含节点元素(item)和指向下一个节点的引用(next)。ConcurrentLinkedQueue包含一个头结点和一个尾节点

    // 头结点,所有后继节点都可以从head开始,使用succ()方法访问到
private transient volatile Node<E> head; // 尾节点, private transient volatile Node<E> tail;

  头尾节点都提到了succ()方法,succ()方法是

    // sicc()方法是返回节点p的后继节点。如果节点p的后继节点指向自己,则返回头结点。这种情况是如何发生的?(节点p已经不在链表中了?)
    final Node<E> succ(Node<E> p) {
        Node<E> next = p.next;
        return (p == next) ? head : next;
    }

 succ()方法主要用途有什么?

   (1). 求队列大小  

    // 返回队列中元素个数,可以看到元素个数是int类型, 如果元素个数超过了Integer.MAX_VALUE的话,也只能返回Integer.MAX_VALUE
    // 另外,这个方法返回的值是不精确的。当然我们不是来看size()方法的,是来看succ()方法是如何使用的。
    public int size() {
        int count = 0; 
        // 从第一个节点开始遍历,如果节点不为null,统计节点个数,然后使用succ()方法获取下一个节点
        for (Node<E> p = first(); p != null; p = succ(p))
            if (p.item != null)
                // Collection.size() spec says to max out
                if (++count == Integer.MAX_VALUE)
                    break;
        return count;
    }

  

   (2). contains()方法中succ()的用法与求队列大小类似

    public boolean contains(Object o) {
        if (o == null) return false;
        for (Node<E> p = first(); p != null; p = succ(p)) {
            E item = p.item;
            if (item != null && o.equals(item))
                return true;
        }
        return false;
    }

  

3. ConcurrentLinkedQueue的构造函数为:

    public ConcurrentLinkedQueue() {
        head = tail = new Node<E>(null);
    }

 从构造函数看,ConcurrentLinkedQueue的头结点是包含null元素的一个节点,并且初始条件下head节点指向tail节点。

 接下来看下head和tail是如何在offer()和poll()方法中怎么使用的。

// 插入元素到队尾
public boolean offer(E e) {
  // 检查元素e是否为null,如果为null,抛出NullPointerException
  checkNotNull(e);
  // 创建新节点newNode
  final java.util.concurrent.ConcurrentLinkedQueue.Node<E>
      newNode = new java.util.concurrent.ConcurrentLinkedQueue.Node<E>(e);
  // 首先赋值tail给t (t = tail),赋值t给p (p = t)
  // 然后执行死循环for(;;)
  for (java.util.concurrent.ConcurrentLinkedQueue.Node<E> t = tail, p = t;;) {
    // 将p的next赋值给q, p.next -> q
    java.util.concurrent.ConcurrentLinkedQueue.Node<E> q = p.next;
    // 如果q为null,表示p是尾节点
    if (q == null) {
      // p是尾节点,将新节点newNode赋值给p的next,p.next -> e(newNode)
      // 这个赋值过程是使用CAS来实现的,CAS比较并交换,意思就是如果newNode != null,则交换他们
      if (p.casNext(null, newNode)) {
        // 如果p != t,即p != t = tail,表示t(= tail)不是尾节点
        if (p != t)
          // 将t置为尾节点,该操作允许失败,因此t(= tail)并不总是尾节点
          // 因此需要执行for(;;),先找到尾节点
          casTail(t, newNode);  // Failure is OK.
        return true;
      }
      // Lost CAS race to another thread; re-read next
    }
    else if (p == q)
      // 如果p == q, 说明尾节点tail已经不在链表中了,
      // 这种情况下,跳转到head,因为从head开始所有的节点都可达
      p = (t != (t = tail)) ? t : head;
    else
      // 如果p == q且q == null,p指向q,即p跳转到下一个元素
      p = (p != t && t != (t = tail)) ? t : q;
  }
}

  

public E poll() {
  // 跳出for(;;)循环的标志位
  restartFromHead:
  for (;;) {
    // 首先赋值head给h (h = head),赋值h给p (p = h),并定义变量q
    // 然后执行死循环for(;;)
    for (java.util.concurrent.ConcurrentLinkedQueue.Node<E> h = head, p = h, q;;) {
      // 获取p的元素值,即头节点的元素值
      E item = p.item;
      // 如果元素值不为null,并将p的元素置null
      // casItem(item, null)意思是如果item != null,则交换两者
      // 交换之后,item就从队列中被移除了
      if (item != null && p.casItem(item, null)) {
        if (p != h) // 如果p不是指向h (head),更新head的值
          updateHead(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;
      else
        p = q;
    }
  }
}

 

4. 生产者消费者使用ConcurrentLinkedQueue

import java.util.concurrent.ConcurrentLinkedQueue;

public class ProducerAndConsumer {
  private static ConcurrentLinkedQueue queue = new ConcurrentLinkedQueue();


  static class Producer extends Thread {
    String name;

    public Producer(String name) {
      this.name = name;
    }

    public void run() {
      for (int i = 0; i < 10; i++) {
        queue.offer(i);
        System.out.println(name + " : " + i);
        try {
          Thread.sleep(1 * 1000);
        } catch (InterruptedException e) {
          e.printStackTrace();
        }
      }
    }
  }


  static class Consumer extends Thread {
    String name;

    public Consumer(String name) {
      this.name = name;
    }

    public void run() {
      for (;;) {
        Object item = queue.poll();
        System.out.println(name + " : " + item);
        try {
          Thread.sleep(1 * 1000);
        } catch (InterruptedException e) {
          e.printStackTrace();
        }
      }
    }
  }

  public static void main(String[] args) {
    new Producer("p1").start();
    new Producer("p2").start();
    new Consumer("c1").start();
    // new Consumer("c2").start();
  }
}

  

 

目录
相关文章
|
JavaScript
|
11月前
|
前端开发 JavaScript
React Hooks 全面解析
【10月更文挑战第11天】React Hooks 是 React 16.8 引入的新特性,允许在函数组件中使用状态和其他 React 特性,简化了状态管理和生命周期管理。本文从基础概念入手,详细介绍了 `useState` 和 `useEffect` 的用法,探讨了常见问题和易错点,并提供了代码示例。通过学习本文,你将更好地理解和使用 Hooks,提升开发效率。
214 4
|
6月前
|
存储 人工智能 搜索推荐
Shandu:开源AI研究黑科技!自动挖掘多层级信息,智能生成结构化报告
Shandu 是一款开源的 AI 研究自动化工具,结合 LangChain 和 LangGraph 技术,能够自动化地进行多层次信息挖掘和分析,生成结构化的研究报告,适用于学术研究、市场分析和技术探索等多种场景。
555 8
Shandu:开源AI研究黑科技!自动挖掘多层级信息,智能生成结构化报告
|
负载均衡 NoSQL Java
聊聊 分布式 WebSocket 集群解决方案(一)
聊聊 分布式 WebSocket 集群解决方案
聊聊 分布式 WebSocket 集群解决方案(一)
|
存储 安全 编译器
C/C中sizeof和strlen函数的实现:详细解析sizeof和strlen函数的实现机制、参数说明和使用技巧
C/C中sizeof和strlen函数的实现:详细解析sizeof和strlen函数的实现机制、参数说明和使用技巧
298 1
|
存储 安全 Java
settings.xml详解(很详细读这一篇就够了)
settings.xml是Java项目中用于配置Maven的重要文件,它详细规定了Maven的运行规则和行为。该文件通常位于用户家目录下的.m2文件夹中,或者项目根目录下的.mvn文件夹内。settings.xml中包含了众多配置项,从代理设置、镜像仓库配置,到服务器认证信息、插件组等,均可以在此文件中进行细致定义。通过合理配置settings.xml,我们可以优化Maven的依赖下载速度,保障仓库访问的安全性,甚至实现私有仓库的搭建与管理。深入了解settings.xml的每一项配置,对于提高Maven使用效率、保障项目构建稳定性具有重要意义。因此,无论是Maven初学者还是资深用户,都应仔
14120 3
|
网络协议 安全 网络安全
【华为HCIP | 高级网络工程师】刷题日记(4)
【华为HCIP | 高级网络工程师】刷题日记(4)
965 0
|
JavaScript
在vue中,怎样理解 Vue 的单向数据流?
在vue中,怎样理解 Vue 的单向数据流?
132 5
|
安全 Java 大数据
一文搞懂什么是“注解”
一文搞懂什么是“注解”
553 0
一文搞懂什么是“注解”
|
Android开发 容器
Android viewpage 设定上一页下一页按钮
Viewpager,视图翻页工具,提供了多页面切换的效果。Android 3.0后引入的一个UI控件,位于v4包中。低版本使用需要导入v4包,但是现在我们开发的APP一般不再兼容3.0及以下的系统版本,另外现在大多数使用Android studio进行开发,默认导入v7包,v7包含了v4,所以不用导包,越来越方便了。
Android viewpage 设定上一页下一页按钮

热门文章

最新文章