ArrayBlockingQueue与LinkedBlockingQueue底层原理

2024-03-16 02:28
文章标签 原理 底层 linkedblockingqueue arrayblockingqueue

本文主要是介绍ArrayBlockingQueue与LinkedBlockingQueue底层原理，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

ArrayBlockingQueue与LinkedBlockingQueue底层原理

在线程池中，等待队列采用ArrayBlockingQueue或者LinkedBlockingDeque，那他们是怎么实现存放线程、阻塞、取出的呢？

一、ArrayBlockingQueue底层原理

1.1 简介

ArrayBlockingQueue是一个阻塞的队列，继承了AbstractBlockingQueue，间接的实现了Queue接口和Collection接口。 底层以数组的形式保存数据，所以它是基于数组的阻塞队列。ArrayBlockingQueue是有边界值的，在创建ArrayBlockingQueue时就要确定好该队列的大小，一旦创建，该队列大小不可更改。
内部的全局锁是使用的ReentrantLock。

1.2 关系图谱

在这里插入图片描述

1.3 父类BlockingQueue的方法梳理
public interface BlockingQueue<E> extends Queue<E> {//将对象塞入队列，如果塞入成功返回true, 否则返回false。boolean add(E e);//将对象塞入到队列中，如果设置成功返回true, 否则返回falseboolean offer(E e);//将元素塞入到队列中，如果队列中已经满了，//则该方法会一直阻塞，直到队列中有多余的空间。void put(E e) throws InterruptedException;//将对象塞入队列并设置时间//如果塞入成功返回 true, 否则返回 false.boolean offer(E e, long timeout, TimeUnit unit)throws InterruptedException;//从队列中取对象，如果队列中没有对象，//线程会一直阻塞，直到队列中有对象，并且该方法取得了该对象。E take() throws InterruptedException;//在给定的时间里，从队列中获取对象，//时间到了直接调用普通的poll方法，为null则直接返回null。E poll(long timeout, TimeUnit unit)throws InterruptedException;//获取队列中剩余长度。int remainingCapacity();//从队列中移除指定的值。boolean remove(Object o);//判断队列中包含该对象。public boolean contains(Object o);//将队列中对象，全部移除，并加到传入集合中。int drainTo(Collection<? super E> c);//指定最多数量限制将队列中对，全部移除，并家到传入的集合中。int drainTo(Collection<? super E> c, int maxElements);
}
1.4 ArrayBlockingQueue源码解析
1.4.1 参数解释
	/** 队列中存放的值 */final Object[] items;/** 值的索引，这是取出位置的索引*/int takeIndex;/** 值的索引，这是插入位置的索引*/int putIndex;/** 队列中有多少个元素 */int count;/** Main lock guarding all access */final ReentrantLock lock;/** Condition for waiting takes 取出时枷锁 */private final Condition notEmpty;/** Condition for waiting puts 存入时枷锁*/private final Condition notFull;
1.4.2 构造方法
	/*** capacity 表示数组中最大容量，默认使用非公平锁*/public ArrayBlockingQueue(int capacity) {this(capacity, false);}/*** capacity 表示数组中最大容量* fair 为 false 时使用非公平锁，true 时使用公平锁*/public ArrayBlockingQueue(int capacity, boolean fair) {if (capacity <= 0)throw new IllegalArgumentException();this.items = new Object[capacity];lock = new ReentrantLock(fair);notEmpty = lock.newCondition();notFull =  lock.newCondition();}/*** capacity 表示数组中最大容量* fair 为 false 时使用非公平锁，true 时使用公平锁* c 初始化时，可以加入将我们有的集合加入该队列中*/public ArrayBlockingQueue(int capacity, boolean fair,Collection<? extends E> c) {this(capacity, fair);final ReentrantLock lock = this.lock;lock.lock(); // Lock only for visibility, not mutual exclusiontry {int i = 0;try {for (E e : c) {checkNotNull(e); //判空items[i++] = e;}} catch (ArrayIndexOutOfBoundsException ex) {throw new IllegalArgumentException();}count = i;putIndex = (i == capacity) ? 0 : i;} finally {lock.unlock();}}
1.4.3 存入数据的put方法
public void put(E e) throws InterruptedException {//判空checkNotNull(e);//显示锁final ReentrantLock lock = this.lock;//可中断锁lock.lockInterruptibly();try {//判断队列元素是否以及满了，满了就阻塞，如果队列满了await 是阻塞队列while (count == items.length)notFull.await();//队列未满，入队方法enqueue(e);} finally {//释放锁lock.unlock();}
}

数据入队方法

   private void enqueue(E x) {// assert lock.getHoldCount() == 1;// assert items[putIndex] == null;final Object[] items = this.items;items[putIndex] = x;//判断队列是否以及满了if (++putIndex == items.length)//满了就将下一个入队索引设置为 0 putIndex = 0;count++;//唤醒 其他阻塞的出队操作notEmpty.signal();}
1.4.4 取出数据的take方法
  public E take() throws InterruptedException {final ReentrantLock lock = this.lock;//可中断锁lock.lockInterruptibly();try {while (count == 0)//如果队列数量为0，则阻塞取数据的锁notEmpty.await();//队列长度不为0，开始取数据return dequeue();} finally {lock.unlock();}}

从队列取出数据

 private E dequeue() {//取得当前items对象final Object[] items = this.items;//获取数组最后一个数据@SuppressWarnings("unchecked")E x = (E) items[takeIndex];//取走后置空数组最后一个元素items[takeIndex] = null;if (++takeIndex == items.length)takeIndex = 0;count--;if (itrs != null)itrs.elementDequeued();//唤醒 存入数据的锁notFull.signal();return x;}

二、LinkedBlockingQueue底层原理

2.1 主要参数 解释
//队列中元素个数
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();
2.2 存入元素put
public void put(E e) throws InterruptedException {if (e == null) throw new NullPointerException();int c = -1;Node<E> node = new Node<E>(e);//利用ReentrantLock独占锁来加锁，保证同时只有一个线程来putfinal ReentrantLock putLock = this.putLock;//利用AtomicInteger来表示queue中的元素个数final AtomicInteger count = this.count;//可打断的加锁putLock.lockInterruptibly();try {// private final Condition notFull = putLock.newCondition();//如果队列满了，就调用notFull。await()。notFull是putLock的条件变量，当调用notFull.await()会将putLock释放，阻塞在等待队列notFull上while (count.get() == capacity) {notFull.await();}//入队,不用获得takeLock，因为与出队操作不涉及共享变量//从入队代码可以看出head是一个哨兵节点，不存放任何实际数据//last = last.next = node;enqueue(node);//count++c = count.getAndIncrement();//如果队列未满，唤醒被阻塞的入队线程if (c + 1 < capacity)notFull.signal();} finally {putLock.unlock();}//如果c == 0，说明入队之前队列为空，唤醒出队的等待线程if (c == 0)signalNotEmpty();
}private void signalNotEmpty() {final ReentrantLock takeLock = this.takeLock;//获取出队锁takeLock.lock();try {//唤醒出队等待线程notEmpty.signal();} finally {takeLock.unlock();}
}

取出元素take

public E take() throws InterruptedException {E x;int c = -1;final AtomicInteger count = this.count;final ReentrantLock takeLock = this.takeLock;takeLock.lockInterruptibly();try {//如果队列为空，放弃takeLock，阻塞在等待队列notEmpty上while (count.get() == 0) {notEmpty.await();}//出队x = dequeue();//count--;c = count.getAndDecrement();//如果队列不为空，唤醒出队等待线程if (c > 1)notEmpty.signal();} finally {takeLock.unlock();}//如果队列不为空，唤醒入队等待线程if (c == capacity)signalNotFull();return x;
}private E dequeue() {//head是哨兵节点，不存放数据，实际的头节点是head.nextNode<E> h = head;//head的nextNode<E> first = h.next;h.next = h;//将head踢出head = first;//first的item才是第一个元素，head是哨兵节点E x = first.item;first.item = null;//从dequeue方法可以看出，queue中始终有一个哨兵head节点，不存储任何数据，queue中第一个元素是head.nextreturn x;
}private void signalNotFull() {final ReentrantLock putLock = this.putLock;putLock.lock();try {//唤醒入队等待线程notFull.signal();} finally {putLock.unlock();}
}

三、入队出队总结

3.1 入队
方法做法
put如果队列满了，就阻塞，当队列不满的时候，会再执行入队操作
offer如果队列满了，返回false。未满就返回true
add如果队列满了，抛出异常,未满就返回true
3.2 出队
方法做法
take如果队列为空，就阻塞，当队列不空的时候，会再执行出队操作
poll如果队列空了，返回null
peek返回队列首元素，不会出队

这篇关于ArrayBlockingQueue与LinkedBlockingQueue底层原理的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/813998。

相关文章

深入探索协同过滤：从原理到推荐模块案例

深入探索协同过滤：从原理到推荐模块案例

文章目录 前言一、协同过滤1. 基于用户的协同过滤（UserCF）2. 基于物品的协同过滤（ItemCF）3. 相似度计算方法 二、相似度计算方法1. 欧氏距离2. 皮尔逊相关系数3. 杰卡德相似系数4. 余弦相似度 三、推荐模块案例1.基于文章的协同过滤推荐功能2.基于用户的协同过滤推荐功能 前言     在信息过载的时代，推荐系统成为连接用户与内容的桥梁。本文聚焦于
阅读更多...
hdu4407(容斥原理)

hdu4407(容斥原理)

题意：给一串数字1,2，......n，两个操作:1、修改第k个数字，2、查询区间[l,r]中与n互质的数之和。 解题思路：咱一看，像线段树，但是如果用线段树做，那么每个区间一定要记录所有的素因子，这样会超内存。然后我就做不来了。后来看了题解，原来是用容斥原理来做的。还记得这道题目吗？求区间[1,r]中与p互质的数的个数，如果不会的话就先去做那题吧。现在这题是求区间[l,r]中与n互质的数的和
阅读更多...
【编程底层思考】垃圾收集机制，GC算法，垃圾收集器类型概述

【编程底层思考】垃圾收集机制，GC算法，垃圾收集器类型概述

Java的垃圾收集（Garbage Collection，GC）机制是Java语言的一大特色，它负责自动管理内存的回收，释放不再使用的对象所占用的内存。以下是对Java垃圾收集机制的详细介绍： 一、垃圾收集机制概述： 对象存活判断：垃圾收集器定期检查堆内存中的对象，判断哪些对象是“垃圾”，即不再被任何引用链直接或间接引用的对象。内存回收：将判断为垃圾的对象占用的内存进行回收，以便重新使用。
阅读更多...
hdu4407容斥原理

hdu4407容斥原理

题意： 有一个元素为 1~n 的数列{An}，有2种操作（1000次）： 1、求某段区间 [a,b] 中与 p 互质的数的和。 2、将数列中某个位置元素的值改变。 import java.io.BufferedInputStream;import java.io.BufferedReader;import java.io.IOException;import java.io.Inpu
阅读更多...
hdu4059容斥原理

hdu4059容斥原理

求1-n中与n互质的数的4次方之和 import java.io.BufferedInputStream;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStream;import java.io.InputStreamReader;import java.io.PrintWrit
阅读更多...
哈希表的底层实现(1)---C++版

哈希表的底层实现(1)---C++版

目录 哈希表的基本原理 哈希表的优点 哈希表的缺点 应用场景 闭散列法 开散列法 开放定值法Open Addressing——线性探测的模拟实现 超大重点部分评析 链地址法Separate Chaining——哈希桶的模拟实现 哈希表（Hash Table）是一种数据结构，它通过将键（Key）映射到值（Value）的方式来实现快速的数据存储与查找。哈希表的核心概念是哈希
阅读更多...
寻迹模块TCRT5000的应用原理和功能实现（基于STM32）

寻迹模块TCRT5000的应用原理和功能实现（基于STM32）

目录 概述 1 认识TCRT5000 1.1 模块介绍 1.2 电气特性 2 系统应用 2.1 系统架构 2.2 STM32Cube创建工程 3 功能实现 3.1 代码实现 3.2 源代码文件 4 功能测试 4.1 检测黑线状态 4.2 未检测黑线状态 概述 本文主要介绍TCRT5000模块的使用原理，包括该模块的硬件实现方式，电路实现原理，还使用STM32类
阅读更多...
TL-Tomcat中长连接的底层源码原理实现

TL-Tomcat中长连接的底层源码原理实现

长连接：浏览器告诉tomcat不要将请求关掉。  如果不是长连接，tomcat响应后会告诉浏览器把这个连接关掉。    tomcat中有一个缓冲区  如果发送大批量数据后 又不处理  那么会堆积缓冲区 后面的请求会越来越慢。
阅读更多...
PHP原理之内存管理中难懂的几个点

PHP原理之内存管理中难懂的几个点

PHP的内存管理, 分为俩大部分, 第一部分是PHP自身的内存管理, 这部分主要的内容就是引用计数, 写时复制, 等等面向应用的层面的管理. 而第二部分就是今天我要介绍的, zend_alloc中描写的关于PHP自身的内存管理, 包括它是如何管理可用内存, 如何分配内存等. 另外, 为什么要写这个呢, 因为之前并没有任何资料来介绍PHP内存管理中使用的策略, 数据结构, 或者算法. 而在我们
阅读更多...
Smarty模板执行原理

Smarty模板执行原理

为了实现程序的业务逻辑和内容表现页面的分离从而提高开发速度，php 引入了模板引擎的概念，php 模板引擎里面最流行的可以说是smarty了，smarty因其功能强大而且速度快而被广大php web开发者所认可。本文将记录一下smarty模板引擎的工作执行原理，算是加深一下理解。 其实所有的模板引擎的工作原理是差不多的，无非就是在php程序里面用正则匹配将模板里面的标签替换为php代码从而将两者
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2