Arrayblockingqueue of Java concurrency collection_ Power node Java college sorting

Arrayblockingqueue introduction

Arrayblockingqueue is a thread safe bounded blocking queue implemented by array.

Thread safety means that the internal arrayblockingqueue protects competing resources through "mutex lock", so as to realize the mutex access of multiple threads to competing resources. Bounded means that the array corresponding to arrayblockingqueue is bounded. Blocking queue refers to that when multiple threads access competing resources, when the competing resources have been obtained by a thread, other threads to obtain the resources need to block and wait; Moreover, arrayblockingqueue sorts elements according to FIFO (first in first out) principle. Elements are inserted into the queue from the tail and returned from the head.

Note: arrayblockingqueue is different from concurrentlinkedqueue. Arrayblockingqueue is array implemented and bounded; The concurrentlinkedqueue is implemented by a linked list and has no boundaries.

Principle and data structure of arrayblockingqueue

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

explain:

1. Arrayblockingqueue inherits from abstractqueue and implements the BlockingQueue interface.

2. Internally, arrayblockingqueue saves data through the object [] array, that is to say, arrayblockingqueue is essentially implemented through the array. The size of the arrayblockingqueue, that is, the capacity of the array, is specified when the arrayblockingqueue is created.

3. Arrayblockingqueue and reentrantlock are combined. Arrayblockingqueue contains a reentrantlock object (lock).

Reentrantlock is a reentrant mutex. According to the mutex, arrayblockingqueue implements "mutex access of multiple threads to competing resources". Moreover, reentrantlock is divided into fair lock and non fair lock. You can specify whether to use fair lock or non fair lock when creating arrayblockingqueue; Moreover, arrayblockingqueue uses unfair locks by default.

4. Arrayblockingqueue and condition are combined. Arrayblockingqueue contains two condition objects (notempty and notfull). Moreover, the condition also depends on the arrayblockingqueue. Through the condition, more accurate access to the arrayblockingqueue can be realized -- (01) if a thread (thread a) wants to get data and the array is just empty, the thread will execute notempty Await() to wait; Notempty. Is called when another thread (thread b) inserts data into the array Signal() wakes up the "waiting thread on notempty". At this point, thread a will be awakened to continue running. (02) if the array is full when a thread (thread h) wants to insert data, the thread will execute notfull Await() to wait; When another thread (thread I) fetches data, it will call notfull Signal() wakes up the "waiting thread on notfull". At this point, thread h will be awakened to continue running.

Arrayblockingqueue function list

The following analyzes the arrayblockingqueue from the aspects of creation, addition, removal and traversal.

1. Create

The following is an explanation of arrayblockingqueue (int capacity, Boolean Fair).

explain:

(01) items is an array that holds "blocking queue" data. It is defined as follows:

(02) Fair is the type of reentrant lock. Fair is true, which means fair lock; Fair is false, indicating that it is a non fair lock.

Notempty and notfull are the two conditions of a lock. They are defined as follows:

The function of lock is to provide an exclusive lock mechanism to protect competitive resources; Condition is to control the lock more finely. It relies on lock to control multithreading through a certain condition.

Notempty means "non null condition of lock". When a thread wants to get data from the queue and there is no data at this time, the thread passes notempty Await() to wait; Notempty. Is called when another thread inserts an element into the queue Signal() wakes up "the thread that entered the waiting state through notempty. Await().".

Similarly, notfull means "full condition of lock". When a thread wants to insert elements into the queue and the queue is full, the thread waits; When another thread takes an element from the queue, it wakes up the waiting thread.

2. Add

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

Note: the function of offer (e e) is to insert e into the tail of the blocking queue. If the queue is full, false is returned, indicating that the insertion failed; Otherwise, insert the element and return true.

(01) count indicates "the number of elements in the queue". In addition, there are two other elements in the queue that traverse takeindex and putindex. Takeindex indicates the index of the next element to be taken out and putindex indicates the index of the next element to be added. Their definitions are as follows:

(02) the source code of insert () is as follows:

Insert () wakes up the waiting thread above notempty after inserting the element.

The source code of Inc () is as follows:

If the value of I + 1 is equal to "queue length", that is, after adding elements, the queue is full; Then set the index of the next added element to 0.

3. Take out

Next, take () as an example to describe the retrieval method of arrayblockingqueue.

Note: take() is used to fetch and return the header of the queue. If the queue is empty, wait all the time.

The source code of extract () is as follows:

Note: after deleting the element, extract() will wake up the waiting thread on notfull.

4. Traversal

The following describes the traversal method of arrayblockingqueue.

ITR is a class that implements the iterator interface. Its source code is as follows:

Arrayblockingqueue 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.