The introduction
Hello, everyone, I am South orange, from contact with Java to now also have almost two years, two years, from a Java have several data structures do not understand super small white, to now understand a little bit of advanced small white, learned a lot of things. The more knowledge is shared, the more valuable, I this period of time summary (including from other big guy over there to learn, quote) some of the focus in the ordinary study and interview (self think), hope to bring some help to everyone
Here are some of the previous articles, if you are interested, you can read them.
- Some overlooked points in the index
- Redis basic knowledge of two articles to meet (1)
- Redis basic knowledge to meet two (2)
Students in need can add my public account, the latest articles in the future are in the first time, you can also ask me for mind map
In Java, we can contact a variety of locks, and each lock because of its different characteristics, in different scenarios have different effects, this article, is to learn the knowledge points, principles and use of these locks with you.
This article is a lot of content to learn from the inevitable Java “lock” things, but also it is to read a lot of meituan technical team articles, to make their own technology more proficient
The first thing I want to do is to post the mind map to you, because I use the free version, so there is a watermark. If you need the original version, you can add my wechat:
The first thing I want to do is to post the mind map to you, because it is a free version, so there is a watermark. If you need the original version, you can add my wechat, and remember to note that it is the students who study together
One, optimistic lock VS pessimistic lock
Pessimistic lock and optimistic lock are probably the two kinds of locks that you hear most, the distinction of these two kinds of locks is more on the mind.
For an operation, a pessimistic lock assumes that another thread must modify the data during the operation, so the lock must be added. Optimistic locks do not think that other threads will disturb them, so they do not need to be locked.
In Java, both the synchronized keyword and the Lock implementation classes are pessimistic locks, whereas optimistic locks are generally implemented using lockless programming, the CAS algorithm.
Let’s start with pessimistic locks
1. Pessimistic lock
- The thread attempts to acquire the lock
- 2. Threads successfully lock and execute, other threads wait, and threads fail to lock and wait to acquire the lock (there are several ways that, in synchronized, can change in one of four states, which I’ll cover in the next section).
- 3. The thread releases the lock after execution, and other threads acquire the lock
Based on the pictures and text, we can see that pessimistic lock is suitable for scenarios with many write operations. The pessimistic lock can ensure data security, but may affect some operation efficiency.
2. Optimistic locking
These two images are from the big man’s article: The Inevitable Java “Lock” thing – Meituan Technical Team
Optimistic locking process:
- 1, the thread directly obtains the synchronization resource data
- 2. Determine whether the synchronized data in memory has been modified by other threads
- 3. If it is not modified, update it directly
- 4, if it is fixed by another thread, select error or retry (spin)
Unlike pessimistic locks, optimistic locks are obviously not suitable for frequent modification because there is no guarantee that data security issues will not occur, so optimistic locks are suitable for read scenarios. For read operations, locking only affects efficiency.
As mentioned above, optimistic locking is generally implemented by the CAS algorithm, so what is the CAS algorithm
3. CAS algorithm
And from that phrase alone, we Get to the heart of the CAS algorithm.
I feel that I have finished my talk. Just like when I met a rookie, the interviewer’s brother asked me: “What is the difference between TCP and UDP?” I unconsciously said, one is simplex communication, one is duplex communication. I paused to continue, when the interviewer cut me off with a stern, “Okay.”
The CAS algorithm involves three operands: memory location (V), expected original value (A), and new value (B).
If the value of the memory location matches the expected original value, the processor automatically updates the location value to the new value. Otherwise, the processor does nothing. In either case, it returns the value for that position before the CAS directive.
Put another way, CAS atomically updates the value of V with the new value B if and only if the value of V is equal to A (” compare + update “is an atomic operation as A whole), otherwise nothing is done.
The addition of java.util.concurrent(J.U.C) to JDK1.5 implements optimistic locking by implementing CAS. Let’s take a look at the main point:
Is it complicated? It’s not complicated at all. We can think of it this way: the CPU tries to update a value, but if it tries to change the value from the original value, the operation fails (because some other operation changed the value first), and then it tries again. If the value you want to change is the same as the original, change it.
However, CAS also has some problems
- ABA problem
One thread, X1, retrives A from memory location V, and another thread, Y1, retrives A from memory, and Y1 does something to turn it into B, and Y1 retrives A from memory location V, and then it retrives A from memory location V, and then it retrives A from memory location V, and then it retrives A from memory location V, and then it retrives A from memory location V, and then it retrives A from memory location V. Although the CAS operation of thread X1 succeeds, it does not mean that the process is problem-free.
The solution: The JDK has provided an AtomicStampedReference class since 1.5 to solve ABA problems. The operation is encapsulated in compareAndSet(), which uses JNI to check whether the current reference equals the expected reference and whether the current flag equals the expected flag. If all are equal, The reference and the value of the flag are set atomically to the given update value.
- Long cycle time and high overhead
If the CAS operation is not successful for a long time, the CAS operation will keep spinning, which brings a large overhead to the CPU.
- Atomic operations that guarantee only one shared variable
Since 1.5, the JDK has provided an AtomicReference class to ensure atomicity between reference objects, allowing multiple variables to be placed in a single object for CAS operations.
Thread safety in Java is a critical issue, and to ensure thread safety, you need both optimistic and pessimistic locks. Pessimistic locks are exclusive, blocking locks. An optimistic lock is a non-exclusive and non-blocking lock. Select what kind of lock in what situation, is the problem we developers need to think about.
Spin locks VS non-spin locks
We mentioned earlier that if the CAS operation is not successful for a long time, it can cause it to spin all the time, which is a waste of performance. But spin is very useful.
Spinlock: When a thread is acquiring a lock, if the lock has been acquired by another thread, then the thread will wait in a loop, and then constantly judge whether the lock can be successfully acquired, until the lock will exit the loop.
Spin locks do not abandon the CUP time slice, but instead wait for the lock release by spin.
Why do you spin? The thread that acquired the lock is still active, but is not performing any valid tasks.
Because in our program, if there is a large number of mutex synchronization code, when high concurrency occurs, the system kernel mode needs to constantly suspend and resume threads, frequent context switch will have a certain impact on the concurrency performance of our system. The amount of time it takes to lock up “shared resources” during the execution of an application is very short. Suspending and restoring threads for that amount of time may take much longer, and it’s penny wise and pound foolish.
Borrow a picture from the big guy again:
Spin-waiting avoids the overhead of thread switching, but it consumes processor time. If the lock is occupied for a short period of time, the spin-wait works very well. On the other hand, if the lock is held for a long time, the spinning thread is a waste of processor resources
This is where adaptive spin locking comes in.
Spinlocks were introduced in JDK1.4.2 and are opened with -xx :+UseSpinning. It became the default in JDK 6, and adaptive spinlocking (adaptive spinlocking) was introduced.Copy the codeAdaptive spin lock
The advent of adaptive spinlocks makes spin operations smarter than they used to be. The term “adaptive” means that for the same lock object, the spin time of a thread is determined based on the spin time and state of the previous thread that held the lock. For example, in the case of A lock object, if A thread has just acquired the lock by spinning, and that thread is running, the JVM will assume that the spin operation has A good chance of obtaining the lock, so it will allow the spin to take longer. But the JVM may even ignore spin operations directly if they are rarely successful for B locking objects.
Therefore, adaptive spin lock can strengthen the performance of spin lock to some extent.
However, with multiple threads competing for lock resources at the same time, we can’t always spin! So the Java team evolved again.
No lock VS biased lock VS lightweight lock VS heavyweight lock
Before we learn about these four locks, let’s look at the concepts of Java object headers and Monitor.
Synchronized is a pessimistic lock that is stored in the Java object header, while Hotspot’s header consists of two parts: Mark Word (tag field) and Klass Pointer (type).
- Mark Word: By default stores an object’s HashCode, generational age, and lock flag bit information.
- Klass Point: A pointer that an object points to its class metadata, which the VM uses to determine which class the object is an instance of.
Every Java object has an invisible lock, called an internal or Monitor lock.
Monitor is a thread private data structure. Each thread has a list of available Monitor records, as well as a global list of available records. Each locked object is associated with a Monitor, and the Owner field in Monitor holds the unique identifier of the thread that owns the lock. Indicates that the lock is occupied by this thread.
Synchronized implements thread synchronization through Monitor, which relies on the underlying operating system’s Mutex Lock for thread synchronization
To understand these concepts, we can look at one through two codes:
Each object has a monitor lock. When the monitor is occupied, it is locked, and the thread attempts to acquire ownership of the monitor by executing the Monitorenter instruction as follows:
- 1. If the entry count of Monitor is 0, then this thread enters monitor and sets the entry count to 1. This thread is the owner of Monitor.
- 2. If a thread already owns the monitor and only re-enters, the number of entries into the monitor is increased by one.
- 3. If another thread has occupied the monitor, the thread blocks until the number of monitor entries reaches zero, and then attempts to acquire the monitor ownership again
The thread executing monitorexit must be the owner of the monitor to which objectref corresponds:
- 1. When the instruction is executed, the number of monitor entries is reduced by 1
- If the number of entries is 0, the thread exits the monitor and is no longer the owner of the monitor
- Other threads blocked by the monitor can attempt to acquire ownership of the monitor
So these two diagrams give you a sense of what we were talking about.
We know that the high concurrency situation, constantly fighting for the lock, the system kernel mode needs to constantly suspend and resume threads, frequent context switch will have a certain impact on the concurrency performance of our system. If synchronizing the contents of a block of code is too simple, the state transition may take longer than the user code executes. This is how synchronized originally implemented synchronization, and this is why synchronized was inefficient prior to JDK 6. These types of locks that rely on the operating system Mutex Lock are called “heavy” locks, and JDK6 introduced “biased locking” and “lightweight locking” to reduce the performance cost of acquiring and releasing locks.
So currently there are four lock states, from low to high level are: no lock, biased lock, lightweight lock and heavyweight lock. The lock status can be upgraded but not degraded.
This is for the four lock states:
| The lock state | Store content | Mark Word |
|---|---|---|
| unlocked | Object hashCode, object generational age, bias lock (0) | 01 |
| Biased locking | Biased thread ID, biased timestamp, object generation age, whether biased lock (1) | 01 |
| Lightweight lock | A pointer to a lock record on the stack | 00 |
| Heavyweight lock | A pointer to a mutex (heavyweight lock) | 10 |
1, no lock
The lockless feature is that the modification takes place in a loop, and the thread keeps trying to modify the shared resource.
If multiple threads modify the same value, one thread can modify the value successfully, while other threads that fail to modify the value will retry until the modification succeeds. The principle and application of CAS is the implementation without locks.
2, bias lock
Biased locking is when a synchronized piece of code is accessed by a thread all the time, so that thread automatically acquies the lock, reducing the cost of acquiring the lock.
A biased lock is only released by a thread holding a biased lock if another thread tries to compete for it. A thread does not actively release a biased lock. When a biased lock is revoked, it waits for a global safe point (at which point no bytecode is executing) and first suspends the thread that owns the biased lock to determine whether the lock object is locked. Undo bias lock to revert to a lockless (” 01 “flag bit) or lightweight (” 00″ flag bit) state.
3. Lightweight locks
When a biased lock is accessed by another thread, the biased lock is upgraded to a lightweight lock, and other threads spin to try to acquire the lock without blocking, thus improving performance.
When the code enters the synchronization block, if the synchronization object Lock state is unlocked (the Lock flag bit is “01” and the bias Lock is “0”), the VIRTUAL machine will first create a space named Lock Record in the stack frame of the current thread, which is used to store the copy of the Lock object’s current Mark Word. Then copy the Mark Word in the object header to the lock record.
After the copy is successful, the VM will use CAS operation to update the Mark Word of the object to the pointer pointing to the Lock Record, and the owner pointer in the Lock Record points to the Mark Word of the object.
If the update action is successful, then the thread owns the lock of the object, and the lock bit of the object Mark Word is set to “00”, indicating that the object is in lightweight locked state.
If the update of the lightweight lock fails, the VM first checks whether the object’s Mark Word is pointing to the stack frame of the current thread. If it is, the current thread already owns the lock and can continue to execute directly into the synchronization block. Otherwise, multiple threads are competing for the lock.
If there is currently only one waiting thread, it waits by spinning. However, when the spin exceeds a certain number of times, or when one thread is holding the lock, one is spinning, and a third is visiting, a lightweight lock becomes a heavyweight lock.
4. Heavyweight locks
When you upgrade to a heavyweight lock, the status value of the lock flag changes to “10”, and the Mark Word stores a pointer to the heavyweight lock. In this case, all threads waiting for the lock will be blocked.
Four, fair lock VS non fair lock
1. Fair lock
A fair lock means that multiple threads acquire a lock in the order in which they apply for the lock. The threads are queued directly and the first thread in the queue can acquire the lock.
The advantages of fair locking are: the thread waiting for the lock will not starve to death, everyone has food to eat, everyone has a book to read
The disadvantages of fair locking are: the overall throughput efficiency is lower than that of unfair locking, and all threads except the first thread in the waiting queue will block. The overhead of CPU to wake up blocked threads is larger than that of unfair locking
2. Non-fair lock
An unfair lock is one in which multiple threads attempt to acquire the lock directly. If the thread fails to acquire the lock, the thread waits at the end of the queue. If the lock happens to be available at the moment, the thread can jump the queue and acquire the lock without blocking.
The advantages of unfair locking are that the overhead of arousing threads is reduced and the overall throughput is high because the thread has the chance to acquire the lock without blocking and the CPU does not have to wake up all threads
The downside of unfair locking is that threads in the waiting queue may starve to death or wait too long to acquire the lock
We can take a look at the application of fair locking and non-fair locking in Java through some source code.
3, seeFair lock FairSyncandNon-fair lock NonfairSync(see source 1/10000)
| Fair lock FairSync | Non-fair lock NonfairSync |
|---|---|
 |
 |
Let’s use the software to compare:
Is that clear? There is only one difference between a fair lock and an unfair lock
Read the comment: Whether to return true depends on whether the header was initialized before the tail and whether the header is accurate (if the current thread is in the queue)
This method determines whether the current thread is first in the synchronization queue. Return true if yes, false otherwise
As a result, fair locks acquire locks sequentially through a synchronous queue, while non-fair locks directly attempt to acquire locks without considering the order of the lock, so there is a situation in which the lock is acquired first after the application.
Reentrant locks VS non-reentrant locks
The concept of a reentrant lock is also easy to understand. When the outer method of the same thread acquired the lock, the inner method of the same thread can automatically acquire the lock (provided that the lock object is the same or the same class). If the lock is not automatically acquired, the lock is non-reentrant.
In JAVA, the most familiar examples of ReentrantLock and synchronized are both reentrant locks.
Why do reentrant locks automatically acquire locks?
Let’s still look at the source code ~!! (Source code is really good 2/10000)
| ReentrantLock | NonReentrantLock |
|---|---|
 |
|
 |
Are these two pictures obvious?
As can be seen from the figure, when the thread tries to acquire the lock, the reentrational lock first tries to acquire and update the status value. If status == 0 means that no other thread is executing the synchronization code, then the status is set to 1 and the current thread starts to execute. If the status! = 0, then determine whether the current thread acquired the lock, if so, perform status+1, and the current thread can acquire the lock again. Instead of a reentrant lock, it simply gets and tries to update the value of the current status if status! If = 0, the thread fails to acquire the lock and the current thread blocks.
When the lock is released, the reentrant lock also obtains the current status value first, provided that the current thread is the one holding the lock. If status-1 == 0, it indicates that all repeated lock acquisition operations of the current thread have been completed, and then the thread will release the lock. Non-reentrant locks release the lock by setting status to 0 after determining that the current thread is the one holding the lock.
Exclusive locks VS shared locks
The concept of exclusive and shared locks can be likened to read/write locks.
For example, if thread A acquires A lock on the data ZZZ, and no other thread can lock ZZZ of any kind or read or write to it, then the lock on ZZZ is exclusive.
If thread A acquires A lock on ZZZ, then other threads can add A shared lock to ZZZ. The thread that acquires the shared lock can read the data, but cannot modify the data.
We can look at the read-write lock ReentrantReadWriteLock
There are two locks inside the read/WriteLock, one is ReadLock, one is WriteLock, now we don’t know what the inside is like, so I choose to see the source (source is really great! 3/10000)
| ReadLock | WriteLock |
|---|---|
 |
|
 |
We were surprised to find an old acquaintance, State, whom we saw all the time.
In exclusive locks the value of state is usually 0 or 1 (the number of reentrants in the case of reentrants), and in shared locks the value of state is the number of held locks. However, ReentrantReadWriteLock has both read locks and write locks. Therefore, an integer variable state is required to describe the number of read locks and write locks (or state), respectively. Therefore, the state variable is divided into two parts: the higher 16 bits indicates the read lock state (number of read locks), and the lower 16 bits indicates the write lock state (number of write locks). And borrow pictures of the big guy
conclusion
This chapter on Java locks is finally over……. Because the weekend did not have a holiday (overtime), basically the rest of the time used up, a little tired, but pretty excited after writing, after all, and share new things!
Well, that’s all for today, see you!
At the same time, if you need a mind map, you can contact me, after all, the more knowledge is shared, the more fragrant!
