Introduction to the implementation principle of ReentrantLock (code example)

This article brings you an introduction to the implementation principles of ReentrantLock (code examples). It has certain reference value. Friends in need can refer to it. I hope it will be helpful to you.

In concurrent programming, in addition to the synchronized keyword, ReentrantLock and ReentrantReadWriteLock in java.util.concurrent.locks in the java concurrency package are also commonly used lock implementations. This article analyzes the principle of reentrant lock from the source code.

Let’s first talk about reentrant locks: After a thread obtains the lock, it can obtain the lock multiple times without blocking itself.

ReentrantLock is implemented based on the abstract class AbstractQueuedSynchronizer (hereinafter referred to as AQS).

Look at the source code:

First of all, it can be seen from the constructor that ReentrantLock has two mechanisms: fair lock and unfair lock.

//默认非公平锁
public ReentrantLock() {
        sync = new NonfairSync();
    }

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

First briefly explain the difference between fair locks and unfair locks, and then analyze the different implementation methods of the two.

Fair lock: Multiple threads are first-come, first-served. Similar to queuing, threads coming later are placed at the end of the queue.

Unfair lock: compete for locks. If it is grabbed, it will be executed. If it is not grabbed, it will be blocked. Wait for the thread that acquired the lock to be released before participating in the competition.

So unfair locks are usually used. Its efficiency is higher than fair lock.

Get lock

Fair lock

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

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

The first step is tryAcquire(arg) try to add Lock, implemented by FairSync, the specific code is as follows:

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

• ##Get the current thread

• Get the state in AQS. If state is 0, it means that no thread has obtained the lock at this time.

• In the if judgment, you must first determine whether the AQS Node queue is empty. If it's not empty, you'll need to queue. The lock is not acquired at this time.

• Try to use the CAS algorithm to update state to 1. The update is successful, the lock is acquired, and the thread at this time is set to the exclusive thread exclusiveOwnerThread. Return true.

• If state is not 0, it means that a thread has already obtained the lock. Therefore, it is necessary to determine whether the thread that obtained the lock (exclusive thread) is the current thread.

• If yes, it means reentrancy. Increase state by 1. Return true.

• At the last step, the lock is not obtained. Return false;

Continue with the above steps. If acquisition of the lock fails, first execute addWaiter(Node.EXCLUSIVE) and write the current thread into the queue

private Node addWaiter(Node mode) {
        Node node = new Node(Thread.currentThread(), mode);
        // Try the fast path of enq; backup to full enq on failure
        Node pred = tail;
        if (pred != null) {
            node.prev = pred;
            if (compareAndSetTail(pred, node)) {
                pred.next = node;
                return node;
            }
        }
        enq(node);
        return node;
    }

• Encapsulate a new node node

• Determine whether the end of the linked list is empty, if not, write the new node node' to the end

• 'If the end of the linked list is empty, use enq(node) to write to the end.

After writing to the queue, the acquireQueued() method suspends the current thread.

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

• In the loop, if the previous node is the head node, try to acquire the lock again. If successful, the loop will end and false will be returned.

• is not the head node. Based on the waitStatus of the previous node, it is judged whether the current thread needs to be suspended. waitStatus is used to record node status, such as node cancellation, node waiting, etc.

• If you determine that you need to suspend, use the parkAndCheckInterrupt() method to suspend the thread. Specifically, use LockSupport.park(this) to suspend the thread.

• If the lock acquisition is successful in the first step here, you can cancel the lock acquisition operation for this node.

Unfair lock

Unfair lock has differences in lock acquisition strategies.

final void lock() {
            if (compareAndSetState(0, 1))
                setExclusiveOwnerThread(Thread.currentThread());
            else
                acquire(1);
        }
 protected final boolean tryAcquire(int acquires) {
            return nonfairTryAcquire(acquires);
        }

• The unfair lock first directly tries to use the CAS algorithm to update the state and acquire the lock

• After the update fails, when trying to acquire the lock

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

Compared with the fair lock, the unfair lock tries to acquire the lock. There is no need to determine whether there are other threads in the queue.

Release lock

The steps for releasing locks are the same for fair locks and unfair locks

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;
    }
//更新state
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;
        }

It is worth noting that because it is a reentrant lock, in the tryRelease() method, the state needs to be updated to 0 before the lock is considered to be completely released. After releasing, wake up the suspended thread.

The above is the detailed content of Introduction to the implementation principle of ReentrantLock (code example). For more information, please follow other related articles on the PHP Chinese website!