开篇语
行列在生活中随处可见,医院缴费需求排队、做核酸需求排队、轿车等红绿灯需求排队等等。
行列是一个按照先来到就排在前面,后来到排在后面的数据结构,而且出队的时分也是按照先来到先出队。运用数组和链表进行完结。通常用于和谐使命的履行和数据的交换。
介绍
LinkedBlockingQueue 是一个可选有界堵塞行列,有界指的是行列存在一个最大容量;堵塞指的是假如行列现已满了,想要往行列持续添加元素的话,那么这个操作将会被暂停,直到行列中有空位才会持续完结添加操作。假如行列现已为空,想要从行列中获取元素,那么这个操作将会被暂停,直接行列中存在元素才会持续完结获取操作。
完结原理
LinkedBlockingQueue 内部运用链表作为元素的存储结构。内部运用了两个锁,分别运用于存操作和取操作。
履行存取操作时,都必须先获取锁,才能够履行存取操作,确保 LinkedBlockingQueue 是线程安全。
LinkedBlockingQueue 经过两个 Condition 条件行列,一个 notFull 条件,一个 notEmpty 条件。在对行列进行刺进元素操作时,判别当时行列现已满,则经过 notFull 条件将线程堵塞,直到其他线程通知该线程行列能够持续刺进元素。在对行列进行移除元素操作时,判别当时行列现已空,则经过 notEmpty 条件堵塞线程,直到其他线程经过该线程能够持续获取元素。
这样确保线程的存取操作不会呈现错误。防止行列在满时,丢掉刺进的元素;也防止在行列空时取到一个 null 值。
构造函数
public LinkedBlockingQueue() {
this(Integer.MAX_VALUE);
}
public LinkedBlockingQueue(int capacity) {
if (capacity <= 0) throw new IllegalArgumentException();
this.capacity = capacity;
last = head = new Node<E>(null);
}
无参构造函数中,默许运用 Integer.MAX_VALUE
作为行列的最大容量。
有参构造函数中,能够自己指定行列的最大容量,而且创建了头节点和尾节点。那么 LinkedBlockingQueue 运用的是有头单向链表。
private final int capacity;
/** Current number of elements */
private final AtomicInteger count = new AtomicInteger();
transient Node<E> head;
private transient Node<E> last;
// 取锁
private final ReentrantLock takeLock = new ReentrantLock();
private final Condition notEmpty = takeLock.newCondition();
// 存锁
private final ReentrantLock putLock = new ReentrantLock();
private final Condition notFull = putLock.newCondition();
而且在对象初始化时,创建了两个锁,分别运用于存操作和取操作。创建了两个条件行列,分别用于行列空和满的情况。
刺进函数
public void put(E e) throws InterruptedException {
if (e == null) throw new NullPointerException();
final int c;
final 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();
if (c + 1 < capacity)
notFull.signal();
} finally {
putLock.unlock();
}
if (c == 0)
signalNotEmpty();
}
-
获取锁
-
判别当时行列是否现已满了
- 假如行列现已满了,调用 notFull 条件行列的 await() 办法,将该线程堵塞,暂停该线程的刺进操作。防止内部溢出的问题。
- 假如没有满,则直接调用入队函数 enqueue 刺进到行列末尾。
-
查看此刻行列是否已满
- 假如未满,则调用 notFull 条件行列的 signal() 办法,唤醒被堵塞在 notFull 条件行列的线程。
-
解锁
-
查看刺进元素前的行列元素数量是否等于0
- 等于 0,则调用 notEmpty 条件行列的 signal() 办法,通知其行列现在不为空,能够唤醒堵塞线程获取元素。
为什么需求调用 notFull 条件行列的 signal() 办法? 由于行列取操作和存操作所运用的锁是不相同的,那么就阐明,一个线程履行存入操作时,其他线程是能够履行取出操作的。我们来看下面这个例子:
- 行列总容量为 5,当时元素数量为5。线程 A 获取了存锁,想要刺进了元素。可是由于行列容量已满,释放锁,而且加入到条件行列中,等待被唤醒。
- 线程 B 获取了存锁,想要刺进了元素。可是由于行列容量已满,释放锁,而且加入到条件行列中,等待被唤醒。
- 线程 C 获取了取锁,取出了元素 1。而且经过 notFull 的 signal 办法唤醒条件行列中被堵塞的线程 A。线程 A 被唤醒后加入到同步行列中,可是此刻还没有竞赛到锁。
- 线程 D 获取了取锁,取出了元素 2。可是还没有履行到唤醒堵塞线程的代码。
- 线程 A 竞赛到锁,开端履行刺进元素操作。将元素刺进之后,查看到行列元素数量为 4,小于行列的总容量,因此会履行 notFull 的 signal 办法唤醒条件行列中被堵塞的线程 B。线程 B 被唤醒后加入到同步行列中,开端竞赛锁。
- 线程 B 竞赛到锁,开端履行刺进元素操作。将元素刺进之后,查看到行列元素数量等于 5,不进行唤醒操作。
这样做的意图是赶快的唤醒堵塞线程,能够更快的完结刺进元素操作。由于线程存和取的操作相互之间并不是互斥的,而是独立运行的,进步吞吐量。
获取函数
public E take() throws InterruptedException {
final E x;
final int c;
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;
}
-
取得取锁
-
判别当时行列是否为空
- 假如行列没有元素,调用 notEmpty 条件行列的 await() 办法,将该线程堵塞,暂停该线程的获取操作。防止获取元素犯错。
- 假如不为空,则直接调用出队函数 dequeue 移除行列第一个元素,并回来给客户端。
-
查看此刻行列是否为空
- 假如不为空,则调用 notEmpty 条件行列的 signal() 办法,唤醒被堵塞在 notEmpty 条件行列的线程。
-
释放锁
-
查看获取元素前的行列元素数量是否等于最大容量
- 等于最大容量,由于此刻现已取出一个元素,因此行列处于未满的状态,能够唤醒堵塞在 notFull 条件的线程,让线程持续刺进元素。
过程 3 的意图是赶快的唤醒堵塞线程,能够更快的完结取元素操作。进步吞吐量。能够尝试自己画出流程图。
入队函数
private void enqueue(Node<E> node) {
last = last.next = node;
}
入队函数极其简略,只要将最后一个元素的 next 指针指向当时元素即完结了刺进操作。
出队函数
private E dequeue() {
// assert takeLock.isHeldByCurrentThread();
// assert head.item == null;
Node<E> h = head;
Node<E> first = h.next;
h.next = h; // help GC
head = first;
E x = first.item;
first.item = null;
return x;
}
我们前面说 LinkedBlockingQueue 运用的是有头链表。头节点只是作为一个标志,实际上并不是一个真正的元素。当获取元素时,将头节点的下一个节点作为头节点,将本来的头节点撤销引证,被垃圾回收即可。
运用场景
适用场景
LinkedBlockingQueue 和 ArrayBlockingQueue 相同适用于多个线程之间需求同享数据、和谐使命履行的场景。因此能够总结出以下几个运用场景:
- 线程池:线程池是一个常见的并发编程模型,它经过线程池中的线程履行使命。而且能够重复运用这些线程。在线程池中,能够运用 LinkedBlockingQueue 来存储需求履行的使命,以此操控使命数量和履行顺序。当线程池中的线程履行完使命之后,能够从 LinkedBlockingQueue 中取出下一个使命履行。
- 出产者-顾客:在出产者-顾客模型中,出产者负责出产数据,顾客负责对数据进行处理。在这种形式下,LinkedBlockingQueue 能够作为出产者与顾客之间的数据通道,确保线程安全和数据正确。
实际运用场景
- Nacos: Nacos 是一个动态服务发现、装备和服务办理渠道,它运用 LinkedBlockingQueue 来完结内部的使命行列。
- Tomcat:从 Tomcat 7 开端,请求行列默许运用了 LinkedBlockingQueue 完结。
- Hystrix: 一个盛行的容错框架,其默许运用 LinkedBlockingQueue 作为请求行列。
总结
LinkedBlockingQueue 和 ArrayBlockQueue 的对比:
- 完结方式不同:LinkedBlockingQueue 是基于链表完结的行列,而 ArrayBlockingQueue 是基于数组完结的行列。
- 刺进和删去元素的功率不同:LinkedBlockingQueue 的刺进和删去元素的功率较高,由于它采用了两把锁来操控读写操作;而 ArrayBlockingQueue 的刺进和删去元素的功率相对较低,由于它采用了一把锁来操控读写操作。
- 内存占用不同:LinkedBlockingQueue 的内存占用比 ArrayBlockingQueue 更高,由于链表结构需求额定的指针存储,而数组结构则不需求。
- 堵塞形式不同:ArrayBlockingQueue支撑公正形式和非公正形式,能够操控入队和出队的顺序;而 LinkedBlockingQueue 只支撑非公正形式。