线程锁系列：CLH Lock

最近在看关于线程锁的算法，做一个整理。资料出自于《The Art of Multiprocessor Programming》，算是一个读书笔记吧。示范代码基于JAVA。

第一章是Craig, Landin, and Hagersten (CLH) locks。先上CLHLock的实现逻辑：

 public class CLHLock implements Lock { 
 private final AtomicReference tail; 
 private final ThreadLocal myPred; 
 private final ThreadLocal myNode; 
 public CLHLock() { 
 tail = new AtomicReference(new QNode()); 
 myNode = new ThreadLocal() { 
 protected QNode initialValue() { 
 return new QNode(); 
 } 
 }; 
 myPred = new ThreadLocal(); 
 } 
 @Override 
 public void lock() { 
 QNode node = myNode.get(); 
 node.locked = true; 
 QNode pred = tail.getAndSet(node); 
 myPred.set(pred); 
 while (pred.locked) { 
 } 
 } 
 @Override 
 public void unlock() { 
 QNode node = myNode.get(); 
 node.locked = false; 
 myNode.set(myPred.get()); 
 } 
 private static class QNode { 
 volatile boolean locked; 
 } 
 } 

CLH Lock是一个自旋锁，能确保无饥饿性，提供先来先服务的公平性。

锁本身被表示成QNode的虚拟链表。共享的tail保存申请的最后的一个申请lock的线程的myNode域。每个申请lock的线程通过一个本地线程变量pred指向它的前驱。另外一个本地线程变量myNode的locked保存本身的状态，true：正在申请锁或已申请到锁；false：已释放锁。每个线程通过监视自身的前驱状态，自旋等待锁被释放。释放锁时，把自身myNode的locked设为false，使后继线程获的锁，并回收前驱的QNode，等待下次使用，因为自身的QNode可能被tail获后继引用，而前驱不再使用老的QNode。

该算法也是空间有效的，如果有n个线程，L个锁，每个线程每次只获取一个锁，那么需要的存储空间是O（L+n），n个线程有n个myNode，L个锁有L个tail。这种算法有一个缺点是在NUMA系统架构下性能表现很差，因为它自旋的locked是前驱线程的，如果内存位置较远，那么性能会受到损失。但是在SMP这种cache一致性的系统架构上表现良好。