上一篇計(jì)算機(jī)系統(tǒng)009 - 操作系統(tǒng)之進(jìn)程中講述了操作系統(tǒng)設(shè)立進(jìn)程、線程的概念主要是為了便于切換管理慈缔，同時(shí)也提到蚯根，在單處理器結(jié)構(gòu)系統(tǒng)中，進(jìn)行進(jìn)程或線程級(jí)別的切換可以在承擔(dān)一定切換消耗后降低平均響應(yīng)時(shí)長(zhǎng)胀糜。而隨著硬件技術(shù)的發(fā)展颅拦，主要是多處理器架構(gòu)的興起，操作系統(tǒng)中并行的概念也逐漸成為主流教藻。

既然提到多處理器架構(gòu)的興起距帅，也就再多說(shuō)幾句。最開始那段時(shí)間括堤，也就是電氣CPU的年代碌秸，CPU既重又笨。第一次飛躍是隨著晶體管硬件技術(shù)的革新而來(lái)悄窃，主頻得到了極大提升讥电，隨后的第二次飛躍則是由集成電路所推動(dòng)。發(fā)展到了這里轧抗，CPU制造商卻發(fā)現(xiàn)通過(guò)提升主頻恩敌、緩存所能換來(lái)的提升效益與成本相比，性價(jià)比很低横媚。自然地纠炮，有一波人就打起了量的主意。通過(guò)將多個(gè)CPU核心灯蝴，甚至多個(gè)CPU本身集成入芯片恢口，同時(shí)處理多個(gè)可分割的計(jì)算任務(wù)，達(dá)到降低平均執(zhí)行時(shí)長(zhǎng)的目的穷躁。簡(jiǎn)單的來(lái)說(shuō)耕肩，就是通過(guò)增加更多的服務(wù)窗口，使得排隊(duì)的時(shí)間減少问潭，進(jìn)而減少整體執(zhí)行時(shí)間猿诸。

1. 并行

介紹其他內(nèi)容之前，先對(duì)并行睦授、并發(fā)兩個(gè)概念稍加說(shuō)明两芳。理解這兩個(gè)概念時(shí)可以類比程序和進(jìn)程的概念摔寨，具體如下：

• 并發(fā)Concurrency
  Concurrency是指程序去枷、算法或問(wèn)題本身可分解為順序無(wú)關(guān)或不完全依賴執(zhí)行順序單元的屬性，從語(yǔ)法來(lái)講，并發(fā)雖然是一個(gè)名詞删顶，但可以看成是表達(dá)為擁有某種能力的形容詞竖螃。也就是說(shuō)假如一個(gè)程序具有并發(fā)的屬性，那么即使將分解后單元以亂序或局部順序執(zhí)行逗余，最終結(jié)果也不會(huì)受影響特咆，這為單元并列執(zhí)行提供了基礎(chǔ)。
  簡(jiǎn)而言之录粱，并發(fā)是只程序在結(jié)構(gòu)上擁有一種能力腻格，與執(zhí)行本身無(wú)關(guān)。

• 并行Parallelism
  如前所述啥繁，并行的全稱可以視為并列執(zhí)行菜职，Parallelism指的是多個(gè)單元或多個(gè)任務(wù)正在同時(shí)執(zhí)行，強(qiáng)調(diào)的是一種現(xiàn)象旗闽。如果說(shuō)并發(fā)是靜態(tài)的程序能力酬核，那么并行就是這種能力動(dòng)態(tài)發(fā)揮作用的現(xiàn)象本身。

插一句題外話适室，由于目前使用的大部分計(jì)算機(jī)系統(tǒng)概念都形成于西方嫡意，所使用的語(yǔ)言也以英文為主，漢化翻譯的過(guò)程中捣辆，有時(shí)候很難找到十分貼切的詞匯去映射抽象的概念本體蔬螟，導(dǎo)致直面概念的中文詞匯（如進(jìn)程、線程汽畴、纖程促煮、并行、并發(fā)）時(shí)很難獲取到精確理解整袁。這時(shí)候菠齿，還是建議先找到概念的英文表示，從英文本身的解釋出發(fā)坐昙，融匯理解绳匀。

1.1 并行核心問(wèn)題

回到并行本身，并行的最大特征是同時(shí)執(zhí)行炸客，那么對(duì)應(yīng)的硬件前提就是切實(shí)存在多個(gè)CPU核心甚至多個(gè)CPU疾棵，以此支持線程、進(jìn)程的調(diào)度痹仙。前面的章節(jié)中我們講到是尔，進(jìn)程、線程本身是需要使用地址空間开仰、椖饷叮空間薪铜、以及其他相關(guān)硬件資源的。按照單處理器架構(gòu)執(zhí)行時(shí)恩溅，始終能保證同一時(shí)刻隔箍，只會(huì)有一個(gè)進(jìn)程或線程運(yùn)行，所以在資源共享這一塊不會(huì)出現(xiàn)太多問(wèn)題脚乡。但在多處理器多核架構(gòu)下多個(gè)進(jìn)程蜒滩、線程同時(shí)執(zhí)行，隨時(shí)有可能發(fā)生兩個(gè)進(jìn)程奶稠、線程需要使用同一資源（包括CPU時(shí)間俯艰、存儲(chǔ)器、文件以及I/O設(shè)備等）的現(xiàn)象锌订。

舉個(gè)例子蟆炊，大部分人應(yīng)該都有包餃子的經(jīng)歷，假如現(xiàn)在有一碗餡料瀑志，里面只有一根勺子涩搓，那么當(dāng)只有一個(gè)人在包餃子時(shí)，他可以隨時(shí)獲取到勺子的使用權(quán)劈猪，并在不用時(shí)將其閑置等待昧甘；假如現(xiàn)在還是一根勺子，但有兩個(gè)人在包餃子战得，由于大家包餃子的節(jié)奏肯定不會(huì)絕對(duì)相同充边，那么在獲取勺子使用權(quán)時(shí)就存在如下幾種情況：

• 對(duì)方使用中，你只能選擇等待
• 對(duì)方未使用常侦，直接獲取浇冰，使用期間如對(duì)方需使用，同樣需等待
• 雙方同一時(shí)刻伸手獲取勺子使用權(quán)

前面兩種還好聋亡，既不會(huì)太閑置肘习，也能和諧進(jìn)行。但第三種情況就尷尬了坡倔，到底誰(shuí)該縮回伸出去的手漂佩？雖然無(wú)比尷尬，但既然發(fā)生了問(wèn)題罪塔，終歸還是要解決的投蝉。從包餃子的所遇到的問(wèn)題中，可以發(fā)現(xiàn)并行的兩大核心問(wèn)題是同步和通信征堪，同步時(shí)為了互斥瘩缆，通信是為了合作。

1.2 同步Synchronization

同步佃蚜，英文表示為Synchronization庸娱，生活中的解釋是協(xié)調(diào)事件共同操作某一系統(tǒng)着绊，而在計(jì)算機(jī)領(lǐng)域，這個(gè)同步指代兩個(gè)方面的同步：

• 進(jìn)程同步
  多個(gè)進(jìn)程在某一特定位置進(jìn)行連接或握手涌韩，以確保達(dá)成共識(shí)或基于指定次序執(zhí)行畔柔。

• 數(shù)據(jù)同步
  數(shù)據(jù)同步是指保持同一數(shù)據(jù)集多個(gè)備份的一致性氯夷，或是保證數(shù)據(jù)完整性臣樱。

上述說(shuō)明的關(guān)鍵點(diǎn)是確保事件的發(fā)生基于指定次序，萬(wàn)事總得講究個(gè)先來(lái)后到腮考，哪怕我比你早一毫秒碰到了勺子雇毫，那也是先來(lái)，理應(yīng)優(yōu)先響應(yīng)踩蔚，獲得使用權(quán)棚放。你要想獲得勺子的使用權(quán)，可以先跟我確認(rèn)馅闽，看我狀態(tài)飘蚯，看我心情給不給你用。如果我不給福也，那你就乖乖等著局骤，等我用完了再用。

所以伴隨著同步的是潛在互斥的結(jié)果暴凑，任何時(shí)刻峦甩，只允許一個(gè)人使用某一特定資源，比如內(nèi)存中某一字節(jié)现喳，又比如打印設(shè)備等凯傲。通常對(duì)于互斥的硬件層的支持有兩種：

• 中斷禁用
  一旦獲得使用權(quán)后立即禁止中斷，直到使用結(jié)束后重新允許中斷嗦篱。既然本進(jìn)程無(wú)法被中斷冰单，自然就不存在資源沖突的問(wèn)題。中斷禁用的問(wèn)題是只適用于單處理器結(jié)構(gòu)的系統(tǒng)灸促，多處理器結(jié)構(gòu)中球凰，每個(gè)CPU有自己的中斷控制，而進(jìn)程中只能禁止所分配到的CPU的中斷腿宰，無(wú)法真正防止其他CPU中進(jìn)程獲取同一資源而引發(fā)沖突呕诉。

• 專用機(jī)器指令
  將兩個(gè)動(dòng)作在一個(gè)指令周期內(nèi)完成來(lái)保證操作整體的原子性，實(shí)現(xiàn)互斥吃度。如在一個(gè)指令周期內(nèi)完成讀-寫或讀-測(cè)試兩條指令甩挫，指令執(zhí)行期間會(huì)阻塞其他指令的訪問(wèn)，以達(dá)成資源級(jí)別的互斥椿每。

1.3 通信

前面提到伊者，假如我正在使用勺子英遭，而你希望使用，那就必須等待我使用結(jié)束亦渗，或是跟我兩目對(duì)視挖诸，會(huì)心一笑讓中斷下來(lái)讓你先用。操作系統(tǒng)中法精，進(jìn)程或線程也需要通過(guò)通信來(lái)確認(rèn)資源當(dāng)前使用情況多律，有效的信息能夠幫助進(jìn)程及時(shí)獲取資源使用權(quán)。

通常進(jìn)程（線程）之間會(huì)以如下三種狀態(tài)共存：

• 雙方都不知道對(duì)方存在
  雙方都不知道對(duì)方的存在搂蜓，那就只有操作系統(tǒng)掌握了雙方的關(guān)系狼荞。例如兩個(gè)進(jìn)程都同時(shí)希望使用打印設(shè)備，假設(shè)該打印設(shè)備任一時(shí)刻只能服務(wù)于單個(gè)進(jìn)程帮碰，那么操作系統(tǒng)就必須保證兩者互斥相味，不去同時(shí)操作打印設(shè)備。當(dāng)然殉挽，現(xiàn)在的打印設(shè)備會(huì)在打印執(zhí)行單元前將打印任務(wù)序列化丰涉，所以同時(shí)提交也能支持，只不過(guò)內(nèi)部依然是依次執(zhí)行單個(gè)打印任務(wù)的斯碌。

• 雙方間接知道對(duì)方的存在
  通過(guò)共享對(duì)象來(lái)達(dá)成通信一死，如生產(chǎn)者、消費(fèi)者输拇，除了生產(chǎn)摘符、消費(fèi)兩個(gè)特性外，他們均不知道各自更多的信息策吠。

• 雙方直接知道對(duì)方的存在
  直接知道意味著知道對(duì)方進(jìn)程的基本信息逛裤，如進(jìn)程ID。有了進(jìn)程ID猴抹，就可以建立兩者通信的專用線路带族。類似而言，假如大家都在某一共享空間如留言板上匿名留言蟀给，為了繼續(xù)通信蝙砌，也只能在留言板上回復(fù)。而如果我知道對(duì)方真正ID跋理，那么就可以直接私信進(jìn)行交流了择克。

基于以上三種共存狀態(tài)，進(jìn)程間為了完成合作前普，也需要使用不同的通信機(jī)制肚邢。

2. 通信機(jī)制

對(duì)于通信機(jī)制的理解，應(yīng)回歸到適用的場(chǎng)景本身。

2.1 信號(hào)量Semaphore

在通信雙方都不知道對(duì)方存在的條件下骡湖，要想完成通信贱纠，那么必須考慮通過(guò)操作系統(tǒng)完成同步，這一部分直接由操作系統(tǒng)全局統(tǒng)籌實(shí)現(xiàn)响蕴。而在雙方間接知道對(duì)方的情況下谆焊，最典型的方法就是信號(hào)量。信號(hào)量的基本原理是：兩個(gè)或多個(gè)進(jìn)程可以通過(guò)簡(jiǎn)單的信號(hào)進(jìn)行合作浦夷，一個(gè)進(jìn)程可以被迫在某一位置停止辖试，直到它接收到一個(gè)特定的信號(hào)。通過(guò)調(diào)整信號(hào)結(jié)構(gòu)军拟，理論上任何復(fù)雜的合作需求都可以得到滿足剃执。

信號(hào)量實(shí)質(zhì)上可視為一個(gè)具有整數(shù)值的變量誓禁，該變量支持三個(gè)操作：

• 初始化懈息，賦值一個(gè)非負(fù)整數(shù)
• signal()，離開臨界區(qū)塊時(shí)使用摹恰，增加信號(hào)量值辫继，當(dāng)信號(hào)量不為負(fù)值時(shí)，處于wait()中進(jìn)程將恢復(fù)運(yùn)行俗慈，進(jìn)入臨界區(qū)姑宽。
• wait()，進(jìn)入臨界區(qū)塊時(shí)使用闺阱，減少信號(hào)量值炮车，當(dāng)信號(hào)量為負(fù)值時(shí)，被阻塞酣溃；為非負(fù)時(shí)瘦穆，可以繼續(xù)。

其邏輯可以換位到銀行窗口服務(wù)與客戶的關(guān)系赊豌，服務(wù)窗口數(shù)量就是信號(hào)量扛或。

• 銀行初始化提供了N個(gè)窗口，等價(jià)于信號(hào)量值初始化為N

• 客戶來(lái)到銀行大廳碘饼，使用wait()申請(qǐng)一個(gè)窗口服務(wù)熙兔，申請(qǐng)后N值減1

  • 如N-1>0，表明申請(qǐng)前N>1艾恼，即申請(qǐng)后仍有窗口富余
  • 如N-1=0住涉，表明申請(qǐng)前N=1，即申請(qǐng)到了最后一個(gè)服務(wù)窗口
  • 如N-1<0钠绍，表明申請(qǐng)前N<=0舆声，即原本就沒有服務(wù)窗口

• 客戶使用完服務(wù)窗口后，發(fā)出signal()信號(hào)五慈，發(fā)出后N值加1纳寂。當(dāng)N+1后不再為負(fù)值主穗，原先被wait()阻塞的進(jìn)程就能繼續(xù)運(yùn)行。即其他等待的客戶就可以使用服務(wù)窗口了

信號(hào)量初始值代表著wait()被阻塞前所支持的進(jìn)程/線程最大數(shù)目毙芜，當(dāng)該值可為任意整數(shù)時(shí)忽媒，稱為計(jì)數(shù)信號(hào)量。而如果信號(hào)量初始值只能為1腋粥，也就是說(shuō)信號(hào)量值只能在0/1間變化晦雨，那么該信號(hào)量也稱為二進(jìn)制信號(hào)量。通常的實(shí)現(xiàn)稱為Mutex隘冲，即互斥量闹瞧。和廣泛分布在整個(gè)程序中的計(jì)數(shù)信號(hào)量相比，Mutex通常只用在同一線程中展辞，即signal()/wait()均應(yīng)由同一線程調(diào)用奥邮。

2.2 管程(Monitor)

管程提供和信號(hào)量相似的功能，而且在使用上更加易于控制罗珍。管程由一至多個(gè)程序洽腺、一個(gè)初始化序列以及局部數(shù)據(jù)組合而成。其主要特征是：

• 只能通過(guò)管程提供的內(nèi)部程序訪問(wèn)數(shù)據(jù)變量
• 每個(gè)進(jìn)程通過(guò)管程提供的程序之一進(jìn)行訪問(wèn)
• 任一時(shí)刻管程中只能執(zhí)行一個(gè)程序覆旱，其他程序均被阻塞直到管程重新可用

前兩個(gè)特征與面向?qū)ο蠓庋b類似蘸朋，最后一個(gè)特征則是互斥的體現(xiàn)。簡(jiǎn)而言之扣唱，管程就是通過(guò)分配有限的訪問(wèn)渠道給進(jìn)程藕坯，并保證任一時(shí)刻只能由一個(gè)渠道訪問(wèn)數(shù)據(jù)，達(dá)到保護(hù)數(shù)據(jù)的目的噪沙。再通俗一點(diǎn)炼彪，管程就像是一個(gè)有多扇門的房間，房間里面儲(chǔ)存了一些物品曲聂，任一時(shí)刻只要有人進(jìn)入房間霹购，就將所有門反鎖。完成對(duì)物品的操作后朋腋，再取消反鎖齐疙，退出房間。

2.3 消息傳遞

和現(xiàn)實(shí)生活中一樣旭咽，消息傳遞的目的是為了將某些訊息告知對(duì)方贞奋，便于對(duì)方及時(shí)做出反應(yīng)。進(jìn)程間傳遞消息也是為了告知對(duì)方發(fā)生了什么事件穷绵、切換到什么狀態(tài)等變化轿塔。消息要想被雙方理解，就要遵循相同的格式。通用的消息格式如下圖所示：

除去消息類型勾缭，最主要的字段應(yīng)該是源ID和目標(biāo)ID揍障，分別代表了消息的發(fā)送者和接收者。對(duì)于同一主機(jī)而言俩由，這可以是相互區(qū)別的進(jìn)程ID即可毒嫡，對(duì)于網(wǎng)絡(luò)中的不同主機(jī)而言，該字段則需添加上網(wǎng)絡(luò)中進(jìn)行唯一標(biāo)示的IP地址幻梯。

3. 典型并行問(wèn)題

要想進(jìn)一步理解各種通信機(jī)制兜畸，還是要回歸到問(wèn)題本身。并行過(guò)程中之所以會(huì)產(chǎn)生問(wèn)題碘梢，關(guān)鍵在于對(duì)同一資源的競(jìng)爭(zhēng)咬摇，如果不能協(xié)調(diào)各進(jìn)程/線程有序訪問(wèn)該資源，就會(huì)使得依賴于資源值的進(jìn)程因?yàn)橹靛e(cuò)誤而導(dǎo)致運(yùn)行錯(cuò)誤煞躬。

3.1 生產(chǎn)-消費(fèi)者問(wèn)題

生產(chǎn)-消費(fèi)者問(wèn)題也稱為有限緩沖問(wèn)題肛鹏，是一個(gè)經(jīng)典的多線程同步問(wèn)題。該問(wèn)題中有如下三個(gè)主體：

• 固定大小的共享緩沖區(qū)
• 生產(chǎn)者線程汰翠，負(fù)責(zé)重復(fù)生成一定數(shù)據(jù)并存放到緩沖區(qū)中
• 消費(fèi)者線程龄坪，負(fù)責(zé)重復(fù)消耗緩沖區(qū)中數(shù)據(jù)

問(wèn)題關(guān)鍵在于確保生產(chǎn)者不會(huì)在緩沖區(qū)滿時(shí)寫入數(shù)據(jù)昭雌，消費(fèi)者也不會(huì)在緩沖區(qū)中為空時(shí)消耗數(shù)據(jù)复唤。換句話說(shuō)，緩沖區(qū)中可用部分的多少是關(guān)鍵數(shù)據(jù)烛卧。

3.2 讀者-寫者問(wèn)題

讀者-寫者問(wèn)題發(fā)生在多個(gè)線程讀或?qū)懲还蚕碣Y源時(shí)佛纫，通常，任一時(shí)刻只允許有一個(gè)線程寫資源总放，且如有線程正在寫資源呈宇，則所有讀操作也會(huì)被阻塞。如無(wú)線程正在寫局雄，則多個(gè)線程可同時(shí)讀取該資源甥啄。

通用的解決方案是使用讀寫鎖，該鎖中可將讀與寫操作互斥炬搭，而在讀本身上使用信號(hào)量進(jìn)行計(jì)數(shù)即可蜈漓。

4. 總結(jié)

本篇概念較多，希望通過(guò)多次對(duì)比例證能夠?qū)?wèn)題進(jìn)行降解宫盔。文中提及并行由來(lái)融虽、并行過(guò)程中潛在典型問(wèn)題以及相應(yīng)的解決辦法，但到目前為止灼芭，仍止步于可能由于對(duì)單一資源競(jìng)爭(zhēng)引發(fā)沖突有额。事實(shí)上，再往壞處想，假如涉及到的資源也從單一變成了多個(gè)（如哲學(xué)家就餐問(wèn)題）巍佑，那么多個(gè)進(jìn)程/線程與多個(gè)資源間的相互競(jìng)爭(zhēng)則會(huì)引發(fā)更大的災(zāi)難茴迁。而這，也就是不得不單獨(dú)開篇去闡述“死鎖”的緣由萤衰。