`
maosheng
  • 浏览: 565038 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

Java 并发编程_ConcurrentLinkedQueue

    博客分类:
  • Java
 
阅读更多
ConcurrentLinkedQueue 的分析和使用:

在并发编程中我们有时候需要使用线程安全的队列。如果我们要实现一个线程安全的队列有两种实现方式一种是使用阻塞算法,另一种是使用非阻塞算法。使用阻塞算法的队列可以用一个锁(入队和出队用同一把锁)或两个锁(入队和出队用不同的锁)等方式来实现,而非阻塞的实现方式则可以使用循环 CAS 的方式来实现。


ConcurrentLinkedQueue 是一个基于链接节点的无界线程安全队列,它采用先进先出的规则对节点进行排序,当我们添加一个元素的时候,它会添加到队列的尾部,当我们获取一个元素,它会返回队列头部的元素。它采用了“wait-free”算法(即 CAS 算法)来实现。

ConcurrentLinkedQueue 的结构:






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

   ........

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

        /**
         * Constructs a new node.  Uses relaxed write because item can
         * only be seen after publication via casNext.
         */
        Node(E item) {
            UNSAFE.putObject(this, itemOffset, item);
        }

        boolean casItem(E cmp, E val) {
            return UNSAFE.compareAndSwapObject(this, itemOffset, cmp, val);
        }

        void lazySetNext(Node<E> val) {
            UNSAFE.putOrderedObject(this, nextOffset, val);
        }

        boolean casNext(Node<E> cmp, Node<E> val) {
            return UNSAFE.compareAndSwapObject(this, nextOffset, cmp, val);
        }

        // Unsafe mechanics

        private static final sun.misc.Unsafe UNSAFE;
        private static final long itemOffset;
        private static final long nextOffset;

        static {
            try {
                UNSAFE = sun.misc.Unsafe.getUnsafe();
                Class k = Node.class;
                itemOffset = UNSAFE.objectFieldOffset
                    (k.getDeclaredField("item"));
                nextOffset = UNSAFE.objectFieldOffset
                    (k.getDeclaredField("next"));
            } catch (Exception e) {
                throw new Error(e);
            }
        }
    }

    /**
     * A node from which the first live (non-deleted) node (if any)
     * can be reached in O(1) time.
     * Invariants:
     * - all live nodes are reachable from head via succ()
     * - head != null
     * - (tmp = head).next != tmp || tmp != head
     * Non-invariants:
     * - head.item may or may not be null.
     * - it is permitted for tail to lag behind head, that is, for tail
     *   to not be reachable from head!
     */
    private transient volatile Node<E> head;

    /**
     * A node from which the last node on list (that is, the unique
     * node with node.next == null) can be reached in O(1) time.
     * Invariants:
     * - the last node is always reachable from tail via succ()
     * - tail != null
     * Non-invariants:
     * - tail.item may or may not be null.
     * - it is permitted for tail to lag behind head, that is, for tail
     *   to not be reachable from head!
     * - tail.next may or may not be self-pointing to tail.
     */
    private transient volatile Node<E> tail;

   .......


}

ConcurrentLinkedQueue 由 head 节点和 tair 节点组成,每个节点(Node)由节点元素(item)和指向下一个节点的引用(next)组成,节点与节点之间就是通过这个 next 关联起来,从而组成一张链表结构的队列。默认情况下 head 节点存储的元素为空,tair 节点等于 head 节点。


入队列:

入队列就是将入队节点添加到队列的尾部。入队主要做两件事情,第一是将入队节点设置成当前队列尾节点的下一个节点。第二是更新 tail 节点,如果 tail 节点的 next 节点不为空,则将入队节点设置成 tail 节点,如果 tail 节点的 next 节点为空,则将入队节点设置成 tail的 next 节点,所以 tail 节点不总是尾节点。





步骤1 添加元素 1。队列更新 head 节点的 next 节点为元素 1 节点。又因为tail 节点默认情况下等于 head 节点,所以它们的 next 节点都指向元素 1 节点。
步骤2 添加元素 2。队列首先设置元素 1 节点的 next 节点为元素 2 节点,然后更新 tail 节点指向元素 2 节点。
步骤3 添加元素 3,设置 tail 节点的 next 节点为元素 3 节点。
步骤4 添加元素 4,设置元素 3 的 next 节点为元素 4 节点,然后将 tail 节点指向元素 4 节点。


    /**
     * Inserts the specified element at the tail of this queue.
     * As the queue is unbounded, this method will never return {@code false}.
     *
     * @return {@code true} (as specified by {@link Queue#offer})
     * @throws NullPointerException if the specified element is null
     */
    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
                        casTail(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;
        }
    }


    /**
     * Throws NullPointerException if argument is null.
     *
     * @param v the element
     */
    private static void checkNotNull(Object v) {
        if (v == null)
            throw new NullPointerException();
    }


定位尾节点:tail 节点并不总是尾节点,所以每次入队都必须先通过 tail 节点来找到尾节点,尾节点可能就是 tail 节点,也可能是 tail 节点的 next 节点。代码中循环体中的第一个 if 就是判断 tail是否有 next 节点,有则表示 next 节点可能是尾节点。获取 tail 节点的 next 节点需要注意的是 p 节点等于 p 的 next 节点的情况,只有一种可能就是 p 节点和 p 的 next 节点都等于空,表示这个队列刚初始化,正准备添加第一次节点,所以需要返回 head 节点。


设置入队节点为尾节点:p.casNext(null, n)方法用于将入队节点设置为当前队列尾节点的next 节点,p 如果是 null 表示 p 是当前队列的尾节点,如果不为 null 表示有其他线程更新了尾节点,则需要重新获取当前队列的尾节点。


出队列:

出队列的就是 从队列里返回一个节点元素,并清空该节点对元素的引用。




并不是每次出队时都更新 head 节点,当 head 节点里有元素时,直接弹出 head节点里的元素,而不会更新 head 节点。只有当 head 节点里没有元素时,出队操作才会更新head节点。这种做法也是通过 hops 变量来减少使用 CAS 更新 head 节点的消耗,从而提高出队效率。


public E poll() {
        restartFromHead:
        for (;;) {
            for (Node<E> 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 time
                        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;
            }
        }
    }



首先获取头节点的元素,然后判断头节点元素是否为空,如果为空,表示另外一个线程已经进行了一次出队操作将该节点的元素取走,如果不为空,则使用 CAS 的方式将头节点的引用设置成null,如果 CAS 成功,则直接返回头节点的元素,如果不成功,表示另外一个线程已经进行了一次出队操作更新了 head 节点,导致元素发生了变化,需要重新获取头节点。








  • 大小: 115.6 KB
  • 大小: 266.3 KB
  • 大小: 249.8 KB
分享到:
评论

相关推荐

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

    《Java并发编程实战》是Java并发编程领域的一本经典著作,它深入浅出地介绍了如何在Java平台上进行高效的多线程编程。这本书的源码提供了丰富的示例,可以帮助读者更好地理解书中的理论知识并将其应用到实际项目中。...

    java并发编程艺术

    并发集合是Java并发编程中的重要组成部分,如`ConcurrentHashMap`, `CopyOnWriteArrayList`, `ConcurrentLinkedQueue`等,它们设计为线程安全,能够在并发环境中高效地工作。书中的章节可能会详细解释这些集合的设计...

    Java并发编程:设计原则与模式(第二版)-3

    《Java并发编程:设计原则与模式(第二版)》是一本深入探讨Java多线程编程技术的权威著作。这本书详细阐述了在Java平台中进行高效并发处理的关键概念、设计原则和实用模式。以下是对该书内容的一些核心知识点的概述...

    Java 并发核心编程

    ### Java 并发核心编程知识点解析 #### 一、Java并发概述 自Java诞生之初,其设计者就赋予了该语言强大的并发处理能力。Java语言内置了对线程和锁的支持,这...理解和掌握这些概念和技术是成功进行并发编程的关键。

    java并发编程实战.zip

    《Java并发编程实战》这本书是Java开发者深入理解并发编程的重要参考资料。它涵盖了Java并发的核心概念、工具和最佳实践,旨在帮助读者在多线程环境中构建高效、可靠的系统。以下是本书涉及的一些关键知识点: 1. *...

    Java并发编程进阶练习代码

    本练习集专注于提升你在Java并发编程中的技巧,通过一系列逐步进阶的代码实例,帮助你掌握从基础到高级的并发概念。 首先,我们从“线程安全”开始。线程安全是指在多线程环境下,一个类或方法能够正确地处理并发...

    《Java 并发编程实战》.zip

    《Java 并发编程实战》是一本专注于Java并发编程领域的权威书籍,旨在帮助开发者深入理解和掌握在多线程环境中编写高效、安全且可维护的代码。这本书涵盖了Java并发编程的基础概念,高级特性以及最佳实践,是Java...

    java并发编程分享

    Java并发编程是Java开发中的重要领域,它涉及到多线程、同步机制、线程池以及并发集合等核心概念。在Java中,并发编程是提高系统性能和资源利用率的关键技术,尤其是在处理大量I/O操作或者计算密集型任务时。本文将...

    java并发编程

    Java并发编程是Java开发中的重要领域,涉及到多线程、同步机制、线程池等多个核心概念,对于提高程序性能和系统资源的利用效率至关重要。在Java中,并发编程的实现主要依赖于Java语言的内置特性以及Java并发API。...

    JAVA并发编程实践-中文-高清-带书签-完整版

    《JAVA并发编程实践》是一本深入探讨Java多线程编程技术的专业书籍,旨在帮助开发者理解和掌握在Java平台上进行高效并发编程的关键知识。本书涵盖了从基本概念到高级特性的全面内容,是Java程序员进阶的必读之作。 ...

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

    《Java并发编程的艺术》这本书是Java开发者深入理解并发编程的重要参考。并发编程是现代多核处理器环境下不可或缺的技术,它能够充分利用系统资源,提高程序的执行效率。以下将详细阐述书中涉及的一些关键知识点。 ...

    Java并发编程实战

    《Java并发编程实战》这本书是面向已有一定Java多线程基础的开发者,旨在提升他们在并发编程领域的专业知识。并发编程是现代计算机系统中的重要组成部分,尤其是在多核处理器和高并发应用场景日益普及的今天,掌握...

    JAVA并发编程实践(中文)含源码

    《JAVA并发编程实践》是一本深入探讨Java多线程与并发控制的权威书籍,中文版本的出现使得更多国内开发者能够无障碍地学习这方面的知识。这本书不仅涵盖了理论基础,还提供了丰富的实战示例,包括源码,使读者能够...

    Java并发编程的艺术.zip

    《Java并发编程的艺术》这本书是Java开发者深入了解并发编程的重要参考资料。在Java开发中,尤其是在多核处理器和高并发场景下,理解和掌握并发编程是至关重要的。以下是对书中的主要知识点的详细阐述: 1. **Java...

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

    《Java并发编程实战》是一本深入探讨Java多线程和并发编程的经典著作,它由Brian Goetz、Tim Peierls、Joshua Bloch、David Holmes和Doug Lea合著,旨在帮助开发者理解和掌握Java并发的核心概念和技术。这本书的源码...

    Java 并发编程实战

    《Java并发编程实战》这本书深入探讨了Java平台上的并发编程技术,涵盖了从基础概念到高级策略,旨在帮助开发者理解和解决多线程环境中的各种问题。并发编程是Java开发中的重要领域,尤其在如今多核处理器普及的时代...

    java并发编程实践

    《Java并发编程实践》是Java领域的一本经典之作,由Brian Goetz等知名专家撰写,中文版的出现使得更多的中国开发者能深入理解并发编程的精髓。这本书深入浅出地探讨了Java平台上的并发编程,涵盖了从基本概念到高级...

    JAVA并发编程实践中文版

    《JAVA并发编程实践》是一本深入探讨Java并发编程的权威指南,专为那些希望充分利用多核处理器性能,提升系统效率的开发者设计。这本书由Brian Goetz等多位Java并发领域的专家共同编写,它不仅介绍了Java并发的基本...

    java并发编程基础PPT以及DEMO示例&操作系统概述PPT

    在本资源中,我们有两个主要的学习材料:一个关于“Java并发编程基础”的PPT和一个包含DEMO示例,另一个是“操作系统概述”的PPT。这些资料对于理解Java多线程编程以及操作系统的基础原理至关重要。 首先,让我们...

Global site tag (gtag.js) - Google Analytics