几种锁算法的实现

Abstract

• TASLock
• TTASLock
• CLHLock
• MCSLock

TASLock

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

TTASLock

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),再次尝试获得锁。

• 在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;
}

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

Summary

• CLHLock的思想是当前线程在前一个线程的node上spin，每个线程unlock时修改自身的标记。
  在共享总线结构下性能可以，无法应对分布式。
• MCSLock 用于解决分布式并行的问题。每个线程都在自己的node上spin，当释放锁时通知
  后面的线程。