科普：CPU緩存一致性協(xié)議
CPU為何要有高速緩存
CPU在摩爾定律的指導(dǎo)下以每18個(gè)月翻一番的速度在發(fā)展，然而內(nèi)存和硬盤(pán)的發(fā)展速度遠(yuǎn)遠(yuǎn)不及CPU。這就造成了高性能能的內(nèi)存和硬盤(pán)價(jià)格及其昂貴。然而CPU的高度運(yùn)算需要高速的數(shù)據(jù)。為了解決這個(gè)問(wèn)題，CPU廠商在CPU中內(nèi)置了少量的高速緩存以解決IO速度和CPU運(yùn)算速度之間的不匹配問(wèn)題。
在CPU訪問(wèn)存儲(chǔ)設(shè)備時(shí)，無(wú)論是存取數(shù)據(jù)抑或存取指令，都趨于聚集在一片連續(xù)的區(qū)域中，這就被稱(chēng)為局部性原理。
時(shí)間局部性（Temporal Locality）：如果一個(gè)信息項(xiàng)正在被訪問(wèn)，那么在近期它很可能還會(huì)被再次訪問(wèn)。
比如循環(huán)、遞歸、方法的反復(fù)調(diào)用等。
空間局部性（Spatial Locality）：如果一個(gè)存儲(chǔ)器的位置被引用，那么將來(lái)他附近的位置也會(huì)被引用。
比如順序執(zhí)行的代碼、連續(xù)創(chuàng)建的兩個(gè)對(duì)象、數(shù)組等。
帶有高速緩存的CPU執(zhí)行計(jì)算的流程
程序以及數(shù)據(jù)被加載到主內(nèi)存
指令和數(shù)據(jù)被加載到CPU的高速緩存
CPU執(zhí)行指令，把結(jié)果寫(xiě)到高速緩存
高速緩存中的數(shù)據(jù)寫(xiě)回主內(nèi)存
目前流行的多級(jí)緩存結(jié)構(gòu)
由于CPU的運(yùn)算速度超越了1級(jí)緩存的數(shù)據(jù)IO能力，CPU廠商又引入了多級(jí)的緩存結(jié)構(gòu)。
多級(jí)緩存結(jié)構(gòu)
多核CPU多級(jí)緩存一致性協(xié)議MESI
多核CPU的情況下有多個(gè)一級(jí)緩存，如何保證緩存內(nèi)部數(shù)據(jù)的一致,不讓系統(tǒng)數(shù)據(jù)混亂。這里就引出了一個(gè)一致性的協(xié)議MESI。
緩存一致性協(xié)議MESI
MESI（Modified Exclusive Shared Or Invalid）(也稱(chēng)為伊利諾斯協(xié)議，是因?yàn)樵搮f(xié)議由伊利諾斯州立大學(xué)提出）是一種廣泛使用的支持寫(xiě)回策略的緩存一致性協(xié)議。
MESI協(xié)議中的狀態(tài)
CPU中每個(gè)緩存行（caceh line)使用4種狀態(tài)進(jìn)行標(biāo)記（使用額外的兩位(bit)表示):
M: 被修改（Modified)
該緩存行只被緩存在該CPU的緩存中，并且是被修改過(guò)的（dirty),即與主存中的數(shù)據(jù)不一致，該緩存行中的內(nèi)存需要在未來(lái)的某個(gè)時(shí)間點(diǎn)（允許其它CPU讀取請(qǐng)主存中相應(yīng)內(nèi)存之前）寫(xiě)回（write back）主存。
當(dāng)被寫(xiě)回主存之后，該緩存行的狀態(tài)會(huì)變成獨(dú)享（exclusive)狀態(tài)。
E: 獨(dú)享的（Exclusive)
該緩存行只被緩存在該CPU的緩存中，它是未被修改過(guò)的（clean)，與主存中數(shù)據(jù)一致。該狀態(tài)可以在任何時(shí)刻當(dāng)有其它CPU讀取該內(nèi)存時(shí)變成共享狀態(tài)（shared)。
同樣地，當(dāng)CPU修改該緩存行中內(nèi)容時(shí)，該狀態(tài)可以變成Modified狀態(tài)。
S: 共享的（Shared)
該狀態(tài)意味著該緩存行可能被多個(gè)CPU緩存，并且各個(gè)緩存中的數(shù)據(jù)與主存數(shù)據(jù)一致（clean)，當(dāng)有一個(gè)CPU修改該緩存行中，其它CPU中該緩存行可以被作廢（變成無(wú)效狀態(tài)（Invalid））。
I: 無(wú)效的（Invalid）
該緩存是無(wú)效的（可能有其它CPU修改了該緩存行）。
MESI狀態(tài)轉(zhuǎn)換圖
狀態(tài)之間的相互轉(zhuǎn)換關(guān)系也可以使用下表進(jìn)行表示。
操作
在一個(gè)典型系統(tǒng)中，可能會(huì)有幾個(gè)緩存（在多核系統(tǒng)中，每個(gè)核心都會(huì)有自己的緩存）共享主存總線，每個(gè)相應(yīng)的CPU會(huì)發(fā)出讀寫(xiě)請(qǐng)求，而緩存的目的是為了減少CPU讀寫(xiě)共享主存的次數(shù)。
一個(gè)緩存除在Invalid狀態(tài)外都可以滿足cpu的讀請(qǐng)求，一個(gè)Invalid的緩存行必須從主存中讀取（變成S或者 E狀態(tài)）來(lái)滿足該CPU的讀請(qǐng)求。
一個(gè)寫(xiě)請(qǐng)求只有在該緩存行是M或者E狀態(tài)時(shí)才能被執(zhí)行，如果緩存行處于S狀態(tài)，必須先將其它緩存中該緩存行變成Invalid狀態(tài)（也既是不允許不同CPU同時(shí)修改同一緩存行，即使修改該緩存行中不同位置的數(shù)據(jù)也不允許）。該操作經(jīng)常作用廣播的方式來(lái)完成，例如：RequestFor Ownership (RFO)。
緩存可以隨時(shí)將一個(gè)非M狀態(tài)的緩存行作廢，或者變成Invalid狀態(tài)，而一個(gè)M狀態(tài)的緩存行必須先被寫(xiě)回主存。
一個(gè)處于M狀態(tài)的緩存行必須時(shí)刻監(jiān)聽(tīng)所有試圖讀該緩存行相對(duì)就主存的操作，這種操作必須在緩存將該緩存行寫(xiě)回主存并將狀態(tài)變成S狀態(tài)之前被延遲執(zhí)行。
一個(gè)處于S狀態(tài)的緩存行也必須監(jiān)聽(tīng)其它緩存使該緩存行無(wú)效或者獨(dú)享該緩存行的請(qǐng)求，并將該緩存行變成無(wú)效（Invalid）。
一個(gè)處于E狀態(tài)的緩存行也必須監(jiān)聽(tīng)其它緩存讀主存中該緩存行的操作，一旦有這種操作，該緩存行需要變成S狀態(tài)。
對(duì)于M和E狀態(tài)而言總是精確的，他們?cè)诤驮摼彺嫘械恼嬲隣顟B(tài)是一致的。而S狀態(tài)可能是非一致的，如果一個(gè)緩存將處于S狀態(tài)的緩存行作廢了，而另一個(gè)緩存實(shí)際上可能已經(jīng)
獨(dú)享了該緩存行，但是該緩存卻不會(huì)將該緩存行升遷為E狀態(tài)，這是因?yàn)槠渌彺娌粫?huì)廣播他們作廢掉該緩存行的通知，同樣由于緩存并沒(méi)有保存該緩存行的copy的數(shù)量，因此（即使有這種通知）也沒(méi)有辦法確定自己是否已經(jīng)獨(dú)享了該緩存行。
從上面的意義看來(lái)E狀態(tài)是一種投機(jī)性的優(yōu)化：如果一個(gè)CPU想修改一個(gè)處于S狀態(tài)的緩存行，總線事務(wù)需要將所有該緩存行的copy變成Invalid狀態(tài)，而修改E狀態(tài)的緩存不需要使用總線事務(wù)。
參考:
計(jì)算機(jī)體系結(jié)構(gòu)（第五版）－復(fù)習(xí)－MESI&MOESI協(xié)議
https://www.cnblogs.com/yanlong300/p/8986041.html
https://www.cnblogs.com/z00377750/p/9180644.html
END
