最近在看關于線程鎖的算法，做一個整理。資料出自于《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一致性的系統架構上表現良好。
