Today learn about ConcurrentLinkedQueue, a Java queue that supports concurrency.
ConcurrentLinkedQueue characteristics
ConcurrentLinkedQueue ConcurrentLinkedQueue ConcurrentLinkedQueue ConcurrentLinkedQueue
The underlying data structure is a borderless queue based on linked lists, which uses FIFO(first-in, first-out) sorting principle and CAS method to achieve thread safety.
Introduction to properties and constructs
The properties and constructors of ConcurrentLinkedQueue are shown below:
ConcurrentLinkedQueue consists of two head and tail attributes that form the underlying linkedQueue structure. Both head and tail are inner class nodes. Node has properties item and Next. Item represents the value stored in the current Node object, and next represents the next Node object from the current Node object.
The bottom layer is a container with a linked list structure and we’ve analyzed a lot of them, but the bottom implementation of a linked list is that one node stores one piece of data.
At the bottom of the figure is the no-argument constructor for ConcurrentLinkedQueue. You can see that it does almost no initialization, except that it initializes a Node object with item equal to null and assigns it to head and tail.
The method of entrance
Container is the most key to the team and team method, first look at the team method, method source as follows:
All join methods end up calling the Offer method. The first step of the Offer method is to verify that the join object is null. Therefore, ConcurrentLinkedQueue does not support storing null objects.
The joining method is actually implemented primarily through a two-step loop call:
The first step is to find the endpoints in the queue;
The second step is to try to set the new node to the next attribute of the tail node. If the setting is successful, it is successful. If the setting fails, the first step is called again.
In summary: find the tail, update the tail, and try again if the update fails.
A team approach
Queue method source as follows:
The queuing method code is also relatively simple, which is to get the head node and judge that its item is not equal to NULL (so the container does not support storing NULL data) and change the item of the node to NULL by CAS. If the modification succeeds, the queuing succeeds.
In fact, the queue exit method is to traverse the linked list from the beginning node. As long as the item of the traversal node is not null, it will try to set it to NULL. If the setting succeeds, it means that the current item has been obtained.
Out of the team, the team approach has p = = q code, which is the current node and his child nodes are the same object, and the reason is that the team approach of updateHead method, it will put the old node next to his own, through such processing can be left linked list node, Cannot be set to null because other threads will consider it a tail.
conclusion
You also learned about a number of blocking queues, some of which have similar functionality to ConcurrentLinkedQueue and the underlying implementation. The ConcurrentLinkedQueue is implemented using CAS, which allows multiple threads to modify the same data, allowing for various special cases.
So The ConcurrentLinkedQueue is special in some key places, such as updating the header and the old header pointing to itself, which is handled both in and out of the queue.
Because multithreaded updates occur, there are many layers of validation in the method.
Java programmer daily study notes, such as understanding the wrong welcome to exchange discussion!
