Java lock classification
There are many locks in Java that can be classified according to different functions and types. Here is my classification of some common locks in Java, including some basic overview
- Whether threads need to lock resources can be divided into
Pessimistic locking和Optimistic locking - From the resource is locked, whether the thread is blocked can be divided into
spinlocks - Concurrent access to resources from multiple threads, known as Synchronized, can be classified as Synchronized
unlocked,Biased locking,Lightweight lock和Heavyweight lock - From the fairness of the lock, can be divided into
Fair lock和Not fair lock - According to whether the lock is repeated acquisition can be divided into
Reentrant lock和No reentrant lock - Can multiple threads get the same lock from that thread
A Shared lock和Exclusive lock
Below we carry on detailed elaboration to each lock classification in turn.
Whether the thread needs to lock the resource
Java according to whether the resource lock is divided into optimistic lock and pessimistic lock, optimistic lock and pessimistic lock is not a real lock, but a design idea, optimistic lock and pessimistic lock for understanding Java multithreading and database is very important, the following will discuss the differences and advantages and disadvantages of the two implementation methods
Pessimistic locking
Pessimistic lock is a kind of negative thinking, it always think the worst may appear, it was assumed that the data could be modified by others, so pessimistic locks in holding data always lock the resources, or data, so that other threads want to request this resource will be blocked, until when pessimistic locks release resources. Traditional relational database inside used a lot of this locking mechanism, ** such as row lock, table lock, read lock, write lock, etc., are in operation before the first lock. The realization of pessimistic locking often depends on the locking function of the database itself.
Exclusive locks such as Synchronized and ReentrantLock in Java are also implementations of the pessimistic locking concept because Synchronzied and ReetrantLock attempt to lock regardless of whether they hold resources. Afraid of their beloved treasure is taken away by others.
Optimistic locking
The idea of optimistic locking is the opposite of the idea of pessimistic locking. It always assumes that resources and data will not be modified by others, so the read will not be locked, but optimistic locking will determine whether the current data has been modified during the write operation (more on how to determine this later). Generally speaking, there are two implementation schemes of optimistic locking: version number mechanism and CAS implementation. Optimistic locking is suitable for multiple application types to improve throughput.
In Java. Java util. Concurrent. Atomic package this atomic variable classes is to use the optimistic locking a way of implementation of CAS.
Two types of lock usage scenarios
The above describes the basic concepts of the two types of locks and describes the application scenarios of the two types of locks. Generally, pessimistic locks will be locked not only for write operations but also for read operations. A typical pessimistic lock call:
select * from student where name="cxuan" for update
Copy the codeSelect * from Student where name = “cXUAN” and lock it. No other write operations will operate on this data until the transaction is committed.
Pessimistic locks because of the read-write lock, so its performance is lower, for now the Internet promotes the three tenors (high performance, high availability, high concurrency), the realization of the pessimistic locks with fewer and fewer, but more commonly read under the condition of still need to use pessimistic locks, because although the performance of the lock is lower, but also block the like optimistic locking, Time to retry in case of inconsistent write.
In contrast, optimistic locking is used for read and write scenarios with few collisions, which can reduce the overhead of locking and increase the throughput of the system.
Optimistic locking the applicable scenario has a lot of, such as cost of typical system, cabinet to a loan modification, in order to guarantee the accuracy of the data and effectiveness, use pessimistic locks lock after a certain data, to meet other need to modify the data of operation, then this operation cannot be completed amount change, be disastrous moment for products, Using the version number mechanism for optimistic locking can solve this problem, as we’ll see below.
The implementation of optimistic locking
Optimistic locking is generally implemented in two ways: version number mechanism and CAS (compare-and-swap) algorithm.
Version number mechanism
The version number mechanism is implemented by adding A version field to the data table, indicating the number of times the data has been modified. When the write operation is performed and the write is successful, version = version + 1. When thread A wants to update data, it will read the version value as well as the data. If the version value read just now is the same as the version value in the current database, the update operation is retried until the update succeeds.
Let’s take the financial system above as an example to sketch this process.
- The cost system has a data table with two fields respectively
The amount of和version, the attribute of the amount can be changed in real time, and version represents the version of the amount that changes each time. The general policy is that when the amount changes, Version adopts the incremental policy of + 1 each time based on the previous version. - After understanding basic situation and basic information, we have a look at this process: after the company receives return money, need to put this money in the Treasury, if there is 100 yuan money in the Treasury
- Let’s start transaction 1: When the male teller performs the writing operation, he will first check (read) how much money is left in the vault. At this time, he reads that there is 100 yuan in the vault, so he can perform the write operation, update the money in the database to 120 yuan, submit the transaction, the money in the vault is 100 -> 120, and the version number is 0 -> 1.
- Open transaction 2: after the female teller receives the salary payment request, she needs to perform the read request first, check how much money is left in the vault, and what is the version number at this time. Then she takes out the salary of the employee from the vault for payment and submits the transaction. After the transaction is successful, the version + 1, and the version at this time is 1 -> 2.
The above two cases are the most optimistic, the above two transactions are executed sequentially, namely transaction 1 and transaction 2 do not interfere with each other, so what if the transaction is executed in parallel?
-
As soon as the transaction is opened, the male teller first performs the read operation, takes out the amount and version number, and performs the write operation
Begin Update table SET Amount = 120,version = version + 1 WHERE amount = 100 and version = 0Copy the codeAt this point the amount is changed to 120, the version number is 1, and the transaction has not yet committed
When transaction 2 is opened, the female teller performs the read operation first, takes out the amount and version number, and performs the write operation
Begin Update the table SET Amount = 50,version = version + 1 WHERE amount = 100 and version = 0Copy the codeAt this point, the amount changes to 50, the version number changes to 1, and the transaction is not committed
Now commit transaction 1, amount changed to 120, version changed to 1, commit transaction. Ideally, it would be amount = 50, version = 2, but in reality, the update for transaction 2 is based on amount 100 and version 0, so transaction 2 will not commit successfully and should read the amount and version number again and write again.
In this way, the possibility of female tellers overwriting the operation results of male operators with the modified results based on the old data version = 0 is avoided.
CAS algorithm
Omit the code, please refer to the complete codeYou should be able to understand the pessimistic lock and optimistic lock
CAS, which stands for Compare and swap, is a well-known lock-free algorithm. The Synchronization of variables between multiple threads without locking is also called non-blocking Synchronization
Java has been supported since JDK1.5. The java.util.Concurrent package provides many classes for concurrent programming, as well as support for CAS algorithms. Some Atomic classes starting with Atomic use CAS as their implementation. Using these classes provides better performance on machines with multi-core cpus.
If you want to make them atomic, you have to lock them, using Synchronzied or ReentrantLock, which we described as an implementation of pessimistic locks, but now we’re talking about optimistic locks, how do you guarantee their atomicity? Keep reading
There are three elements involved in CAS:
- Memory value V that needs to be read or written
- The value A for comparison
- The new value B to be written
Change the memory value V to B if and only if the expected value A and memory value V are the same, otherwise nothing is done.
Using the AtomicInteger in java.util.concurrent as an example, how can thread safety be ensured without locking
public class AtomicCounter {
private AtomicInteger integer = new AtomicInteger();
public AtomicInteger getInteger(a) {
return integer;
}
public void setInteger(AtomicInteger integer) {
this.integer = integer;
}
public void increment(a){
integer.incrementAndGet();
}
public void decrement(a){ integer.decrementAndGet(); }}public class AtomicProducer extends Thread{
private AtomicCounter atomicCounter;
public AtomicProducer(AtomicCounter atomicCounter){
this.atomicCounter = atomicCounter;
}
@Override
public void run(a) {
for(int j = 0; j < AtomicTest.LOOP; j++) {
System.out.println("producer : "+ atomicCounter.getInteger()); atomicCounter.increment(); }}}public class AtomicConsumer extends Thread{
private AtomicCounter atomicCounter;
public AtomicConsumer(AtomicCounter atomicCounter){
this.atomicCounter = atomicCounter;
}
@Override
public void run(a) {
for(int j = 0; j < AtomicTest.LOOP; j++) {
System.out.println("consumer : "+ atomicCounter.getInteger()); atomicCounter.decrement(); }}}public class AtomicTest {
final static int LOOP = 10000;
public static void main(String[] args) throws InterruptedException {
AtomicCounter counter = new AtomicCounter();
AtomicProducer producer = new AtomicProducer(counter);
AtomicConsumer consumer = newAtomicConsumer(counter); producer.start(); consumer.start(); producer.join(); consumer.join(); System.out.println(counter.getInteger()); }}Copy the codeAccording to the test, no matter how many times the loop results in 0, that is, in the case of multiple threads parallel, AtomicInteger can ensure thread safety. IncrementAndGet and decrementAndGet are atomic operations.
Disadvantages of optimistic locking
Everything has advantages and disadvantages, there is no perfect solution in the software industry, only the optimal solution, so optimistic lock also has its weaknesses and defects:
ABA problem
If A variable reads A value of A for the first time and is ready to write to A and the value is still A, can we assume that the value of A has not been changed? This could be the case with A -> B -> A, but AtomicInteger doesn’t think so, it just believes what it sees, and what it sees is what it sees.
The AtomicStampedReference class provides this capability after JDK 1.5, where the compareAndSet method first checks whether the current reference is equal to the expected reference, and whether the current flag is equal to the expected flag. The reference and the flag are set atomically to the given updated value.
DCAS, a variant of CAS, can also be used to solve this problem. DCAS is a reference to the number of changes added to each V. For each V, if the reference is modified once, the counter is incremented by one. Then, when the variable needs to be updated, both the value of the variable and the value of the counter are checked.
High cycle overhead
We know optimistic locking when writing will determine whether to write to success. If you write is not successful would trigger wait – > retry mechanism, this kind of circumstance is a spin lock, in simple terms, is suitable for short term gain is less than to wait for retry lock, lock, it is not suitable for long-term access is less than the other, the spin cycle for the performance overhead is larger.
The use of CAS and synchronized
To put it simply, CAS applies to the case of less writing (read more, less conflict), while synchronized applies to the case of more writing (write more, more conflict).
- In the case of less resource competition (less thread conflict), Synchronized Synchronized lock is used for thread blocking and wake up switching, as well as switching between user-mode kernel states, which consumes additional CPU resources. CAS, on the other hand, is hardware-based, does not need to enter the kernel, does not need to switch threads, and operates with less spin, thus achieving higher performance.
- In the case of serious resource competition (serious thread conflict), CAS has a high probability of spin, which wastes more CPU resources and is less efficient than synchronized.
The resource is locked. Whether the thread is blocked
The background of the proposed spin lock
Due to the limitation of certain resources in a multi-processor environment, mutual exclusion is sometimes required. At this time, the concept of lock should be introduced. Only the thread that has obtained the lock can access the resource. Then there is the question, what should a thread that has not acquired the lock do?
There are usually two processing methods: one is that the thread that has not acquired the lock will loop and wait to determine whether the lock has been released. This kind of lock is called spin-lock, and it does not require BLOCKING the thread. Another way to handle this is to block itself and wait for rescheduling requests, called mutex.
What is a spin lock
Spin lock definition: when a thread attempts to acquire a lock, if the lock has already been acquired by someone else, the thread cannot acquire the lock, and will wait for some time before attempting to acquire the lock again. This mechanism of cyclic locking -> waiting is called spinlock.
The principle of spin locking
Spinlocks principle is simple, if the thread holding the lock can lock is released in a short time resources, and the thread lock wait for competition there is no need to do between kernel mode and user mode switch into the blocking state, they just need to wait for a while (spin), until the thread holding the lock lock is released after available, thus avoiding the user process and the consumption of the kernel switch.
Because they avoid operating system process scheduling and thread switching, spin locks are usually appropriate for short periods of time. For this reason, operating system kernels often use spin locks. However, if locked for long periods of time, spin locks can be very costly in performance, preventing other threads from running and scheduling. The longer a thread holds the lock, the greater the risk that the thread holding the lock will be interrupted by the Operating System (OS) scheduler. If an interrupt occurs, the other threads will remain spinning (repeatedly trying to acquire the lock), and the thread holding the lock does not intend to release it, resulting in an indefinite delay until the thread holding the lock can complete and release it.
A good way to solve this problem is to set a spin time for the spin lock and release the spin lock immediately. The purpose of a spin lock is to hold CPU resources without releasing them until the lock is acquired. But how do you choose spin time? If the spin execution time is too long, a large number of threads in the spin state will occupy CPU resources, which will affect the overall system performance. So the cycle of spin is extra important! The JDK introduced adaptive spin locking in 1.6. Adaptive spin locking means that the spin time is not fixed, but is determined by the previous spin time on the same lock and the state the lock has. It is generally considered that the optimal time for a thread to switch context is the time.
Advantages and disadvantages of spin locks
Spinlocks reduce thread blocking as much as possible, which is a big performance improvement for blocks that are less competitive for locks and have a very short lock time, because the spin cost is less than the cost of blocking, suspending and waking up operations that cause the thread to do two context switches!
But if the lock of the competition is intense, or thread holding the lock need long time to occupy the lock synchronization block, this time is not suitable for using a spin lock, because of the spin lock before acquiring a lock is CPU doing this all the time, for the XX XX, competition at the same time a large number of threads in a lock, and can lead to acquiring a lock for a long time, The cost of thread spin is greater than the cost of thread blocking and suspending operations, and other threads that need CPU cannot obtain CPU, resulting in CPU waste. So in this case we want to turn off the spin lock.
Implementation of spin lock
Let’s use Java code to implement a simple spin lock
public class SpinLockTest {
private AtomicBoolean available = new AtomicBoolean(false);
public void lock(a){
// Cyclic detection attempts to acquire the lock
while(! tryLock()){// doSomething...}}public boolean tryLock(a){
// Try to acquire the lock, return true on success, false on failure
return available.compareAndSet(false.true);
}
public void unLock(a){
if(! available.compareAndSet(true.false)) {throw new RuntimeException("Lock release failed"); }}}Copy the codeOne problem with this simple spin lock is that it does not guarantee fairness in multithreaded competition. For the SpinlockTest above, when multiple threads want to acquire the lock, whoever sets available to false first will acquire the lock first. This may cause some threads to never acquire the lock, causing thread hunger. Just as we rush to the cafeteria after class and rush to the subway after work, we usually solve such problems by queuing. Similarly, we call this kind of lock a QueuedSpinlock. Computer scientists have used various methods to implement queued spinlocks, such as TicketLock, MCSLock, and CLHLock. Next, we will give a general introduction to these locks.
TicketLock
In computer science, TicketLock is a synchronization mechanism or locking algorithm that is a spin lock that uses ticket to control the order in which threads are executed.
Like a ticket queue management system. A bakery or service organization (such as a bank) may use this method to record the order of arrival for each customer who arrives first, rather than waiting in line each time. Usually, this site will have a distributor (cry, register, and so on), the first people need to take out your line now on the machine number, this number is according to the order of increasing, there will be a sign next to display is the sign of is service, this is usually a representative is currently in service queue number, the current number to complete after service, The sign says the next number is available for service.
Like the system above, TicketLock is based on a first-in, first-out (FIFO) queue mechanism. TicketLock has two values of type INT, each starting with 0. The first value is a queue ticket, and the second value is a queue ticket. The queue ticket is the position of the thread in the queue, and the out-queue ticket is the queue position of the ticket that now holds the lock. It might be a little ambiguous, but basically, the queue ticket is where you get your ticket number, and the queue ticket is where you get your ticket number. That should make some sense now.
When the caller calls you, there cannot be the same number to do business at the same time, there must be only one person to do it, when done, the caller calls the next person, this is called atomicity. You can’t be interrupted when you’re doing business, and you can’t have two people with the same number doing business at the same time. Then, the next person checks to see if their number matches the number called. If so, it’s your turn to do the business. Otherwise, you have to wait. The key point of this process is that after each person conducts a transaction, he or she must discard his or her number so that the caller can continue to call the person below. If the person does not discard the number, the other person can only continue to wait. Let’s implement the bill queuing scheme
public class TicketLock {
// Queue ticket (current queue number)
private AtomicInteger queueNum = new AtomicInteger();
// Queue ticket (currently waiting number)
private AtomicInteger dueueNum = new AtomicInteger();
If the lock is obtained successfully, the queue number of the current thread is returned
public int lock(a){
int currentTicketNum = dueueNum.incrementAndGet();
while(currentTicketNum ! = queueNum.get()){// doSomething...
}
return currentTicketNum;
}
// Release the lock: pass in the current queue number
public void unLock(int ticketNum){
queueNum.compareAndSet(ticketNum,ticketNum + 1); }}Copy the codeEach time when calling a number, the dialing machine will determine whether it is the called number. When each person finishes the business, the dialing machine will add + 1 to the current number and let the queue continue to move forward.
However, the above design is problematic, because after obtaining your own number, you can change the number, which causes the system disorder, the lock can not be released in time. Knowing that there needed to be a role that would ensure that everyone would line up at their number, we redesigned the logic
public class TicketLock2 {
// Queue ticket (current queue number)
private AtomicInteger queueNum = new AtomicInteger();
// Queue ticket (currently waiting number)
private AtomicInteger dueueNum = new AtomicInteger();
private ThreadLocal<Integer> ticketLocal = new ThreadLocal<>();
public void lock(a){
int currentTicketNum = dueueNum.incrementAndGet();
// When the lock is acquired, the queue number of the current thread is saved
ticketLocal.set(currentTicketNum);
while(currentTicketNum ! = queueNum.get()){// doSomething...}}// Release the lock from the queue buffer pool
public void unLock(a){
Integer currentTicket = ticketLocal.get();
queueNum.compareAndSet(currentTicket,currentTicket + 1); }}Copy the codeThis time there is no need to return the value, do business, to the current number of the cache up, after the business, need to release the cache of this ticket.
disadvantages
TicketLock solved the fairness problem, but in a multi-processor system, each process/thread occupied by the processor reads and writes to the same variable queueNum. Each read and write operation must be cached synchronization between multiple processor caches, which leads to heavy system bus and memory traffic. Greatly reduces the overall system performance.
To solve this problem, MCSLock and CLHLock were created.
CLHLock
Craig, Landin and Hagersten are the inventors of TicketLock, which is based on a linked list. CLH is an extensible, high-performance, fair spinlock based on linked lists. The application thread can only spin on local variables. It continuously polls the state of the precursor and terminates the spin if it finds that the precursor has released the lock.
public class CLHLock {
public static class CLHNode{
private volatile boolean isLocked = true;
}
// The tail node
private volatile CLHNode tail;
private static final ThreadLocal<CLHNode> LOCAL = new ThreadLocal<>();
private static final AtomicReferenceFieldUpdater<CLHLock,CLHNode> UPDATER =
AtomicReferenceFieldUpdater.newUpdater(CLHLock.class,CLHNode.class,"tail");
public void lock(a){
// Create a new node and store it with the current thread
CLHNode node = new CLHNode();
LOCAL.set(node);
// Set the newly created node as the tail node and return the old node (atomic operation), where the old node is actually the precursor of the current node
CLHNode preNode = UPDATER.getAndSet(this,node);
if(preNode ! =null) {// If the precursor node is not null, it indicates that when the lock is occupied by other threads, it determines the lock flag of the precursor node through continuous polling and waits for the precursor node to release the lock
while (preNode.isLocked){
}
preNode = null;
LOCAL.set(node);
}
// If there is no precursor node, the lock is not occupied by another thread, and the current thread acquires the lock
}
public void unlock(a) {
// Get the node corresponding to the current thread
CLHNode node = LOCAL.get();
// If the tail node is equal to node, update the tail node to null and set the lock status of Node to false, indicating that the current thread released the lock
if(! UPDATER.compareAndSet(this, node, null)) {
node.isLocked = false;
}
node = null; }}Copy the codeMCSLock
MCS Spinlock is a scalable, high-performance, fair Spinlock based on linked lists. The application thread spins only on local variables, and the direct precursor is responsible for notifying it to end its spin, thus greatly reducing the number of unnecessary processor cache synchronization and reducing the bus and memory overhead. MCS comes from the initials of its inventors: John Mellor-Crummey and Michael Scott.
public class MCSLock {
public static class MCSNode {
volatile MCSNode next;
volatile boolean isLocked = true;
}
private static final ThreadLocal<MCSNode> NODE = new ThreadLocal<>();
/ / the queue
@SuppressWarnings("unused")
private volatile MCSNode queue;
private static final AtomicReferenceFieldUpdater<MCSLock,MCSNode> UPDATE =
AtomicReferenceFieldUpdater.newUpdater(MCSLock.class,MCSNode.class,"queue");
public void lock(a){
// Create a node and save it to ThreadLocal
MCSNode currentNode = new MCSNode();
NODE.set(currentNode);
// Set queue to the current node and return the previous node
MCSNode preNode = UPDATE.getAndSet(this, currentNode);
if(preNode ! =null) {
// If the previous node is not null, the lock is already held by another thread
preNode.next = currentNode;
// Loop until the lock flag of the current node is false
while (currentNode.isLocked) {
}
}
}
public void unlock(a) {
MCSNode currentNode = NODE.get();
// Next is null to indicate that there are no threads waiting to acquire locks
if (currentNode.next == null) {
// Update the status and set queue to null
if (UPDATE.compareAndSet(this, currentNode, null)) {
// queue==currentNode, i.e. there is no node behind the currentNode
return;
} else {
// If not successful, queue! =currentNode; if the currentNode is followed by another node, a thread is waiting
// If subsequent nodes of the current node are null, wait until they are not null (see locking method).
while (currentNode.next == null) {}}}else {
// If the value is not null, it indicates that a thread is waiting to acquire the lock. In this case, the node lock status corresponding to the waiting thread is updated to false, and the successor node of the current thread is set to NULL
currentNode.next.isLocked = false;
currentNode.next = null; }}}Copy the codeCLHLock and MCSLock
- The difference is that CLHLock is based on an implicit list with no real subsequent node attributes, whereas MCSLock is a display list with an attribute pointing to subsequent nodes.
- The state of the thread that acquired the lock is stored in nodes, and each thread has a separate node. This solves the TicketLock multi-processor cache synchronization problem.
Multiple threads access resources concurrently
Classification of lock states
The Java language has four states specifically for the synchronized keyword: no lock, biased lock, lightweight lock, and heavyweight lock, but you need to understand Java object headers and Monitor before you can understand these locks.
Java object head
Synchronized is a pessimistic lock that requires a resource to be locked before performing synchronization. This lock is inside the object header. Taking the Hotspot VIRTUAL machine as an example, the Hopspot object header contains two main parts of data: a Mark Word (marking field) and a Class Pointer (type Pointer).
Mark Word: Default store object HashCode, generational age, and lock flag bit information. This information is irrelevant to the definition of the object itself, so Mark Word is designed as a non-fixed data structure to store as much data as possible in a very small amount of memory. It reuses its own storage space based on the state of the object, which means that the data stored in Mark Word changes as the lock flag bit changes during runtime.
Class Point: A pointer to the object’s class metadata that the virtual machine uses to determine which class the object is an instance of.
The size of a Mark Word on a 32-bit VM is different from that of a 64-bit VM. The Mark Word and class Pointer on a 32-bit VM occupy 32bits of bytes respectively. A 64-bit VM uses 64bits of Mark Word and class Pointer bytes
It is translated in Chinese
- Stateless is equal to
unlockedThe object header allocates 25bit space for storing the hashcode of the object, 4bit space for storing the generation age, 1bit space for storing the identification bit of whether the lock is biased or not, and 2bit space for storing the identification bit of 01 Biased lockingIt is divided into more details and still opens 25bit space, in which 23bit is used to store the thread ID, 2bit is used to store the epoch, 4bit is used to store the generational age, 1bit is used to store whether there is bias lock identifier, 0 means no lock, 1 means bias lock, and the identifier bit of the lock is still 01Lightweight lockTo directly open up 30bit space to store the pointer to the lock record in the stack, 2bit to store the lock flag bit, its flag bit is 00Heavyweight lockAs with the lightweight lock, 30 bits of space is used to store Pointers to the heavyweight lock, and 2 bits are used to store the identification bit of the lock, which is 11The GC tagOpen up 30bit memory space is not occupied, 2bit space storage lock flag bit is 11.
The lock flag bit of both no-lock and biased lock is 01, but the 1bit in front distinguishes whether the state is no-lock or biased lock.
The enumeration in the Markoop.hpp class in the OpenJDK provides a clue as to why memory is allocated this way
To explain
- Age_bits is what we call a generational collection identifier, occupying 4 bytes
- Lock_bits is the flag bit of a lock, occupying two bytes
- Biased_lock_bits indicates whether to bias the lock. It takes 1 byte
- Max_hash_bits specifies the number of hashcode bytes that can be calculated without locking. 32-4-2 -1 = 25 bytes for a 32-bit VM or 57 bytes for a 64-bit VM. But there are 25 bytes left unused, so a 64-bit Hashcode takes up 31 bytes
- Hash_bits: For 64-bit virtual machines, 31 is used if the maximum number of bytes is greater than 31; otherwise, the actual number of bytes is used
- Cms_bits specifies whether a 64-bit vm uses 0 bytes. If yes, a 64-bit vm uses 1byte
- Epoch_bits is the size of the epoch in bytes, which is 2 bytes.
Synchronized lock
Synchronized uses lock records stored in Java object headers.
The JVM implements method synchronization and code block synchronization based on entering and exiting Monitor objects. Code block synchronization is implemented using monitorenter, which inserts at the start of the synchronized code block after compilation, and Monitorexit, which inserts at the end of the method and at exceptions. Any object has a Monitor associated with it, and when a Monitor is held, it is locked.
According to the vm specification, when monitorenter executes, it first attempts to acquire the lock on an object. If the object is not locked or the current thread already owns the lock, it increments the lock counter by one. Accordingly, monitorexit decrement the lock counter by one. When the counter is reduced to 0, the lock is released. If the object lock fails to be acquired, the current thread blocks and waits until the object lock is released by another thread.
Monitor
Synchronized is implemented through an internal object called a monitor Lock, and the essence of the monitor Lock depends on the underlying operating system’s Mutex Lock (Mutex Lock). However, switching between threads in the operating system requires switching from user state to core state, which costs a lot and takes a relatively long time to switch between states, which is why Synchronized is of low efficiency. Therefore, this type of Lock, which relies on the implementation of the operating system Mutex Lock, is called a heavyweight Lock.
Java SE 1.6 introduces biased locks and lightweight locks to reduce the performance cost of acquiring and releasing locks. There are four lock states, from lowest to highest: no lock state, biased lock state, lightweight lock state, and heavyweight lock state. Locks can be upgraded but not degraded.
So there are four lock states: lock free, biased, lightweight, and heavyweight. As locks compete, locks can be upgraded from biased locks to lightweight locks to heavyweight locks (but locks are upgraded in one direction, meaning they can only be upgraded from low to high, with no lock degradation). Bias locking and lightweight locking are enabled by default in JDK 1.6. We can also disable bias locking by -xx: -usebiasedlocking =false.
Classification and interpretation of locks
Let’s start with a general flow chart to get a feel for the process, and then we’ll break it down
unlocked
No lock, that is, no resource is locked. All threads can access the same resource, but only one thread can modify the resource successfully.
The feature of lockless is that the modification operation is carried out within the loop, and the thread will continuously try to modify the shared resource until it can successfully modify the resource and exit. There is no conflict in this process, which is very similar to the CAS implementation we introduced in the previous article. The principle and application of CAS is the lockless implementation. Lockless can’t completely replace locking, but the performance of locking is very high in some cases.
Biased locking
The authors of HotSpot have found that in most cases, locks are not only not contested by multiple threads, but also acquired by the same thread multiple times. Biased locking appears in this situation, which is to solve the problem of improving performance when only one thread performs synchronization.
As can be seen from the allocation of object headers, biased locks have more thread ids and epochs than unlocked locks. Here we describe the acquisition process of biased locks
Bias lock acquisition process
- First the thread accesses the synchronized code block by checking the object header Mark Word
Lock flag bitDetermine the current lock status. If the value is 01, it indicates no lock or biased lock, and then based onBiased lockIs marked to determine whether there is no lock or biased lock. If there is no lock, go to the next step - The thread uses CAS to try to lock the object. If CAS is used to replace ThreadID successfully, it means that it is the first time to lock the object. Then the current thread will acquire the biased lock of the object, and record the current ThreadID and the epoch of obtaining the lock in the Mark Word of the object header. The synchronized code block is then executed.
SafePoint: A SafePoint is a place in Java code where a thread can pause.
When the next thread enters and exits the synchronization code block, it does not need to conduct CAS operation to lock and unlock, but simply determine whether the thread ID pointing to the current thread is stored in the Mark Word of the object header, and the Mark to judge is of course based on the flag bit of the lock. It looks something like this if you use a flow chart
Closing bias lock
Biased locking is enabled by default in Java 6 and Java 7. Since biased locking is intended to improve performance when only one thread is executing synchronized blocks, if you are sure that all locks in your application are normally in contention, you can turn biased locking off with the JVM argument: -xx: -usebiasedLocking =false, and your application will enter lightweight locking by default.
About the epoch
The object header of the bias lock has a value called epoch, which acts as a timestamp for the validity of the bias.
Lightweight lock
Lightweight lock means that when the current lock is biased, the resource is accessed by another thread, so the biased lock will be upgraded to lightweight lock. Other threads will try to acquire the lock through the form of spin without blocking, thus improving performance. The following is the detailed acquisition process.
Lightweight locking locking process
- Then, if the CAS operation fails to replace ThreadID, go to the next step
- If the CAS operation fails to replace the ThreadID (switch to another thread’s point of view), the resource has been accessed synchronously, the lock is revoked, the bias lock is revoked, and the thread holding the bias lock arrives
Global SafePoint, the thread holding the bias lock will be suspended, and then the status of the thread holding the bias lock will be checked. If the synchronization has exited, the thread holding the bias lock will be woken up to perform the next step - Check if the Mark Word in the object header records the current thread ID, if so, execute the synchronization code, if not, perform step 2 of the bias lock acquisition process.
If expressed as a flow, it looks like this (with partial lock acquisition included)
Heavyweight lock
Heavyweight lock acquisition process is more complex, friends to be prepared, in fact, look at a few times is not so troublesome, ha ha.
The process of acquiring heavyweight locks
-
Then the above biased lock acquisition process, from biased lock upgrade to lightweight lock, go to the next step
-
Will be held at the original biased locking in the thread’s stack allocation record, lock the object header Mark Word copy to the original hold biased locking is recorded in the thread, then the original hold to lock the thread for lightweight lock, and then resume the original hold biased locking thread, from a security point to continue, after the execution, execute the next step, the current thread to perform step 4
-
After the lightweight unlock operation is complete, determine the following two conditions
- Determines whether the lock record pointer in the Mark Word in the object header points to a pointer to the current stack record
- Whether the Mark Word information copied to the current thread lock record is the same as the Mark Word in the object header.
If both criteria are met, the lock will be released. If one of the criteria is not met, the lock will be released and the waiting thread will be aroused for a new round of lock competition.
-
Copy the MarkWord in the object header to the lock record of the current thread. Execute the CAS lock operation, which will point the pointer of the lock record in the object header MarkWord to the lock record of the current thread. If successful, obtain the lightweight lock, execute the synchronization code, and then execute step 3. Go to the next step
-
If the current thread does not successfully acquire the lock using CAS, it spins for a while, tries again, and if it does not acquire the lock after several spins have reached the upper limit, the lightweight lock is upgraded to the heavyweight lock
If I were to use a flow chart, it would look something like this
Fairness and unfairness of locks
We know that in a concurrent environment, multiple threads need to access the same resource, and only one thread can acquire the lock and access the resource at a time. What about the remaining threads? This is like the model of the canteen line. The first person who arrives at the canteen has the right to buy the food first, so the rest of the people need to queue behind the first person. This is the ideal situation, that is, everyone can buy the food. Then the reality is that while you are waiting in line, there will be a few dishonest people who want to take a shortcut and jump the queue for dinner. If the person who jumps the queue has no one to stop him or her, he or she will be able to buy dinner. If someone stops him or her, he or she will have to go to the back of the queue.
For normal queuing people, no one cuts the line, everyone is waiting for the chance to queue for lunch, so this way is fair to everyone, first come, second served. This type of lock is also called a fair lock.
So if the person who jumps the queue succeeds in buying the meal and no matter whether someone stops him during the process, his behavior is unfair to the people who wait in line normally, which is also called unfair lock in the world of locking.
Then we can draw the following conclusion from the above description
Fair lock means that the order in which threads acquire locks is allocated according to the order in which they acquire locks, i.e., first-come, first-served FIFO order. The non-fair lock is a preemption mechanism to obtain the lock, which is random. Unlike the fair lock, the first to get the lock may not be the first to get the lock, which may cause some threads can not get the lock all the time, and the result is unfair.
Implementation of lock fairness
In Java, we typically implement lock fairness through ReetrantLock
Let’s explain the fairness and unfairness of locks through two examples
Fairness of locks
public class MyFairLock extends Thread{
private ReentrantLock lock = new ReentrantLock(true);
public void fairLock(a){
try {
lock.lock();
System.out.println(Thread.currentThread().getName() + "Holding lock");
}finally {
System.out.println(Thread.currentThread().getName() + "Release the lock."); lock.unlock(); }}public static void main(String[] args) {
MyFairLock myFairLock = new MyFairLock();
Runnable runnable = () -> {
System.out.println(Thread.currentThread().getName() + "Start");
myFairLock.fairLock();
};
Thread[] thread = new Thread[10];
for(int i = 0; i <10; i++){ thread[i] =new Thread(runnable);
}
for(int i = 0; i <10; i++){ thread[i].start(); }}}Copy the codeWe create a ReetrantLock and pass true to the constructor. We can look at the constructor for the ReetrantLock
public ReentrantLock(boolean fair) {
sync = fair ? new FairSync() : new NonfairSync();
}
Copy the codeAccording to the JavaDoc comments, if true, a fair lock for ReentrantLock will be created and then a FairSync will be created, which is an inner class of Sync whose main purpose is to synchronize objects to obtain a fair lock.
And the Sync is already in the inner class, Sync, inherited AbstractQueuedSynchronizer class AbstractQueuedSynchronizer AQS is we used to say, It is the most important class in JUC (java.util.Concurrent) that implements both exclusive and shared locks.
abstract static class Sync extends AbstractQueuedSynchronizer {... }Copy the codeThat is, if we set fair to true, we can implement a fair lock, right? Going back to the sample code, we can execute this code, and its output is taken sequentially (not posted here for space reasons), which means that we create a fair lock
Unfairness of locks
The opposite of fair is unfair. We implement a fair lock by setting the fair parameter to true, as opposed to setting the fair parameter to false. Prove it with the facts
private ReentrantLock lock = new ReentrantLock(false);
Copy the codeThe rest of the code stays the same, so let’s run it and see the output (partial output)
Thread-1Start the Thread -4Start the Thread -1Holding lock Thread-1The lock Thread- was released5Start the Thread -6Start the Thread -3Start the Thread -7Start the Thread -2Start theCopy the codeIt can be seen that threads are not started in order to obtain the lock. It can be seen that the acquisition of the lock by the unfair lock is out of order, that is, there is a process of preempting the lock. That is, we implement an unfair lock by setting the fair parameter to false.
ReentrantLock Basic Overview
ReentrantLock is a ReentrantLock, as well as a mutex, that has the same method and monitor lock semantics as synchronized, but has more extensible capabilities than synchronized.
The ReentrantLock’s reentrancy means that it can be owned by the thread that was successfully locked last time but has not yet been unlocked. When only one thread attempts to lock, calling the lock() method immediately returns success and acquires the lock directly. This method returns immediately if the current thread already owns the lock. This can be checked using isHeldByCurrentThread and getHoldCount.
The constructor of this class accepts the optional fairness parameter. When fairness is set to true, when a multi-threaded contention attempts to lock, the lock tends to be accessed by the thread with the longest waiting time, which is also an indication of fairness. Otherwise, the lock does not guarantee the order of access for each thread, which is an unfair lock. A program that uses a fair lock with many thread accesses may show lower overall throughput (that is, slower; Usually much slower). However, the number of times it takes to acquire the lock and ensure that the thread does not starve is relatively small. Note however: fairness of locks does not guarantee fairness of thread scheduling. Thus, one of the multiple threads using a fair lock may acquire it multiple times in a row while the other active threads are not doing it and do not currently hold the lock. This is also a sign of mutual exclusion.
Also note that the tryLock() method does not support fairness. If the lock is retrievable, it can still return success even if other threads wait.
The following code is recommended for locking and unlocking
class MyFairLock {
private final ReentrantLock lock = new ReentrantLock();
public void m(a) {
lock.lock();
try {
// ...
} finally {
lock.unlock()
}
}
}
Copy the codeThe ReentrantLock lock supports a maximum of 2,147,483,647 recursive locks through the same thread. Trying to exceed this limit causes the locking method to throw an error.
How does ReentrantLock implement lock fairness
We mentioned above that ReentrantLock can be used to implement fairness of locks. What is the mechanism? ReentrantLock: ReentrantLock: ReentrantLock: ReentrantLock: ReentrantLock
Tracing the source code reveals that calling lock. Lock () is actually calling sync’s internal method
abstract void lock(a);
Copy the codeSync is the most basic synchronization control Lock class, with fair and unfair Lock implementations. It inherits AbstractQueuedSynchronizer using AQS state represents the number of locks held.
Lock is an abstract method that needs to be implemented by subclasses, and classes that inherit AQS mainly have
As we can see, all classes implementing AQS are located under the JUC package, and there are five main classes: ReentrantLock, ReentrantReadWriteLock, Semaphore, CountDownLatch, and ThreadPoolExecutor, ReentrantLock, ReentrantReadWriteLock, and Semaphore all implement fair and unfair locks.
The following is the inheritance of FairSync
Inheritance of NonFairSync for an unfair lock
As can be seen from the inheritance diagram, the inheritance relationship of the two classes is the same. We found from the source code, the implementation of fair lock and unfair lock is the difference between the following code (in the next article, we will analyze the implementation of fair lock and unfair lock from the perspective of principle).
Through the comparison of the source code in the figure above, it is clear that the only difference between the lock() method of a fair lock and that of an unfair lock is that the fair lock has an additional constraint on acquiring the synchronous state: hasqueued24 ().
Hasqueuedtoraise () is also a method in AQS used to query whether any thread has waited longer to acquire a lock than the current one, that is, each waiting thread is on a queue. It determines whether the current thread on the queue has acquired a lock, Return true if the current thread is queued before the current thread, false if the current thread is at the beginning of the queue or if the queue is empty.
To sum up, fair lock is to achieve multiple threads to obtain locks in accordance with the order of lock application through synchronization queue, so as to achieve fair characteristics. Unfair lock does not consider the queuing problem when adding the lock, directly try to obtain the lock, so there is the situation of obtaining the lock first after applying.
Locks are distinguished by whether or not they are reentrant
Reentrant lock
A reentrant lock, also known as a recursive lock, means that when the same thread acquires the lock from the outer method, the inner method of the same thread automatically acquires the lock (provided that the lock object is the same object or class). The lock will not be blocked because it has been acquired before and has not been released. Java ReentrantLock and synchronized are both reentrantlocks. One advantage of ReentrantLock is that it can avoid deadlocks to some extent.
Let’s start with a piece of code to illustrate the reentrancy of synchronized
private synchronized void doSomething(a){
System.out.println("doSomething...");
doSomethingElse();
}
private synchronized void doSomethingElse(a){
System.out.println("doSomethingElse...");
}
Copy the codeIn the above code, we lock doSomething() and doSomethingElse() using synchronized, and doSomething() calls doSomethingElse(), Because synchronized is reentrant, the same thread that calls the doSomething() method can also enter a doSomethingElse() method.
No reentrant lock
If synchronized is a non-reentrant lock, then the lock on doSomething() must be dropped when the doSomethingElse() method is called; the object lock is actually held by the current thread and cannot be released. So a deadlock occurs.
That is, non-reentrant locks cause deadlocks
Multiple threads can share the same lock
Exclusive locks and shared locks
Exclusive multiple locks and shared locks generally correspond to JDK source code ReentrantLock and ReentrantReadWriteLock source code to introduce exclusive locks and shared locks.
An exclusive lock, also known as an exclusive lock, means that the lock can only be owned by one thread at a time, and other threads that want to access resources will be blocked. The implementation classes for synchronized in the JDK and Lock in JUC are mutex.
A shared lock means that the lock can be owned by multiple threads. If a thread adds a shared lock to a resource, other threads can only add a shared lock to the resource, not an exclusive lock. The thread that acquires the shared lock can only read the data, not modify it.
ReentrantReadWriteLock has two locks: ReadLock and WriteLock, a ReadLock and a WriteLock. A closer look reveals that ReadLock and WriteLock are locks implemented by the internal class Sync. Sync is derived from a subclass of AQS, which is the root of concurrency, as well as CountDownLatch, ReentrantLock, and Semaphore.
In ReentrantReadWriteLock, the lock body of a read lock and a write lock is Sync. However, the read lock and write lock are added in different ways. Read locks are shared locks, while write locks are exclusive locks. The shared lock of a read lock ensures efficient concurrent reads, while the read-write, read-write, and write-write processes are mutually exclusive because the read lock and the write lock are separated. So ReentrantReadWriteLock is a huge increase in concurrency over regular mutex.
Welcome to attention
Article Reference:
Pessimistic and optimistic locks for Java multithreading
Baike.baidu.com/item/ pessimistic locks
Blog.csdn.net/qq_34337272…
www.blogjava.net/jinfeng_wan…
Blog.hudiary.cn/articles on spin locks
En.wikipedia.org/wiki/Ticket…
Blog.stephencleary.com/2013/04/rec…
Researcher.watson.ibm.com/researcher/…
Tech.meituan.com/2018/11/15/…
www.jianshu.com/p/eaea337c5…
Blog.csdn.net/oChangWen/a…