【JUC源码专题】LinkedBlockingQueue 源码分析（JDK8）

LinkedBlockingQueue 不同于 ArrayBlockingQueue，前者通过使用 Atomicinteger 类型的 count 变量和链表中哨兵结点（头结点 head）将锁拆分为 take 和 put 两把锁使锁细粒度化了，在多线程竞争方面性能优于后者。后者由于是连续的地址空间，所以适合用在需要利用高速缓存的场景。

LinkedBlockingQueue 用法

import java.util.concurrent.LinkedBlockingQueue;

public class TestQueue {
    public static void main(String[] args) throws InterruptedException {
        LinkedBlockingQueue<Integer> bq = new LinkedBlockingQueue<>(8);
        bq.put(1);
        Integer take = bq.take();
        boolean contains = bq.contains(1);
    }
}
1
2
3
4
5
6
7
8
9
10

核心变量

    // 队列容量，默认为 Integer.MAX_VALUE
    /** The capacity bound, or Integer.MAX_VALUE if none */
    private final int capacity;

    // 当前队列的元素个数
    /** Current number of elements */
    private final AtomicInteger count = new AtomicInteger();

    // 链表头结点，head.item 永远为 null
    /** Invariant: head.item == null */
    transient Node<E> head;

    // 链表尾结点，last.next 永远为 null
    /** Invariant: last.next == null */
    private transient Node<E> last;
    
    // 消费者的锁
    private final ReentrantLock takeLock = new ReentrantLock();

    // 消费者的挂起操作以及唤醒用的 condition
    // 等待队列为非空
    private final Condition notEmpty = takeLock.newCondition();

    // 生产者的锁
    private final ReentrantLock putLock = new ReentrantLock();

    // 生产者的挂起操作以及唤醒用的 condition
    // 等待队列为非满
    private final Condition notFull = putLock.newCondition();
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

构造方法

    public LinkedBlockingQueue(int capacity) {
        if (capacity <= 0) throw new IllegalArgumentException();
        this.capacity = capacity;
        // 值为 null 的哨兵结点。在获取/添加数据时，不需要判断 head/last 是否为 null。
        last = head = new Node<E>(null);
    }
1
2
3
4
5
6

生产者

put(E e)

    public void put(E e) throws InterruptedException {
        if (e == null) throw new NullPointerException();
        int c = -1;
        Node<E> node = new Node<E>(e);
        final ReentrantLock putLock = this.putLock;
        final AtomicInteger count = this.count;
        // 可中断获取锁
        putLock.lockInterruptibly();
        try {
            // 当队列满时进行等待
            while (count.get() == capacity) {
                notFull.await();
            }
            // 将元素添加到队列中
            enqueue(node);
            // 队列元素数量加一
            c = count.getAndIncrement();
            // 因为前面是 getAndIncrement 先 get 后 increment 所以需要 c + 1 后判断当前容量是否小于最大容量，若是则唤醒等待队列非满的线程即唤醒其他生产者。
            if (c + 1 < capacity)
                notFull.signal();
        } finally {
            putLock.unlock();
        }
        // 若放入队列之前队列为空，则在放入元素之后唤醒等待队列为非空的线程即唤醒消费者。
        if (c == 0)
            signalNotEmpty();
    }
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

add(E e)

    public boolean add(E e) {
        if (offer(e))
            return true;
        else
            throw new IllegalStateException("Queue full");
    }
1
2
3
4
5
6

offer(E e)

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;  
    Node<E> node = new Node<E>(e);  
    // 获取生产者的锁
    final ReentrantLock putLock = this.putLock;  
    putLock.lock();  
    try {  
        if (count.get() < capacity) {  
            // 添加到链表尾部
            // last = last.next = node;
            enqueue(node);
            // 先 get 后加 1  
            c = count.getAndIncrement();  
            if (c + 1 < capacity)  
                // 唤醒生产者
                notFull.signal();  
        }  
    } finally {  
        // 释放锁
        putLock.unlock();  
    }  
    // 若 c == 0，则说明本次添加数据之前，队列中元素个数为 0。
    // 如果有消费者在队列中没有数据时来消费，则该消费者会挂起
    if (c == 0)  
        // 唤醒消费者
        signalNotEmpty();  
    // 若添加成功，则 c 必然大于等于 0，返回 true。否则返回 false。
    return c >= 0;  
}
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

signalNotEmpty()

    private void signalNotEmpty() {
        // 获取读锁
        final ReentrantLock takeLock = this.takeLock;
        takeLock.lock();
        try {
            // 唤醒消费者
            notEmpty.signal();
        } finally {
            takeLock.unlock();
        }
    }
1
2
3
4
5
6
7
8
9
10
11

offer(E e, long timeout, TimeUnit unit)

    public boolean offer(E e, long timeout, TimeUnit unit)
        throws InterruptedException {

        if (e == null) throw new NullPointerException();
        // timeout 转纳秒
        long nanos = unit.toNanos(timeout);
        int c = -1;
        // 获取写锁
        final ReentrantLock putLock = this.putLock;
        final AtomicInteger count = this.count;
        // 允许中断的加锁方式
        putLock.lockInterruptibly();
        try {
            // 判断队列容量是否已满
            while (count.get() == capacity) {
                // 挂起的时间小于等于 0，直接返回 false
                if (nanos <= 0)
                    return false;
                // 挂起线程
                nanos = notFull.awaitNanos(nanos);
            }
            // 入队
            enqueue(new Node<E>(e));
            // 元素个数 +1
            c = count.getAndIncrement();
            if (c + 1 < capacity)
                // 唤醒生产者
                notFull.signal();
        } finally {
            // 释放锁
            putLock.unlock();
        }
        if (c == 0)
            // 唤醒消费者
            signalNotEmpty();
        return true;
    }
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

消费者

take()

    public E take() throws InterruptedException {
        E x;
        int c = -1;
        final AtomicInteger count = this.count;
        final ReentrantLock takeLock = this.takeLock;
        // 可中断获取锁
        takeLock.lockInterruptibly();
        try {
            // 若队列为空，则等待
            while (count.get() == 0) {
                notEmpty.await();
            }
            // 从队列中获取一个元素
            x = dequeue();
            // 元素数量减一
            c = count.getAndDecrement();
            // 唤醒其他等待队列为空的线程来消费即唤醒其他消费者
            if (c > 1)
                notEmpty.signal();
        } finally {
            takeLock.unlock();
        }
        // 若获取元素之前队列是满的，则此时可能有生产者线程正在等待。获取元素后，唤醒生产者线程。
        if (c == capacity)
            signalNotFull();
        return x;
    }
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

remove()

    public E remove() {
        E x = poll();
        if (x != null)
            return x;
        else
            throw new NoSuchElementException();
    }#
1
2
3
4
5
6
7

poll()

    public E poll() {
        final AtomicInteger count = this.count;
        if (count.get() == 0)
            // 队列无数据，return null
            return null;
        E x = null;
        int c = -1;
        // 获取消费者锁
        final ReentrantLock takeLock = this.takeLock;
        // 加锁
        takeLock.lock();
        try {
            // DCL
            if (count.get() > 0) {
                // 出队
                x = dequeue();
                // 先 get 后减 1
                c = count.getAndDecrement();
                if (c > 1)
                    // 唤醒消费者
                    notEmpty.signal();
            }
        } finally {
            // 释放锁资源
            takeLock.unlock();
        }
        if (c == capacity)
            // 唤醒生产者
            signalNotFull();
        return x;
    }
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

dequeue()

    private E dequeue() {
        // 获取哨兵结点
        Node<E> h = head;
        // 获取哨兵结点的 next 结点
        Node<E> first = h.next;
        // 将哨兵结点的 next 指向自己
        h.next = h; // help GC
        // 将 first 设置为新的头结点
        head = first;
        // 获取结点的数据最后返回
        E x = first.item;
        // 将头结点的数据置为空
        first.item = null;
        return x;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

poll(long timeout, TimeUnit unit)

    public E poll(long timeout, TimeUnit unit) throws InterruptedException {
        E x = null;
        int c = -1;
        long nanos = unit.toNanos(timeout);
        final AtomicInteger count = this.count;
        final ReentrantLock takeLock = this.takeLock;
        // 允许中断的加锁
        takeLock.lockInterruptibly();
        try {
            while (count.get() == 0) {
                if (nanos <= 0)
                    return null;
                // 挂起当前线程
                nanos = notEmpty.awaitNanos(nanos);
            }
            x = dequeue();
            c = count.getAndDecrement();
            if (c > 1)
                notEmpty.signal();
        } finally {
            takeLock.unlock();
        }
        if (c == capacity)
            signalNotFull();
        return x;
    }
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

take()

    public E take() throws InterruptedException {
        E x;
        int c = -1;
        final AtomicInteger count = this.count;
        final ReentrantLock takeLock = this.takeLock;
        takeLock.lockInterruptibly();
        try {
            // 区别于 poll(timeout,unit)，除非中断标记位，抛出异常，否则一直等待
            while (count.get() == 0) {
                notEmpty.await();
            }
            x = dequeue();
            c = count.getAndDecrement();
            if (c > 1)
                notEmpty.signal();
        } finally {
            takeLock.unlock();
        }
        if (c == capacity)
            signalNotFull();
        return x;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

contains(Object o)

为了保证查询时队列元素不发生变化，这里需要在获取全局锁后进行查询。

    public boolean contains(Object o) {
        if (o == null) return false;
        // 获取 put 和 take 锁，禁止其他线程操作队列
        fullyLock();
        try {
            // 从链表头开始遍历
            for (Node<E> p = head.next; p != null; p = p.next)
                if (o.equals(p.item))
                    return true;
            return false;
        } finally {
            fullyUnlock();
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14