Synchronized is the king's harem manager, and thread is the queen

If synchronized is the "chief steward" around the "king", then Thread is like the princess in his harem. The "king" can only choose one princess to accompany him every day, and the princesses will try every means to compete for the right to accompany him. The chief steward needs to use certain means to let the king "flip" a "princess" to accompany the king.

In the article JMM's Analysis of Volatile and Synchronized Principles, the deep relationship between memory model and concurrent implementation principle is explained. Today, listen to "Code Brother"'s nonsense to unravel how the synchronized general manager dispatches the "Princess" to accompany the "King". What exactly does the princess experience in different state changes? Let's see what means the synchronized general manager has taken to "flip" a princess more efficiently. There are still 30 seconds to reach the battlefield in the palace fight!!!

• The 6 states of a princess
• How to improve the efficiency of synchronized management
  • Adaptive Spin
  • Lock Elimination
  • Lock coarsening
  • Bias lock/lightweight lock/heavyweight lock

"Code Byte" tells several stories to help readers fully understand the principles of synchronized lock optimization (biased lock -> lightweight lock -> heavyweight lock) and the mystery of thread conversion between 6 states.

Three concepts are abstracted: Thread corresponds to the beautiful "Princess" in the harem, synchronized is the chief steward of the harem who is responsible for arranging and scheduling the princess, and "King" is the resource that the princesses want to compete for.

The 6 states of a princess

The beauties in the harem are strictly classified. In this game of power, each princess' goal is to gain the favor of the "king", and their own status in the game also changes accordingly.

Just like the process of a living thing from birth to growth and eventual death, the "Princess" also has its own life cycle. There are a total of 6 states in the Princess' life cycle.

• New: Thread state for a thread which has not yet started.
• Runnable is runnable and ready: (feeling comfortable and ready). The Runnable state in Java corresponds to two states in the operating system thread state, namely Running and Ready. That is to say, a thread in the Runnable state in Java may be executing or may not be executing and is waiting for CPU resources to be allocated.
• Blocked (poor health, banished to the cold palace)
• WAITING: (Waiting to be called)
• Timed Waiting: Waiting outside the door for a certain period of time
• Terminated: burp

Thread Status

The princess can only be in one of the states at any time, and the thread state is obtained through the getState() method.

New

Day 1

The king went on a secret visit and drove to Taohuayuan. He saw the pleasant scenery, like a fairyland on earth. He stopped the car and sat to enjoy the maple forest in the evening, the frosted leaves were redder than the flowers in February. At this moment, a woman's charming eyes closed shyly, and her red lips smiled. The wind rolled up the grape belt, and the sun shone on the pomegranate skirt. She walked past the king and encountered a villain. The king picked up the nunchaku and hummed and haha, and he subdued the villain by flying over the eaves and walls, and the beauty was in his arms. The Fragrant Concubine entered the palace for the first time.

The "king" drafted an imperial edict to recruit her into the palace, which contained new Thread(), and the title of "Fragrant Concubine" was officially established. New means that the thread has been created but has not yet been started, just like the "Fragrant Concubine" has just entered the palace, and the journey waiting for her will be thrilling and heart-wrenching.

At this moment, the "Queen" (which can be understood as the JVM) orders Eunuch Zhao to allocate a bedroom for the "Fragrant Concubine" (that is, allocate memory) and initialize the "maid" around her (initialize the value of the member variable).

Runnable Runnable, ready

After receiving the edict from the king and arranging her food, clothing, housing and transportation, the "Fragrant Concubine" was ready to accompany the king. However, there were many beauties in the harem, and not all of them could be accompanied. The "Fragrant Concubine" was already ready and was also striving for the opportunity to dance with the "king". She took the initiative to tell Eunuch Zhao that she was proficient in everything from music, chess, calligraphy and painting. She hoped to be arranged, so she was dispatched by Eunuch Zhao. The "Queen" arranged for the maid to bathe and change clothes for the "Fragrant Concubine", put on rouge and wait for the call (equivalent to the start() method of the thread being called). (The Java virtual machine will create a method call stack programmable counter for it, and wait for the dispatch to run) At this moment, the thread is in a runnable state.

The Runnable state in Java corresponds to two states in the operating system thread state, namely Running and Ready. That is to say, a thread in the Runnable state in Java may be executing or may not be executing and is waiting for CPU resources to be allocated.

If a running thread is in the Runnable state, when it runs halfway through the task, the CPU executing the thread is scheduled to do other things, causing the thread to temporarily stop running. Its state remains unchanged and is still Runnable, because it may be scheduled back at any time to continue executing the task.

Note: To start a thread, use the start() method instead of the run() method. When you call the start() method to start a thread, the system will treat the run method as a method execution body. It is important to remember that after calling the run() method of a thread, the thread is no longer in the newly created state. Do not call the start() method again. You can only call the start() method on a newly created thread, otherwise an IllegaIThreadStateExccption exception will be triggered.

After the "Fragrant Concubine" bathed and changed her clothes (start() was called), she burned incense and played the zither. The "Shu Concubine" did not show weakness and danced to compete for the right to accompany her. After all, the "Fragrant Concubine" was new, and the "King" who loved the new and hated the old loved her very much. The "Fragrant Concubine" won the right to accompany her tonight. After the "Queen" gave her CPU slices, she executed the run() method. The core function of this method is to make a baby...

Before having a baby, the "Fragrant Concubine" went through a lot of disputes and her status was constantly changing. If you are not careful, you may enter the TERMINATED state and be done with it. Please continue reading...

Waiting, Timed Waiting, Blocked

The previously favored "Shu Fei" lost to the new "Xiang Fei". When entering the palace, preparing to make a baby, the king had important matters to deal with, so he used the Object.wait() skill card, and "Xiang Fei" could only wait for the king to come back...

In order to unlock the Object.wait() skill that he had previously released on "Xiang Fei", Wang Guilai released Object.notify() to unlock the card and notify "Xiang Fei" that they can kiss each other together. At this moment, "Xiang Fei" actually had incontinence and triggered Thread.join(), so she had to go to the toilet, asking Lao Wang to wait for a moment.

Although "Shufei" was already in the Runnable state that night, the steward used the LockSupport.park() skill card, which prevented her from entering the palace, and her state changed from Runnable to Waiting. No chance for Lao Wang tonight!!!

Because "Ka Fei" was too dark, it was directly rejected by the synchronized manager and changed from Runnable to Blocked.

There are other "concubines" who were stood up by the old king. He told them to meet after 3 o'clock. I am dissatisfied with this time management. They were hit by the following skill cards and entered the TIMED_WAITING state directly:

• Thread.sleep:
• Object.wait with timeout
• Thread.join with timeout
• LockSupport.parkNanos
• LockSupport.parkUntil

Day 2

Let's get back to the topic. Yesterday, Xiang Fei's incontinence triggered Thread.join(). After going to the toilet, she had sex with Wang, and finally the day broke.

The "Shu Fei" who was rejected by the synchronized chief steward and changed from Runnable to Blocked was favored by the old king the next day. Because the "Xiang Fei" was incontinent at the critical moment, she wanted to find the "Shu Fei" who was almost turned over yesterday. So today, the "Shu Fei" got the monitor lock left by the old king for her, and got the permission of the synchronized chief steward, and changed from yesterday's Blocked to Runnable...

In addition, some princesses wanted to gain the right to accompany or to take charge of the harem. Their conspiracy was discovered and they were sentenced to the Terminated penalty, which was a disaster.

How to improve the efficiency of synchronized management

In addition to using LockSupport.unpark() and other methods to obtain the right to accompany the king, the princesses can also obtain the right to accompany the king through synchronized flipping of cards appointed by the king. Faced with three thousand beauties, the chief steward must improve his efficiency, otherwise he will be exhausted and unable to select a princess to accompany the king, which is punishable by death.

Because before Java 5, the synchronized filtering method was very inefficient, and a bunch of princesses came in and argued that they would do it all, and the order was chaotic, just like the OFO deposit refunding scene, where the previous chief steward was beheaded...

After the 6th term, great improvements were made, including the use of adaptive spin, lock elimination, lock coarsening, lightweight lock, and biased lock, which greatly improved efficiency.

Adaptive Spin

Notifying the princesses to line up or calling a new princess requires the operating system to switch CPUs, which is time-consuming.

In order to let the concubine who is currently applying for companionship "wait a moment", the synchronized chief steward will let the princess spin, because the king and Dorgon are dealing with military secrets and will be back soon. The concubine only needs to ask the chief steward whether the king has returned every once in a while. Once the king has returned, she does not need to enter the blocking state and get to accompany the king today. Avoid the time and effort of notifying multiple princesses to compete.

To sum up the benefits of spin locks in one sentence, spin locks use loops to continuously try to acquire locks, keeping the thread in the Runnable state, saving the overhead of thread state switching.

The following is the process of acquiring a lock using spin and non-spin:

Spin and No Spin

AtomicInteger

In the concurrent package of Java 1.5 and above, that is, the java.util.concurrent package, the atomic classes in it are basically implementations of spin locks. Let's look at the definition of the AtomicInteger class:

 public class AtomicInteger extends Number implements java.io. Serializable {
    private static final long serialVersionUID = 6214790243416807050L; 
 
    // setup to use Unsafe.compareAndSwapInt for updates
    private static final Unsafe unsafe = Unsafe.getUnsafe();
    private static final long valueOffset; 
 
 static {
 try {
            valueOffset = unsafe.objectFieldOffset
                (AtomicInteger.class.getDeclaredField( "value" ));
        } catch (Exception ex) { throw new Error(ex); }
 } 
 
    private volatile int value; 
     
 ......
 }

The function of each attribute:

• Unsafe: Get and manipulate memory data.
• valueOffset: stores the offset of value in AtomicInteger.
• value: stores the int value of AtomicInteger. This attribute needs the volatile keyword to ensure that it is visible between threads.

When viewing the source code of AtomicInteger's increment function incrementAndGet(), the underlying function calls unsafe.getAndAddInt().

However, since JDK itself only has Unsafe.class, we cannot fully understand the function of the method by only looking at the parameter name in the class file. We use OpenJDK 8 to view the source code of Unsafe:

 // JDK AtomicInteger auto-increment
 public final int getAndIncrement() {
 return unsafe.getAndAddInt(this, valueOffset, 1);
 } 
 
 // OpenJDK 8
 // Unsafe.java
 public final int getAndAddInt(Object o, long offset, int delta) {
 int v;
 do {
       v = getIntVolatile(o, offset);
   } while (!compareAndSwapInt(o, offset, v, v + delta));
 return v;
 }

Spinning is implemented by do while. The getAndAddInt() loop obtains the value v at the offset in the given object o, and then determines whether the memory value is equal to v. If they are equal, the memory value is set to v + delta, otherwise false is returned, and the loop continues to retry until the setting is successful to exit the loop and return the old value.

The entire "compare + update" operation is encapsulated in compareAndSwapInt(), which is completed in JNI with the help of a CPU instruction. It is an atomic operation that ensures that multiple threads can see the modified value of the same variable.

In version 1.6, synchronized came up with an adaptive spin lock to solve the problem of long-term spinning, preventing people from waiting and asking stupidly. It will be based on the success rate and failure rate of the recent spin.

If the most recent attempt to spin acquire a lock was successful, then the next time you may continue to use spin and allow it to spin for a longer time; but if the most recent spin acquisition of a lock failed, then the spin process may be omitted in order to reduce useless spins and improve efficiency.

Lock Elimination

Concubine Shu was cunning. On a dark and windy night in 107 AD, she colluded with Xiao Zhezi in the kitchen and put a colorless and odorless drug in the pot, making everyone weak.

So I was the only one left to apply to the synchronized manager, so I didn't need to go through the tedious process and went straight to the point. I met Lao Wang directly without locking.

Lock elimination means deleting unnecessary locking operations. When the virtual machine real-time editor is running, it eliminates some locks that "require synchronization in the code, but it is detected that there is no possibility of shared data competition".

According to the code escape technology, if it is determined that the data on the heap will not escape the current thread in a section of code, then this section of code can be considered thread-safe and there is no need to lock it.

 public class SynchronizedTest { 
 
 public   static void main(String[] args) {
        SynchronizedTest test = new SynchronizedTest(); 
 
 for ( int i = 0; i < 100000000; i++) {
 test.append( "codebytes" , "def" );
 }
 } 
 
 public void append(String str1, String str2) {
        StringBuffer sb = new StringBuffer();
        sb.append(str1).append(str2);
 }
 }

Although StringBuffer's append is a synchronized method, the StringBuffer in this program is a local variable and will not escape from this method (that is, the reference of StringBuffer sb is not passed outside this method and cannot be obtained by other threads), so this process is actually thread-safe and the lock can be eliminated.

Lock coarsening

Zhen Huan is deeply favored by the old king, and those who are favored are fearless. Every time you enter and exit the synchronized general manager to hang your door, you need to verify whether the monitor lock is obtained. After Zhen Huan comes in, she likes to go out for a walk, come in to see the old king for a few seconds, and then go out again. The general manager does not need to verify every time, so the scope of the restriction is expanded to prevent repeated verification.

If a series of consecutive operations repeatedly lock and unlock the same object, and even the locking operation occurs in a loop, then even if there is no thread contention, frequent mutual exclusion synchronization operations will cause unnecessary performance loss.

If the virtual machine detects that a series of fragmented operations are all locking the same object, it will expand (coarsen) the scope of lock synchronization to outside the entire operation sequence.

 public class StringBufferTest {
    StringBuffer stringBuffer = new StringBuffer(); 
 
 public void append(){
 stringBuffer.append( "Follow" );
 stringBuffer.append( "public account" );
 stringBuffer.append( "code byte" );
 }
 }

Each call to the stringBuffer.append method requires locking and unlocking. If the virtual machine detects a series of locking and unlocking operations on the same object, it will merge them into a larger locking and unlocking operation, that is, locking at the first append method and unlocking after the last append method.

Bias lock/lightweight lock/heavyweight lock

The synchronized principle has been explained in detail in the article Analyzing Volatility and Synchronized Principles from JMM. This article mainly explains the optimization methods for JVM with low synchronized performance.

Bias lock

The old king favors Zhen Huan, so the synchronized chief steward stores the thread ID of the lock preference in a cabinet called Mark Word, which records Zhen Huan's ID. There is no need to perform a tedious card-flipping process. It only needs to determine whether the ID of the princess applied for is consistent with the ID recorded in the cabinet.

Because the king favors Zhen Huan, he likes to turn over Zhen Huan's cards every time.

When a thread accesses a synchronized code block and acquires a lock, the thread ID of the lock bias is stored in the Mark Word. When a thread enters and exits a synchronized block, it no longer uses CAS operations to lock and unlock, but instead checks whether the Mark Word stores a bias lock pointing to the current thread.

The purpose of introducing biased locks is to minimize unnecessary lightweight lock execution paths in the absence of multi-threaded competition, because the acquisition and release of lightweight locks rely on multiple CAS atomic instructions, while biased locks only need to rely on one CAS atomic instruction when replacing the ThreadID.

The biased lock will only be released by the thread holding the biased lock when other threads try to compete for the biased lock. The thread will not actively release the biased lock. To cancel the biased lock, you need to wait for the global security point (at this point in time when no bytecode is being executed). It will first suspend the thread holding the biased lock to determine whether the lock object is in a locked state. After canceling the biased lock, it will be restored to the unlocked (flag bit is "01") or lightweight lock (flag bit is "00") state.

Biased locking is enabled by default in JDK 6 and later JVMs. You can disable biased locking by setting the JVM parameter -XX:-UseBiasedLocking=false. After this is disabled, the program will enter the lightweight locking state by default.

Lightweight lock

It means that when the lock is a biased lock and is accessed by another thread, the biased lock will be upgraded to a lightweight lock, and other threads will try to acquire the lock by spinning without blocking, thereby improving performance.

When the code enters the synchronization block, if the synchronization object lock state is unlocked (the lock flag is "01", and whether it is biased lock is "0"), the virtual machine will first create a space called Lock Record in the stack frame of the current thread to store a copy of the current Mark Word of the lock object, which is officially called Displaced Mark Word. At this time, the status of the thread stack and the object header is as shown in the figure below.

Lightweight lock

Copy the Mark Word in the Object header to the LockRecord.

After the copy is successful, the virtual machine will use the CAS operation to try to update the object's Mark Word to a pointer to the Lock Record, and point the owner pointer in the Lock record to the object mark word. If the update is successful, go to step 4.

If the update is successful, the thread owns the lock of the object, and the lock flag of the object Mark Word is set to "00", which means that the object is in a lightweight locked state. At this time, the status of the thread stack and the object header are as shown in the following figure.

If this update operation fails, the virtual machine will first check whether the object's Mark Word points to the stack frame of the current thread. If so, it means that the current thread already has the lock of this object, and it can directly enter the synchronization block to continue execution. Otherwise, it means that multiple threads are competing for the lock. If there is only one waiting thread, you can wait a little by spinning, and another thread may release the lock soon. However, when the spin exceeds a certain number of times, or one thread is holding the lock, one is spinning, and a third thread visits, the lightweight lock expands to a heavyweight lock. The heavyweight lock blocks all threads except the thread that owns the lock to prevent the CPU from idling. The status value of the lock flag becomes "10", and the Mark Word stores a pointer to the heavyweight lock (mutex). The subsequent threads waiting for the lock will also enter a blocked state.

Heavyweight lock

As shown in step (5) of the locking process of the lightweight lock, the lightweight lock is suitable for the scenario where threads almost alternately execute synchronized blocks. If there is a situation where the same lock is accessed at the same time, the lightweight lock will expand to a heavyweight lock. The lock mark bit of Mark Word is updated to 10, and Mark Word points to the mutex (heavyweight lock)

The heavyweight lock of Synchronized is implemented through a monitor lock inside the object, which is essentially implemented by the Mutex Lock of the underlying operating system. The operating system needs to switch from user state to kernel state to switch between threads, which is very costly and takes a relatively long time to switch between states. This is why Synchronized is inefficient.

Lock upgrade path

From lock-free to biased lock, to lightweight lock, and finally to heavyweight lock. Combining the knowledge we have discussed before, biased lock has the best performance and avoids CAS operation. Lightweight lock uses spin and CAS to avoid thread blocking and wakeup caused by heavyweight lock, and has medium performance. Heavyweight lock will block the thread that cannot obtain the lock, and has the worst performance.

Lock escalation

In summary, biased locks solve the locking problem by comparing Mark Words and avoiding CAS operations. Lightweight locks solve the locking problem by using CAS operations and spins to avoid thread blocking and wakeup that affects performance. Heavyweight locks block all threads except the thread that owns the lock.

This article is reprinted from the WeChat public account "MaGeByte", which can be followed through the following QR code. To reprint this article, please contact the WeChat public account "MaGeByte".