Exclusive lock ReentrantLock principle

introduce

ReentrantLock is a reentrant exclusive lock. At the same time, only one thread can acquire the lock. Other threads acquiring the lock will be blocked and put into the AQS blocking queue of the lock.

It has the same basic behavior and semantics as synchronized, but ReentrantLock is more flexible and powerful, adds advanced functions such as polling, timeout and interrupt, and also supports fair lock and unfair lock.

As can be seen from the class diagram, ReentrantLock is still implemented using AQS, and whether it is a fair lock or a non fair lock can be selected according to the parameters. It is a non fair lock by default.

public ReentrantLock() {
    sync = new NonfairSync();
}
public ReentrantLock(boolean fair) {
        sync = fair ? new FairSync() : new NonfairSync();
}

The Sync class directly inherits the AQS class. Its subclasses NonfairSync and FairSync implement the unfair and fair policies of obtaining locks respectively.

static final class NonfairSync extends Sync {}
static final class FairSync extends Sync {}

In ReentrantLock, the state value of AQS indicates the number of reentrant times that a thread acquires a lock. By default, the state value of 0 indicates that no thread currently holds a lock. When a thread obtains the lock for the first time, it will try to set the state to 1 using CAS. If CAS succeeds, the current thread will obtain the lock, and then record that the holder of the lock is the current thread. After the thread acquires the lock for the second time, it will set state to 2, which is the number of reentrants. When the thread releases the lock, it will try to use CAS to reduce the state by 1. If it is 0 after 1, the lock will be released.

Acquire lock

void lock()

public void lock() {
    sync.lock();
}

When a thread calls this method, if the current lock is not occupied by other threads and the current thread has not acquired the lock before, the current thread acquires it, then sets the owner of the lock as itself, then sets the AQS state to 1, and then returns.

If the current thread has acquired the lock, it simply adds 1 to the AQS state and returns.

If the lock is already held by another thread, the current thread will enter the blocking queue of AQS and the blocking is suspended.

The lock() method in ReentrantLock is delegated to the sync class, and sync uses NonfairSync or FairSync according to the constructor of ReentrantLock.

Let's first look at the implementation of unfair locks.

final void lock() {
    // CAS set status value
    if (compareAndSetState(0, 1))
        setExclusiveOwnerThread(Thread.currentThread());
    else
        // Call the acquire method of AQS
        acquire(1);
}

In lock(), the compareAndSetState method is called first. Because the default state value is 0, the first thread will set it to 1 through CAS when calling the method for the first time, and then successfully obtain the lock, and then set the lock holder to the current thread through setExclusiveOwnerThread method.

When another thread obtains the lock through lock(), it will fail to enter else, call the acquire(1) method and pass the parameter as 1. Let's take another look at the acquire method.

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

As mentioned in the previous article, AQS does not provide the implementation of the tryAcquire method. Let's take a look at the tryAcquire method rewritten by ReentrantLock. Here we still look at the implementation of unfair locks.

static final class NonfairSync extends Sync {
        final void lock() {
            if (compareAndSetState(0, 1))
                setExclusiveOwnerThread(Thread.currentThread());
            else
                acquire(1);
        }
                //Call this method
        protected final boolean tryAcquire(int acquires) {
            return nonfairTryAcquire(acquires);
        }
    }

final boolean nonfairTryAcquire(int acquires) {
    final Thread current = Thread.currentThread();
    int c = getState();
    if (c == 0) {
        if (compareAndSetState(0, acquires)) {
            setExclusiveOwnerThread(current);
            return true;
        }
    }
    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;
}

This method first checks whether the current state value is 0. If it is 0, it indicates that the lock is currently idle. Then try CAS to obtain the lock. After success, set the state to 1, and then the lock holder is the current thread.

If the state is not 0, the lock has been held. If the holder happens to be the current thread, add 1 to the state and return true. Note that if nextc < 0, the lock may overflow.

If the current thread is not the holder, it returns false and then joins the AQS blocking queue.

Let's take a look at the implementation of fair lock.

protected final boolean tryAcquire(int acquires) {
    final Thread current = Thread.currentThread();
    int c = getState();
    if (c == 0) {
          //Fair strategy
        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;
}

The difference between the tryAcquire method of fair lock and non fair lock is that there is an additional hasQueuedPredecessors() method, which is the core code to realize fair lock.

public final boolean hasQueuedPredecessors() {
    //Read header node
    Node t = tail;
    //Read tail node
    Node h = head;
    //s is the successor node of the first node h
    Node s;
    return h != t &&
        ((s = h.next) == null || s.thread != Thread.currentThread());
}

In this method, because the queue is FIFO, it is necessary to judge whether there are nodes with related threads in the queue. If yes, return true, indicating that the thread needs to queue; if no, return false, indicating that the thread does not need to queue.

First, let's look at the first condition H= t，

• If both the head node and the tail node are null, it means that the queue is still empty or even has not completed initialization, then fasle will be returned naturally without queuing.
• The head node and the tail node are not null but equal, which means that both the head node and the tail node point to an element, indicating that there is only one node in the queue. At this time, there is no need to queue, because the first node in the queue does not participate in the queue and holds the synchronization state, so the second incoming node does not need to queue, because its predecessor node is the head node, Therefore, the second incoming node is the first node that can normally obtain the synchronization state. The third node needs to queue up and wait for the second node to release the synchronization state.

Next, let's look at the second condition, (s = h.next) == null, if h= T && s = = null indicates that an element will be queued as the first node of AQS, and returns true.

Next, let's look at the third condition, s.thread= Thread. Currentthread(), judge whether the subsequent node is the current thread.

🙋🏻‍♀️ For example, case 1:

h != t returns true, (s = h.next) == null returns false, s.thread= Thread. Currentthread() returns false

First H= T returns true, indicating that at least two different nodes exist in the queue;

(s = h.next) == null returns false, indicating that there are successor nodes after the header node;

s.thread != Thread.currentThread() returns false, indicating that the current thread and subsequent nodes are the same;

It indicates that it is the current node's turn to try to obtain the synchronization status. There is no need to queue up, and false is returned.

🙋🏻‍♀️ For example, case 2:

h != t returns true, (s = h.next) == null returns true

First H= T returns true, indicating that at least two different nodes exist in the queue;

(s = h.next) == null returns true, indicating that there is no successor node after the head node, that is, the sentry node;

Returns true, indicating that queuing is required.

🙋🏻‍♀️ For example, case 3:

h != t returns true, (s = h.next) == null, returns false, s.thread= Thread. Currentthread() returns true

First H= T returns true, indicating that at least two different nodes exist in the queue;

(s = h.next) == null returns false, indicating that there are successor nodes after the header node;

s.thread != Thread.currentThread() returns true, indicating that the thread of the subsequent node is not the current thread, indicating that someone is already queuing in front, so you have to queue honestly.

Returns true, indicating that queuing is required.

void lockInterruptibly()

public void lockInterruptibly() throws InterruptedException {
    sync.acquireInterruptibly(1);
}
public final void acquireInterruptibly(int arg)
            throws InterruptedException {
        // If the current thread is interrupted, an exception is thrown
        if (Thread.interrupted())
            throw new InterruptedException();
        //Trying to get resources
        if (!tryAcquire(arg))
            //Call the method that AQS can be interrupted
            doAcquireInterruptibly(arg);
}

This method is similar to the lock() method, except that it will respond to interrupts. When the current thread calls this method, if other threads call the interrupt() method of the current thread, the current thread will throw an InterruptedException exception.

boolean tryLock()

public boolean tryLock() {
    return sync.nonfairTryAcquire(1);
}
final boolean nonfairTryAcquire(int acquires) {
            final Thread current = Thread.currentThread();
            int c = getState();
            if (c == 0) {
                if (compareAndSetState(0, acquires)) {
                    setExclusiveOwnerThread(current);
                    return true;
                }
            }
            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;
}

This method attempts to obtain the lock. If the current lock is not held by other threads, the current thread obtains the lock and returns true. Otherwise, it returns false.

📢 Note: this method will not cause the current thread to block.

boolean tryLock(long timeout,TimeUnit unit)

public boolean tryLock(long timeout, TimeUnit unit)
        throws InterruptedException {
    return sync.tryAcquireNanos(1, unit.toNanos(timeout));
}

The difference between tryLock and tryLock is that the timeout time is set. If the timeout time is up and the lock has not been obtained, false is returned.

Release lock

void unlock()

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

public final boolean release(int arg) {
    if (tryRelease(arg)) {
        Node h = head;
        if (h != null && h.waitStatus != 0)
            unparkSuccessor(h);
        return true;
    }
    return false;
}

protected final boolean tryRelease(int releases) {
    int c = getState() - releases;
    //If unlock is not called by the lock holder, an exception is thrown
    if (Thread.currentThread() != getExclusiveOwnerThread())
        throw new IllegalMonitorStateException();
    boolean free = false;
    // If the current number of reentrants is 0, the lock holds the thread
    if (c == 0) {
        free = true;
        setExclusiveOwnerThread(null);
    }
    setState(c);
    return free;
}

This method first attempts to release the lock. If the tryRelease() method returns true, the lock will be released. Otherwise, it will be minus 1. If the lock holder does not call unlock, an IllegalMonitorStateException will be thrown.

Code practice

/**
 * @author Mystery jack
 * Official account: Java rookie programmer
 * @date 2022/1/21
 * @Description Using ReentrantLock to implement a simple thread safe List
 */
public class ReentrantLockList {

    private List<String> array = new ArrayList<>();

    private volatile ReentrantLock lock = new ReentrantLock();

    public void add(String e) {
        lock.lock();
        try {
            array.add(e);
        } finally {
            lock.unlock();
        }
    }

    public void remove(String e) {
        lock.lock();
        try {
            array.remove(e);
        } finally {
            lock.unlock();
        }
    }

    public String get(int index) {
        lock.lock();
        try {
            return array.get(index);
        } finally {
            lock.unlock();
        }
    }

}

Before operating array, this class ensures that only one thread can operate array at the same time by locking, but only one thread can access array elements.

summary

When three threads attempt to obtain the exclusive lock ReentrantLock at the same time, if thread 1 obtains it, threads 2 and 3 will be converted to Node nodes, which will then be placed in the AQS blocking queue corresponding to ReentrantLock and suspended.

Suppose thread 1 calls the conditional variable 1 created by the lock after entering the lock and enters the await, and thread 1 releases the lock. Thread 1 will then be converted to a Node and inserted into the condition queue of condition variable 1.

Since thread 1 releases the lock, thread 2 and thread 3 in the blocking queue will have the opportunity to obtain the lock. If a fair lock is used, thread 2 will obtain the lock, and then remove the Node corresponding to thread 2 from the AQS blocking queue.