Implementation analysis of queue synchronizer

Queue synchronizer implementation analysis includes synchronization queue, exclusive synchronization state acquisition and release, shared synchronization state acquisition and release, timeout synchronization state acquisition and so on. Due to space constraints, this article first analyzed synchronous queues, exclusive synchronization state acquisition and release. In the meantime, it is recommended to read locks (1) in Java before reading this article.

1. Synchronize queues

● Synchronizer internal maintenance of a synchronization queue (FIFO bidirectional queue) to manage the queuing work of threads. When the current thread fails to obtain the synchronization status, the synchronizer will add the current thread and related information as a Node to the end of the synchronization queue and block the current thread. When the synchronization state is released, the first node in the synchronization queue will wake up and compete to obtain a new synchronization state.

● It is important to note that the first node in the synchronization queue is the node that successfully obtained the synchronization status. After releasing the synchronization status, the first node wakes up its subsequent nodes, which set themselves as the first node after obtaining the synchronization status successfully.

2. Obtain and release the exclusive synchronization status

● The acquire(int arg) method of the synchronizer can be used to obtain the synchronization state exclusively, as follows:

public final void acquire(long arg) {
        if(! tryAcquire(arg) && acquireQueued(addWaiter(Node.EXCLUSIVE), arg)) selfInterrupt(); }Copy the code

  • 1. TryAcquire (int arg) attempts to obtain the synchronization status without blocking. If it succeeds, the tryAcquire(int arg) method returns directly. Otherwise, perform steps 2 and 3.

  • 2. AddWaiter (Node mode) Indicates that the current thread and related information will be added to the end of the synchronization queue due to the failure to obtain the synchronization status.

  • 3. AcquireQueued (Node Node,int arg) means to let the Node attempt to obtain the synchronization state in an infinite loop.


● The addWaiter(Node mode) method is as follows:

private Node addWaiter(Node mode) { Node node = new Node(Thread.currentThread(), mode); // Quickly try to add node to the end of the synchronization queue. // Synchronizer has head and tail nodes.if(pred ! = null) { node.prev = pred;if (compareAndSetTail(pred, node)) {
                pred.next = node;
                return node;
            }
        }
        enq(node);
        return node;
    }
Copy the code
private Node enq(final Node node) {
        for (;;) {
            Node t = tail;
            if (t == null) { // Must initialize
                if (compareAndSetHead(new Node()))
                    tail = head;
            } else {
                node.prev = t;
                if (compareAndSetTail(t, node)) {
                    t.next = node;
                    returnt; }}}}Copy the code
  • 1.compareAndSetTail(Node expect, Node update) Ensures that nodes can be safely added to the synchronization queue. If you do not, you may have multiple nodes ready to be added to the end of the synchronized queue at the same time, resulting in a skewed number of nodes and out of order.
  • 2. Before calling the final Node Node (ENQ) method, if the Node succeeds in joining the queue, the program returns without calling the final Node Node (ENQ) method. If the Node fails to join the queue, the final Node (ENQ) is called to ensure that the Node can join the queue in an “infinite loop” mode.


AcquireQueued (Node Node,int arg) acquireQueued(Node Node,int arg)

 final boolean acquireQueued(final Node node, long arg) {
        boolean failed = true;
        try {
            boolean interrupted = false;
            for (;;) {
                final Node p = node.predecessor();
                if (p == head && tryAcquire(arg)) {
                    setHead(node);
                    p.next = null; // help GC
                    failed = false;
                    return interrupted;
                }
                if (shouldParkAfterFailedAcquire(p, node) &&
                    parkAndCheckInterrupt())
                    interrupted = true;
            }
        } finally {
            if(failed) cancelAcquire(node); }}Copy the code
  1. AcquireQueued (Node Node,int arg) Indicates that the Node continuously attempts to obtain the synchronization status after entering the queue. If the synchronization status is obtained successfully, the Node will exit from the spin.
  2. 2. Only the node whose prev is the head can attempt to obtain the synchronization state for three reasons:
    • ● Maintain the FIFO principle for synchronous queues.
    • ● The first node in the synchronization queue is the node that has successfully obtained the synchronization status, and the first node will wake up the subsequent nodes after releasing the synchronization status. After the subsequent nodes wake up, they need to check whether their precursor node is the first node.
    • ● A node that is prematurely notified (prematurely notified means that the node whose precursor is not the primary node is woken up due to an interruption) succeeds in obtaining the synchronization state, which violates the principle that the first node in the synchronization queue is the node that successfully obtained the synchronization state.


● The synchronizer releases the synchronization state as follows:

public final boolean release(long arg) {
       if (tryRelease(arg)) {
           Node h = head;
           if(h ! = null && h.waitStatus ! = 0) unparkSuccessor(h); // Wake up subsequent node threads on the first nodereturn true;
       }
       return false;
   }
Copy the code


Summary: When obtaining an exclusive synchronization state, the synchronizer maintains a synchronization queue. The node that fails to obtain the synchronization state will be added to the queue and continuously try to obtain the synchronization state through spin. The condition for removal from the queue is that the leading node of the precursor node has successfully obtained synchronization status. Releasing synchronization wakes up subsequent nodes of the first node.