線程同步可以說(shuō)在日常開(kāi)發(fā)中是用的很多， 但對(duì)于其內(nèi)部如何實(shí)現(xiàn)的，一般人可能知道的并不多。 本篇文章將從如何實(shí)現(xiàn)簡(jiǎn)單的鎖開(kāi)始，介紹linux中的鎖實(shí)現(xiàn)futex的優(yōu)點(diǎn)及原理，最后分析JAVA中同步機(jī)制如wait/notify, synchronized, ReentrantLock。
自己實(shí)現(xiàn)鎖
首先，如果要你實(shí)現(xiàn)操作系統(tǒng)的鎖，該如何實(shí)現(xiàn)？先想想這個(gè)問(wèn)題，暫時(shí)不考慮性能、可用性等問(wèn)題，就用最簡(jiǎn)單、粗暴的方式。當(dāng)你心中有個(gè)大致的思路后，再接著往下看。
下文中的代碼都是偽代碼。
自旋
最容易想到可能是自旋：
volatile int status=0;
void lock(){
while(!compareAndSet(0,1)){
}
//get lock
}
void unlock(){
status=0;
}
boolean compareAndSet(int except,int newValue){
//cas操作,修改status成功則返回true
}
上面的代碼通過(guò)自旋和cas來(lái)實(shí)現(xiàn)一個(gè)最簡(jiǎn)單的鎖。
這樣實(shí)現(xiàn)的鎖顯然有個(gè)致命的缺點(diǎn)：耗費(fèi)cpu資源。沒(méi)有競(jìng)爭(zhēng)到鎖的線程會(huì)一直占用cpu資源進(jìn)行cas操作，假如一個(gè)線程獲得鎖后要花費(fèi)10s處理業(yè)務(wù)邏輯，那另外一個(gè)線程就會(huì)白白的花費(fèi)10s的cpu資源。（假設(shè)系統(tǒng)中就只有這兩個(gè)線程的情況）。
yield+自旋
要解決自旋鎖的性能問(wèn)題必須讓競(jìng)爭(zhēng)鎖失敗的線程不忙等,而是在獲取不到鎖的時(shí)候能把cpu資源給讓出來(lái)，說(shuō)到讓cpu資源，你可能想到了yield()方法，看看下面的例子：
volatile int status=0;
void lock(){
while(!compareAndSet(0,1)){
yield();
}
//get lock
}
void unlock(){
status=0;
}
當(dāng)線程競(jìng)爭(zhēng)鎖失敗時(shí)，會(huì)調(diào)用yield方法讓出cpu。需要注意的是該方法只是當(dāng)前讓出cpu，有可能操作系統(tǒng)下次還是選擇運(yùn)行該線程。其實(shí)現(xiàn)是 將當(dāng)期線程移動(dòng)到所在優(yōu)先調(diào)度隊(duì)列的末端（操作系統(tǒng)線程調(diào)度了解一下？有時(shí)間的話，下次寫(xiě)寫(xiě)這塊內(nèi)容）。也就是說(shuō)，如果該線程處于優(yōu)先級(jí)最高的調(diào)度隊(duì)列且該隊(duì)列只有該線程，那操作系統(tǒng)下次還是運(yùn)行該線程。
自旋+yield的方式并沒(méi)有完全解決問(wèn)題，當(dāng)系統(tǒng)只有兩個(gè)線程競(jìng)爭(zhēng)鎖時(shí)，yield是有效的。但是如果有100個(gè)線程競(jìng)爭(zhēng)鎖，當(dāng)線程1獲得鎖后，還有99個(gè)線程在反復(fù)的自旋+yield，線程2調(diào)用yield后，操作系統(tǒng)下次運(yùn)行的可能是線程3；而線程3CAS失敗后調(diào)用yield后，操作系統(tǒng)下次運(yùn)行的可能是線程4... 假如運(yùn)行在單核cpu下，在競(jìng)爭(zhēng)鎖時(shí)最差只有1%的cpu利用率，導(dǎo)致獲得鎖的線程1一直被中斷，執(zhí)行實(shí)際業(yè)務(wù)代碼時(shí)間變得更長(zhǎng)，從而導(dǎo)致鎖釋放的時(shí)間變的更長(zhǎng)。
sleep+自旋
你可能從一開(kāi)始就想到了，當(dāng)競(jìng)爭(zhēng)鎖失敗后，可以將用Thread.sleep將線程休眠，從而不占用cpu資源：
volatile int status=0;
void lock(){
while(!compareAndSet(0,1)){
sleep(10);
}
//get lock
}
void unlock(){
status=0;
}
上述方式我們可能見(jiàn)的比較多，通常用于實(shí)現(xiàn)上層鎖。該方式不適合用于操作系統(tǒng)級(jí)別的鎖，因?yàn)樽鳛橐粋€(gè)底層鎖，其sleep時(shí)間很難設(shè)置。sleep的時(shí)間取決于同步代碼塊的執(zhí)行時(shí)間，sleep時(shí)間如果太短了，會(huì)導(dǎo)致線程切換頻繁（極端情況和yield方式一樣）；sleep時(shí)間如果設(shè)置的過(guò)長(zhǎng)，會(huì)導(dǎo)致線程不能及時(shí)獲得鎖。因此沒(méi)法設(shè)置一個(gè)通用的sleep值。就算sleep的值由調(diào)用者指定也不能完全解決問(wèn)題：有的時(shí)候調(diào)用鎖的人也不知道同步塊代碼會(huì)執(zhí)行多久。
park+自旋
那可不可以在獲取不到鎖的時(shí)候讓線程釋放cpu資源進(jìn)行等待，當(dāng)持有鎖的線程釋放鎖的時(shí)候?qū)⒌却木€程喚起呢？
volatile int status=0;
Queue parkQueue;
void lock(){
while(!compareAndSet(0,1)){
//
lock_wait();
}
//get lock
}
void synchronized unlock(){
lock_notify();
}
void lock_wait(){
//將當(dāng)期線程加入到等待隊(duì)列
parkQueue.add(nowThread);
//將當(dāng)期線程釋放cpu
releaseCpu();
}
void lock_notify(){
//得到要喚醒的線程
Thread t=parkList.poll();
//喚醒等待線程
wakeAThread(t);
}
上面是偽代碼，描述這種設(shè)計(jì)思想，至于釋放cpu資源、喚醒等待線程的的具體實(shí)現(xiàn)，后文會(huì)再說(shuō)。這種方案相比于sleep而言，只有在鎖被釋放的時(shí)候，競(jìng)爭(zhēng)鎖的線程才會(huì)被喚醒，不會(huì)存在過(guò)早或過(guò)完喚醒的問(wèn)題。
小結(jié)
對(duì)于鎖沖突不嚴(yán)重的情況，用自旋鎖會(huì)更適合，試想每個(gè)線程獲得鎖后很短的一段時(shí)間內(nèi)就釋放鎖，競(jìng)爭(zhēng)鎖的線程只要經(jīng)歷幾次自旋運(yùn)算后就能獲得鎖，那就沒(méi)必要等待該線程了，因?yàn)榈却€程意味著需要進(jìn)入到內(nèi)核態(tài)進(jìn)行上下文切換，而上下文切換是有成本的并且還不低，如果鎖很快就釋放了，那上下文切換的開(kāi)銷將超過(guò)自旋。
目前操作系統(tǒng)中，一般是用自旋+等待結(jié)合的形式實(shí)現(xiàn)鎖：在進(jìn)入鎖時(shí)先自旋一定次數(shù)，如果還沒(méi)獲得鎖再進(jìn)行等待。
futex
linux底層用futex實(shí)現(xiàn)鎖，futex由一個(gè)內(nèi)核層的隊(duì)列和一個(gè)用戶空間層的atomic integer構(gòu)成。當(dāng)獲得鎖時(shí)，嘗試cas更改integer，如果integer原始值是0，則修改成功，該線程獲得鎖，否則就將當(dāng)期線程放入到 wait queue中（即操作系統(tǒng)的等待隊(duì)列）。
上述說(shuō)法有些抽象，如果你沒(méi)看明白也沒(méi)關(guān)系。我們先看一下沒(méi)有futex之前，linux是怎么實(shí)現(xiàn)鎖的。
futex誕生之前
在futex誕生之前，linux下的同步機(jī)制可以歸為兩類：用戶態(tài)的同步機(jī)制 和內(nèi)核同步機(jī)制。 用戶態(tài)的同步機(jī)制基本上就是利用原子指令實(shí)現(xiàn)的自旋鎖。關(guān)于自旋鎖其缺點(diǎn)也說(shuō)過(guò)了，不適用于大的臨界區(qū)（即鎖占用時(shí)間比較長(zhǎng)的情況）。
內(nèi)核提供的同步機(jī)制，如semaphore等，使用的是上文說(shuō)的自旋+等待的形式。 它對(duì)于大小臨界區(qū)和都適用。但是因?yàn)樗莾?nèi)核層的（釋放cpu資源是內(nèi)核級(jí)調(diào)用），所以每次lock與unlock都是一次系統(tǒng)調(diào)用，即使沒(méi)有鎖沖突，也必須要通過(guò)系統(tǒng)調(diào)用進(jìn)入內(nèi)核之后才能識(shí)別。
理想的同步機(jī)制應(yīng)該是沒(méi)有鎖沖突時(shí)在用戶態(tài)利用原子指令就解決問(wèn)題，而需要掛起等待時(shí)再使用內(nèi)核提供的系統(tǒng)調(diào)用進(jìn)行睡眠與喚醒。換句話說(shuō)，在用戶態(tài)的自旋失敗時(shí)，能不能讓進(jìn)程掛起，由持有鎖的線程釋放鎖時(shí)將其喚醒？ 如果你沒(méi)有較深入地考慮過(guò)這個(gè)問(wèn)題，很可能想當(dāng)然的認(rèn)為類似于這樣就行了（偽代碼）：
void lock(int lockval) {
//trylock是用戶級(jí)的自旋鎖
while(!trylock(lockval)) {
wait();//釋放cpu，并將當(dāng)期線程加入等待隊(duì)列，是系統(tǒng)調(diào)用
}
}
boolean trylock(int lockval){
int i=0;
//localval=1代表上鎖成功
while(!compareAndSet(lockval,0,1)){
if(++i>10){
return false;
}
}
return true;
}
void unlock(int lockval) {
compareAndSet(lockval,1,0);
notify();
}
上述代碼的問(wèn)題是trylock和wait兩個(gè)調(diào)用之間存在一個(gè)窗口： 如果一個(gè)線程trylock失敗，在調(diào)用wait時(shí)持有鎖的線程釋放了鎖，當(dāng)前線程還是會(huì)調(diào)用wait進(jìn)行等待，但之后就沒(méi)有人再將該線程喚醒了。
futex誕生之后
我們來(lái)看看futex的方法定義：
//uaddr指向一個(gè)地址，val代表這個(gè)地址期待的值，當(dāng)*uaddr==val時(shí)，才會(huì)進(jìn)行wait int futex_wait(int *uaddr, int val); //喚醒n個(gè)在uaddr指向的鎖變量上掛起等待的進(jìn)程 int futex_wake(int *uaddr, int n);
futex_wait真正將進(jìn)程掛起之前會(huì)檢查addr指向的地址的值是否等于val，如果不相等則會(huì)立即返回，由用戶態(tài)繼續(xù)trylock。否則將當(dāng)期線程插入到一個(gè)隊(duì)列中去，并掛起。
futex內(nèi)部維護(hù)了一個(gè)隊(duì)列，在線程掛起前會(huì)線程插入到其中，同時(shí)對(duì)于隊(duì)列中的每個(gè)節(jié)點(diǎn)都有一個(gè)標(biāo)識(shí)，代表該線程關(guān)聯(lián)鎖的uaddr。這樣，當(dāng)用戶態(tài)調(diào)用futex_wake時(shí)，只需要遍歷這個(gè)等待隊(duì)列，把帶有相同uaddr的節(jié)點(diǎn)所對(duì)應(yīng)的進(jìn)程喚醒就行了。
作為優(yōu)化，futex維護(hù)的其實(shí)是個(gè)類似java 中的concurrent hashmap的結(jié)構(gòu)。其持有一個(gè)總鏈表，總鏈表中每個(gè)元素都是一個(gè)帶有自旋鎖的子鏈表。調(diào)用futex_wait掛起的進(jìn)程，通過(guò)其uaddr hash到某一個(gè)具體的子鏈表上去。這樣一方面能分散對(duì)等待隊(duì)列的競(jìng)爭(zhēng)、另一方面減小單個(gè)隊(duì)列的長(zhǎng)度，便于futex_wake時(shí)的查找。每個(gè)鏈表各自持有一把spinlock，將"*uaddr和val的比較操作"與"把進(jìn)程加入隊(duì)列的操作"保護(hù)在一個(gè)臨界區(qū)中。 另外，futex是支持多進(jìn)程的，當(dāng)使用futex在多進(jìn)程間進(jìn)行同步時(shí)，需要考慮同一個(gè)物理內(nèi)存地址在不同進(jìn)程中的虛擬地址是不同的。
