6.26 Fair Lock

A fair lock follows the first-come, first-served principle.

Even if the lock has already been released, a thread that arrived later cannot compete for it until nobody is waiting ahead of it.

1. How to Use It

public class TestReentrantLock
{
    private static int val = 0;
    private final static Lock lock = new ReentrantLock(true);// Fair lock

    public static void main(String[] args) throws InterruptedException
    {
        Thread thread1 = new Thread(() -> {

            for (int i = 0; i < 100000; i++)
            {
                try
                {
                    lock.lock();
                    val++;
                }
                finally
                {
                    lock.unlock();
                }

            }
        });

        Thread thread2 = new Thread(() -> {

            for (int i = 0; i < 100000; i++)
            {
                try
                {
                    lock.lock();
                    val--;
                }
                finally
                {
                    lock.unlock();
                }
            }
        });


        thread1.start();
        thread2.start();

        thread1.join();
        thread2.join();
        System.out.println(val);
    }
}

2. Principle Analysis

2.1. Constructor

2.1.1. Implemented with AQS Underneath

public class ReentrantLock implements Lock, java.io.Serializable {

    private final Sync sync;

    // Nonfair lock by default
    public ReentrantLock() {
        sync = new NonfairSync();
    }

    public ReentrantLock(boolean fair) {
        // If true, a fair lock uses FairSync; otherwise NonfairSync
        sync = fair ? new FairSync() : new NonfairSync();
    }

    // Sync is a subclass of AQS
    abstract static class Sync extends AbstractQueuedSynchronizer {}
    // FairSync is a subclass of Sync
    static final class FairSync extends Sync {}
}

2.2. Locking

• lock

public void lock() {
    // Call FairSync.lock
    sync.lock();
}

2.2.1. Call the Fair Lock’s lock Method

• FairSync.lock

final void lock() {
    // Call AQS.acquire
    acquire(1);
}

2.2.2. Call AQS acquire to Acquire the Lock

• AQS.acquire

public final void acquire(int arg) {
    // Call FairSync.tryAcquire to acquire the lock
    if (!tryAcquire(arg) &&
        // If acquisition fails, join the AQS queue and repeatedly block the current thread,
        // waiting to be woken to continue acquiring the lock
        acquireQueued(addWaiter(Node.EXCLUSIVE), arg))
        // Restore the interrupt flag
        selfInterrupt();
}

Because FairSync overrides AQS’s tryAcquire, this calls FairSync.tryAcquire.

The rest of the logic is the same as 5.AQS.md. Only the main logic is briefly described below.

2.2.3. Try to Acquire the Lock [Only the Queue Head May Compete — Fair Lock]

• FairSync.tryAcquire

protected final boolean tryAcquire(int acquires) {
final Thread current = Thread.currentThread();
    int c = getState();
    // The lock has not yet been acquired
    if (c == 0) {
        // [Fair lock]: nobody in the queue is waiting ahead of me
        // (the queue is empty or I am the queue head)
        if (!hasQueuedPredecessors() &&
            // CAS-set state and acquire the lock successfully
            compareAndSetState(0, acquires)) {
            // Set the lock-owning thread to the current thread
            setExclusiveOwnerThread(current);
            return true;
        }
    }
    // The lock has already been acquired, and the owner is the current thread: reenter
    else if (current == getExclusiveOwnerThread()) {
        // Increase state
        int nextc = c + acquires;
        if (nextc < 0)
            throw new Error("Maximum lock count exceeded");
        setState(nextc);
        return true;
    }
    // Lock acquisition failed
    return false;
}

2.2.4. If Lock Acquisition Fails, Join the Blocking Queue

• AQS.addWaiter

private Node addWaiter(Node mode) {
    // Construct a node with the current thread and EXCLUSIVE mode
    Node node = new Node(Thread.currentThread(), mode);
    // The queue is not empty
    Node pred = tail;
    if (pred != null) {
        // Insert at the tail
        node.prev = pred;
        if (compareAndSetTail(pred, node)) {
            pred.next = node;
            return node;
        }
    }
    // The queue is empty or insertion at the tail failed
    enq(node);
    return node;
}

2.2.4.1. Enqueue Operation

• enq

private Node enq(final Node node) {
// Infinite loop until enqueue succeeds
for (;;) {
    Node t = tail;
    // The queue is empty, so initialize the head.
    // Note that this is new Node rather than the current node (the head is a placeholder)
    if (t == null) {
        if (compareAndSetHead(new Node()))
            tail = head;
    // The queue is not empty; insert at the tail
    } else {
        node.prev = t;
        if (compareAndSetTail(t, node)) {
            t.next = node;
            return t;
        }
    }
}
}

2.2.5. Block and Wait to Be Woken to Continue Acquiring the Lock

• acquireQueued

final boolean acquireQueued(final Node node, int arg) {
    boolean failed = true;
    try {
        boolean interrupted = false;
        // Infinite loop until lock acquisition succeeds
        for (;;) {
            // Logic 1.
            // When the predecessor of the current node is the head
            // (fair lock: nobody is waiting for the lock ahead of me), try to acquire the lock
            final Node p = node.predecessor();
            if (p == head && tryAcquire(arg)) {
                // After acquiring the lock, set the head to the current node
                setHead(node);
                p.next = null; // help GC
                failed = false;
                return interrupted;
            }
            // Logic 2.
            // When the predecessor's state is SIGNAL (it promises to wake the current node),
            // block the current thread.
            // When is it woken? When the lock is released.
            // What happens after it wakes? Continue the loop and execute Logic 1 above
            if (shouldParkAfterFailedAcquire(p, node) &&
                parkAndCheckInterrupt())
                interrupted = true;
        }
    } finally {
        // When is this executed? When an exception causes lock acquisition to fail
        if (failed)
            cancelAcquire(node);
    }
}

2.2.5.1. Determine Whether Blocking Is Needed

• shouldParkAfterFailedAcquire

// Given (predecessor, current node) -> whether to block the current thread
private static boolean shouldParkAfterFailedAcquire(Node pred, Node node) {
    int ws = pred.waitStatus;
    // If the predecessor is SIGNAL, it promises to wake the current node after releasing the lock.
    // Return true so the current thread can block
    if (ws == Node.SIGNAL)
        return true;
    // Predecessor state > 0 means CANCELLED.
    // Walk backward to find an uncancelled predecessor, removing CANCELLED nodes from the list
    if (ws > 0) {
        do {
            node.prev = pred = pred.prev;
        } while (pred.waitStatus > 0);
        pred.next = node;
    // Predecessor state >= 0, i.e. 0 or PROPAGATE.
    // CAS-set the predecessor's state to SIGNAL; on failure it will retry. Why?
    } else {
        compareAndSetWaitStatus(pred, ws, Node.SIGNAL);
    }
    return false;
}

2.2.5.1.1. Block the Current Thread

• parkAndCheckInterrupt

private final boolean parkAndCheckInterrupt() {
    // Use Unsafe underneath to block the current thread.
    // This clears the thread's interrupt flag, so the interrupt state needs to be returned
    LockSupport.park(this);
    return Thread.interrupted();
}

2.3. Unlocking

public void unlock() {
    // Call AQS.release
    sync.release(1);
}

2.3.1. Release the Lock with AQS

• release

public final boolean release(int arg) {
    // Sync overrides tryRelease; release the lock through Sync
    if (tryRelease(arg)) {
        Node h = head;
        // If the queue head is non-null and its state is normal, wake the head's successor
        if (h != null && h.waitStatus != 0)
            unparkSuccessor(h);
        return true;
    }
    return false;
}

Sync overrides tryRelease, so this calls Sync.tryRelease.

The rest of the logic is the same as 5.AQS.md. Only the main logic is briefly described below.

2.3.2. Try to Release the Lock

• Sync.tryRelease

protected final boolean tryRelease(int releases) {
    // Unlock
    int c = getState() - releases;
    // Locking and unlocking must be done by the same thread
    if (Thread.currentThread() != getExclusiveOwnerThread())
        throw new IllegalMonitorStateException();
    boolean free = false;
    if (c == 0) {
        // After the lock has been fully released, clear the owning thread
        free = true;
        setExclusiveOwnerThread(null);
    }
    // Set the state after unlocking
    setState(c);
    return free;
}

2.3.3. After Releasing the Lock Successfully, Wake a Node in the Blocking Queue

• AQS.unparkSuccessor

private void unparkSuccessor(Node node) {
    int ws = node.waitStatus;
    // If the current node's state < 0, change it to 0.
    // 0 is an empty state because after the thread of this node releases the lock,
    // there is nothing else it needs to do
    if (ws < 0)
        compareAndSetWaitStatus(node, ws, 0);


     // The current node's next node is null or has state > 0 (cancelled)
    Node s = node.next;
    if (s == null || s.waitStatus > 0) {
        s = null;
        // Traverse backward from the tail to find the nearest following node to the current node
        // whose state <= 0 (not cancelled)
        for (Node t = tail; t != null && t != node; t = t.prev)
            if (t.waitStatus <= 0)
                s = t;
    }
    // Wake the next node (fair lock)
    if (s != null)
        LockSupport.unpark(s.thread);
}

3. References

• Learning AQS in JUC — ReentrantLock Source Code Analysis | ifeve.com