java clh_CLH lock 原理及JAVA实现

CLH 锁的名字也与他们的发明人的名字相关：Craig，Landin and Hagersten。

CLH Lock摘要

CLH lock is Craig, Landin, and Hagersten (CLH) locks, CLH lock is a spin lock, can ensure no hunger, provide fairness first come first service.

The CLH lock is a scalable, high performance, fairness and spin lock based on the list, the application thread spin only on a local variable, it constantly polling the precursor state, if it is found that the pre release lock end spin.

CLH锁是自旋锁的一种，对它的研究是因为AQS源代码中使用了CLH锁的一个变种，为了更好的理解AQS中使用锁的思想，所以决定先好好理解CLH锁

二. CLH原理

CLH也是一种基于单向链表(隐式创建)的高性能、公平的自旋锁，申请加锁的线程只需要在其前驱节点的本地变量上自旋，从而极大地减少了不必要的处理器缓存同步的次数，降低了总线和内存的开销。

三. Java代码实现

类图

public interface Lock {

void lock();

void unlock();

}

public class QNode {

volatile boolean locked;

}

import java.util.concurrent.atomic.AtomicReference;

public class CLHLock implements Lock {

// 尾巴，是所有线程共有的一个。所有线程进来后，把自己设置为tail

private final AtomicReference tail;

// 前驱节点，每个线程独有一个。

private final ThreadLocal myPred;

// 当前节点，表示自己，每个线程独有一个。

private final ThreadLocal myNode;

public CLHLock() {

this.tail = new AtomicReference(new QNode());

this.myNode = new ThreadLocal() {

protected QNode initialValue() {

return new QNode();

}

};

this.myPred = new ThreadLocal();

}

@Override

public void lock() {

// 获取当前线程的代表节点

QNode node = myNode.get();

// 将自己的状态设置为true表示获取锁。

node.locked = true;

// 将自己放在队列的尾巴，并且返回以前的值。第一次进将获取构造函数中的那个new QNode

QNode pred = tail.getAndSet(node);

// 把旧的节点放入前驱节点。

myPred.set(pred);

// 判断前驱节点的状态，然后走掉。

while (pred.locked) {

}

@Override

public void unlock() {

// unlock. 获取自己的node。把自己的locked设置为false。

QNode node = myNode.get();

node.locked = false;

myNode.set(myPred.get());

}

简单的看一下CLH的算法定义

the list, the application thread spin only on a local variable, it constantly polling the precursor state, if it is found that the pre release lock end spin.

基于list，线程仅在一个局部变量上自旋，它不断轮询前一个节点状态，如果发现前一个节点释放锁结束.

所以在java中使用了ThreadLocal作为具体实现,AtomicReference为了消除多个线程并发对tail引用Node的影响，核心方法lock()中分为3个步骤去实现

初始状态 tail指向一个node(head)节点

private final AtomicReference tail = new AtomicReference(new Node());

thread加入等待队列: tail指向新的Node，同时Prev指向tail之前指向的节点，在java代码中使用了getAndSet即CAS操作使用

Node pred = this.tail.getAndSet(node);

this.prev.set(pred);

寻找当前线程对应的node的前驱node然后开始自旋前驱node的status判断是否可以获取lock

while (pred.locked);

同理unlock()方法，获取当前线程的node，设置lock status，将当前node指向前驱node(这样操作tail指向的就是前驱node等同于出队操作).至此CLH Lock的过程就结束了

测试CLHLock

public class CLHLockDemo2 {

public static void main(String[] args) {

final Kfc kfc = new Kfc();

for (int i = 0; i < 10; i++) {

new Thread("eat" + i) {

public void run() {

kfc.eat();

}

}.start();

}

class Kfc {

private final Lock lock = new CLHLock();

private int i = 0;

public void eat() {

try {

lock.lock();

System.out.println(Thread.currentThread().getName() + ": " + --i);

Thread.sleep(1000);

} catch (InterruptedException e) {

e.printStackTrace();

} finally {

lock.unlock();

}

public void cook() {

try {

lock.lock();

System.out.println(Thread.currentThread().getName() + ": " + ++i);

Thread.sleep(1000);

} catch (InterruptedException e) {

e.printStackTrace();

} finally {

lock.unlock();

}

运行结果

eat1: -1

eat0: -2

eat3: -3

eat4: -4

eat7: -5

eat2: -6

eat5: -7

eat6: -8

eat8: -9

eat9: -10

四.　CLH优缺点

CLH队列锁的优点是空间复杂度低(如果有n个线程，L个锁，每个线程每次只获取一个锁，那么需要的存储空间是O(L+n)，n个线程有n个myNode，L个锁有L个tail)，CLH的一种变体被应用在了JAVA并发框架中。唯一的缺点是在NUMA系统结构下性能很差，在这种系统结构下，每个线程有自己的内存，如果前趋结点的内存位置比较远，自旋判断前趋结点的locked域，性能将大打折扣，但是在SMP系统结构下该法还是非常有效的。一种解决NUMA系统结构的思路是MCS队列锁。

五. 了解与CLH对应的MCS自旋锁

MCS 自旋锁

MCS 的名称来自其发明人的名字：John Mellor-Crummey和Michael Scott。

MCS 的实现是基于链表的，每个申请锁的线程都是链表上的一个节点，这些线程会一直轮询自己的本地变量，来知道它自己是否获得了锁。已经获得了锁的线程在释放锁的时候，负责通知其它线程，这样 CPU 之间缓存的同步操作就减少了很多，仅在线程通知另外一个线程的时候发生，降低了系统总线和内存的开销。实现如下所示：

import java.util.concurrent.atomic.AtomicReferenceFieldUpdater;

public class MCSLock {

public static class MCSNode {

volatile MCSNode next;

volatile boolean isWaiting = true; // 默认是在等待锁

}

volatile MCSNode queue;// 指向最后一个申请锁的MCSNode

private static final AtomicReferenceFieldUpdater UPDATER = AtomicReferenceFieldUpdater

.newUpdater(MCSLock.class, MCSNode.class, "queue");

public void lock(MCSNode currentThread) {

MCSNode predecessor = UPDATER.getAndSet(this, currentThread);// step 1

if (predecessor != null) {