實現(xiàn)一個自定義的有界阻塞隊列. 當(dāng)隊列為空時,阻塞直到有可取的元素被喚醒;當(dāng)隊列滿時,阻塞直到有空間存放元素被喚醒.
分析:
1)為實現(xiàn)有界: 采用數(shù)組進(jìn)行存儲元素模擬隊列,為了提高空間的利用率,使用循環(huán)隊列
2)為實現(xiàn)阻塞和喚醒,構(gòu)造同步機(jī)制,使用內(nèi)置鎖(synchronized)或者顯式鎖(Lock)
1,使用內(nèi)置鎖(synchronized)
class BlockingQueueWithSynchronized<T> {
private int tail, head, count;
private T[] elems;
BlockingQueueWithSynchronized(int capacity) {
if (capacity <= 0) {
throw new IllegalArgumentException("capacity需要大于0");
}
elems = (T[]) new Object[capacity];
}
public synchronized T take() throws InterruptedException {
while (isEmpty()) {
wait();
}
T t = elems[head];
elems[head] = null;
head++;
if (head == elems.length) {
head = 0;
}
count--;
notifyAll();
return t;
}
public synchronized void put(T t) throws InterruptedException {
while (isFull()) {
wait();
}
elems[tail] = t;
tail++;
if (tail == elems.length) {
tail = 0;
}
count++;
notifyAll();
}
public synchronized boolean isFull() {
return elems.length == count;
}
public synchronized boolean isEmpty() {
return count == 0;
}
}
在這里每次取(take)和每次存(put)都會進(jìn)行喚醒操作;但是執(zhí)行喚醒操作后,被喚醒的線程可能再次被阻塞.
例如,當(dāng)隊列為空,進(jìn)行取操作被阻塞,當(dāng)放入元素后喚醒所有的線程(notifyAll),但是只有一個可用元素, 所有被喚醒的取元素線程都將進(jìn)行競爭,只有一個線程能最終獲取獲取元素,其余取元素線程會再次被阻塞掛起.
那么將會問為何不使用notify呢?這樣就可以避免喚醒所有的線程,但是問題來了, notify只能喚醒一個線程,如果喚醒的是存放元素的線程,那么取元素的線程就喪失了一次獲取的機(jī)會.
所以采用synchronize可以會造成喚醒的"粒度"過大.
下面采用顯式鎖的方式來解決這個問題
2,顯式鎖(Lock)
class BlockingQueueWithLock<T> {
private int tail, head, count;
private T[] elems;
private final Lock lock = new ReentrantLock();
// 不滿 ,可繼續(xù)放
private final Condition notFull = lock.newCondition();
// 不空 ,可繼續(xù)取
private final Condition notEmpty = lock.newCondition();
BlockingQueueWithLock(int capacity) {
if (capacity <= 0) {
throw new IllegalArgumentException("capacity需要大于0");
}
elems = (T[]) new Object[capacity];
}
public T take() throws InterruptedException{
try{
lock.lock();
while(isEmpty()){
notEmpty.await();
}
T t = elems[head];
//不讓隊列在繼續(xù)引用該元素,GC可以回收
elems[head] = null;
head++;
if(head == elems.length){
head = 0;
}
count--;
notFull.signal();
return t;
}finally{
lock.unlock();
}
}
public void put(T t) throws InterruptedException{
try{
lock.lock();
while(isFull()){
notFull.await();
}
elems[tail] = t;
tail++;
if(tail == elems.length){
tail = 0;
}
count++;
notEmpty.signal();
}finally{
lock.unlock();
}
}
public boolean isFull() {
try {
lock.lock();
return elems.length == count;
} finally {
lock.unlock();
}
}
public boolean isEmpty() {
try {
lock.lock();
return count == 0;
} finally {
lock.unlock();
}
}
}
對于上面的實現(xiàn)方式,喚醒線程的時候使用signal為什么不是signalAll呢?
例如,當(dāng)隊列滿的時候取走一個元素,然后notFull.signal喚醒等待存放的線程存放元素,如果使用signalAll那么將喚醒所有阻塞的線程競爭這個一個存放的位置, 只有一個勝出,其余的將會繼續(xù)被阻塞.
如果使用signal那么只會喚醒一個線程,這樣減少了線程阻塞掛起和線程恢復(fù)的開銷
參考:
<<java編發(fā)編程實戰(zhàn)>>
