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

創(chuàng)新互聯(lián)建站總部坐落于成都市區(qū)，致力網(wǎng)站建設(shè)服務(wù)有成都網(wǎng)站建設(shè)、做網(wǎng)站、網(wǎng)絡(luò)營銷策劃、網(wǎng)頁設(shè)計(jì)、網(wǎng)站維護(hù)、公眾號搭建、微信小程序開發(fā)、軟件開發(fā)等為企業(yè)提供一整套的信息化建設(shè)解決方案。創(chuàng)造真正意義上的網(wǎng)站建設(shè)，為互聯(lián)網(wǎng)品牌在互動行銷領(lǐng)域創(chuàng)造價(jià)值而不懈努力！

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

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

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

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

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

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

并發(fā)與并行

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

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

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

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

具體而言，早期的 redis（6.0 版本后也引入了多線程）會是一個(gè)很好地區(qū)分并發(fā)和并行的例子，它本身是一個(gè)單線程的數(shù)據(jù)庫，但是可以通過多路復(fù)用與事件循環(huán)的方式來提供并發(fā)地 IO 服務(wù)。這是因?yàn)槎嗪瞬⑿斜举|(zhì)上會有很大的一個(gè)同步的代價(jià)，特別是在鎖或者信號量的情況下。因此，Redis 利用了單線程的事件循環(huán)來保證一系列的原子操作，從而保證了即使在高并發(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ā)維度

線程級并發(fā)

從 20 世紀(jì) 60 年代初期出現(xiàn)時(shí)間共享以來，計(jì)算機(jī)系統(tǒng)中就開始有了對并發(fā)執(zhí)行的支持；傳統(tǒng)意義上，這種并發(fā)執(zhí)行只是模擬出來的，是通過使一臺計(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è)集成電路芯片上：

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

超線程，有時(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è)線程。

指令級并發(fā)

在較低的抽象層次上，現(xiàn)代處理器可以同時(shí)執(zhí)行多條指令的屬性稱為指令級并行。實(shí)每條指令從開始到結(jié)束需要長得多的時(shí)間，大約 20 個(gè)或者更多的周期，但是處理器使用了非常多的聰明技巧來同時(shí)處理多達(dá) 100 條的指令。在流水線中，將執(zhí)行一條指令所需要的活動劃分成不同的步驟，將處理器的硬件組織成一系列的階段，每個(gè)階段執(zhí)行一個(gè)步驟。這些階段可以并行地操作，用來處理不同指令的不同部分。我們會看到一個(gè)相當(dāng)簡單的硬件設(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 處理器都具有并行地對 4 對單精度浮點(diǎn)數(shù)（C 數(shù)據(jù)類型 float）做加法的指令。

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

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

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

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

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

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

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

并發(fā)級別

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

阻塞：阻塞是指一個(gè)線程進(jìn)入臨界區(qū)后，其它線程就必須在臨界區(qū)外等待，待進(jìn)去的線程執(zhí)行完任務(wù)離開臨界區(qū)后，其它線程才能再進(jìn)去。
無饑餓：線程排隊(duì)先來后到，不管優(yōu)先級大小，先來先執(zhí)行，就不會產(chǎn)生饑餓等待資源，也即公平鎖；相反非公平鎖則是根據(jù)優(yōu)先級來執(zhí)行，有可能排在前面的低優(yōu)先級線程被后面的高優(yōu)先級線程插隊(duì)，就形成饑餓
無障礙：共享資源不加鎖，每個(gè)線程都可以自有讀寫，單監(jiān)測到被其他線程修改過則回滾操作，重試直到單獨(dú)操作成功；風(fēng)險(xiǎn)就是如果多個(gè)線程發(fā)現(xiàn)彼此修改了，所有線程都需要回滾，就會導(dǎo)致死循環(huán)的回滾中，造成死鎖
無鎖：無鎖是無障礙的加強(qiáng)版，無鎖級別保證至少有一個(gè)線程在有限操作步驟內(nèi)成功退出，不管是否修改成功，這樣保證了多個(gè)線程回滾不至于導(dǎo)致死循環(huán)
無等待：無等待是無鎖的升級版，并發(fā)編程的最高境界，無鎖只保證有線程能成功退出，但存在低級別的線程一直處于饑餓狀態(tài)，無等待則要求所有線程必須在有限步驟內(nèi)完成退出，讓低級別的線程有機(jī)會執(zhí)行，從而保證所有線程都能運(yùn)行，提高并發(fā)度。

量化模型

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

Amdahl 定律

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

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

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

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

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

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

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

Amdahl 定律旨在說明，多核 CPU 對系統(tǒng)進(jìn)行優(yōu)化時(shí)，優(yōu)化的效果取決于 CPU 的數(shù)量以及系統(tǒng)中的串行化程序的比重；如果僅關(guān)注于提高 CPU 數(shù)量而不降低程序的串行化比重，也無法提高系統(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è)線程。在存儲管理一節(jié)中我們介紹了計(jì)算機(jī)系統(tǒng)中的不同的存儲類別：

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

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

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

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

原子性

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

i++

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

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

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

有序性

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

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

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

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

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

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

可見性

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

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

CPU 讀寫流程

傳統(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í)寫入新的數(shù)據(jù)。所以 CPU 通過 Store Buffer 和 Invalidate Queue 組件來降低這類操作的延時(shí)。如圖：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

某些 Java 編譯器會將沒有使用到的補(bǔ)齊數(shù)據(jù), 即示例代碼中的 6 個(gè)長整型在編譯時(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í)行亂序的問題可以分別使用優(yōu)化屏障 (Optimization Barrier)和內(nèi)存屏障 (Memory Barrier)這兩個(gè)機(jī)制來解決：

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

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

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

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

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

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

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

網(wǎng)站建設(shè)知識

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