转载

几种锁算法的实现

Multicore

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);  } }

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

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: