實(shí)現(xiàn)一個(gè)自定義的有界阻塞隊(duì)列. 當(dāng)隊(duì)列為空時(shí),阻塞直到有可取的元素被喚醒;當(dāng)隊(duì)列滿時(shí),阻塞直到有空間存放元素被喚醒.

分析:
 1)為實(shí)現(xiàn)有界: 采用數(shù)組進(jìn)行存儲(chǔ)元素模擬隊(duì)列,為了提高空間的利用率,使用循環(huán)隊(duì)列
 2)為實(shí)現(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)都會(huì)進(jìn)行喚醒操作;但是執(zhí)行喚醒操作后,被喚醒的線程可能再次被阻塞.
例如,當(dāng)隊(duì)列為空,進(jìn)行取操作被阻塞,當(dāng)放入元素后喚醒所有的線程(notifyAll),但是只有一個(gè)可用元素, 所有被喚醒的取元素線程都將進(jìn)行競(jìng)爭(zhēng),只有一個(gè)線程能最終獲取獲取元素,其余取元素線程會(huì)再次被阻塞掛起.
那么將會(huì)問為何不使用notify呢?這樣就可以避免喚醒所有的線程,但是問題來(lái)了, notify只能喚醒一個(gè)線程,如果喚醒的是存放元素的線程,那么取元素的線程就喪失了一次獲取的機(jī)會(huì).
所以采用synchronize可以會(huì)造成喚醒的"粒度"過大.
下面采用顯式鎖的方式來(lái)解決這個(gè)問題

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];
                        //不讓隊(duì)列在繼續(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();
        }
    }
}

對(duì)于上面的實(shí)現(xiàn)方式,喚醒線程的時(shí)候使用signal為什么不是signalAll呢?
例如,當(dāng)隊(duì)列滿的時(shí)候取走一個(gè)元素,然后notFull.signal喚醒等待存放的線程存放元素,如果使用signalAll那么將喚醒所有阻塞的線程競(jìng)爭(zhēng)這個(gè)一個(gè)存放的位置, 只有一個(gè)勝出,其余的將會(huì)繼續(xù)被阻塞.
如果使用signal那么只會(huì)喚醒一個(gè)線程,這樣減少了線程阻塞掛起和線程恢復(fù)的開銷

參考:
<<java編發(fā)編程實(shí)戰(zhàn)>>