This is the 21st day of my participation in the August More Text Challenge

background

SMP(Symmetric Multi-Processor)

Symmetric multiprocessor architecture is a parallel technology which is widely used compared with asymmetric multiprocessor technology.

  • In this architecture, a computer is made up of multiple cpus that share memory and other resources, and all cpus have equal access to memory, I/O, and external interrupts.
  • While using multiple cpus at the same time, they behave like a single machine from an administrative standpoint.
  • The operating system distributes the task queue symmetrically over multiple cpus, which greatly improves the data processing capability of the entire system.
  • However, as the number of cpus increases, each CPU must access the same memory resources. Sharing resources may become a system bottleneck, resulting in CPU resource waste.

NUMA(Non-Uniform Memory Access)

Inconsistent storage access: cpus are divided into CPU modules. Each CPU module consists of multiple cpus and has independent local memory and I/O slots. Modules can access each other through interconnected modules.

  • Access to local memory (the memory of this CPU module) will be much faster than access to remote memory (the memory of other CPU modules), and this is where inconsistent memory access comes in.

  • NUMA is a good solution to the SMP scaling problem. When the number of cpus increases, the system performance does not increase linearly because the latency of accessing remote memory is much greater than that of accessing local memory.

CLH lock

CLH is a high-performance, fair spinlock based on one-way linked lists. The thread applying for the lock spins through the variables of the precursor node. After the front node is unlocked, the current node finishes spinning and locks.

  • CLH has more advantages in SMP architecture.
  • In NUMA architectures, if the current node and the precursor node are not in the same CPU module, there is additional overhead across CPU modules, while MCS locks are more suitable for NUMA architectures.

Locking logic

  1. Get the lock node of the current thread. If it is empty, initialize it.

  2. The synchronous method obtains the tail node of the linked list and sets the current node as the tail node. At this time, the original tail node is the front node of the current node.

  3. If the tail node is empty, the current node is the first node and the lock succeeds.

  4. If the tail node is not empty, it spins based on the lock value of the front node (locked==true) until the lock value of the front node becomes false.

Unlock the logic

  1. Get the lock node corresponding to the current thread. If the node is empty or the lock value is false, it does not need to unlock and returns directly.

  2. If the synchronization method fails, the current node is not the last node. In this case, set locked=false to unlock the current node. If the current node is the tail node, you do not need to set this parameter.


public class CLHLock {
    private final AtomicReference<Node> tail;
    private final ThreadLocal<Node> myNode;
    private final ThreadLocal<Node> myPred;
 
    public CLHLock(a) {
        tail = new AtomicReference<>(new Node());
        myNode = ThreadLocal.withInitial(() -> new Node());
        myPred = ThreadLocal.withInitial(() -> null);
    }
 
    public void lock(a){
        Node node = myNode.get();
        node.locked = true;
        Node pred = tail.getAndSet(node);
        myPred.set(pred);
        while (pred.locked){}
    }
 
    public void unLock(a){
        Node node = myNode.get();
        node.locked=false;
        myNode.set(myPred.get());
    }
 
 
    static class Node {
        volatile boolean locked = false; }}Copy the code

The MCS lock

The main difference between MSC and CLH is not that the lists are explicit or implicit, but that the rules for thread spin are different :CLH spins wait in locked domains of its nodes, while MCS spins wait in locked domains of its nodes. Because of this, it solves the problem of CLH fetching locked domain state memory too far in NUMA system architectures.

Specific implementation rules of MCS lock:

  • A. When the queue is initialized, there are no nodes. Tail =null

  • B. Thread A wants to acquire the lock and places itself at the end of the queue. Since it is the first node, its locked domain is false

  • C. thread B and c have to join the queue, a – > next = B, B – > next = c, B and c without acquiring a lock, in a wait state, so locked domain to true, the tail pointer to the thread c corresponding nodes

  • D. After thread A releases the lock, thread A follows its next pointer to thread B and sets B’s locked field to false. This action triggers thread B to acquire the lock.

public class MCSLock {
 
    private final AtomicReference<Node> tail;
 
    private final ThreadLocal<Node> myNode;
 
    public MCSLock(a) {
        tail = new AtomicReference<>();
        myNode = ThreadLocal.withInitial(() -> new Node());
    }
 
    public void lock(a) {
 
        Node node = myNode.get();
        Node pred = tail.getAndSet(node);
        if(pred ! =null) {
            node.locked = true;
            pred.next = node;
            while (node.locked) {
            }
        }
 
    }
 
    public void unLock(a) {
        Node node = myNode.get();
        if (node.next == null) {
            if (tail.compareAndSet(node, null)) {
                return;
            }
 
            while (node.next == null) {
            }
        }
        node.next.locked = false;
        node.next = null;
    }
 
    class Node {
        volatile boolean locked = false;
        Node next = null;
    }
 
    public static void main(String[] args) {
 
        MCSLock lock = new MCSLock();
 
        Runnable task = new Runnable() {
            private int a;
 
            @Override
            public void run(a) {
                lock.lock();
                for (int i = 0; i < 10; i++) {
                    a++;
                    try {
                        Thread.sleep(100);
                    } catch(InterruptedException e) { e.printStackTrace(); } } System.out.println(a); lock.unLock(); }};new Thread(task).start();
        new Thread(task).start();
        new Thread(task).start();
        newThread(task).start(); }}Copy the code