0 前言
LinkedBlockingQueue - 单链表实现的阻塞队列。该队列按 FIFO(先进先出)排序元素,新元素从队列尾部插入,从队首获取元素.是深入并发编程的基础数据结构.
1 继承体系
Queue 作为最基础的接口,定义了队列的三类基本操作:
BlockingQueue 基于 Queue 加了阻塞功能:
- 一直阻塞
- 阻塞一定时间,返回特殊值
remove 方法,BlockingQueue 类注释中定义的是抛异常,但 LinkedBlockingQueue 中 remove 方法实际是返回 false。
2 属性
2.1 链式存储
- 节点的数据结构
- next 为当前元素的下一个,为 null 表示当前节点是最后一个
- 链表容量
- 默认大小为 Integer.MAX_VALUE !显然太大了!禁用!
- 链表已有元素大小
使用了 AtomicInteger,线程安全
链表头、尾
2.2 锁
- take 时的锁
- take 的条件队列,condition 可理解为基于 ASQ 建立的条件队列
- put 时的锁
- put 的条件队列
- take 锁和 put 锁,是为保证队列操作时的线程安全,设计两种锁,是为了 take 和 put 两种操作可同时进行,互不影响。
2.3 迭代器
- 实现了自己的迭代器
private class Itr implements Iterator<E> { /* * Basic weakly-consistent iterator. At all times hold the next * item to hand out so that if hasNext() reports true, we will * still have it to return even if lost race with a take etc. */ private Node<E> current; private Node<E> lastRet; private E currentElement; Itr() { fullyLock(); try { current = head.next; if (current != null) currentElement = current.item; } finally { fullyUnlock(); } } public boolean hasNext() { return current != null; } /** * Returns the next live successor of p, or null if no such. * * Unlike other traversal methods, iterators need to handle both: * - dequeued nodes (p.next == p) * - (possibly multiple) interior removed nodes (p.item == null) */ private Node<E> nextNode(Node<E> p) { for (;;) { Node<E> s = p.next; if (s == p) return head.next; if (s == null || s.item != null) return s; p = s; } } public E next() { fullyLock(); try { if (current == null) throw new NoSuchElementException(); E x = currentElement; lastRet = current; current = nextNode(current); currentElement = (current == null) ? null : current.item; return x; } finally { fullyUnlock(); } } public void remove() { if (lastRet == null) throw new IllegalStateException(); fullyLock(); try { Node<E> node = lastRet; lastRet = null; for (Node<E> trail = head, p = trail.next; p != null; trail = p, p = p.next) { if (p == node) { unlink(p, trail); break; } } } finally { fullyUnlock(); } } }