CLH (Craig, Landin, and Hagersten) lock

Giriş

Bir çeşit spin lock. Açıklaması şöyle. java.util.concurrent.locks.AbstractQueuedSynchronizer.Node buna benzer bir mantık kullanıyor

The CLH lock is a scalable, high-performance, and fair spin lock based on a linked list. The application thread only spins on local variables. It always reads the state of the pre-node. If it finds that the pre-node releases the lock, it ends from spin

CLH Lock'a gelmeden Önce

1. Test And Set  Lock

Şöyle yaparız

public class TASLock implements Lock {
 AtomicBoolean state = new AtomicBoolean(false);
 public void lock() {
   while (state.getAndSet()) {}
 }
 public void unlock() {
   state.set(false);
 }
}

2. Test&Test&Set Lock

Şöyle yaparız

public class TTASLock implements Lock {
  AtomicBoolean state = new AtomicBoolean(false);
  public void lock() {
    while (true) {
      while(state.get()) {}
      if(!state.getAndSet())
        return;
     }
 }
 public void unlock() {
   state.set(false);
 }
}

Kuyruk Kullanan Kilitler

Bu kilitler FIFO fairness, fast lock release, low contention gibi iyi özellikler sunuyorlar, ancak abort işlemini iyi desteklemiyorlar

3. Anderson queue lock (ALock)

Açıklaması şöyle

ALock: Acquiring the Lock

• To acquire the lock, each thread atomically increments the tail field

• If the flag is true, the lock is acquired

• Otherwise, spin until the flag is true

ALock: Contention

• If another thread wants to acquire the lock, it applies get&increment

• The thread spins because the flag is false

ALock: Releasing the Lock

• The first thread releases the lock by setting the next slot to true

• The second thread notices the change and gets the lock

Örnek

Şöyle yaparız. Burada atomic olan sadece AtomicInteger yani benim kuyruktaki yerimi gösteren sayaç. 

public class Alock implements Lock {
  //One flag per thread 
  boolean[] flags = {true,false,...,false};
  AtomicInteger next = new AtomicInteger(0);
  //Thread-local variable
  ThreadLocal<Integer> mySlot;

  public void lock() {
    //Take the next slot   
    mySlot = next.getAndIncrement();
    while (!flags[mySlot % n]) {}
    flags[mySlot % n] = false;
 }
 public void unlock() {
   //Tell next thread to go
   flags[(mySlot+1) % n] = true;
 }
}

CLH Lock Gerçekleştirimi

Açıklaması şöyle. Burada Anderson kilidinden farklı olarak kilitlemek için benden önceki düğümün bayrağı üzerinde bekliyorum. 

The threads could update own flag and spin on their predecessor’s flag

This is basically what the CLH lock does, but using a linked list instead of an array

Örnek

Şöyle yaparız

static class CLHLock implements Lock {
    AtomicReference<QNode> tail;
    ThreadLocal<QNode> myNode, myPred;

  public CLHLock() {
    tail = new AtomicReference<QNode>(new QNode());

    this.myNode = new ThreadLocal<QNode>() {
      protected QNode initialValue() {
        return new QNode();
      }
    };

    this.myPred = new ThreadLocal<QNode>() {
      protected QNode initialValue() {
        return null;
      }
    };
  }

  public void lock() {
    QNode qnode = this.myNode.get();
    qnode.locked.set(true);  

    QNode pred = this.tail.getAndSet(qnode); //Add myself to tail. Tail is AtomicRef.
    myPred.set(pred); //Save my predecessor
    while (pred.locked.get()) {} //Wait if my predecessor is locked
  }

  public void unlock() {
    QNode qnode = this.myNode.get(); 
    qnode.locked.set(false); //Tell next thread to go      
    this.myNode.set(this.myPred.get()); 
  }

  static class QNode {  
    public AtomicBoolean locked = new AtomicBoolean(false);
  }
}