JUC

ArrayBlockingQueue源码分析

王守钰 2020-03-06 11:03:33

ArrayBlockingQueue的继承关系

image

主要属性

 /** 队列存储元素 */
final Object[] items;

/** 取出元素的指针 */
int takeIndex;

/** 放元素的指针 */
int putIndex;

/** 元素的数量 */
int count;

/** 保证并发访问的锁 */
final ReentrantLock lock;

/** 非空条件 */
private final Condition notEmpty;

/** 非满条件 */
private final Condition notFull;
  • 利用数组存储元素;
  • 通过放指针和取指针来标记下一次操作的位置;
  • 利用重入锁来保证并发安全;

构造方法

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();
}
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 exclusion
    try {
        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();
    }
}
  • 初始化ArrayBlockingQueue必须要传入容量大小;
  • 可以通过构造方法来控制重入锁是公平锁还是非公平锁;

入列

public boolean add(E e) {
    return super.add(e);
}
public boolean add(E e) {
    // 调用offer(e)如果成功返回true,否则抛出异常
    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();
    }
}

public void put(E e) throws InterruptedException {
    checkNotNull(e);
    final ReentrantLock lock = this.lock;
    // 加锁,如果线程中断了抛出异常
    lock.lockInterruptibly();
    try {
        // 如果数组满了,使用notFull等待
        // notFull等待的意思是说现在队列满了
        // 只有取走一个元素后,队列才不满
        // 然后唤醒notFull,然后继续现在的逻辑
        // 这里之所以使用while而不是if
        // 是因为有可能多个线程阻塞在lock上
        // 即使唤醒了可能其它线程先一步修改了队列又变成满的了
        // 这时候需要再次等待
        while (count == items.length)
            notFull.await();
        // 入列
        enqueue(e);
    } finally {
        // 解锁
        lock.unlock();
    }
}

public boolean offer(E e, long timeout, TimeUnit unit)
    throws InterruptedException {

    checkNotNull(e);
    long nanos = unit.toNanos(timeout);
    final ReentrantLock lock = this.lock;
    // 加锁
    lock.lockInterruptibly();
    try {
        // 如果数组满了,就阻塞nanos纳秒
        // 如果唤醒这个线程时依然没有空间且时间到了就返回false
        while (count == items.length) {
            if (nanos <= 0)
                return false;
            nanos = notFull.awaitNanos(nanos);
        }
        enqueue(e);
        return true;
    } 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)
        putIndex = 0;
    // 数量加1    
    count++;
    // 唤醒notEmpty,因为入队了一个元素,所以肯定不为空了
    notEmpty.signal();
}
  • add(e)时如果队列满了则抛出异常;
  • offer(e)时如果队列满了则返回false;
  • put(e)时如果队列满了则使用notFull等待;
  • offer(e, timeout, unit)时如果队列满了则等待一段时间后如果队列依然满就返回false;
  • 利用放指针循环使用数组来存储元素;

出列

public E remove() {
    // 调用poll()方法出队
    E x = poll();
    if (x != null)
        // 如果有元素出队就返回这个元素
        return x;
    else
        // 如果没有元素出队就抛出异常
        throw new NoSuchElementException();
}

public E poll() {
    final ReentrantLock lock = this.lock;
    // 加锁
    lock.lock();
    try {
        // 如果队列没有元素则返回null,否则出队
        return (count == 0) ? null : dequeue();
    } finally {
        lock.unlock();
    }
}

public E take() throws InterruptedException {
    final ReentrantLock lock = this.lock;
    // 加锁
    lock.lockInterruptibly();
    try {
        // 如果队列无元素,则阻塞等待在条件notEmpty上
        while (count == 0)
            notEmpty.await();
        // 有元素了再出队
        return dequeue();
    } finally {
        // 解锁
        lock.unlock();
    }
}

public E poll(long timeout, TimeUnit unit) throws InterruptedException {
    long nanos = unit.toNanos(timeout);
    final ReentrantLock lock = this.lock;
    // 加锁
    lock.lockInterruptibly();
    try {
        // 如果队列无元素,则阻塞等待nanos纳秒
        // 如果下一次这个线程获得了锁但队列依然无元素且已超时就返回null
        while (count == 0) {
            if (nanos <= 0)
                return null;
            nanos = notEmpty.awaitNanos(nanos);
        }
        return dequeue();
    } finally {
        lock.unlock();
    }
}

private E dequeue() {
    final Object[] items = this.items;
    @SuppressWarnings("unchecked")
    // 取取指针位置的元素
    E x = (E) items[takeIndex];
    // 把取指针位置设为null
    items[takeIndex] = null;
    // 取指针前移,如果数组到头了就返回数组前端循环利用
    if (++takeIndex == items.length)
        takeIndex = 0;
    // 元素数量减1
    count--;
    if (itrs != null)
        itrs.elementDequeued();
    // 唤醒notFull条件
    notFull.signal();
    return x;
}
  • remove()时如果队列为空则抛出异常;
  • poll()时如果队列为空则返回null;
  • take()时如果队列为空则阻塞等待在条件notEmpty上;
  • poll(timeout, unit)时如果队列为空则阻塞等待一段时间后如果还为空就返回null;
  • 利用取指针循环从数组中取元素;

总结

  • ArrayBlockingQueue不需要扩容,因为是初始化时指定容量,并循环利用数组;
  • ArrayBlockingQueue利用takeIndex和putIndex循环利用数组;
  • 入队和出队各定义了四组方法为满足不同的用途;
  • 利用重入锁和两个条件保证并发安全;

ArrayBlockingQueue的缺点

  • 队列长度固定且必须在初始化时指定,所以使用之前一定要慎重考虑好容量;
  • 如果消费速度跟不上入队速度,则会导致提供者线程一直阻塞,且越阻塞越多,非常危险;

BlockingQueue中的方法

操作抛出异常返回特定值阻塞超时
入队add(e)offer(e)——falseput(e)offer(e, timeout, unit)
出队remove()poll()——nulltake()poll(timeout, unit)
检查element()peek()——null--