Java常见的阻塞队列总结

java阻塞队列

阻塞队列和普通队列主要区别在阻塞二字：

• 阻塞添加：队列已满时，添加元素线程会阻塞，直到队列不满时才唤醒线程执行添加操作
• 阻塞删除：队列元素为空时，删除元素线程会阻塞，直到队列不为空再执行删除操作

常见的阻塞队列有 linkedblockingqueue 和 arrayblockingqueue，其中它们都实现 blockingqueue 接口，该接口定义了阻塞队列需实现的核心方法：

public interface blockingqueue<e> extends queue<e> {
	// 添加元素到队尾，成功返回true，队列满抛出异常 illegalstateexception
    boolean add(e e);
	// 添加元素到队尾，成功返回 true，队列满返回 false
    boolean offer(e e);
	// 阻塞添加
    void put(e e) throws interruptedexception;
	// 阻塞添加，包含最大等待时长
    boolean offer(e e, long timeout, timeunit unit) throws interruptedexception;
	// 阻塞移除队顶元素
    e take() throws interruptedexception;
	// 阻塞移除队顶元素，包含最大等待时长
    e poll(long timeout, timeunit unit) throws interruptedexception;
	// 返回可以添加到队列不阻塞的最大数量
    int remainingcapacity();
	// 如果存在元素则删除，成功返回 true，失败返回 false
    boolean remove(object o);
	// 是否包含某元素
    public boolean contains(object o);
    // 批量移除元素并添加入指定集合
    int drainto(collection<? super e> c);
	// 批量移除包含最大数量
    int drainto(collection<? super e> c, int maxelements);
}

除了上面的方法，还有三个继承自 queue 接口的方法常常被用到：

// 获取队列头元素，不删除，没有抛出异常 nosuchelementexception
e element();
// 获取队列头元素，不删除，没有返回 null
e peek();
// 获取并移除队列头元素，没有返回 nul
e poll();

根据具体作用，方法可以被分为以下三类：

• 添加元素类：add() 成功返回 true，失败抛异常、offer() 成功返回 true，失败返回 false，可以定义最大等待时长、put() 阻塞方法
• 删除元素类：remove() 成功返回 true，失败返回 false、poll() 成功返回被移除元素，为空返回 null、take() 阻塞方法
• 查询元素类：element() 成功返回元素，否则抛出异常、peek() 返回对应元素或 null

根据方法类型又可以分为阻塞和非阻塞，其中 put()、take() 是阻塞方法，带最大等待时长的 offer() 和 poll() 也是阻塞方法，其余都是非阻塞方法，阻塞队列基于上述方法实现

arrayblockingqueue 基于数组实现，满足队列先进先出特性，下面我们通过一段代码初步认识：

public class arrayblockingqueuetest {

    arrayblockingqueue<testproduct> queue = new arrayblockingqueue<testproduct>(1);

    public static void main(string[] args) {
        arrayblockingqueuetest test = new arrayblockingqueuetest();
        new thread(test.new product()).start();
        new thread(test.new customer()).start();
    }

    class product implements runnable {
        @override
        public void run() {
            while (true) {
                try {
                    queue.put(new testproduct());
                    system.out.println("生产者创建产品等待消费者消费");
                } catch (interruptedexception e) {
                    e.printstacktrace();
                }
            }
        }
    }

    class customer implements runnable {
        @override
        public void run() {
            while (true) {
                try {
                    thread.sleep(1000);
                    queue.take();
                    system.out.println("消费者消费产品等待生产者创建");
                } catch (interruptedexception e) {
                    e.printstacktrace();
                }
            }
        }
    }

    class testproduct {
    }

}

上述代码比较简单，在一个容量为1的阻塞队列中，生产者和消费者由于容量限制依次阻塞运行。

arrayblockingqueue 基于 reentrantlock 锁和 condition 等待队列实现，因此存在公平和非公平的两种模式。公平场景下所有被阻塞的线程按照阻塞顺序执行，非公平场景下，队列中的线程和恰好准备进入队列的线程竞争，谁抢到就是谁的。默认使用非公平锁，因为效率更高：

public arrayblockingqueue(int capacity) {
    this(capacity, false);
}
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();
}

从代码可以看出，arrayblockingqueue 通过一个 reentrantlock 锁以及两个 condition 等待队列实现，它的属性如下：

public class arrayblockingqueue<e> extends abstractqueue<e> implements blockingqueue<e>, java.io.serializable {
	// 保存数据的数组
    final object[] items;
	// 移除元素的索引
    int takeindex;
	// 添加元素的索引
    int putindex;
	// 元素数量
    int count;
	// 用于并发控制的锁
    final reentrantlock lock;
	// 不为空，用于take()操作
    private final condition notempty;
	// 不满，用于put()操作
    private final condition notfull;
	// 迭代器
    transient itrs itrs = null;
}

从代码可以看出，arrayblockingqueue 使用同一个锁、移除元素和添加元素通过数组下标的方式记录，分表表示队列头和队列尾。通过两个等待队列分别阻塞 take() 和 put() 方法，下面我们直接看源码：

public boolean add(e e) {
    if (offer(e))
        return true;
    else
        throw new illegalstateexception("queue full");
}
public boolean offer(e e) {
	// 检查是否为空
    checknotnull(e);
    final reentrantlock lock = this.lock;
    lock.lock();
    try {
    	// 判断队列是否已满
        if (count == items.length)
            return false;
        else {
            enqueue(e);
            return true;
        }
    } finally {
        lock.unlock();
    }
}
private void enqueue(e x) {
    final object[] items = this.items;
    // 赋值保存数据
    items[putindex] = x;
    // 循环复用空间
    if (++putindex == items.length)
        putindex = 0;
    count++;
    // 唤醒take线程
    notempty.signal();
}

从代码可以看出：add() 方法基于 offer() 方法实现，offer() 方法添加失败返回 false 后，add() 方法抛出异常。offer() 方法会加锁，保证线程安全，队列没满时执行入队操作，入队操作通过操作数组实现，并且通过循环复用数组空间。元素添加成功后队列不为空，调用 signal() 方法唤醒移除元素的阻塞线程，最后我们看 put() 方法：

public void put(e e) throws interruptedexception {
	// 判断不为空
	checknotnull(e);
	final reentrantlock lock = this.lock;
	lock.lockinterruptibly();
	try {
		// 队列满就挂起在等待队列
	    while (count == items.length)
	        notfull.await();
	    enqueue(e);
	} finally {
	    lock.unlock();
	}
}

从代码可以看出，当队列满时，当前线程会被挂起到等待队列中，直到队列不满时被唤醒执行添加操作。下面我们看删除操作：

public boolean remove(object o) {
	// 判断是否为 null
    if (o == null) return false;
    final object[] items = this.items;
    final reentrantlock lock = this.lock;
    lock.lock();
    try {
        if (count > 0) {
            final int putindex = this.putindex;
            int i = takeindex;
            // 从移除下标开始遍历到添加新元素的下标
            do {
                if (o.equals(items[i])) {
                    removeat(i);
                    return true;
                }
                // 循环判断，移除下标可能大于添加下标（添加下标二次遍历时）
                if (++i == items.length)
                    i = 0; 
            } while (i != putindex);
        }
        return false;
    } finally {
        lock.unlock();
    }
}
void removeat(final int removeindex) {
	final object[] items = this.items;
	// 要删除的元素正好是移除下标
	if (removeindex == takeindex) {
	    items[takeindex] = null;
	    // 循环删除
	    if (++takeindex == items.length)
	        takeindex = 0;
	    count--;
	    if (itrs != null)
	        itrs.elementdequeued();
	} else {
	    final int putindex = this.putindex;
	    // 如果不是移除下标，从该下标开始到添加下标，所有元素左移一位
	    for (int i = removeindex;;) {
	        int next = i + 1;
	        if (next == items.length)
	            next = 0;
	        if (next != putindex) {
	        	// 向左移除
	            items[i] = items[next];
	            i = next;
	        } else {
	        	// 最后put下标置为null
	            items[i] = null;
	            this.putindex = i;
	            break;
	        }
	    }
	    count--;
	    // 更新迭代器
	    if (itrs != null)
	        itrs.removedat(removeindex);
	}
	notfull.signal();
}

remove() 和 poll()、take() 不同，它可以删除指定的元素。这里需要考虑删除的元素不是移除索引指向的情况，从代码可以看出，当要删除的元素不是移除索引指向的元素时，将所有从被删除元素下标开始到添加元素下标所有元素左移一位。

public e poll() {
	final reentrantlock lock = this.lock;
	lock.lock();
	try {
	    return (count == 0) ? null : dequeue();
	} finally {
	    lock.unlock();
	}
}
private e dequeue() {
	final object[] items = this.items;
	e x = (e) items[takeindex];
	items[takeindex] = null;
	if (++takeindex == items.length)
	    takeindex = 0;
	count--;
	if (itrs != null)
	    itrs.elementdequeued();
	// 移除元素后唤醒put()添加线程
	notfull.signal();
	return x;
}

相比 remove() 方法，poll() 方法简单了很多，这里不做赘述，下面我们看 take()：

public e take() throws interruptedexception {
	final reentrantlock lock = this.lock;
	lock.lockinterruptibly();
	try {
		// 队列为空就挂起
	    while (count == 0)
	        notempty.await();
	    return dequeue();
	} finally {
	    lock.unlock();
	}
}

take() 方法和 put() 方法可以说基本一致，相对也比较简单，最后我们来看看两个查询方法：

public e element() {
    e x = peek();
    if (x != null)
        return x;
    else
        throw new nosuchelementexception();
}
public e peek() {
    final reentrantlock lock = this.lock;
    lock.lock();
    try {
    	// 直接返回移除元素下标对应的元素，也就是队列头
        return itemat(takeindex); 
    } finally {
        lock.unlock();
    }
}
final e itemat(int i) {
    return (e) items[i];
}

element() 基于 peek() 方法实现实现、当队列为空时，peek() 方法返回 null，element() 抛出异常。关于 arrayblockingqueue 就介绍到这里

linkedblockingqueue 基于链表实现，它的属性如下：

public class linkedblockingqueue<e> extends abstractqueue<e> implements blockingqueue<e>, java.io.serializable {
	// 链表节点，存储元素
    static class node<e> {
        e item;
        node<e> next;
        node(e x) { item = x; }
    }
	// 链表容量
    private final int capacity;
	// 当前元素数量
    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();
}

从代码可以看出，元素被封装为 node 节点保存在单向链表中，其中链表默认长度为 integer.max_value，因此在使用时需注意内存溢出：当添加元素速度大于删除元素速度时，队列最终会记录到大量不会用到并且无法回收的对象，导致内存溢出。

arrayblockingqueue 和 linkedblockingqueue 的主要区别在于 reentrantlock 锁的数量和等待队列，linkedblockingqueue 用到两个锁和两个等待队列，也就是说添加和删除操作可以并发执行，整体效率更高。下面我们直接看代码：

public boolean add(e e) {
     if (offer(e))
         return true;
     else
         throw new illegalstateexception("queue full");
}
public boolean offer(e e) {
	// 元素为空抛出异常
	if (e == null) throw new nullpointerexception();
	// 获取当前队列容量
	final atomicinteger count = this.count;
	// 队列已满时直接返回false
	if (count.get() == capacity)
	    return false;
	int c = -1;
	node<e> node = new node<e>(e);
	// 获取添加锁
	final reentrantlock putlock = this.putlock;
	putlock.lock();
	try {
		// 二次判断，因为上面判断时未加锁，数据可能已更新
	    if (count.get() < capacity) {
	    	// 入队操作
	        enqueue(node);
	        // 获取还未添加元素前，队列的容量
	        c = count.getandincrement();
	        if (c + 1 < capacity)
	        	// 唤醒其它添加元素的线程
	            notfull.signal();
	    }
	} finally {
	    putlock.unlock();
	}
	// 如果添加前队列没有数据，也就是说现在有一条数据时
	if (c == 0)
		// 唤醒take线程 
	  	signalnotempty();
	return c >= 0;
}
private void enqueue(node<e> node) {
     last = last.next = node;
}
private void signalnotempty() {
	// 唤醒take线程前必须获取对应take锁
    final reentrantlock takelock = this.takelock;
    takelock.lock();
        notempty.signal();
    } finally {
        takelock.unlock();
    }
}

这里有以下几点需要我们注意：

1.linkedblockingqueue count 属性必须通过并发类封装，因为可能存在添加、删除两个线程并发执行，需考虑同步

2.这里需要判断两次的主要原因在于方法开始时并没有加锁，数值可能改变，因此在获取到锁后需要二次判断

3.和 arrayblockingqueue 不同，linkedblockingqueue 在队列不满时会唤醒添加线程，这样做的原因是 linkedblockingqueue 中添加和删除操作使用不同的锁，各自只需管好自己，还可以提高吞吐量。而 arrayblockingqueue 使用唯一锁，这样做会导致移除线程永远不被唤醒或添加线程永远不被唤醒，吞吐量较低

4.添加元素前队列长度为0才唤醒移除线程，因为队列长度为0时，移除线程肯定已经挂起，此时唤醒一个移除线程即可。因为移除线程和添加线程类似，都会自己唤醒自己。而 c>0 时只会有两种情况：存在移除线程在运行，如果有会递归唤醒，无须我们参与、不存在移除线程运行，此时也无须我们参与，等待调用 take()、poll() 方法即可

5.唤醒只针对 put()、take() 方法阻塞的线程，offer() 方法直接返回（不包含最大等待时长），不参与唤醒场景

下面我们来看 put() 阻塞方法的实现：

public void put(e e) throws interruptedexception {
    if (e == null) throw new nullpointerexception();
    int c = -1;
    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();
}

从代码可以看出，put() 方法和 offer() 方法唯一区别在于自身通过 condition 阻塞挂起到等待队列，其余基本相同。至此关于添加操作介绍完毕，下面我们看移除方法：

public boolean remove(object o) {
	if (o == null) return false;
	// 同时加两个锁
	fullylock();
	try {
		// 循环查找
	    for (node<e> trail = head, p = trail.next; p != null; trail = p, p = p.next) {
	        if (o.equals(p.item)) {
	            unlink(p, trail);
	            return true;
	        }
	    }
	    return false;
	} finally {
	    fullyunlock();
	}
}
void unlink(node<e> p, node<e> trail) {
	// p是要溢出的节点，trail是它的前驱节点
	// 方便gc
    p.item = null;
    // 引用取消
    trail.next = p.next;
    if (last == p)
        last = trail;
    if (count.getanddecrement() == capacity)
        notfull.signal();
}
void fullylock() {
    putlock.lock();
    takelock.lock();
}
void fullyunlock() {
    takelock.unlock();
    putlock.unlock();
}

从代码可以看出，remove() 方法只会在操作前容量不满时唤醒创建线程，并不会唤醒移除线程。并且由于我们不确定要删除元素的位置，因此此时需要加两个锁，确保数据安全。

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();
    }
    // 移除前如果队列是满的，唤醒添加线程
    if (c == capacity)
        signalnotfull();
    return x;
}
private e dequeue() {
	node<e> h = head;
	// 获取要删除的节点
	node<e> first = h.next; 
	// 清除原来的头结点(方便gc)
	h.next = h; 
	// 设置新的头结点
	head = first;
	// 获取返回值
	e x = first.item;
	// 新头结点置为空
	first.item = null;
	return x;
}

需要注意的一点，每次出队时更换 head 节点，head 节点本身不保存数据，head.next 记录下次需要出队的元素，每次出队后 head.next 变为新的 head 节点返回并置为 null

poll() 方法和上面提到的 offer() 方法基本镜像相同，这里我再不做过多赘述

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;
}

take() 方法和 poll() 方法类似，区别在于新增了阻塞逻辑。至此关于溢出元素方法介绍完毕，最后我们看看查询方法源码：

public linkedblockingqueue(int capacity) {
   if (capacity <= 0) throw new illegalargumentexception();
   this.capacity = capacity;
   last = head = new node<e>(null);
}
public e element() {
    e x = peek();
    if (x != null)
        return x;
    else
        throw new nosuchelementexception();
}
public e peek() {
    if (count.get() == 0)
        return null;
    final reentrantlock takelock = this.takelock;
    takelock.lock();
    try {
        node<e> first = head.next;
        if (first == null)
            return null;
        else
            return first.item;
    } finally {
        takelock.unlock();
    }
}

从代码可以看出，默认 head 和 last 头尾节点都为 null，入队时直接从 next 开始操作，也就是说 head 节点不保存数据。

最后我们来看看有最大等待时长的 offer() 方法：

public boolean offer(e e, long timeout, timeunit unit) throws interruptedexception {
	if (e == null) throw new nullpointerexception();
	// 将时间转换成纳秒
	long nanos = unit.tonanos(timeout);
	int c = -1;
	// 获取锁
	final reentrantlock putlock = this.putlock;
	// 获取当前队列大小
	final atomicinteger count = this.count;
	// 可中断锁
	putlock.lockinterruptibly();
	try {
	    while (count.get() == capacity) {
	    	// 小于0说明已到达最大等待时长
	        if (nanos <= 0)
	            return false;
	        // 如果队列已满，根据等待队列阻塞等待
	        nanos = notfull.awaitnanos(nanos);
	    }
	    // 队列没满直接入队
	    enqueue(new node<e>(e));
	    c = count.getandincrement();
	    if (c + 1 < capacity)
	        notfull.signal();
	} finally { 
	    putlock.unlock();
	}
	if (c == 0)
	    signalnotempty();
	return true;
}
 public final long awaitnanos(long nanostimeout) throws interruptedexception {
    if (thread.interrupted()) throw new interruptedexception();
	// 将当前线程封装为 aqs node 类加入等待队列
    node node = addconditionwaiter();
    // 释放锁
    int savedstate = fullyrelease(node);
    //计算过期时间
    final long deadline = system.nanotime() + nanostimeout;
    int interruptmode = 0;
    // 当前线程没有唤醒进入同步队列时
    while (!isonsyncqueue(node)) {
    	// 已经等待相应时间，删除当前节点，将状态设置为已关闭从队列删除
        if (nanostimeout <= 0l) {
            transferaftercancelledwait(node);
            break;
        }
        // 判断是否超时
        if (nanostimeout >= spinfortimeoutthreshold)
        	// 挂起线程
            locksupport.parknanos(this, nanostimeout);
        // 判断线程状态是否被中断
        if ((interruptmode = checkinterruptwhilewaiting(node)) != 0)
            break;
        // 重新计算剩余等待时间
        nanostimeout = deadline - system.nanotime();
    }
    // 被唤醒后执行自旋操作争取获得锁，同时判断线程是否被中断
    if (acquirequeued(node, savedstate) && interruptmode != throw_ie)
        interruptmode = reinterrupt;
    if (node.nextwaiter != null)
    	// 清理等待队列中不为condition状态的线程
        unlinkcancelledwaiters();
    // 判断是否被中断
    if (interruptmode != 0)
    	// 抛出异常或中断线程，独占模式抛出异常，共享模式中断线程
        reportinterruptafterwait(interruptmode);
    // 返回时差,如果成功当前时间小于最大等待时长，返回值大于0，否则返回值小于0
    return deadline - system.nanotime();
}

从代码可以看出，包含最大等待时长的 offer()、poll() 方法通过循环判断时间是否超时的方式挂起在等待队列，达到最大等待时长还未被唤醒或没被执行就返回

arrayblockingqueue 和 linkedblockingqueue 对比：

• 大小不同，一个有界，一个*。arrayblockingqueue 必须指定初始大小，linkedblockingqueue *时可能内存溢出
• 一个采用数组，一个采用链表，数组保存无须创建新对象，链表需创建 node 对象
• 锁机制不同，arrayblockingqueue 添加删除操作使用同一个锁，两者操作不能并发执行。linkedblockingqueue 添加和删除使用不同锁，添加和删除操作可并发执行，整体效率 linkedblockingqueue 更高

到此这篇关于java常见的阻塞队列总结的文章就介绍到这了,更多相关java阻塞队列内容请搜索以前的文章或继续浏览下面的相关文章希望大家以后多多支持！