LinkedBlockingQueue 是 Java 中用于实现线程安全队列的类。它是一个基于链接节点的阻塞队列，并且在队列为空时，获取元素的线程会阻塞;当队列满时，存储元素的线程会阻塞。LinkedBlockingQueue 的使用方法如下：
1. 创建一个 LinkedBlockingQueue 对象。
2. 使用 put() 方法往队列里存入元素。
3. 使用 take() 方法从队列取出元素。
基本的入队出队
1. public class LinkedBlockingQueue<E> extends AbstractQueue<E> 2. implements BlockingQueue<E>, java.io.Serializable { 3. static class Node<E> { 4. E item; 5. /** 6. * 下列三种情况之一 7. * <p> 8. * - 真正的后继节点 9. * <p> 10. * - 自己, 发生在出队时 11. * <p> 12. * - null, 表示是没有后继节点, 是最后了 13. */ 14. Node<E> next; 15. Node(E x) { 16. item = x; 17. } 18. } 19. }
初始化链表 last = head = new Node(null); Dummy 节点用来占位，item 为 null
当一个节点入队 last = last.next = node;
再来一个节点入队 last = last.next = node;
出队
1. h = head first = h.next h.next = h head = first 2. 3. Node<E> h = head; 4. 5. Node<E> first = h.next; 6. 7. h.next = h; // help GC 8. 9. head = first; 10. 11. E x = first.item; 12. 13. first.item = null; 14. 15. return x;
h = head
first = h.next
h.next = h
head = first
1. E x = first.item; 2. 3. first.item = null; 4. 5. return x;
加锁分析
高明之处在于用了两把锁和 dummy 节点 用一把锁，同一时刻，最多只允许有一个线程（生产者或消费者，二选一）执行 用两把锁，同一时刻，可以允许两个线程同时（一个生产者与一个消费者）执行 消费者与消费者线程仍然串行 生产者与生产者线程仍然串行
线程安全分析
当节点总数大于 2 时（包括 dummy 节点），putLock 保证的是 last 节点的线程安全，takeLock 保证的是 head 节点的线程安全。两把锁保证了入队和出队没有竞争
当节点总数等于 2 时（即一个 dummy 节点，一个正常节点）这时候，仍然是两把锁锁两个对象，不会竞争
当节点总数等于 1 时（就一个 dummy 节点）这时 take 线程会被 notEmpty 条件阻塞，有竞争，会阻塞
1. // 用于 put(阻塞) offer(非阻塞) 2. private final ReentrantLock putLock = new ReentrantLock(); 3. 4. 5. // 用户 take(阻塞) poll(非阻塞) 6. private final ReentrantLock takeLock = new ReentrantLock();
put 操作
1. public void put(E e) throws InterruptedException { 2. if (e == null) throw new NullPointerException(); 3. int c = -1; 4. Node<E> node = new Node<E>(e); 5. final ReentrantLock putLock = this.putLock; 6. // count 用来维护元素计数 7. final AtomicInteger count = this.count; 8. putLock.lockInterruptibly(); 9. try { 10. // 满了等待 11. while (count.get() == capacity) { 12. // 倒过来读就好: 等待 notFull 13. notFull.await(); 14. } 15. // 有空位, 入队且计数加一 16. enqueue(node); 17. c = count.getAndIncrement(); 18. // 除了自己 put 以外, 队列还有空位, 由自己叫醒其他 put 线程 19. if (c + 1 < capacity) 20. notFull.signal(); 21. } finally { 22. putLock.unlock(); 23. } 24. // 如果队列中有一个元素, 叫醒 take 线程 25. if (c == 0) 26. // 这里调用的是 notEmpty.signal() 而不是 notEmpty.signalAll() 是为了减少竞争 27. signalNotEmpty(); 28. }
take 操作
1. public E take() throws InterruptedException { 2. E x; 3. int c = -1; 4. final AtomicInteger count = this.count; 5. final ReentrantLock takeLock = this.takeLock; 6. takeLock.lockInterruptibly(); 7. try { 8. while (count.get() == 0) { 9. notEmpty.await(); 10. } 11. x = dequeue(); 12. c = count.getAndDecrement(); 13. if (c > 1) 14. notEmpty.signal(); 15. } finally { 16. takeLock.unlock(); 17. } 18. // 如果队列中只有一个空位时, 叫醒 put 线程 19. // 如果有多个线程进行出队, 第一个线程满足 c == capacity, 但后续线程 c < capacity 20. if (c == capacity) 21. // 这里调用的是 notFull.signal() 而不是 notFull.signalAll() 是为了减少竞争 22. signalNotFull() 23. return x; 24. }
由 put 唤醒 put 是为了避免信号不足
性能比较
主要列举 LinkedBlockingQueue 与 ArrayBlockingQueue 的性能比较
- Linked 支持有界，Array 强制有界
- Linked 实现是链表，Array 实现是数组
- Linked 是懒惰的，而 Array 需要提前初始化 Node 数组
- Linked 每次入队会生成新 Node，而 Array 的 Node 是提前创建好的
- Linked 两把锁，Array 一把锁
