Analyze the implementation principle and application scenario of blocking queue in Java

Some common queues we usually use are non blocking queues, such as PriorityQueue LinkedList (LinkedList is a two-way linked list, which implements the dequeue interface). When using a non blocking queue, there is a big problem: it will not block the current thread, so in the face of a consumer producer model, you must additionally implement the synchronization strategy and inter thread wake-up strategy, which is very troublesome. However, with a blocking queue, it is not necessary Similarly, it will block the current thread. For example, a thread takes elements from an empty blocking queue. At this time, the thread will be blocked until there are elements in the blocking queue. When there are elements in the queue, the blocked thread will wake up automatically (we don't need to write code to wake up). This provides great convenience. I. several main blocking queues

Since Java 1.5, in Java util. Several blocking queues are provided under the concurrent package, mainly including the following:

Arrayblockingqueue: a blocking queue based on array implementation. The capacity must be specified when creating arrayblockingqueue object. Fairness and unfairness can be specified. By default, it is unfair, that is, the queue with the longest waiting time is not guaranteed to have the highest priority to access the queue.

Linkedblockingqueue: a blocking queue based on a linked list. If the capacity size is not specified when creating the linkedblockingqueue object, the default size is integer MAX_ VALUE。

Priorityblockingqueue: the above two queues are first in first out queues, but priorityblockingqueue is not. It sorts the elements according to the priority of the elements and exits the queue according to the priority. Each outgoing element is the element with the highest priority. Note that this blocking queue is an unbounded blocking queue, that is, there is no upper limit on the capacity (you can know from the source code that it has no signal flag that the container is full). The first two types are bounded queues.

Delayqueue: a delay blocking queue based on PriorityQueue. The element in delayqueue can only be obtained from the queue when the specified delay time has expired. Delayqueue is also an unbounded queue, so the operation (producer) that inserts data into the queue will never be blocked, but only the operation (consumer) that obtains data will be blocked.

II Method in blocking queue vs method in non blocking queue

1. Several main methods in non blocking queue:

For non blocking queues, offer, poll and peek are generally recommended, but add and remove are not recommended. Because using offer, poll and peek methods can judge whether the operation is successful or not through the return value, but using add and remove methods can not achieve this effect. Note that none of the methods in the non blocking queue are synchronized.

2. Several main methods in blocking queue:

The blocking queue includes most methods in the non blocking queue. The five methods listed above exist in the blocking queue, but note that these five methods are synchronized in the blocking queue. In addition, blocking queue provides four other very useful methods:

III Implementation principle of blocking queue

If the queue is empty, the consumer will wait all the time. When the producer adds elements, how does the consumer know that there are elements in the current queue? If you were to design the blocking queue, how would you design it so that producers and consumers can communicate efficiently? Let's take a look at how JDK is implemented.

Implemented using notification mode. The so-called notification mode is that when a producer adds elements to a full queue, it will block the producer. When a consumer consumes elements in a queue, it will notify the producer that the current queue is available. By viewing the JDK source code, it is found that arrayblockingqueue uses condition to implement it. The code is as follows:

When we insert an element into the queue, if the queue is unavailable, the blocking producer mainly uses locksupport park(this); To achieve

Continue to enter the source code, found that calling setBlocker first save the thread that will block, then call unsafe.. Park blocks the current thread.

unsafe. Park is a native method. The code is as follows:

The park method will block the current thread. It will return only when one of the following four situations occurs.

When the unpark corresponding to the park is executed or has been executed. Note: executed refers to the park that is executed before unpark. When the thread is interrupted. If the time in the parameter is not zero, wait for the specified number of milliseconds. When abnormal phenomena occur. These anomalies cannot be determined in advance. Let's continue to look at how the JVM implements the park method. Park is implemented in different ways on different operating systems. Under Linux, the system method pthread is used_ cond_ Wait implementation. The implementation code is in the JVM source code path Src / OS / Linux / VM / OS_ linux. The OS:: platformevent:: Park method in CPP is as follows:

pthread_ cond_ Wait is a multithreaded condition variable function, and cond is the abbreviation of condition. Literally, it means that the thread is waiting for a condition to occur, which is a global variable. This method takes two parameters, a shared variable_ Cond, a mutex_ mutex。 The unpark method uses pthread under Linux_ cond_ Signal implementation. Park is implemented using WaitForSingleObject under windows.

When the queue is full, the producer inserts an element into the blocking queue, and the producer thread will enter the waiting (parking) state. We can see this by using jstack dump to block the producer thread:

IV Examples and usage scenarios

Next, use object Wait() and object Notify(), non blocking queue to implement producer consumer mode:

This is the classic producer consumer model, which blocks queues and objects Wait() and object Notify () is implemented, and wait () and notify () are mainly used to realize inter thread communication.

The specific inter thread communication methods (the use of wait and notify) will be described in the following chapters.

The following is a producer consumer model implemented using blocking queues:

Have you found that using blocking queue code is much simpler, and there is no need to consider synchronization and inter thread communication separately.

In concurrent programming, blocking queue is generally recommended to avoid unexpected errors in the program.

The most classic scenario of blocking queue is the reading and parsing of socket client data. The thread reading the data keeps putting the data into the queue, and then the parsing thread keeps fetching data from the queue for parsing. There are other similar scenarios where blocking queues can be used as long as they conform to the producer consumer model.