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，当释放锁时通知
  后面的线程。