几种锁算法的实现，几种锁算法实现,Abstract 4种

几种锁算法的实现，几种锁算法实现,Abstract 4种

Abstract 4种Lock的实现： TASLockTTASLockCLHLockMCSLock 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);  }}

while (state.get()){}是一个改进，效果是先看一眼lock的状态，当lock是false时，再真正的执行state.getAndSet(true)。当state.getAndSet(true) 的return为false时，说明之前的确是false，于是获得锁，return。否则回到while(true),再次尝试获得锁。 defect： 在unlock时，state.set(false)还是会带来大量的cache miss。cache miss VS cache hit CLHLock 队列锁。 CLHLock```javavoid 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 ```javapublic 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，当释放锁时通知后面的线程。