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