Why you need a lock

When concurrent access to shared resources is not managed, the result is chaos. As shown above, both sides want to change the color of the cube, but at any given moment, we can’t be sure what color the cube is going to be next, because we can’t be sure whose time slice ended up changing the color of the cube. Obviously, such uncertainty is unacceptable to the program. What we want is for the red square to come first and then the square to be red. And then after the green square, the square is green, or the other way around.

Then, the code scope that each party modifies the other block is called the critical section, and the behavior to enter the critical section and modify is called the race condition. To eliminate the impact of the race condition and make the program deterministic, we need to lock the shared resource so that only one thread can access it at any given time.

When only the thread with the lock has access to the critical section, the result is the same as above, rather than the chaotic behavior of changing the block to green while the other thread is changing it to red.

Java also provides different locking schemes for a variety of possible concurrent scenarios, and having this knowledge allows us to take most of the scenarios at ease and implement more appropriate locking schemes when we want to achieve more aggressive goals.

The characteristics of the lock

Locks in Java are distinguished between the Synchronized and Lock interfaces, and you can see descriptions of built-in locks, shared locks, reentrant locks, and the like, which are really about features rather than specific implementations of a particular type of Lock. Just as a person can have multiple identities — he’s a doctor, he’s A CEO, he’s a father — locks can have multiple identities, they can be shared, they can be reentrant, etc.

Locks in Java may have the following features:

  • Pessimistic locking and Optimistic locking: Pessimistic locking means that while you are using a shared resource, other threads will modify the data, so to avoid tampering, other threads entering the critical section will be blocked until they finish using it. An optimistic lock, on the other hand, assumes that while it is using a shared resource, other threads will not modify the data. Therefore, an optimistic lock only races the locks and does not block other threads.
  • Exclusive and shared locks: depending on whether multiple threads are allowed to access a shared resource at the same time. If you can anticipate that no writes will occur in the next few days, you can increase concurrency efficiency by allowing multiple access. Although everyone is in the critical section, there is no race condition; after all, the read operation does not change any data.
  • Fair lock and unfair lock: distinguish between whether to assign locks to threads according to the order in which they apply for locks, that is, whether to allow queue jumping. If you allow queue-jumping, you may make some threads hungry, unable to allocate a lock to continue running; If queue jumping is not allowed, then some urgent tasks will be delayed, after all, we also need VIP access in life.
  • Reentrant and non-reentrant locks: Distinguish between the thread that acquired the lock and whether it can acquire the lock repeatedly before releasing it. If a recursive method requires a lock, it cannot recurse when the lock is non-reentrant. In life, for example, it can be understood as whether the act of blocking is allowed. When eating in a restaurant, the need to add dishes, the restaurant is allowed to plug the behavior, but also acceptable. However, if you register to see a doctor, and after the diagnosis, you say to the doctor, “Let my friend take a look,” and the doctor ignores you, such behavior is not allowed.
  • Interruptible and non-interruptible locks: Whether to allow a response when a lock is not applied late or when a thread is interrupted. Interruptible locks allow a thread to determine how long it waits for the lock and how it responds to interrupts.

Of course, this distinguishes the locking features in Java in a larger direction, but it does not represent all the features. This is specific because these features have to be weighed when implementing arbitrary locks. Other features of locks will appear later, but mostly refer to the unique features of a particular type of lock.

CAS(Compare and Set)

Not only Java, but the operating system’s concurrency means also depend on CAS, which is literally the cornerstone of atomic operations. CAS can be seen in various locking schemes to further improve performance. Therefore, for the sake of smooth writing later, CAS will be explained separately first.

CAS, which means compare and exchange, is guaranteed atomicity by hardware-supported atomic instructions:

CAS accepts three parameters, the memory address, the expected memory value, and the memory value to be updated. First, the location of the data is found through the memory address. Next, compare the value of the memory address to see if it is the same as expected. If not, return false; If so, set the new value and return true. During this process, the CPU locks the memory bus so that no other CPU can access the memory until the instruction ends, ensuring the atomicity of the instruction operation.

Of course, CAS will have the ABA problem, that is, when the data goes through the process of changing from A to B and then changing A, for some callers, A is no longer the expected A. This can be distinguished by adding A->B->A to 1A->2B->3A. The ABA solution in Java is supported by the AtomicStampedReference.

CAS has features that make it possible to guarantee atomicity for individual variable operations.

The realization of Synchronized

First and foremost, Synchronized is an all-too-familiar means of concurrency. Synchronized is exclusive, unfair, reentrant, and noninterruptible. It applies to pairs of methods, blocks of code, and objects.

Synchronized is a kind of conduit, and the implementation of Synchronized is completely transparent to the user. It is in line with the characteristics of the tube: language features to provide markup, translation recognition by the editor, by the language implementation to ensure atomicity. Simply put, Synchronized is a guarantee at the language implementation level — only one thread at a time can access the tag range.

    / / lock
    public static synchronized void A(){ index = 1; }

    / / lock
    public static void B(){
        synchronized (SData.class){index = 2; } } publicvoid C(){
        / / object lock
        synchronized (this){index = 3;}
    }

    // // Object locks
    public synchronized void D(){
        index = 4; 
    }

    public void E(){
        / / object lock
        synchronized (lock){index = 5; } } publicvoid F(){
        / / lock
        synchronized (SData.class){index = 6;}
    }
Copy the code

These are all possible uses of Synchronized, which can be divided into class and object locks, with ABF in the former and CDE in the latter.

In will compile the good. Class file, through the command

Javap-verbose Specifies the class path

After parsing, you can see what a method looks like after it has been translated. Methods modified by synchronized are marked in the method’s flag bit:

flags: ACC_PUBLIC, ACC_STATIC, ACC_SYNCHRONIZED
Copy the code

ACC_SYNCHRONIZED means that this is a synchronized method, and access to this method requires a lock.

If a block of code is locked, it will have the following instruction line

X,y, and z represent numbers.x: monitorenter
...
y: monitorexit
...
z: monitorexit
...
Copy the code

Where monitorenter means that the following instructions need to be executed to get the lock and enter the synchronized code block, monitorexit means that the synchronized code block exits and the lock is released. The reason why there are two MonitoreXit is because an exception exit is needed to prevent an exception from occurring in the generation of the synchronized code block and not releasing the lock, causing other threads to block.

And the ultimate realization needs to be further understood.

How is Synchronized implemented at run time

In Java, everything is an object, a type, which can also be represented as an object of type Class. The storage layout of objects in the VIRTUAL machine can be divided into three areas: object headers, Instance Data, and Padding.

The Header stores business-irrelevant information, divided into Mark Word, Class MetaData Address(type pointer), and Array Length if the object is of an Array type.

With Synchronized, an object is locked, and a specific type is treated as an object of type Class, thus distinguishing between object locks and Class locks.

The Mark Word contains information such as the HashCode, GC generation age, lock status identifier, thread holding the lock, preferred thread ID, preferred timestamp, and so on

Thus, who holds a lock can be known by Mark Word. So how do you use this information?

Java associates each object with a Monitor, which can be implemented in a variety of ways, and can be created and destroyed along with the object, or generated when a thread attempts to acquire a lock. This means that every object is inherently a lock, monitored by Monitor. Its main data structure is visible in objectMonitor.hpp

ObjectMonitor(){... _WaitSet = NULL;// The set of threads in the wait state
   _owner // The thread that got the lock
   _EntryList    = NULL ; // The collection of threads waiting for a lock block. }Copy the code

  1. When a thread requests a lock, it waits in the _EntryListd collection and then participates in the lock race
  2. When a thread acquires a lock, _Owner flags the thread that acquired the lock
  3. If the thread that acquired the lock calls the wait() method, it enters the _WaitSet set, releases the lock at the same time, and waits to be awakened
  4. When the _WaitSet thread wakes up, it reparticipates in the race

Synchronized, then, depends on how Mark Word is used and how Monitor is implemented.

The optimization of Synchronized

Monitor depends on the implementation of the underlying operating system. Applying and releasing locks, blocking and waking up generate system calls and considerable overhead. Synchronized in this way is also called heavyweight lock. Frequently using Synchronized to apply for and release locks will degrade system performance.

Since Synchronized is implemented at the language level, there’s a lot of room for imagination in how it’s implemented. This also leads to the next content, biased locking/lightweight locking/heavyweight locking /.

Synchronized will go through lock inflation from biased locks, to lightweight locks, to heavyweight locks, depending on how they actually run.

If only one thread is going to the critical section for a long period of time, or if concurrency is not coming that fast, access to the critical section should behave as if there were no locks. Mark Word’s reserved location records the state of the lock, so you know what the current lock is.

Biased locking

At the beginning of the program, it is in an unlocked state. Next, a thread applies for the lock, and Mark Word marks it as a biased lock when the CAS race lock (CAS guarantees atomicity of the race) is successfully acquired. When the same thread arrives again, it is found to be the lock holder and is biased to the lock, directly into the critical section.

Thus, biased locking means that no race condition can occur because there is only one thread.

Lightweight lock

As the program runs, a new thread tries to enter the critical section, and the contention lock fails through CAS. Mard Work immediately makes the biased lock flag lock a lightweight lock because a race condition has already occurred. Then, the lock is repeatedly acquired for the thread through CAS, and if the thread holding the lock is in the critical section for a short time, the thread applying for the lock will acquire the lock quickly.

So, lightweight locking means that there are race conditions, but people can be assigned to locks very quickly.

Heavyweight lock

Of course, the thread requesting the lock does not always acquire it quickly, so rather than wasting CPU time with repeated CAS retries, it is better to block the thread directly. Then, in the case of lightweight locks, if a thread fails to acquire the lock after a certain number of retries, Mard Work immediately marks the lightweight lock as a heavyweight lock, and after that all threads that fail to acquire the lock will be blocked, requiring the participation of Monitor.

Thus, heavy locking means that threads cannot be assigned to locks quickly in the event of a race condition.

Synchronized locks can only expand, not contract. Biased lock and light lock for optimistic lock, heavyweight lock for pessimistic lock.

The beauty of Synchronized is that its optimization, lock application release, and lock allocation are all automatic and can be quickly used by developers.

The Lock semantics

Synchronized can complete most concurrent scenarios, but can cause threads to block for an unknown amount of time. “If I go to a restaurant and it’s full, I want to leave rather than wait,” Synchronized can’t satisfy that scenario. Also, sometimes we want to control the lock allocation process, and even more, we like VIP access and want some threads to get the lock in priority.

Lock has its stage:

public interface Lock {
    void lock(); // Acquire the lock. If the lock is not acquired, it will block
    void lockInterruptibly() throws InterruptedException; // Acquire lock, can be interrupted, not acquired will be blocked
    boolean tryLock(); // Acquire the lock without blocking regardless of the result
    boolean tryLock(long time, TimeUnit unit) throws InterruptedException; // Acquire the lock, return the result at most within unit time, can be interrupted
    void unlock(); / / releases the lock
    Condition newCondition(); // You can obtain locks only after certain conditions are met
}
Copy the code

The Lock interface provides a set of method semantics to implement a Lock. When implementing a Lock, we should consider how to satisfy the function expressed by Lock and have its own characteristics.

A Lock should have the following characteristics:

  • You can block without access, just like Synchronized, and use lock() to express semantics
  • You can also respond to interrupts during the lock acquisition process with lockInterruptibly() and tryLock()
  • You can also decide how long you want to wait when you can’t get the lock, and then go ahead and tryLock() to express semantics
  • It supports a conditional lock that allows the thread to wait for an event to occur before acquiring the lock. It looks like a fence, and the semantics are expressed in Condition

The clearest contrast between Lock and Synchronized is that it is interruptible, does not force blocking, and expresses the conditional locking feature that Synchronized does not support.

AQS basis

The lock processing is divided into two parts, one part is how to add unlock, and the other part is to assign the lock to whom. In Synchronized, both sections are transparent, only marked with keywords. When you want to implement a lock, you have to take care of both parts, and there are a lot of details that need to be paid attention to.

In order to put more energy on the “add how to unlock”, to express the characteristics of different locks, Java abstract out AQS (AbstractQueuedSynchronizer) to assist in the Lock. AQS solves the problem of “to whom to assign locks”.

Here, just for a summary of the operating mechanism of AQS, more specific reference: penny know AQS (AbstractQueuedSynchronizer)

  1. When a lock is requested, that is, a method with semantics similar to acquire() is called,AQS will ask the subclass if the lock was successful, and if so, the run continues. Otherwise, AQS will record the request for a lock in Node granularity, insert it into its maintained CLH queue and suspend the thread.
  2. In the CLH queue, only the node closest to the head node that has not cancelled applying for a lock is eligible to apply for a lock.
  3. When the thread is awakened, it attempts to acquire the lock. If it cannot acquire the lock, it continues to suspend. If you get it, continue running.
  4. When a thread releases a lock, i.e., calls the semantically similar method release(), AQS will ask the subclass if the lock has been successfully unlocked, and if so, AQS will proactively call the appropriate thread from the CLH queue, procedure 2, 3.
  5. If you need to wait for the condition to meet before applying for a lock, that is, when a method similar to wait() is called, it is shown in AQS that a one-way waiting condition queue is maintained with Node as the granularity to suspend the thread represented by Node.
  6. When the condition is met, that is, when the semantically similar method of signal() is called, the Node at the top of the waiting condition queue that has not cancelled the wait is awakened and 1 is performed.
  7. Subclasses can maintain the AQS state property to record the added unlock state. AQS also provides the CAS method compareAndSetState() to preemp update state.

The key point is that threads applying for locks via AQS can compete for locks via CAS. State indicates how many locks have been assigned, and CAS guarantees the atomicity of the state that represents the state of the lock, so that threads can be suspended if necessary. When the thread is awakened, it participates in the lock contention process again. From the outside, it looks as if the entry method was blocked and restored in the appropriate future.

With AQS, you can see how other locks implement Lock semantics and what features they have.

ReentranLock(ReentranLock)

ReentranLock implements Lock semantics, and has the characteristics of AQS, is pessimistic Lock, exclusive Lock, reentrant Lock, whether fair and whether interruptible depends on the user.

ReentranLock inherits the AQS feature with its internal Sync class, and when instantiated, fairness can be determined by parameters. A ReentranLock allows only one thread to hold the lock, so it is an exclusive lock, and any other thread applying for the lock will therefore be suspended.

The reentrability of ReentranLock is shown in that, when the lock is held by a thread, AQS asks whether the lock is successfully applied. If Sync finds that the thread applying for the lock is the same as the thread holding the lock, it will update the state state through CAS to re-assign the lock and reply that the lock is successfully applied. That’s reentrant.

Whether it is fair is reflected in that, when applying to AQS for allocation of lock, there is a chance to ask whether the lock is successful. At this time, whether to ignore the waiting thread in the CLH queue represents whether to give the opportunity to jump the queue.

Concrete implementation principle is visible: ReentranLock

ReentrantReadWriteLock(read/write lock)

ReentrantReadWriteLock also implements Lock semantics and provides AQS features. ReentrantReadWriteLock is a reentrant Lock.

ReentrantReadWriteLock is a pessimistic lock or an optimistic lock. Both exclusive and shared locks. Why do you say so?

ReentrantReadWriteLock applies to scenarios where the number of read operations exceeds that of write operations. Read locks and write locks work together. In general, the ReentrantReadWriteLock lock has some features that depend on the time period of observation.

Only read lock

For a period of time, if only read locks are available, then ReentrantReadWriteLock is a shared lock or an optimistic lock. This is easy to understand. The read operation does not change the state of the data, so there is no race condition. In this case, everyone can acquire the lock, and there are no threads queuing in the CLH queue.

Only write lock

For a period of time, ReentrantReadWriteLock is a pessimistic lock or an exclusive lock if only write locks are available. In this case, ReentrantReadWriteLock behaves like ReentranLock. Because the race condition is intense, threads can only pass through the critical section one by one.

Both read and write locks are available

ReentrantReadWriteLock is a pessimistic lock if both read and write locks exist for a period of time. Although read locks do not have a race condition, they are not allocated until the write lock is complete, so everyone needs to queue up in the CLH.

It is important to note that if a read lock is not released in front of a write lock, the write lock must wait and the data should not expire while the read lock is being processed. This provides a window of time for the read lock to process and makes the write lock more exclusive.

Reentrancy and fairness

Fair or not Like ReentranLock, the implementation class to which the lock is assigned by AQS can be implemented by choosing whether to ignore the situation in the CLH queue when the lock is first requested.

In the case of reentrancy, write locks are exclusive and can be maintained directly through state, while in the case of read locks and shared locks, something else is required to record the reentrancy of each thread. ReentrantReadWriteLock records this information by using ThreadLocal to maintain an object of type HoldCounter inside each thread.

In particular, threads that have both read locks can continue to apply for write locks, whereas threads that have not.

The implementation principle is as follows: ReentrantReadWriteLock

Semaphore

Semaphore’s inner class Sync inherits AQS and implements Lock semantics except for conditional locking (without directly declaring implementation).

Semaphore is a non-reentrant lock that can be applied for more than one lock at a time. It is a rare lock that does not support reentrant.

The Semaphore scenario is how to concurrently consume limited shared resources. For example, table, if there is no table, will not receive a new batch of guests.

The reason why Semaphore does not support reentry is that it can cause deadlocks because of the limited resources. Take an extreme example of a table: if the guests who are eating all ask for more seats, but there are no more seats, then the request for a table is not able to cause waiting, and the waiting guests do not want to finish eating and release a table.

Semaphore’s fair or unfair nature also depends on whether the CLH queue is considered when applying to AQS for the first time.

For details, see Semaphore

Other features

In addition to the above features that a lock should consider, there are other unique features that a lock has that represent a specific implementation.

Conditions for the lock

Conditional locking means that threads waiting for a condition to arrive are suspended until the condition is met. When the condition is met, some threads are allowed to apply for the lock, making the conditional lock much like a fence.

Java provides Condition as a method semantic template for conditional locking, with await() for waiting conditions and signal() for reaching conditions.

The same is true for conditional locking implemented with AQS. A conditional wait queue is maintained, all await() threads are queued as nodes, and some nodes are queued as CLH after the signal() arrives.

spinlocks

Spin-lock is in the unlocked state. Since CAS can guarantee the atomicity of a single variable, other critical sections that only depend on a single variable can be unlocked by CAS. It operates by repeating CAS until it succeeds, also known as spin.

Spin-locking is based on the assumption that threads in the critical section are short enough to be more efficient by wasting CPU time spinning until lock acquisition succeeds. This is because spin costs less CPU time than the performance cost of blocking and evoking the thread’s context switch in the scenario for which the spin lock is intended.

Segmented lock

Sometimes, it’s not necessary to have all shared resources in one place, just like going to a bank and choosing different counters. This is what segmented locking is all about: it stores shared resources in different areas and refines lock granularity so that competition for one resource does not affect another.

Take the ConccurrentHashMap implementation in JDK7 as an example, the data structure of type Segment is segmented, and each Segment is a ReentrantLock. In this way, different data is distributed in different areas, and the corresponding visitors to the corresponding location to compete.

conclusion

The article starts with what locks are needed, describes the implementation of synchronized and Lock, and takes a peek at the form in which locks exist in Java.

When considering the implementation of a lock, you need to consider pessimistic vs. optimistic, exclusive vs. shared, fair or not, reentrant or not, interruptible or not, and further, support for conditional locking semantics.

Synchronized improves the efficiency of the lock inflation process with bias locks -> lightweight locks -> heavyweight locks, as it is implemented at the bottom, leaving more room for imagination.

Lock semantic Lock, through AQS to solve the problem of who will be assigned to the Lock, can focus on its own way to add and unlock, meet and form the different characteristics of various locks. Once you have mastered AQS, you can use it to implement locks with business features.

Of course, you’ll also see a variety of names for locks, and you’ll need to consider whether the characteristics of the lock are one of the common features to consider, or the only unique features.

CAS can be found everywhere in the scheme to improve the efficiency of locking, so that no lock is the desired lock. Then, in the face of concurrency, can be from the need to lock -> whether CAS can solve -> can not block -> whether some feature of blocking lock, such a choice path to find a more suitable solution.

Above, wrong place, not stingy give instruction.

reference

Principle of Synchronized

Java CAS theory

JAVA in the CAS