Concurrentlinkedqueue of Java concurrency collection_ Power node Java college sorting

Introduction to concurrentlinkedqueue

Concurrentlinkedqueue is a thread safe queue, which is suitable for "high concurrency" scenarios.

It is an unbounded thread safe queue based on linked nodes. Elements are sorted according to FIFO (first in first out) principle. Null elements cannot be placed in queue elements (except for special nodes implemented internally).

Principle and data structure of concurrentlinkedqueue

The data structure of concurrentlinkedqueue is shown in the following figure:

explain:

1. Concurrentlinkedqueue inherits from abstractqueue.

2. The concurrentlinkedqueue is implemented internally through a linked list. It contains both the head node and the tail node of the linked list. Concurrentlinkedqueue sorts elements according to FIFO (first in first out) principle. Elements are inserted into the linked list from the tail and returned from the head.

3. The type of next in the linked list node of concurrentlinkedqueue is volatile, and the type of linked list data item is also volatile. As for volatile, we know that its semantics includes: "when reading a volatile variable, you can always see the last write to the volatile variable (by any thread)". Concurrent linkedqueue uses volatile to realize the mutually exclusive access of multiple threads to competing resources.

List of concurrentlinkedqueue functions

Let's analyze the creation, addition and deletion of concurrentlinkedqueue.

1 create

The following describes it with concurrentlinkedqueue().

Note: in the constructor, create a "node with null content", and set the values of header head and footer tail as the new node.

Head and tail are defined as follows:

Both head and tail are volatile types. They have the meaning given by volatile: "when reading a volatile variable, you can always see the last write to the volatile variable (by any thread)".

Node is declared as follows:

explain:

Node is a one-way linked list node, next is used to point to the next node, and item is used to store data. The API for operating node data in node is implemented through CAS function of unsafe mechanism; For example, casnext() is to "compare and set the next node of the node" through the CAS function.

2. Add

Next, take add (E) as an example to explain the addition in concurrentlinkedqueue.

Note: add () actually calls offer () to complete the addition operation.

The source code of offer () is as follows:

Note: the function of offer (e e) is to add element E to the end of the linked list. The place where offer () compares is to understand the for loop. The following three cases are distinguished to analyze for.

Case 1 -- Q is empty. This means that Q is the next node of the tail node. At this time, set "the next node of P as newnode" through p.casnext (null, newnode). If the setting is successful, compare "P and T" (if P is not equal to t, set newnode as the new tail node), and then return true. Otherwise (meaning "other threads have modified the tail node"), do nothing and continue the for loop.

p. Casnext (null, newnode) is to call CAS to operate on P. If "the next node of P is equal to null", set "the next node of P is equal to newnode"; If the setting is successful, it returns true, and if it fails, it returns false.

Case 2 -- P and Q are equal. When will this happen? Through "case 3", we know that after "case 3", the value of P may be equal to Q.

At this time, if the tail node has not changed, then the head node should have changed, set P as the head node, and then traverse the linked list again; Otherwise (if the tail node changes), set P as the tail node.

Case 3 - others.

We will p = (P! = T & & T! = (t = tail))? t : q; Convert to the following code.

If P and T are equal, set p to Q. Otherwise, judge whether the tail node has changed. If there is no change, set p to Q; Otherwise, set P as the tail node.

The source code of checknotnull() is as follows:

3. Delete

Next, take poll () as an example to explain the deletion in concurrentlinkedqueue.

Note: the function of poll() is to delete the header node of the linked list and return the corresponding value of the deleted node. The implementation principle of poll () is similar to that of offer (). The or loop is divided into four cases for analysis.

Case 1: the "header node data" is not null, and the "set header node data to null" operation succeeds.

p. Casitem (item, null) -- call CAS function to compare whether "data value of node P" is equal to item. If yes, set the data value of node p to null.

When case 1 occurs, compare "P and H" first, if P= h. That is, if the table hair changes, call updatehead() to update the header; Then return the item value of the deleted node.

The source code of updatehead() is as follows:

Note: the ultimate purpose of updatehead() is to update the header to P and set the next node of H to h itself.

Cashead (h, P) sets the header through CAS function. If the header is equal to h, set the header to P.

The source code of lazysetnext() is as follows:

The putorderedobject() function was introduced in the previous chapter "todo". h. Lazysetnext (H) is used to set the next node of h as H itself through CAS function, which may delay execution.

Case 2: if the next node in the header is null, that is, the linked list has only one "header node with null content".

Call updatehead (h, P) to update the header to p; Then return null.

Case 3: P = q

After the occurrence of "case 4", it will lead to P = q; At this point, "situation 3" will occur. When "case 3" occurs, it will jump to the restartfromhead tag to restart the operation.

Case 4: other cases.

Set P = Q.

Concurrentlinkedqueue example

(a) operation result:

Result description: if the queue in the source code is changed to a LinkedList object, the program will generate a concurrentmodificationexception.