Implementation of blocking queues and non-blocking queues in java

In Java, blocking queues (Blocking Queue)andNon-Blocking Queue** is two queue types for concurrent programming, which have different behaviors and uses in multithreaded environments. The main difference between them is how they are handled: a blocking queue blocks the thread when the operation cannot be completed immediately, while a non-blocking queue returns immediately or performs other operations.

1. What is a blocking queue?

Blocking queue(Blocking Queue) is a thread-safe queue that is located in JavaIn the bag. Blocking queues support automatically waiting (i.e. blocking) when the queue is empty until an element can be consumed, or automatically waiting when the queue is full until there is room for new elements to be inserted. This behavior makes blocking queues very useful in the producer-consumer model.

The operations that block queues includeBlocking insertion operationandBlocking deletion operation. Their main methods are:

put(E e): If the queue is full, the current thread will be blocked until the queue has free space.
take(): If the queue is empty, the current thread will be blocked until there are elements available in the queue.

There are several commonly used blocking queues in Java:

ArrayBlockingQueue: A bounded blocking queue, implemented based on array. Fixed size, supports fairness settings.
LinkedBlockingQueue: An optional bounded blocking queue, implemented based on linked lists. The default size isInteger.MAX_VALUE, suitable for scenarios with different task production and consumption rates.
PriorityBlockingQueue: An unbounded blocking queue that supports priority sorting. Based on the heap implementation, elements are dequeued in priority order.
DelayQueue: An unbounded blocking queue that supports delayed acquisition of elements. Elements can only be retrieved from the queue after the delay of the element expires.
SynchronousQueue: A blocking queue that does not store elements, each insertion operation must wait for a corresponding delete operation. Suitable for exchange scenarios.

2. What is a non-blocking queue?

Non-blocking queues(Non-Blocking Queue) is a thread-safe queue that does not block. The non-blocking queue does not wait for the current thread to complete the operation, but returns or performs other operations immediately. They are usually usedCAS（Compare-And-Swap）Operations to ensure thread safety, thereby avoiding thread blocking while waiting for locks.

Non-blocking queue operations includeNon-blocking insertion operationandNon-blocking deletion operation. Their main methods are:

offer(E e): Try to insert elements into the queue, if successful, returntrue, if the queue is full, return immediatelyfalse。
poll(): Try to take an element from the queue, return the element if it succeeds, and return immediately if the queue is emptynull。

Commonly used non-blocking queues in Java include:

ConcurrentLinkedQueue: An unbounded non-blocking queue based on linked lists, using CAS operations to achieve thread safety. Suitable for high concurrency scenarios.
ConcurrentLinkedDeque: A double-ended non-blocking queue, based on linked list implementation, supports insertion and deletion operations at both ends of the queue.

3. The difference between blocking queues and non-blocking queues

Blocking vs. non-blocking:Blocking queues may block when read or write, while this does not happen with normal queues. When a thread tries to read data from an empty normal queue or write data to a full normal queue, it will directly return a specific value instead of waiting for other threads to operate.
Synchronous and asynchronous:Blocking queues are usually used to process scenarios synchronously, while ordinary queues are usually used to process scenarios asynchronously. In the synchronous processing scenario, multiple threads need to work in coordination, while in the asynchronous processing scenario, multiple threads can independently perform their respective tasks among them.
Performance differences:Because blocking queues use locking mechanisms, performance bottlenecks may occur in high concurrency situations; instead of blocking queues use atomic operations and CAS instructions, they have better performance in high concurrency situations.

4. Use scenarios and selection guide

Blocking queues and non-blocking queues are each suitable for different scenarios. Understanding their characteristics and working mechanisms can help developers better choose the right data structure to solve concurrency problems.

4.1 Use scenarios for blocking queues

Producer-Consumer Model: The most common application scenario for blocking queues is the producer-consumer model. In this model, the producer thread constantly puts the tasks into the queue, and the consumer thread constantly takes the tasks from the queue. Using blocking queues can prevent producer or consumer threads from waiting when the queue is empty or full, thereby improving system performance.
Task Scheduling and Worker Thread Pooling: In a task scheduling system or worker thread pool, blocking queues can be used to store tasks. The worker thread of the thread pool can take tasks from the queue and execute them, and if there is no task, it will automatically wait until a new task arrives.
Delay task execution：DelayQueueApplicable to scenarios where tasks need to be executed after a certain delay, such as timed task scheduling.

4.2 Use scenarios for non-blocking queues

High concurrency scenarios: Non-blocking queues are often used in scenarios where high concurrent access is required because it does not use locks but relies on CAS operations to ensure thread safety, reducing the overhead of lock competition and providing higher throughput.
Low latency applications: For applications that require fast response and low latency, non-blocking queues are a very suitable choice. For example, in financial transaction systems or high-performance computing systems, it is necessary to process requests very quickly without being affected by locks.
Unbounded queue: Non-blocking queues are usually unbounded, e.g.ConcurrentLinkedQueue, which means they do not limit the queue size, but be careful to use to avoid memory overflow.

5. Implementation principle of blocking queues and non-blocking queues

5.1 Implementation principle of blocking queues

The implementation of blocking queues depends on internal locks and conditional variables (Condition) to implement thread synchronization. For example,ArrayBlockingQueueThe implementation is as follows:

Insert operation（put()）: If the queue is full, the insert thread will be placed in the conditional queue of "wait for available space" until another thread takes the element and wakes it up.
Take out operation (take()）: If the queue is empty, the fetch thread will be placed in the conditional queue of "waiting for element" until another thread inserts the element and wakes it up.

These methods passReentrantLockandConditionTo implement synchronous control:

public void put(E e) throws InterruptedException {
    final ReentrantLock lock = ;
    ();
    try {
        while (count == )
            ();  // Waiting for queue not full        enqueue(e);
    } finally {
        ();
    }
}

5.2 Implementation principle of non-blocking queues

Non-blocking queues usually use CAS (Compare-And-Swap) operations to achieve thread safety.ConcurrentLinkedQueueis a typical non-blocking queue, which is implemented through linked lists. Thatoffer()andpoll()The method is implemented as follows:

Insert operation (offer()）: Use the CAS operation to insert a new node to the end of the linked list. If it fails, try again until it succeeds.
Take out operation (poll()）: Use the CAS operation to obtain and remove the head node of the linked list. It will also retry when the operation fails until it succeeds.

public boolean offer(E e) {
    final Node&lt;E&gt; newNode = new Node&lt;&gt;(e);
    for (Node&lt;E&gt; t = tail, p = t;;) {
        Node&lt;E&gt; q = ;
        if (q

 == null) {
            if ((null, newNode)) {
                if (p != t)
                    casTail(t, newNode);  //Update tail nodes with CAS                return true;
            }
        } else if (p == q)
            p = (t != (t = tail)) ? t : head;
        else
            p = (p != t &amp;&amp; t != (t = tail)) ? t : q;
    }
}

6. Sample code

Here is a simple example using blocking and non-blocking queues:

Blocking queue example: ArrayBlockingQueue

import ;
import ;

public class BlockingQueueExample {
    public static void main(String[] args) throws InterruptedException {
        BlockingQueue&lt;Integer&gt; queue = new ArrayBlockingQueue&lt;&gt;(5);

        // Producer thread        Thread producer = new Thread(() -&gt; {
            try {
                for (int i = 0; i &lt; 10; i++) {
                    ("Producer production: " + i);
                    (i);  // Blocking insertion operation                }
            } catch (InterruptedException e) {
                ().interrupt();
            }
        });

        // Consumer thread        Thread consumer = new Thread(() -&gt; {
            try {
                while (true) {
                    Integer item = ();  // Blocking and withdrawing operation                    ("Consumer consumption: " + item);
                }
            } catch (InterruptedException e) {
                ().interrupt();
            }
        });

        ();
        ();
    }
}

Non-blocking queue example: ConcurrentLinkedQueue

import ;
import ;

public class NonBlockingQueueExample {
    public static void main(String[] args) {
        Queue&lt;Integer&gt; queue = new ConcurrentLinkedQueue&lt;&gt;();

        // Add elements        (1);
        (2);
        (3);

        // Remove the element        Integer item;
        while ((item = ()) != null) {
            ("take out: " + item);
        }
    }
}

7. Summary

Blocking queues and non-blocking queues have different application scenarios and characteristics in Java concurrent programming. Blocking queues achieve thread safety through internal locks and condition variables, and are suitable for scenarios such as producer-consumer models and task scheduling. Non-blocking queues are thread-safe through CAS operations and are suitable for high concurrency and low latency scenarios.

This is the end of this article about the implementation of blocking queues and non-blocking queues in Java. For more related contents of blocking queues and non-blocking queues in Java, please search for my previous articles or continue browsing the related articles below. I hope everyone will support me in the future!