Face to face Manual Chapter 16: explanation and implementation of fair lock of code peasant association lock and reentrantlock

author ： Little brother Fu
Blog ：https://bugstack.cn

precipitation 、 Share 、 grow up , Let yourself and others have something to gain ！

One 、 Preface

Java How much to learn to get a job ？

Recently, some friends often ask me , In my experience , Enough to learn , It seems that more depends on how ambitious you are . If you're just looking for a 10k Work in second tier cities within , It's still easier . You don't have to learn data structures 、 You don't need to know algorithms 、 Also need to understand the source code 、 Not to mention a lot of project experience .

But on the contrary, I met a domestic university TOP2 The graduating baby , This part-time job is Offer harvester ： tencent 、 Ali 、 There are also job opportunities in Singapore and so on , Pay is also high , Maybe more than you know about the price of cabbage . School is useless 、 Learning is useless , Sheer nonsense. ！

The more you can do on this road , The earlier you can work , The more you get ！

Two 、 Interview questions

Thank you plane , Notes , Just last winter, Barra's foot relaxing plane , Because I lost my Nike socks , Swearing to meet the interviewer .

interviewer ： Yo , The plane , Why don't you look happy .

Thank you plane ： Don't worry , Don't worry , I think I learned synchronized Well ！

interviewer ： That's just right , Can you lock the plane ？

Thank you plane ： ah ... I didn't go to the club ！！！ How do you know

interviewer ： I said, Java lock , What do you think ！ Do you know fair lock , Do you know how , Tell me about it ！

Thank you plane ： Fair lock ！？ Um. , It is not ReentrantLock Used in the , I feel as if I have an impression , But I don't remember .

interviewer ： Ah , Go home and search CLH Well ！

3、 ... and 、ReentrantLock and Fair lock

1. ReentrantLock Introduce

In view of the previous article, I have based on ,HotSpot Virtual machine source code analysis synchronized Implementation and corresponding core knowledge points , I would like to introduce ReentrantLock. But because ReentrantLock More knowledge points , Therefore, it will be divided into several parts to explain , Highlight the key points of each article , Avoid swallowing dates with pig Bajie .

Introduce ：ReentrantLock Is a reentrant and exclusive lock , Have and synchronized The monitor (monitor enter、monitor exit) Locks basically have the same behavior and semantics . But with synchronized comparison , It's more flexible 、 Powerful 、 Added rotation training 、 Overtime 、 Advanced functions such as interrupts and the ability to create fair and unfair locks .

2. ReentrantLock Knowledge chain

chart 16-1 ReentrantLock Lock the chain of knowledge

ReentrantLock Is based on Lock Implemented reentrant lock , be-all Lock It's all based on AQS Realized ,AQS and Condition Each maintains different objects , In the use of Lock and Condition when , It's actually the movement of two queues . It provides shared locks 、 Mutexes are based on state The operation of . And it's reentrant because of the synchronizer Sync, stay Sync In the two implementation classes of , Including fair lock and unfair lock .

The concrete implementation of this fair lock , That's the point of this chapter , Understand what a fair lock is 、 The concrete implementation of fair lock . After learning the basic knowledge, you can better understand ReentrantLock

3. ReentrantLock Fair lock code

3.1 initialization

   ReentrantLock lock = new ReentrantLock(true);  // true： Fair lock 
lock.lock();
try {
    // todo
} finally {
    lock.unlock();
}

  

Initializes the constructor input parameters , Select whether to initialize fair locks for .
In fact, in general, there is no need for a fair lock , Unless you need to be sequential in your scene .
Use ReentrantLock Remember to be in finally Closed in ,lock.unlock().

3.2 Fair lock 、 Not fair lock , choice

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

  

Choose fair lock in constructor （FairSync）、 Not fair lock （NonfairSync）.

3.3 hasQueuedPredecessors

   static final class FairSync extends Sync {

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

  

Fair and non-fair locks , Mainly in the method tryAcquire in , Is there a !hasQueuedPredecessors() Judge .

3.4 The first judge of the queue

   public final boolean hasQueuedPredecessors() {
    Node t = tail; // Read fields in reverse initialization order
    Node h = head;
    Node s;
    return h != t &&
        ((s = h.next) == null || s.thread != Thread.currentThread());
}

  

In this judgment, it mainly depends on whether the current thread is the first in the synchronization queue , yes ：true、 no ：false
This part involves the implementation of fair lock ,CLH（Craig,Landin andHagersten）. The initials of three authors

Four 、 What is fair lock

chart 16-2 Public toilets line up to enter the pit

The fair lock is like a toilet on the side of the road , You need to line up to go to the toilet . Of course, if someone doesn't line up , So it's unfair lock , For example, leaders should go first .

CLH It is a high performance based on one way linked list 、 Fair spin lock .AQS The queue in is CLH Virtual two-way queues for variants （FIFO）,AQS It is achieved by encapsulating each thread requesting shared resources into a node .

In order to better understand CLH Principle , You need to have practical code . Next one CLH To introduce separately for the core 4 Implementation of fair lock , In order to master the most basic knowledge of technology stack .

5、 ... and 、 Fair lock implementation

1. CLH

1.1 Look at the picture

chart 16-3 CLH Schematic diagram of implementation process

1.2 Code implementation

   public class CLHLock implements Lock {

    private final ThreadLocal<CLHLock.Node> prev;
    private final ThreadLocal<CLHLock.Node> node;
    private final AtomicReference<CLHLock.Node> tail = new AtomicReference<>(new CLHLock.Node());

    private static class Node {
        private volatile boolean locked;
    }

    public CLHLock() {
        this.prev = ThreadLocal.withInitial(() -> null);
        this.node = ThreadLocal.withInitial(CLHLock.Node::new);
    }

    @Override
    public void lock() {
        final Node node = this.node.get();
        node.locked = true;
        Node pred_node = this.tail.getAndSet(node);
        this.prev.set(pred_node);
        //  The spin 
        while (pred_node.locked);
    }

    @Override
    public void unlock() {
        final Node node = this.node.get();
        node.locked = false;
        this.node.set(this.prev.get());
    }

}

  

1.3 Code explanation

CLH（Craig,Landin and Hagersten）, It is a kind of extensible based on linked list 、 High performance 、 Fair spin lock .

In the implementation of this code , It is equivalent to a virtual linked list structure , from AtomicReference Methods getAndSet Connect .getAndSet Get current element , Set up new elements

lock()

adopt this.node.get() Get current node , And set up locked by true.
Then call this.tail.getAndSet(node), Get the current tail node pred_node, At the same time, set the newly added node as the tail node .
After that, I put this.prev Set to the previous tail node , It is equivalent to the direction of the link .
And finally, spin while (pred_node.locked), Until the program releases .

unlock()

The process of releasing the lock is to dismantle the chain , Set the node that releases the lock to false node.locked = false.
After that, the most important thing is to set the current node to the previous node , In this way, it is equivalent to taking down its own node , Waiting for the garbage collection .

CLH The advantage of queue lock is low space complexity , stay SMP（Symmetric Multi-Processor） Symmetric multiprocessor architecture （ A computer consists of many CPU form , And share memory and other resources , be-all CPU Can have equal access to memory 、I/O And external interruptions ） The effect is good . But in NUMA(Non-Uniform Memory Access) The effect is not very good , This part of knowledge can be expanded on its own .

2. MCSLock

2.1 Code implementation

   public class MCSLock implements Lock {

    private AtomicReference<MCSLock.Node> tail = new AtomicReference<>(null);
    ;
    private ThreadLocal<MCSLock.Node> node;

    private static class Node {
        private volatile boolean locked = false;
        private volatile Node next = null;
    }

    public MCSLock() {
        node = ThreadLocal.withInitial(Node::new);
    }

    @Override
    public void lock() {
        Node node = this.node.get();
        Node preNode = tail.getAndSet(node);
        if (null == preNode) {
            node.locked = true;
            return;
        }
        node.locked = false;
        preNode.next = node;
        while (!node.locked) ;
    }

    @Override
    public void unlock() {
        Node node = this.node.get();
        if (null != node.next) {
            node.next.locked = true;
            node.next = null;
            return;
        }
        if (tail.compareAndSet(node, null)) {
            return;
        }
        while (node.next == null) ;
    }

}

  

2.1 Code explanation

MCS From the initials of the inventor's name ： John Mellor-Crummey and Michael Scott.

It is also a kind of extensibility based on linked list 、 High performance 、 Fair spin lock , But with CLH Different . It really has the next node next, After adding this real node , It can spin only on local variables , and CLH Is the spin on the properties of the precursor node .

Because of the different spin nodes , Lead to CLH More suitable for SMP framework 、MCS It can fit NUMA Inconsistent storage access architecture . You can imagine CLH More need thread data in the same block of memory in order to better ,MCS Because it is in our store variable optional , So whether the data is scattered in different CPU The modules have no effect .

Code implementation and CLH There's not much difference , There is no narration here , You can see code learning .

3. TicketLock

3.1 Look at the picture

chart 16-4 Bank line-up and station calling map

3.2 Code implementation

   public class TicketLock implements Lock {

    private AtomicInteger serviceCount = new AtomicInteger(0);
    private AtomicInteger ticketCount = new AtomicInteger(0);
    private final ThreadLocal<Integer> owner = new ThreadLocal<>();

    @Override
    public void lock() {
        owner.set(ticketCount.getAndIncrement());
        while (serviceCount.get() != owner.get());
    }

    @Override
    public void unlock() {
        serviceCount.compareAndSet(owner.get(), owner.get() + 1);
        owner.remove();
    }
}

  

3.3 Code explanation

TicketLock It's like you go to the bank 、 It's the same as the number card I gave you , You can't go in until you call your number . It belongs to the strict fairness realization , But on multiprocessor systems , Each process / All processors occupied by threads are reading and writing the same variable , Each read and write operation requires cache synchronization between multiprocessors , Very expensive system performance .

Code implementation is also relatively simple ,lock() Set the owner's number plate in the , And go into spin alignment .unlock() Use in CAS To unlock , And deal with removing .

6、 ... and 、 summary

ReentrantLock Is based on Lock Implemented reentrant lock , For fair locks CLH The implementation of the , It's just the tip of the iceberg of knowledge , But there is this foot , Can be very good warm-up, easy to follow-up learning .
ReentrantLock More flexible to use , And more maneuverability , But it has to be in finally Middle release lock , The purpose is to ensure that after obtaining the lock , Finally, it can be released . At the same time, do not write the lock acquisition process in the try Inside .
The implementation of fair lock depends on different scenarios and SMP、NUMA Use , There will be different pros and cons . In the actual use of the general default will choose unfair lock , Even spin costs performance , It is usually used in less waiting threads , Avoid spinning too long .