多线程队列

Java多线程包括线程池会用到缓存任务的队列，Java提供的线程安全队列分为两种：阻塞队列和非阻塞队列

1.阻塞队列

阻塞队列支持生产者模式和消费者模式互相等待，队列为空，消费线程阻塞，直到队列不为空；当队列满时，生产线程会阻塞，直到队列不满。

Java ThreadPool中也用到阻塞队列，当创建的线程数超过核心线程数，新提交的任务会被push到阻塞队列中。根据自己的业务可以选择不同的队列。

Java线程池Executors实现的四种类型的ThreadPoolExecutor对应上面的缓存队列详情如下：

 2.非阻塞队列

常用的非阻塞线程安全队列是ConcurrentLinkedQueue，一种无界限队列。FIFO原则，基于链表实现，CAS乐观锁保证线程安全。

构造函数：

• head、tail节点组成
• 每个节点（Node）由节点元素（item）和指向下一个节点的引用 (next) 组成
• 节点与节点之间通过 next 关联
• 队列初始化时， head 节点存储的元素为空，tail 节点等于 head 节点

 
public ConcurrentLinkedQueue() {
   head = tail = new Node(null);
}
 
private static class Node {
        volatile E item;
        volatile Node next;
            .
            .
}

入列：一个线程入列一个数据时，会将该数据封装成一个 Node 节点，并先获取到队列的队尾节点，当确定此时队尾节点的 next 值为 null 之后，再通过 CAS 将新队尾节点的 next 值设为新节点。此时 p != t，也就是设置 next 值成功，然后再通过 CAS 将队尾节点设置为当前节点即可。

 
public boolean offer(E e) {
        checkNotNull(e);
        //创建入队节点
        final Node newNode = new Node(e);
        //t，p为尾节点，默认相等，采用失败即重试的方式，直到入队成功         
        for (Node t = tail, p = t;;) {
            //获取队尾节点的下一个节点
            Node q = p.next;
            //如果q为null，则代表p就是队尾节点
            if (q == null) {
                //将入列节点设置为当前队尾节点的next节点
                if (p.casNext(null, newNode)) {
                    //判断tail节点和p节点距离达到两个节点
                    if (p != t) // hop two nodes at a time
                        //如果tail不是尾节点则将入队节点设置为tail。
                        // 如果失败了，那么说明有其他线程已经把tail移动过 
                        casTail(t, newNode);  // Failure is OK.
                    return true;
                }
            }
            // 如果p节点等于p的next节点，则说明p节点和q节点都为空，表示队列刚初始化，所以返回  
            else if (p == q)
                p = (t != (t = tail)) ? t : head;
            else
                // Check for tail updates after two hops.
                p = (p != t && t != (t = tail)) ? t : q;
        }
    }

出列： 首先获取 head 节点，并判断 item 是否为 null，如果为空，则表示已经有一个线程刚刚进行了出列操作，然后更新 head 节点；如果不为空，则使用 CAS 操作将 head 节点设置为 null，CAS 就会成功地直接返回节点元素，否则还是更新 head 节点

 
    public E poll() {
        // 设置起始点
        restartFromHead:
        for (;;) {
            //p获取head节点
            for (Node h = head, p = h, q;;) {
                //获取头节点元素
                E item = p.item;
                //如果头节点元素不为null，通过cas设置p节点引用的元素为null
                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;
                }
                //如果p节点的下一个节点为null，则说明这个队列为空，更新head结点
                else if ((q = p.next) == null) {
                    updateHead(h, p);
                    return null;
                }
                //节点出队失败，重新跳到restartFromHead来进行出队
                else if (p == q)
                    continue restartFromHead;
                else
                    p = q;
            }
        }
    }

结论：ConcurrentLinkedQueue 是基于 CAS 乐观锁实现的，在并发时的性能要好于其它阻塞队列，因此很适合作为高并发场景下的排队队列。

Disruptor

Disruptor是英国外汇交易公司LMAX开发的一个高性能队列，研发的初衷是解决内存队列的延迟问题。

为什么性能高？

• CAS
• 消除伪共享
• RingBuffer

最后

我们看到Executors提供的很多默认方法使用的都是无界的LinkedBlockingQueue，高负载的情况下无界队列很容易导致OOM，OOM会导致stop world，这是致命的，所以不建议使用Executors。建议使用使用了有界队列的线程池。

当没有设置拒绝策略时会抛出RejectedExecutionException运行时异常，并不会强制抛出，所以任务比较重要时，务必要自己实现拒绝策略。自定义拒绝策略往往和降级策略（重要的任务可以存入数据库或消息队列，启用另外的补偿线程池去做消费）搭配使用。