The art of java Concurrent Programming -- Analysis of ReentrantLock's fair lock principle

lock method analysis

	final void lock() {
        acquire(1);
    }

The lock method calls the acquire method of AbstractQueuedSynchronizer

	/**
     * Acquires in exclusive mode, ignoring interrupts.  Implemented
     * by invoking at least once {@link #tryAcquire},
     * returning on success.  Otherwise the thread is queued, possibly
     * repeatedly blocking and unblocking, invoking {@link
     * #tryAcquire} until success.  This method can be used
     * to implement method {@link Lock#lock}.
     *
     * @param arg the acquire argument.  This value is conveyed to
     *        {@link #tryAcquire} but is otherwise uninterpreted and
     *        can represent anything you like.
     */
	public final void acquire(int arg) {
        if (!tryAcquire(arg) &&
            acquireQueued(addWaiter(Node.EXCLUSIVE), arg))
            selfInterrupt();
    }

The acquire method first calls the tryAcquire method, and the fair lock implements the FairSync class. The method is as follows:

	/**
         * Fair version of tryAcquire.  Don't grant access unless
         * recursive call or no waiters or is first.
         */
        protected final boolean tryAcquire(int acquires) {
            final Thread current = Thread.currentThread();
            int c = getState();
            if (c == 0) {
                if (!hasQueuedPredecessors() &&
                    compareAndSetState(0, acquires)) {
                    setExclusiveOwnerThread(current);
                    return true;
                }
            }
            else if (current == getExclusiveOwnerThread()) {
                int nextc = c + acquires;
                if (nextc < 0)
                    throw new Error("Maximum lock count exceeded");
                setState(nextc);
                return true;
            }
            return false;
        }

This method first obtains the current thread object, judges the state value of the object, and obtains the success of locking:

  1. Is 0, no thread successfully obtained the lock. Judge whether a thread is acquiring a lock. If not, use the CAS mechanism to set the state value to 1. If it is set to 1 successfully, the lock is obtained successfully, and the thread that is set to obtain the lock is the current thread.
  2. If it is not zero, a thread obtains a lock. It is judged that the thread obtaining the lock is the current thread. If the lock is obtained successfully, the lock state value is increased by 1. If the state is less than zero, it indicates that too many times of obtaining the lock lead to the value moving out and an exception is thrown. If not, the current thread fails to obtain the lock.
    Return to the acquire method of AbstractQueuedSynchronizer. If the lock acquisition fails, addWaiter method will be called to build the Node object, and then acquirequeueueueueueueueued method will be called
	/**
     * Acquires in exclusive uninterruptible mode for thread already in
     * queue. Used by condition wait methods as well as acquire.
     *
     * @param node the node
     * @param arg the acquire argument
     * @return {@code true} if interrupted while waiting
     */
    final boolean acquireQueued(final Node node, int 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);
        }
    }

The addWaiter method mainly puts the new node at the end of the queue. It will not be introduced. The acquirequeueueueueueueueued method obtains the lock in the dead cycle to judge whether the previous node of the current node is head (the first Node). If it is, call tryAcquire to continue to obtain the lock. The lock is obtained successfully. Set the current node to head and return false. Call shouldParkAfterFailedAcquire method

	/**
     * Checks and updates status for a node that failed to acquire.
     * Returns true if thread should block. This is the main signal
     * control in all acquire loops.  Requires that pred == node.prev.
     *
     * @param pred node's predecessor holding status
     * @param node the node
     * @return {@code true} if thread should block
     */
    private static boolean shouldParkAfterFailedAcquire(Node pred, Node node) {
        int ws = pred.waitStatus;
        if (ws == Node.SIGNAL)
            /*
             * This node has already set status asking a release
             * to signal it, so it can safely park.
             */
            return true;
        if (ws > 0) {
            /*
             * Predecessor was cancelled. Skip over predecessors and
             * indicate retry.
             */
            do {
                node.prev = pred = pred.prev;
            } while (pred.waitStatus > 0);
            pred.next = node;
        } else {
            /*
             * waitStatus must be 0 or PROPAGATE.  Indicate that we
             * need a signal, but don't park yet.  Caller will need to
             * retry to make sure it cannot acquire before parking.
             */
            compareAndSetWaitStatus(pred, ws, Node.SIGNAL);
        }
        return false;
    }

Check the waitStatus status of the previous node

  1. waitStatus ==Node.SIGNAL (the value is - 1 and it is in the waiting state. If the node releases the synchronization lock, it will wake up the successor node). Return true, and the thread can park.
  2. Waitstatus > 0 indicates that the previous node has been canceled and needs to be crossed. If false is returned, the thread cannot park.
  3. For other values, use the CAS mechanism to update the waitStatus of the previous node to node SIGNAL. If false is returned, the thread cannot park.
    If the thread can, park will call parkAndCheckInterrupt to block the thread
	/**
     * Convenience method to park and then check if interrupted
     *
     * @return {@code true} if interrupted
     */
    private final boolean parkAndCheckInterrupt() {
        LockSupport.park(this);
        return Thread.interrupted();
    }

If park is not allowed, the thread will follow the loop to execute the dead cycle in the acquirequeueueueueueueueued method until it obtains the lock or enters the blocking state, or the exception is set to waitStatus 1 (cancel state).

unlock method analysis

 /**
     * Attempts to release this lock.
     *
     * <p>If the current thread is the holder of this lock then the hold
     * count is decremented.  If the hold count is now zero then the lock
     * is released.  If the current thread is not the holder of this
     * lock then {@link IllegalMonitorStateException} is thrown.
     *
     * @throws IllegalMonitorStateException if the current thread does not
     *         hold this lock
     */
    public void unlock() {
        sync.release(1);
    }

The unlock method calls the release method of AbstractQueuedSynchronizer

  /**
     * Releases in exclusive mode.  Implemented by unblocking one or
     * more threads if {@link #tryRelease} returns true.
     * This method can be used to implement method {@link Lock#unlock}.
     *
     * @param arg the release argument.  This value is conveyed to
     *        {@link #tryRelease} but is otherwise uninterpreted and
     *        can represent anything you like.
     * @return the value returned from {@link #tryRelease}
     */
    public final boolean release(int arg) {
        if (tryRelease(arg)) {
            Node h = head;
            if (h != null && h.waitStatus != 0)
                unparkSuccessor(h);
            return true;
        }
        return false;
    }

First call reentrantlock Tryrelease method

	protected final boolean tryRelease(int releases) {
            int c = getState() - releases;
            if (Thread.currentThread() != getExclusiveOwnerThread())
                throw new IllegalMonitorStateException();
            boolean free = false;
            if (c == 0) {
                free = true;
                setExclusiveOwnerThread(null);
            }
            setState(c);
            return free;
        }
1. If the thread that obtains the lock is not the current thread, an exception will be thrown
2. Locked state State minus 1. If it is 0, it means that the number of times to obtain the lock is equal to the number of times to release the lock, the lock is released successfully, and the current execution thread of the lock is set to null. If it is greater than 0, it means that the number of times the lock is released is less than the number of times the lock is added. It is necessary to continue releasing the lock. Releasing the lock fails. set up state Value of.

Return to the release method of AbstractQueuedSynchronizer. If the lock release fails, the thread still holds the lock. It is necessary to continue to release the lock before other threads can obtain the lock successfully. If the lock is released successfully, and if the head of the lock (the head Node is not empty) is not cancelled, call the unparksuccess method

 /**
     * Wakes up node's successor, if one exists.
     *
     * @param node the node
     */
    private void unparkSuccessor(Node node) {
        /*
         * If status is negative (i.e., possibly needing signal) try
         * to clear in anticipation of signalling.  It is OK if this
         * fails or if status is changed by waiting thread.
         */
        int ws = node.waitStatus;
        if (ws < 0)
            compareAndSetWaitStatus(node, ws, 0);

        /*
         * Thread to unpark is held in successor, which is normally
         * just the next node.  But if cancelled or apparently null,
         * traverse backwards from tail to find the actual
         * non-cancelled successor.
         */
        Node s = node.next;
        if (s == null || s.waitStatus > 0) {
            s = null;
            for (Node t = tail; t != null && t != node; t = t.prev)
                if (t.waitStatus <= 0)
                    s = t;
        }
        if (s != null)
            LockSupport.unpark(s.thread);
    }

If the waitStatus of the head node is less than 0, use CAS mechanism to set the waitStatus of the head node to 0.
If the next node of the head node is null or in the cancelled state, traverse forward from the tail to find the first thread that has not been cancelled to wake up, otherwise wake up the next node. Wake up the thread of the node to obtain the lock (continue to execute the dead cycle in the acquirequeueueueued method of AbstractQueuedSynchronizer)

Schematic diagram of synchronization queue

Exclusive lock process

Keywords: Java Multithreading Concurrent Programming

Added by nelsok on Sat, 19 Feb 2022 12:47:28 +0200