Java lock classification, principle and example

Java lock classification

Java parallel programming often hears the terms biased lock, spin lock, optimistic lock, and so on, but what are the relationships between these locks, and how exactly are locks classified? According to the classification rules of locks, it can be divided into the following seven categories. Segment lock is a lock design, not a specific lock.

• Bias lock/lightweight lock/heavyweight lock
• Reentrant lock/non-reentrant lock
• Shared/exclusive lock
• Fair lock/unfair lock
• Pessimistic lock/optimistic lock
• Spinlocks/non-spinlocks
• Interruptible locks/non-interruptible locks
• Segmented lock

Here we introduce the principles and corresponding examples of each type of lock.

The principle of Java lock

1. Bias lock/lightweight lock/heavyweight lock

Java1.6 was based on heavyweight locks. Java1.6 has since optimized synchronized, introducing biased locks, lightweight locks, and upgrade mechanisms to reduce the performance cost of acquiring and releasing locks. Before introducing Java locks, let’s take a look at Java’s object structure. In the HotSpot virtual machine, the layout of objects stored in memory can be divided into three areas: object headers, Instance Data, and alignment Padding. MarkWord is a part of the object header, which is mainly used to store the runtime data of the object itself, such as HashCode, GC generation age, lock status flag, lock held by the thread, biased thread ID, biased timestamp, etc. The length of this data is 32 – and 64-bit, respectively, on a 32-bit or 64-bit VM (with compression pointer disabled). The last two bits of MarkWord are lock-state flags, and the state of the object determines what MarkWord stores.

• Biased locking: is an optimization of locks introduced in Java1.6. When only one thread executes the synchronization code block, the CAS operation is used to write the ID of the thread that acquired the lock/lock level in the header information of the object.
• Lightweight lock: It refers to that when a biased lock is accessed by another thread, the biased lock will be upgraded to lightweight lock. In many cases, the code in synchronized is executed alternately by multiple threads rather than at the same time, that is, there is no actual competition or only a short lock competition, which is solved by CAS operation. Other threads will attempt to acquire the lock in the form of spin without blocking, improving performance.
• Heavyweight lock: it is a mutex. It is implemented using the synchronization mechanism of the operating system and costs a lot. When multiple threads compete for a long time, the lightweight lock cannot meet the demand, and the lock will expand to the heavyweight lock. Heavyweight locks block other threads that can’t acquire the lock.

Lock upgrade: no lock -> bias lock -> Lightweight lock -> heavyweight lock

To sum up, biased lock has the best performance, that is, only one thread executes synchronous code blocks. When there are multiple threads executing alternately, lightweight lock uses CAS operation and thread spin to acquire the lock, and the performance is medium. When there is actual competition among multiple threads, heavyweight lock will block the thread that cannot obtain the lock, and the performance is worst.

2. Reentrant lock/non-reentrant lock

In the same thread, if the outer method acquires the lock automatically when entering the inner method, it is a reentrant lock; if the inner method needs to re-acquire the lock, it is a non-reentrant lock. When methodA() is executed, the thread acquires the object lock. When methodB is executed, the lock does not need to be reacquired. One benefit of reentrant locks is that deadlocks are somewhat avoided.

Synchronized void methodA() {// omit synchronization..... methodB(); } synchronized void methodB() {// omit...... }Copy the code

3. Shared lock/exclusive lock

• Shared lock: The same lock can be acquired by multiple threads at the same time.
• Exclusive lock: a lock can only be acquired by one thread at a time.

Read-write locks are good examples of shared and exclusive locks. Read locks are shared locks that guarantee concurrent read. Write locks are exclusive locks that can only be acquired by one thread at a time.

Shared lock and exclusive lock is realized through AQS, AQS provides the method of exclusive lock and shared lock must be realized, with exclusive lock function subclass, it must realize tryAcquire, tryRelease, isHeldExclusively, etc. Subclasses of Shared locks must implement methods such as tryAcquireShared and tryReleaseShared. Methods with the Shared suffix support Shared lock semantics.

• AQS(AbstractQueuedSynchronizer):Is Java. Util. Concurrent. The locks package under the basis of the abstract class, provides the basic framework of Java lock. Here are the key data structures in AQS.
  • A shared state is maintained in AQSstate. 1) statevolatileThe modifier ensures memory visibility between threads. 2)getState() and setState() methods are adoptedfinalModify, disallow AQS subclass rewriting; 3)compareAndSetState() method adopts CAS algorithm with optimistic lock idea and uses final modification to forbid subclass rewriting.

    // source code private volatile int state; protected final int getState() { return state; } protected final void setState(int newState) { state = newState; } protected final boolean compareAndSetState(int expect, int update) { // See below for intrinsics setup to support this return unsafe.compareAndSwapInt(this, stateOffset, expect, update); }Copy the code

  • CLH queues (Craig, Landin, and Hagersten Locks)Is the bidirectional queue of FIFO in AQS, which internally records the first and last elements of the queue through node head and tail, and the queue element type isNode. AQS use CLH queues to complete synchronization statestateManagement. When the current thread fails to obtain the synchronization state, AQS will construct a Node (Node) of the thread waiting state and add it to the CLH synchronization queue. At the same time, IT will block the current thread. When the synchronization state is released, the first Node will wake up (fair lock) and make it try to obtain the synchronization state again.
    • Tail points to the new node, the prev of the new node points to the last node, and the next of the last node points to the current node.
    • Dequeue: After the thread of the node releases the synchronization state, it wakes up its successor node (next), which sets itself up as the lead node when the synchronization state is successfully obtained.
  • NodeIs a static inner class of AQS that represents a thread. It holds thread references, waitStatus, prev, next, and nextWaiter of the condition queue.

    // AQS static final class Node {...... /** thread status: * SIGNAL- indicates that subsequent nodes need to wake up. Threads on subsequent nodes of the current node are blocked by park, and the current node is unblocked by unpark before releasing or canceling. * CANCELLED- CANCELLED status. The thread of the current node was cancelled due to timeout or interrupt. * CONDITION- Wait state. The current node is in the condition queue; PROPAGATE- PROPAGATE state, release of shared lock. This state is used to optimize lock contention, so that threads in the queue are awakened one by one. * 0- Indicates the initial state of the node. */ volatile int waitStatus; volatile Node prev; volatile Node next; volatile Thread thread; Node nextWaiter; . }Copy the code

  • ConditionObject: Is an internal class of AQS that implements the Condition interface and supports Condition variables for AQS. Synchronized control synchronizes the wait(), notify(), and notifyAll() methods of Object to realize the wait/notification mode. And the Lock? Condition interface is provided to implement wait/notification mechanism with await(), signal(), signalAll() and other methods.

  public class ConditionObject implements Condition {
   /** First node of condition queue. */
   private transient Node firstWaiter;
   /** Last node of condition queue. */
   private transient Node lastWaiter;
  }
  Copy the code

1. The Condition signal method does not mean that the thread can execute immediately. The signal method is used to remove the node from the wait queue and then join the synchronization queue. The thread is always executed based on the synchronization state (i.e. whether the thread holds the lock or not).
2. ConditionObject each maintains a separate wait queue. The CLH queue maintained by AQS is a synchronization queue. They are all nodes of the same type.

4. Fair/unfair lock

• Fair lock: Multiple threads acquire locks in the order in which they are applied. This results in poor performance and a lot of time spent on thread scheduling.
• Unfair lock: Multiple threads obtain locks in a different order than the one that applied for them earlier. Possibly, it could lead to priority reversals or starvation. The advantage is that the response time is improved, and instead of spending a lot of time on thread scheduling, you spend executing code.

How to implement fair lock:

ReentrantLock lock=new ReentrantLock(true); //true: obtains a fair lockCopy the code

The implementation of an unfair lock is as follows:

ReentrantLock lock=new ReentrantLock(); // Default is unfair lock ReentrantLock lock=new ReentrantLock(false);Copy the code

ReentrantLock source code: FairSync and NonfairSync are two static inner classes in the ReentrantLock class that inherit from Sync. Sync is also a static inner class in the ReentrantLock class that inherits from the AQS in the previous section.

// Synchronizer, used to implement all synchronization mechanisms, such as fair/unfair private final Sync Sync; abstract static class Sync extends AbstractQueuedSynchronizer { /** * Performs non-fair tryLock. tryAcquire is implemented in * subclasses, but both need nonfair try for trylock method. */ @ReservedStackAccess final boolean nonfairTryAcquire(int acquires) { final Thread current = Thread.currentThread(); Int c = getState(); // Get the lock status, SetExclusiveOwnerThread (current); if (c == 0) {if (compareAndSetState(0, acquires)) {setExclusiveOwnerThread(current); // Set the lock holder to the current thread. } else if (current == getExclusiveOwnerThread()) {int nexTC = c + acquires; if (nextc < 0) // overflow throw new Error("Maximum lock count exceeded"); setState(nextc); return true; } return false; }... } public ReentrantLock(boolean fair) { sync = fair ? new FairSync() : new NonfairSync(); } static final class NonfairSync extends Sync {private static Final Long serialVersionUID = 7316153563782823691L; protected final boolean tryAcquire(int acquires) { return nonfairTryAcquire(acquires); Static final class FairSync extends Sync {private static Final Long serialVersionUID = -3000897897090466540L; /** * Fair version of tryAcquire. Don't grant access unless * recursive call or no waiters or is first. */ @ReservedStackAccess protected final boolean tryAcquire(int acquires) { final Thread current = Thread.currentThread(); Int c = getState(); If (c == 0) {if (! Hasqueuedtoraise () && // Determine the existence of a thread that has waited longer, does not return false (the current thread has acquired the lock, determines whether there are pioneer nodes in the current queue, CompareAndSetState (0, acquires)) {setExclusiveOwnerThread(current); // Set the lock holder to the current thread. } else if (current == getExclusiveOwnerThread()) {int nexTC = c + acquires; if (nextc < 0) throw new Error("Maximum lock count exceeded"); setState(nextc); return true; } return false; }}Copy the code

5. Pessimistic lock/optimistic lock

• Pessimistic lock: The belief that concurrent operations on the same data will be modified, and even if no modification is made, the modification will be considered. Therefore, for concurrent operations on the same data, pessimistic locking takes the form of locking. Suitable for scenarios with many write operations.
• Optimistic lock: It considers that concurrent operations on the same data will not be modified. When updating data, the data will be updated on a trial basis. Usually, CAS spin is used to update data. Optimistically, concurrency without locking is fine. Suitable for scenarios with many read operations.

Pessimistic locks are implemented using various locks in Java; Implementation of optimistic lock: 1)CAS algorithm; 2) Version number mechanism.

• CAS algorithm (compare and swap) :Is a non-blocking lock-free algorithm that copies a copy of a variable from main memory for each thread to its runtime environment when the thread is started.The CAS algorithm contains three parameters (V,E, and N), where V represents the variable to be updated (that is, the value copied from main memory),E represents the expected value, and N represents the new value. If the value of memory location V is equal to the expected original value E, the processor automatically updates the value of memory location to the new value N, otherwise the processor does nothing.When multiple threads try to update the same variable using CAS at the same time, only one thread can update the value of the variable, and all other threads fail. The thread that fails is not suspended, but is informed that it has lost the race and can try again. The Java1.5 java.util.Concurrent package is built on CAS, CAS changes the state variable in the Lock implementation, and implementation classes in the Atomic package are almost always implemented using CAS.
  • Disadvantages: 1) Too long cycle time; 2) Only one shared variable atomic operation can be guaranteed; 3) THERE will be ABA problems.
  • Advantages: CPU instruction level operation, only one atomic operation, so very fast. And CAS avoids the problem of asking the operating system to determine the lock, instead taking care of it directly within the CPU.
• Version number mechanism: Generally, a version number field is added to the data table to indicate the number of times the data has been modified. When the data has been modified, the version value will be increased by one. When thread A wants to update the data value, it reads the version value as well as the data. When submitting the update, it updates the version value only when the version value it just read is the same as the version value in the current database. Otherwise, it retries the update operation until the update succeeds.

6. Spinlocks/non-spinlocks

Spin locking means that the thread attempting to acquire the lock does not immediately block or release the CPU, but instead attempts to acquire the lock in a circular manner, reducing the consumption of thread context switching. The disadvantage is that the loop consumes CPU. If you can’t get the lock, you just give up, join the waiting queue, get blocked, etc.

Spin locks are implemented by having the current thread execute continuously in the loop body, and then enter the critical section when the loop condition is changed by other threads. The current thread executes the loop body continuously without changing thread state, so it responds faster. However, when the number of threads increases, performance degrades significantly and each thread needs to execute, consuming CPU time. If threads are not in contention and the lock is held for a short time, use spin locks.

7. Breakable/non-breakable locks

If thread A is executing the code in the lock, thread B is waiting to acquire the object lock, and if the waiting time is too long to allow THREAD B to do something else, thread B can interrupt it or another thread can interrupt it.

In Java, the synchronized keyword represents an unbreakable lock, and once a thread has acquired the lock, it can’t perform any other logical processing until it has acquired it. A Lock is typically an interruptible Lock. For example, if the lockInterruptibly method is used to acquire the Lock and you do not want to acquire it, you can do something else after the interrupt without waiting until the Lock is acquired. Already realized the Lock interface, realize lockInterruptibly method source code calls the sync. AcquireInterruptibly, the method for AQS.

public void lockInterruptibly() throws InterruptedException {
    sync.acquireInterruptibly(1);
}
Copy the code

8. Subsection locking

Segmented locking is a lock design that in ConcurrentHashMap is implemented concurrently through smaller granularity segmented locking to improve the efficiency of concurrent operations. Let’s take a look at the source code for HashMap, Hastable, and ConcurrentHashMap to understand why segwise locks occur.

1) Thread unsafe HashMap: In multi-threaded scenarios, data inconsistency or an infinite loop can occur when using the HashMap put operation. Why does this happen?

• The PUT operation causes data inconsistency

For example, if there are two threads A and B, thread A wants to put A key-value pair into the HashMap. Thread A first calculates the position of the bucket to insert the record, and then obtains the head node of the list in the bucket. At this time, thread A runs out of time slice, while thread B is scheduled to execute, and thread B successfully puts the record into the bucket. Assume that thread A calculated index of barrels and thread B calculated bucket index is the same, when A thread B success after insertion, thread A was scheduled to run again, it is still holding the expired head, continue to implement the put operation, that covered the thread B are inserted record, caused the data inconsistent behavior.

• The PUT operation causes an infinite loop

Java8 has optimized the HashMap. When the list length is larger than 8, it is converted to the storage structure of red-black tree, resize optimization, etc., but it is still thread unsafe. In order to simplify the analysis, the HashMap source code of Java7 is used for thread unsafe analysis. The implementation of a HashMap uses an array of nodes with a linked list inside each entry. Because a HashMap uses the hashCode of the key to find the storage location **(h&(Length-1)), different keys may have the same hashCode, and then hash conflicts occur. Also called hash collision, to resolve hash collisions, there are open address methods and chained address methods. HashMap uses the chained address method **, that is, to store entries with the same hash value in the same array entry. An array entry can be regarded as a bucket, which contains the same entry key hashCode.

transient Node<K,V>[] table; // The variable is transient, the variable is no longer part of the object persistence, and the variable content cannot be accessed after serialization at...... Static class Node<K,V> implements map. Entry<K,V> {final int hash; static class Node<K,V> implements map. Entry<K,V> {final int hash; final K key; V value; Node<K,V> next; . }Copy the code

The initial length of the HashMap array is 16, and the loadFact is 0.75. When records exceed the threshold and hash conflicts occur, the HashMap will expand, doubling its original size each time, until it cannot resize beyond the set maximum value. After expansion, the array length will change and the storage location will be recalculated. Index = h&(Length-1) may also change. First, let’s look at the transfer method.

void transfer(Entry[] newTable, boolean rehash) { int newCapacity = newTable.length; for (Entry<K,V> e : table) { while(null ! = e) { Entry<K,V> next = e.next; // 1 if (rehash) { e.hash = null == e.key ? 0 : hash(e.key); } int i = indexFor(e.hash, newCapacity); e.next = newTable[i]; // 2 newTable[i] = e; // 3 e = next; // 4}}}Copy the code

Suppose you have a length of 2 a HashMap, [3, a] – > [7, b] – > [5] c in the location of the index to 1 \ color {red} {[3, a] – > [7, b] – > [5] c in the location of the index to 1} [3, a] – > [7, b] – > [5] c in the location of the index to 1, Two threads A and B respectively perform put operation on the HashMap. First, HashMap expansion is performed. When the thread executes to position 1 in the transfer method, thread A’s time slice runs out. E = [3, a], next = \ [7, b] color {red} {e = [3, a], next = [7] b} e = [3, a], next = b [7]. Color {red}{[5,c] = 1; color{red}{[5,c] = 1; color{red} = 1; [7, b] – > [a] 3, in the place of the index 3} [5] c in the location of the index to 1, b [7] – > [a] 3, in the index 3 position. At this point, thread A is scheduled again to continue execution. After thread A first migrates [3, A] to A new array and processes [7,b], thread B processes next of [7, B]. After thread B expands, thread B has pointed next of [7, B] to [3, A], [3, A] and [7,b] form A circular linked list. Color {red}{[3,a] and [7,b] form a circular linked list, so that when the data is obtained to iterate the linked list formed an infinite loop}[3,a] and [7,b] form a circular linked list, so that when the data is obtained to iterate the linked list formed an infinite loop. The reason for the dead-loop is that in expansion, the head insertion method is used in steps 2, 3 and 4 of the Transfer method, which will cause the inversion of the linked list and further form the circular linked list.

2) Thread-safe Hashtable with low efficiency: Hashtable uses synchronized to ensure thread safety, but the efficiency of Hashtable is very low when the thread competition is fierce. When one thread accesses the synchronization method of the Hashtable, other threads may enter a blocking or polling state while accessing the synchronization method of the Hashtable. You can neither add elements using the PUT method nor get them using the GET method.

ConcurrentHashMap: ConcurrentHashMap: ConcurrentHashMap: ConcurrentHashMap: ConcurrentHashMap: ConcurrentHashMap: ConcurrentHashMap: Each element in the array is a linked list; It is also a ReentrantLock (the Segment inherits ReentrantLock). Segment locking is designed to refine the granularity of the lock. When an operation does not need to update the entire array, only one segment of the array is locked.

Static class Segment<K,V> extends ReentrantLock implements Serializable {}Copy the code

When you put an element, instead of locking the entire HashMap, you use HashCode to determine the segment position of the element, and then lock the segment, so that when you multithreaded put operations, as long as they are not placed in a segment, you can achieve true parallel inserts. However, in order to obtain the global information of the HashMap, we need to obtain all the segment locks to obtain the statistics.

Java lock instance

• Synchronized: an unfair, pessimistic, exclusive, mutually exclusive, reentrant, heavyweight lock;
• ReentrantLock: a pessimistic, exclusive, mutually exclusive, reentrant, heavyweight lock that is not fair by default but is fair by implementation.
• ReentrantReadWriteLock is an interface that implements ReadWriteLock. ReadLock () is used to obtain read locks and writeLock() is used to obtain write locks.
• Semaphore: is a shared lock. Semaphore is a counting Semaphore used to manage a group of resources with an AQS-based sharing mode internally. It is equivalent to assigning a quantity to a thread to control the number of threads allowed to be active.