快读系列-自己实现阻塞队列

0x00 摘要

其实BlockingQueue简单来说就是一个put锁,一个take锁,还有一个放入的元素形成的Node队列。这篇文章,我们通过写代码实现一个简易的阻塞队列来进一步加深对阻塞队列的印象和理解。

0x01 CustomBlockingQueue

在这里,我们通过代码简单实现了一个阻塞队列的基本功能:

/**
 * Created by chengc on 2018/8/15.
 * 其实BlockingQueue简单来说就是一个put锁,一个take锁,还有一个放入的元素形成的Node队列
 * 1.offer
 * 拿到锁的线程就把元素放入队列尾部,并释放锁;
 * 最后唤醒(调用LockSupport.unpark)一个等待时间最长的take线程(在takeCondition队列内),将其移入take锁的队列中
 *
 * 2.take
 * 拿到锁的线程,先判断元素个数是否为0 ,如果为0就在takeCondition上await(其实就是LockSupport.park来阻塞)。
 * 直到offer线程唤醒,就能从队列中拿出元素,释放take锁并返回拿到的元素
 */
public class CustomBlockingQueue<E> {
    private final int capacity;
    private final AtomicInteger count = new AtomicInteger();

    static class Node<E>{
        E item;
        Node<E> next;

        Node(E x){
            item = x;
        }
    }
    private Node<E> head;
    private Node<E> last;
    private final ReentrantLock putLock = new ReentrantLock();
    private final ReentrantLock takeLock = new ReentrantLock();
    private final Condition takeCondition = takeLock.newCondition();

    public CustomBlockingQueue(){
        this(Integer.MAX_VALUE);
    }
    public CustomBlockingQueue(int capacity){
        this.capacity = capacity;
        last = head = new Node<E>(null);
    }

    public int size(){
        return this.count.get();
    }

    public boolean offer(E item){
        final AtomicInteger tmpCount = this.count;
        putLock.lock();
        if(tmpCount.get() >= this.capacity){
            return false;
        }
        this.enqueue(new Node<E>(item));
        tmpCount.incrementAndGet();
        putLock.unlock();
        this.signalTake();
        return true;
    }

    public E take() throws InterruptedException {
        final AtomicInteger tmpCount = this.count;
        takeLock.lock();
        while(tmpCount.get() == 0){
            takeCondition.await();
        }
        E result = this.dequeue();
        tmpCount.decrementAndGet();
        takeLock.unlock();
        return result;
    }

    private void signalTake(){
        this.takeLock.lock();
        this.takeCondition.signal();
        this.takeLock.unlock();
    }


    private void enqueue(Node<E> item){
        last.next = item;
        last = last.next;
    }

    private E dequeue(){
        Node<E> firstDataNode = head.next;
        head.next = null;
        head = firstDataNode;
        E result = firstDataNode.item;
        firstDataNode.item = null;
        return result;
    }
}

0x02 ProducerConsumer

以下是该队列的测试代码,采用经典的生产者消费者模式,模拟一个生产者生产,两个消费者竞争消费的场景:

import org.apache.log4j.Logger;

/**
 * Created by chengc on 2018/8/15.
 */
public class ProducerConsumer {
    public static void main(String args[]){

        //Creating shared object
        CustomBlockingQueue sharedQueue = new CustomBlockingQueue<>(5);

        //Creating Producer and Consumer Thread
        Thread prodThread = new Thread(new Producer(sharedQueue));
        Thread consumer1 = new Thread(new Consumer("Shaoxing C",sharedQueue));
        Thread consumer2 = new Thread(new Consumer("Yu Z",sharedQueue));

        //Starting producer and Consumer thread
        prodThread.start();
        consumer1.start();
        consumer2.start();
    }

}

class Producer implements Runnable {
    Logger logger = Logger.getLogger(ProducerConsumer.class);
    private final CustomBlockingQueue sharedQueue;

    public Producer(CustomBlockingQueue sharedQueue) {
        this.sharedQueue = sharedQueue;
    }

    @Override
    public void run() {
        for(int i=0; i<100; i++){
            try {
                String productName = "Food"+i;
                System.out.println("start to produce:"+productName+", size is "+sharedQueue.size());
                sharedQueue.offer(productName);
                System.out.println("finished producing:"+productName+", size is "+sharedQueue.size());
                Thread.sleep(1000);
            } catch (InterruptedException ex) {
//                    logger.log(Level.SEVERE, null, ex);
            }
        }
    }

}

//Consumer Class in Java
class Consumer implements Runnable{

    private final CustomBlockingQueue sharedQueue;
    private final String consumerName;
    public Consumer (String name,CustomBlockingQueue sharedQueue) {
        this.sharedQueue = sharedQueue;
        consumerName = name;
    }

    @Override
    public void run() {
        while(true){
            try {
                System.out.println(consumerName + " Consumed: "+ sharedQueue.take()+", size is "+sharedQueue.size());
                Thread.sleep(2000);
            } catch (InterruptedException ex) {
//                    Logger.getLogger(Consumer.class.getName()).log(Level.SEVERE, null, ex);
            }
        }
    }
}