This is the 17th day of my participation in the August Text Challenge.More challenges in August

preface

What is a blocking queue? What are the seven blocking queues? Why do I need to block queues? Through the analysis of JDK 1.8 source code to understand the essence of the source code design and clever place, and use in our actual project, he can attack jade.

1. What is blocking queue

Blocking queues can wait for the queue to become non-empty (i.e., blocking wait), while storing elements, waiting space is available.

The BlockingQueue method comes in four forms, with different methods for handling operations that cannot be satisfied immediately, but may be satisfied at some point in the future:

  1. Throw an exception
  2. Return a special value (null or false, depending on the operation)
  3. Blocks the current thread indefinitely until the operation can succeed
  4. Block only for a given maximum time limit before giving up.

2. JDK has 7 types of blocking queues

JDK 7 provides seven blocking queues, as follows.

  1. ArrayBlockingQueue: A bounded blocking queue composed of array structures.
  2. LinkedBlockingQueue: A bounded blocking queue consisting of a linked list structure.
  3. PriorityBlockingQueue: An unbounded blocking queue that supports priority sorting.
  4. DelayQueue: an unbounded blocking queue implemented using a priority queue.
  5. SynchronousQueue: A blocking queue that does not store elements.
  6. LinkedTransferQueue: An unbounded blocking queue consisting of a linked list structure.
  7. LinkedBlockingDeque: A bidirectional blocking queue consisting of a linked list structure.

2.1 ArrayBlockingQueue

ArrayBlockingQueue is a bounded blocking queue implemented with arrays. This queue sorts elements according to first-in, first-out (FIFO) primitives.

Take a look at the ArrayBlockingQueue dependency inheritance, with arrays at the bottomObject[] items;That holds the element.

2.2 LinkedBlockingQueue

LinkedBlockingQueue is a bounded blocking queue implemented as a linked list. The default and maximum length of this queue is integer.max_value. This queue sorts elements on a first-in, first-out basis.

2.3 PriorityBlockingQueue

PriorityBlockingQueue is an unbounded blocking queue that supports a priority. By default, elements are arranged in natural ascending order. You can also customize the class to implement the compareTo() method to specify the element collation rules, or when initializing PriorityBlockingQueue, specify the constructor parameter Comparator to sort the elements. Note that the order of elements of the same priority cannot be guaranteed.

2.4 DelayQueue

DelayQueue is an unbounded blocking queue that supports delayed fetching of elements. The queue is implemented using PriorityQueue. Elements in the queue must implement the Delayed interface, which specifies when an element is created how long it will take to retrieve the current element from the queue. Elements can only be extracted from the queue when the delay expires.

Usage Scenarios:

  1. Design of cache system
  2. Scheduled Task Scheduling

2.5 SynchronousQueue will

SynchronousQueue is a blocking queue that stores no elements. Each PUT operation must wait for a take operation or it cannot continue to add elements.

It supports fair access queues. By default, threads use an unfair policy to access queues. Use the following constructor to create a equity-access SynchronousQueue, which, if set to true, will be accessed in first-in, first-out order by waiting threads.

public SynchronousQueue(a) {
    this(false);
}

public SynchronousQueue(boolean fair) {
    transferer = fair ? new TransferQueue<E>() : new TransferStack<E>();
}
Copy the code

2.6 LinkedTransferQueue

LinkedTransferQueue is an unbounded blocking TransferQueue queue consisting of a linked list structure. LinkedTransferQueue has tryTransfer and Transfer methods compared to other blocked queues.

2.6.1 transfer method

2.6.2 tryTransfer method

2.7 LinkedBlockingDeque

LinkedBlockingDeque is a two-way blocking queue consisting of a linked list structure.

3. Implementation principle of blocking queue

If the queue is empty and the consumer is waiting, how does the consumer know that the current queue has an element when the producer adds an element? How would you design it?

Implement using notification pattern. Notification mode blocks producers when they add elements to a full queue, and notifies producers when consumers consume elements in a queue that the queue is available.

JDK ArrayBlockingQueue source analysis

public ArrayBlockingQueue(int capacity, boolean fair) {
    if (capacity <= 0)
        throw new IllegalArgumentException();
    this.items = new Object[capacity];
    lock = new ReentrantLock(fair);
    // This is the key point of blocking queues, defining two conditional queues
    notEmpty = lock.newCondition();
    notFull =  lock.newCondition();
}
Copy the code

Let’s look at the put operation, the source code is not complicated, I will briefly explain the while condition, determine if the queue is full, wait notfull.await (), when the queue is full, continue to queue.

We may be confused why we use while instead of if, because multi-threaded cases, other lines first queue conditional queue await and single, can refer to my Java concurrent programming -AQS source conditional queue

public void put(E e) throws InterruptedException {
    checkNotNull(e);
    final ReentrantLock lock = this.lock;
    lock.lockInterruptibly();
    try {
        while (count == items.length)
            notFull.await();
        enqueue(e);
    } finally{ lock.unlock(); }}Copy the code

Take method

public E take(a) throws InterruptedException {
    final ReentrantLock lock = this.lock;
    lock.lockInterruptibly();
    try {
        // If there are no elements in the queue, the block waits on condition notEmpty
        while (count == 0)
            notEmpty.await();
            
        / / out of the queue
        return dequeue();
    } finally{ lock.unlock(); }}Copy the code

reference

The Art of Concurrent Programming in Java