簡單自旋鎖（可重入）
自旋鎖是指當(dāng)一個線程嘗試獲取某個鎖時，如果該鎖已被其他線程占用，就一直循環(huán)檢測鎖是否被釋放，而不是進入線程掛起或睡眠狀態(tài)寂玲。
自旋鎖適用于鎖保護的臨界區(qū)很小的情況，臨界區(qū)很小的話梗摇，鎖占用的時間就很短拓哟。
public class SpinLock implements Lock {
/**
* use thread itself as synchronization state
* 使用Owner Thread作為同步狀態(tài)，比使用一個簡單的boolean flag可以攜帶更多信息
*/
private AtomicReference<Thread> owner = new AtomicReference<>();
/**
* reentrant count of a thread, no need to be volatile
*/
private int count = 0;
@Override
public void lock() {
Thread t = Thread.currentThread();
// if re-enter, increment the count.
if (t == owner.get()) {
++count;
return;
}
//spin
while (owner.compareAndSet(null, t)) {
}
}
@Override
public void unlock() {
Thread t = Thread.currentThread();
//only the owner could do unlock;
if (t == owner.get()) {
if (count > 0) {
// reentrant count not zero, just decrease the counter.
--count;
} else {
// compareAndSet is not need here, already checked
owner.set(null);
}
}
}
}
SimpleSpinLock里有一個owner屬性持有鎖當(dāng)前擁有者的線程的引用伶授，如果該引用為null断序，則表示鎖未被占用，不為null則被占用糜烹。
這里用AtomicReference是為了使用它的原子性的compareAndSet方法（CAS操作）违诗，解決了多線程并發(fā)操作導(dǎo)致數(shù)據(jù)不一致的問題，確保其他線程可以看到鎖的真實狀態(tài)疮蹦。
缺點：
- CAS操作需要硬件的配合较雕；
- 保證各個CPU的緩存（L1、L2挚币、L3、跨CPU Socket扣典、主存）的數(shù)據(jù)一致性妆毕，通訊開銷很大，在多處理器系統(tǒng)上更嚴(yán)重贮尖；
- 沒法保證公平性笛粘，不保證等待進程/線程按照FIFO順序獲得鎖。
TicketLock
Ticket Lock 是為了解決上面的公平性問題，類似于現(xiàn)實中銀行柜臺的排隊叫號：鎖擁有一個服務(wù)號薪前，表示正在服務(wù)的線程润努，還有一個排隊號；每個線程嘗試獲取鎖之前先拿一個排隊號示括，然后不斷輪詢鎖的當(dāng)前服務(wù)號是否是自己的排隊號铺浇，如果是，則表示自己擁有了鎖垛膝，不是則繼續(xù)輪詢鳍侣。
當(dāng)線程釋放鎖時，將服務(wù)號加1吼拥，這樣下一個線程看到這個變化倚聚，就退出自旋。
public class TicketLock implements Lock {
private AtomicInteger serviceNum = new AtomicInteger(0);
private AtomicInteger ticketNum = new AtomicInteger(0);
private final ThreadLocal<Integer> myNum = new ThreadLocal<>();
@Override
public void lock() {
myNum.set(ticketNum.getAndIncrement());
while (serviceNum.get() != myNum.get()) {
}
}
@Override
public void unlock() {
serviceNum.compareAndSet(myNum.get(), myNum.get() + 1);
myNum.remove();
}
}
缺點：
Ticket Lock 雖然解決了公平性的問題凿可，但是多處理器系統(tǒng)上惑折，每個進程/線程占用的處理器都在讀寫同一個變量serviceNum ，每次讀寫操作都必須在多個處理器緩存之間進行緩存同步枯跑，這會導(dǎo)致繁重的系統(tǒng)總線和內(nèi)存的流量惨驶，大大降低系統(tǒng)整體的性能。
下面介紹的CLH鎖和MCS鎖都是為了解決這個問題的全肮。
CLHLock
CLH的發(fā)明人是：Craig敞咧，Landin and Hagersten。是一種基于鏈表的可擴展辜腺、高性能休建、公平的自旋鎖，申請線程只在本地變量上自旋评疗，它不斷輪詢前驅(qū)的狀態(tài)测砂，如果發(fā)現(xiàn)前驅(qū)釋放了鎖就結(jié)束自旋。
CLH隊列中的結(jié)點QNode中含有一個locked字段百匆，該字段若為true表示該線程需要獲取鎖砌些，且不釋放鎖，為false表示線程釋放了鎖加匈。結(jié)點之間是通過隱形的鏈表相連存璃，之所以叫隱形的鏈表是因為這些結(jié)點之間沒有明顯的next指針，而是通過preNode所指向的結(jié)點的變化情況來影響myNode的行為雕拼。CLHLock上還有一個尾指針纵东，始終指向隊列的最后一個結(jié)點。CLHLock的類圖如下所示：
當(dāng)一個線程需要獲取鎖時啥寇，會創(chuàng)建一個新的QNode偎球，將其中的locked設(shè)置為true表示需要獲取鎖洒扎，然后線程對tail域調(diào)用getAndSet方法，使自己成為隊列的尾部衰絮，同時獲取一個指向其前趨的引用preNode,然后該線程就在前趨結(jié)點的locked字段上自旋袍冷，直到前趨結(jié)點釋放鎖。當(dāng)一個線程需要釋放鎖時猫牡，將當(dāng)前結(jié)點的locked域設(shè)置為false胡诗，同時回收前趨結(jié)點。如下圖所示镊掖，線程A需要獲取鎖乃戈，其myNode域為true，些時tail指向線程A的結(jié)點亩进，然后線程B也加入到線程A后面症虑，tail指向線程B的結(jié)點。然后線程A和B都在它的preNode域上旋轉(zhuǎn)归薛，一旦它的preNode結(jié)點的locked字段變?yōu)閒alse谍憔，它就可以獲取鎖。明顯線程A的preNode locked域為false主籍，此時線程A獲取到了鎖习贫。
實現(xiàn)如下：
public class CLHLock implements Lock {
/**
* 鎖等待隊列的尾部
*/
private AtomicReference<QNode> tail;
private ThreadLocal<QNode> preNode;
private ThreadLocal<QNode> myNode;
public CLHLock() {
tail = new AtomicReference<>(null);
myNode = ThreadLocal.withInitial(QNode::new);
preNode = ThreadLocal.withInitial(() -> null);
}
@Override
public void lock() {
QNode qnode = myNode.get();
//設(shè)置自己的狀態(tài)為locked=true表示需要獲取鎖
qnode.locked = true;
//鏈表的尾部設(shè)置為本線程的qNode，并將之前的尾部設(shè)置為當(dāng)前線程的preNode
QNode pre = tail.getAndSet(qnode);
preNode.set(pre);
if(pre != null) {
//當(dāng)前線程在前驅(qū)節(jié)點的locked字段上旋轉(zhuǎn)千元，直到前驅(qū)節(jié)點釋放鎖資源
while (pre.locked) {
}
}
}
@Override
public void unlock() {
QNode qnode = myNode.get();
//釋放鎖操作時將自己的locked設(shè)置為false苫昌，可以使得自己的后繼節(jié)點可以結(jié)束自旋
qnode.locked = false;
//回收自己這個節(jié)點，從虛擬隊列中刪除
//將當(dāng)前節(jié)點引用置為自己的preNode幸海，那么下一個節(jié)點的preNode就變?yōu)榱水?dāng)前節(jié)點的preNode祟身，這樣就將當(dāng)前節(jié)點移出了隊列
myNode.set(preNode.get());
}
private class QNode {
/**
* true表示該線程需要獲取鎖，且不釋放鎖物独，為false表示線程釋放了鎖袜硫，且不需要鎖
*/
private volatile boolean locked = false;
}
}
CLH隊列鎖的優(yōu)點是空間復(fù)雜度低（如果有n個線程，L個鎖挡篓，每個線程每次只獲取一個鎖婉陷，那么需要的存儲空間是O（L+n），n個線程有n個myNode官研，L個鎖有L個tail）秽澳，CLH的一種變體被應(yīng)用在了JAVA并發(fā)框架中。唯一的缺點是在NUMA系統(tǒng)結(jié)構(gòu)下性能很差戏羽，在這種系統(tǒng)結(jié)構(gòu)下担神，每個線程有自己的內(nèi)存，如果前趨結(jié)點的內(nèi)存位置比較遠(yuǎn)蛛壳，自旋判斷前趨結(jié)點的locked域杏瞻，性能將大打折扣，但是在SMP系統(tǒng)結(jié)構(gòu)下該法還是非常有效的衙荐。一種解決NUMA系統(tǒng)結(jié)構(gòu)的思路是MCS隊列鎖捞挥。
MCSLock
MCS 來自于其發(fā)明人名字的首字母： John Mellor-Crummey和Michael Scott。是一種基于鏈表的可擴展忧吟、高性能砌函、公平的自旋鎖，申請線程只在本地變量上自旋溜族，直接前驅(qū)負(fù)責(zé)通知其結(jié)束自旋讹俊，從而極大地減少了不必要的處理器緩存同步的次數(shù)，降低了總線和內(nèi)存的開銷煌抒。
public class MCSLock implements Lock {
private AtomicReference<QNode> tail;
private ThreadLocal<QNode> myNode;
public MCSLock() {
tail = new AtomicReference<>(null);
myNode = ThreadLocal.withInitial(QNode::new);
}
@Override
public void lock() {
QNode qnode = myNode.get();
QNode preNode = tail.getAndSet(qnode);
if (preNode != null) {
qnode.locked = false;
preNode.next = qnode;
//wait until predecessor gives up the lock
while (!qnode.locked) {
}
}
qnode.locked = true;
}
@Override
public void unlock() {
QNode qnode = myNode.get();
if (qnode.next == null) {
//后面沒有等待線程的情況
if (tail.compareAndSet(qnode, null)) {
//真的沒有等待線程仍劈，則直接返回，不需要通知
return;
}
//wait until predecessor fills in its next field
// 突然有人排在自己后面了寡壮，可能還不知道是誰贩疙，下面是等待后續(xù)者
while (qnode.next == null) {
}
}
//后面有等待線程，則通知后面的線程
qnode.next.locked = true;
qnode.next = null;
}
private class QNode {
/**
* 是否被qNode所屬線程鎖定
*/
private volatile boolean locked = false;
/**
* 與CLHLock相比况既，多了這個真正的next
*/
private volatile QNode next = null;
}
}
CLH鎖 與 MCS鎖 的比較
差異：
- 從代碼實現(xiàn)來看这溅，CLH比MCS要簡單得多。
- 從自旋的條件來看棒仍，CLH是在前驅(qū)節(jié)點的屬性上自旋悲靴，而MCS是在本地屬性變量上自旋。
- 從鏈表隊列來看莫其，CLHNode不直接持有前驅(qū)節(jié)點癞尚，CLH鎖釋放時只需要改變自己的屬性；MCSNode直接持有后繼節(jié)點榜配，MCS鎖釋放需要改變后繼節(jié)點的屬性否纬。
- CLH鎖釋放時只需要改變自己的屬性，MCS鎖釋放則需要改變后繼節(jié)點的屬性蛋褥。
