最近在看關(guān)于線程鎖的算法，做一個整理。資料出自于《The Art of Multiprocessor Programming》，算是一個讀書筆記吧。示范代碼基于JAVA。
第一章是Craig, Landin, and Hagersten (CLH) locks。先上CLHLock的實現(xiàn)邏輯：
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指向它的前驅(qū)。另外一個本地線程變量myNode的locked保存本身的狀態(tài)，true：正在申請鎖或已申請到鎖；false：已釋放鎖。每個線程通過監(jiān)視自身的前驅(qū)狀態(tài)，自旋等待鎖被釋放。釋放鎖時，把自身myNode的locked設(shè)為false，使后繼線程獲的鎖，并回收前驅(qū)的QNode，等待下次使用，因為自身的QNode可能被tail獲后繼引用，而前驅(qū)不再使用老的QNode。
該算法也是空間有效的，如果有n個線程，L個鎖，每個線程每次只獲取一個鎖，那么需要的存儲空間是O（L+n），n個線程有n個myNode，L個鎖有L個tail。這種算法有一個缺點是在NUMA系統(tǒng)架構(gòu)下性能表現(xiàn)很差，因為它自旋的locked是前驅(qū)線程的，如果內(nèi)存位置較遠，那么性能會受到損失。但是在SMP這種cache一致性的系統(tǒng)架構(gòu)上表現(xiàn)良好。
