几种锁算法的实现详解编程语言

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