概述

  • 要实现一个线程安全的队列有两种方式:阻塞和非阻塞。阻塞队列无非就是锁的应用,而非阻塞则是CAS算法的应用。下面我们就开始一个非阻塞算法的研究:CoucurrentLinkedQueue。

    解析

  • ConcurrentLinkedQueue是一个基于链接节点的无边界的线程安全队列,它采用FIFO原则对元素进行排序。采用“wait-free”算法(即CAS算法)来实现的。
  • CoucurrentLinkedQueue的结构由head节点和tail节点组成,每个节点由节点元素item和指向下一个节点的next引用组成,而节点与节点之间的关系就是通过该next关联起来的,从而组成一张链表的队列。节点Node为ConcurrentLinkedQueue的内部类,定义如下
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    private static class Node<E> {
    /** 节点元素域 */
    volatile E item;
    volatile Node<E> next;

    //初始化,获得item 和 next 的偏移量,为后期的CAS做准备

    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);
    }
    }
    }

总结

参考