The introduction

I don’t know if you’ve ever met an interviewer who said at the beginning of the interview that you need to manually implement a fifO non-reentrant lock. Is it a surprise? Is it exciting? It’s time to show off. Here’s an example

public class FIFOMutex {

    private final AtomicBoolean locked = new AtomicBoolean(false);
    private final Queue<Thread> waiters
        = new ConcurrentLinkedQueue<Thread>();

    public void lock(a) {
        boolean wasInterrupted = false;
        Thread current = Thread.currentThread();
        waiters.add(current);

        // Only if you are at the head of the queue can you get the lock, otherwise block yourself
        // if the cas operation fails, there is a concurrency problem, and someone else has already blocked it
        // Waiters. Peek ()! If you are the leader of the queue, why not directly obtain the lock and cas operation?
        // This is mainly because the next remove operation removes itself, but it hasn't actually released the lock, which is released in the unlock method
        while(waiters.peek() ! = current || ! locked.compareAndSet(false.true)) {
            LockSupport is used to block the current thread
            LockSupport.park(this);
            // Ignore the thread interrupt, just note that it was interrupted
            // Interrupt is only a state. It is up to the programmer to exit the program or throw an exception
            if (Thread.interrupted()) {
                wasInterrupted = true; }}// Remove the queue. Note that the threads behind the queue are at the head of the queue, but they still cannot obtain the locks. The locked values are true.
        // The cas operation in the while loop above will still fail and block
        waiters.remove();
        // Set the interrupt state if it has been interrupted
        if(wasInterrupted) { current.interrupt(); }}public void unlock(a) {
        locked.set(false);
        // Wake up the thread at the head of the queueLockSupport.unpark(waiters.peek()); }}Copy the code

The above example is an example of LockSupport in the JDK. LockSupport is a very low-level class that provides synchronization primials for threads. If you have to dig deeper, its implementation borroops from the Unsafe class, where methods are native and the real implementation is C++ code

With the above example, the following two methods are called

    public static void park(Object blocker) 
    public static void unpark(Thread thread) 
Copy the code

LockSupport’s wait and wake up is based on a license, which is held in C++ code with a variable count, which has only two possible values, one 0 and one 1. The initial value is 0

Call park once

  1. If count=0, block and wait for count to become 1
  2. If count=1, change count=0 and run directly without blocking

Call unpark once

  1. If count=0, change count=1
  2. If count=1, keep count=1

Multiple consecutive calls to unpark have the same effect as one

So the whole process, even if you call unpark multiple times, it’s just equal to 1, it doesn’t add up

Source code analysis

park

public static void park(Object blocker) { Thread t = Thread.currentThread(); // Set the current thread to block in blocker so that it can dump threads latersetBlocker(t, blocker); // call UNSAFE to block the current thread. UNSAFE. Park ()false, 0L); // Wake up and come heresetBlocker(t, null);
    }
Copy the code

UNSAFE. Park (false, 0L). The following happens when you call this method

  1. If the permission value is 1 (that is, unpark was called before, and park was not called later to consume the permission), return immediately without blocking and change the permission value to 0
  2. If the permission value is 0, block and wait until awakened by one of the following three events
    1. Another thread calls the unpark method to wake it up
    2. Other threads call the thread’s interrupt method to specify that the thread is interrupted
    3. There is no reason to wake up this thread.

unpark

    public static void unpark(Thread thread) {
        if(thread ! Unpark. unpark(thread); // Unsafe.unpark. unpark. (thread); // Unsafe.unpark. (thread); // Unsafe.unpark. (thread); // unsafe.unpark. (thread); }Copy the code

Even though broadening broadening is UNSAFE, a thread that needs to be aroused is specified. Unlike notify, synchronized locks are placed on objects, and threads block on objects. During the awakening process, there is no way to specify which thread to wake up, but only notify the thread waiting on the object monitoring lock to grab the lock. The specific person who grabs the lock is unpredictable, which also determines that synchronized cannot achieve a fair first-in, first-out lock similar to the above.

Park and unpark are called in no particular order

Let me give you an example


public class LockSupportTest {

    private static final Logger logger = LoggerFactory.getLogger(LockSupportTest.class);

    public static void main(String[] args) throws Exception {
        LockSupportTest test = new LockSupportTest();
        Thread park = new Thread(() -> {
            logger.info(Thread.currentThread().getName() + ": The park thread sleeps for a while and waits for another thread to unpark this thread.");
            try {
                Thread.sleep(4000);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
            logger.info(Thread.currentThread().getName() + ": call park");
            LockSupport.park(test);
            logger.info(Thread.currentThread().getName() + ": Awakened");
        });

        Thread unpark = new Thread(() -> {
            logger.info(Thread.currentThread().getName() + ": Call unpark to wake up the thread" + park.getName());
            LockSupport.unpark(park);
            logger.info(Thread.currentThread().getName() + ": Execution completed"); }); park.start(); Thread.sleep(2000); unpark.start(); }}Copy the code

Output result:

Unpark 18:52:44.064 thread-1: Unpark 18:52:42.064 thread-1: 18:52:46.079 Thread-0: Park 18:52:46.079 thread-0: the Thread is awakenedCopy the code

As you can see from the results, even if unpark is called first and then Park is called, the thread can return immediately and the whole process is not blocked. This is quite different from the wait() and notify () methods of Object objects, where an out-of-order wait() and notify () can cause a thread to block and not wake up on its wait(). LockSupport is a feature that eliminates the need to care about thread execution order and greatly reduces the possibility of deadlocks.

Support the timeout

// The unit of nanos is nanosecond, which indicates the maximum number of nanos nanoseconds to wait.
For example, I will wait for you at most 1000 nanoseconds. If you are not there, I will not wait for you any more. Otherwise, it is the same as Park
public static void parkNanos(Object blocker, long nanos)
// Deadline is an absolute time in milliseconds
// (e.g., wait until 9:30 this morning, if you are not there yet, I will not wait for you), otherwise the same as Park
public static void parkUntil(Object blocker, long deadline)
Copy the code

Because of this method, all kinds of locks such as ReentrantLock can support timeout wait. In fact, the underlying implementation is borrowed from these two methods. This is another feature that synchronized has no way of implementing

Support for querying which object the thread is blocking on

    public static Object getBlocker(Thread t) {
        if (t == null)
            throw new NullPointerException();
        return UNSAFE.getObjectVolatile(t, parkBlockerOffset);
    }
Copy the code

Before I did not read the source code has a question, the thread is already blocked, why can also view the specified thread block on the related object? Shouldn’t it be called without any response? Unsafe. getObjectVolatile(t, parkBlockerOffset) is not a volatile thread, but a volatile thread (t, parkBlockerOffset). This method gets an object with a specified offset in the memory region

Best practices

The blocking statement locksupport.park () needs to be in the body of the loop, as in the example at the beginning of this article

        while(waiters.peek() ! = current || ! locked.compareAndSet(false.true)) {
            // In the circulating body
            LockSupport.park(this);
            // Sensei came here later
            // Ignore other irrelevant code
        }
Copy the code

What’s the problem if it’s not in circulation? Suppose it becomes the following code snippet

        if(waiters.peek() ! = current || ! locked.compareAndSet(false.true)) {// Locksupport. park(this); // Wake up later to here // ignore other irrelevant code}Copy the code

This involves the concept of a thread waking up for no reason, meaning that a blocked thread is woken up without another thread calling the unpark() method

If two threads, A and B, enter successively, A will lock first, and B will block. However, if thread B is woken up for no reason while thread A has not released the lock, then thread B will execute directly down to acquire the lock. At this point, both thread A and thread B have access to the critical resource. This is illegal. Those that determine that B is not at the head of the queue or that CAS has failed continue to call park to block. So remember the Park method has to be in the circulating body

Compare park and unpark in LockSupport with Wait and notify in Object

  1. They can implement communication between threads
  2. Both Park and WAIT can block a thread
  3. Park and unpark can be used anywhere in the code
  4. Wait,notify, and notifyAll are used together with synchronized and must be used only after a monitor lock has been acquired, for example
synchronized (lock){
 lock.wait()
}
Copy the code
  1. The order of wait and notify is strictly controlled, and if a wait is executed after notify, the wait is never notified
  2. Park and unpark communicate with each other by license, without any guarantee of order
  3. Park supports timeout waiting, but WAIT does not
  4. Unpark supports waking up specified threads, but notify does not
  5. Both WAIT and Park can be awakened by interrupts, and wait gets an interrupt exception

To consider

LockSupport is essentially an Object, so can calling unpark LockSupport wake up the thread that called locksupport.wait ()? Please write your answer in the comments section

After watching two things

If you find this article inspiring, I’d like to invite you to do me two small favors:

  1. Like, so that more people can see this content (collection does not like, is a rogue -_-)
  2. Pay attention to the public number “interview BAT”, do not regularly share the original knowledge, the original is not easy, please support more (it also provides brush small program oh).