Welcome to github.com/hsfxuebao/j… , hope to help you, if you feel ok, please click on the Star

1. Spin lock

SpinLock: Multiple threads, when a thread attempts to acquire a lock, if the lock is occupied, the current thread loops to check whether the lock has been released, while the thread is not asleep or suspended.

Code implementation

Here is a simple implementation of the spinlock:

package io.github.brightloong.concurrent.lock; import java.util.concurrent.atomic.AtomicReference; /** * public class SpinLock {//AtomicReference, CAS, Private AtomicReference<Thread> owner = new AtomicReference<Thread>(); public void lock() { Thread currentThread = Thread.currentThread(); // Null is the expected value, currentThread is the value to be set, if the current memory value is equal to the expected value of null, Replace currentThread while (! owner.compareAndSet(null, currentThread)) { } } public void unlock() { Thread currentThread = Thread.currentThread(); Owner.com pareAndSet(currentThread, null); owner.compareAndSet(currentThread, null); }}Copy the code
  • AtomicReference is used to store the current thread that acquired the lock, ensuring atomicity of the compareAndSet operation. For details about CAS, please refer to Java CAS Learning Record

disadvantages

  • An unfair lock does not guarantee the order in which the thread acquires the lock.
  • Ensure the data consistency of each CPU cache (L1, L2, L3, cross-CPU Socket, main memory), communication overhead is very high, especially in multi-processor systems.
  • There is no guarantee of fairness, no guarantee of waiting processes/threads acquiring locks in FIFO order.

2. CLH lock

CLH lock :Craig, Landin, and Hagersten (okay, those are the names of the three), which is a linked list-based spinlock that constantly polls the state of the precursor and finishes spinning if the precursor releases the lock.

implementation

CLH lock implementation is as follows:

  • Threads hold their own node variables, which have a locked property true (locks are required) and false (no locks required).
  • The thread holds a reference to the precursor’s Node, polls the precursor for locked properties, spins when it is true, or releases the lock when it is false.
  • Tail always points to the last thread added.

Operation principle

Its operation is illustrated by the following figure:

CLH

  1. When initialized, tail points to a node similar to head, and Node is false and preNode is null.
  2. When thread A enters, thread A holds A node whose locked properties are true and whose preNode points to the previous head node.
  3. When thread B enters, thread B holds nodes whose locked properties are true, thread B’s preNodes point to nodes in thread A, thread B’s nodes are locked to true, and thread A polls thread B’s nodes for locked states with true spin.
  4. When thread A finishes, it releases the lock (changing locked to false), and thread B polls thread A’s nodes to false, ending the spin.

Code implementation

CLH spinlock code implementation:

package io.github.brightloong.concurrent.lock; import java.util.concurrent.atomic.AtomicReference; Public class CLHLock {public class CLHLock <Node> tail = new AtomicReference<Node>(); ThreadLocal<Node> Node; ThreadLocal<Node> Node; ThreadLocal<Node> preNode = new ThreadLocal<Node>(); Public CLHLock() {// initialize node node = new ThreadLocal< node >() { The default is null @override protected Node initialValue() {return new Node(); }}; // Initialize tail to point to a node, similar to a head node, and the locked property is false tail.set(new node ()); } public void lock() {// Because of the initialValue() method in the constructor mentioned above, each thread will have a default value // and node locked properties are false. Mynode. locked = true; // Set myNode.locked = true; PreNode = tail.getAndSet(myNode); preNode = tail.getAndSet(myNode); This.prenode.set (preNode); While (prenode.locked) {}} public void unlock() {// Unlock is simple, set the nodes to false, Node.get ().locked = false; Node.set (prenode.get ())); } private class Node{private Boolean locked = false; }}Copy the code
  • Node has only one locked property, which is false by default
  • A ThreadLocal node is a node of the current thread. ThreadLocal implements thread isolation of variables
  • ThreadLocal preNode: a precursor node

advantages

  • It’s a fair lock, FIFO
  • The advantage of CLH queue locks is that the space complexity is low (if there are N threads, L locks, and each thread only acquires one lock at a time, then the storage space required is O (L+ N).

disadvantages

The SMP architecture

In this architecture, a computer consists of multiple cpus that share memory and other resources. All cpus have equal access to memory, I/O, and so on. Although multiple cpus can be used at the same time, they behave like a single CPU machine externally, and the operating system dramatically improves the data processing power of the entire system by distributing the task queues symmetrically across multiple cpus.

Everyday PC, notebook, mobile phone and some old servers all have this architecture. Its architecture is simple, but its expansion performance is very poor, as can be seen from Linux:

The ls/sys/devices/system/node / # if only see one node0 namely SMP architectureCopy the code

SMP architecture diagram

However, as the number of cpus increases, each CPU must access shared resources. In some scenarios, resources can only be accessed by a single thread, and in some scenarios, operations must be notified to other cpus. As a result, performance loss and resource waste result in system bottlenecks.

The NUMA architecture

That is, inconsistent storage access, which is a technical solution to solve the poor scalability of SMP. Each CPU module consists of multiple cpus and has independent local memory and I/O. Access between modules is completed through interconnected modules (similar to remote communication). The speed of accessing local resources is much higher than that of accessing external resources.

NUMA architecture diagram

NUMA architecture is equivalent to packing cpus of multiple SMP architectures, which can better solve the problem of SMP architecture expansion. However, in a single NUMA CPU module, although the number of cpus is controlled to reduce the performance loss in the operation of shared resources, the increase of CPU modules does not linearly increase system performance due to the interconnection of the modules.

MPP architecture

MPP provides another way to extend the system. It is a server system from the user’s point of view, where multiple SMP servers are connected through a network of nodes to work together to accomplish the same task. Its basic feature is that multiple SMP servers (each SMP server is called a node) are connected through the network of nodes. Each node only accesses its own local resources (memory, storage, etc.). It is a completely shared Nothing structure, so its expansion ability is the best. The current technology can connect 512 nodes with thousands of cpus. Experiments have shown that the best CPU utilization of SMP servers is between 2 and 4 cpus.

MPP architecture diagram

MMP can be regarded as a blade server. Each blade fan is an independent SMP architecture server. High-performance network devices interact with each blade fan to ensure data transmission performance between SMP servers. The MMP architecture relies on the processing capability of the management system to ensure communication.

The disadvantage of CLH locking is that it has poor performance in NUMA systems, where each thread has its own memory. If the memory location of the forward node is far away, the spin determines the locked domain of the forward node.

Another implementation

CLH use on the Internet there is a spin lock AtomicReferenceFieldUpdater version, here is the code posted, personally think that this version compared to more difficult to understand the implementation of the above, add some comments to help understand in the code.

package io.github.brightloong.concurrent.lock; import java.util.concurrent.atomic.AtomicReferenceFieldUpdater; Public class CLHLock2 {public static class CLHNode {private Boolean isLocked = true; } //tail indicates the last thread to be added. / / the AtomicReferenceFieldUpdater is based on the reflection of the utility, the specified class specifies the volatile field can be atomic updates. // Atomically update the tail field of the CLHLock2 class. private static final AtomicReferenceFieldUpdater<CLHLock2, CLHNode> UPDATER = AtomicReferenceFieldUpdater . newUpdater(CLHLock2.class, CLHNode .class , "tail" ); /** * pass node as an argument, similar to threadLocal, Public void lock(CLHNode currentThread) {public void lock(CLHNode currentThread) { CLHNode preNode = updater.getAndSet (this, currentThread); // If preNode is empty, no thread is currently acquiring the lock. if(preNode ! Public void unlock(CLHNode currentThread) {} public void unlock(CLHNode currentThread) { // return true if the currentThread is equal to the currentThread in tail, indicating that no thread is waiting for the lock. // If false is returned, other threads are waiting for the lock, and isLocked is updated to false if (! UPDATER .compareAndSet(this, currentThread, null)) { currentThread. isLocked = false ; // Change the state to allow subsequent threads to terminate the spin}}}Copy the code

The MCS lock

MCS locks address the drawbacks of CLH locks above. MCS comes from the initials of its inventors: John Mellor-Crummey and Michael Scott.

MCS Spinlock is an extensible, 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 of the end of the spin (unlike CLH Spinlock, it does not poll the precursor’s state, but is actively notified by the precursor). This greatly reduces the number of unnecessary processor cache synchronizations and reduces bus and memory overhead.

The principle of

  • Each thread holds its own Node, which has locked properties: true to wait for the lock, false to obtain the lock, and holds a reference to the next node (which may exist)
  • Threads are polling for the locked state of their nodes. True indicates that the lock is temporarily in use by another thread, waiting to acquire the lock, or spin.
  • When the thread releases the lock, it changes the locked properties of the nextNode to notify the heirs to end the spin.

Code implementation

package io.github.brightloong.concurrent.lock; import java.util.concurrent.atomic.AtomicReferenceFieldUpdater; Public class MCSLock {public static class MCSNode {// hold a reference to the successor MCSNode next; Boolean locked = true; } volatile MCSNode tail; / / points to the last one to apply for the lock MCSNode private static final AtomicReferenceFieldUpdater < MCSLock, MCSNode> UPDATER = AtomicReferenceFieldUpdater .newUpdater(MCSLock.class, MCSNode.class, "tail"); Public void lock(MCSNode currentThreadMcsNode) { MCSNode predecessor = Updater.getAndSet (this, currentThreadMcsNode); // If the predecessor is empty, no thread occupies the lock. Next = currentThreadMcsNode; null) {// Set the current node as the predecessor of the predecessor. / / step5 / / polling own isLocked attributes while (currentThreadMcsNode. Locked) {}}} public void unlock (MCSNode currentThreadMcsNode) { // Updater. get(this) obtains the node of the last thread to be added. // If the last node to be added is different from the current node (currentThreadMcsNode), there are other threads waiting for the lock. If (updater. get(this) == currentThreadMcsNode) {// If (updater. get(this) == currentThreadMcsNode) {// CurrentThreadMcsNode. Next, said there is no dye behind yourself if (currentThreadMcsNode. Next = = null) {/ / step2 / / set the tail is empty, if return true set success, If false is returned, the setting failed (other threads joined, If (UPDATER.compareAndSet(this, currentThreadMcsNode, Null)) {// //step3 // Set successfully return, no other threads wait for lock return; } else {// Another thread suddenly joined, need to check whether the successor has a value, because: Step4 after the execution, Step5 may not have performed while (currentThreadMcsNode. Next = = null) {}}} / / modify successors isLocked, notify the successors over the spin currentThreadMcsNode.next.locked = false; currentThreadMcsNode.next = null; // for GC } } }Copy the code

Similar to CLH locks, I use ThreadLocal to store nodes instead of passing arguments to a function to implement an MCS lock.

package io.github.brightloong.concurrent.lock; import java.util.concurrent.atomic.AtomicReferenceFieldUpdater; public class MCSLock2 { private class MCSNode { boolean locked = true; // MCSNode next; } volatile MCSNode tail; / / the AtomicReferenceFieldUpdater is to ensure that the tail atomic updates private static final AtomicReferenceFieldUpdater < MCSLock2, MCSNode> UPDATER = AtomicReferenceFieldUpdater .newUpdater(MCSLock2.class, MCSNode.class, "tail"); ThreadLocal<MCSNode> node = new ThreadLocal<MCSNode>(){@override protected MCSNode initialValue() { return new MCSNode(); }}; public void lock() { MCSNode myNode = node.get(); MCSNode preNode = UPDATER.getAndSet(this, myNode); // Similarly, preNode == null if (preNode! = null) { preNode.next = myNode; While (myNode.locked) {}}} public void unlock() {MCSNode myNode = node.get(); MCSNode next = myNode.next; If (next == null) {if (next == null) {if (next == null) {if (next == null) { If (UPDATER.compareAndSet(this, myNode, null)) {return; } else {// Wait for step1 to complete while (next == null) {}} next. Locked = false; next = null; //for CG } }Copy the code

reference

Spinlocks & CLH lock & MCS lock learning record Interview is forbid AQS – AQS overview www.cnblogs.com/tonylovett/… www.360doc.com/content/14/…

= = =