Details of spin locks for Java locks

As a tool for concurrent sharing of data and ensuring consistency, locks are implemented in the JAVA platform in various ways (such as synchronized, ReentrantLock, and so on). These locks have been written and provided to facilitate our development, but the specific nature and type of locks are rarely mentioned. This series of articles will examine common lock names and features in JAVA to answer your questions.

1. Spin lock

The spin lock is implemented by having the current thread execute continuously in the loop, and only enters the critical section when the loop's conditions are changed by other threads. The following

public class SpinLock {
  private AtomicReference<Thread> sign =new AtomicReference<>();
  public void lock(){

    Thread current = Thread.currentThread();

    while(!sign .compareAndSet(null, current)){

    }

  }
  public void unlock (){

    Thread current = Thread.currentThread();

    sign .compareAndSet(current, null);

  }

}

Using the CAS atomic operation, the lock function sets the owner to the current thread and predicts that the original value is null. The unlock function sets the owner to null and predicts the value to be the current thread.

When a second thread calls the lock operation, the owner value is not null, causing the loop to continue to execute until the first thread calls the unlock function and sets the owner to null before the second thread enters the critical section.

Since the spin lock simply keeps the current thread executing the loop body without changing the thread state, it responds faster. However, when the number of threads increases, the performance decreases significantly, because each thread needs to execute and consumes CPU time. If the thread is not heavily contested and the lock is held for a period of time. Suitable for using spin lock.

Note: this example is a non-fair lock. The order of acquiring the lock will not follow the order of entering the lock.

2. Other types of spin locks

As mentioned above, there are three other common forms of spin lock :TicketLock, CLHlock, and MCSlock

The Ticket lock mainly solves the problem of access order. The main problem is on the multi-core CPU:

package com.alipay.titan.dcc.dal.entity;
import java.util.concurrent.atomic.AtomicInteger;
public class TicketLock {

    private AtomicInteger                     serviceNum = new AtomicInteger();

    private AtomicInteger                     ticketNum  = new AtomicInteger();

    private static final ThreadLocal<Integer> LOCAL      = new ThreadLocal<Integer>();
    public void lock() {

        int myticket = ticketNum.getAndIncrement();

        LOCAL.set(myticket);

        while (myticket != serviceNum.get()) {

        }
    }
    public void unlock() {

        int myticket = LOCAL.get();

        serviceNum.compareAndSet(myticket, myticket + 1);

    }

}

Each time a serviceNum service number is queried, affecting performance (it must be read from main memory and prevented from being modified by other cpus).

CLHLock and MCSLock are two similar types of fair locks, sorted in the form of a linked list.

import java.util.concurrent.atomic.AtomicReferenceFieldUpdater;
public class CLHLock {

    public static class CLHNode {

        private volatile boolean isLocked = true;

    }
    @SuppressWarnings("unused")

    private volatile CLHNode                                           tail;

    private static final ThreadLocal<CLHNode>                          LOCAL   = new ThreadLocal<CLHNode>();

    private static final AtomicReferenceFieldUpdater<CLHLock, CLHNode> UPDATER = AtomicReferenceFieldUpdater.newUpdater(CLHLock.class,

                                                                                   CLHNode.class, "tail");
    public void lock() {

        CLHNode node = new CLHNode();

        LOCAL.set(node);

        CLHNode preNode = UPDATER.getAndSet(this, node);

        if (preNode != null) {

            while (preNode.isLocked) {

            }

            preNode = null;

            LOCAL.set(node);

        }

    }
    public void unlock() {

        CLHNode node = LOCAL.get();

        if (!UPDATER.compareAndSet(this, node, null)) {

            node.isLocked = false;

        }

        node = null;

    }

}

CLHlock is constantly querying precursor variables, making it unsuitable for use in NUMA architecture (where each thread is distributed in a different physical memory area)

MCSLock loops through the nodes of the local variables. There is no CLHlock problem.

import java.util.concurrent.atomic.AtomicReferenceFieldUpdater;
public class MCSLock {

    public static class MCSNode {

        volatile MCSNode next;

        volatile boolean isLocked = true;

    }
    private static final ThreadLocal<MCSNode>                          NODE    = new ThreadLocal<MCSNode>();

    @SuppressWarnings("unused")

    private volatile MCSNode                                           queue;

    private static final AtomicReferenceFieldUpdater<MCSLock, MCSNode> UPDATER = AtomicReferenceFieldUpdater.newUpdater(MCSLock.class,

                                                                                   MCSNode.class, "queue");
    public void lock() {

        MCSNode currentNode = new MCSNode();

        NODE.set(currentNode);

        MCSNode preNode = UPDATER.getAndSet(this, currentNode);

        if (preNode != null) {

            preNode.next = currentNode;

            while (currentNode.isLocked) {
            }

        }

    }
    public void unlock() {

        MCSNode currentNode = NODE.get();

        if (currentNode.next == null) {

            if (UPDATER.compareAndSet(this, currentNode, null)) {
            } else {

                while (currentNode.next == null) {

                }

            }

        } else {

            currentNode.next.isLocked = false;

            currentNode.next = null;

        }

    }

}

In terms of code, CLH is simpler than MCS,

The CLH queue is an implicit queue with no real successor attributes.

The queue of MCS is an explicit queue with real successor node attributes.

The lock that JUC ReentrantLock USES internally by default is a CLH lock (with a lot of improvements, replacing spinlocks with blocking locks, and so on).

(full text)