One, foreword

LinkedBlockingQueue and ConcurrentLinkedQueue are two commonly used data structures with high concurrency. They are both queues, but there are some similarities and differences. I just came home from a meeting today. Also want to use the way of blog, record the learning process of new knowledge, regard this as the first blog.

Second, the LinkedBlockingQueue

LinkedBlockingQueue is a queue, and it is a blocking queue. If the queue is empty or full, it will block (that is, it will lock the operation), and the operation can only be performed after adding a new element or releasing the position of the response:

    /** Lock held by take, poll, etc */
    private final ReentrantLock takeLock = new ReentrantLock();

    /** Wait queue for waiting takes */
    private final Condition notEmpty = takeLock.newCondition();

    /** Lock held by put, offer, etc */
    private final ReentrantLock putLock = new ReentrantLock();

    /** Wait queue for waiting puts */
    private final Condition notFull = putLock.newCondition();
Copy the code

LinkedBlockingQueue can be set to either bounded or unbounded

bounded

Specifying the queue size determines whether the element is full based on the specified size

LinkedBlockingQueue queue = new LinkedBlockingQueue(100);
Copy the code
public LinkedBlockingQueue(int capacity) {
        if (capacity <= 0) throw new IllegalArgumentException();
        this.capacity = capacity;
        last = head = new Node<E>(null);
 }
Copy the code

If there is no value in the queue, it will be locked, and no access can be performed, only if there is a value in the queue

while (count.get() == 0) {
    notEmpty.await();
}

Copy the code

unbounded

There is no need to specify the queue size. The default size is integer. MAX_VALUE, which is the maximum value that Integer can store ** (0x7FFFFFFf) **

public LinkedBlockingQueue(a) {
        this(Integer.MAX_VALUE);
}
Copy the code
LinkedBlockingQueue queue = new LinkedBlockingQueue();
Copy the code

We can create a LinkedBlockingQueue from the collection

Collection<Integer> list = Arrays.asList(1.2.3.4.5);
LinkedBlockingQueue queue = new LinkedBlockingQueue(list);
Copy the code

Since the linkedBlockingQueue will block if the element is empty, the following shows whether the log operation can be printed if the element is empty

public LinkedBlockingQueueDemo(a){
    ExecutorService executorService = Executors.newCachedThreadPool();
    // Create a linkedBlockingQueue object
    LinkedBlockingQueue<Integer> linkedBlockingQueue = new LinkedBlockingQueue<>();

    executorService.execute(()->{
        try {
            // Since the element in linkedBlockingQueue is now empty, it will block and the log will not be printed
            linkedBlockingQueue.take();
            log.info("Execute linkedBlockingQueue take()");
        } catch(InterruptedException e) { e.printStackTrace(); }}); }Copy the code

Add an element to the linkedBlockingQueue and the linkedBlockingQueue releases the lock and prints the following log

public LinkedBlockingQueueDemo(a){
    ExecutorService executorService = Executors.newCachedThreadPool();
    // Create a list and store it in linkedBlockingQueue
    Collection<Integer> collection = Arrays.asList(1.2.3.4.5);
    // Create an unbounded linkedBlockingQueue
    LinkedBlockingQueue<Integer> linkedBlockingQueue = new LinkedBlockingQueue<>(collection);

    executorService.execute(()->{
        try {
            // If there are elements in the linkedBlockingQueue, the lock is released and the log can be printed
            linkedBlockingQueue.take();
            log.info("Execute linkedBlockingQueue take()");
        } catch(InterruptedException e) { e.printStackTrace(); }}); }Copy the code

Third, ConcurrentLinkedQueue

In contrast to LinkedBlockingQueue, ConcurrentLinkedQueue is a borderless, thread-safe, non-blocking queue

Create a concurrentLinkedQueue object

ConcurrentLinkedQueue queue = new ConcurrentLinkedQueue();
Copy the code

ConcurrentLinkedQueue can also be created from collections, the source code is included below

public ConcurrentLinkedQueue(Collection<? extends E> c) {
    Node<E> h = null, t = null;
    for (E e : c) {
        Node<E> newNode = new Node<E>(Objects.requireNonNull(e));
        if (h == null)
            h = t = newNode;
        else
            t.appendRelaxed(t = newNode);
    }
    if (h == null)
        h = t = new Node<E>();
    head = h;
    tail = t;
}
Copy the code
Collection<Integer> collection = Arrays.asList(1.2.3.4);
ConcurrentLinkedQueue queue = new ConcurrentLinkedQueue(collection);
Copy the code

Compared with LinkedBlockingQueue

ConcurrentLinkedQueue is a non-blocking queue that returns Null if the element is empty and does not block like LinkedBlockingQueue. Although it is borderless, it will throw an OOM exception if memory is used up

Producers and consumers, or if there are multiple consumers competing for resources, if there are multiple consumers competing for resources, when the element is not added to the queue, one of the threads will have retrieved the element, however, causing a null pointer exception to be thrown. If there is only one thread, there will be no problem

int element = 1;
ExecutorService executorService = Executors.newFixedThreadPool(2);
ConcurrentLinkedQueue<Integer> queue = new ConcurrentLinkedQueue<>();
// Add elements
Runnable offerTask = () -> queue.offer(element);
// Retrieve the element
Callable<Integer> pollTask = () ->{
    // If not empty, get the element
    while(queue.peek() ! =null) {return queue.poll().intValue();
    }
    // Return null if null
    return null;
};
// Perform the add element task
executorService.submit(offerTask);
// Perform the task of retrieving elements
Future<Integer> returnValue = executorService.submit(pollTask);
System.out.println("element:"+element);
System.out.println("returnValue:"+returnValue.get().intValue());

ERROR:
element:1
Exception in thread "main" java.lang.NullPointerException
	at com.yangzinan.linked.ConcurrentLinkedQueueDemo.<init>(ConcurrentLinkedQueueDemo.java:27)
	at com.yangzinan.linked.ConcurrentLinkedQueueDemo.main(ConcurrentLinkedQueueDemo.java:32)

Copy the code

Now only one thread is used with the following effect:

int element = 1;
ExecutorService executorService = Executors.newFixedThreadPool(1);
ConcurrentLinkedQueue<Integer> queue = new ConcurrentLinkedQueue<>();
// Add elements
Runnable offerTask = () -> queue.offer(element);
// Retrieve the element
Callable<Integer> pollTask = () ->{
    // If not empty, get the element
    while(queue.peek() ! =null) {return queue.poll().intValue();
    }
    // Return null if null
    return null;
};
// Perform the add element task
executorService.submit(offerTask);
// Perform the task of retrieving elements
Future<Integer> returnValue = executorService.submit(pollTask);
System.out.println("element:"+element);
System.out.println("returnValue:"+returnValue.get().intValue());


INFO：
  element:1
	returnValue:1
Copy the code

Four,

In common

1. Both are queue implementations

2. Both implement Queue interfaces

3. Use Linked Nodes storage nodes

4. Both are applicable to high-concurrency scenarios

The difference between

features LinkedBlockingQueue ConcurrentLinkedQueue
obstructive Is a BlockingQueue that implements the BlockingQueue interface and blocks if the queue is full or empty The BlockingQueue interface is not implemented, it does not block, and Null is returned if the element is empty
Queue size The length of the queue can be specified at initialization or not. The default length is integer.max_value At initialization, you do not need to specify a queue length
The lock feature Lock-based queues Based on lockless queues
algorithm The implementation of the lock is based on the “double lock” algorithm Rely on Michael&Scott algorithm to achieve no blocking, no lock
implementation Double locks are used, mainly putLock and takeLock. Put /take uses the first lock and take/poll uses the second lock Use the CAS