`
aigo
  • 浏览: 2635166 次
  • 性别: Icon_minigender_1
  • 来自: 宜昌
社区版块
存档分类
最新评论

java中的无锁队列:ConcurrentLinkedQueue

阅读更多

java 1.5提供了一种无锁队列(wait-free/lock-free)ConcurrentLinkedQueue可支持多个生产者多个消费者线程的环境

http://docs.oracle.com/javase/1.5.0/docs/api/java/util/concurrent/ConcurrentLinkedQueue.html

 

下面这个是网上别人自己实现的一种无锁算法队列,原理和jdk官方的ConcurrentLinkedQueue相似:通过volatile关键字来保证数据唯一性(注:java的volatile和c++的volatile关键字是两码事!),但是里面又用到了atomic,感觉有点boost::lockfree::queue的风格,估计作者是参考了boost的代码来编写这个java无锁队列。

 

实现代码:

import java.util.concurrent.atomic.AtomicReference;

public class LockFreeQueue<T> {
    private static class Node<E> {
        E value;
        volatile Node<E> next;

        Node(E value) {
            this.value = value;
        }
    }

    private AtomicReference<Node<T>> head, tail;

    public LockFreeQueue() {
        // have both head and tail point to a dummy node
        Node<T> dummyNode = new Node<T>(null);
        head = new AtomicReference<Node<T>>(dummyNode);
        tail = new AtomicReference<Node<T>>(dummyNode);
    }

    /**
     * Puts an object at the end of the queue.
     */
    public void putObject(T value) {
        Node<T> newNode = new Node<T>(value);
        Node<T> prevTailNode = tail.getAndSet(newNode);
        prevTailNode.next = newNode;
    }

    /**
     * Gets an object from the beginning of the queue. The object is removed
     * from the queue. If there are no objects in the queue, returns null.
     */
    public T getObject() {
        Node<T> headNode, valueNode;

        // move head node to the next node using atomic semantics
        // as long as next node is not null
        do {
            headNode = head.get();
            valueNode = headNode.next;
            // try until the whole loop executes pseudo-atomically
            // (i.e. unaffected by modifications done by other threads)
        } while (valueNode != null && !head.compareAndSet(headNode, valueNode));

        T value = (valueNode != null ? valueNode.value : null);

        // release the value pointed to by head, keeping the head node dummy
        if (valueNode != null)
            valueNode.value = null;

        return value;
}

代码出处:

Is this (Lock-Free) Queue Implementation Thread-Safe?

http://stackoverflow.com/questions/1634368/is-this-lock-free-queue-implementation-thread-safe

 

分享到:
评论

相关推荐

    无锁队列

    在Java中,一个著名的无锁队列实现是`ConcurrentLinkedQueue`,它是Java并发包`java.util.concurrent`的一部分。这个队列基于循环队列的设计,利用了链表节点的CAS操作来实现元素的插入和移除。在`...

    Java concurrency集合之ConcurrentLinkedQueue_动力节点Java学院整理

    ConcurrentLinkedQueue是Java并发包`java.util.concurrent`下的一个类,它实现了`Queue`接口,并且是一个完全由原子操作构建的无锁队列。队列遵循FIFO(先进先出)原则,这意味着元素会按照它们被插入的顺序被取出。...

    ConcurrentLinkedQueue源码分析.rar

    首先,我们要明白`ConcurrentLinkedQueue`是Java并发包`java.util.concurrent`中的一个类,它实现了`Queue`接口,并且遵循FIFO(先进先出)原则。与传统的同步队列如`ArrayBlockingQueue`不同,`...

    Java很好的学习笔记4 无锁.md,学习代码

    5. 无锁数据结构:如无锁栈、队列的实现,如ConcurrentLinkedQueue和ConcurrentLinkedStack。 同时,"并发编程资料"目录下的其他文件,如"NET.md"、"ThreadLocal.md"、"TimeUnit.md"、"并发编程.pdf"、"并发编程_...

    聊聊并发(6)ConcurrentLinkedQueue的

    总结来说,`ConcurrentLinkedQueue`是Java并发库中的一个高效并发队列,其无锁的实现方式和FIFO特性使其在多线程环境下表现出色。理解并掌握其工作原理对于优化并发代码、提升系统性能具有重要意义。

    Java 并发核心编程

    3. **ConcurrentLinkedQueue**: 提供了一个基于链表的无界队列实现,适用于高并发场景。 #### 五、线程协作 线程之间的协作是多线程编程中的另一个关键方面,涉及到线程之间的通信和同步。Java提供了多种机制来...

    java并发编程实战源码,java并发编程实战pdf,Java

    10. **并发模式**:书中可能还会介绍生产者消费者模式、读写锁模式、双端队列模式等经典的并发设计模式,帮助开发者解决实际问题。 通过学习《Java并发编程实战》的源码,你可以更直观地了解这些概念如何在实际代码...

    关于Java_Collection_API_

    对于多线程环境下的队列操作,推荐使用`java.util.concurrent.ConcurrentLinkedQueue`类,该类采用无锁并发设计,能提供更好的性能。 综上所述,在实际开发过程中,开发者需要根据具体的应用场景选择合适的集合类,...

    Java容器.xmind

    container Collection 标记: 顶级接口 List 标记: interface ArrayList 标记: class ...ConcurrentLinkedQueue ...写有锁,读无锁,读写之间不阻塞...LinkedBlockingQueue 链表结构实现,无界队列(默认上限Integer.MAX_VALUE)

    [中文]Java并发编程的艺术pdf

    - **生产者-消费者模式**:使用`BlockingQueue`实现线程间的数据交换,生产者将数据放入队列,消费者从队列中取出数据。 - **工作窃取**:线程通过窃取其他线程的工作任务来提高并行性,如Fork/Join框架。 6. **...

    聊聊并发(5)原子操作的实现原理Java开发Java经验技

    2. 非阻塞数据结构:比如并发队列,如`ConcurrentLinkedQueue`,其内部就大量使用了原子类,实现了在不加锁的情况下保证数据的一致性。 3. 更新计数器:在统计类应用中,例如记录访问量、点击量等,原子类能够提供...

    深入浅出Java多线程.pdf

    - **ConcurrentLinkedQueue**:线程安全的链表队列,适用于大量线程并发的情况。 - **CopyOnWriteArrayList**:通过复制底层数组的方式实现写操作,适用于读多写少的场景。 **16. CopyOnWrite** - **CopyOnWrite ...

    java5 并发包 (concurrent)思维导图

    - `ConcurrentLinkedQueue`:无界并发队列,基于链接节点的无锁算法实现。 - `LinkedBlockingQueue`:基于链接节点的阻塞队列,适用于生产者-消费者模型。 - `CopyOnWriteArrayList`和`CopyOnWriteArraySet`:...

    java 面试题 集合

    Java集合框架是Java编程语言中的核心部分,它提供了一种高效、灵活的数据组织方式,使得开发者可以方便地存储和操作对象。在Java面试中,集合相关的知识点常常是考察的重点,因为它们涉及到数据结构、内存管理和多...

    java-concurrency:Java中的并发

    Java并发编程是Java开发中的一项核心技能,它涉及到如何在多线程环境下高效、安全地执行任务。在Java中,并发处理主要通过`java.util.concurrent`(JUC)框架实现,该框架提供了丰富的工具类和接口,使得开发者可以...

    java源码之并发编程

    4. **并发集合**:Java并发编程中,线程安全的集合类是非常重要的,例如`ConcurrentHashMap`、`CopyOnWriteArrayList`和`ConcurrentLinkedQueue`。这些集合类内部实现了锁分离或无锁算法,能在并发环境下提供高效且...

    java自带并发框架

    Java并发框架是Java JDK中内置的一系列用于处理多线程并行执行的工具和类库,自JDK 5.0引入以来,极大地简化了并发编程的复杂性。这个框架由Doug Lea设计,并在JSR-166任务中提出,最终在Tiger(JDK 5)版本中被引入...

    JAVA高并发包介绍

    它是Java并发包中一个线程安全的有序映射表,基于跳表(Skip List)的数据结构实现。ConcurrentSkipListMap通过一种分层的多级链表来维护其内部结构,这使得它在高并发环境下不仅能够保持良好的读写性能,同时还能...

    实战java高并发程序设计源码下载

    Java并发包(java.util.concurrent)中提供了一系列线程安全的集合类,如ConcurrentHashMap、CopyOnWriteArrayList和ConcurrentLinkedQueue等。这些集合在多线程环境下能保证数据的一致性和完整性。 五、线程池 ...

Global site tag (gtag.js) - Google Analytics