前言

計算機(jī)操作系統(tǒng)是一門“人造的”系統(tǒng)；處處都透露這人類的思考慣性，人性的哲學(xué)原理。從人類本身的處理角度去理解操作系統(tǒng)中線程的各種原理是很有必要的，會讓你對線程的理解更加深刻。

背景

線程模型

基于上述的描述，我們對線程進(jìn)行定義：線程就是在進(jìn)程里一個單獨(dú)的順序控制流。至于進(jìn)程把哪些指令切分成進(jìn)程，后面文章再進(jìn)行分析。下面我們開始養(yǎng)金魚。

養(yǎng)金魚

有一間屋里有三個房間；其中兩個房間住著人（Tom和Jerry），另一個房間養(yǎng)了條金魚；金魚需要兩個人進(jìn)行喂養(yǎng)，金魚有個很大的特點(diǎn)，就是沒有飽的感覺，會不停的吃直到撐死自己；如果兩個人先后都喂養(yǎng)了金魚，金魚就會撐死；如果兩個人先后都沒有喂養(yǎng)金魚，金魚會餓死；（假設(shè)不考慮給兩個人排班的情況，兩個人的行為不受約束）。

上述的兩個人就相當(dāng)于兩個線程，而金魚則是臨界資源；這就是一個線程同步的問題？線程同步的目的就是為了讓多個線程不管執(zhí)行的時候如何穿插，其運(yùn)行結(jié)果都是正確的。

為了養(yǎng)好金魚，Tom和Jerry只能做如下約定： （1）每天喂魚一次，且僅一次； （2）如果今天Tom喂了魚，Jerry今天就不能喂魚了；反之亦然； （3）如果今天有一人沒有喂魚；另一個必須喂魚；不然魚會餓死；

原始階段

在非同步的情況下，Tom和Jerry只能靠經(jīng)驗(yàn)來判斷魚是否已經(jīng)被喂過；比如兩個線程，Tom線程來查看魚是否已喂的時候，發(fā)現(xiàn)魚并沒有喂，準(zhǔn)備進(jìn)行喂食；這個時候線程切換到Jerry，Jerry同樣檢查魚的狀態(tài)，發(fā)現(xiàn)魚還沒有喂，進(jìn)行喂食；然后線程又切回Tom，Tom進(jìn)行喂食；這樣魚撐死了。

留字條階段

由于上述兩個線程都對魚狀態(tài)進(jìn)行了數(shù)據(jù)競爭，同一時刻訪問了同一個數(shù)據(jù)（魚的狀態(tài)）。要防止魚撐死，Tom和Jerry開始商量如何防止數(shù)據(jù)競爭；最簡單的方法就是同一時刻不讓兩個人查看魚的狀態(tài)，這就需要協(xié)調(diào)兩個線程；只有一個線程可以進(jìn)入臨界區(qū)，這稱為互斥。 那怎么確保一次只有一個人在臨界區(qū)呢？ 顯而易見，自然是讓兩個人進(jìn)行交談；如果Tom和Jerry一個早班一個晚班，正常碰不到面，那最簡單的辦法就是留字條；

留字條的做法就相當(dāng)于兩個線程之間的共享內(nèi)存，一個線程對內(nèi)存的修改對另一個線程可見；

于是Tom和Jerry的流程就變成了先去檢查字條；

## Tom, Jerry
if (noNote){
 leave note;
 if (noFeed){
 feed fish;
 }
 remove note;
}

上面的程序看似用了字條這樣的互斥手段，實(shí)際并沒有達(dá)到互斥的目的；金魚依然有撐死的風(fēng)險（當(dāng)兩個程序都進(jìn)入了檢查字條的條件中）；本方案并沒有解決魚撐死的問題，但有所改進(jìn)，降低了魚撐死的概率。

互斥留字條階段

仔細(xì)分析上面留字條的程序，會發(fā)現(xiàn)程序沒有解決的根本原因在于先檢查字條，然后再留字條，這造成了一個空檔，當(dāng)?shù)诙€線程在空檔時切換過去，就造成了魚撐死。

如果修改下順序，先留字條，然后再檢查字條狀態(tài)是否會有用？需要區(qū)分下是誰留的字條。

## Tom
leave noteTom;
if (no noteJerry){
  if (no feed){
    feed fish;
  }
}
remove noteTom;

## Jerry
leave noteJerry;
if (no noteTom){
  if (no feed){
    feed fish;
  }
}
remove noteJerry;

這樣不管線程怎么穿插，總有一個留字條的動作在檢查這個字條之前，這樣就避免了魚撐死的可能。
那這個程序成功了？NO。
如果上述程序兩個穿插執(zhí)行，那么將沒有一個人去喂魚，魚會餓死。因此程序還是不對的，沒有達(dá)到最終的效果。但是對于計算機(jī)而言，餓死對于撐死是一種改善：如果撐死，程序運(yùn)行可能出錯；而餓死，大家都拿不到資源，線程處于阻塞狀態(tài)，停止推進(jìn)，不一定會產(chǎn)生錯誤。

循環(huán)等待階段

分析上面的餓死原因，因?yàn)闆]有人進(jìn)入臨界區(qū)；互斥是保證同一時間只有一個線程進(jìn)入臨界區(qū)；現(xiàn)在是互斥過頭了，兩個線程沒有一個進(jìn)入臨界區(qū)，導(dǎo)致沒有人喂食，魚餓死了。
這個時候就必須保證有一個人一定進(jìn)入臨界區(qū)，怎么辦？
當(dāng)你去買喜茶時，一直買不到，能怎么辦，一直等唄。最粗暴最簡單的方法。
在這邊也是，為了能有一個人進(jìn)入臨界區(qū)，保證魚一定有人喂；因此需要有一個人一直等待，我們暫定Tom。

## Tom
leave noteTom;
while(noteJerry){
  do nothing;
}
if (no feed){
  feed fish;
}
remove noteTom;

檢查下發(fā)現(xiàn)，現(xiàn)在魚不會出現(xiàn)餓死和撐死的情況了，是否大功告成了?

對稱之美

上面的程序解決了金魚的生計問題；但是會帶來兩個問題：
（1）Tom一直在空等待，浪費(fèi)資源；

空等待還可以造成線程優(yōu)先級倒掛的問題；高優(yōu)先級的空等待等待低優(yōu)先級的資源；就像總統(tǒng)要聽平民的話一樣；

（2）Tom和Jerry都是喂金魚的，但是程序不一樣，不是對稱的；Tom要多做事；不美觀，兩套維護(hù)邏輯；
此外，不對稱的程序會增加理論證明的困難，這邊不詳細(xì)展開。

那怎么解決這兩個問題呢？
不好解決。如果去除了空等待，則會出現(xiàn)餓死的情況；如果要對稱，兩邊都是空等待，一樣會造成餓死情況。推進(jìn)似乎走到了盡頭。

鎖階段

我們再看看留字條階段，之所以出現(xiàn)撐死的原因在于：檢查字條和留字條之間出現(xiàn)了空檔，正是這個空檔的存在，導(dǎo)致魚可能會撐死。
從人的角度出發(fā)思考，顯而易見的會想如果這個空檔不出現(xiàn)，是否就不會撐死了???

之前我們的思考都是基于指令級的，在一個非常低的層次上打轉(zhuǎn)；因?yàn)槭侵噶顚拥?，所以就沒辦法消除指令之間的空檔；現(xiàn)在指令層次已經(jīng)無能為力了，應(yīng)該提高抽象層次，將思路上升到一組指令的控制。
在金魚問題中，我們陷入了金魚和字條貼魚缸的層次來思考怎么同步養(yǎng)金魚；那是否可以上升一個層次從放置魚缸的房間的層次來考慮養(yǎng)金魚的問題。

基于上面的分析，檢查字條和留字條我們當(dāng)成一個操作，變相的就是房間上鎖的操作，只能保證一個人進(jìn)入房間（進(jìn)入房間唯一做的事就是喂金魚）；這樣問題就轉(zhuǎn)換為：
（1）如果保證同時只有一個人進(jìn)房間；（防止撐死）
（2）每天必須有一個人進(jìn)房間；（防止餓死）

這在生活中最常見的做法就是：一個人進(jìn)去后鎖門，那么另一個人一定進(jìn)不去該房間。這就是鎖的概念。

##Tom
lock();
if (no feed){
  feed fish;
}
unlock();

##Jerry
lock();
if (no feed){
  feed fish();
}
unlock();

由上述程序可以看出，同一時間只會有一個人進(jìn)入房間進(jìn)行喂食，魚不會撐死；當(dāng)程序執(zhí)行時，總有一個人會進(jìn)入房間進(jìn)行喂食，魚不會餓死；并且程序還是對稱的；完美~~

鎖應(yīng)該具備的特性：

• 鎖的初始狀態(tài)是打開狀態(tài)；
• 進(jìn)入臨界區(qū)前必須獲得鎖；
• 出臨界區(qū)時必須打開鎖；
• 如果別人持有鎖，則必須等待；
  留字條就相當(dāng)于鎖，但是它不滿足于第四個條件，別人持有鎖時，沒有等待，所以不能互斥；

鎖優(yōu)化階段

上述程序完美的實(shí)現(xiàn)了Tom和Jerry的需求，金魚可以很好的生活了；但是運(yùn)行了一段時間后，Tom發(fā)現(xiàn)一個問題；當(dāng)Jerry進(jìn)入房間喂魚時，Tom需要一直等待在外面，而Jerry喂魚比較慢，Tom覺得很浪費(fèi)時間，怎么辦？？？
去除鎖是很不現(xiàn)實(shí)的，因?yàn)榫褪强挎i來保證互斥；但是我們可以減少鎖的時間；喂魚這個耗時動作沒必要放在鎖里；

## Tom
lock();
if (no noteJerry){
  leave noteTom;
}
unlock();
if (no noteJerry){
  if (no feed){
     feed fish;
  }
  remove note;
}

## Jerry
lock();
if (no noteTom){
  leave noteJerry;
}
unlock();
if (no noteTom){
  if (no feed){
    feed fish();
  }
  remove note;
}

這個程序把喂食獨(dú)立出了鎖，相當(dāng)于鎖門只是為了再魚缸上貼個字條，然后在后續(xù)的任意時間段根據(jù)字條來喂食；現(xiàn)在加鎖的步驟只有貼字條，這個動作很快。

睡覺和叫醒階段

不管上述程序鎖的內(nèi)容多么精簡，依然存在這鎖等待的情況；占用CPU資源在空跑，那么怎么解決這種現(xiàn)象？？？
在日常人類生活中，如果需要長時間等待，則最常見的做法是先去做其他事，等過段時間再來看看等待的事有沒有好；或者讓等待完成的事通知你。
計算機(jī)的思想也是一樣的，如果出現(xiàn)等待，那么這個等待的線程需要讓出CPU給其他線程執(zhí)行，這樣才能保證CPU資源利用率最大化。如果對方持有鎖，則不需要等待，而是直接去睡覺；等對方釋放鎖的時候再喚醒你。這就是最典型的生產(chǎn)者和消費(fèi)者的場景。

現(xiàn)在問題升級了?。。?br> Tom和Jerry為了保持魚的活性，在房間里裝了很多通水的管子，魚可以在房間里任意游動；那么生產(chǎn)者和消費(fèi)者在這邊是什么場景？
魚缸是一個固定的投食點(diǎn)，Tom和Jerry是生產(chǎn)者，魚是消費(fèi)者，Tom和Jerry每天定時生產(chǎn)飼料；魚則每天消費(fèi)飼料。
當(dāng)投食點(diǎn)里沒有食物時，魚就去游動或者睡覺；然后每天會自動通知Tom和Jerry進(jìn)行生產(chǎn)飼料；當(dāng)飼料生產(chǎn)出來后，Tom和Jerry會通過超聲波通知魚來吃飯。

int  count=0;
void producer(){
  while(true){
    produce item;
    if (count == 1){
       sleep();
    }
    insert item;
    count = count+1;
    if (count == 1){
       wakeup(consumer);
    }
  }
}

void consumer(){
  while(true){
    if (count==0) sleep();
    remove item;
    count = count - 1;
    if (count == 0) wakeup(producer);
  }
}

上述程序是一個典型的生產(chǎn)者和消費(fèi)者的簡易代碼；會有什么問題嗎？（count共享變量應(yīng)該要加鎖控制，這邊不展示）
比如，消費(fèi)者先執(zhí)行，當(dāng)它判斷現(xiàn)在count==0時，也就是現(xiàn)在還沒有生產(chǎn)任何物品，這個時候CPU切換到了producer；producer生產(chǎn)物品，并一直執(zhí)行到最后的wakeup，由于現(xiàn)在消費(fèi)者還沒有執(zhí)行sleep操作，wakeup相當(dāng)于做了個無用功；之后CPU又切換到了consumer，然后執(zhí)行sleep操作；這樣再執(zhí)行producer時，也會因?yàn)槲锲芬褲M而sleep；問題就來了，producer和consumer都sleep了；整個流程阻塞了，死鎖了。

這個問題的根源在哪？？？
因?yàn)橹暗膚akeup操作丟失了，如果這個wakeup操作沒有丟失，而是保存著，當(dāng)consumer sleep后操作又被執(zhí)行，問題就不存在了。

信號量

信號量：能夠?qū)⑾到y(tǒng)發(fā)送的信號累積起來的操作系統(tǒng)原語。
簡單的來說，信號量就是一個計數(shù)器，其值就是信號累積的數(shù)量。如果將信號量的值限制為0和1，則該信號量就是一把鎖。
上述生產(chǎn)者和消費(fèi)者的問題就可以通過三個信號量來解決。

• mutex：互斥信號量，保證只有一個線程操作緩沖區(qū)；
• full：緩沖區(qū)計數(shù)信號量，商品數(shù)量；
• empty：緩沖區(qū)計數(shù)信號量，緩沖區(qū)空位數(shù)量；

int mutex = 1;
int empty = 1;
int full = 0;
void producer(){
  while(true){
    produce item;
    empty--;
    mutex--;
    insert item;
    mutex++;
    full++;
  }
}

void consumer(){
  while(true){
    full--;
    mutex--;
    remove item;
    mutex++;
    empty++;
  }
}

只有full==0和empty==0同時成立，才會出現(xiàn)生產(chǎn)者和消費(fèi)者同時睡眠的情況，顯然是不成立的。

為啥需要full和empty兩個信號量，因?yàn)樯a(chǎn)者和消費(fèi)者等待的信號不同，需要在不同的信號量上睡眠。

為了實(shí)現(xiàn)線程同步，我們引入了鎖；但是鎖又帶來循環(huán)等待的問題，為此我們又引入了睡覺與叫醒；但又帶來了死鎖的問題，又引入了信號量；操作系統(tǒng)的演化深深的反映著“人造”這兩個字。
那么信號量是不是就是操作系統(tǒng)終極原語了？？？

我們先來看下信號量對于生產(chǎn)者和消費(fèi)者的代碼：
如果將消費(fèi)者的full--和mutex--順序交換下，會出現(xiàn)啥問題；消費(fèi)者先互斥進(jìn)入緩沖區(qū)，然后full--，發(fā)現(xiàn)沒有物品，則等待；這個時候生產(chǎn)者開始執(zhí)行，先empty--，然后mutex--；由于這個時候消費(fèi)者已經(jīng)在緩存區(qū)了，生產(chǎn)者將不能進(jìn)入緩存區(qū)；死鎖；
由此可見信號量的操作順序非常重要，稍有不慎，就容易死鎖；如果一個程序中有幾十個信號量，那么他們之間的順序?qū)⒎浅?fù)雜，編寫這樣的信號量代碼將是非常反人類的，那有什么辦法解決？？？

管程

由于信號量編寫和維護(hù)的復(fù)雜性，很難真正的被應(yīng)用。在人類的哲學(xué)中，每個人擅長的東西不一樣，比如家里的洗衣機(jī)壞了，你不會自己去修，而是找專門的人來修，這就是術(shù)業(yè)有專攻（你不行的時候，把困難交給別人）。因此在操作系統(tǒng)中，信號量的組織工作自己做不了，就交給一個專門的構(gòu)造來負(fù)責(zé)，程序員就解脫了。這個構(gòu)造就是管程。

管程是一個程序語言級別的構(gòu)造，它的正確運(yùn)行是通過編譯器保障的。管程的英文是monitor；是一組子程序、變量和數(shù)據(jù)結(jié)構(gòu)組成，把需要同步的代碼至于管程中，由編譯器保證任何時候只有一個線程在管程中運(yùn)行。

管程有兩種同步機(jī)制：鎖和條件變量。鎖用來控制互斥；條件變量就是線程等待的東西，用來控制執(zhí)行的順序。

一個管程包含了：

• 多個彼此可以交互并且共享資源的線程；
• 多個與資源使用相關(guān)的變量；
• 一個互斥鎖；
• 條件變量；
  管程其實(shí)就是對信號量的面向?qū)ο蟮姆庋b。東尼·霍爾證明了管程與信號量是等價的。管程比信號量更加安全可控，容易差錯。

消息傳遞

那么管程有沒有什么問題呢？
管程最大的問題就是對編譯器的依賴。編譯器在編譯管程時，需要在其前后加上同步原語。
另一個問題是：管程只適用于單機(jī)系統(tǒng)；現(xiàn)在的分布式系統(tǒng)完全不適用。

如果需要在網(wǎng)絡(luò)環(huán)境下進(jìn)行同步，靠的是消息傳遞。消息傳遞分為send和receive兩個操作系統(tǒng)的系統(tǒng)調(diào)用。
以生產(chǎn)者消費(fèi)者為例，生產(chǎn)者先等待空盒消息，如果有空盒，則生成物品，放入盒子，并發(fā)送給消費(fèi)者；消費(fèi)者先發(fā)送空盒消息，然后等待生產(chǎn)者發(fā)送的物品消息，最后再發(fā)送空盒消息，消費(fèi)物品。

消息傳遞的優(yōu)點(diǎn)有很多，是當(dāng)前使用非常普遍的線程同步機(jī)制。同事消息傳遞也有很大的缺點(diǎn)：最大的問題就是消息的丟失和身份識別。
消息在網(wǎng)絡(luò)環(huán)境丟失的概率還是很大的；而且也需要確定你收到的消息確實(shí)是你想要的人發(fā)送的。于是就誕生了很多可靠的協(xié)議，比如TCP；以及用于身份識別的數(shù)字簽名和對稱加密技術(shù)。

總結(jié)

計算機(jī)操作系統(tǒng)演進(jìn)的過程中處處透露出人類的哲學(xué)；從問題分析到解決問題，然后引入問題，再轉(zhuǎn)移問題，解決問題，呈現(xiàn)一個螺旋式上升的過程；明白了這些技術(shù)演進(jìn)的過程，有助于了解技術(shù)適用的基本場景，也有助于更深刻的理解一門技術(shù)。