`
淘气天空lc
  • 浏览: 47938 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

Non-Blocking and Blocking Concurrent Queue Algorithm 高效的非阻塞队列实现

 
阅读更多
import java.util.concurrent.atomic.AtomicReferenceFieldUpdater;

/**
 * Created by luochao on 14-1-4.
 */
public class ConcurrentQueue<Content> {
    private volatile Node<Content> head;
    private volatile Node<Content> tail;
    private final static AtomicReferenceFieldUpdater<ConcurrentQueue,Node> HEAD_UPDATER = AtomicReferenceFieldUpdater.newUpdater(ConcurrentQueue.class,Node.class,"head");
    private final static AtomicReferenceFieldUpdater<ConcurrentQueue,Node> TAIL_UPDATER= AtomicReferenceFieldUpdater.newUpdater(ConcurrentQueue.class,Node.class,"tail");
    private  boolean casHead(final Node<Content> expect,final Node<Content> update){
       return HEAD_UPDATER.compareAndSet(this,expect,update);
    }
    private boolean casTail(final Node<Content> expect,final Node<Content> update){
        return TAIL_UPDATER.compareAndSet(this,expect,update);
    }
    public ConcurrentQueue(){
        Node node = new Node(null,null);
        this.head = node;
        this.tail = node;

    }
    public void enqueue(Content content){
        Node newNode = new Node(null,content);
        while (true){
            Node t = tail;
            Node next = t.next;
            if(t == tail){//判断tail是否被修改 已经next一致性
                if(next == null){ //从队列末尾入列
                   if(t.casNext(null, newNode)){
                     casTail(tail,newNode);
                     return;
                   }
                }else {
                   casTail(tail,next);
                }
            }

        }
    }
    public boolean dequeue(Content content){
        Node h = head;
        Node t = tail;
        Node next = h.next;
        while (true){
            if(h == head){//double check 检查head是否一致
               if(h == t){//判断是否为空队列 Is queue empty or Tail falling behind?
                  if (next == null){
                      return false;
                  }
                  //Tail is falling behind. Try to advance it
                  casTail(t,next);
                  return true;
               }else{
                   if (casHead(h,next)){
                       return true;
                   }
               }
            }
        }

    }
    private static class Node<Content>{
            volatile Node next;
            Content value;

            Node(Node next, Content value) {
                this.next = next;
                this.value = value;
            }
            private  boolean casNext(Node<Content> expect,Node<Content> update){
                return NEXTUPDATE.compareAndSet(this,expect,update);
            }
            //字段更新器 param 1 字段所在类  2 更新字段的值 3 字段名称 基于cas
            private static final AtomicReferenceFieldUpdater<Node,Node> NEXTUPDATE =
                    AtomicReferenceFieldUpdater.newUpdater(Node.class,Node.class,"next");

    }
}

  Simple, Fast, and Practical Non-Blocking and Blocking  Concurrent Queue Algorithms

 refer:http://www.cs.rochester.edu/u/michael/PODC96.html

分享到:
评论

相关推荐

    non-blocking socket

    在现代网络编程中,非阻塞套接字(non-blocking socket)和多路复用(multiplexing)是处理高并发连接的关键技术之一。这些技术能够帮助服务器高效地管理多个客户端连接,避免因等待某个操作完成而浪费资源。本文将...

    Fast Portable non-blocking network programming with Libevent

    《Fast Portable non-blocking network programming with Libevent》是一本关于Libevent库的书籍,它专注于指导读者如何使用Libevent 2.0或更高版本来编写快速、可移植且支持异步I/O的网络程序。本书的作者是Nick ...

    Asynchronous, non-blocking SAP NW RFC SDK bindings for Nod.zip

    标题中的"Asynchronous, non-blocking SAP NW RFC SDK bindings for Node"是指为Node.js开发的一个库,它提供了异步、非阻塞的方式与SAP NetWeaver RFC SDK进行交互。SAP NetWeaver RFC SDK是SAP提供的一套软件开发...

    tomcat-8.0.21

    2.默认http与ajp请求实现non-blocking技术,即NIO技术。 3.多个应用发布的时候可以先打成jar包,然后打成一个总的war发布。(这句翻译不太准,意思大概是这样子的) 4.默认支持应用工程字符集为UFT-8 5.提升了日志...

    Asynchronous, non-blocking SAP NW RFC SDK bindings for Pyt.zip

    标题中的"Asynchronous, non-blocking SAP NW RFC SDK bindings for Pyt" 指的是一种Python库,它提供了异步、非阻塞的接口来与SAP NetWeaver RFC(远程功能调用)SDK交互。SAP NW RFC SDK是SAP提供的一套开发工具,...

    Ultralow-crosstalk, strictly non-blocking microring-based optical switch

    The switch fabric delivers strictly non-blocking connectivity while completely canceling the first-order crosstalk. The 4×4 switching circuit consists of eight silicon microring-based spatial (de-)...

    let-prove-blocking-queue:以多种方式证明阻塞队列的死锁状态

    "let-prove-blocking-queue"项目显然旨在通过多种方法分析和证明阻塞队列的死锁状态。 死锁是并发编程中的一个重要问题,它通常涉及到四个条件:互斥、占有并等待、无剥夺和循环等待。在阻塞队列中,这四个条件可能...

    网络 switching with flooding 实验 和 UDP 使用例子(non-blocking sockets)

    experiments 里面包含运行实验的运行文件,先将其他八个程序打开之后最后打开 main client new 然后让其自动运行 结果会保存在一个.txt里面。 源代码 有main client new 和 一个关于随机数生成的头文件 和 子文件

    支持多线程和泛型的阻塞队列

    阻塞队列(Blocking Queue)是线程安全的数据结构,它结合了队列的先进先出(FIFO)原则和等待机制。当队列为空时,尝试获取元素的线程会被阻塞,直到队列中有新的元素;当队列满时,尝试插入元素的线程也会被阻塞,...

    spring-non-blocking-io:弹簧无阻塞

    用法下载仓库与mvn package一起mvn package 并使用java -jar target/spring-non-blocking-io-0.0.1-SNAPSHOT.jar 调用api并等待响应。这个怎么运作实例将在几秒钟内联机。 每次调用该服务时,一个简单的Thread.sleep...

    Non-Blocking-Driving-Program

    综上所述,"Non-Blocking-Driving-Program"是一个涉及C++异步编程的项目,通过非阻塞I/O技术来提升程序性能,实现高效的并发执行。在深入研究项目代码时,需要理解上述关键概念和工具的使用,以及如何将它们巧妙地...

    non-blocking-vs-blocking:一个演示示例,显示了非阻塞请求与阻塞请求之间的区别。 包括加特林负载测试

    Java中通过NIO(Non-blocking Input/Output)提供了对非阻塞I/O的支持,例如使用Selector和Channel等机制。 在Java中,非阻塞I/O的一个典型应用场景是网络编程,特别是服务器端。例如,使用Java NIO的...

    Nonblocking and blocking Assignments

    博主的博客Verilog之blocking & nonblocking assignments有些内容是参考了这篇英文文献的,其中对verilog中有关阻塞与非阻塞赋值语句的8种准则进行了详细的举例说明,读者可以下载文章进行详细阅读,以便更好地理解...

    阻塞队列(Blocking Queue)是一个支持两个附加操作的队列.txt

    阻塞队列是Java中并发编程的一个重要组件,它属于Java.util.concurrent包中的一部分。阻塞队列的主要特点在于它支持两个额外的条件操作:当队列为空时,尝试从队列中取元素的操作会被阻塞,直到队列中出现新的元素;...

    python 并发编程 非阻塞IO模型原理解析

    非阻塞IO(non-blocking IO) Linux下,可以通过设置socket使其变为non-blocking。当对一个non-blocking socket执行读操作时,流程是这个样子: 从图中可以看出,当用户进程发出read操作时,如果kernel中的数据还...

    Netpoll 是由 字节跳动 开发的高性能 NIO(Non-blocking IO) 网络库.rar

    扩展性: 提供了较多的扩展接口以及默认扩展实现,使用者也可以根据需要自行定制扩展,具体见下面的框架扩展。 多消息协议: RPC 消息协议默认支持 Thrift、Kitex Protobuf、gRPC。Thrift 支持 Buffered 和 Framed ...

    non-blocking-algorithms-java:Java非阻塞算法

    2. **非阻塞数据结构**:`ConcurrentHashMap`是Java中一个典型的非阻塞数据结构,它使用分段锁技术实现高效的并发读写。相比于传统的`synchronized HashMap`,`ConcurrentHashMap`在多线程环境下性能更优,因为它...

    网络IO模型:同步IO和异步IO,阻塞IO和非阻塞IO.pdf

    同步(synchronous) IO和异步(asynchronous) IO,阻塞(blocking) IO和非阻塞(non-blocking)IO分别是什么,到底有什么区别?这个问题其实不同的人给出的答案都可能不同,比如wiki,就认为asynchronous IO和non...

    Passive Event Listeners - 被动事件监听器1

    被动事件监听器(Passive Event ...Chrome浏览器会发出警告,提示开发者考虑使用被动事件监听器,以减少页面阻塞,提高用户体验。尽管这不影响代码的基本功能,但遵循这些最佳实践可以让你的Web应用更加高效和流畅。

    Blocking-Non-Blocking-IO-task2

    2. **非阻塞I/O(Non-Blocking I/O)** 非阻塞I/O模型允许线程在等待数据准备期间不被挂起,可以继续执行其他任务。在Java中,NIO(New IO)库提供了非阻塞I/O的支持。例如,`Selector`类可以监视多个通道,当数据...

Global site tag (gtag.js) - Google Analytics