preface
Thread concurrency series:
Thread State Java Thread State Java Thread State Java Thread State Java Thread State Java Thread State Java Thread State Java Thread State Java Thread State Java Thread State Java Thread State Java Thread State Unsafe/CAS/LockSupport Application and principle Java concurrency “lock” nature (step by step to implement the lock) Java Synchronized implementation of mutual exclusion application and source exploration Java object header analysis and use (Synchronized related) Java The evolution process of Synchronized partial lock/lightweight lock/heavyweight lock Java Synchronized principle of heavyweight lock in depth (mutual exclusion) Java Synchronized principle of heavyweight lock in depth (synchronization) Java concurrency AQS In-depth analysis (on) the Java concurrency of AQS deep parsing (under) Java Thread. Sleep/Thread. Join/Thread. The yield/Object. Wait/Condition. Await explanation of Java concurrency Already the thorough analysis of concurrent Java (with Synchronized difference) Java Semaphore/CountDownLatch/CyclicBarrier ReentrantReadWriteLock in-depth analysis Deep parsing (principle), Java Semaphore CountDownLatch/CyclicBarrier in-depth analytical (application), the most detailed graphic analytic Java various locks (ultimate) thread pool will understand series
The previous article analyzed the evolution of biased locking and lightweight locking. This article will analyze the main part: the principle of heavyweight locking. Through this article, you will learn:
1. Application of ObjectMonitor 2. Expansion process of lock 3. Locking process of heavyweight lock 4
1. Application of ObjectMonitor
We know that when the Lock is in the lightweight Lock state, the Mark Word holds a pointer to the Lock Record, which is thread private. However, in the heavyweight lock state, it means that some thread does not get the lock and needs to block waiting for the lock. When the thread with the lock releases the lock, it wakes up to continue competing for the lock. This raises the question: How do other threads find blocked threads? It’s easy to think of blocking threads in a list shared by multiple threads. Lock Record is thread-private, which obviously doesn’t meet the requirements. Therefore, the ObjectMonitor class is introduced for heavyweight locks.
#ObjectMonitor. HPP ObjectMonitor() {// Mark Word _header = NULL; _count = 0; // The number of threads waiting for a lock _waiters = 0, // The number of threads re-entry _recursions = 0; _object = NULL; // The Lock itself points to the thread or Lock Record _owner = NULL; // Wait () _WaitSet = NULL; // Wait queue lock _WaitSetLock = 0; _Responsible = NULL ; _succ = NULL ; //ObjectWaiter queue _cxq = NULL; FreeNext = NULL ; //ObjectWaiter queue _EntryList = NULL; _SpinFreq = 0 ; _SpinClock = 0 ; OwnerIsThread = 0 ; _previous_owner_tid = 0; }Copy the codeIt can be seen that the Lock Record has information in ObjectMonitor, such as Mark Word _header field, store pointer to the object header _object field. Of course, ObjectMonitor has more information, such as queue _CXQ where the lock fails to be acquired and queue _WaitSet where the thread waits after the wait() method is called.
2, lock expansion process
Now that you know you have ObjectMonitor, let’s see how you can use it. Reviewing the previous analysis, when a bias Lock is upgraded to a lightweight Lock, the Mark Word needs to be modified to point to Lock Record, and when a lightweight Lock is upgraded to a heavyweight Lock, the Mark Word needs to be modified to point to ObjectMonitor. The process of creating/acquiring an ObjectMonitor object is the bulking of the lock. The inflate process in the source code is a inflate(xx) function:
#synchronizer.cpp ObjectMonitor * ATTR ObjectSynchronizer::inflate (Thread * Self, oop object) { ... // loop endlessly until ObjectMonitor is obtained for (;;) Const markOop Mark = object-> Mark (); ObjectMonitor * inf = mark->monitor(); if (mark->has_monitor()) {ObjectMonitor * inf = mark->monitor(); return inf ; } // if (mark == markOopDesc::INFLATING()) {// Continue the loop and wait for the INFLATING to complete. } if (mark->has_locker()) {// Assign ObjectMonitor object ObjectMonitor * m = omAlloc (Self); // initialize some parameters m->Recycle(); m->_Responsible = NULL ; m->OwnerIsThread = 0 ; m->_recursions = 0 ; m->_SpinDuration = ObjectMonitor::Knob_SpinLimit ; // Consider: Maintain by type/class // Try to change Mark Word to inflated state, now Mark Word is all 0 --------->(1) MarkOop CMP = (markOop) Atomic:: cMPxchg_ptr (markOopDesc::INFLATING(), object->mark_addr(), mark); if (cmp ! OmRelease (Self, m, true); continue ; Mark Word markOop DMW = Mark ->displaced_mark_helper(); // Interference -- just retry} M ->set_header(DMW); Lock Record------->(2) m->set_owner(mark->locker()); M ->set_object(object); ------->(3) object->release_set_mark(markOopDesc::encode(m)); . // Successful, return ObjectMonitor object m; } // ObjectMonitor * m = omAlloc (Self); // initialize some parameters m->Recycle(); Mark m->set_header(mark); / / _owner NULL -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- > (4) the m - > set_owner (NULL); m->set_object(object); m->OwnerIsThread = 1 ; m->_recursions = 0 ; m->_Responsible = NULL ; m->_SpinDuration = ObjectMonitor::Knob_SpinLimit ; // consider: Keep metastats by type -------------------->(5) if (Atomic::cmpxchg_ptr (markOopDesc::encode(m), object->mark_addr(), mark) ! = mark) { ... // Fail, retry continue; }... // Successful, return ObjectMonitor object m; }}Copy the code(1) If the current lock is a lightweight lock, it means that some thread is holding the lock, and try CAS to change the lock to the inflated state. (2) _owner does not refer to any thread, but to Lock Reocrd, which will be determined later. (3) In the case of lightweight Lock, Mark Word stores the pointer to Lock Record, but now it becomes the pointer to the heavyweight Lock, that is, the pointer to ObjectMonitor. This is a single-threaded operation, so you can set it directly. MarkOopDesc ::encode(m) is defined as follows:
#markOop.hpp static markOop encode(ObjectMonitor* monitor) { intptr_t tmp = (intptr_t) monitor; / / Mark Word pointing ObjectMonitor return (markOop) (TMP | monitor_value); }Copy the code(4) If the current lock is unlocked, set _owner to null. (5) CAS tries to point Mark Word to ObjectMonitor.
The above is the expansion process, which is shown as follows:
3, heavyweight lock lock process
First attempt at locking
Review the core of biased locking and lightweight locking process: modify Mark Word. The Mark Word is also modified when ballooning to a heavyweight lock, except that there is no thread holding the heavyweight lock. Take a look at the preemption process for heavyweight locks:
#ObjectMonitor. CPP void ATTR ObjectMonitor:: Enter (TRAPS) {// The current Thread * const Self = Thread; void * cur ; Cur = Atomic::cmpxchg_ptr (Self, & _OWNER, NULL); If (cur == NULL) {return (cur == NULL); If (cur == Self) {if (cur == Self) {recursions ++; return ; If (Self->is_lock_owned ((address)cur)) {// recursions = 1; // Change the current thread _owner = Self; OwnerIsThread = 1 ; return ; }... {... for (;;) {// If no lock is obtained, EnterI (THREAD) is executed; . _recursions = 0 ; _succ = NULL ; exit (false, Self) ; jt->java_suspend_self(); }}Copy the codeThe enter(xx) function does the following:
CAS attempts to modify the _owner field of the ObjectMonitor. The result is as follows: 1. The lock is not occupied by any other thread, and the current thread successfully obtains the lock. 2. The lock is occupied by the current thread. The current thread re-enters the lock and successfully obtains the lock. 3. The lock is occupied by the LockRecord, which belongs to the current thread and belongs to the reentrant. The reentrant count is 1. 4. If none of the above conditions is met, call EnterI().
It is shown as follows:
Try locking again
After the initial failure to acquire the lock, the following flow occurs, which is the implementation of the EnterI() function:
CPP void ATTR ObjectMonitor::EnterI (TRAPS) {// Thread * Self = Thread; / / try to lock -- -- -- -- -- -- -- -- -- -- - > (1) if (TryLock (Self) > 0) {return; } / / try to spin lock -- -- -- -- -- -- -- -- -- -- - > (2) if (TrySpin (Self) > 0) {return; ObjectWaiter node(Self); // Suspend/wake up the thread reset parameter Self->_ParkEvent->reset(); Node._prev = (ObjectWaiter *) 0xBAD; Node. TState = ObjectWaiter::TS_CXQ; ObjectWaiter * nxt ; for (;;) { node._next = nxt = _cxq ; / / insert node _cxq queue head -- -- -- -- -- -- -- -- -- -- - > (3) if (Atomic: : cmpxchg_ptr (& node, & _cxq, NXT) = = NXT) break; / / try to acquiring a lock -- -- -- -- -- -- -- -- -- -- - > (4) if (TryLock (Self) > 0) {return; }}... for (;;) {/ / acquiring a lock to try again -- -- -- -- -- -- -- -- -- -- - > (5) if (TryLock (Self) > 0) break; if ((SyncFlags & 2) && _Responsible == NULL) { Atomic::cmpxchg_ptr (Self, &_Responsible, NULL) ; } / / hung thread -- -- -- -- -- -- -- -- -- -- - > (6) if (_Responsible = = Self | | (SyncFlags & 1)) {/ / hang a timeout Self - > _ParkEvent - > park ((jlong) RecheckInterval) ; } else {// Suspend without timeout Self->_ParkEvent->park(); } / / wake after acquiring a lock again, success is out of the loop - -- -- -- -- -- -- -- -- -- -- > (7) if (TryLock (Self) > 0) break; / /... // Remove nodes from _cxq or _EntryList ----------->(8) UnlinkAfterAcquire (Self, &node); . return ; }Copy the code(1) TryLock, as the name implies, attempts to acquire the lock:
#ObjectMonitor.cpp int ObjectMonitor::TryLock (Thread * Self) { for (;;) {//for loop name dead void * own = _owner; If (own! = NULL) return 0 ; _owner if (Atomic::cmpxchg_ptr (Self, &_owner, NULL) == NULL) {return 1; } if (true) return -1 ; }}Copy the code(2) TryLock only performs the CAS once, while TrySpin does what the name suggests: spin the lock.
#ObjectMonitor.cpp int ObjectMonitor::TrySpin_VaryDuration (Thread * Self) { ... for (ctr = Knob_PreSpin + 1; --ctr >= 0 ; ) { if (TryLock(Self) > 0) { ... return 1 ; } // pause (); }... }Copy the codeYou can see that TryLock is called 10 times in TrySpin. The source code indicates that an xp value of 20-100 is probably best. (3) This is an infinite loop until the queue is inserted successfully or the lock is acquired. This is writing to _CXQ, and its _next pointer points to _CXQ, so each new node is put in the queue head. CAS is required because there may be multithreaded changes to _CXQ. (4) After the queue fails to be inserted, try again to obtain the lock. (5) Another endless loop, trying to acquire the lock first. (6) At this point, the thread gives up acquiring the lock, suspends itself, and blocks waiting for another thread to wake it up. (7) When a thread wakes up the thread suspended in (6), the awakened thread immediately tries to acquire the lock again. If it still fails, it continues the loop back to (5). (8) After the lock is successfully obtained, the node needs to be removed from the queue (_CXq /_EntryList) because the preceding node has been added to the queue.
From the analysis of (1) to (8) above, it can be seen that the enterI() function mainly does the following things:
1. Multiple attempts to lock. Wrap the thread and add it to the blocking queue. 3. Try again to acquire the lock. 4. Hang yourself after failure. 5. Continue trying to acquire the lock after being woken up. 6, the success of the exit process, failure to continue to step on the process.
It is shown as follows:
4. Unlocking process of heavyweight lock
The above analysis of the locking process, which has two results:
1. If the lock is successfully acquired, the critical section code can be executed. 2. Failed to obtain the lock, and suspended to wait for someone to wake up.
Consider a question about 2: Who awakens it and how? If the thread fails to release the critical section code, it will enter the process of releasing the heavy lock. The release process of the heavyweight lock, namely the implementation of exit() :
#ObjectMonitor.cpp void ATTR ObjectMonitor::exit(bool not_suspended, TRAPS) { Thread * Self = THREAD ; -------->(1) if (THREAD! If (THREAD->is_lock_owned((address) _owner)) {if (THREAD->is_lock_owned((address) _owner)) { } else {// return; } } if (_recursions ! = 0) {// recursions--; return ; }... for (;;) OrderAccess::release_store_ptr (&_owner, NULL); if (Knob_ExitPolicy == 0) {if (Knob_ExitPolicy == 0) { // drop the lock OrderAccess::storeload() ; // If there are no threads waiting at _cxq/_EntryList, Directly out of the if ((intptr_t (_EntryList) | intptr_t (_cxq)) = = 0 | | _succ! = NULL) { TEVENT (Inflated exit - simple egress) ; return ; } if (Atomic::cmpxchg_ptr (THREAD, &_owner, NULL)! = NULL) {return; } } else { ... } ObjectWaiter * w = NULL ; int QMode = Knob_QMode ; // By default QMode=0 w = _EntryList; // By default, QMode=0 w = _EntryList; if (w ! = NULL) {/ / _EntryList not empty, the lock is released -- -- -- -- -- -- -- -- - (2) ExitEpilog (Self, w); return ; } // if _EntryList is empty, check whether _cxq has data w = _cxq; if (w == NULL) continue ; // Do not continue the loop for (;;) {// NULL _cxq header ObjectWaiter * u = (ObjectWaiter *) Atomic:: cMPxCHg_ptr (NULL, &_CXq, w); if (u == w) break ; w = u ; } if (QMode == 1) { ... } else {// QMode == 0 or QMode == 2 //_EntryList points to _cxq _EntryList = w; ObjectWaiter * q = NULL ; ObjectWaiter * p ; // The purpose of this loop is to connect the node precursors in _EntryList ---------(3) 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 ; } } w = _EntryList ; if (w ! = NULL) {/ / releases the lock -- -- -- -- -- -- -- -- -- (4) ExitEpilog (Self, w); return ; }}}Copy the codeThe exit() function does the following: (1) If the expansion Lock is a lightweight Lock, then _owner points to the Lock Record. This is where the owner of a lightweight lock walks after releasing the lock, so the thread releasing the lock is not necessarily the owner of the heavyweight lock. ExitEpilog (Self, w)
void ObjectMonitor::ExitEpilog (Thread * Self, ObjectWaiter * Wakee) {ParkEvent ParkEvent * Trigger = Wakee->_event; Wakee = NULL ; OrderAccess::release_store_ptr (& _OWNER, NULL); OrderAccess::fence() ; // ST _owner vs LD in unpark() // Trigger->unpark(); }Copy the codeInside release_store_ptr are atomic operations implemented by assembly statements. (3) Before _EntryList only used the backward-driven node, that is, the queue implemented by one-way linked list. Here the front-driven node is used, that is, _EntryList becomes bidirectional linked list. (4) and (2) the same function, release the lock and wake up the corresponding thread.
Let’s take a look at question 2 above, as we know from the lock release process:
The thread currently holding the lock releases the lock and wakes up the blocking thread waiting for the lock
The default QMode=0 is used as an example:
1. If the _EntryList queue is not empty, fetch the _EntryList queue head node and wake up. 2. If _EntryList is empty, point _EntryList to _CXQ and wake up the queue head node.
It is shown as follows:
5, heavyweight lock summary
It can be clearly seen from the process of locking and unlocking:
1, lock process is constantly trying to lock, really can not put in the queue, and still insert the queue head position, and finally suspend themselves. 2. Imagine A scenario where thread A is holding the lock and thread B is waiting in the queue. When thread A releases the lock, thread C comes in to acquire the lock. Thread B’s unqueued behavior creates an unfair race lock. 3. Imagine another scenario: thread A still holds the lock, thread B waits in the queue, and thread C also wants to acquire the lock, so it enters the queue head, which is in front of thread B. When A releases the lock, it wakes up the head node in the queue, which is thread C. C thread queue-jumping causes unfair competition lock. 4, Because there is no queue, there is a heavy lock is not fair.
The overall locking and unlocking process is shown as follows:
The scenarios corresponding to the flow in the figure are as follows:
1. Thread A preempts the lock first. Thread A has successfully acquired the lock before entering the blocking queue. 2. Thread B then preempts the lock, finds the lock already occupied, and joins the blocking queue. 3. Finally, thread C also preempts the lock, finds that the lock has been occupied, and joins the queue head of the blocking queue. At this time, thread B has been occupied by thread C. 4. When A releases the lock, it wakes up C, the queue head thread in the blocking queue, and C starts to preempt the lock. 5. After C gets the lock, remove himself from the blocking queue. 6. Follow the same process as before.
The above process may be boring, but use code to illustrate the above scenario:
public class TestThread { static Object object = new Object(); static Thread a, b, c; public static void main(String args[]) { a = new Thread(new Runnable() { @Override public void run() { System.out.println("A before get lock"); synchronized (object) { System.out.println("A get lock"); try { Thread.sleep(1000); b.start(); Thread.sleep(1000); c.start(); Thread.sleep(2000); } catch (Exception e) { } } System.out.println("A after get lock"); }}); a.start(); b = new Thread(new Runnable() { @Override public void run() { System.out.println("B before get lock"); synchronized (object) { System.out.println("B get lock"); } System.out.println("B after get lock"); }}); b.start(); c = new Thread(new Runnable() { @Override public void run() { System.out.println("C before get lock"); synchronized (object) { System.out.println("C get lock"); } System.out.println("C after get lock"); }}); c.start(); }}Copy the codeThe output is fixed each time:
It can be seen that it is consistent with our expectation: although B preempts the lock first, IT is always grabbed by C, the latecomer, which shows the unfairness.
6. Comparison with biased locks and lightweight locks
So far, bias lock, lightweight lock, heavyweight lock have been analyzed. The core of locking is who is the lock?
For bias locks and lightweight locks, “lock” is the Mark Word. For heavyweight locks, the “lock” is ObjectMonitor.
For more information on the similarities and differences of the three and how they apply, please refer to the previous article:Java Synchronized is an evolution of the lock/lightweight/heavyweight bias
This article examines the mutual exclusion process for heavyweight locks, and the next article will examine the synchronization process (wait/notify/notifyAll) closely related to heavyweight locks.
This article source based on JDK1.8.