并發(fā)面試必備系列之并發(fā)基礎(chǔ)與內(nèi)存模型

坐標(biāo)上海松江高科技園，誠(chéng)聘高級(jí)前端工程師/高級(jí) Java 工程師，有興趣的看 JD：https://www.lagou.com/jobs/6361564.html

并發(fā)面試必備系列之并發(fā)基礎(chǔ)與內(nèi)存模型

在 《Awesome Interviews》 歸納的常見(jiàn)面試題中，無(wú)論前后端，并發(fā)與異步的相關(guān)知識(shí)都是面試的中重中之重，本系列即對(duì)于面試中常見(jiàn)的并發(fā)知識(shí)再進(jìn)行回顧總結(jié)；你也可以前往 《Awesome Interviews》，在實(shí)際的面試題考校中了解自己的掌握程度。也可以前往《Java 實(shí)戰(zhàn)》、《Go 實(shí)戰(zhàn)》等了解具體編程語(yǔ)言中的并發(fā)編程的相關(guān)知識(shí)。

隨著硬件性能的迅猛發(fā)展與大數(shù)據(jù)時(shí)代的來(lái)臨，為了讓代碼運(yùn)行得更快，單純依靠更快的硬件已無(wú)法滿足要求，并行和分布式計(jì)算是現(xiàn)代應(yīng)用程序的主要內(nèi)容；我們需要利用多個(gè)核心或多臺(tái)機(jī)器來(lái)加速應(yīng)用程序或大規(guī)模運(yùn)行它們，并發(fā)編程日益成為編程中不可忽略的重要組成部分。

簡(jiǎn)單定義來(lái)看，如果執(zhí)行單元的邏輯控制流在時(shí)間上重疊，那它們就是并發(fā)（Concurrent）的；由此定義可擴(kuò)展到非常廣泛的概念，其向下依賴于操作系統(tǒng)、存儲(chǔ)等，與分布式系統(tǒng)、微服務(wù)等，而又會(huì)具體落地于 Java 并發(fā)編程、Go 并發(fā)編程、JavaScript 異步編程等領(lǐng)域。云計(jì)算承諾在所有維度上（內(nèi)存、計(jì)算、存儲(chǔ)等）實(shí)現(xiàn)無(wú)限的可擴(kuò)展性，并發(fā)編程及其相關(guān)理論也是我們構(gòu)建大規(guī)模分布式應(yīng)用的基礎(chǔ)。

并發(fā)與并行

并發(fā)就是可同時(shí)發(fā)起執(zhí)行的程序，指程序的邏輯結(jié)構(gòu)；并行就是可以在支持并行的硬件上執(zhí)行的并發(fā)程序，指程序的運(yùn)?狀態(tài)。換句話說(shuō)，并發(fā)程序代表了所有可以實(shí)現(xiàn)并發(fā)行為的程序，這是一個(gè)比較寬泛的概念，并行程序也只是他的一個(gè)子集。并發(fā)是并?的必要條件；但并發(fā)不是并?的充分條件。并發(fā)只是更符合現(xiàn)實(shí)問(wèn)題本質(zhì)的表達(dá)，目的是簡(jiǎn)化代碼邏輯，?不是使程序運(yùn)?更快。要是程序運(yùn)?更快必是并發(fā)程序加多核并?。

簡(jiǎn)言之，并發(fā)是同一時(shí)間應(yīng)對(duì)（dealing with）多件事情的能力；并行是同一時(shí)間動(dòng)手做（doing）多件事情的能力。

并發(fā)是問(wèn)題域中的概念——程序需要被設(shè)計(jì)成能夠處理多個(gè)同時(shí)(或者幾乎同時(shí))發(fā)生的事件；一個(gè)并發(fā)程序含有多個(gè)邏輯上的獨(dú)立執(zhí)行塊，它們可以獨(dú)立地并行執(zhí)行，也可以串行執(zhí)行。而并行則是方法域中的概念——通過(guò)將問(wèn)題中的多個(gè)部分并行執(zhí)行，來(lái)加速解決問(wèn)題。一個(gè)并行程序解決問(wèn)題的速度往往比一個(gè)串行程序快得多，因?yàn)槠淇梢酝瑫r(shí)執(zhí)行整個(gè)任務(wù)的多個(gè)部分。并行程序可能有多個(gè)獨(dú)立執(zhí)行塊，也可能僅有一個(gè)。

具體而言，早期的 Redis（6.0 版本后也引入了多線程） 會(huì)是一個(gè)很好地區(qū)分并發(fā)和并行的例子，它本身是一個(gè)單線程的數(shù)據(jù)庫(kù)，但是可以通過(guò)多路復(fù)用與事件循環(huán)的方式來(lái)提供并發(fā)地 IO 服務(wù)。這是因?yàn)槎嗪瞬⑿斜举|(zhì)上會(huì)有很大的一個(gè)同步的代價(jià)，特別是在鎖或者信號(hào)量的情況下。因此，Redis 利用了單線程的事件循環(huán)來(lái)保證一系列的原子操作，從而保證了即使在高并發(fā)的情況下也能達(dá)到幾乎零消耗的同步。再引用下 Rob Pike 的描述：

A single-threaded program can definitely provides concurrency at the IO level by using an IO (de)multiplexing mechanism and an event loop (which is what Redis does).

并發(fā)維度

線程級(jí)并發(fā)

從 20 世紀(jì) 60 年代初期出現(xiàn)時(shí)間共享以來(lái)，計(jì)算機(jī)系統(tǒng)中就開(kāi)始有了對(duì)并發(fā)執(zhí)行的支持；傳統(tǒng)意義上，這種并發(fā)執(zhí)行只是模擬出來(lái)的，是通過(guò)使一臺(tái)計(jì)算機(jī)在它正在執(zhí)行的進(jìn)程間快速切換的方式實(shí)現(xiàn)的，這種配置稱為單處理器系統(tǒng)。從 20 世紀(jì) 80 年代，多處理器系統(tǒng)，即由單操作系統(tǒng)內(nèi)核控制的多處理器組成的系統(tǒng)采用了多核處理器與超線程（HyperThreading）等技術(shù)允許我們實(shí)現(xiàn)真正的并行。多核處理器是將多個(gè) CPU 集成到一個(gè)集成電路芯片上：

超線程，有時(shí)稱為同時(shí)多線程（simultaneous multi-threading），是一項(xiàng)允許一個(gè) CPU 執(zhí)行多個(gè)控制流的技術(shù)。它涉及 CPU 某些硬件有多個(gè)備份，比如程序計(jì)數(shù)器和寄存器文件；而其他的硬件部分只有一份，比如執(zhí)行浮點(diǎn)算術(shù)運(yùn)算的單元。常規(guī)的處理器需要大約 20 000 個(gè)時(shí)鐘周期做不同線程間的轉(zhuǎn)換，而超線程的處理器可以在單個(gè)周期的基礎(chǔ)上決定要執(zhí)行哪一個(gè)線程。這使得 CPU 能夠更好地利用它的處理資源。例如，假設(shè)一個(gè)線程必須等到某些數(shù)據(jù)被裝載到高速緩存中，那 CPU 就可以繼續(xù)去執(zhí)行另一個(gè)線程。

指令級(jí)并發(fā)

在較低的抽象層次上，現(xiàn)代處理器可以同時(shí)執(zhí)行多條指令的屬性稱為指令級(jí)并行。實(shí)每條指令從開(kāi)始到結(jié)束需要長(zhǎng)得多的時(shí)間，大約 20 個(gè)或者更多的周期，但是處理器使用了非常多的聰明技巧來(lái)同時(shí)處理多達(dá) 100 條的指令。在流水線中，將執(zhí)行一條指令所需要的活動(dòng)劃分成不同的步驟，將處理器的硬件組織成一系列的階段，每個(gè)階段執(zhí)行一個(gè)步驟。這些階段可以并行地操作，用來(lái)處理不同指令的不同部分。我們會(huì)看到一個(gè)相當(dāng)簡(jiǎn)單的硬件設(shè)計(jì)，它能夠達(dá)到接近于一個(gè)時(shí)鐘周期一條指令的執(zhí)行速率。如果處理器可以達(dá)到比一個(gè)周期一條指令更快的執(zhí)行速率，就稱之為超標(biāo)量（Super Scalar）處理器。

單指令、多數(shù)據(jù)

在最低層次上，許多現(xiàn)代處理器擁有特殊的硬件，允許一條指令產(chǎn)生多個(gè)可以并行執(zhí)行的操作，這種方式稱為單指令、多數(shù)據(jù)，即 SIMD 并行。例如，較新的 Intel 和 AMD 處理器都具有并行地對(duì) 4 對(duì)單精度浮點(diǎn)數(shù)（C 數(shù)據(jù)類型 float）做加法的指令。

同步、異步、阻塞、非阻塞

在并發(fā)與并行的基礎(chǔ)概念之后，我們還需要了解同步、異步、阻塞與非阻塞這幾個(gè)概念的關(guān)系與區(qū)別。

同步即執(zhí)行某個(gè)操作開(kāi)始后就一直等著按部就班的直到操作結(jié)束，異步即執(zhí)行某個(gè)操作后立即離開(kāi)，后面有響應(yīng)的話再來(lái)通知執(zhí)行者。從編程的角度來(lái)看，如果同步調(diào)用，則調(diào)用的結(jié)果會(huì)在本次調(diào)用后返回。如果異步調(diào)用，則調(diào)用的結(jié)果不會(huì)直接返回。會(huì)返回一個(gè) Future 或者 Promise 對(duì)象來(lái)供調(diào)用方主動(dòng)/被動(dòng)的獲取本次調(diào)用的結(jié)果。

而阻塞與非阻塞在并發(fā)編程中，主要是從對(duì)于臨界區(qū)公共資源或者共享數(shù)據(jù)競(jìng)態(tài)訪問(wèn)的角度來(lái)進(jìn)行區(qū)分。某個(gè)操作需要的共享資源被占用了，只能等待，稱為阻塞；某個(gè)操作需要的共享資源被占用了，不等待立即返回，并攜帶錯(cuò)誤信息回去，期待重試，則稱為非阻塞。

值得一提的是，在并發(fā) IO 的討論中，我們還會(huì)出現(xiàn)同步非阻塞的 IO 模型，這是因?yàn)?IO 操作(read/write 系統(tǒng)調(diào)用)其實(shí)包含了發(fā)起 IO 請(qǐng)求與實(shí)際的 IO 讀寫(xiě)這兩個(gè)步驟。阻塞 IO 和非阻塞 IO 的區(qū)別在于第一步，發(fā)起 IO 請(qǐng)求的進(jìn)程是否會(huì)被阻塞，如果阻塞直到 IO 操作完成才返回那么就是傳統(tǒng)的阻塞 IO，如果不阻塞，那么就是非阻塞 IO。同步 IO 和異步 IO 的區(qū)別就在于第二步，實(shí)際的 IO 讀寫(xiě)(內(nèi)核態(tài)與用戶態(tài)的數(shù)據(jù)拷貝)是否需要進(jìn)程參與，如果需要進(jìn)程參與則是同步 IO，如果不需要進(jìn)程參與就是異步 IO。如果實(shí)際的 IO 讀寫(xiě)需要請(qǐng)求進(jìn)程參與，那么就是同步 IO；因此阻塞 IO、非阻塞 IO、IO 復(fù)用、信號(hào)驅(qū)動(dòng) IO 都是同步 IO。

并發(fā)級(jí)別

在實(shí)際的部署環(huán)境下，受限于 CPU 的數(shù)量，我們不可能無(wú)限制地增加線程數(shù)量，不同場(chǎng)景需要的并發(fā)需求也不一樣；譬如秒殺系統(tǒng)中我們強(qiáng)調(diào)高并發(fā)高吞吐，而對(duì)于一些下載服務(wù)，則更強(qiáng)調(diào)快響應(yīng)低時(shí)延。因此根據(jù)不同的需求場(chǎng)景我們也可以定義不同的并發(fā)級(jí)別：

• 阻塞：阻塞是指一個(gè)線程進(jìn)入臨界區(qū)后，其它線程就必須在臨界區(qū)外等待，待進(jìn)去的線程執(zhí)行完任務(wù)離開(kāi)臨界區(qū)后，其它線程才能再進(jìn)去。

• 無(wú)饑餓：線程排隊(duì)先來(lái)后到，不管優(yōu)先級(jí)大小，先來(lái)先執(zhí)行，就不會(huì)產(chǎn)生饑餓等待資源，也即公平鎖；相反非公平鎖則是根據(jù)優(yōu)先級(jí)來(lái)執(zhí)行，有可能排在前面的低優(yōu)先級(jí)線程被后面的高優(yōu)先級(jí)線程插隊(duì)，就形成饑餓

• 無(wú)障礙：共享資源不加鎖，每個(gè)線程都可以自有讀寫(xiě)，單監(jiān)測(cè)到被其他線程修改過(guò)則回滾操作，重試直到單獨(dú)操作成功；風(fēng)險(xiǎn)就是如果多個(gè)線程發(fā)現(xiàn)彼此修改了，所有線程都需要回滾，就會(huì)導(dǎo)致死循環(huán)的回滾中，造成死鎖

• 無(wú)鎖：無(wú)鎖是無(wú)障礙的加強(qiáng)版，無(wú)鎖級(jí)別保證至少有一個(gè)線程在有限操作步驟內(nèi)成功退出，不管是否修改成功，這樣保證了多個(gè)線程回滾不至于導(dǎo)致死循環(huán)

• 無(wú)等待：無(wú)等待是無(wú)鎖的升級(jí)版，并發(fā)編程的最高境界，無(wú)鎖只保證有線程能成功退出，但存在低級(jí)別的線程一直處于饑餓狀態(tài)，無(wú)等待則要求所有線程必須在有限步驟內(nèi)完成退出，讓低級(jí)別的線程有機(jī)會(huì)執(zhí)行，從而保證所有線程都能運(yùn)行，提高并發(fā)度。

量化模型

多線程不意味著并發(fā)，但并發(fā)肯定是多線程或者多進(jìn)程；多線程存在的優(yōu)勢(shì)是能夠更好的利用資源，有更快的請(qǐng)求響應(yīng)。但是我們也深知一旦進(jìn)入多線程，附帶而來(lái)的是更高的編碼復(fù)雜度，線程設(shè)計(jì)不當(dāng)反而會(huì)帶來(lái)更高的切換成本和資源開(kāi)銷。如何衡量多線程帶來(lái)的效率提升呢，我們需要借助兩個(gè)定律來(lái)衡量。

Amdahl 定律

Amdahl 定律可以用來(lái)計(jì)算處理器平行運(yùn)算之后效率提升的能力，其由 Gene Amdal 在 1967 年提出；它描述了在一個(gè)系統(tǒng)中，基于可并行化和串行化的組件各自所占的比重，程序通過(guò)獲得額外的計(jì)算資源，理論上能夠加速多少。任何程序或算法可以按照是否可以被并行化分為可以被并行化的部分 1 - B 與不可以被并行化的部分 B，那么根據(jù) Amdahl 定律，不同的并行因子的情況下程序的總執(zhí)行時(shí)間的變化如下所示：

如果 F 是必須串行化執(zhí)行的比重，那么 Amdahl 定律告訴我們，在一個(gè) N 處理器的機(jī)器中，我們最多可以加速：

當(dāng) N 無(wú)限增大趨近無(wú)窮時(shí)，speedup 的最大值無(wú)限趨近 1/F，這意味著一個(gè)程序中如果 50% 的處理都需要串行進(jìn)行的話，speedup 只能提升 2 倍(不考慮事實(shí)上有多少線程可用)；如果程序的 10% 需要串行進(jìn)行，speedup 最多能夠提高近 10 倍。

Amdahl 定律同樣量化了串行化的效率開(kāi)銷。在擁有 10 個(gè)處理器的系統(tǒng)中，程序如果有 10% 是串行化的，那么最多可以加速 5.3 倍(53 ％的使用率)，在擁有 100 個(gè)處理器的系統(tǒng)中，這個(gè)數(shù)字可以達(dá)到 9.2(9 ％的使用率)。這使得無(wú)效的 CPU 利用永遠(yuǎn)不可能到達(dá) 10 倍。下圖展示了隨著串行執(zhí)行和處理器數(shù)量變化，處理器最大限度的利用率的曲線。隨著處理器數(shù)量的增加，我們很明顯地看到，即使串行化執(zhí)行的程度發(fā) 生細(xì)微的百分比變化，都會(huì)大大限制吞吐量隨計(jì)算資源增加。

Amdahl 定律旨在說(shuō)明，多核 CPU 對(duì)系統(tǒng)進(jìn)行優(yōu)化時(shí)，優(yōu)化的效果取決于 CPU 的數(shù)量以及系統(tǒng)中的串行化程序的比重；如果僅關(guān)注于提高 CPU 數(shù)量而不降低程序的串行化比重，也無(wú)法提高系統(tǒng)性能。

Gustafson

系統(tǒng)優(yōu)化某部件所獲得的系統(tǒng)性能的改善程度，取決于該部件被使用的頻率，或所占總執(zhí)行時(shí)間的比例。

內(nèi)存模型

如前文所述，現(xiàn)代計(jì)算機(jī)通常有兩個(gè)或者更多的 CPU，一些 CPU 還有多個(gè)核；其允許多個(gè)線程同時(shí)運(yùn)行，每個(gè) CPU 在某個(gè)時(shí)間片內(nèi)運(yùn)行其中的一個(gè)線程。在存儲(chǔ)管理一節(jié)中我們介紹了計(jì)算機(jī)系統(tǒng)中的不同的存儲(chǔ)類別：

每個(gè) CPU 包含多個(gè)寄存器，這些寄存器本質(zhì)上就是 CPU 內(nèi)存；CPU 在寄存器中執(zhí)行操作的速度會(huì)比在主內(nèi)存中操作快非常多。每個(gè) CPU 可能還擁有 CPU 緩存層，CPU 訪問(wèn)緩存層的速度比訪問(wèn)主內(nèi)存塊很多，但是卻比訪問(wèn)寄存器要慢。計(jì)算機(jī)還包括主內(nèi)存（RAM），所有的 CPU 都可以訪問(wèn)這個(gè)主內(nèi)存，主內(nèi)存一般都比 CPU 緩存大很多，但速度要比 CPU 緩存慢。當(dāng)一個(gè) CPU 需要訪問(wèn)主內(nèi)存的時(shí)候，會(huì)把主內(nèi)存中的部分?jǐn)?shù)據(jù)讀取到 CPU 緩存，甚至進(jìn)一步把緩存中的部分?jǐn)?shù)據(jù)讀取到內(nèi)部的寄存器，然后對(duì)其進(jìn)行操作。當(dāng) CPU 需要向主內(nèi)存寫(xiě)數(shù)據(jù)的時(shí)候，會(huì)將寄存器中的數(shù)據(jù)寫(xiě)入緩存，某些時(shí)候會(huì)將數(shù)據(jù)從緩存刷入主內(nèi)存。無(wú)論從緩存讀還是寫(xiě)數(shù)據(jù)，都沒(méi)有必要一次性全部讀出或者寫(xiě)入，而是僅對(duì)部分?jǐn)?shù)據(jù)進(jìn)行操作。

并發(fā)編程中的問(wèn)題，往往源于緩存導(dǎo)致的可見(jiàn)性問(wèn)題、線程切換導(dǎo)致的原子性問(wèn)題以及編譯優(yōu)化帶來(lái)的有序性問(wèn)題。以 Java 虛擬機(jī)為例，每個(gè)線程都擁有一個(gè)屬于自己的線程棧（調(diào)用棧），隨著線程代碼的執(zhí)行，調(diào)用棧會(huì)隨之改變。線程棧中包含每個(gè)正在執(zhí)行的方法的局部變量。每個(gè)線程只能訪問(wèn)屬于自己的棧。調(diào)用棧中的局部變量，只有創(chuàng)建這個(gè)棧的線程才可以訪問(wèn)，其他線程都不能訪問(wèn)。即使兩個(gè)線程在執(zhí)行一段相同的代碼，這兩個(gè)線程也會(huì)在屬于各自的線程棧中創(chuàng)建局部變量。因此，每個(gè)線程擁有屬于自己的局部變量。所有基本類型的局部變量全部存放在線程棧中，對(duì)其他線程不可見(jiàn)。一個(gè)線程可以把基本類型拷貝到其他線程，但是不能共享給其他線程，而無(wú)論哪個(gè)線程創(chuàng)建的對(duì)象都存放在堆中。

原子性

所謂的原子性，就是一個(gè)或者多個(gè)操作在 CPU 執(zhí)行的過(guò)程中不被中斷的特性，CPU 能保證的原子操作是 CPU 指令級(jí)別的，而不是高級(jí)語(yǔ)言的操作符。我們?cè)诰幊陶Z(yǔ)言中部分看似原子操作的指令，在被編譯到匯編之后往往會(huì)變成多個(gè)操作：

i++

# 編譯成匯編之后就是：
# 讀取當(dāng)前變量 i 并把它賦值給一個(gè)臨時(shí)寄存器;
movl i(%rip), %eax
# 給臨時(shí)寄存器+1;
addl $1, %eax
# 把 eax 的新值寫(xiě)回內(nèi)存
movl %eax, i(%rip)

我們可以清楚看到 C 代碼只需要一句，但編譯成匯編卻需要三步(這里不考慮編譯器優(yōu)化，實(shí)際上通過(guò)編譯器優(yōu)化可以將這三條匯編指令合并成一條)。也就是說(shuō)，只有簡(jiǎn)單的讀取、賦值(而且必須是將數(shù)字賦值給某個(gè)變量，變量之間的相互賦值不是原子操作)才是原子操作。按照原子操作解決同步問(wèn)題方式：依靠處理器原語(yǔ)支持把上述三條指令合三為一，當(dāng)做一條指令來(lái)執(zhí)行，保證在執(zhí)行過(guò)程中不會(huì)被打斷并且多線程并發(fā)也不會(huì)受到干擾。這樣同步問(wèn)題迎刃而解，這也就是所謂的原子操作。但處理器沒(méi)有義務(wù)為任意代碼片段提供原子性操作，尤其是我們的臨界區(qū)資源十分龐大甚至大小不確定，處理器沒(méi)有必要或是很難提供原子性支持，此時(shí)往往需要依賴于鎖來(lái)保證原子性。

對(duì)應(yīng)原子操作/事務(wù)在 Java 中，對(duì)基本數(shù)據(jù)類型的變量的讀取和賦值操作是原子性操作，即這些操作是不可被中斷的，要么執(zhí)行，要么不執(zhí)行。Java 內(nèi)存模型只保證了基本讀取和賦值是原子性操作，如果要實(shí)現(xiàn)更大范圍操作的原子性，可以通過(guò) synchronized 和 Lock 來(lái)實(shí)現(xiàn)。由于 synchronized 和 Lock 能夠保證任一時(shí)刻只有一個(gè)線程執(zhí)行該代碼塊，那么自然就不存在原子性問(wèn)題了，從而保證了原子性。

有序性

顧名思義，有序性指的是程序按照代碼的先后順序執(zhí)行。現(xiàn)代編譯器的代碼優(yōu)化和編譯器指令重排可能會(huì)影響到代碼的執(zhí)行順序。編譯期指令重排是通過(guò)調(diào)整代碼中的指令順序，在不改變代碼語(yǔ)義的前提下，對(duì)變量訪問(wèn)進(jìn)行優(yōu)化。從而盡可能的減少對(duì)寄存器的讀取和存儲(chǔ)，并充分復(fù)用寄存器。但是編譯器對(duì)數(shù)據(jù)的依賴關(guān)系判斷只能在單執(zhí)行流內(nèi)，無(wú)法判斷其他執(zhí)行流對(duì)競(jìng)爭(zhēng)數(shù)據(jù)的依賴關(guān)系。就拿無(wú)鎖環(huán)形隊(duì)列來(lái)說(shuō)，如果 Writer 做的是先放置數(shù)據(jù)，再更新索引的行為。如果索引先于數(shù)據(jù)更新，Reader 就有可能會(huì)因?yàn)榕袛嗨饕迅露x到臟數(shù)據(jù)。

禁止編譯器對(duì)該類變量的優(yōu)化，解決了編譯期的重排序并不能保證有序性，因?yàn)?CPU 還有亂序執(zhí)行（Out-of-Order Execution）的特性。流水線（Pipeline）和亂序執(zhí)行是現(xiàn)代 CPU 基本都具有的特性。機(jī)器指令在流水線中經(jīng)歷取指、譯碼、執(zhí)行、訪存、寫(xiě)回等操作。為了 CPU 的執(zhí)行效率，流水線都是并行處理的，在不影響語(yǔ)義的情況下。處理器次序（Process Ordering，機(jī)器指令在 CPU 實(shí)際執(zhí)行時(shí)的順序）和程序次序（Program Ordering，程序代碼的邏輯執(zhí)行順序）是允許不一致的，即滿足 As-if-Serial 特性。顯然，這里的不影響語(yǔ)義依舊只能是保證指令間的顯式因果關(guān)系，無(wú)法保證隱式因果關(guān)系。即無(wú)法保證語(yǔ)義上不相關(guān)但是在程序邏輯上相關(guān)的操作序列按序執(zhí)行。從此單核時(shí)代 CPU 的 Self-Consistent 特性在多核時(shí)代已不存在，多核 CPU 作為一個(gè)整體看，不再滿足 Self-Consistent 特性。

簡(jiǎn)單總結(jié)一下，如果不做多余的防護(hù)措施，單核時(shí)代的無(wú)鎖環(huán)形隊(duì)列在多核 CPU 中，一個(gè) CPU 核心上的 Writer 寫(xiě)入數(shù)據(jù)，更新 index 后。另一個(gè) CPU 核心上的 Reader 依靠這個(gè) index 來(lái)判斷數(shù)據(jù)是否寫(xiě)入的方式不一定可靠。index 有可能先于數(shù)據(jù)被寫(xiě)入，從而導(dǎo)致 Reader 讀到臟數(shù)據(jù)。

在 Java 中與有序性相關(guān)的經(jīng)典問(wèn)題就是單例模式，譬如我們會(huì)采用靜態(tài)函數(shù)來(lái)獲取某個(gè)對(duì)象的實(shí)例，并且使用 synchronized 加鎖來(lái)保證只有單線程能夠觸發(fā)創(chuàng)建，其他線程則是直接獲取到實(shí)例對(duì)象。

if (instance == null) {
    synchronized(Singleton.class) {
        if (instance == null){
            instance = new Singleton();
        }
    }
}

不過(guò)雖然我們期望的對(duì)象創(chuàng)建的過(guò)程是：內(nèi)存分配、初始化對(duì)象、將對(duì)象引用賦值給成員變量，但是實(shí)際情況下經(jīng)過(guò)優(yōu)化的代碼往往會(huì)首先進(jìn)行變量賦值，而后進(jìn)行對(duì)象初始化。假設(shè)線程 A 先執(zhí)行 getInstance() 方法，當(dāng)執(zhí)行完指令 2 時(shí)恰好發(fā)生了線程切換，切換到了線程 B 上；如果此時(shí)線程 B 也執(zhí)行 getInstance() 方法，那么線程 B 在執(zhí)行第一個(gè)判斷時(shí)會(huì)發(fā)現(xiàn) instance != null，所以直接返回 instance，而此時(shí)的 instance 是沒(méi)有初始化過(guò)的，如果我們這個(gè)時(shí)候訪問(wèn) instance 的成員變量就可能觸發(fā)空指針異常。

可見(jiàn)性

所謂的可見(jiàn)性，即是一個(gè)線程對(duì)共享變量的修改，另外一個(gè)線程能夠立刻看到。單核時(shí)代，所有的線程都是直接操作單個(gè) CPU 的數(shù)據(jù)，某個(gè)線程對(duì)緩存的寫(xiě)對(duì)另外一個(gè)線程來(lái)說(shuō)一定是可見(jiàn)的；譬如下圖中，如果線程 B 在線程 A 更新了變量值之后進(jìn)行訪問(wèn)，那么獲得的肯定是變量 V 的最新值。多核時(shí)代，每顆 CPU 都有自己的緩存，共享變量存儲(chǔ)在主內(nèi)存。運(yùn)行在某個(gè) CPU 中的線程將共享變量讀取到自己的 CPU 緩存。在 CPU 緩存中，修改了共享對(duì)象的值，由于 CPU 并未將緩存中的數(shù)據(jù)刷回主內(nèi)存，導(dǎo)致對(duì)共享變量的修改對(duì)于在另一個(gè) CPU 中運(yùn)行的線程而言是不可見(jiàn)的。這樣每個(gè)線程都會(huì)擁有一份屬于自己的共享變量的拷貝，分別存于各自對(duì)應(yīng)的 CPU 緩存中。

CPU 讀寫(xiě)流程

傳統(tǒng)的 MESI 協(xié)議中有兩個(gè)行為的執(zhí)行成本比較大。一個(gè)是將某個(gè) Cache Line 標(biāo)記為 Invalid 狀態(tài)，另一個(gè)是當(dāng)某 Cache Line 當(dāng)前狀態(tài)為 Invalid 時(shí)寫(xiě)入新的數(shù)據(jù)。所以 CPU 通過(guò) Store Buffer 和 Invalidate Queue 組件來(lái)降低這類操作的延時(shí)。如圖：

當(dāng)一個(gè)核心在 Invalid 狀態(tài)進(jìn)行寫(xiě)入時(shí)，首先會(huì)給其它 CPU 核發(fā)送 Invalid 消息，然后把當(dāng)前寫(xiě)入的數(shù)據(jù)寫(xiě)入到 Store Buffer 中。然后異步在某個(gè)時(shí)刻真正的寫(xiě)入到 Cache Line 中。當(dāng)前 CPU 核如果要讀 Cache Line 中的數(shù)據(jù)，需要先掃描 Store Buffer 之后再讀取 Cache Line（Store-Buffer Forwarding）。但是此時(shí)其它 CPU 核是看不到當(dāng)前核的 Store Buffer 中的數(shù)據(jù)的，要等到 Store Buffer 中的數(shù)據(jù)被刷到了 Cache Line 之后才會(huì)觸發(fā)失效操作。而當(dāng)一個(gè) CPU 核收到 Invalid 消息時(shí)，會(huì)把消息寫(xiě)入自身的 Invalidate Queue 中，隨后異步將其設(shè)為 Invalid 狀態(tài)。和 Store Buffer 不同的是，當(dāng)前 CPU 核心使用 Cache 時(shí)并不掃描 Invalidate Queue 部分，所以可能會(huì)有極短時(shí)間的臟讀問(wèn)題。當(dāng)然這里的 Store Buffer 和 Invalidate Queue 的說(shuō)法是針對(duì)一般的 SMP 架構(gòu)來(lái)說(shuō)的，不涉及具體架構(gòu)。事實(shí)上除了 Store Buffer 和 Load Buffer，流水線為了實(shí)現(xiàn)并行處理，還有 Line Fill Buffer/Write Combining Buffer 等組件。

典型案例：并發(fā)加

可見(jiàn)性問(wèn)題最經(jīng)典的案例即是并發(fā)加操作，如下兩個(gè)線程同時(shí)在更新變量 test 的 count 屬性域的值，第一次都會(huì)將 count=0 讀到各自的 CPU 緩存里，執(zhí)行完 count+=1 之后，各自 CPU 緩存里的值都是 1，同時(shí)寫(xiě)入內(nèi)存后，我們會(huì)發(fā)現(xiàn)內(nèi)存中是 1，而不是我們期望的 2。之后由于各自的 CPU 緩存里都有了 count 的值，兩個(gè)線程都是基于 CPU 緩存里的 count 值來(lái)計(jì)算，所以導(dǎo)致最終 count 的值都是小于 20000 的。

Thread th2 = new Thread(()->{
    test.add10K();
});

Thread th3 = new Thread(()->{
    test.add10K();
});

// 每個(gè)線程中對(duì)相同對(duì)象執(zhí)行加操作
count += 1;

在 Java 中，如果多個(gè)線程共享一個(gè)對(duì)象，并且沒(méi)有合理的使用 volatile 聲明和線程同步，一個(gè)線程更新共享對(duì)象后，另一個(gè)線程可能無(wú)法取到對(duì)象的最新值。當(dāng)一個(gè)共享變量被 volatile 修飾時(shí)，它會(huì)保證修改的值會(huì)立即被更新到主存，當(dāng)有其他線程需要讀取時(shí)，它會(huì)去內(nèi)存中讀取新值。通過(guò) synchronized 和 Lock 也能夠保證可見(jiàn)性，synchronized 和 Lock 能保證同一時(shí)刻只有一個(gè)線程獲取鎖然后執(zhí)行同步代碼，并且在釋放鎖之前會(huì)將對(duì)變量的修改刷新到主存當(dāng)中。因此可以保證可見(jiàn)性。

Cache Line & False Sharing | 緩存行與偽共享

緩存系統(tǒng)中是以緩存行（Cache Line）為單位存儲(chǔ)的，緩存行是 2 的整數(shù)冪個(gè)連續(xù)字節(jié)，一般為 32-256 個(gè)字節(jié)。最常見(jiàn)的緩存行大小是 64 個(gè)字節(jié)。當(dāng)多線程修改互相獨(dú)立的變量時(shí)，如果這些變量共享同一個(gè)緩存行，就會(huì)無(wú)意中影響彼此的性能，這就是偽共享。

若兩個(gè)變量放在同一個(gè)緩存行中，在多線程情況下，可能會(huì)相互影響彼此的性能。如上圖所示，CPU1 上的線程更新了變量 X，則 CPU 上的緩存行會(huì)失效，同一行的 Y 即使沒(méi)有更新也會(huì)失效，導(dǎo)致 Cache 無(wú)法命中。同樣地，若 CPU2 上的線程更新了 Y，則導(dǎo)致 CPU1 上的緩存行又失效。如果 CPU 經(jīng)常不能命中緩存，則系統(tǒng)的吞吐量則會(huì)下降。這就是偽共享問(wèn)題。

解決偽共享問(wèn)題，可以在變量的前后都占據(jù)一定的填充位置，盡量讓變量占用一個(gè)完整的緩存行。如上圖中，CPU1 上的線程更新了 X，則 CPU2 上的 Y 則不會(huì)失效。同樣地，CPU2 上的線程更新了 Y，則 CPU1 的不會(huì)失效。參考 Java 內(nèi)存布局可知，所有對(duì)象都有兩個(gè)字長(zhǎng)的對(duì)象頭。第一個(gè)字是由 24 位哈希碼和 8 位標(biāo)志位(如鎖的狀態(tài)或作為鎖對(duì)象)組成的 Mark Word。第二個(gè)字是對(duì)象所屬類的引用。如果是數(shù)組對(duì)象還需要一個(gè)額外的字來(lái)存儲(chǔ)數(shù)組的長(zhǎng)度。每個(gè)對(duì)象的起始地址都對(duì)齊于 8 字節(jié)以提高性能。因此當(dāng)封裝對(duì)象的時(shí)候?yàn)榱烁咝剩瑢?duì)象字段聲明的順序會(huì)被重排序成下列基于字節(jié)大小的順序：

doubles (8) 和 longs (8)
ints (4) 和 floats (4)
shorts (2) 和 chars (2)
booleans (1) 和 bytes (1)
references (4/8)
<子類字段重復(fù)上述順序>

一條緩存行有 64 字節(jié), 而 Java 程序的對(duì)象頭固定占 8 字節(jié)(32 位系統(tǒng))或 12 字節(jié)(64 位系統(tǒng)默認(rèn)開(kāi)啟壓縮, 不開(kāi)壓縮為 16 字節(jié))。我們只需要填 6 個(gè)無(wú)用的長(zhǎng)整型補(bǔ)上 6*8=48 字節(jié)，讓不同的 VolatileLong 對(duì)象處于不同的緩存行, 就可以避免偽共享了；64 位系統(tǒng)超過(guò)緩存行的 64 字節(jié)也無(wú)所謂，只要保證不同線程不要操作同一緩存行就可以。這個(gè)辦法叫做補(bǔ)齊（Padding）：

public final static class VolatileLong
{
    public volatile long value = 0L;
 ?  public long p1, p2, p3, p4, p5, p6; // 添加該行，錯(cuò)開(kāi)緩存行，避免偽共享
}

某些 Java 編譯器會(huì)將沒(méi)有使用到的補(bǔ)齊數(shù)據(jù), 即示例代碼中的 6 個(gè)長(zhǎng)整型在編譯時(shí)優(yōu)化掉, 可以在程序中加入一些代碼防止被編譯優(yōu)化。

public static long preventFromOptimization(VolatileLong v) {
    return v.p1 + v.p2 + v.p3 + v.p4 + v.p5 + v.p6;
}

屏障

編譯器優(yōu)化亂序和 CPU 執(zhí)行亂序的問(wèn)題可以分別使用優(yōu)化屏障 (Optimization Barrier)和內(nèi)存屏障 (Memory Barrier)這兩個(gè)機(jī)制來(lái)解決：

• 優(yōu)化屏障 (Optimization Barrier)：避免編譯器的重排序優(yōu)化操作，保證編譯程序時(shí)在優(yōu)化屏障之前的指令不會(huì)在優(yōu)化屏障之后執(zhí)行。這就保證了編譯時(shí)期的優(yōu)化不會(huì)影響到實(shí)際代碼邏輯順序。
• 內(nèi)存屏障 (Memory Barrier)分為寫(xiě)屏障（Store Barrier）、讀屏障（Load Barrier）和全屏障（Full Barrier），其作用有兩個(gè)：防止指令之間的重排序、保證數(shù)據(jù)的可見(jiàn)性。

多處理器同時(shí)訪問(wèn)共享主存，每個(gè)處理器都要對(duì)讀寫(xiě)進(jìn)行重新排序，一旦數(shù)據(jù)更新，就需要同步更新到主存上 (這里并不要求處理器緩存更新之后立刻更新主存)。在這種情況下，代碼和指令重排，再加上緩存延遲指令結(jié)果輸出導(dǎo)致共享變量被修改的順序發(fā)生了變化，使得程序的行為變得無(wú)法預(yù)測(cè)。為了解決這種不可預(yù)測(cè)的行為，處理器提供一組機(jī)器指令來(lái)確保指令的順序要求，它告訴處理器在繼續(xù)執(zhí)行前提交所有尚未處理的載入和存儲(chǔ)指令。同樣的也可以要求編譯器不要對(duì)給定點(diǎn)以及周?chē)噶钚蛄羞M(jìn)行重排。這些確保順序的指令稱為內(nèi)存屏障。具體的確保措施在程序語(yǔ)言級(jí)別的體現(xiàn)就是內(nèi)存模型的定義。

POSIX、C++、Java 都有各自的共享內(nèi)存模型，實(shí)現(xiàn)上并沒(méi)有什么差異，只是在一些細(xì)節(jié)上稍有不同。這里所說(shuō)的內(nèi)存模型并非是指內(nèi)存布 局，特指內(nèi)存、Cache、CPU、寫(xiě)緩沖區(qū)、寄存器以及其他的硬件和編譯器優(yōu)化的交互時(shí)對(duì)讀寫(xiě)指令操作提供保護(hù)手段以確保讀寫(xiě)序。將這些繁雜因素可以籠統(tǒng)的歸納為兩個(gè)方面：重排和緩存，即上文所說(shuō)的代碼重排、指令重排和 CPU Cache。簡(jiǎn)單的說(shuō)內(nèi)存屏障做了兩件事情：拒絕重排，更新緩存。

C++11 提供一組用戶 API std::memory_order 來(lái)指導(dǎo)處理器讀寫(xiě)順序。Java 使用 happens-before 規(guī)則來(lái)屏蔽具體細(xì)節(jié)保證，指導(dǎo) JVM 在指令生成的過(guò)程中穿插屏障指令。內(nèi)存屏障也可以在編譯期間指示對(duì)指令或者包括周?chē)噶钚蛄胁贿M(jìn)行優(yōu)化，稱之為編譯器屏障，相當(dāng)于輕量級(jí)內(nèi)存屏障，它的工作同樣重要，因?yàn)樗诰幾g期指導(dǎo)編譯器優(yōu)化。屏障的實(shí)現(xiàn)稍微復(fù)雜一些，我們使用一組抽象的假想指令來(lái)描述內(nèi)存屏障的工作原理。使用 MB_R、MB_W、MB 來(lái)抽象處理器指令為宏：

• MB_R 代表讀內(nèi)存屏障，它保證讀取操作不會(huì)重排到該指令調(diào)用之后。
• MB_W 代表寫(xiě)內(nèi)存屏障，它保證寫(xiě)入操作不會(huì)重排到該指令調(diào)用之后。
• MB 代表讀寫(xiě)內(nèi)存屏障，可保證之前的指令不會(huì)重排到該指令調(diào)用之后。

這些屏障指令在單核處理器上同樣有效，因?yàn)閱翁幚砥麟m不涉及多處理器間數(shù)據(jù)同步問(wèn)題，但指令重排和緩存仍然影響數(shù)據(jù)的正確同步。指令重排是非常底層的且實(shí) 現(xiàn)效果差異非常大，尤其是不同體系架構(gòu)對(duì)內(nèi)存屏障的支持程度，甚至在不支持指令重排的體系架構(gòu)中根本不必使用屏障指令。具體如何使用這些屏障指令是支持的 平臺(tái)、編譯器或虛擬機(jī)要實(shí)現(xiàn)的，我們只需要使用這些實(shí)現(xiàn)的 API(指的是各種并發(fā)關(guān)鍵字、鎖、以及重入性等，下節(jié)詳細(xì)介紹)。這里的目的只是為了幫助更好 的理解內(nèi)存屏障的工作原理。

內(nèi)存屏障的意義重大，是確保正確并發(fā)的關(guān)鍵。通過(guò)正確的設(shè)置內(nèi)存屏障可以確保指令按照我們期望的順序執(zhí)行。這里需要注意的是內(nèi)存屏蔽只應(yīng)該作用于需要同步的指令或者還可以包含周?chē)噶畹钠?。如果用?lái)同步所有指令，目前絕大多數(shù)處理器架構(gòu)的設(shè)計(jì)就會(huì)毫無(wú)意義。

延伸閱讀

您可以通過(guò)以下導(dǎo)航來(lái)在 Gitbook 中閱讀筆者的系列文章，涵蓋了技術(shù)資料歸納、編程語(yǔ)言與理論、Web 與大前端、服務(wù)端開(kāi)發(fā)與基礎(chǔ)架構(gòu)、云計(jì)算與大數(shù)據(jù)、數(shù)據(jù)科學(xué)與人工智能、產(chǎn)品設(shè)計(jì)等多個(gè)領(lǐng)域：

• 知識(shí)體系：《Awesome Lists | CS 資料集錦》、《Awesome CheatSheets | 速學(xué)速查手冊(cè)》、《Awesome Interviews | 求職面試必備》、《Awesome RoadMaps | 程序員進(jìn)階指南》、《Awesome MindMaps | 知識(shí)脈絡(luò)思維腦圖》、《Awesome-CS-Books | 開(kāi)源書(shū)籍（.pdf）匯總》

• 編程語(yǔ)言：《編程語(yǔ)言理論》、《Java 實(shí)戰(zhàn)》、《JavaScript 實(shí)戰(zhàn)》、《Go 實(shí)戰(zhàn)》、《Python 實(shí)戰(zhàn)》、《Rust 實(shí)戰(zhàn)》

• 軟件工程、模式與架構(gòu)：《編程范式與設(shè)計(jì)模式》、《數(shù)據(jù)結(jié)構(gòu)與算法》、《軟件架構(gòu)設(shè)計(jì)》、《整潔與重構(gòu)》、《研發(fā)方式與工具》

• Web 與大前端：《現(xiàn)代 Web 開(kāi)發(fā)基礎(chǔ)與工程實(shí)踐》、《數(shù)據(jù)可視化》、《iOS》、《Android》、《混合開(kāi)發(fā)與跨端應(yīng)用》

• 服務(wù)端開(kāi)發(fā)實(shí)踐與工程架構(gòu)：《服務(wù)端基礎(chǔ)》、《微服務(wù)與云原生》、《測(cè)試與高可用保障》、《DevOps》、《Node》、《Spring》、《信息安全與***測(cè)試》

• 分布式基礎(chǔ)架構(gòu)：《分布式系統(tǒng)》、《分布式計(jì)算》、《數(shù)據(jù)庫(kù)》、《網(wǎng)絡(luò)》、《虛擬化與編排》、《云計(jì)算與大數(shù)據(jù)》、《Linux 與操作系統(tǒng)》

• 數(shù)據(jù)科學(xué)，人工智能與深度學(xué)習(xí)：《數(shù)理統(tǒng)計(jì)》、《數(shù)據(jù)分析》、《機(jī)器學(xué)習(xí)》、《深度學(xué)習(xí)》、《自然語(yǔ)言處理》、《工具與工程化》、《行業(yè)應(yīng)用》

• 產(chǎn)品設(shè)計(jì)與用戶體驗(yàn)：《產(chǎn)品設(shè)計(jì)》、《交互體驗(yàn)》、《項(xiàng)目管理》

• 行業(yè)應(yīng)用：《行業(yè)迷思》、《功能域》、《電子商務(wù)》、《智能制造》

此外，你還可前往 xCompass 交互式地檢索、查找需要的文章/鏈接/書(shū)籍/課程；或者在 MATRIX 文章與代碼索引矩陣中查看文章與項(xiàng)目源代碼等更詳細(xì)的目錄導(dǎo)航信息。最后，你也可以關(guān)注微信公眾號(hào)：『某熊的技術(shù)之路』以獲取最新資訊。