Synchronized talked to the interviewer for half an hour

This is the second in a series of articles about Angela and her Interviewer that synchronized Talked to her Interviewer for half an Hour.

Follow the wechat official account [Angela’s blog] to receive first hand news

Historical article (constantly updated) : “A HashMap Waffled with an interviewer for half an hour [1]”

preface

After half an hour of talking with the interviewer about HashMap, zhong Kui arrived at the second interview without weakening the former. Zhong Kui, dressed in a slightly yellowed checkered robe, stands across from Angela and begins his attack, which Angela is most impressed by is the mage’s synchronized hook.

The opening

Interviewer: Why don’t you introduce yourself first?

Angela: I am Angela, one of the grass three bitches, the strongest single (Zhong Kui cold hum)! I am **. I am currently working in — company as a system developer.

Interviewer: Can you tell me something about synchronized?

Angela: [drops hook, asks me if I ate without making any small talk] Yeah, well, there was something about synchronized.

Interviewer: Tell me about synchronized. When is synchronized used?

Angela: This is about multi-threaded access to shared resources. When a resource may be accessed and modified by multiple threads at the same time, locks are needed. Let me draw a picture for you.

Insert a picture description here

Angela: As shown in the figure above, for example, in honor of Kings, we have two threads counting the economy of offspring and Angela respectively. Thread A reads the current economy of the team from memory and loads it into the thread’s local stack. After the +100 operation, thread B also writes the economy value + 200 from memory and writes 200 back to memory. Thread B has just finished writing, and thread A has written 100 back into memory, so we have A problem. Our economy should be 300, but we have 100 in memory.

Interviewer: Can you tell me about synchronized?

Angela: Lock when accessing a race resource, because multiple threads modify the economy value, so the economy value is a static resource, show you? Here is the unlocked code and console output, please have a look:

Two threads, thread A makes the economy +1 and thread B makes the economy + 2, each execute 1000 times. The correct result should be 3000, but the result is 2845.

Insert a picture description here

Angela: 👇 this is the locked code and console output.

(img-6NwdhDEz-1585279691724)(/Users/zw/Library/Application Support/typora-user-images/image-20200321210555529.png)]

Interviewer: I see 👆 you use synchronized to lock code blocks. Is there anything else synchronized can do?

Angela: Well, synchronized has three areas of action:

  1. Lock static methods;

  2. Locking on non-static methods;

  3. Lock code blocks;

    Sample code is as follows

    public class SynchronizedSample {



        private final Object lock = new Object();



        private static int money = 0;

    		// Non-static methods

        public synchronized void noStaticMethod(a){

            money++;

        }

    		// Static method

        public static synchronized void staticMethod(a){

            money++;

        }

    		

        public void codeBlock(a){

          	/ / code block

            synchronized (lock){

                money++;

            }

        }

    }

    Copy the code

Interviewer: Do you know the difference between synchronized and other areas of use?

Angela: I see. First, let’s be clear: the lock is on the object, we’re locking on the object.

✖️ 3 (This is why wait/notify must be performed after the lock is held. The lock must be held before it is released.)

The difference between the three scopes is actually the difference between the locked objects, as shown in the following table:

scope Lock object
Nonstatic method Current object => this
A static method Class => SynchronizedSample.class (Everything is an object, this is a class object)
The code block Specify object => Lock (as in the code above)

Interviewer: Do you know how the JVM uses synchronized to lock objects and secure multithreaded access to race resources?

Angela: (⊙o⊙)… Well, it’s a bit complicated, but I’m afraid I don’t have enough time. Why don’t we make an appointment next time?

Interviewer: don’t next time, today I have plenty of time, you slowly speak, I slowly 👂 you say.

Angela: I’ll have to talk to you about it. Divided into two time periods to discuss with you, first said to Pan Gu created the world, Nu Wa built stone to repair the sky, cough cough, sorry to pull away……

  1. Before JDK6, synchronized was still a heavyweight Lock, equivalent to the Green Dragon Crescent Blade in Guan’s hands. Every time synchronized was implemented, it depended on the operating system Mutex Lock, which involved the operating system to switch the thread from user state to kernel state, and the switching cost was very high.
  2. In JDK6, the researchers introduced biased locking and lightweight locking because Sun programmers found that most programs did not have multiple threads accessing a race resource at the same time most of the time. Each thread was locked and unlocked, and the operating system had to cut back and forth between user and kernel mode each time, which was too costly.

Interviewer: Tell me, respectively, why synchronized was so important before JDK 6? What about bias locking and lightweight locking after JDK6?

Angela: Ok. Firstly, to understand the realization principle of synchronized, two preparatory knowledge should be understood:

  1. The first preparation knowledge: need to know the Java object header, lock type and state are closely related to the object header Mark Word;

    Synchronized locks are associated with object headers. Let’s look at the structure of the object:Objects are stored in the heap, which is mainly divided into three parts: object header, object instance data and alignment fill (array object has one more area: record the length of array). The following three parts are briefly described, although synchronized is only related to Mard Word in object header.

    1. Object:

      The object header is divided into two sections, Mard Word and Klass Word, and 👇 lists the details:

      Object header structure Store information – Note
      Mard Word Store information such as the object’s hashCode, lock information, or generational age or GC flag
      Klass Word Stores Pointers to the object’s owning class (metadata), which the JVM uses to determine which class the object belongs to

    2. Object instance data:

      As shown in the figure above, the member variable data in the class belongs to the object instance data;

    3. Align fill:

      The JVM requires objects to occupy multiples of eight to facilitate memory allocation (in bytes), so this part is used to fill up insufficient space.

  2. Second prep: You need to understand Monitor, that every object has a Monitor object associated with it; The Monitor object properties are shown below (Hospot 1.7 code).

    // the 👇 figure details the role of important variables

    ObjectMonitor() {

        _header       = NULL;

        _count        = 0;   // Reentrant times

        _waiters      = 0.// Number of waiting threads

        _recursions   = 0;

        _object       = NULL;

        _owner        = NULL;  // The thread currently holding the lock

        _WaitSet      = NULL;  // The thread that called wait is blocked and placed here

        _WaitSetLock  = 0 ;

        _Responsible  = NULL ;

        _succ         = NULL ;

        _cxq          = NULL ;

        FreeNext      = NULL ;

        _EntryList    = NULL ; // The thread waiting for the lock to be in the block is eligible as a candidate resource thread

        _SpinFreq     = 0 ;

        _SpinClock    = 0 ;

        OwnerIsThread = 0 ;

      }

    Copy the code

    The ObjectMonitor object associated with the ObjectMonitor object has an internal thread contention mechanism, as shown below:

Interviewer: I have read the two prepared knowledge, behind tell me about JDK 6 before synchronized concrete implementation logic.

Angela: Ok. [Start my show]

  1. When two threads A and B both started to give our team’s economic money variable + money, they found that synchronized lock was added to the method when they wanted to operate. At this time, thread A was scheduled to execute it, and thread A got the lock first. -1.1 Set _owner in MonitorObject to thread A; -1.2 Set mark Word to the address of the Monitor object and change the lock flag bit to 10. -1.3 Block thread B and put it on ContentionList queue;

  2. The JVM takes one thread at a time from the end of the Waiting Queue and places it on OnDeck as a candidate. However, if the concurrency is high, the Waiting Queue will be CAS performed by a large number of threads. In order to reduce the competition for tail elements, The Waiting Queue is split into ContentionList and EntryList queues, and the JVM moves some threads to EntryList as preparatory threads for OnDeck. A few additional points:

    • All threads requesting locks are first placed in ContentionList, a ContentionList queue;

    • The threads in the Contention List that qualify as candidate resources are moved to the Entry List.

    • At any one time, at most one thread is competing for the lock resource, and that thread is called OnDeck;

    • The thread that has obtained the resource is called Owner.

    • The ContentionList, EntryList, and WaitSet threads are all blocked by the operating system (pthread_mutex_lock in The Linux kernel).

  3. The Owner of thread A may call the wait lock to release the lock. At this time, thread A enters the wait Set and waits to be awakened.

That’s how SYNCHRONIZED was implemented prior to JDK 6.

Interviewer: Do you know whether synchronized is fair or unfair?

Angela: It’s not fair. There are two main reasons:

  • When Synchronized threads compete for locks, the first thing Synchronized does is not to queue up directly in the ContentionList queue, but to try to obtain the lock by spin (there may be other threads waiting for the lock in the ContentionList). If the lock cannot be obtained, Synchronized enters the ContentionList. This is obviously unfair to threads that are already in the queue;
  • Another injustice is that a thread that spins to acquire the lock may also directly preempt the lock resource of the OnDeck thread.

Interviewer: You mentioned earlier that synchronized was optimized after JDK 6. Tell me about it?

Angela: Don’t worry! Let me order some therapy, and we’ll talk about it. The Mark Word storage structure of the object header is shown in the following figure and the source code notes (for example, the following discussion is based on the background of the 32-bit JVM, 64-bit will be specified). In order to save storage space, Mard Word can express the complete state information with 4 bytes. Of course, the object can only be one of the following 5 states at a certain time.

Here is a simplified Version of Mark Word

Hash: Saves the hash code of an object

Age: generational age of the saved object

Biased_lock: bias lock identifier bit

Lock: identifier of the lock status

JavaThread* : Holds the ID of the thread holding the biased lock

Epoch: Save the bias timestamp

Copy the code

Angela: JDK 6 improved to include biased and lightweight locks because of two problems with synchronized heavyweight locks:

  • Depending on the implementation of mutex related instructions of the underlying operating system, locking and unlocking need to switch between user mode and kernel mode, resulting in significant performance loss.

  • Researchers have found that locking and unlocking of most objects is done in a specific thread. That is, there is a low probability of threads competing for locks. They did an experiment, looking for some typical software, to test the repeat rate of the same thread lock unlocking, as shown in the figure below, you can see that the repeat lock rate is very high. Early JVMS wasted 19% of their execution time on locks.

Insert a picture description here

Thin locks are a lot cheaper than inflated locks, but their performance suffers from the fact that every compare-and-swap operation must be executed atomically on multi-processor machines, although most objects are locked and unlocked only by one particular thread.

It was reported that 19% of the total execution time was wasted by thread synchronization in an early version of Java Virtual machine.

Interviewer: Can you tell me how synchronized went from no lock to biased lock since JDK 6?

Angela: It’s OK! Jm-xx :+UseBiasedLocking To enable biased locking:

Insert a picture description here
  1. First Thread A accesses the synchronization code block and uses the CAS operation to place the Thread ID inMark WordIn the middle;
  2. If the CAS succeeds, thread A acquires the lock
  3. Revoke bias if the CAS fails, another thread (such as thread B) holds the lock.
  4. Lock removal process: – Let thread A block at the global safe point (similar to thread before GC blocked at the safe point) – traverse the thread stack to see if there is A Lock Record of the locked object, if there is A Lock Record, need to repair the Lock Record and Markword, make it become unlocked state. – Restore thread A – set the status of whether the lock is biased to 0 and start the lightweight lock process (described later) as illustrated in the following figureMark WordTransformation in this process The interviewer: Good, so tell me how biased lock undo went to lightweight lock? And when does a lightweight lock become a heavyweight lock?Angela: Continue the above process, after the lock is removed (bias lock state is 0), now whether thread A or thread B executes to the synchronized code block to lock, the process is as follows:
    • A thread creates a LockRecord in its own frame.
    • Thread A willMark WordCopy to Lock Record of thread stack, this location is called displayced HDR, as shown below:
    • Points the Owner pointer in the lock record to the locked object (holding the object address).
    • Replace the MarkWord in the object header of the lock object with a pointer to the lock record. The two steps are shown below:
  5. The lock flag bit becomes 00, indicating a lightweight lock

The interviewer: Seems to know a lot about synchronized. When will the lightweight lock be upgraded to the heavyweight lock, please answer?Angela: When a lock is upgraded to a lightweight lock, if there is still a new thread competing for the lock, the new thread will spin to try to acquire the lock. After a certain number of attempts (default is 10), the lock will be upgraded to a heavyweight lock.The interviewer: Why?AngelaIf thread B spins for a short period of time, it is easy to get the lock. If thread B spins for a short period of time, it is easy to get the lock. If thread B spins for a short period of time, it is not easy to get the lock. This is the process of lock inflation. Below is the transformation diagram of Mark Word and lock stateMain 👆 chart I marked out, the lock is currently biased state, biased lock state position is 1, see a lot of online articles are written wrong, write here only the lock bias will be set to 1, must pay attention to.The interviewer: Since biased locks have retracted, will expand, performance loss is so large, still need to use them?Angela: If it is determined that the race resource will be accessed by high concurrency, it is recommended to pass-XX:-UseBiasedLockingParameter close biased locking, the benefits of biased locking is concurrent degree is low, the same thread locks don’t need memory copy operation, removes lightweight Lock the Lock Record in thread stack zhongjian, copy the contents of the Mark Down, also forgave heavyweight Lock the underlying operating system user mode to kernel mode switch, because the previous said, System instructions are required. In addition, Hotspot has also made another optimization based on the lock object epoch batch offset and batch undo offset, which greatly reduces the CAS of biased locks and the loss caused by lock revocation. 👇 figure is the pressure measurement done by the researchers:

Eliminating Synchronization-Related Atomic Operations with Biased Locking and Bulk Rebiasing

Angela: They conducted tests on several typical software, and found that batch undo biased lock and batch add biased lock based on epoch can greatly improve throughput, but there is no special improvement in performance when the concurrency is very large.The interviewer: Yes, yes, but have you read the source code of synchronized?Angela: that of course, the source code is my two skills, high outbreak of damage can play out to see it, we step by step. Let’s compile the sample code from the beginning of this article into a class file and passjavap -v SynchronizedSample.classHow does synchronized work at the source level? As shown below: Angela: synchronized is implemented in code blocks through monitorenter and Monitorexit directives. Locking static methods and methods adds ACC_SYNCHRONIZED to the method’s flags. The JVM checks method flags when it runs the method, starts the locking process when it encounters a synchronization flag, and starts locking when it encounters a Monitorenter instruction inside the method.

Monitorenter instruction function source code in InterpreterRuntime: : monitorenter

IRT_ENTRY_NO_ASYNC(void, InterpreterRuntime::monitorenter(JavaThread* thread, BasicObjectLock* elem))

#ifdef ASSERT

  thread->last_frame().interpreter_frame_verify_monitor(elem);

#endif

  if (PrintBiasedLockingStatistics) {

    Atomic::inc(BiasedLocking::slow_path_entry_count_addr());

  }

  Handle h_obj(thread, elem->obj());

  assert(Universe::heap()->is_in_reserved_or_null(h_obj()),

         "must be NULL or an object");

 // Whether bias lock is enabled

  if (UseBiasedLocking) {

    // Try biased locking

    ObjectSynchronizer::fast_enter(h_obj, elem->lock(), true, CHECK);

  } else {

    // Lightweight locking logic

    ObjectSynchronizer::slow_enter(h_obj, elem->lock(), CHECK);

  }

  assert(Universe::heap()->is_in_reserved_or_null(elem->obj()),

         "must be NULL or an object");

#ifdef ASSERT

  thread->last_frame().interpreter_frame_verify_monitor(elem);

#endif

IRT_END

Copy the code

Biased lock code

// -----------------------------------------------------------------------------

//  Fast Monitor Enter/Exit

// This the fast monitor enter. The interpreter and compiler use

// some assembly copies of this code. Make sure update those code

// if the following function is changed. The implementation is

// extremely sensitive to race condition. Be careful.



void ObjectSynchronizer::fast_enter(Handle obj, BasicLock* lock, bool attempt_rebias, TRAPS) {

// Whether to use bias locking

 if (UseBiasedLocking) {

// If it is not globally safe

if (! SafepointSynchronize::is_at_safepoint()) {

// Get bias lock

      BiasedLocking::Condition cond = BiasedLocking::revoke_and_rebias(obj, attempt_rebias, THREAD);

      if (cond == BiasedLocking::BIAS_REVOKED_AND_REBIASED) {

        return;

      }

    } else {

assert(! attempt_rebias, "can not rebias toward VM thread");

// At the global safe point, undo bias lock

      BiasedLocking::revoke_at_safepoint(obj);

    }

assert(! obj->mark()->has_bias_pattern(), "biases should be revoked by now");

 }

// Enter the lightweight lock process

 slow_enter (obj, lock, THREAD) ;

}

Copy the code

The specific implementation code of BiasedLocking is in BiasedLocking::revoke_and_rebias. Because the function is very long, it will not be posted. Interested parties can read it in Hotspot 1.8-biasedlocking. Lightweight lock code flow

void ObjectSynchronizer::slow_enter(Handle obj, BasicLock* lock, TRAPS) {

// Get the object's markOop data mark

  markOop mark = obj->mark();

assert(! mark->has_bias_pattern(), "should not see bias pattern here");



// Check whether mark is lock-free and can not be biased (the lock identifier is 01 and the bias marker is 0)

  if (mark->is_neutral()) {

    // Anticipate successful CAS -- the ST of the displaced mark must

    // be visible <= the ST performed by the CAS.

// Save Mark to displaced_header in thread stack Lock Record

    lock->set_displaced_header(mark);

// CAS updates the Mark Down to a pointer to the lock object

    if (mark == (markOop) Atomic::cmpxchg_ptr(lock, obj()->mark_addr(), mark)) {

      TEVENT (slow_enter: release stacklock) ;

      return ;

    }

    // Fall through to inflate() ...

  } else

// The Lock Record of the current thread has been obtained by the pointer in mark.

  if (mark->has_locker() && THREAD->is_lock_owned((address)mark->locker())) {

assert(lock ! = mark->locker(), "must not re-lock the same lock");

assert(lock ! = (BasicLock*)obj->mark(), "don't relock with same BasicLock");

    lock->set_displaced_header(NULL);

    return;

  }



 lock->set_displaced_header(markOopDesc::unused_mark());

/ / lock expansion

  ObjectSynchronizer::inflate(THREAD, obj())->enter(THREAD);

Copy the code

If (mark-> neutral()) is_neutral()) : if (mark-> neutral()) is_neutral() : if (mark-> neutral()) is_neutral() Atomic:: CMPxchg_ptr is an Atomic operation, which ensures that only one thread can replace the Mark Word with displaced_header. Assuming that thread A succeeds in executing the Mark Word, it means that thread A has acquired the lock and continues to execute the synchronized code block. 3, failed to perform thread B, exit the critical section, through ObjectSynchronizer: : inflate method locks began to inflation;

Interviewer: synchronized source code this part can, 👂 not down. Can you tell me about other Java locks besides synchronized?

Angela: ReentrantLock can also be used for locking.

Interviewer: Then write a piece of code to achieve the same effect as before adding economy.

Angela: coding as shown in 👇 : The interviewerCan you tell me about the underlying implementation of ReentrantLock?

Angela: It’s getting late. Can we talk another time?

Interviewer: Go home and wait for the announcement.

Angela: [heart is broken], it seems that the interview is yellow, 😔, heart tired.

Unfinished, the next article introduces the underlying principles of ReentrantLock, see Angela how to fight Zhong Kui interviewers 300 rounds.

The resources

[1]

A HashMap with the interviewer pull for half an hour: https://blog.csdn.net/zhengwangzw/article/details/104889549


[2]

1.8 biasedLocking Hotspot. CPP: https://github.com/sourcemirror/jdk-8-hotspot/blob/master/src/share/vm/runtime/biasedLocking.cpp