江苏龙网

  1. 主页 > 生活百科 > >

线程锁系列：CLH Lock

线程锁


线程锁系列：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();}@Overridepublic void lock() {QNode node = myNode.get();node.locked = true;QNode pred = tail.getAndSet(node);myPred.set(pred);while (pred.locked) {}}@Overridepublic 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一致性的系统架构上表现良好 。

【线程锁系列：CLH Lock】


    推荐阅读


    上一篇：定不要忽略这些倒茶的些基本礼仪

    下一篇：蒙古族的饮茶习俗是善于喝奶茶