文档章节

04.JUC 集合 - LinkedBlockingQueue

夕阳晒裤衩
 夕阳晒裤衩
发布于 2017/02/23 16:53
字数 959
阅读 11
收藏 0

##基本概念

LinkedBlockingQueue 是一个用链表实现的有界阻塞队列

LinkedBlockingQueue 按照先进先出的原则对元素进行排序。

LinkedBlockingQueue 采用了双锁、双条件队列来提高读写效率。


##内部构造

LinkedBlockingQueue 内部维护着一个单向链表,且链表头节点的值永远为空。如下图所示:

输入图片说明

下面来看它的构成:

  • Node ,节点
static class Node<E> {
	E item;

	Node<E> next;

	Node(E x) {
		item = x;
	}
}
  • 构造函数
private transient Node<E> head;
private transient Node<E> last;
private final int capacity;

public LinkedBlockingQueue() {
	// 该队列是有界的,若不指定容量,默认为最大值
	this(Integer.MAX_VALUE);
}

public LinkedBlockingQueue(int capacity) {
	if (capacity <= 0){
		// 抛出异常...
	}

	this.capacity = capacity;
	last = head = new Node<E>(null);
}

##双锁机制

由于采用了双锁机制,因此它的出队、入队操作可以同时进行,从而提高效率。

// 用于入队操作
private final ReentrantLock putLock = new ReentrantLock();
private final Condition notFull = putLock.newCondition();

// 用于出队操作
private final ReentrantLock takeLock = new ReentrantLock();
private final Condition notEmpty = takeLock.newCondition();

由于出入队可以同时进行,因此必须避免冲突问题。

  • 同一元素操作冲突:由于 LinkedBlockingQueue 采用了 FIFO(先进先出)的原则,实际上是双端操作,不会存在冲突。并且在其内部定义了两个变量:head、last。
// 出队修改头节点
private transient Node<E> head;

// 入队修改尾节点
private transient Node<E> last;
  • 元素数量操作冲突:因为入队数量要+1,出队数量要-1,因此需要保证它的可见性,这里采用了这里采用原子类来实现:
private final AtomicInteger count = new AtomicInteger(0);

##入队操作

  • offer,该操作成功返回 true,失败返回 false。
public boolean offer(E e) {
	if (e == null){
		// 抛出异常...
	}

	// 判断元素的个数是否超过容量4
	final AtomicInteger count = this.count;
	if (count.get() == capacity){
		return false;
	}
	
	int c = -1;
	
	Node<E> node = new Node(e);

	// 加锁
	final ReentrantLock putLock = this.putLock;
	putLock.lock();
	
	try {
		// 再次判断,存在等待获取锁期间,其他线程执行入队操作。
		if (count.get() < capacity) {
			// 入队操作
			enqueue(node);

			// 注意:数量+1,返回的旧值
			c = count.getAndIncrement();
			if (c + 1 < capacity){
				// 队列未满,唤醒因为队列满而阻塞的线程
				notFull.signal();
			}
		}
	} finally {
		putLock.unlock();
	}

	// 为 0 表示之前队列是空的,唤醒出队时因为空队列而进入 notEmpty 条件等待队列的线程
	if (c == 0){
		signalNotEmpty();
	}

	return c >= 0;
}
  • put,该操作成功返回 true,失败则进入阻塞。
 private final AtomicInteger count = new AtomicInteger(0);

public void put(E e) throws InterruptedException {

	if (e == null){
		// 抛出异常...
	}

	int c = -1;
	Node<E> node = new Node(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();
	}
}
  • 关键
private void enqueue(Node<E> node) {
	last = last.next = node;
}

private void signalNotEmpty() {
	final ReentrantLock takeLock = this.takeLock;
	takeLock.lock();
	try {
		notEmpty.signal();
	} finally {
		takeLock.unlock();
	}
}
  • 入队操作的过程如下所示:

输入图片说明


##出队操作

  • poll,成功返回被移除的元素,失败返回 null。
public E poll() {
	final AtomicInteger count = this.count;
	if (count.get() == 0){
		return null;
	}

	E x = null;
	int c = -1;

	// 加锁
	final ReentrantLock takeLock = this.takeLock;
	takeLock.lock();
	
	try {
		if (count.get() > 0) {
			// 关键 -> 出队
			x = dequeue();
			c = count.getAndDecrement();
			if (c > 1){
				notEmpty.signal();
			}
		}
	} finally {
		takeLock.unlock();
	}

	// 表示出队前满队列,唤醒因入队时满队列而进入 notFull 条件等待队列的线程。
	if (c == capacity){
		signalNotFull();
	}
	return x;
}
  • 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;
}
  • 关键
private E dequeue() {
	// 头节点、以及它的后继节点
	Node<E> h = head;
	Node<E> first = h.next;

	// 等于 h.next = null,即断开后指针
	h.next = h; 

	// 设置新的头节点
	head = first;

	E x = first.item;

	// 将节点的值置空
	first.item = null;
	return x;
}

private void signalNotFull() {
	final ReentrantLock putLock = this.putLock;
	putLock.lock();
	try {
		notFull.signal();
	} finally {
		putLock.unlock();
	}
}
  • 出队过程如下图所示:

输入图片说明


© 著作权归作者所有

共有 人打赏支持
夕阳晒裤衩
粉丝 4
博文 15
码字总数 18485
作品 0
天津
程序员
Java集合--阻塞队列(LinkedBlockingQueue)

1. LinkedBlockingQueue 上篇中,说到了ArrayBlockingQueue阻塞队列。在ArrayBlockingQueue中,底层使用了数组结构来实现。 那么,提到数组了就不得不提及链表。作为两对成双成对的老冤家,链...

贾博岩
2017/12/10
0
0
并发队列ConcurrentLinkedQueue和阻塞队列LinkedBlockingQueue用

在Java多线程应用中,队列的使用率很高,多数生产消费模型的首选数据结构就是队列。Java提供的线程安全的Queue可以分为阻塞队列和非阻塞队列,其中阻塞队列的典型例子是BlockingQueue,非阻塞...

凯文加内特
2014/07/31
0
0
并发队列ConcurrentLinkedQueue和阻塞队列LinkedBlockingQueue用法

在Java多线程应用中,队列的使用率很高,多数生产消费模型的首选数据结构就是队列。Java提供的线程安全的Queue可以分为阻塞队列和非阻塞队列,其中阻塞队列的典型例子是BlockingQueue,非阻塞...

F风向标F
2013/12/03
0
0
Java: Queue 各种方法的细小区别

Java提供了Quere,相当好用,在1.5版本中又有增强。 add 增加一个元索 如果队列已满,则抛出一个IIIegaISlabEepeplian异常 remove 移除并返回队列头部的元素 如果队列为空,则抛出一个NoSuc...

xiaomin0322
03/06
0
0
集合框架 Queue---BlockingQueue详解

本例介绍一个特殊的队列:BlockingQueue,如果BlockingQueue是空的,从BlockingQueue取东西的操作将会被阻断进入等待状态,直到BlockingQueue进了东西才会被唤醒,同样,如果BlockingQueue是...

长平狐
2012/11/28
587
0

没有更多内容

加载失败,请刷新页面

加载更多

TypeScript基础入门之高级类型的字符串字面量类型

转发TypeScript基础入门之高级类型的字符串字面量类型 高级类型 字符串字面量类型 字符串字面量类型允许你指定字符串必须的固定值。 在实际应用中,字符串字面量类型可以与联合类型,类型保护...

durban
19分钟前
2
0
iOS权限授权添加

<!-- 相册 --> <key>NSPhotoLibraryUsageDescription</key> <string>App需要您的同意,才能访问相册</string> <!-- 相册写入 --> <key>NSPhotoLibraryAddUsageDescription</key> <string>App......

RainOrz
24分钟前
1
0
支配树(Dominator Tree)

MAT中的支配树 在使用MAT分析项目的内存泄漏问题时,其中有一个支配树(Dominator)视图。如果我们把Java对象之间的引用关系看做一张有向图(可以存在环)的话,对象的支配树体现了对象之间的...

akane_oimo
25分钟前
1
0
xshell官网下载及安装(免费版本)

百度搜索xshell,点击xshell官网下载链接,如图 然后点击下图的按钮 点击Latest Products,可以下载最新版本,选择要下载的版本,点击下载 选择上面红框里面的,并填写内容,submit之后会有邮...

曾大大胖
30分钟前
2
0
Android 调用系统分享文字、图片、文件,可直达微信、朋友圈、QQ、QQ空间、微博

兼容SDK 18以上的系统,直接调用系统分享功能,分享文本、图片、文件到第三方APP,如:微信、QQ、微博等 因为偷懒,可直达微信、朋友圈、QQ、QQ空间、微博的分享仅写了图片分享的,其他的文本...

她叫我小渝
32分钟前
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部