主要的CPU處理技術(shù)：多線程、多核心弟跑、SMP（Symmetric Multi-Processing對稱多處理結(jié)構(gòu)）、NUMA技術(shù)席吴、亂序執(zhí)行夭织、分枝技術(shù)吭露、控制器 來自百度百科中央處理器CPU。目前主流的查百度都是說SMP/MPP/NUMA這三種尊惰。
1 SMP (Symmetric Multi Processing),對稱多處理系統(tǒng)內(nèi)有許多緊耦合多處理器讲竿，在這樣的系統(tǒng)中，所有的CPU共享全部資源弄屡，如總線题禀，內(nèi)存和I/O系統(tǒng)等，操作系統(tǒng)或管理數(shù)據(jù)庫的復(fù)本只有一個(gè)膀捷，這種系統(tǒng)有一個(gè)最大的特點(diǎn)就是共享所有資源迈嘹。多個(gè)CPU之間沒有區(qū)別，平等地訪問內(nèi)存全庸、外設(shè)秀仲、一個(gè)操作系統(tǒng)。操作系統(tǒng)管理著一個(gè)隊(duì)列壶笼，每個(gè)處理器依次處理隊(duì)列中的進(jìn)程神僵。如果兩個(gè)處理器同時(shí)請求訪問一個(gè)資源（例如同一段內(nèi)存地址），由硬件拌消、軟件的鎖機(jī)制去解決資源爭用問題挑豌。Access to RAM is serialized; this and cache coherency issues causes performance to lag slightly behind the number of additional processors in the system.
2 NUMA(Non-Uniform Memory Access) 由于 SMP 在擴(kuò)展能力上的限制，人們開始探究如何進(jìn)行有效地?cái)U(kuò)展從而構(gòu)建大型系統(tǒng)的技術(shù)墩崩， NUMA 就是這種努力下的結(jié)果之一。利用 NUMA 技術(shù)侯勉，可以把幾十個(gè) CPU( 甚至上百個(gè) CPU) 組合在一個(gè)服務(wù)器內(nèi)鹦筹。
3 MPP(Massive Parallel Processing) 和 NUMA 不同， MPP 提供了另外一種進(jìn)行系統(tǒng)擴(kuò)展的方式址貌，它由多個(gè) SMP 服務(wù)器通過一定的節(jié)點(diǎn)互聯(lián)網(wǎng)絡(luò)進(jìn)行連接铐拐，協(xié)同工作，完成相同的任務(wù)练对，從用戶的角度來看是一個(gè)服務(wù)器系統(tǒng)遍蟋。其基本特征是由多個(gè) SMP 服務(wù)器 ( 每個(gè) SMP 服務(wù)器稱節(jié)點(diǎn) ) 通過節(jié)點(diǎn)互聯(lián)網(wǎng)絡(luò)連接而成，每個(gè)節(jié)點(diǎn)只訪問自己的本地資源 ( 內(nèi)存螟凭、存儲等 ) 虚青，是一種完全無共享 (Share Nothing) 結(jié)構(gòu)，因而擴(kuò)展能力最好螺男，理論上其擴(kuò)展無限制棒厘，目前的技術(shù)可實(shí)現(xiàn) 512 個(gè)節(jié)點(diǎn)互聯(lián)纵穿，數(shù)千個(gè) CPU 。目前業(yè)界對節(jié)點(diǎn)互聯(lián)網(wǎng)絡(luò)暫無標(biāo)準(zhǔn)奢人，如 NCR 的 Bynet 谓媒， IBM 的 SPSwitch ，它們都采用了不同的內(nèi)部實(shí)現(xiàn)機(jī)制何乎。但節(jié)點(diǎn)互聯(lián)網(wǎng)僅供 MPP 服務(wù)器內(nèi)部使用句惯，對用戶而言是透明的。
更多三者的閱讀請到SMP支救、NUMA抢野、MPP體系結(jié)構(gòu)介紹
MESI（Modified Exclusive Shared Or Invalid）(也稱為伊利諾斯協(xié)議，是因?yàn)樵搮f(xié)議由伊利諾斯州立大學(xué)提出）是一種廣泛使用的支持寫回策略的緩存一致性協(xié)議搂妻，該協(xié)議被應(yīng)用在Intel奔騰系列的CPU中蒙保，詳見“support the more efficient write-back cache in addition to the write-through cache previously used by the Intel 486 processor
MESI協(xié)議中的狀態(tài)
CPU中每個(gè)緩存行（caceh line)使用4種狀態(tài)進(jìn)行標(biāo)記（使用額外的兩位(bit)表示):
M: 被修改（Modified)
該緩存行只被緩存在該CPU的緩存中，并且是被修改過的（dirty),即與主存中的數(shù)據(jù)不一致欲主，該緩存行中的內(nèi)存需要在未來的某個(gè)時(shí)間點(diǎn)（允許其它CPU讀取請主存中相應(yīng)內(nèi)存之前）寫回（write back）主存邓厕。當(dāng)被寫回主存之后，該緩存行的狀態(tài)會變成獨(dú)享（exclusive)狀態(tài)扁瓢。
E: 獨(dú)享的（Exclusive)
該緩存行只被緩存在該CPU的緩存中详恼，它是未被修改過的（clean)，與主存中數(shù)據(jù)一致引几。該狀態(tài)可以在任何時(shí)刻當(dāng)有其它CPU讀取該內(nèi)存時(shí)變成共享狀態(tài)（shared)昧互。同樣地，當(dāng)CPU修改該緩存行中內(nèi)容時(shí)伟桅，該狀態(tài)可以變成Modified狀態(tài)敞掘。
S: 共享的（Shared)
該狀態(tài)意味著該緩存行可能被多個(gè)CPU緩存，并且各個(gè)緩存中的數(shù)據(jù)與主存數(shù)據(jù)一致（clean)楣铁，當(dāng)有一個(gè)CPU修改該緩存行中玖雁，其它CPU中該緩存行可以被作廢（變成無效狀態(tài)（Invalid））。
I: 無效的（Invalid）
該緩存是無效的（可能有其它CPU修改了該緩存行）盖腕。
操作：
在一個(gè)典型系統(tǒng)中赫冬，可能會有幾個(gè)緩存（在多核系統(tǒng)中，每個(gè)核心都會有自己的緩存）共享主存總線溃列，每個(gè)相應(yīng)的CPU會發(fā)出讀寫請求劲厌，而緩存的目的是為了減少CPU讀寫共享主存的次數(shù)。
一個(gè)緩存除在Invalid狀態(tài)外都可以滿足cpu的讀請求听隐，一個(gè)invalid的緩存行必須從主存中讀炔贡恰（變成S或者 E狀態(tài)）來滿足該CPU的讀請求。
一個(gè)寫請求只有在該緩存行是M或者E狀態(tài)時(shí)才能被執(zhí)行，如果緩存行處于S狀態(tài)辽幌，必須先將其它緩存中該緩存行變成Invalid狀態(tài)（也既是不允許不同CPU同時(shí)修改同一緩存行增淹，即使修改該緩存行中不同位置的數(shù)據(jù)也不允許）。該操作經(jīng)常作用廣播的方式來完成乌企，例如：Request For Ownership (RFO)
緩存可以隨時(shí)將一個(gè)非M狀態(tài)的緩存行作廢虑润，或者變成Invalid狀態(tài)，而一個(gè)M狀態(tài)的緩存行必須先被寫回主存加酵。
一個(gè)處于M狀態(tài)的緩存行必須時(shí)刻監(jiān)聽所有試圖讀該緩存行相對就主存的操作拳喻，這種操作必須在緩存將該緩存行寫回主存并將狀態(tài)變成S狀態(tài)之前被延遲執(zhí)行。
一個(gè)處于S狀態(tài)的緩存行也必須監(jiān)聽其它緩存使該緩存行無效或者獨(dú)享該緩存行的請求猪腕，并將該緩存行變成無效（Invalid）冗澈。
一個(gè)處于E狀態(tài)的緩存行也必須監(jiān)聽其它緩存讀主存中該緩存行的操作，一旦有這種操作陋葡，該緩存行需要變成S狀態(tài)亚亲。
對于M和E狀態(tài)而言總是精確的，他們在和該緩存行的真正狀態(tài)是一致的腐缤。而S狀態(tài)可能是非一致的捌归，如果一個(gè)緩存將處于S狀態(tài)的緩存行作廢了，而另一個(gè)緩存實(shí)際上可能已經(jīng)獨(dú)享了該緩存行岭粤，但是該緩存卻不會將該緩存行升遷為E狀態(tài)惜索，這是因?yàn)槠渌彺娌粫V播他們作廢掉該緩存行的通知，同樣由于緩存并沒有保存該緩存行的copy的數(shù)量剃浇，因此（即使有這種通知）也沒有辦法確定自己是否已經(jīng)獨(dú)享了該緩存行巾兆。
從上面的意義看來E狀態(tài)是一種投機(jī)性的優(yōu)化：如果一個(gè)CPU想修改一個(gè)處于S狀態(tài)的緩存行，總線事務(wù)需要將所有該緩存行的copy變成invalid狀態(tài)虎囚，而修改E狀態(tài)的緩存不需要使用總線事務(wù)角塑。
好了了解了這些概念后可以來測試了，首先實(shí)現(xiàn)第一個(gè)簡單的自旋鎖 借助AtomicBoolean
package com.alibaba.otter.canal.common;
import java.util.concurrent.atomic.AtomicBoolean;
public class TASLock { //test and set lock 嘗試去set 鎖
AtomicBoolean state = new AtomicBoolean(false);
void lock() {
while (true) {
if (state.compareAndSet(state.get(),true)) {
return;
}
}
}
void unLock() {
state.set(false);
}
}
然后進(jìn)行優(yōu)化先取得是否被占用再去執(zhí)行占用
package com.alibaba.otter.canal.common;
import java.util.concurrent.atomic.AtomicBoolean;
public class TTASLock { // test for first then test set lock
AtomicBoolean state = new AtomicBoolean(false);
void lock() {
while (true) {
while (state.get()) {
}
if (state.compareAndSet(state.get(), true)) {
return;
}
}
}
void unLock() {
state.set(false);
}
}
測試類
package com.alibaba.otter.canal.common;
import java.util.concurrent.CountDownLatch;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import org.junit.After;
import org.junit.Before;
import org.junit.Test;
@SuppressWarnings("restriction")
public class TASTest extends AbstractZkTest {
//并發(fā)線程數(shù)
private final static int NTHREAD = 10;
//計(jì)數(shù)
private static volatile int count = 0;
//最大計(jì)數(shù)
private final static int MAX = 1000000;
//TAS鎖
private static TASLock lock = new TASLock();
//TTAS鎖
// private static TTASLock lock = new TTASLock();
@Before
public void setUp() {
}
@After
public void tearDown() {
}
@Test
public void testUnsafe() throws InterruptedException {
final CountDownLatch endGate = new CountDownLatch(1);
final CountDownLatch startGate = new CountDownLatch(1);
ExecutorService e = Executors.newFixedThreadPool(NTHREAD);
for (int i = 0; i < NTHREAD; i++) {
e.execute(new Runnable() {
@Override
public void run() {
try {
startGate.await();
while (true) {
lock.lock();
if (count < MAX) {
count++;
lock.unLock();
continue;
}
lock.unLock();
break;
}
endGate.countDown();
} catch (InterruptedException ignored) {
}
}
});
}
long start = System.currentTimeMillis();
startGate.countDown();
endGate.await();
long end = System.currentTimeMillis();
long time = end - start;
e.shutdown();
System.out.print(time);
}
@Test
public void testSingleThread() throws InterruptedException {
long start = System.currentTimeMillis();
while (true) {
lock.lock();
if (count < MAX*10) {
count++;
lock.unLock();
continue;
}
lock.unLock();
break;
}
long end = System.currentTimeMillis();
long time = end - start;
System.out.print(time);
}
}
測試結(jié)果淘讥，單線程的執(zhí)行效率最高吉拳，多線程的情況下導(dǎo)致執(zhí)行效率變慢，我的電腦時(shí)4核的适揉，可以見線程的上下文切換很需要時(shí)間，而且CPU容易飆升到100%煤惩，這種情況下反而優(yōu)化后的鎖更浪費(fèi)時(shí)間嫉嘀，因?yàn)镃PU耗盡的原因，所以實(shí)際工作中還是需要結(jié)合服務(wù)器去做測試魄揉。
接下來我們看下著名的CLH鎖和MCS鎖
TAS剪侮、TTAS兩種自旋鎖。這兩種鎖的缺點(diǎn)是：任何一個(gè)處理器每一次對鎖成功的訪問（state.compareAndSet(state.get(),true)和set(false)任意一個(gè)方法的調(diào)用），都會將其他處理器的cache中的緩存失效掉瓣俯。這樣會導(dǎo)致以下后果：
其他處理器無法再采用局部自旋的方式對相同數(shù)據(jù)進(jìn)行訪問杰标，后續(xù)的其他處理器對鎖的訪問都會獨(dú)占bus發(fā)送消息。而鎖的釋放也是需要占用bus彩匕，因此有可能其他處理器對bus的占用而導(dǎo)致鎖的釋放被延遲腔剂；
當(dāng)鎖釋放后的一剎那，其他正在局部自旋的處理器同時(shí)競爭去獲取鎖（調(diào)用state.compareAndSet(state.get(),true)）驼仪，原本只有一個(gè)處理器能在此次競爭中獲勝掸犬，但其他獲取失敗的處理器還是在bus上制造了大量無用的交通阻塞，因此也會導(dǎo)致鎖的釋放被延遲绪爸；
由于數(shù)據(jù)訪問存在局部性湾碎，cache從memory中加載數(shù)據(jù)時(shí)，一次會加載一個(gè)數(shù)據(jù)塊奠货，即cache存儲的是cache line介褥。Cache中鎖狀態(tài)數(shù)據(jù)的失效，會導(dǎo)致其他和鎖狀態(tài)處于同一個(gè)cache line中的數(shù)據(jù)也被失效掉递惋，從而影響其他原本與鎖不存在競爭的處理器的執(zhí)行速度柔滔。
另外，最后一個(gè)缺點(diǎn)就是無法實(shí)現(xiàn)鎖的公平性丹墨，最先自旋等待獲取鎖的處理器廊遍，在競爭中，不一定最先獲取到鎖贩挣。
雖然基于時(shí)間延遲的BackoffTTAS鎖能一定程度的降低cache被無故失效的次數(shù)喉前，但如何設(shè)置最優(yōu)的延遲時(shí)間卻是一個(gè)難題，因?yàn)椴煌钠脚_會有不同的最優(yōu)參數(shù)王财，同時(shí)卵迂，引入延遲后，有可能導(dǎo)致處理器不能及時(shí)的得到鎖绒净，造成無謂的等待见咒。 那么我們希望最理想的情況是：
由于鎖（此處指排它鎖）同一時(shí)刻只能由一個(gè)處理器持有，所以在鎖釋放后的一剎那挂疆，最多只需要通知一個(gè)正在等待持有鎖的處理器去獲取鎖改览，其他處理器就不需要同時(shí)去湊熱鬧了，輪到它的時(shí)候缤言，會自動(dòng)只通知他宝当。
當(dāng)某個(gè)處理器獲取到鎖或者釋放鎖時(shí)，不要失效掉其他還未輪到順序的處理器的cache胆萧，這樣這些處理器就能一直在自己的cache中局部自旋庆揩，不會占用bus。
CLH鎖和MCS鎖就是基于這種理念設(shè)計(jì)出來的
先看CLHLock
package com.alibaba.otter.canal.common;
import java.util.concurrent.atomic.AtomicReferenceFieldUpdater;
public class CLHLock {
public static class CLHNode {
private volatile boolean isLocked = true;
//CLH算法中，每個(gè)申請鎖的線程通過一個(gè)CLHNode 對象表示订晌，
//CLHNode 中有一個(gè)**volatile ****boolean**類型的成員變量isLocked 虏辫，
//isLocked 為true，則表示對應(yīng)的線程已經(jīng)獲取到了鎖或者正在等待獲取鎖锈拨；
//isLocked 為false砌庄，則表示對應(yīng)的線程已經(jīng)釋放了鎖。
}
@SuppressWarnings("unused")
private volatile CLHNode tail;
private static final ThreadLocal<CLHNode> LOCAL = new ThreadLocal<CLHNode>();
private static final AtomicReferenceFieldUpdater<CLHLock, CLHNode> UPDATER = AtomicReferenceFieldUpdater
.newUpdater(CLHLock.class, CLHNode.class, "tail");
public void lock() {
CLHNode node = new CLHNode();
LOCAL.set(node);
CLHNode preNode = UPDATER.getAndSet(this, node);
if (preNode != null) {
while (preNode.isLocked) {
}
preNode = null;
LOCAL.set(node);
}
}
public void unlock() {
CLHNode node = LOCAL.get();
if (!UPDATER.compareAndSet(this, node, null)) {
node.isLocked = false;
}
node = null;
}
}
鎖由多個(gè)CLHNode 對象組成的虛擬鏈表表示推励，之所以稱為虛擬鏈表鹤耍，是因?yàn)镃LHNode 之間并沒有類似于next指針之類的引用，CLHNode 之間通過鎖的一個(gè)本地線程（ThreadLocal）變量LOCAL 相連验辞，preNode 指向當(dāng)前節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)稿黄，即當(dāng)前線程的前一個(gè)線程。而鏈表的尾節(jié)點(diǎn)則通過鎖AtomicReferenceFieldUpdater<CLHLock, CLHNode>類型的tail成員變量指向跌造，即tail指向加入到申請鎖的隊(duì)列中的最近一個(gè)線程杆怕。
當(dāng)一個(gè)線程申請鎖時(shí)：
首先會實(shí)例化一個(gè)CLHNode 節(jié)點(diǎn)，并將其設(shè)置為自己的本地線程變量LOCAL中壳贪；
然后利用 UPDATER.getAndSet(this, node); 得到 前一個(gè)節(jié)點(diǎn) 其實(shí)就是實(shí)例化的 CLHNode 的節(jié)點(diǎn)node 然后在此node上自旋陵珍。
釋放鎖時(shí)：
本地變量中獲得node節(jié)點(diǎn) 然后進(jìn)行tail的指向，釋放鎖 然后歸還對象node违施。
再看一下MCSLock
package com.alibaba.otter.canal.common;
import java.util.concurrent.atomic.AtomicReferenceFieldUpdater;
public class MCSLock {
public static class MCSNode {
volatile MCSNode next;
volatile boolean isLocked = true;
}
private static final ThreadLocal<MCSNode> NODE = new ThreadLocal<MCSNode>();
@SuppressWarnings("unused")
private volatile MCSNode queue;
private static final AtomicReferenceFieldUpdater<MCSLock, MCSNode> UPDATER = AtomicReferenceFieldUpdater.newUpdater(MCSLock.class,
MCSNode.class, "queue");
public void lock() {
MCSNode currentNode = new MCSNode();
NODE.set(currentNode);
MCSNode preNode = UPDATER.getAndSet(this, currentNode);
if (preNode != null) {
preNode.next = currentNode;
while (currentNode.isLocked) {
}
}
}
public void unlock() {
MCSNode currentNode = NODE.get();
if (currentNode.next == null) {
if (UPDATER.compareAndSet(this, currentNode, null)) {
} else {
while (currentNode.next == null) {//隊(duì)列尾發(fā)生了改變互纯，必然有新的節(jié)點(diǎn)正在或者將要添加進(jìn)來，因此循環(huán)等待
}
}
} else {
currentNode.next.isLocked = false;
currentNode.next = null;
}
}
}
MCS隊(duì)列鎖也是為每個(gè)線程分配一個(gè)節(jié)點(diǎn)磕蒲，節(jié)點(diǎn)中任然包含一個(gè)locked屬性留潦，和CLH隊(duì)列鎖不同，MCS隊(duì)列鎖使用一個(gè)真正的隊(duì)列來保存等待線程辣往，因此節(jié)點(diǎn)中還包含一個(gè)next屬性兔院，并且locked屬性的含義也不一樣，在這里表示該線程是否應(yīng)該被阻塞站削，線程將循環(huán)探測自己節(jié)點(diǎn)的locked屬性坊萝，直到該屬性被前續(xù)節(jié)點(diǎn)的線程修改為false。
線程調(diào)用lock后许起，首先獲取自己對應(yīng)的節(jié)點(diǎn)node十偶，并將node設(shè)置為隊(duì)列尾，并返回前續(xù)節(jié)點(diǎn)园细，如果前續(xù)節(jié)點(diǎn)不為空扯键，則表明線程應(yīng)該等待：線程首先將node的locked設(shè)置為true，表示自己將被阻塞珊肃，然后設(shè)置前續(xù)節(jié)點(diǎn)的next指向node，然后就開始循環(huán)直到node的locked屬性被設(shè)置為false。 線程在調(diào)用unlock后伦乔，首先獲取自己對應(yīng)的節(jié)點(diǎn)node厉亏，如果node的next為空，則嘗試將隊(duì)列尾設(shè)置到空烈和，如果成功爱只，則說明隊(duì)列已經(jīng)為空，則退出招刹；否則則說明隊(duì)列尾發(fā)生了變化恬试，需要等待其它線程設(shè)置node的next屬性，最后設(shè)置node的next的locked屬性疯暑，并退出训柴。 MCS隊(duì)列鎖和CLH隊(duì)列鎖具有相同的特點(diǎn)，前續(xù)節(jié)點(diǎn)對狀態(tài)的改變只會影響到后續(xù)的節(jié)點(diǎn)妇拯，不同點(diǎn)是MCS隊(duì)列鎖是在本地cache自旋等待幻馁。
總結(jié)：我個(gè)人覺得MCSLock更好理解 （不知道為啥會這么想，可能是自旋的自己的節(jié)點(diǎn)的狀態(tài) 而 CLHLock是前驅(qū)節(jié)點(diǎn)的狀態(tài)） 適合MUMA系統(tǒng)越锈，因?yàn)樗鉀Q了CLH在NUMA系統(tǒng)架構(gòu)中獲取locked域狀態(tài)內(nèi)存過遠(yuǎn)的問題
