An overview of the

LinkedBlockingQue is an unbounded (maximum integer.max_value) blocking queue with configurable capacity based on a linked list implementation. The element at the head of the queue is the oldest, and the element at the end of the queue is the latest. The new element will be inserted at the end of the queue.

1. Data structure

Based on linked lists, there is at least one empty element in the queue and no element in the header.

2, the principle of

LinkedBlockingQueue has two locks, takeLock and putLock, one for read and write. This means that only reading and writing are mutually exclusive, and reading and writing can be done simultaneously. In order to ensure visibility and atomicity of the number of queue elements during read/write operations, the element variable count of the queue is of type AtomicInteger, and its value is only increased or decreased during read/write locking, as described in the later source section.

3. Source code interpretation

3.1 variable

LinkedBlockingQueue (Condition) putLock (Condition), takeLock (Condition), notFull (Condition), notEmpty (Condition); Capacity, queue head, queue end Last node, number of queue elements count. No more details.

3.2 Construction method

LinkedBlockingQueue has three constructors, as follows:

  • The capacity is not set. The default capacity isInteger.MAX_VALUE;
  • Set the capacity tocapacityAnd initialize the queue.
  • willCollectionThe elements in the collection are imported into the queueput(E x)Method, which will be described later in the put method, but not here.

3.3 Put (E x) Team entry method

Used to insert elements at the end of the == queue ==, queue full causes the == queuing thread to block ==. Look at the flow chart first, and then look at the source code. Because is to let oneself deepen the memory, so the process picture is relatively detailed.

Public void put(E E) throws InterruptedException {// Null elements are not allowedif(e == null) throw new NullPointerException(); int c = -1; // Create a new Node with the current element Node<E> Node = new Node<E>(E); final ReentrantLock putLock = this.putLock; final AtomicInteger count = this.count; / / get lock putLock squad. LockInterruptibly (); Try {// If the queue is full, the thread is added to the waiting queue of Conditionwhile(count.get() == capacity) { notFull.await(); } // enqueue(node); C = count.getAndincrement (); // If the element can still be inserted, then the waiting queue thread is releasedif(c + 1 < capacity) notFull.signal(); } finally {// unlock putlock. unlock(); } // Notify the outgoing thread that the queue is not emptyif (c == 0)
            signalNotEmpty();
    }
Copy the code

3.4 Take (E x) queue out method

The element == is used to fetch the last element of the == queue. If the queue is empty, the thread will block == before it exits the queue. Similarly, want to see the flow chart in the source code.

public E take() throws InterruptedException { E x; int c = -1; final AtomicInteger count = this.count; final ReentrantLock takeLock = this.takeLock; / / get takeLock lock takeLock lockInterruptibly (); Try {// If the queue is empty, join the queue for the notEmpty conditionwhile(count.get() == 0) { notEmpty.await(); } // get the queue header element x = dequeue(); C = count.getAnddecrement (); // If there is still data available in the queue, the notEmpty condition waits for the first thread in the queueif(c > 1) notEmpty.signal(); } finally { takeLock.unlock(); } // If the element in the queue goes from full to non-full, notify the PUT threadif (c == capacity)
            signalNotFull();
        return x;
    }
Copy the code

3.5 Other Methods

The other methods are similar to accessor principles, so I won’t repeat them. Interested can look at the source code. Because we usually use blocking queues for multi-threaded concurrent scenarios, so in fact, as long as you know the queue operation is basically ok, other methods are rarely used, and it is not recommended to spend too much time to study.

conclusion

  • Elements are not allowed to be null and NullPointException is thrown.
  • You can set the queue length to Integer.MAX_VALUE.
  • Based on linked list, the underlying data structure is linked list. After initialization, there will be an empty element at the head.
  • Read and write are locked, so security class;
  • Read and write both locks, so read and write can be done at the same time, which is a bit more throughput than ArrayBlockingQueue;
  • A Node object will be initialized for each joining operation, so frequent joining will produce more new-generation garbage;