This article covers thread blocking and wake up in four vertical ways. Java code layer, JVM layer, Linux user layer. How do you see and perceive each layer through visual operation

background

Java Lock locks are a major hurdle to concurrent resource access. The essence of Lock is AQS. AQS is the core of juC package, and a single class can support the advanced and important Mutil Thread framework. Think of the author. There have been a lot of online bulls on AQS, ReentrantLock has a good explanation. But they are theoretical, is there a way: Visual see multithreading is how to preempt the lock, grab when is how to queue, queuing time the whole AQS is what kind of state, queuing thread is how to do block, the underlying principle is what, grab the thread release lock queuing thread is how to get the lock, and so on a series of questions.

From a practical point of view, this paper creates a scene of multi-thread switching and accessing lock through debug mode, and visualizes the generation and solution of the above problems.

This article is focused and concise, and I hope you have some insights and ideas

The key point

Those of you who trade stocks have heard of the key point method. Fall to our technology, understand and understand these key points, can truly understand AQS and a specific application scenario of AQS: ReentrantLock

  1. Visualize blocking, queuing, wake up, queuing, etc from a practical perspective
  2. Describe the state of AQS objects in several thread queuing scenarios
  3. Code points that thread blocks and wakes up
  4. The implementation principle of Java thread blocking, Java code level implementation, JVM level implementation, system user level implementation, system kernel level implementation, four levels of contact

The body of the

  • Conceptually, the principle for lock is as follows: when two threads seize a resource, they essentially compete for the lock on the resource. The thread that has grabbed the resource starts to do something, and the thread that has not grabbed the resource queues up for the thread that has grabbed the lock to release it and notify it. Then he gets the lock and starts to do things too.

Java code layer

  • Specifically, for ReentrantLock and AQS, ReentrantLock uses the functionality implemented by AQS, while AQS implements locking by updating its fields: state and queue

Let’s start this “walk” with a lock usage example.Notice the breakpoint in the diagram. To distinguish the breakpoints, I have identified bP1, bP2, bp3, BP4, bp5. Note that the suspend type of breakpoint selects thread

Now start the Run Debug program.As shown, you can see that both threads are up. When you switch threads, you’ll notice that the two threads are at BP1 and BP2. We let both threads execute to BP3, at which point both threads are about to acquire the lock. The state of the Lock is 0, and the queue is emptyWe then execute Thread thread-0, which starts to enter the Lock.

final void lock() { if (compareAndSetState(0, 1)) //(1) setExclusiveOwnerThread(Thread.currentThread()); else acquire(1); //(2)} //Copy the code

After the execution of (1), Thread thread-0 adds one to the state of AQS. Here, state is updated from 0 to 1, indicating that Thread thread-0 has obtained the lock. At this time, take a look at the lock status, as shown in the following figureYou can see just one change: State goes from 0 to 1. The Thread thread-0 goes back to the outPut() method to execute the business logic.

We switch to Thread thread-1, which also goes inside the Lock. Since Thread thread-1 is holding the lock, Thread thread-1 executes at (2) of “code segment 1”. Since this paper focuses on the key point at the beginning, the logic of acquire(1) method is simplified: Acquire (1) consists of three methods: TryAcquire (ARG), addWaiter(Node.exclusive), acquireQueued(Node, ARG)

  • TryAcquire (ARG): Try to acquire again, or reentrant the lock

  • AddWaiter (node.exclusive): Create a Node and queue it to the end of the AQS queue (head, tail). Let’s take a snapshot of the information on this node, as shown below, created with waitStatus set to 0 and holding the current thread

BTW: The value of waitStatus is important, as follows

// the thread held by the node was CANCELLED = 1; SIGNAL = -1; SIGNAL = -1; Condition condition = -2; // The next shared mode should PROPAGATE PROPAGATE = -3 unconditionally; 0:None of the aboveCopy the code
  • acquireQueued(node, arg): Composed of shouldParkAfterFailedAcquire and parkAndCheckInterrupt – shouldParkAfterFailedAcquire: Update waitStatus on the successor node of the current node to SIGNAL(-1). Since the current node needs to be awakened by its predecessor, SIGNAL(-1) does just that. After this method is executed, let’s take a look at the snapshot of the AQS object at this point

ParkAndCheckInterrupt: Stops the current thread (thread suspension), essentially via unsafe.park (false, 0L). This method is native, which means looking at the JVM source code (described below).

private final boolean parkAndCheckInterrupt() { LockSupport.park(this); //this:AQS object return thread.interrupted (); } public static void park(Object blocker) {// static void park(Object blocker); setBlocker(t, blocker); UNSAFE.park(false, 0L); setBlocker(t, null); }Copy the code

BTW:setBlocker(t, Blocker) actually assigns the AQS object to the parkBlocker field of the current thread. This field is used by diagnostic and analysis tools.As shown, the current Thread thread-1 is blocked after executing the BP6 breakpoint line. And then you figure out when to wake up.

Now there are two nodes in the AQS queue: the node where Thread thread0 resides is the head node of the AQS queue, marked with node A; The node where thread-1 resides is the tail node of the AQS queue and is marked with node B. A is the predecessor of B, and B is the successor of A.

Let’s switch the Thread back to thread-0. In this example, Thread 0 goes to outPut and releases the lock(lock.unlock())

Let’s go inside the unlock method

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

Release: consists of two methods: tryRelease(ARG) and unparkprecursor (head) — tryRelease: to subtract the state of the AQS by one: update here from 1 to 0. — Unparksucceeded (head) : Update the waitStatus of the head node from -1 to 0. Call locksupport. unpark(s.read) to wake up the Thread of s node. We know that the node of current Thread thread-0 is the head node of AQS queue. The waitStatus of head node is SINGAL(-1), which means to wake up the successor node. So it is the nodes of thread-1 threads that are awakened here by the unparksucceeded. Locksupport.unpark (s.read) wakes up the Thread-0 Thread. As shown below, by blocking at bp6 breakpoint line, Thread 1 wakes up and executes at BP7 breakpoint line

After thread-1 is awakened at (5) of the acquireQueued method, the code is still in the acquireQueued method’s wireless loop. Therefore, if its successor node is head node, it will assign this node as head node and try to obtain the lock lock. That is to add one to the state of AQS, which is updated from 0 to 1, indicating that Thread-1 has obtained the lock lock. At the same time, the node where thread-1 resides becomes the head node of AQS.

boolean acquireQueued(final Node node, int arg) { boolean interrupted = false; for (;;) { final Node p = node.predecessor(); If (p == head && tryAcquire(arg)) {// (3) setHead(node) will try to acquire lock; // (4) this node is set to head node p.ext = null; // help GC return interrupted; }... ParkAndCheckInterrupt () wake up // (5) wake up}}Copy the code

Now thread-0 releases the lock lock, and Thread-1 acquires the lock lock. Let’s take a look at the information snapshot of the AQS object at this time, as shown below

At this point, the key points 1, 2, and 3 are already answered. For 4, we continue >>>

The JVM layer

Ununsafe. Park (false,0L) and ununsafe. Unpark (thread). But they are native types. So the source code needs to go to the JVM to see

You need to install the debug version of OpenJDK. I installed OpenJDk8U60 and opened it using the Clion IDE. Specific installation process Google good. Open Clion, as shown below Let’s take a look at the basics and ignore the rest, but remember that everything we need is in hotspot/ SRC. There are two rules for the mapping between JVM and Java code: XXX. XXX () = = > XXX_Xxx (). For example, if we want to look at Unsafe. Park, we search for the Unsafe class first, to get Unsafe. CPP; Then find Unsafe_Park in the file, as shown belowThread -> Parker ()->park(isAbsolute! = 0, time), from which we find the Parker::park method in the os_bsd. CPP file, as shown in the following figure

The whole method is basically to see if the _counter counter is greater than zero, and if there’s a thread interrupt. If you reach the pthread_mutex_trylock method (actually called the function), try adding a mutex lock. The pthread_mutex_trylock method is a system call that locks an operating system mutex and returns 0 on success. The Unpark function is roughly the same as the park function. pthread.h

__API_AVAILABLE(MacOS (10.4), ios(2.0)) int pthread_mutex_trylock(pthread_mutex_t *); __API_AVAILABLE(MacOS (10.4), ios(2.0)) int pthread_mutex_trylock(pthread_mutex_t *); __API_AVAILABLE(MacOS (10.4), ios(2.0)) int pthread_mutex_UNLOCK (pthread_mutex_t *);Copy the code

Each thread is associated with a Parker object, and each Parker object maintains three roles: counters, mutexes, and condition variables. Park action: Gets the Parker object associated with the current thread. Set the counter to 0 and check whether the original value of the counter is 1, if so, abort subsequent operations. Locks a mutex. Blocks on a condition variable while releasing the lock and waiting to be woken up by another thread. When woken up, the lock is reacquired. When the thread returns to the running state, set the counter value to 0 again. Releases the lock.

Unpark operation: Gets the Parker object associated with the target thread (note that the target thread is not the current thread). Locks a mutex. Set the counter to 1. Wakes up the thread waiting on the condition variable. Releases the lock.

This is what we see at the JVM layer when threads hang and wake up.

Linux user layer

How is pthread_mutex_trylock implemented at the system level

The pthread.h file is the only declaration of the pthread_mutex_lock function, which is implemented through the C/C++ Runtime Library. We can look at pthread_mutex_lock with the man command and see that it is a class of three command, namely the Library calls command. Finally, pthread_mutex_lock is implemented by calling LLL_UNLOCK(Linux-based FUtex) of type System Calls. $man pthread_mutex_lock

Pthread_mutex_lock is implemented as follows,

pthread_mutex_lock (pthread_mutex_t *mutex) { if (type == PTHREAD_MUTEX_TIMED_NP)) { /* Normal mutex. */ /*LLL_UNLOCK is LLL_UNLOCK (mutex->__data.__lock, PTHREAD_MUTEX_PSHARED (mutex)); PTHREAD_MUTEX_PSHARED is an interprocess, false */ LLL_UNLOCK(mutex); } else if (type == PTHREAD_MUTEX_RECURSIVE_NP) { /* Recursive mutex. */ pid_t id = THREAD_GETMEM (THREAD_SELF, tid); / * if already hold the lock, increase the count without block this thread * / if (mutex - > __data. __owner = = id) {+ + mutex - > __data. __count; return 0; LLL_MUTEX_LOCK (mutex); // set count mutex->__data.__count = 1; } / /... Special handling and other types of lock logic ignored... }Copy the code

Mutex is a structure with the following structure:

pthread_mutex_t { int __lock; // Lock variable, passed to the system call futex, used as the user space lock variable usunint __count; // Reentrant count int __owner; Int __kind; // Whether to share between processes, etc... // int __nusers; // other fields omitted}Copy the code

Man man allows you to check which commands belong to: library function calls, kernel calls, etc. We usually use class 1 commands

In general, pthread_mutex_lock calls llL_lock/llL_UNLOCK. In fact, it calls FUTEX_WAIT/FUTEX_WAKE of FUtex to sleep and wake up threads.

We call pthread_mutex_lock user-mode and it calls the kernel-mode futex function

The Linux kernel layer

Now let’s look at the kernel futex function. The man futex function is system calls.

Futex’s idea is to replace the bus LOCK with spin, and put the spin part in user mode. The pthread_mutex_lock function is handed over to lowLevelLock’s lll_lock() to spin. The first step in the spin is to try to set the futex flag variable from 0 to 1, marking the transition from idle to requested but not contending. Once atomic variables are overwritten, Means the lock was acquired successfully, otherwise the __lll_lock_wait() spin is executed, the flag is set to 2, the flag is contested and trapped in the kernel, and the futex() system call is executed to block the thread/process.

Let’s actually run a program and check the corresponding system kernel function calls when the program is running through strace command. To do this, we prepare a Java program to run in Linux with the following code: /root/project/lock/ c1_1_LockSupportTest.java

public class C1_1_LockSupportTest { public static void main(String[] args) { Thread t1 = new Thread(() -> { System. The out. Println (" park start "); LockSupport.park(); System. The out. Println (" end of the park "); }, "t1"); Threadt2 = new Thread(() -> {system.out.println ("unpark "); LockSupport.unpark(t1); System. The out. Println (" unpark end "); }, "t2"); Scanner scanner = new Scanner(System.in); String input; System.out.println(" Enter '1' to start t1, '2' to start T2, '3' to exit "); while (! (input = scanner.nextLine()).equals("3")) { if (input.equals("1")) { if (t1.getState().equals(Thread.State.NEW)) { t1.start(); } } else if (input.equals("2")) { if (t2.getState().equals(Thread.State.NEW)) { t2.start(); } } } } }Copy the code

The content of the program is to define two threads, one is locksupport.park () block, one is locksupport.unpark (T1) wake up. Input 1: starts thread T1, thus suspending thread T1; Input 2: start thread T2, thus waking up thread T1; Input 3: program execution ends

Javac c1_1_LOCKSupportTest. class, then strace -ff -o out Java C1_1_LockSupportTest run, This command will print out the details of each C1_1_LockSupportTest thread call to the kernel. The output file starts with out. After executing the command, I opened four Windows for easy viewing, as follows

Strace command to produce the principle of this result, I learned from the great god of Zhou Zhili, thank you.

Tail -f out.31105: C1_1_LockSupportTest main thread: C1_1_LockSupportTest main thread: C1_1_LockSupportTest

The main thread is waiting for input action. Note that the last out file is now: out.31113. When we type 1, thread T1 will be run, and when we look we will see an out file: out.32102. The following figure win4

At this point, thread T1 executes locksupport.park (), so thread T1 hangs. Linux kernel calls futex function; tail -f out.32102; tail -f out.32102;

Now we enter 2 again, run thread T2, execute locksupport. unpark(T1) to wake up T1, and then watch the 4 Windows change. As shown in the figure below, focusing on the Windows of Win3, it can be found that it stopped at the position of FUtex originally, and now it outputs several more lines until exit(0) is entered. Because when thread T1 wakes up and says “end of park”, the whole thread is finished.

Then type 3 to end the program. This is a demonstration of what happens in the Linux kernel state when the entire Java thread is suspended and woken up. Now, that’s key point 4.

it`s time to summary

This describes what Park and unpark in Java do from the Java layer to the JVM layer, to the Linux user layer, to the Linux kernel layer. This article is more of a series than a detailed explanation of the process. The purpose is to act as a guide and introduction. First, the ability is limited, more is to visualize the whole process, so that we can see and perceive the whole process concretely. Deepen understanding, not memorization.

Some of the theories in this article come from the online article of Daniel, thanks big guy.

The attachment

  • Source of t1, T2 code

JVM source code analysis (4) : in-depth understanding of park/unpark

  • Pthread_mutex_lock:

Chapter 4 Programming with Synchronization Objects

The Chinese version of

mutex-lock-for-linux-thread-synchronization/

Pthread_mutex_trylock source in glibc NPTL/pthread_mutex_trylock. C file path: code.woboq.org/userspace/g…

  • futex:

some-synchronization-designs-of-user-mode

translation-basics-of-futexes