@yexiaoqi
2022-04-21T17:09:28.000000Z
字数 1662
阅读 489
刷题
import java.util.concurrent.locks.Condition;
import java.util.concurrent.locks.ReentrantLock;
/**
* 要求:用数组实现一个阻塞队列
* 考察:java.util.concurrent.ArrayBlockingQueue的实现原理
* 思路:1.用数组实现队列,考虑使用环形数组,用两个指针putIndex、takeIndex表示下一个要入队、出队的位置,
* 入队/出队到数组末尾时都从零开始,count为元素数量,count=0说明队列为空,count=数组size说明队列已满
* 2.给队列加上阻塞能力和保证线程安全,考虑使用lock+Condition.await
*/
public class ArrayBlockingQueue<E> {
final Object[] items;
int putIndex;
int takeIndex;
int count;
ReentrantLock lock;
private final Condition notEmpty;
private final Condition notFull;
public ArrayBlockingQueue(int capacity) {
if (capacity <= 0)
throw new IllegalArgumentException();
this.items = new Object[capacity];
// 创建 lock 对象
lock = new ReentrantLock();
// 队列[非空]Condition
notEmpty = lock.newCondition();
// 队列[不满]Condition
notFull = lock.newCondition();
}
/**
* 为什么while循环需要放在锁内?
* 如果不放在锁内,则可能会出现多个线程同时看到满足条件,进而去加锁入队。虽然入队还是在临界区,
* 但会出现队列已满,仍然在执行入队操作的情况。和单例的双检查锁中少一个检查的问题类似
*/
public void put(E e) throws InterruptedException {
final ReentrantLock lock = this.lock;
lock.lockInterruptibly();
try {
while (count == items.length)
//如果队列已满,调用await()方法释放锁并阻塞,被其他线程signal唤醒后会重新抢锁,
//再次获取锁后会继续走到while循环判断条件的地方
notFull.await();
//如果还可以存,则执行入队操作
enqueue(e);
//唤醒一个线程
notEmpty.signal();
} finally {
lock.unlock();
}
}
public E take() throws InterruptedException {
final ReentrantLock lock = this.lock;
lock.lockInterruptibly();
try {
while (count == 0)
//如果队列为空,调用await()方法释放和notEmpty关联的锁并阻塞
notEmpty.await();
E e = dequeue();
notFull.signal();
return e;
} finally {
lock.unlock();
}
}
// 入队
private void enqueue(E e) {
Object[] items = this.items;
items[putIndex] = e;
if (++putIndex == items.length) putIndex = 0;
count++;
}
// 出队
private E dequeue() {
Object[] items = this.items;
E e = (E) items[takeIndex];
items[takeIndex] = null;
if (++takeIndex == items.length) takeIndex = 0;
count--;
return e;
}
}