6.34 Nonfair Lock

A nonfair lock means that once the lock has been released, any thread may compete for it, regardless of whether it arrived earlier or later.

1. How to Use It

public class TestReentrantLock
{
    private static int val = 0;
    private final static Lock lock = new ReentrantLock();// Nonfair 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. Implementation Principles

2.1. Constructor

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, use FairSync for a fair lock; otherwise use 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

public void lock() {
    // Simply call the lock method of the Sync field, i.e. NonfairSync.lock
    sync.lock();
}

2.2.1. Lock with a Nonfair Lock

• NonfairSync.lock

final void lock() {
    // Acquire the lock. CAS-set state to 1; state represents the mutex here
    if (compareAndSetState(0, 1))
        // Set the current thread as the thread that owns the mutex
        setExclusiveOwnerThread(Thread.currentThread());
    else
        // If acquisition fails, call AQS.acquire
        acquire(1);
}

2.2.2. Lock Through AQS

• AQS.acquire

public final void acquire(int arg) {
    // Call NonfairSync.tryAcquire to acquire the lock
    if (!tryAcquire(arg) &&
        // If lock 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 NonfairSync overrides AQS’s tryAcquire, this calls NonfairSync.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 Lock Through the Nonfair Lock

• NonfairSync.tryAcquire

protected final boolean tryAcquire(int acquires) {
    // Call NonfairSync.nonfairTryAcquire
    return nonfairTryAcquire(acquires);
}

2.2.3.1. Nonfair Lock-Acquisition Operation [May Compete Regardless of Queue Position — Nonfair Lock]

• NonfairSync.nonfairTryAcquire

final boolean nonfairTryAcquire(int acquires) {
    final Thread current = Thread.currentThread();
    int c = getState();
    // The lock has not yet been acquired
    if (c == 0) {
        // Regardless of whether someone is waiting ahead, try to acquire the lock directly (nonfair lock)
        if (compareAndSetState(0, acquires)) {
            setExclusiveOwnerThread(current);
            return true;
        }
    }
    // The lock has already been acquired and the owner is the current thread: reenter
    else if (current == getExclusiveOwnerThread()) {
        int nextc = c + acquires;
        if (nextc < 0) // overflow
            throw new Error("Maximum lock count exceeded");
        setState(nextc);
        return true;
    }
    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. Join the Queue

• AQS.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;
            }
        }
    }
}

• 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 current node's predecessor is the head,
            // 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 current node's predecessor 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 waking? Continue the loop and execute Logic 1 above
            if (shouldParkAfterFailedAcquire(p, node) &&
                parkAndCheckInterrupt())
                interrupted = true;
        }
    // If an exception occurs, execute the logic below
    } finally {
        // cancelAcquire runs in every case except successful lock acquisition
        if (failed)
            cancelAcquire(node);
    }
}

• 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;
}

• 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() {
        // Simply call AQS.release
        sync.release(1);
    }

2.3.1. Release the Lock with AQS

• release

public final boolean release(int arg) {
    // Call Sync to release the lock
    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;
}

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) {
        free = true;
        setExclusiveOwnerThread(null);
    }
    // Set the state after unlocking
    setState(c);
    return free;
}

2.3.2.1. After Releasing the Lock Successfully, Wake Subsequent Nodes in the Blocking Queue

• 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 (does a nonfair lock also do this?)
        if (s != null)
            LockSupport.unpark(s.thread);
    }

3. References

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