普通自旋鎖
利用AtomicReference.compareAndSet 確定對象的原子性，并通過while不斷循環(huán)阻塞其他線程。
當(dāng)上個(gè)線程unLock后，阻塞線程跳出while。
public class SpinningLock {
/**
* 持有鎖的線程 為空標(biāo)識沒有線程持有
*/
private AtomicReference<Thread> ref = new AtomicReference<>();
/**
* 鎖
*/
public void Lock(){
// 獲取當(dāng)前線程
Thread currentThread = Thread.currentThread();
// ref.compareAndSet
// 1. 當(dāng)ref = null時(shí) compareAndSet 把當(dāng)前線程賦值到ref 并返回true
// 2. 當(dāng)ref != null時(shí) compareAndSet 返回false
while (!ref.compareAndSet(null, currentThread)){
// 通過循環(huán)不斷的自旋判斷鎖是否被其他線程持有 hlod資源
}
}
/**
* 解鎖
*/
public void unLock(){
Thread currentThread = Thread.currentThread();
ref.get();
ref.compareAndSet(currentThread, null);
}
}
優(yōu)點(diǎn)：
- 無需上下文切換，速率快
缺點(diǎn)：
- conpareAndSet是其核心，底層通過各系統(tǒng)cpu指令實(shí)現(xiàn)（依賴硬件）。
- 無法保證等待線程按FIFO順序獲得鎖（非公平）
自旋鎖變種（TicketLock-解決普通自旋鎖 公平性問題）
類似排號流程:
lock()
用戶A和B去醫(yī)院排號，A到了1號，B取到了2號 => myNum.set(ticketNum.getAndIncrement());。
醫(yī)生按照票號順序叫號對A一頓服務(wù)，B就老老實(shí)實(shí)坐板凳等著 => while (serviceNum.get() != myNum.get())unlock()
當(dāng)醫(yī)生服務(wù)完后，看了眼A的票號，下個(gè)應(yīng)該是2號治療了 => serviceNum.compareAndSet(myNum.get(), myNum.get() + 1);
然后將A請出去 => myNum.remove(); 讓還在while等著的B進(jìn)來。
public class TicketLock implements Lock {
// 服務(wù)號 線程完成作業(yè) +1
private AtomicInteger serviceNum = new AtomicInteger(0);
// 取票號 線程進(jìn)入時(shí)取號
private AtomicInteger ticketNum = new AtomicInteger(0);
// 當(dāng)前線程持有號
private final ThreadLocal<Integer> myNum = new ThreadLocal<>();
@Override
public void lock() {
// 當(dāng)前線程取號
myNum.set(ticketNum.getAndIncrement());
// 當(dāng)服務(wù)號 ！= 線程所取到的號 死循環(huán)阻塞 監(jiān)聽到serviceNum = myNum時(shí)退出循環(huán)
while (serviceNum.get() != myNum.get()) {
}
}
@Override
public void unlock() {
serviceNum.compareAndSet(myNum.get(), myNum.get() + 1);
myNum.remove();
}
}
該變種雖然解決了公平性問題，但是在多處理系統(tǒng)上需要對serviceNum進(jìn)行讀寫同步，增大了內(nèi)存和總線的流量，降低了系統(tǒng)整體性能。
自旋鎖變種（CLHLock）
CLHLock發(fā)明人是：Craig，Landin and Hagersten 所以才以CLH開頭。這是種基于鏈表，可擴(kuò)展和高性能的自旋鎖。
該設(shè)計(jì)的思想主要是將線程有序的抽象成一個(gè)個(gè)Node對象，利用對象的線程共享locked屬性，判斷是否存在上個(gè)節(jié)點(diǎn)持有鎖，以此阻塞或通過。每次獲取鎖時(shí)將當(dāng)前node放入尾部鏈表，將上個(gè)node放入前區(qū)鏈表；解鎖時(shí)獲取當(dāng)前node，置為false，讓后續(xù)線程通過，再將currNode置為preNode,因?yàn)槌跏蓟瘯r(shí)是個(gè)初始對象，相當(dāng)于平移，這樣就將當(dāng)前node移出節(jié)點(diǎn)
public class CLHLock implements Lock {
// 指向尾部節(jié)點(diǎn)
private final AtomicReference<QNode> tail;
// 指向前驅(qū)節(jié)點(diǎn)
private final ThreadLocal<QNode> preNode;
// 當(dāng)前節(jié)點(diǎn)
private final ThreadLocal<QNode> myNode;
public CLHLock() {
tail = new AtomicReference<>(new QNode());
myNode = ThreadLocal.withInitial(QNode::new);
preNode = new ThreadLocal<>();
}
@Override
public void lock() {
// 獲取一個(gè)QNode
QNode qnode = myNode.get();
// 設(shè)置自己的狀態(tài)為locked=true表示需要獲取鎖
qnode.locked = true;
// 鏈表的尾部設(shè)置為本線程的qNode，并將之前的尾部設(shè)置為當(dāng)前線程的preNode
QNode pre = tail.getAndSet(qnode);
// 把舊的節(jié)點(diǎn)放入前驅(qū)節(jié)點(diǎn)。
preNode.set(pre);
// 當(dāng)前線程在前驅(qū)節(jié)點(diǎn)的locked字段上旋轉(zhuǎn)，直到前驅(qū)節(jié)點(diǎn)釋放鎖資源
while (pre.locked) {
}
}
@Override
public void unlock() {
// 獲取當(dāng)前節(jié)點(diǎn)
QNode qnode = myNode.get();
// 釋放鎖操作時(shí)將自己的locked設(shè)置為false，可以使得自己的后繼節(jié)點(diǎn)可以結(jié)束自旋
qnode.locked = false;
// 回收自己這個(gè)節(jié)點(diǎn)，從虛擬隊(duì)列中刪除
// 將當(dāng)前節(jié)點(diǎn)引用置為自己的preNode，那么下一個(gè)節(jié)點(diǎn)的preNode就變?yōu)榱水?dāng)前節(jié)點(diǎn)的preNode，這樣就將當(dāng)前節(jié)點(diǎn)移出了隊(duì)列
myNode.set(preNode.get());
}
private class QNode {
// true表示該線程需要獲取鎖，且不釋放鎖，為false表示線程釋放了鎖，且不需要鎖 volatile 修飾其它線程可見
private volatile boolean locked = false;
}
優(yōu)點(diǎn)：
空間復(fù)雜度低（如果有n個(gè)線程，L個(gè)鎖，每個(gè)線程每次只獲取一個(gè)鎖，那么需要的存儲(chǔ)空間是O（L+n），n個(gè)線程有n個(gè)myNode，L個(gè)鎖有L個(gè)tail），CLH的一種變體被應(yīng)用在了JAVA并發(fā)框架中
缺點(diǎn)：
在NUMA系統(tǒng)結(jié)構(gòu)下性能很差(在這種系統(tǒng)結(jié)構(gòu)下，每個(gè)線程有自己的內(nèi)存，如果前趨結(jié)點(diǎn)的內(nèi)存位置比較遠(yuǎn)，自旋判斷前趨結(jié)點(diǎn)的locked域，性能將大打折扣)
自旋鎖變種（MCSLock）
MCS 來自于其發(fā)明人名字的首字母： John Mellor-Crummey和Michael Scott。是一種基于鏈表的可擴(kuò)展、高性能、公平的自旋鎖。
MCSLock 與 CLHNode的差異
- 從代碼實(shí)現(xiàn)來看，CLH比MCS要簡單得多。
- 從自旋的條件來看，CLH是在前驅(qū)節(jié)點(diǎn)的屬性上自旋，而MCS是在本地屬性變量上自旋。
- MCSLock：
while (!qnode.locked)- CLHNode：
while (pre.locked)
- 從鏈表隊(duì)列來看，CLHNode不直接持有前驅(qū)節(jié)點(diǎn)，CLH鎖釋放時(shí)只需要改變自己的屬性；MCSNode直接持有后繼節(jié)點(diǎn)，MCS鎖釋放需要改變后繼節(jié)點(diǎn)的屬性。
- CLH鎖釋放時(shí)只需要改變自己的屬性，MCS鎖釋放則需要改變后繼節(jié)點(diǎn)的屬性。
public class MCSLock implements Lock {
// 尾結(jié)點(diǎn)
private AtomicReference<QNode> tail;
// 當(dāng)前節(jié)點(diǎn)
private ThreadLocal<QNode> myNode;
public MCSLock() {
tail = new AtomicReference<>(null);
myNode = ThreadLocal.withInitial(QNode::new);
}
@Override
public void lock() {
// 獲取當(dāng)前節(jié)點(diǎn)
QNode qnode = myNode.get();
// 賦值當(dāng)前節(jié)點(diǎn) 并返回舊值（即上個(gè)節(jié)點(diǎn)）
QNode preNode = tail.getAndSet(qnode);
// 上個(gè)節(jié)點(diǎn)不為空 說明有線程持有資源
if (preNode != null){
// 設(shè)置當(dāng)前節(jié)點(diǎn)設(shè)置為false
qnode.locked = false;
// 將上個(gè)節(jié)點(diǎn)的指針 指向當(dāng)前節(jié)點(diǎn)
preNode.next = qnode;
// 等待上個(gè)節(jié)點(diǎn)執(zhí)行完畢
while (!qnode.locked) {
}
}
// 設(shè)置當(dāng)前節(jié)點(diǎn)為持有資源進(jìn)程
qnode.locked = true;
}
@Override
public void unlock() {
// 獲取當(dāng)前節(jié)點(diǎn)
QNode qnode = myNode.get();
if (qnode.next == null) {
//后面沒有等待線程的情況
if (tail.compareAndSet(qnode, null)) {
//真的沒有等待線程，則直接返回，不需要通知
return;
}
// if (tail.compareAndSet(qnode, null)) return false 說明已經(jīng)進(jìn)入了另外一個(gè)線程
while (qnode.next == null) {
}
}
//后面有等待線程，則通知后面的線程
qnode.next.locked = true;
qnode.next = null;
}
private class QNode {
/**
* 是否被qNode所屬線程鎖定
*/
private volatile boolean locked = false;
/**
* 與CLHLock相比，多了這個(gè)真正的next
*/
private volatile QNode next = null;
}
}
優(yōu)點(diǎn)：
申請線程只在本地變量上自旋，直接前驅(qū)負(fù)責(zé)通知其結(jié)束自旋，從而極大地減少了不必要的處理器緩存同步的次數(shù)，降低了總線和內(nèi)存的開銷，解決NUMA系統(tǒng)結(jié)構(gòu)的思路是MCS隊(duì)列鎖。
