This article has participated in the call for good writing activities, click to view: back end, big front end double track submission, 20,000 yuan prize pool waiting for you to challenge!
Multithreaded concurrency is a very important content in Java language, but also a difficult point in Java foundation. It is important because multithreading is frequently used in daily development, and it is difficult because there are so many knowledge points involved in multithreading concurrency that it is not easy to fully master Java concurrency knowledge. For this reason, Java concurrency is one of the most frequently covered topics in Java interviews. This series of articles will take a systematic look at Java concurrency in terms of the Java memory model, volatile keywords, synchronized keywords, ReetrantLock, Atomic concurrency classes, and thread pools. In this series of articles, you will learn more about the use of volatile, the implementation of synchronized, AQS and CLH queue locking, and clearly understand spin locking, bias locking, optimistic locking, pessimistic locking… And so on a dizzying array of concurrent knowledge.
Multi-threaded concurrency series
This time, understand the Java memory model and the volatile keyword once and for all
This time, thoroughly understand the Synchronized keyword in Java
This time, thoroughly understand the Java ReentranLock implementation principle
This time, understand Java thoroughly and send out the Atomic Atomic classes in the package
Understanding the wait and wake up mechanism of Java threads
Understanding the wait and wake up mechanism of Java threads (Part 2)
Java Concurrency series finale: Get to the bottom of how Java thread pools work
The principle of ThreadLocal is simple
This article, the fifth in the Java concurrency series, takes an in-depth look at Java’s wake up and wait mechanism.
About the thread of waiting and wake up must be no stranger to everyone, after all, in the beginning of learning Java foundation is the focus of learning content. In the previous two articles analyzing synchronized and ReentranLock, we skipped the contents related to thread wait and wake up, mainly because it is not easy to deeply understand thread wait and wake up mechanism, so we will write a separate article to analyze this knowledge point. In this article, we will further divide the waiting and awakening of the next thread from two aspects of synchronized and ReentranLock.
Before I start, I would like to recommend the GitHub repository AndroidNote, which is my study notes and the source of the first draft of my article. This repository contains a lot of Java and Android advancements. Is a systematic and comprehensive Android knowledge base. It is also a valuable interview guide for students preparing for interviews. Welcome to the GitHub warehouse homepage.
A view of thread wait and wake up from synchronized lock
When you first learned Java, you must have used synchronized to implement the code of “producer-consumer” model, which used several Object methods such as wait(), notify() and notifyAll(). I don’t know if you were confused at that time. Why are methods of thread waiting related to wakeup defined in the Object class?
What? Have you forgotten what the producer-consumer model is? Well, let’s start by reviewing the producer-consumer model.
1. The producer-consumer model
The producer-consumer model is a typical example of thread cooperative communication. There are two types of roles in this model, namely producer threads and consumer threads. The producer thread is responsible for submitting user requests, and the consumer thread is responsible for processing requests submitted by the producer. In many cases, producers and consumers do not reach a certain balance, that is, sometimes producers produce too fast for consumption; Sometimes consumers are too busy for producers to produce. In this case, a producer and consumer shared memory cache is needed to balance the collaboration between the two. Producers and consumers communicate through a shared memory cache to balance and decouple producer and consumer threads. As shown below:
When there are no items in the queue container, consumers need to be in a waiting state, and when the container is full, producers need to be in a waiting state. And every time a consumer consumes a good, it notifies the waiting producer that it is ready to produce. When production produces a good, it also notifies the waiting consumer that it is ready to consume.
2. Use synchronized to realize the producer-consumer model
Knowing the producer-consumer model, we try to implement an example of the producer-consumer model using the synchronized keyword combined with wait() and notifyAll() methods.
Let’s choose a more classic example of bread production. First, we need a bread container class. The container class has two operations: put bread and take bread.
public class BreadContainer {
LinkedList<Bread> list = new LinkedList<>();
// Container capacity
private final static int CAPACITY = 10;
/** * put the bread */
public synchronized void put(Bread bread) {
while (list.size() == CAPACITY) {
try {
If the container is full, the producer thread is blocked
wait();
} catch (InterruptedException e) {
e.printStackTrace();
}
}
list.add(bread);
// Notify the consumer thread when the bread is successfully produced
notifyAll();
System.out.println(Thread.currentThread().getName() + " product a bread" + bread.toString() + " size = " + list.size());
}
/** * take out the bread */
public synchronized void take(a) {
while (list.isEmpty()) {
try {
If the container is empty, the consumer thread is blocked
wait();
} catch (InterruptedException e) {
e.printStackTrace();
}
}
Bread bread = list.removeFirst();
// After consumption, producers are notified to produce bread
notifyAll();
System.out.println("Consumer " + Thread.currentThread().getName() + " consume a bread" + bread.toString() + " size = "+ list.size()); }}Copy the codeThe put method in the above code puts the produced bread into the container. If the container is full, the producer thread needs to be blocked to stop production, and when the producer successfully puts the bread into the container, it needs to try to wake up the waiting consumer thread to consume it.
When the container is empty, it blocks the consumer thread and makes it wait. If the bread is consumed successfully, it notifies the producer to start production.
Note that both methods use the synchronized keyword, and that the synchronized object is the instance of the synchronized method. The wait() and notifyAll() methods are also BreadContainer objects. Remember this passage, put a Flag here, we’ll analyze it later.
Then the producer and consumer implementation is relatively simple, with the following code:
/ / producer
public class Producer implements Runnable {
private final BreadContainer container;
public Producer(BreadContainer container) {
this.container = container;
}
@Override
public void run(a) {
// Producers produce bread
container.put(newBread()); }}/ / consumer
public class Consumer implements Runnable {
private final BreadContainer container;
public Consumer(BreadContainer container) {
this.container = container;
}
@Override
public void run(a) {
// Consumers consume breadcontainer.take(); }}Copy the codeNext, in the test code, open multiple producer threads and multiple consumer threads simultaneously
public static void main(String[] args) {
BreadContainer container = new BreadContainer();
new Thread(() -> {
for (int i = 0; i < 100; i++) {
new Thread(new Producer(container)).start();
}
}).start();
new Thread(() -> {
for (int i = 0; i < 100; i++) {
new Thread(new Consumer(container)).start();
}
}).start();
}
Copy the codeRun the main method at this point, and the producer and consumer threads work well together.
Notice that the main method instantiates a BreadContainer object. The synchronized lock object mentioned above in Flag is the container. The wait and notifyAll methods are also the methods of the Container instance. What do the wait and notify methods of Containers do to cause threads to block and wake up? Where does the blocked thread go? Why call the wait and notifyAll methods in the Container object? Is it possible to call wait and notifyAll of other objects instead?
Implementation principles of Wait () and Notify
Using the synchronized keyword, a synchronized object is associated with a monitor object. When a thread acquires a synchronized lock, The count in the Monitor object is incremented by one, and the thread ID is stored in the _ower of the monitor. At this point, if another thread attempts to hold the lock, it will be placed in the _WaitSet queue and wait.
Remember the Flag we set in the last video? Synchronized locks container objects, and wait and notify are also methods of containers, which gives some idea of the problems we left behind in the previous section. Is a thread put into a wait queue when a wait method is called and woken up when a notify or notifyAll method is invoked? To answer this question, we need to look at what wait and notify/notifyAll do.
Let’s take a look at the implementation of wait, notify, and notifyAll methods in Object
public class Object {
public final native void notify(a);
public final native void notifyAll(a);
public final void wait(a) throws InterruptedException {
wait(0L);
}
public final native void wait(long timeoutMillis) throws InterruptedException;
}
Copy the codeUnfortunately, these methods are native, which means they are implemented in the VIRTUAL machine using C/C++. In this case, we might as well scratch the virtual machine code to find out, after all, there is no proof.
1. Implementation of WAIT on VMS
Following on from the producer-consumer model in the previous section, when a producer thread puts bread into a container and finds that the container is full, it calls wait. At this point, the thread releases the lock and blocks.
CPP objectMonitor :: WAIT (jLong millis, bool interruptible, TRAPS) function,ObjectMonitor:: Wait core code:
void ObjectMonitor::wait(jlong millis, bool interruptible, TRAPS) {
/ /... Omit other code
// The current thread
Thread * const Self = THREAD ;
// Encapsulate the thread as ObjectWaiter
ObjectWaiter node(Self);
// Mark the state as Wait
node.TState = ObjectWaiter::TS_WAIT ;
Self->_ParkEvent->reset() ;
Thread::SpinAcquire (&_WaitSetLock, "WaitSet - add");// Add the thread to the wait queue
AddWaiter (&node) ;
Thread::SpinRelease (&_WaitSetLock) ;
// ...
// The thread exits monitor and releases the lock
exit (true, Self) ;
}
Copy the codeAs you can see, after the wait function is called, the thread is wrapped into an ObjectWaiter object, and the addWait function is called to add the thread to the wait queue. Now look at the code for the addWait function:
inline void ObjectMonitor::AddWaiter(ObjectWaiter* node) {
if (_WaitSet == NULL) {
// Initialize _WaitSet, that is, only one node element
_WaitSet = node;
// _WaitSet is a two-way circular list
node->_prev = node;
node->_next = node;
} else {
/ / head node
ObjectWaiter* head = _WaitSet ;
// The prev of the head of the loop chain is the tail
ObjectWaiter* tail = head->_prev;
assert(tail->_next == head, "invariant check");
// Insert node into the tail of _WaitSettail->_next = node; head->_prev = node; node->_next = head; node->_prev = tail; }}Copy the codeThe AddWaiter function is a relatively simple implementation that initializes a _WaitSet list and inserts node to the end of the _WaitSet queue, which is a circular, bidirectional list.
After the thread completes the insertion queue operation, it continues to call the exit function to release the monitor lock and suspend itself.
2. Implement notify on the VM
NotifyAll is called to wake up the consumer thread after the producer has produced the bread. Here we take notify as an example to see the implementation of the notify function in objectMonitor. CPP
void ObjectMonitor::notify(TRAPS) {
int Policy = Knob_MoveNotifyee ;
// Fetch the ObjectWaiter queue from _WaitSet
ObjectWaiter * iterator = DequeueWaiter() ;
if(iterator ! =NULL) {
ObjectWaiter * List = _EntryList ;
// Execute different logic according to the Policy. The default value of Policy is 2
if (Policy == 0) { // prepend to EntryList
// ...
} else if (Policy == 1) { // append to EntryList
// ...
} else if (Policy == 2) { // prepend to cxq
// prepend to cxq
if (List == NULL) {
iterator->_next = iterator->_prev = NULL ;
_EntryList = iterator ;
} else {
iterator->TState = ObjectWaiter::TS_CXQ ;
for (;;) {
ObjectWaiter * Front = _cxq ;
iterator->_next = Front ;
if (Atomic::cmpxchg_ptr (iterator, &_cxq, Front) == Front) {
break; }}}}else if (Policy == 3) { // append to cxq
// ...}}// ...
}
Copy the codeIn the notify function, Knob_MoveNotifyee is assigned to Policy, and Knob_MoveNotifyee is a constant with a value of 2, so we’ll only focus on the case where Policy is 2. DequeueWaiter() is a function with the following code:
inline ObjectWaiter* ObjectMonitor::DequeueWaiter(a) {
// dequeue the very first waiter
ObjectWaiter* waiter = _WaitSet;
if (waiter) {
DequeueSpecificWaiter(waiter);
}
return waiter;
}
Copy the codeThis function takes the _WaitSet set and assigns it to the iterator. If the iterator is not NULL, there is a blocked thread.
We then assign _EntryList to List, and if List is NULL, there is no thread waiting to acquire the lock. The iterators in the block are then formed into a two-way loop list and _EntryList is pointed to the iterator. Indicates that the blocking thread is able to acquire the lock, but the thread has not yet been awakened.
If _EntryList is not NULL, interator is added to the _CXQ queue through CAS and the _CXQ pointer points to Interator.
You can see that the notify function only queues the thread and does not actually wake it up. The actual operation to wake up the thread is in exist, which is executed after the VIRTUAL machine reads the Monitorexist instructions. The simplified code of Exist is as follows:
void ObjectMonitor::exit(bool not_suspended, TRAPS) {
// ...
for (;;) {
ObjectWaiter * w = NULL ;
// QMode defaults to 0
int QMode = Knob_QMode ;
if (QMode == 2&& _cxq ! =NULL) {
/ /... This takes the head node from the _CXq queue and wakes it up, regardless of omission.
return ;
}
// ...
w = _EntryList ;
// Check whether _EntryList is empty
if(w ! =NULL) {
assert (w->TState == ObjectWaiter::TS_ENTER, "invariant");// _EntryList is not empty, and directly wakes up the head of the _EntryList queue
ExitEpilog (Self, w) ;
return ;
}
// _EntryList is empty, point w to _CXq
w = _cxq ;
if (w == NULL) continue ;
// ...
if (QMode == 1) {
// ...
} else {
// The _CXq queue is not empty
// QMode == 0 or QMode == 2
// If the _CXq queue is empty, point _EntryList to _CXq queue
_EntryList = w ;
ObjectWaiter * q = NULL ;
ObjectWaiter * p ;
// Create a bidirectional ring list
for(p = w ; p ! =NULL ; p = p->_next) {
guarantee (p->TState == ObjectWaiter::TS_CXQ, "Invariant"); p->TState = ObjectWaiter::TS_ENTER ; p->_prev = q ; q = p ; }}if(_succ ! =NULL) continue;
w = _EntryList ;
if(w ! =NULL) {
guarantee (w->TState == ObjectWaiter::TS_ENTER, "invariant");// Wake up the _EntryList header
ExitEpilog (Self, w) ;
return; }}// Release lock and wake up thread
void ObjectMonitor::ExitEpilog (Thread * Self, ObjectWaiter * Wakee) {
assert (_owner == Self, "invariant");// Exit protocol:
// 1. ST _succ = wakee
// 2. membar #loadstore|#storestore;
// 2. ST _owner = NULL
// 3. unpark(wakee)
_succ = Knob_SuccEnabled ? Wakee->_thread : NULL ;
ParkEvent * Trigger = Wakee->_event ;
Wakee = NULL ;
/ / releases the lock
OrderAccess::release_store_ptr (&_owner, NULL); OrderAccess::fence() ; // ST _owner vs LD in unpark()
// Wake up the thread
Trigger->unpark() ;
/ /...
}
Copy the codeThe code of exist is rather complicated, which has been simplified here. Since the default value of QMode is 0, only this case will be discussed.
1) First, if _EntryList is not NULL, ExitEpilog is called directly to fetch the header from _EntryList and wake up the thread;
2) If _EntryList is NULL, but _CXQ queue is not NULL, then fetch all the elements in _CXQ queue and construct a two-way ring-linked list, assign _EntryList to it, and set _CXQ to NULL;
3) Finally, the ExitEpilog function is called to release the lock and wake up the _EntryList header.
Third, summary
This article starts from a simple “producer-consumer” model, recognizes wait and notify/notifyAll methods in Object, and deeply analyzes the implementation of these two methods in virtual machine. The synchronized keyword in Java code by the compiler compiled into bytecode monitorenter/monitorexist instruction, when the virtual machine to execute commands to the relevant will call virtual machine related to the underlying function, take the lock and the operation of the lock is released. Because the lock Object is associated with the Monitor Object, wait and notify/notifyAll can be called to block and wake up threads on this Object instance. The wait function encapsulates the thread as WaitObject and puts it into the wait queue, while the notify/notifyAll function takes out the thread object and puts it into the EntryList queue and wakes up after releasing the lock.
The wait and wake mechanism of synchronized locks obviously has one drawback. Using the producer-consumer model as an example, because both producer and consumer threads are added to the same WaitSet queue, notifyAll cannot precisely control which type of thread is awakened. And in this time, thoroughly understand the Java ReentranLock implementation principle in this article we know ReentranLock, ReentranLock and synchronized have similar wait and wake up mechanism, and can accurately control the specified thread wake up. So how does ReentranLock work? We’ll talk about that next time.
Reference & Recommended reading
Blocking (3) : CXQ, EntryList, and WaitSet