1、 為什麼要引入MCS鎖？
在NUMA架構體系下，通路remote memory的速度要遠遠慢于通路local memory的速度。如下圖所示（引自Companion slides for The Art of Multiprocessor Programming by Maurice Herlihy & Nir Shavit）：
在前一篇文章中分析了CLH算法，由于每個線程都在其前驅線程的QNode節點的locked域自旋，在NUMA體系下，即每個線程都在其前驅線程的remote memory位置自旋，是以性能上會打折扣。
那麼在NUMA體系下，如果每個線程自旋的位置都能固定在自己的local memory中，則性能相比于CLH算法，應該會有一定的提升。MCS鎖就是基于這種理念設計出來的。
2、MCS鎖介紹
同CLH鎖一樣，每個申請鎖的線程通過一個QNode對象表示，QNode中有一個volatile boolean類型的成員變量locked，locked為true，則表示對應的線程已經擷取到了鎖或者正在等待擷取鎖；locked為false，則表示對應的線程已經釋放了鎖。
鎖則由多個QNode節點組成連結清單标示，與CLH鎖不同的是，MCS中的鎖不是虛拟連結清單，而是實際連結清單，每個QNode節點都有一個next域指向其後繼結點。
public class QNode {
public volatile boolean locked = false;
public QNode next = null;
}
而連結清單的尾節點則通過鎖AtomicReference<QNode>類型的tail成員變量指向，即tail指向加入到申請鎖的隊列中的最近一個線程。
public class MCSLock implements Lock {
private AtomicReference<QNode> tail;
private ThreadLocal<QNode> myNode;
public MCSLock() {
tail = new AtomicReference<QNode>(null);
myNode = new ThreadLocal<QNode>() {
protected QNode initialValue() {
return new QNode();
}
};
}
public void lock() {
QNode qnode = myNode.get();
QNode pred = tail.getAndSet(qnode);
if (null != pred) {
qnode.locked = true;
pred.next = qnode;
}
while (qnode.locked) {
}
}
public void unlock() {
QNode qnode = myNode.get();
if (null == qnode.next) {
if (tail.compareAndSet(qnode, null)) {
return;
}
while (null == qnode.next) {
}
}
qnode.next.locked = false;
qnode.next = null;
}
}
當一個線程申請鎖時：
a)首先會執行個體化一個QNode節點，并将其設定為自己的本地線程變量myNode；
b)然後通過調用AtomicReference的getAndSet()方法，将myNode設定為隊列的最後一個節點，并傳回其前驅節點
c)接着判斷前面是否已經有其他線程加入到鎖的等待隊列中，即前驅節點是否為空。如果前驅節點為空，則說明自己是第一個加入到鎖的等待隊列中的線程，執行自旋，由于locked域初始值為false，是以能立即退出自旋，擷取到鎖；
d)如果前驅節點非空，則首先将myNode的locked域設定為true，表明自己正在等待擷取鎖；同時将前驅結點的next域指向myNode。
e)最後該線程一直在自己節點的locked域自旋，直到locked域變為false，即前驅節點釋放了鎖。
當一個線程釋放鎖時，會處于以下三種情況之一中：
a)此刻沒有其它線程正在申請鎖，即目前節點的next域指向null，且tail指向目前節點：此種情況通過調用AtomicReference的compareAndSet()方法，将tail指向null；然後直接傳回。
b)此刻有其他線程正在申請鎖，而且已更新tail域，但還未将前驅節點的next域指向它。即目前節點的next域指向null，且tail不是指向目前節點：此種情況則一直等待其他線程設定前驅節點的next域後，才将後繼節點的locked域設定為false，以便後繼節點退出自旋，進而擷取到釋放的鎖。
c)此刻有其他線程正在申請鎖，而且已更新tail域，而且已将前驅節點的next域指向它。即目前節點的next域非空：此種情況則直接将後繼節點的locked域設定為false，以便後繼節點退出自旋，進而擷取到釋放的鎖。
下圖闡述了MCS算法中鎖的擷取和釋放過程（引自The art of Multiprocessor Programming一書）：
