CLH的发明人是:Craig,Landin and Hagersten。

CLH锁即 Craig, Landin, and Hagersten (CLH) locks

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

CLH锁是一种基于链表的可扩展、高性能、公平的自旋锁,申请线程只在本地变量上自旋,它不断轮询前驱的状态,如果发现前驱释放了锁就结束自旋。

CLH算法实现

CLH队列锁表示为QNode对象的链表,QNode中含有一个locked字段,该字段若为true表示该线程需要获取锁,且不释放锁,为false表示线程释放了锁。结点之间是通过隐形的链表相连,之所以叫隐形的链表是因为这些结点之间没有明显的next指针,每个线程通过一个线程局部变量pred指向其前驱,线程通过检测前驱结点的locked域来判断是否轮到自己。如果该域为true,则前驱线程要么已经获得锁要么正在等待锁;如果该域为false,则前驱进程已释放锁,轮到自己了。正常情况下,队列链中只有一个结点的locked域为false。CLHLock上还有一个尾指针,始终指向队列的最后一个结点。

当一个线程调用lock()方法想获得锁时,将自己的locked域置为true,表示该线程不准备释放锁,然后并将自己的结点加入到队列链尾部。最后就是在前驱的locked域上旋转,等待前驱释放锁。当这个线程调用unlock()方法要释放锁时,线程要将自己的locked域置为false,表示已经释放锁,然后将前驱结点作为自己的新结点以便日后访问。

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
  
//clh 1
  
class ClhSpinLock {
      
private final ThreadLocal<Node> prev;
      
private final ThreadLocal<Node> node;
      
private final AtomicReference<Node> tail = new AtomicReference<Node>(new Node());

public ClhSpinLock() {
          
this.node = new ThreadLocal<Node>() {
              
protected Node initialValue() {
                  
return new Node();
              
}
          
};

this.prev = new ThreadLocal<Node>() {
              
protected Node initialValue() {
                  
return null;
              
}
          
};
      
}

public void lock() {
          
final Node node = this.node.get();
          
node.locked = true;
          
// 一个CAS操作即可将当前线程对应的节点加入到队列中,
          
// 并且同时获得了前继节点的引用,然后就是等待前继释放锁
          
Node pred = this.tail.getAndSet(node);
          
this.prev.set(pred);
          
while (pred.locked) {// 进入自旋
          
}
      
}

public void unlock() {
          
final Node node = this.node.get();
          
node.locked = false;// 改变状态,让后续线程结束自旋
          
this.node.set(this.prev.get());
      
}

private static class Node {
          
private volatile boolean locked;
      
}
  
}

//clh 2
  
import java.util.concurrent.atomic.AtomicReferenceFieldUpdater;

public class CLHLock {
      
public static class CLHNode {
          
private volatile boolean isLocked = true; // 默认是在等待锁
      
}

@SuppressWarnings("unused" )
      
private volatile CLHNode tail ;
      
private static final AtomicReferenceFieldUpdater<CLHLock, CLHNode> UPDATER = AtomicReferenceFieldUpdater
                    
.newUpdater(CLHLock.class, CLHNode .class , "tail" );

public void lock(CLHNode currentThread) {
          
CLHNode preNode = UPDATER.getAndSet( this, currentThread);
          
if(preNode != null) {//已有线程占用了锁,进入自旋
              
while(preNode.isLocked ) {
              
}
          
}
      
}

public void unlock(CLHNode currentThread) {
          
// 如果队列里只有当前线程,则释放对当前线程的引用(for GC)。
          
if (!UPDATER.compareAndSet(this, currentThread, null)) {
              
// 还有后续线程
              
currentThread.isLocked = false ;// 改变状态,让后续线程结束自旋
          
}
      
}
  
}
  

NUMA与SMP

SMP(Symmetric Multi-Processor),即对称多处理器结构,指服务器中多个CPU对称工作,每个CPU访问内存地址所需时间相同。其主要特征是共享,包含对CPU,内存,I/O等进行共享。SMP的优点是能够保证内存一致性,缺点是这些共享的资源很可能成为性能瓶颈,随着CPU数量的增加,每个CPU都要访问相同的内存资源,可能导致内存访问冲突,可能会导致CPU资源的浪费。常用的PC机就属于这种。

NUMA(Non-Uniform Memory Access)非一致存储访问,将CPU分为CPU模块,每个CPU模块由多个CPU组成,并且具有独立的本地内存、I/O槽口等,模块之间可以通过互联模块相互访问,访问本地内存的速度将远远高于访问远地内存(系统内其它节点的内存)的速度,这也是非一致存储访问NUMA的由来。NUMA优点是可以较好地解决原来SMP系统的扩展问题,缺点是由于访问远地内存的延时远远超过本地内存,因此当CPU数量增加时,系统性能无法线性增加。

http://googi.iteye.com/blog/1736570

http://blog.csdn.net/aesop_wubo/article/details/7533186

http://zhanjindong.com/2015/03/11/java-concurrent-package-aqs-clh-and-spin-lock