幾種鎖算法的實現

Abstract

4種Lock的實現：

• TASLock
• TTASLock
• CLHLock
• MCSLock

TASLock

每一個Lock帶有一個狀態位，lock()與unlock()操作原子的改變狀態位。false時可進入，true時spin。

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

defect：

• 在鎖被其他線程持有的情況下， while(state.getAndSet(true)) 會不停的將

  state從true改為true

TTASLock

TASLock算法的改進。

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

1. while (state.get()){} 是一個改進，效果是先看一眼lock的狀態，當lock是false時，
   再真正的執行 state.getAndSet(true) 。
2. 當state.getAndSet(true) 的return為false時，說明之前的確是false，于是獲得鎖，return。
   否則回到while(true),再次嘗試獲得鎖。

defect：

• 在unlock時，state.set(false)還是會帶來大量的cache miss。
• cache miss VS cache hit

CLHLock

void initCLHlock()
{
  q.locked = FALSE;
  tail = &q;
}
void lock()
{
  QNode* qnode = (QNode*)pthread_getspecific(myNode);
  qnode->locked = TRUE;
  QNode* pred = getAndSet(qnode);//原子的得到隊尾，并將qnode設為新的隊尾。
  pthread_setspecific(myPred, pred);
  while(pred->locked)
  {
  }
}
void unlock()
{
  QNode* qnode = (QNode*)pthread_getspecific(myNode);
  qnode->locked = FALSE;
  QNode* pred = (QNode*)pthread_getspecific(myPred);
  pthread_setspecific(myNode, pred);//unlock時必須將myNode指向前面的Node
}

NOTE :

• unlock時必須將myNode指向前面的Node！
  > 后果 ：如果Thread A unlock()后，緊接著又進入
  隊尾， A的locked會再次被置為TRUE， Thread B還在看著Thread A 的locked字段，于是產生
  deadlock。
• 初始時教室里面有一個空凳子， 每個學生來到門口排隊時都自己帶著一個凳子。

MCSLock

public class MCSLock implements Lock
{
  AtomicReference<QNode> tail;
  ThreadLocal<QNode> myNode;
  public MCSLock()
  {
    queue = new AtomicReference<QNode>(null);
    myNode = new ThreadLocal<QNode>()
    {
      protected QNode initialValue()
      {
        return new QNode();
      }
    };
  }
  ...
  class QNode
  {
    boolean locked = false;
    QNode next = null;//與CLHLock相比，多了這個真正的next
  }
}   
public void lock()
{
  QNode qnode = myNode.get();
  QNode pred = tail.getAndSet(qnode);
  if (pred != null)
  {
    qnode.locked = true;
    pred.next = qnode;
    //wait until predecessor gives up the lock
    while(qnode.locked){}//將自己設為true然后spin，看似deadlock
  }
}
public void unlock()
{
  QNode qnode = myNode.get();
  if (qnode.next == null)        //后面沒有等待線程的情況
  {//------there is a gap!!!!
    if (tail.compareAndSet(qnode, null))
      return;                //真的沒有等待線程，則直接返回，不需要通知
    //wait until predecessor fills in its next field
    while (qnode.next == null){}
  }
  //右面有等待線程，則通知后面的線程
  qnode.next.locked = false;
  qnode.next = null;
}

NOTE:

• unlock()要要特別的注意。

Summary

• CLHLock的思想是當前線程在前一個線程的node上spin，每個線程unlock時修改自身的標記。
  在共享總線結構下性能可以，無法應對分布式。
• MCSLock 用于解決分布式并行的問題。每個線程都在自己的node上spin，當釋放鎖時通知
  后面的線程。