Linkedblockingdeque of Java concurrency set_ Power node Java college sorting

Linkedblockingdeque introduction

Linkedblockingdeque is a bidirectional concurrent blocking queue implemented by a bidirectional linked list. The blocking queue supports both FIFO and Filo operation modes, that is, it can operate (insert / delete) from the head and tail of the queue at the same time; Moreover, the blocking queue supports thread safety.

In addition, linkedblockingdeque is optional (to prevent excessive expansion), that is, the capacity of the queue can be specified. If not specified, the default capacity size is equal to integer MAX_ VALUE。

Linkedblockingdeque principle and data structure

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

explain:

1. Linkedblockingdeque inherits from abstractqueue, which is essentially a bidirectional queue supporting FIFO and Filo.

2. Linkedblockingdeque implements the blockingdeque interface, which supports multithreading concurrency. When multiple threads compete for the same resource, after a thread obtains the resource, other threads need to block and wait.

3. Linkedblockingdeque is implemented through a two-way linked list.

3.1 first is the header of the bidirectional linked list. 3.2 last is the end of a two-way linked list. 3.3 count is the actual size of linkedblockingdeque, that is, the number of current nodes in the two-way linked list. 3.4 capacity is the capacity of linkedblockingdeque, which is specified when creating linkedblockingdeque. 3.5 lock controls the mutex of linkedblockingdeque. When multiple threads compete to access linkedblockingdeque at the same time, a thread obtains the mutex lock, while other threads need to block and wait. Until the thread releases the lock, other threads have the opportunity to obtain the lock and obtain the CPU execution right. 3.6 notempty and notfull are "non empty condition" and "not full condition" respectively. Through them, concurrency control can be more delicate.

List of linkedblockingdeque functions

Let's analyze linkedblockingdeque from the aspects of creating, adding, taking out and traversing arrayblockingqueue

1. Create

The following is a description of linkedblockingdeque (int capacity).

Note: capacity is the capacity of "chain blocking queue".

Related data results in linkedblockingdeque are defined as follows:

Note: lock is a mutex lock, which is used to control the mutex access of multiple threads to the elements in linkedblockingdeque; Notempty and notfull are conditions bound to lock, which are used to achieve more precise control over multithreading.

The node of the bidirectional linked list is defined as follows:

2. Add

Next, take offer (e e) as an example to explain the addition method of linkedblockingdeque.

Offer () actually calls offerlast () to add an element to the end of the queue.

The source code of offerlast() is as follows:

Note: offerlast() is used to create a new node and insert the node into the end of the two-way linked list. It will acquire the lock before inserting the node; Release the lock after the operation is completed. The source code of linklast() is as follows:

Note: linklast() is used to insert nodes into the end of the bidirectional queue; After inserting the node, wake up the waiting thread on notempty.

3. Delete

Next, take () as an example to explain the extraction method of linkedblockingdeque.

Take () is actually the first element of the queue that calls takefirst ().

The source code of takefirst() is as follows:

Note: takefirst() is used to delete the first node of the two-way linked list and return the value corresponding to the node. It will acquire the lock before inserting the node; Release the lock after the operation is completed.

The source code of unlikfirst() is as follows:

Note: unlinkfirst() is used to delete the first node of the bidirectional queue; Wake up the waiting thread on notfull after deleting the node.

4. Traversal

The following describes the traversal method of linkedblockingdeque.

Iterator () actually returns an ITER object.

The ITR class is defined as follows:

ITR inherits from abstractitr, and abstractitr is defined as follows:

Linkedblockingdeque example

(a) operation result:

Result description: in the sample program, start two threads (thread TA and thread TB) to operate linkedblockingdeque respectively. For thread TA, it will first obtain "thread name" + "sequence number", and then add the string to linkedblockingdeque; Next, we iterate over and output all the elements in linkedblockingdeque. The operation of thread TB is the same as that of thread TA, except that the name of thread TB is different from that of thread TA.

When the queue is a linkedblockingdeque object, the program can run normally. If the queue is changed to LinkedList, the program will generate a concurrentmodificationexception.