十年網(wǎng)站開發(fā)經(jīng)驗 + 多家企業(yè)客戶 + 靠譜的建站團(tuán)隊
量身定制 + 運(yùn)營維護(hù)+專業(yè)推廣+無憂售后,網(wǎng)站問題一站解決
參考Google的這個問題what is a store buffer?
一、硬件方面的問題
1、背景
在現(xiàn)代系統(tǒng)的CPU中,所有的內(nèi)存訪問都是通過層層緩存進(jìn)行的。CPU的讀/寫(以及指令)單元正常情況下甚至都不能直接與內(nèi)存進(jìn)行訪問,這是物理結(jié)構(gòu)決定的。CPU和緩存進(jìn)行通信,而緩存才能與內(nèi)存進(jìn)行通信。處理器保證從系統(tǒng)內(nèi)存中讀取或者寫入一個字節(jié)是原子的,但是復(fù)雜的內(nèi)存操作處理器是不能保證其原子性的,比如跨總線操作、跨多個緩存行和跨頁表的訪問。但是處理器提供了總線鎖定和緩存鎖定兩個機(jī)制來保證復(fù)雜內(nèi)存操作的原子性。
硬件緩存模型如下圖所示:
解釋:具體這些會在MESI協(xié)議里面講,先有個概念
(1) CPU就是CPU
(2)Store Bufferes存儲緩存
(3)Cache 就是代表高速緩存
(4)Invalidate Queues 無效隊列
(5)Memory 內(nèi)存
2、問題與解決
問題:如果有多個CPU,每個CPU都有自己的緩存,其中一個修改了緩存,會發(fā)生什么?答案是什么也不會發(fā)生。我們希望擁有多組緩存的時候,需要它們保持同步?;蛘哒f,系統(tǒng)的內(nèi)存在各個CPU之間無法做到與生俱來的同步,我們實際上是需要一個大家都能遵守的方法來達(dá)到同步的目的。接下來看帶來的問題與解決方案。
(1)原子性問題
我們以一個原子操作的i++為例,來講解這個問題。
如果多個處理器同時對共享變量i進(jìn)行讀該寫操作,那么共享變量就會被多個處理器就行同時操作,這樣的讀寫該操作就不是原子的,操作完成之后共享變量的值會和期望的不一致。如果i=1,我們CPU0進(jìn)行i++操作,CPU1進(jìn)行i++操作,我們期望結(jié)果是3,但是有可能結(jié)果是2。
原因可能是多個處理器同時從各自的緩存中讀取變量i,分別進(jìn)行i++,操作,然后分別寫入系統(tǒng)。這就不是原子的了,讀改寫被分開了。所以要解決這個問題就必須保證CPU0進(jìn)行讀改寫時,CPU1不行進(jìn)行讀改寫操作。
通過總線鎖來保證原子性
所謂處理器總線鎖就是使用處理器提供的一個LOCK#信號,當(dāng)一個處理器總線上輸出此信號時,其它處理器的請求將被阻塞住,那么該處理器可以獨(dú)占共享內(nèi)存。
通過緩存鎖定來保證原子性
總線鎖定把CPU和內(nèi)存之間的通信鎖住了,這使得鎖定期間,其它處理器不能操作其它內(nèi)存地址的數(shù)據(jù),所以總線鎖的開銷比較大,所以就引進(jìn)了緩存鎖定來代替總線鎖定來進(jìn)行優(yōu)化。
所謂“緩存鎖定”是指內(nèi)存區(qū)域如果被緩存在處理器的緩存中,那么當(dāng)它執(zhí)行鎖操作會寫內(nèi)存時,處理器不需要再總線上加鎖,而是修改內(nèi)存地址,并允許處理器的緩存一致性協(xié)議“來保證操作的原子性,因為緩存一致性協(xié)議會阻止同時修改由兩個以上處理器緩存區(qū)的內(nèi)存區(qū)域數(shù)據(jù),當(dāng)其它處理器回寫已被修改的緩存行數(shù)據(jù)實,會使其它緩存行無效。
緩存一致性協(xié)議(MESI)大多數(shù)支持
結(jié)合硬件緩存模型圖來講解:
已修改(Modified)緩存段,屬于臟段,它們已經(jīng)被所屬的處理器修改了。如果一個段處于已修改狀態(tài),那么它在其他處理器緩存中的拷貝馬上會變成失效狀態(tài),這個規(guī)律和E狀態(tài)一樣。此外,已修改緩存段如果被丟棄或標(biāo)記為失敗,那么先要把它的內(nèi)容回寫到內(nèi)存中-這和回寫模式下常規(guī)的臟段處理方。
狀態(tài)轉(zhuǎn)換時需要發(fā)送的消息:
當(dāng)前狀態(tài) | 操作 | 操作分析 | 之后狀態(tài) |
---|---|---|---|
M | 本核讀(read) | M表示已修改,緩存和內(nèi)存不一致,本核讀緩存中取值,狀態(tài)不變 | M |
M | 本核寫(write) | 本核修改內(nèi)容,已經(jīng)為已修改,再次修改狀態(tài)不變 | M |
M | other核讀(read) | 當(dāng)本核監(jiān)聽到總線別的核要讀取內(nèi)存時,需要先將數(shù)據(jù)寫到內(nèi)存,然后其它核在讀,和別的核共享,狀態(tài)變?yōu)镾 | S |
M | other核寫(write) | 當(dāng)本核監(jiān)聽到總線別的核要寫時,需要先將本數(shù)據(jù)寫到內(nèi)存,然后在讓其它核在這個基礎(chǔ)上修改,狀態(tài)變?yōu)镮 | I |
E | 本核讀(read) | E表示獨(dú)占,緩存和內(nèi)存一致,緩存讀取,狀態(tài)不變 | E |
E | 本核寫(write) | 本核修改內(nèi)容,寫入緩存,緩存和內(nèi)存不一致,狀態(tài)改變?yōu)镸 | M |
E | other核讀(read) | 當(dāng)本核監(jiān)聽到總線別的核要讀取內(nèi)存時,和別的核共享,狀態(tài)變?yōu)镾 | S |
E | other核寫(write) | 當(dāng)本核監(jiān)聽到總線別的核要寫時,首先肯定在這之前先共享了數(shù)據(jù)S,然后在由其它核修改數(shù)據(jù),寫回內(nèi)存,本緩存變?yōu)闊o效I | I |
S | 本核讀(read) | S表示分享,多個核共享數(shù)據(jù),和內(nèi)存中一致,從緩存中讀,狀態(tài)不變S | S |
S | 本核寫(write) | 本核修改內(nèi)容,發(fā)起總線請求,其它核設(shè)置無效I,然后修改,寫入緩存,緩存和內(nèi)存不一致,狀態(tài)改變?yōu)镸 | M |
S | other核讀(read) | 當(dāng)本核監(jiān)聽到總線別的核要讀取內(nèi)存時,和別的核共享,狀態(tài)變?yōu)镾 | S |
S | other核寫(write) | 當(dāng)本核監(jiān)聽到總線別的核要寫時,本核數(shù)據(jù)無效,狀態(tài)改變?yōu)镮 | I |
I | 本核讀(read) | I表示無效,緩存沒有數(shù)據(jù),需要讀取內(nèi)存,情況如下:(1) 別的核沒有數(shù)據(jù),從內(nèi)存中讀取,獨(dú)占E。(2)別的核有數(shù)據(jù),可能為E或S,是E就先寫入內(nèi)存,然后本核讀取內(nèi)存,本核和其它核狀態(tài)都是S | S或者E |
I | 本核寫(write) | 首先要讀,然后在寫,如果是E,修改然后狀態(tài)為E,如果是S,通知其它線程緩存無效,然后改狀態(tài)為M | M |
I | other核讀(read) | 和本核無關(guān) | I |
I | other核寫(write) | 和本核無關(guān) | I |
我們發(fā)現(xiàn)上面的狀態(tài)轉(zhuǎn)換只有當(dāng)緩存段處于E或M狀態(tài)時,處理器才能去寫它,也就是說只有這兩種狀態(tài)下,處理器是獨(dú)占這個緩存段的。當(dāng)處理器想寫某個緩存段時,如果它沒有獨(dú)占權(quán),它必須先發(fā)送一條“我要獨(dú)占權(quán)”的請求給總線,這會通知其他處理器,把它們擁有的同一緩存段的拷貝失效(如果它們有的話)。只有在獲得獨(dú)占權(quán)后,處理器才能開始修改數(shù)據(jù)——并且此時,這個處理器知道,這個緩存段只有一份拷貝,在我自己的緩存里,所以不會有任何沖突。反之,如果有其他處理器想讀取這個緩存段(我們馬上能知道,因為我們一直在窺探總線),獨(dú)占或已修改的緩存段必須先回到“共享”狀態(tài)。如果是已修改的緩存段,那么還要先把內(nèi)容回寫到內(nèi)存中。
MESI協(xié)議的問題(性能)
我們來分析一個例子,如下代碼示例:
int a = 5;
public void add () {
a = a + 2;
}
假如現(xiàn)在有三個CPU,每個CPU都有a的緩存,狀態(tài)為S,現(xiàn)在CPU1要去修改a,我們要做些什么操作了,首先要申請總線,獨(dú)占這一緩存,獲取成功后,給CPU2、CPU3發(fā)生Invalidate消息,使CPU2、CPU3的緩存失效,然后CPU2、CPU3是本緩存失效后,回復(fù)確認(rèn)Invalidate Acknowledge消息,然后CPU1,才能去修改緩存,然后而這個過程中CPU1啥都不能干,這就浪費(fèi)了CPU的性能,所以硬件就提供了寫優(yōu)化策略。
Store Bufferes和Invalidate Queues
Store Bufferes 緩存存儲,當(dāng)處理器需要把修改寫入緩存時,然后在寫入內(nèi)存這個過程時,我們處理器不需要等待了。只需要把指數(shù)據(jù)寫入Store Bufferes,然后發(fā)生Invalidate消息給其它CPU,然后本CPU就可以去執(zhí)行其它指令了,等到我們都收所有回復(fù)確認(rèn)Invalidate Acknowledge消息,在把Store Bufferes消息寫回緩存修改狀態(tài)為(M),如果有其它CPU來讀,就會刷新到內(nèi)存,狀態(tài)變?yōu)镾。Store Bufferes 的作用是讓 CPU 需要寫的時候僅僅將其操作交給 Store Buffere,然后繼續(xù)執(zhí)行下去,Store Bufferes 在某個時刻就會完成一系列的同步行為。
Invalidate Queues 無效隊列,這么理解吧我們在修改數(shù)據(jù)時,需要使其它處理器數(shù)據(jù)失效,這其實也是一系列的寫操作,如果我們這些消息都交給Store Bufferes處理,Store Bufferes速度快,但是容量很小,所以就設(shè)計出了Invalidate Queues,當(dāng)別的CPU收到Invalidate消息時,把這個操作加入無效隊列,然后快速返回Invalidate Acknowledge消息,讓發(fā)起者做后續(xù)操作,然后Invalidate并不是馬上處理,而只是加入了隊列,也就是說其實不是立刻讓本CPU的緩存數(shù)據(jù)失效,而是等CPU處理無效隊列里的無效消息時。
(2)可見性問題(Store Bufferes和Invalidate Queues產(chǎn)生)
Store Bufferes和Invalidate Queues問題;問題分析,我們發(fā)現(xiàn)Store Bufferes的寫入緩存和Invalidate Queues的處理失效,都是最終一致性的表現(xiàn),這在單核操作時可能沒什么問題,如果是多核操作(其實就是Java的并發(fā))那么數(shù)據(jù)修改的可見性就是不確定的。
代碼分析:兩個CPU同時操作()
我么假設(shè)此時numone的狀態(tài)為共享(S),flag狀態(tài)為E,
我們假設(shè)CPU1中的執(zhí)行update方法,CPU2執(zhí)行test方法。
現(xiàn)在CPU1需要修改numone,由于numone為共享狀態(tài),所以緩存和內(nèi)存一致,所以我們獲取總線,通知其它CPU緩存的numone變?yōu)闊o效(I),然后CPU1把numone的8加入Store Bufferes里面,就去執(zhí)行其它指令了,CPU1執(zhí)行修改flag,因為flag為E,所以直接修改,寫入緩存。CPU2,執(zhí)行test方法,由于CPU1修改了flag所以需要刷新到內(nèi)存,然后CPU2去從內(nèi)存中讀取flag,CPU1和CPU2狀態(tài)變?yōu)镾,此時CPU2可能收到無效消息,加入無效隊列,然后我們打印numone,結(jié)果是多少了,不確定,因為CPU1 何時把numone刷新至內(nèi)存,CPU2何時執(zhí)行無效消息,這都是不確定的,所以我們打印的numone可能是8或者0。
其實也可以理解為CPU指令的重排序,CPU1flag的寫入發(fā)生在了numone的前面,導(dǎo)致CPU2打印時不確定這個值是否寫入;CPU2的讀取numone可能發(fā)生在了無效命令前面。
public class StoreBufferesQuestion {
private int numone = 0;
private Boolean flag = false;
public void update() {
numone = 8;
flag = true;
}
public void test() {
while (flag) {
// numone 是多少?
System.out.println(numone);
}
}
}
Store Bufferes和Invalidate Queues問題解決:硬件 level 上很難揣度軟件上這種前后數(shù)據(jù)依賴關(guān)系,因此往往無法通過某種手段自動的避免這種問題,因而只有通過軟件的手段表示(對應(yīng)也需要硬件提供某種指令來支持這種語義),這個就是 Memory Barrier(內(nèi)存屏障)。
Store Memory Barrier(a.k.a. ST, SMB, smp_wmb)是一條告訴處理器在執(zhí)行這之后的指令之前,應(yīng)用所有已經(jīng)在存儲緩存(store buffer)中的保存的指令。
Load Memory Barrier (a.k.a. LD, RMB, smp_rmb)是一條告訴處理器在執(zhí)行任何的加載前,先應(yīng)用所有已經(jīng)在失效隊列中的失效操作的指令。
再看下如下代碼:
這樣就保證了可見性。
public class StoreBufferesQuestion {
private int numone = 0;
private Boolean flag = false;
public void update() {
numone = 8;
Store Memory Barrier指令;刷新Store Bufferes
flag = true;
}
public void test() {
while (flag) {
// numone 是多少?
Load Memory Barrier指令;執(zhí)行時效消息
System.out.println(numone);
}
}
}
總結(jié)
我們看到硬件為了解決原子性,使用了總線鎖和緩存鎖,緩存鎖是基于緩存一致性協(xié)議實現(xiàn)的。緩存一致性協(xié)議帶來了指令執(zhí)行順序問題,影響了多核處理器之間的可見性。因為硬件無法知道我們這些軟件數(shù)據(jù)在執(zhí)行時的指令順序,所以硬件就制定了這樣一套硬件規(guī)則來滿足硬件需求,提供Memory Barrier來解決方案來應(yīng)對軟件可能發(fā)生的問題,具體需要我們軟件自己去實現(xiàn)。
二、軟件層面的問題(JAVA)
我們在編寫并發(fā)程序時,也會出現(xiàn)問題原子性問題、可見性問題。
Java如何實現(xiàn)原子操作
在Java中可以通過鎖和循環(huán)CAS的方式實現(xiàn)原子操作。
CAS是英文單詞CompareAndSwap的縮寫,中文意思是:比較并替換。CAS需要有3個操作數(shù):內(nèi)存地址V,舊的預(yù)期值A(chǔ),即將要更新的目標(biāo)值B。從Java 1.5開始,JDK并發(fā)包提供了一些類支持原子操作。
CAS實現(xiàn)原子操作存在的問題
1)ABA問題。因為CAS需要在操作值得時候,檢查值沒有變化,如果沒有發(fā)生變化則更新,但是一個值原來是A,變成了B,由變成了A,那么使用CAS允許檢查時會發(fā)現(xiàn)它的值沒有發(fā)生變化,但是實際卻發(fā)生了變化。ABA問題的解決思路就是使用版本號,每次變量更新的時候版本號加1,那么A-B-A就會變成1A-2B-3A.從Java1.5開始,JDK的atomic包里提供了一個類AtomicStampedReference來解決ABA問題。這個類的compareAndSet方法作用是首先檢查當(dāng)前引用是否等于預(yù)期引用,并且檢查當(dāng)前標(biāo)志是否等于預(yù)期標(biāo)志,如果全部相等,則以原子方式將引用和該標(biāo)志的值設(shè)置為給定的更新值。
2)循環(huán)時間長開銷大。自旋CAS如果長時間不成功,會給CPU帶來非常大的執(zhí)行開銷。
3)只能保證一個共享變量的原子操作。
使用鎖機(jī)制來實現(xiàn)原子性:鎖機(jī)制保證了只有獲得鎖的線程才能夠操作鎖定的內(nèi)存區(qū)域。JVM內(nèi)部實現(xiàn)了很多種鎖機(jī)制。
可見性問題
Java線程之間的通信對程序員完全透明,內(nèi)存可見性問題很容易困擾Java程序員。
Java內(nèi)存模型的抽象結(jié)構(gòu)
在Java中,所有實例域、靜態(tài)域和數(shù)組元素都存在堆內(nèi)存中,堆內(nèi)存在線程之間共享。局部變量,方法定義參數(shù)和異常處理器參數(shù)不會再線程之間共享,他們不會存在內(nèi)存可見性問題,也不受內(nèi)存模型的影響。
Java線程之間的通信由Java內(nèi)存模型控制,JMM決定一個線程對共享變量的寫入何時對另一個線程可見。從抽象的角度來看,JMM定義了線程和主內(nèi)存之間的抽象關(guān)系:線程之間的共享變量存儲在主內(nèi)存中,每個線程都有一個私有的本地內(nèi)存,本地內(nèi)存中存儲了該線程讀/寫共享變量的副本。本地內(nèi)存是JMM的一個抽象概念,并不真實存在。它涵蓋了緩存、寫緩存區(qū)、寄存器以及其他的硬件和編譯優(yōu)化。如下圖所示。
線程之間的通信:如下圖所示
1)線程A把本地內(nèi)存A中更新過的共享變量刷新到主內(nèi)存中去。
2)線程B到主內(nèi)存中去讀取線程A 已更新過的共享變量。
影響可見性的因素(重排序)
在執(zhí)行程序時,為了提高性能,編譯器和處理器常常會對指令做重排序。分為3中類型。
1)編譯器重排序。編譯器在不改變單線程語義的前提下,可以重新安排語句的執(zhí)行順序。
2)指令級并行的重排序?,F(xiàn)代處理器采用了指令并行技術(shù)。如果不存在數(shù)據(jù)依賴性,處理器可以改變語句對應(yīng)機(jī)器指令的執(zhí)行順序。
3)內(nèi)存系統(tǒng)的重排序。由于處理器使用緩存和讀/寫緩沖區(qū),這使得加載和存儲操作看上去可能是亂序執(zhí)行。(處理器的重排序)
從Java源代碼到最終的指令序列,會經(jīng)歷下面三種排序,如下圖所示:
重排序的規(guī)則;as-if-serial語義:不管怎么重排序,單線程程序的執(zhí)行結(jié)果不能被改變。編譯和處理器都必須遵循as-if-serial語義。但是如果操作之間沒有數(shù)據(jù)依賴關(guān)系,這些操作就可以被重排序。
對于處理器的(內(nèi)存和指令)重排序,JMM的處理器重排序規(guī)則會要求Java編譯器生成指令時,插入特定類型的內(nèi)存屏障指令。JMM把內(nèi)存屏障分為4類:
屏障類型 | 指令示例 | 說明 |
---|---|---|
LoadLoad Barries | Load1;LoadLoad;Load2 | 確保Load1數(shù)據(jù)的裝載先于Load2及后續(xù)所有裝載指令的裝載 |
StoreStore Barries | Store1;LoadLoad;Store2 | 確保Store1數(shù)據(jù)對其它處理器可見(刷新到內(nèi)存)先于Store2機(jī)后續(xù)所有指令的存儲 |
LoadStore Barries | Load1;LoadLoad;Store2 | 確保Load1數(shù)據(jù)的裝載先于Store2及所有后續(xù)的存儲指令的刷新到內(nèi)存 |
StoreLoad Barries | Store1;LoadLoad;Load2 | 確保Store1數(shù)據(jù)對其他處理器變得可見(刷新到內(nèi)存)先于Load2及后續(xù)所有指令的裝載 |
happens-before(JMM可見性的保證)
JSR-133使用happens-before的概念來指定連個操作之間的執(zhí)行順序。由于這兩個操作可以在一個線程之內(nèi),也可以在不同線程之間。因此,JMM可以通過happens-before關(guān)系向程序員提供跨線程的內(nèi)存可見性。
happens-before關(guān)系定義
(1)如果一個操作happens-before另一個操作,那么第一個操作的執(zhí)行結(jié)果將對第二個操作可見,而且第一個操作的執(zhí)行順序排在第二個操作前面。這是JMM對程序員的保證。
(2)兩個操作之間存在happens-before關(guān)系,并不意味著Java平臺的具體實現(xiàn)必須要按照happens-before的指向順序來執(zhí)行。如果重排序之后的執(zhí)行結(jié)果,與按happens-before關(guān)系的執(zhí)行結(jié)果一致,這種重排序并不非法(也就是說,JMM允許這種重排序)。這是JMM對重排序指定的規(guī)則,只要不改變程序的執(zhí)行結(jié)果(單線程和正確同步的線程),怎么優(yōu)化都行。
happens-before規(guī)則(滿足規(guī)則即滿足可見性)
1)程序順序規(guī)則:一個線程中的每個操作,happens-before與該線程中的任意后續(xù)操作。
2)監(jiān)視器鎖規(guī)則:對一個鎖的解鎖,happens-before與隨后對這個鎖的加鎖。
3)volatile變量規(guī)則:對一個volatile域的寫,happens-before于任意后續(xù)對這個volatile域的讀。
4)傳遞性:如果A happens-before B,且B happens-before C,那么A happens-before C。
5)start()規(guī)則:如果線程A 執(zhí)行操作ThreadB.start()(線程B啟動),那么A線程的ThreadB.start()操作happens-before于線程B中的任意操作。
6)join規(guī)則:如果線程A執(zhí)行操作ThreadB.join()并成功返回,那么線程B中的任意操作happens-before于線程A從ThreadB.join()操作成功的返回。
總結(jié):Java提供了鎖和CAS來保證原子性操作,通過JMM的規(guī)則來禁止一些重排序,通過JMM的happens-before規(guī)則來保證內(nèi)存的可見性。我們可以看到規(guī)則里面有一些關(guān)鍵字,volatile(通過內(nèi)存屏障)、鎖保證了可見性,我們在下面的章節(jié)詳解---------------------------以下是個人理解:我們結(jié)合硬件緩存模型來看,其實JMM是對處理器緩存模型的一種實現(xiàn),硬件實現(xiàn)了最終緩存在一致性的方案,并提供了強(qiáng)一致性緩存的解決方案(內(nèi)存屏障的指令),JMM實現(xiàn)了這個方案,在我們需要的時候(插入內(nèi)存屏障)提供強(qiáng)大的可見性保證,不需要時遵循硬件的優(yōu)化策略(可以進(jìn)行指令重排序優(yōu)化,提高執(zhí)行性能)。
創(chuàng)新互聯(lián)www.cdcxhl.cn,專業(yè)提供香港、美國云服務(wù)器,動態(tài)BGP最優(yōu)骨干路由自動選擇,持續(xù)穩(wěn)定高效的網(wǎng)絡(luò)助力業(yè)務(wù)部署。公司持有工信部辦法的idc、isp許可證, 機(jī)房獨(dú)有T級流量清洗系統(tǒng)配攻擊溯源,準(zhǔn)確進(jìn)行流量調(diào)度,確保服務(wù)器高可用性。佳節(jié)活動現(xiàn)已開啟,新人活動云服務(wù)器買多久送多久。