Shulou(Shulou.com)06/02 Report--

This article is to share with you about how to use ConcurrentLinkedQueue to achieve concurrency in java, the editor thinks it is very practical, so I share it with you to learn. I hope you can get something after reading this article.

In concurrent programming, we may often need to use thread-safe queues, for which java provides two modes of queues: blocking queues and non-blocking queues.

Note: how do blocking queues and non-blocking queues achieve thread safety?

Blocking queues can be thread-safe with one lock (one lock is shared in and out of the queue) or two locks (one lock is used in the queue and one lock in the queue). The typical implementation in JDK is BlockingQueue

Non-blocking queues can use cyclic CAS to ensure data consistency to achieve thread safety.

Let's take a look at how JDK implements thread-safe queue ConcurrentLinkedQueue in a non-blocking manner.

ConcurrentLinkedQueue source code analysis

ConcurrentLinkedQueue is an unbounded thread-safe queue based on linked nodes, following the FIFO principle of the queue, the end of the queue joins the queue and the first leaves the queue. Let's first take a look at the basic data structure of the queue and initialize the relevant source code implementation.

Queue basic data structure Node and initialization

Node implementation

Node implementation

As you can see from the source code, Node has two private attributes, item, and a next that points to the next node. To reduce overhead, both item and next are declared to be of type volatile, and they use CAS to ensure thread safety for updates.

ConcurrentLinkedQueue data structure

ConcurrentLinkedQueue Private Properties

ConcurrentLinkedQueue consists of head and tail nodes, and nodes are connected by next to form a queue with a linked list structure.

Queue initialization

ConcurrentLinkedQueue has two private properties, head and tail:

ConcurrentLinkedQueue Private Properties

Let's take a look at how ConcurrentLinkedQueue is initialized.

ConcurrentLinkedQueue initialization

As can be seen from the source code, when initializing a ConcurrentLinkedQueue object, a node with item and next of null will be created, and both head and tail will point to this node. The initialized queue structure is as follows:

Post-initialization structure diagram

After looking at the data structure and initialization, we should take a look at two important implementations of the queue: queuing and demarcation.

ConcurrentLinkedQueue joined the team.

Offer implementation

The essence of joining a queue is to insert a node at the end of the queue. The specific execution process is as follows:

Call the checkNotNull method to determine whether the queue element is null, and if it is null, a null pointer exception is thrown

Create a queuing node

Loop to perform end-of-line insertion:

CAS is set successfully: compare p with t. If p is not equal to t, set tail node to queue node. If queue is successful, return true. If p equals t, return true directly.

The CAS setting is not successful, indicating that another thread has made changes to the tail node, so continue to execute the for loop until the queue is successful.

Case 1: if the next node Q of the tail node is null, set the next node of the p node to the queue node through p.casNext (null, newNode):

Case 3: change the order, first talk about the last case, rewrite the code, it will be easier to understand:

Changed code

You can see that if p and t are equal, point p to Q, otherwise, judge whether the tail node has changed, if there is no change, point p to Q, if there is a change, set p to the tail node.

Case 2: through the operation of case 3, the equality of p and Q may occur. At this time, if the tail node has not changed, then the head node should have changed. Set p to the head node and traverse the queue from scratch. If the tail node changes, set p to the tail node.

So far, the source code analysis of joining the team is almost the same, to be honest, it is still very confused, and we may still be struggling in our hearts: first, what is the process of joining the team like? Second, join the team and directly CAS to update the tail node, why do you have to deal with it so painstakingly?

In response to the first question, give a picture, and you can fully understand:

Queue structure change chart. Jpg

Add node 1, when the next node of the tail node is null, in accordance with case 1 in the above code, and the next node of the tail node of the update queue is element 1. Since the initialization is that the head node is equal to the tail node, the next nodes of head and tail both point to node 1.

Add node 2, when the next node of the tail node is not null, and p is not equal to Q, in accordance with case 3 in the above code, first execute case 3 point p to the next node of the tail node, then execute the relevant logic of case 1, set the next node of node 1 to element 2, at this time p is not equal to t, update the tail node, point the tail node to element 2

The enrollment process of nodes 3 and 4 is the same as that of 1 and 2, so I won't repeat them here. It should be noted that the tail node does not necessarily point to the last node in the queue, it may point to the previous node of the last node!

For the second question, let's try to think about it another way. If we let the tail node be the end node of the queue each time, all we have to do is set the queue node to the tail node. The code can be simplified like this:

Tail is the enlistment of the node at the end of the queue.

The amount of code mentioned above is indeed very small, and the logic is very clear and easy to understand, but the disadvantage of doing so is that you need to cycle through the CAS to update the tail node every time you join the queue.

If the number of updates to the tail node can be reduced, then the efficiency of joining the queue can be improved. Therefore, Doug Lea does not make the tail node as the end of the queue node. It is only necessary to update the tail node when the distance between the tail node and the end of the queue is equal to 1. However, this may lead to a longer time for each queuing to locate the tail node when the queue length is longer, even so, it can still improve the efficiency of queuing, because in essence, the write operation of the volatile variable is much more expensive than the read operation.

After analyzing the entry into the team, let's take a look at the departure of ConcurrentLinkedQueue.

ConcurrentLinkedQueue is on the team.

Poll implementation

The essence of dequeuing is to reference the situation header node and return the value of the header node. The specific line logic is as follows:

Get the element of the header node

If the element of the header node is not null, and call p.casItem (item, null) to set the header node data to null successfully:

If p is not equal to the head node, and the header changes, call the updateHead method to update the header node, and then return the delete node item

Otherwise, the header node is not updated and the delete node item is returned directly.

If the condition in step 2 is not true and the next node Q of the header node is null, then the queue has only one null node, call the updateHead method to update the header node to p, and then return null

If the conditions in steps 2 and 3 are not true and p equals Q, jump to the restartFromHead tag and re-execute

Step 2, 3, 4, 4 is not valid, point p to Q

Cycle through the above steps

As a matter of fact, there is only so much source code. In order to make it easier to understand the process of finding a team, you should still give a picture:

The change diagram of queue structure

Node 1 is out of the queue, when the item of head is null, execute step 5 of the above code logic and point to node 1, if the item field of p is not empty, perform step 2, set the item of node 1 to null, when p is not equal to h, update the header node (if the next node of p is not null, point the header node to Q, otherwise point to p), return the item,head execution node of node 1 to node 2

Node 2 is out of the queue, when the item of head is not null, execute step 2 of the above code logic, set the item of node 2 to null, then p equals h, and the item,head directly returning to node 2 still points to node 2.

Nodes 3 and 4 come out in the same way as nodes 1 and 2, so I'm not going to repeat them here. It should be noted that the head node does not necessarily point to the first valid node in the queue, it may point to the previous node of the valid node!

Note: the valid node here refers to the node that traverses backwards from the head node, and item is not a null node.

Of course, the reason why the head node does not always point to the first valid node of the queue is the same as joining the queue, and the most important reason is to reduce the number of CAS updates to the head node, so as to improve the efficiency of dequeuing.

The above is how to use ConcurrentLinkedQueue to achieve concurrency in java. The editor believes that there are some knowledge points that we may see or use in our daily work. I hope you can learn more from this article. For more details, please follow the industry information channel.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.