最近抽空整理了一下几年前的学习笔记，发现有些东西久了不用就忘记了，感慨年纪大了忘性大呀。现在把这些笔记整理一下分享到博客上，分享的同时加深自己的记忆。

java5加入了一个java.util.concurrent包，这个包的大部分代码作者都是Doug Lea大神，JUC对java并发编程有着里程碑式的意义。

由于笔记是几年前的，当时的学习时在JDK6的基础上做的，所以如无特殊说明文中涉及到的代码都是基于JDK6的。今天的主角是BlockingQueue，这是一个阻塞队列，不接受null元素，该队列应用非常广泛，可以用来实现消费者-生产者模型，JDK中的线程池的任务队列也时通过BlockingQueue来实现。它包含几个关键方法：

BlockingQueue有两个主要的实现LinkedBlockingQueue和ArrayBlockingQueue，下面主要来学习一下这两个实现。

ArrayBlockingQueue：是基于数组实现的阻塞队列，有界且不能扩容，在构造时需要传参指定队列的容量，如果设置的初始容量过大导致数组所占内存超出了当前堆中最大的连续空间，队列创建会失败。该队列在逻辑上是环形的，当当前元素位置处于数组最后一个位置时，下一个入队元素会插到数组的第一个位置。

LinkedBlockingQueue：基于链表实现的阻塞队列，不用考虑当前堆中是否有足够连续空间的问题，初始容量可以设置到Integer.MAX_VALUE。

关于这两者的实现细节可以去看源代码，主要是通过Lock+Condition来实现，对JDK的Lock、Condition不熟悉的可以通过学习这两个类的源代码来加深学习，下面简单测试一下这两种实现的性能，首先测试入队方法，这里选中offer方法，测试方法是插入1000000个元素，执行100次取总时间的平均值，测试代码如下：

private static long testOfferOfLinkedBlockingQueue(int elements, int threads)
throws InterruptedException {
long time = System.currentTimeMillis();
final BlockingQueue<Integer> queue = new LinkedBlockingQueue<Integer>(
elements);
final CountDownLatch latch = new CountDownLatch(elements);
for (int i = 0; i < threads; i++) {
final int index = i;
Thread t = new Thread(new Runnable() {

@Override
public void run() {
while (queue.offer(index)) {
latch.countDown();
}
}
});
t.start();
}
latch.await();
return System.currentTimeMillis() - time;
}

private static long testOfferOfArrayBlockingQueue(int elements, int threads)
throws InterruptedException {
long time = System.currentTimeMillis();
final BlockingQueue<Integer> queue = new ArrayBlockingQueue<Integer>(
elements);
final CountDownLatch latch = new CountDownLatch(elements);
for (int i = 0; i < threads; i++) {
final int index = i;
Thread t = new Thread(new Runnable() {

@Override
public void run() {
while (queue.offer(index)) {
latch.countDown();
}
}
});
t.start();
}
latch.await();
return System.currentTimeMillis() - time;
}

private static void testOfferOfBlockingQueue() throws InterruptedException {
final int testNumber = 100;
final int elements = 1000000;
final int threads = 1;
long totalTime = 0;
for (int i = 0; i < testNumber; i++) {
totalTime += testOfferOfArrayBlockingQueue(elements, threads);
}
System.out.println(totalTime / testNumber);

totalTime = 0;
for (int i = 0; i < testNumber; i++) {
totalTime += testOfferOfLinkedBlockingQueue(elements, threads);
}
System.out.println(totalTime / testNumber);
}

public static void main(String[] args) throws InterruptedException {
testOfferOfBlockingQueue();
}

LinkedBlockingQueue的入队操作：

    private void insert(E x) {
        last = last.next = new Node<E>(x);
    }

    public boolean offer(E e) {        if (e == null) throw new NullPointerException();        final AtomicInteger count = this.count;        if (count.get() == capacity)            return false;        int c = -1;        final ReentrantLock putLock = this.putLock;        putLock.lock();        try {            if (count.get() < capacity) {                insert(e);                c = count.getAndIncrement();                if (c + 1 < capacity)                    notFull.signal();            }        } finally {            putLock.unlock();        }        if (c == 0)            signalNotEmpty();        return c >= 0;    }

    private void insert(E x) {
        items[putIndex] = x;
        putIndex = inc(putIndex);
        ++count;
        notEmpty.signal();
    }

    public boolean offer(E e) {        if (e == null) throw new NullPointerException();        final ReentrantLock lock = this.lock;        lock.lock();        try {            if (count == items.length)                return false;            else {                insert(e);                return true;            }        } finally {            lock.unlock();        }    }

通过对比两者的代码可以发现ArrayBlockingQueue的插入操作非常轻量级，基本上就是给数组元素赋值，而LinkedBlockingQueue多了一个创建Node对象的动作，这就是造成两者效率差异的根因，频繁的创建Node对象会增加GC压力。通过jvisualvm的VisualGC插件来看一下GC的情况：

ArrayBlockingQueue入队动作的GC情况：

从上面的GC结果中可以看出，LinkedBlockingQueue无论是GC次数和GC时间都远远超过了ArrayBlockingQueue。在测试结果中还发现一个比较特殊的现象：无论是ArrayBlockingQueue还是LinkedBlockingQueue，单线程的效率是最高的，而且差异还比较大，而当线程数2到15的性能基本上接近，我的机器是双核的，理论上来讲多线程能利用多核的优势进行并行处理，两个线程应该比单线程快才对，初步分析了一下，应该是队列的入队操作太过轻量级导致了并行执行带来的优势被线程上下文带来的开销完全抵消。如果任务消耗的时间比较长，并行执行的优势才会慢慢的体现出来，可以稍微修改一下测试代码验证一下，可以再上述测试代码的while循环中加一个执行1000空循环，修改之后执行测试结果发现双线程比单线程的执行时间小了，贴一下测试结果：

下面来看一下出队的 情况，来测试一下poll方法的性能，下面是测试代码，从队列中读取1000000个元素，执行100次取总时间平均值：

    private static long testPollOfLinkedBlockingQueue(int elements, int threads)
throws InterruptedException {
final BlockingQueue<Integer> queue = new LinkedBlockingQueue<Integer>(
elements);
for (int i = 0; i < elements; i++) {
queue.offer(i);
}
long time = System.currentTimeMillis();
final CountDownLatch latch = new CountDownLatch(elements);
for (int i = 0; i < threads; i++) {
Thread t = new Thread(new Runnable() {

@Override
public void run() {
while (queue.poll() != null) {
latch.countDown();
}
}
});
t.start();
}
latch.await();
return System.currentTimeMillis() - time;
}

private static long testPollOfArrayBlockingQueue(int elements, int threads)
throws InterruptedException {
final BlockingQueue<Integer> queue = new ArrayBlockingQueue<Integer>(
elements);
for (int i = 0; i < elements; i++) {
queue.offer(i);
}
long time = System.currentTimeMillis();
final CountDownLatch latch = new CountDownLatch(elements);
for (int i = 0; i < threads; i++) {
Thread t = new Thread(new Runnable() {

@Override
public void run() {
while (queue.poll() != null) {
latch.countDown();
}
}
});
t.start();
}
latch.await();
return System.currentTimeMillis() - time;
}

private static void testPollOfBlockingQueue() throws InterruptedException {
final int testNumber = 100;
final int elements = 1000000;
final int threads = 1;
long totalTime = 0;
for (int i = 0; i < testNumber; i++) {
totalTime += testPollOfArrayBlockingQueue(elements, threads);
}
System.out.println(totalTime / testNumber);

totalTime = 0;
for (int i = 0; i < testNumber; i++) {
totalTime += testPollOfLinkedBlockingQueue(elements, threads);
}
System.out.println(totalTime / testNumber);
}

ArrayBlockingQueue入队代码：

    public E poll() {
        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
            if (count == 0)
                return null;
            E x = extract();
            return x;
        } finally {
            lock.unlock();
        }
    }
    private E extract() {
        final E[] items = this.items;
        E x = items[takeIndex];
        items[takeIndex] = null;
        takeIndex = inc(takeIndex);
        --count;
        notFull.signal();
        return x;
    }

    public E poll() {
        final AtomicInteger count = this.count;
        if (count.get() == 0)
            return null;
        E x = null;
        int c = -1;
        final ReentrantLock takeLock = this.takeLock;
        takeLock.lock();
        try {
            if (count.get() > 0) {
                x = extract();
                c = count.getAndDecrement();
                if (c > 1)
                    notEmpty.signal();
            }
        } finally {
            takeLock.unlock();
        }
        if (c == capacity)
            signalNotFull();
        return x;
    }
    private E extract() {
        Node<E> first = head.next;
        head = first;
        E x = first.item;
        first.item = null;
        return x;
    }

ArrayBlockingQueue出队动作的GC情况：

LinkedBlockingQueue出队动作的GC情况：

从结果中可以看出LinkedBlockingQueue的GC时间略高于ArrayBlockingQueue。

通过上面贴出的代码还可以发现，LinkedBlockingQueue的锁粒度比较小，读写锁时分离，实现比较复杂，而ArrayBlockingQueue的锁是全局锁，读写互斥，实现比较简单。没有搞清楚Doug Lea大神时怎么想的，为什么ArrayBlockingQueue的锁实现不参考LinkedBlockingQueue。我的理解可能的原因是，ArrayBlockingQueue的读写动作都比较轻量级，时间很短，就算读写互斥也对性能的影响很小，而读写锁分离会大大增加代码的复杂度。