What is java queue

The queue is a special linear table that follows the principle of "first in, first out". In our daily use, we often use it to operate data concurrently. In concurrent programming, it is sometimes necessary to use thread-safe queues. If you want to implement a thread-safe queue, there are usually two ways: one is to use a blocking queue, and the other is to use a thread synchronization lock.

What is a blocking queue?

Suppose there is a bakery with a customer eating bread and a chef baking bread. There are no more than 2 pieces of bread in the basket. After the chef finishes the test, he puts the bread into the basket, and when the guests eat the bread, they take it out of the basket. In order to ensure that there is bread in the basket when the guests eat the bread or the basket does not overflow when the chef bakes the bread, At this time, we need to introduce the concept of blocking queue, which is what we often call the producer-consumer model.

A blocking queue is a queue that supports two additional operations. These two additional operations support blocking insertion and removal methods.

(1) Support blocking insertion method: This means that when the queue is full, the queue will block the thread inserting elements until the queue is not full.

(2) Support blocking removal method: This means that when the queue is empty, the thread that obtains the element will wait for the queue to become non-empty. Blocking queues are often used in producer and consumer scenarios. The producer is the thread that adds elements to the queue, and the consumer is the thread that takes elements from the queue. A blocking queue is a container used by producers to store elements and consumers to obtain elements.

Non-blocking queues in the system: PriorityQueue and ConcurrentLinkedQueue

Let’s take a look at the relationship between non-blocking queues (taking PriorityQueue as an example):

The PriorityQueue class inherits from AbstractQueue and implements the Serializable interface. Essentially maintaining an ordered list, PriorityQueue is located in the Java util package. The word Priority in the first half of its name means priority. In fact, this queue has "priority". Elements added to the Queue are positioned according to their natural ordering (through its java.util.Comparable implementation) or according to the java.util.Comparator implementation passed to the constructor.

ConcurrentLinkedQueue is a thread-safe queue based on linked nodes. Concurrent access does not require synchronization. Because it adds elements to the tail of the queue and removes them from the head, ConcurrentLinkedQueue's shared access to a common collection works just fine without knowing the size of the queue. Collecting information about the queue size will be slow and requires traversing the queue; ConcurrentLinkedQueue is an unbounded thread-safe queue based on linked nodes. It sorts nodes using a first-in, first-out rule. When we add an element, it is added to The tail of the queue; when we get an element, it returns the element at the head of the queue.

Queue that implements blocking interface:

The BlockingQueue interface and five blocking queue classes are added to java.util.concurrent. It's essentially a FIFO data structure with a twist. Rather than immediately adding or removing elements from the queue, the thread executing the operation blocks until space or an element becomes available.

The five queues provide different ones:

·ArrayBlockingQueue: A bounded queue backed by an array.

·LinkedBlockingQueue: An optional bounded queue backed by linked nodes.

·PriorityBlockingQueue: An unbounded priority queue backed by a priority heap.

·DelayQueue: A time-based scheduling queue backed by a priority heap.

·SynchronousQueue: A simple rendezvous mechanism using the BlockingQueue interface.

Let’s take a look at the inheritance relationship between ArrayBlockingQueue and LinkedBlockingQueue:

By looking at the inheritance relationship between the two classes, we You can know that they also inherit from AbstractQueue and implement the Serializable interface; the difference is that they also implement the BlockingQueue interface.

Let’s briefly introduce some of them:

LinkedBlockingQueueThe default size of LinkedBlockingQueue is Integer.MAX_VALUE, which can be understood as a cached bounded waiting queue. You can choose to specify its maximum capacity. It is a queue based on a linked list. This queue sorts elements according to FIFO (first in, first out). When the producer puts a piece of data into the queue, it is cached inside the queue. When the queue buffer reaches the maximum cache capacity (LinkedBlockingQueue can specify this value through the constructor), the producer queue is blocked until the consumer consumes from the queue. When a piece of data is dropped, the producer thread will be awakened, and vice versa for consumers.

ArrayBlockingQueue needs to specify capacity when constructing, and you can choose whether fairness is required. If the fairness parameter is set to true, the thread with the longest waiting time will be processed first (actually achieved by setting ReentrantLock to true This kind of fairness: that is, the thread with the longest waiting time will operate first). Generally, fairness will cost you in performance, so use it only when you really need it. It is an array-based blocking circular queue that sorts elements according to the FIFO (first in first out) principle.

PriorityBlockingQueue is a priority queue, not a first-in-first-out queue. Elements are removed in order of priority, and the queue has no upper limit (after looking at the source code, PriorityBlockingQueue is a repackage of PriorityQueue, based on the heap data structure, and PriorityQueue has no capacity limit, the same as ArrayList, so in priority It will not be blocked when putting on the blocking queue. Although this queue is logically unbounded, because the resources are exhausted, trying to perform an add operation may cause an OutOfMemoryError), but if the queue is empty, then the operation of taking the element take will block, so its retrieval operation take is blocked. In addition, the elements entering the queue must have comparison capabilities.

About ConcurrentLinkedQueue and LinkedBlockingQueue:

can also be understood as the difference between blocking queue and non-blocking queue:

1.LinkedBlockingQueue uses a lock mechanism, ConcurrentLinkedQueue uses the CAS algorithm, although the underlying lock acquisition of LinkedBlockingQueue also uses the CAS algorithm.

2. Regarding fetching elements, ConcurrentLinkedQueue does not support blocking to fetch elements, and LinkedBlockingQueue supports the blocking take() method.

3. Regarding the performance of inserting elements, in actual use, especially on multi-CPU servers, the gap between locking and lock-free is reflected. ConcurrentLinkedQueue will be much faster than LinkedBlockingQueue.

Producer-consumer code:

I saw a small example of a producer-consumer on the Internet, which is very helpful for understanding blocking queues. The code is as follows:

import java.util.concurrent.ArrayBlockingQueue;
import java.util.concurrent.BlockingQueue;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
 
public class BlockingQueueTest {
    public static class Basket {
        BlockingQueue<String> basket = new ArrayBlockingQueue<>(3);
 
        private void produce() throws InterruptedException {
            basket.put("苹果");
        }
 
        private void consume() throws InterruptedException {
            basket.take();
        }
 
        private int getAppleNumber() {
            return basket.size();
        }
    }
 
    private static void testBasket() {
        final Basket basket = new Basket();
        class Producer implements Runnable {
            public void run() {
                try {
                    while (true) {
                        System.out.println("生产者开始生产苹果###");
                        basket.produce();
                        System.out.println("生产者生产苹果完毕###");
                        System.out.println("篮子中的苹果数量：" + basket.getAppleNumber() + "个");
                        Thread.sleep(300);
                    }
                } catch (InterruptedException e) {}
            }
        }
 
        class Consumer implements Runnable {
            public void run() {
                try {
                    while (true) {
                        System.out.println("消费者开始消费苹果***");
                        basket.consume();
                        System.out.println("消费者消费苹果完毕***");
                        System.out.println("篮子中的苹果数量：" + basket.getAppleNumber() + "个");
                        Thread.sleep(1000);
                    }
                } catch (InterruptedException e) {}
            }
        }
        ExecutorService service = Executors.newCachedThreadPool();
        Producer producer = new Producer();
        Consumer consumer = new Consumer();
        service.submit(producer);
        service.submit(consumer);
        try {
            Thread.sleep(10000);
        } catch (InterruptedException e) {}
        service.shutdownNow();
    }
 
    public static void main(String[] args) {
        BlockingQueueTest.testBasket();
    }
}

Many java training videos, all on the PHP Chinese website, welcome to learn online!

The above is the detailed content of What is java queue. For more information, please follow other related articles on the PHP Chinese website!