ch6第六章CacheCoherence

1、第六章 Cache Coherence6.1 Cache Coherence問題6.1.1 Cache Coherence的提出6.1.2 多個Cache不一致的原因6.1.3 兩種設(shè)計Cache一致性協(xié)議策略6.2 監(jiān)聽總線協(xié)議 6.2.1 寫一次協(xié)議6.3 基于目錄的Cache一致性協(xié)議 6.3.1 目錄的一般性問題6.3.2 全映射目錄6.3.3 有限目錄6.3.4 鏈式目錄6.4 三種Cache一致性策略 6.4.1 采用Write-Through策略的Cache 6.4.2 采用Write-Bach策略的Cache 6.4.3 采用Write-Once策略的Cache6.1 Cach

2、e Coherence問題6.1.1 Cache Coherence問題的提出 在多處理器系統(tǒng)中，多個Cache中，對應的copy內(nèi)容應該一致，如下圖：MemoryCachePCachePCacheP這幾個copy應該一致6.1.2 多個Cache不一致的原因 1.共享可寫數(shù)據(jù)的不一致性（sharing of writable data）P1P2更新前xxx處理機CachesharedmemoryP1P2寫通過xxxP1P2寫回xxx2.進程遷移的不一致性P1P2遷移前xx處理機CacheP1P2寫通過xxxP1P2寫回xxx上圖中： 右圖為：包含共享變量x的進程原來在P1上運行，并對x進行了

3、修改（但采取寫回策略，所以暫時沒有修改Memory），由于某種原因遷移到P2，修改過的x仍在P1的Cache中，P2運行時從Memory中得到x，這個x其實是“過時”的，所以造成了不一致。 中間圖為：P2中運行的進程對x進行了修改，采取寫通過策略，所以把Memory中的x也修改為x，由于某種原因該進程遷移到P1，但P1的Cache中仍為x，所以造成不一致。3. I/O操作（繞過Cache的I/O操作）P1P2xx存儲器P1P2寫通過xxP1P2寫回xxxxxxxI/O存儲器輸入存儲器輸出c1c2總線上圖中： 中間圖為：當I/O處理機將一個新的數(shù)據(jù)x寫入主存儲器時，繞過采用寫通過策略的cache

4、，則C1和共享存儲器之間產(chǎn)生了不一致。 右圖為：直接從主存儲器輸出數(shù)據(jù)時（繞過Cache），采用寫回策略的高速緩存產(chǎn)生不一致性。6.1.3 兩種設(shè)計Cache一致性協(xié)議策略 1.寫無效（write invalidate） 任一處理器寫它的私有Cache時，它都使所有其它的Cache中的副本失效。 對Write-through，它也更新memory中的副本（最終是一個Cache中的副本和memory中的副本是有效的）。 對Write-back，它使memory中的副本也失效（最終只有一個Cache中的副本是有效的）。2.寫更新（write update） 任一處理器寫它的私有Cache時，它都立

5、即更新所有其它的Cache中的副本。 對Write-through，它也更新主存儲器中的副本。 對Write-back，對存儲器中副本的更新延遲到這個Cache被置換的時刻。3. 示意圖 下圖表示數(shù)據(jù)塊x在共享存儲器和三臺處理機的Cache中的副本一致的情形。x共享存儲器CacheP1xP2xxP3總線處理機 下圖表示P1進行寫無效操作后的情形。寫通過：xI表示無效P1IP2xIP3寫回：xI表示無效P1IP2IIP3 下圖表示P1進行寫更新操作后的情形（寫通過）。xI表示無效P1xP2xxP34.寫無效的問題主要開銷在兩個方面： （1）作廢各Cache副本的開銷； （2）由作廢引起缺失造成的

6、開銷，即處理機需要訪問已經(jīng)作廢的數(shù)據(jù)時將引起Cache的缺失。 后果： 如果一個處理機經(jīng)常對某個塊連續(xù)寫，且各處理處理機間對共享塊的競爭較小，這時寫無效策略維護一致性的開銷是很小的。如發(fā)生嚴重競爭，即處理機之間對某個地址的共享數(shù)據(jù)競爭，將產(chǎn)生較多的作廢，引起更多的作廢缺失。結(jié)果是共享數(shù)據(jù)在各Cache間倒來倒去，產(chǎn)生顛簸現(xiàn)象，當緩存塊比較大時，這種顛簸現(xiàn)象更為嚴重。5. 寫更新的問題 由于更新時，所有的副本均需要更新，開銷很大。6.2 監(jiān)聽總線協(xié)議(Snoopy protocol) 通過總線監(jiān)聽機制實現(xiàn)Cache和共享存儲器之間的一致性。適用性分析： 適用于具有廣播能力的總線結(jié)構(gòu)多機系統(tǒng)，允許

7、每臺處理機監(jiān)聽其它處理機的存儲器訪問情況。 只適用于小規(guī)模的多處理機系統(tǒng)。6.2.1 寫一次(write-once)協(xié)議 寫無效監(jiān)聽一致性協(xié)議，將寫通過和寫回策略結(jié)合。 為了減少總線流量，高速緩存塊的第一次寫用寫通過方法，產(chǎn)生一份正確的主存儲器副本，并使其它的Cache中的副本無效，之后就采用寫回方法更新Cache與主存儲器。1. 一致性協(xié)議的內(nèi)容 （1）Cache可能出現(xiàn)的狀態(tài)集合 （2）共享主存的狀態(tài) （3）為維護一致性而引起的狀態(tài)轉(zhuǎn)換。2. 每份Cache中的副本可能出現(xiàn)的四種狀態(tài) （1）有效（valid state）：與主存儲器副本一致的Cache副本，即該副本未經(jīng)修改，所以這個Cac

8、he副本不是唯一的副本。 （2）保留（reserved state）：這一Cache副本是第一次修改，并用寫通過方法寫入主存，所以這一Cache副本和主存儲器副本一致。 （3）重寫（dirty state）：Cache副本不止一次被修改過，由于不再采用寫通過方法，所以這個Cache副本是唯一的副本。與存儲器和其它的Cache副本都不一致。主存儲器中的副本也是無效的。 （4）無效（invalid state）與存儲器或其它的Cache副本不一致，或在Cache中找不到。3. 局部命令（Local commands） （1）P-Read：本地處理機讀自己的Cache副本。 （2）P-Write：本

9、地處理機寫自己的Cache副本。4. 一致性命令 （1）Read-blk：從另一Cache讀一份有效的副本。 （2）Write-inv：在寫命中時在總線上廣播一個無效命令。 （3）Read-inv：在寫缺失時在總線上廣播一個無效命令。 Dirty: modified more than once, the only copy in the system; Invalid: inconsistent copy; Reserved: after written once, the only copy consistent with memory; Valid: A copy consistent

10、with the memory copy.5. Write-Once一致性協(xié)議狀態(tài)轉(zhuǎn)移圖其中，四種狀態(tài)的含義如下：InvalidValidDirtyReservedRead-inv(4)P-Write(1)P-Write(hit:local still dirty)P-Write(hit:local, not memoryupdate, local copy becomes dirty)P-Write(hit:local,updatememory copy,broadcastwrite-inv to all cache,local copybecomesreserved)Read-blk(3)

11、Read-inv(4)P-Read(2)Read-blk(3)Read-inv(4)/Write-inv(5)P-Read(hit:alwayslocal,no statetransition)下一節(jié)(用鼠標點擊連線來察看詳細信息）P-Write(1)(1)P-Write(miss: take a dirty copy from a remote cache, or from memory; send Read-inv to invalidate all copies; update local copy into a dirty one).InvalidValidDirtyReserved下

12、一節(jié)InvalidValidDirtyReserved(2)P-Read(miss: if no dirty copy exists, memory supplies a validcopy, otherwise, the cache inhibits memory and supplies a copyand updates memory. Both copies become valid).P-Read(2)下一節(jié)InvalidValidDirtyReserved(3)Read-blk(read from remote processors, the localcopy become va

13、lid).Read-blk(3)下一節(jié)InvalidValidDirtyReserved(3)Read-blk(read from remote processors, the localcopy become valid).Read-blk(3)下一節(jié)InvalidValidDirtyReserved(4)Read-inv(A remote cache reads a block during a write-miss,updates it and invalidates all other copies).Read-inv(4)下一節(jié)InvalidValidDirtyReserved(4)

14、Read-inv(A remote cache reads a block during a write-miss,updates it and invalidates all other copies).Read-inv(4)下一節(jié)InvalidValidDirtyReserved(4)Read-inv(A remote cache reads a block during a write-miss,updates it and invalidates all other copies).(5)Write-inv(A remote cache updates its local copy d

15、uring a write-hits and invalidates all other copies).Read-inv(4)/Write-inv(5)下一節(jié) (1)P-Write(miss: take a dirty copy from a remote cache which then updates memory, or from memory; send Read-inv to invalidate all copies; update local copy into a dirty one). (2)P-Read(miss: if no dirty copy exists, mem

16、ory supplies a valid copy, otherwise, the cache inhibits memory and supplies a copy and updates memory. Both copies become valid). (3)Read-blk(read from remote processors, the local copy become valid). (4)Read-inv(A remote cache reads a block during a write-miss, updates it and invalidates all other

17、 copies). (5)Write-inv(A remote cache updates its local copy during a write-hits and invalidates all other copies).6. Write-Once一致性協(xié)議狀態(tài)轉(zhuǎn)移表必是局部進行，不影響有效狀態(tài)第一次寫命中，用寫通過法。同時修改本地和主存副本并廣播Write-inv使所有副本失效commandcurrentstatenextstatestatusP-Read有效有效Read-hitP-Write有效保留Write-hitaction第二次寫命中，用寫回法。但不修改主存的副本P-Writ

18、e保留重寫Write-hit寫缺失時，則從主存或遠程Cache送來副本。并廣播Read-inv使所有其它副本無效。commandcurrentstatenextstatestatusP-Write無效保留 Write-missaction（續(xù)表）第二次以后更多的寫命中，用寫回法。無狀態(tài)改變。P-Write重寫重寫Write-hitcommandcurrentstatenextstatestatusaction（續(xù)表）讀缺失時,如遠程Cache中沒有重寫副本，則主存中一定有一份正確的副本，供給發(fā)請求的Cache。如遠程的Cache有重寫的副本，則它禁止主存操作，并將副本發(fā)給請求的Cache，兩種

19、情況均使發(fā)請求的Cache得到的副本為有效。P-Read無效有效 Read-miss遠程Cache讀此副本，讀后兩份副本均有效Read-blk保留或重寫有效commandcurrentstatenextstatestatusaction（續(xù)表）寫缺失時，遠程Cache讀一個塊，并修改它，并使所有其它Cache的副本無效。Read-inv除無效外的其它狀態(tài)無效寫命中時，一遠程Cache修改其本地副本，并使數(shù)據(jù)塊的其它副本無效Write-inv有效無效commandcurrentstatenextstatestatusaction（續(xù)表）如果副本處于重寫狀態(tài)，必須通過塊替換寫回主存，否則不產(chǎn)生替換

20、操作Write-inv有效無效替代7. 一個具體的例子如下圖的系統(tǒng)：MemoryC1P1C2P2C3P3讀的情況： （1）如果C1為Valid，讀C1，則Read hit，狀態(tài)不變。 （2）如果C1為Reserved，讀C1，則Read hit，狀態(tài)不變。 （3）如果C1為Dirty，讀C1，則Read hit，狀態(tài)不變。 （4）如果C1為Invalid，C2和C3沒有東西，則讀C1時Read miss，這時只有memory中有正確的副本，把它取到C1，C1改為Valid（P-Read負責實現(xiàn)狀態(tài)的改變）。 （5）如果C1為Invalid，C2為Dirty，則讀C1時Read miss，這時只

21、有C2中的內(nèi)容是正確的，要發(fā)Read-blk信號把副本從C2讀到C1，同時修改memory，把C1，C2都改為Valid（程序狀態(tài)轉(zhuǎn)移圖中P-Read(2)使C1Valid，Read-blk(3)使C2 Valid）。 （6）如果C1為Invalid，C2為Reserved，則讀C1時Read miss，這時發(fā)Read-blk信號把 C2C1，C1，C2都改為Valid，其中Read-blk(3)負責把C2由ReservedValid，P-Read(2)負責把C1由InvalidValid。寫的情況： （1）如果C1為Valid，寫C1，則Write hit，發(fā)P-write修改C1內(nèi)容，修改

22、memory，發(fā)Write-inv(4)給所有Cache，C1變成Reserved狀態(tài)。 （2）如果C1為Reserved，寫C1，則Write hit，發(fā)P-write修改C1內(nèi)容，不修改memory，C1狀態(tài)變?yōu)镈irty。 （3）如果C1為Dirty，寫C1，則Write hit，發(fā)P-write修改C1內(nèi)容，不修改memory，狀態(tài)仍為Dirty。 （4）如果C1為Invalid，C2，C3沒有東西，這時memory中有這個地址的數(shù)據(jù)副本，從memory中讀取該副本到C1，再把要寫的內(nèi)容寫入C1，這時C1和memory內(nèi)容不一致，把C1的狀態(tài)變?yōu)镈irty。 （5）如果C1為Inval

23、id，C2為Dirty，這時memory中內(nèi)容和C2中的內(nèi)容不一致，把 C2C1，再把要寫的內(nèi)容寫入C1，C1Dirty，發(fā)Read-inv使其它所有Cache的副本變成無效狀態(tài)。 （6）如果C1為Invalid，C2為Reserved，這時memory中的內(nèi)容和C2內(nèi)容一致，把C2C1，再把要寫的內(nèi)容寫入C1，這時C1與memory內(nèi)容不一致，使C1Dirty，發(fā)Read-inv使其它所有Cache的副本變成無效狀態(tài)。C1的三種狀態(tài)的圖示:xxP1xP2xP3C1C2C3memoryvalidC1中的副本和memory中一致xxP1IP2IP3C1C2C3memoryReservedInva

24、lidC1中的副本和memory中一致，都正確xxP1IP2IP3C1C2C3memoryDirtyInvalidC1中的副本和memory不一致，只有C1中的副本正確8.其它的一些問題 CPU要向Cache寫數(shù)據(jù)，如果write miss，表示該數(shù)據(jù)塊不在Cache中或者該數(shù)據(jù)快處于無效狀態(tài)，那么需要把正確的數(shù)據(jù)從memory或其它的Cache中取過來，然后再寫操作。 為什么不能直接寫？ （1）可能該數(shù)據(jù)塊根本不在Cache中，所以需要從其它地方調(diào)入。 （2）已在Cache中，但數(shù)據(jù)不正確，這時如果直接寫入數(shù)據(jù)，整個數(shù)據(jù)塊可能還是不正確的。例如，數(shù)據(jù)不正確的原因是100號單元數(shù)據(jù)已修改，如果

25、要寫入一個數(shù)據(jù)到101單元，這時不能直接寫，否則100號單元還是錯的。 Cache Coherence問題概要：多處理機系統(tǒng)共享存儲器Cache塊的狀態(tài)訪問的數(shù)據(jù)是最新的，不是“過時”的內(nèi)容6.3 基于目錄的Cache一致性協(xié)議6.3.1 目錄的一般性問題 1.Cache一致性協(xié)議的開銷分析 （1）采用寫無效協(xié)議無效后，當其它處理機再讀該副本時，出現(xiàn)Read miss，要有開銷 （2）采用寫更新協(xié)議需要更新所有Cache和memory中的副本，所以開銷大，有些處理機對更新后的數(shù)據(jù)可能不會使用。 2. 基于目錄的一致性協(xié)議的基本思想 當處理機臺數(shù)增加時，一般不用總線結(jié)構(gòu)，而采用多級互連網(wǎng)絡(luò)。多級

26、互連網(wǎng)絡(luò)實現(xiàn)廣播功能代價很大。 為什么需要廣播功能？把一致性命令，如Write-inv，Read-inv等命令要發(fā)送給所有的Cache。 能不能只發(fā)送給存放該副本的Cache?基于目錄的協(xié)議的基本思想 3. 目錄的結(jié)構(gòu) （1）目錄里放什么有關(guān)Cache副本駐留在哪里的信息：所有共享數(shù)據(jù)塊的所有Cache副本的地址表。 （2）每個目錄項（每個數(shù)據(jù)結(jié)構(gòu)）包含若干個指向這個塊（每個數(shù)據(jù)塊有個目錄項）的Cache副本地址的指針以及一個重寫位（用來說明是否有一個Cache允許把有關(guān)的數(shù)據(jù)寫入）。 （3）基于目錄的Cache一致性協(xié)議是依靠一個目錄來記錄系統(tǒng)之中哪些處理機的Cache中有指定存儲塊的副本。

27、當一臺處理機希望寫某個共享塊時，通過目錄向有該塊的副本的那些處理機“點對點”的發(fā)無效信號，使所有其它的副本無效。 4. 目錄的方式（1）集中目錄方式（中心目錄）1976年Tang提出。用一個中心目錄存放所有Cache目錄的副本，它能提供為保證一致性所需要的所有信息。 缺點：容量非常大，必須采用聯(lián)想方法來檢查，沖突多，檢索時間長。（2）分布式目錄1978年Censier和Feautrier提出。每個存儲模塊維護各自的目錄，目錄中記錄著每個存儲塊的當前信息。當前信息指明哪些Cache有該存儲塊的副本。如下面的圖：D1M1D2M2DmMmD1M1D2M2DmMm互連網(wǎng)絡(luò) 如果C2讀miss，這時C1

28、中有Dirty的副本，則把它寫回memory，內(nèi)存再給C2一個副本，變成Valid。 如果C1寫命中，它告訴memory控制器，控制器發(fā)無效命令給在D1的當前向量中有記錄的所有Cache。 5. 三種目錄 全映射（full map）目錄：存放與全局存儲器中每個塊有關(guān)的數(shù)據(jù)。系統(tǒng)中的每個Cache可以同時存儲任何數(shù)據(jù)塊的副本，即每個目錄項包含N個指針（N是處理機數(shù)目）。 有限（limited）目錄：每個目錄項有固定數(shù)目的指針（小于N）。 鏈式（chained）目錄：將目錄分布到各個Cache（其余同全映射目錄）。6.3.2 全映射目錄 1.目錄項結(jié)構(gòu) 目錄項中有N個處理機位（對應N臺處理機）和一

29、個重寫位，如下圖所示：目錄項：重寫位（1位）處理機位（N位） 處理機位表示相應處理機的Cache block的狀態(tài)（存在或不存在）。 有一個也只有一個處理機位為“1”，那么該處理機可以對該塊進行寫操作。 Cache的每個塊有兩個狀態(tài)位：有效位有效塊是否允許寫有效1位 Cache的狀態(tài)位應該和目錄項的狀態(tài)一致。1位允許寫目錄項：重寫位（1位）處理機位（N位）Cache狀態(tài)位：2.目錄的三種情況我們來看三臺處理機（三個Cache）的例子。（1）C1，C2，C3都沒有單元X的副本Shared Memoryx:c000dataC1P1C2P2C3P3（2）C1，C2，C3同時請求X單元的副本，這時目錄

30、項中的三個指針（處理機位）被置1，表示這些Cache中已有數(shù)據(jù)副本。 目錄項的重寫位被置為未寫（c）狀態(tài)，表示無一處理機允許寫入該數(shù)據(jù)塊。Shared Memoryx:c111datax:P1x:P2x:P3C1C2C3（3）C3請求對該塊的寫允許權(quán)時出現(xiàn)第（3）種情形，重寫被置成D狀態(tài)，且有一個指針指向C3的數(shù)據(jù)塊。Shared Memoryx:D001dataP1P2 x:P3C1C2C3data3.第二種情況第三種情況的過程 P3向C3發(fā)出寫請求時：（1）C3檢測出包含單元X的塊是有效的，但Cache中的塊允許位狀態(tài)表示不允許處理機對該塊進行寫操作。（2）C3向包含單元X的存儲器模塊發(fā)出

31、寫請求，并暫停P3工作。（3）該存儲器模塊發(fā)出一個無效請求給C1和C2（根據(jù)目錄項的內(nèi)容發(fā)幾個無效信號）（4）C1和C2收到無效請求后，把相應位置0，表示含單元X的塊已無效，并發(fā)送一個回答信號給請求的存儲器模塊。（5）存儲器模塊收到回答信號后，將重寫位置 D，清除指向C1、C2的指針，發(fā)出允許信號給C3。（6）C3收到寫允許信號后，修改Cache的狀態(tài)并激活處理機P3。4. 目錄所占空間 假設(shè)存儲器大小和處理機臺數(shù)N成正比，即臺數(shù)增加時，存儲器的模塊數(shù)也增加，所以數(shù)據(jù)塊的個數(shù)也和N成正比。 另外目錄項的大小也和處理機臺數(shù)N成正比，所以目錄的總所占空間和N2成正比。 即：目錄項數(shù)*項大小 = O

32、 ( N2) 太大不便于擴展。6.3.3 有限目錄 解決目錄過大的問題。任意一個數(shù)據(jù)塊在Cache中同時存在的副本數(shù)量有一定限制，那么目錄大小的增加不會超過一個常數(shù)。符號表示法： DiriX i:指針的數(shù)量。X是NB，表示沒有廣播功能的方案。 DirNNB表示沒有廣播功能的全映射方式 DiriNB（i N）：使用i個指針的沒有廣播功能的有限目錄協(xié)議方式。 除了多于i個Cache請求讀一個特定的數(shù)據(jù)塊的情況外，有限目錄協(xié)議與全映射協(xié)議類似。 有限目錄中指針不是每臺處理機一位，而是針對處理機的二進制標識符進行編碼，所以指針占log2N位存儲器。 在全映射方式中，每個處理機對應一個指針，所以N臺處理

33、機一共用了N位，而有限目錄中只用log2N位，設(shè)N =16，則log216 = 4。 如果允許兩個指針，則需要8位。 所以目錄的存儲容量為O（Nlog2N），比全映射容易擴充。 如果多處理機系統(tǒng)中的處理機具有局部性，即在任何給定的時間間隔內(nèi)，只有一小部分處理機訪問某個給定的存儲器字，那么有限目錄足以應付這個小的工作處理機組了。6.3.4 鏈式目錄 用目錄指針鏈來跟蹤共享數(shù)據(jù)副本。 兩種方法，單鏈法與雙鏈法。 數(shù)據(jù)塊共享副本的數(shù)目并無限制。 所占的空間及可擴展性同有限目錄。 它的工作原理如下過程所示。（1）P1要讀單元X，則memory發(fā)送一份副本給C1，同時送給C1一個鏈結(jié)束指針（CT：Cha

34、in Termination），存儲器也保存指向C1的指針。Shared Memoryx:cdataP1P2P3C1C2C3x:CTdata（2）當P2要讀單元X時，存儲器送一份副本給C2，同時送給C2一個指向C1的指針，存儲器保存指向C2的指針。Shared Memoryx:cdataP1P2P3C1C2C3x:CTdatax:data（3）重復以上步驟，所有Cache都得到單元X的副本。（4）如果P3要對單元X進行寫操作，它必須沿著鏈發(fā)送一個數(shù)據(jù)無效信息。為了保證順序一致性，在有鏈結(jié)束指針的處理機回答無效信號之前，存儲器模塊不給P3寫允許權(quán)。 無效命令從一個Cache到一個Cache順序進

35、行，不象snoopy協(xié)議那樣同時發(fā)送給所有Cache。（5）替換。假設(shè)C1到CN都有單元X的副本，還假設(shè)單元X和單元Y都映射到同一個高速緩存塊（直接映射法）。如果處理機Pi要讀單元Y，它首先必須把X所在的塊從Cache中去掉，這可以采用兩種方法： 1）沿著鏈發(fā)一個消息使Ci+1的指針指向Ci-1，這樣使Ci從鏈中去掉（這時Ci中存放Y了）。 2）使Ci+1到CN中的單元X無效（這時Ci中存放Y了）。目錄占用的存儲容量：指針的尺寸以處理機數(shù)目的對數(shù)關(guān)系增長（這和有限目錄相同）log2N，每個Cache塊的指針數(shù)目與處理機個數(shù)無關(guān)。解決Cache一致性的其它辦法：（1）不允許有私有 Cache：S

36、hared Cache方案（2）可寫的共享數(shù)據(jù)不存放在Cache中6.4 三種Cache一致性策略6.4.1 采用Write-Through策略的Cache 數(shù)據(jù)塊的兩種狀態(tài)：有效和無效（指本地處理機相應數(shù)據(jù)塊的狀態(tài)，并非整個Cache的狀態(tài)。) 一致性的四種操作： Rr和Wr：其它處理機對該數(shù)據(jù)塊（指在其它處理機Cache中的數(shù)據(jù)塊）的讀寫 Rl和Wl：是本地處理機對該數(shù)據(jù)塊的讀寫狀態(tài)轉(zhuǎn)移圖如下：有效無效RrWlRlRl, WlWrRr, WrCache的數(shù)據(jù)塊為無效時： 其它處理機的任何操作都不會影響本地Cache的這種無效狀態(tài)； 只有在本地處理機讀或者寫了數(shù)據(jù)塊中的某個數(shù)據(jù)，即對Cach

37、e執(zhí)行了Read或Write命令時，該數(shù)據(jù)塊的狀態(tài)才會成為“有效”。 Cache的數(shù)據(jù)塊為“有效”時： 本地處理機的讀、寫操作，不會影響該狀態(tài)； 其它處理機對存有相同內(nèi)容的數(shù)據(jù)塊讀，不會影響該狀態(tài)； 其它處理機對存有相同內(nèi)容的數(shù)據(jù)塊執(zhí)行了寫操作，該數(shù)據(jù)塊狀態(tài)變成無效。6.4.2 采用Write-Back策略的Cache 1.數(shù)據(jù)塊的三種狀態(tài) RO (只讀）狀態(tài)：表示整個系統(tǒng)中不止一個副本正確（例如一個在Cache中，一個在memory中）。 讀-寫狀態(tài)：表示整個系統(tǒng)中，只有這個副本是正確的，其它都“過時”（即無效），這說明這個 Cache的數(shù)據(jù)塊至少被寫過一次，但memory中的內(nèi)容還沒有被修

38、改。 無效狀態(tài)：“過時”數(shù)據(jù)。2. 一致性的四種操作： Rr和Wr：其它處理機對該數(shù)據(jù)塊（指在其它處理機Cache中的數(shù)據(jù)塊）的讀寫 Rl和Wl：是本地處理機對該數(shù)據(jù)塊的讀寫狀態(tài)轉(zhuǎn)移圖如下：3. 處于RO狀態(tài) 本地讀，遠程讀不會改變狀態(tài) 本地寫，使ROR-W（這時只有一個數(shù)據(jù)塊正確） 遠程寫，使RO無效無效ROWlWrRl, RrW-R4. 處于讀-寫狀態(tài)無效RORrWrRl,WlW-R 本地讀、寫不會改變狀態(tài) 遠程讀：這時只有這個 Cache的數(shù)據(jù)塊是正確的，所以要有“寫回”動作（即把內(nèi)容寫回Memory），另外還需要把正確的數(shù)據(jù)傳遞給遠程讀的處理機相應的Cache。兩個Cache的狀態(tài)RO

39、 遠程寫：把本地處理機的數(shù)據(jù)塊傳遞給遠程處理機，遠程處理機對數(shù)據(jù)塊進行寫操作，遠程處理機對應的Cache狀態(tài)變?yōu)镽O，而本地的Cache變?yōu)闊o效狀態(tài)。5. 處于無效狀態(tài)無效ROWlRr,WrW-RRl 本地讀：無效RO 本地寫：無效WR（同時使其它擁有相同內(nèi)容的數(shù)據(jù)塊的Cache中相應的數(shù)據(jù)塊的狀態(tài)變成無效） 遠程寫、遠程讀：不影響狀態(tài)的改變*6.4.3 采用Write-Once策略的Cache 1. Write-Through和Write-Back的缺點 Write-Through策略的弱點是每次都要修改memory，所以總線流量增大； Write-Back策略的弱點是Cache寫了一次后，

40、Memory中的內(nèi)容不一致。2. Write-Once的基本思想 把Write-Through和Write-Back兩者的優(yōu)點結(jié)合在一起：減少總線流量。 Cache的第一次寫采用Write-Through策略（有一個以上的副本正確）； Cache而后的寫采用Write-Back策略（只有一份副本正確）。 為了區(qū)分是否是第一次寫，把“讀-寫”狀態(tài)分成兩個狀態(tài)：Reserved和Drity。3. 數(shù)據(jù)塊的四種狀態(tài) 有效狀態(tài)（Valid）：相當于Write-Back里的“只讀”，從共享存儲器中讀入的并與存儲器副本一致的Cache數(shù)據(jù)塊。 無效狀態(tài)（Invalid）：在Cache中找不到或Cache中

41、的數(shù)據(jù)塊內(nèi)容與共享存儲器中的內(nèi)容不一致的Cache數(shù)據(jù)塊。 保留狀態(tài)（Reserved）：數(shù)據(jù)從共享存儲器讀入Cache只被寫過一次。Cache中的副本與共享存儲器中的副本是一致的，并且它是正確的副本。 重寫狀態(tài)（Dirty）：Cache中的數(shù)據(jù)塊不止一次被寫過，此時共享存儲器中的數(shù)據(jù)塊也不是正確的數(shù)據(jù)塊，唯一正確的數(shù)據(jù)塊在Cache中。4. 如果處于“有效”狀態(tài)有效保留WrRl, Rr無效Wl重寫（1）本地讀Rl，不影響狀態(tài)。（2）本地寫Wl（第一次寫），采用Write-Through策略，這時要發(fā)無效命令給其它Cache中相應的副本，并修改memory。有效保留（3）遠程寫Wr（不管是第幾

42、次寫），遠程CPU會發(fā)無效命令：有效無效（4）遠程讀Rr：不影響狀態(tài)。5. 如果處于“保留”狀態(tài)有效保留WrRl無效Rr重寫Wl（1）本地讀Rl，不影響狀態(tài)。（2）遠程讀Rr：這時Cache中只有處于保留狀態(tài)的數(shù)據(jù)塊是正確的，所以把該數(shù)據(jù)塊送到遠程CPU的Cache中（遠程Cache中該數(shù)據(jù)塊變?yōu)橛行В?，本?shù)據(jù)塊狀態(tài)已變?yōu)橛行А?（3）本地寫Wl：第二次及以后的寫，采取Write-Back策略，不修改Memory，狀態(tài)由Reserved變?yōu)镈irty（這時只有一個副本有效），發(fā)無效命令給其它Cache的對應的副本，使Memory中的副本也無效。（4）遠程寫Wr：遠程CPU會發(fā)無效命令，使狀態(tài)由

43、Reserved變?yōu)镮nvalid。6. 如果處于“重寫”狀態(tài)有效保留WrRr無效Rl，Wl重寫（1）本地讀Rl：不影響狀態(tài)。（2）本地寫Wl：不影響狀態(tài)。（3）遠程讀Rr：這時只有這個Cache的數(shù)據(jù)塊是正確的，所以把該數(shù)據(jù)塊發(fā)送給遠程的Cache，遠程Cache的數(shù)據(jù)塊和本Cache中的數(shù)據(jù)塊都變得有效。（4）遠程寫Wr：遠程CPU寫后，發(fā)無效命令使狀態(tài)由重寫無效。7. 如果處于“無效”狀態(tài)有效保留RlWr, Rr無效Wl重寫（1）本地讀Rl：這時產(chǎn)生Read-Miss，設(shè)法找到有效的數(shù)據(jù)塊調(diào)入Cache： 如果系統(tǒng)存在處于有效，保留或重寫狀態(tài)的相應數(shù)據(jù)塊，則將其調(diào)入本地Cache 如果系

44、統(tǒng)中不存在處于有效、保留或重寫狀態(tài)的相應數(shù)據(jù)塊，則說明共享存儲器中的數(shù)據(jù)塊是正確的，直接從共享存儲器讀入即可。 讀入后相應數(shù)據(jù)塊進入“有效”狀態(tài)。（2）遠程讀Rr：狀態(tài)不變（3）本地寫Wl：一定是Write-Miss，系統(tǒng)首先把正確的內(nèi)容調(diào)入Cache，然后寫Cache，因為是第一次寫，所以Write-Through策略，同時寫memory，將本地Cache狀態(tài)置為“保留”，同時將系統(tǒng)中其它相應的數(shù)據(jù)塊置為“無效”（4）遠程寫Wr：狀態(tài)不變第七章 Memory Consistency7.1 問題的提出7.1.1 存儲器一致性問題7.1.2 存儲器訪問的原子性問題7.1.3 存儲器訪問操作的三個

45、階段7.1.4 一個例子*7.1.5 多處理機存儲器的行為7.2 四種存儲器一致性模型 7.2.1 順序一致性模型7.2.2 弱一致性模型7.2.3 處理機一致性7.2.4 釋放一致性7.2.5 四種模型的其它說明7.1 問題的提出7.1.1 存儲器一致性問題1.定義存儲器一致性是指一個系統(tǒng)正確執(zhí)行存儲器操作的能力。各處理機看到存儲器的值是一致的。2.順序一致性程序次序執(zhí)行次序存儲器訪問次序順序一致性：存儲器訪問次序同程序執(zhí)行次序一致。順序不一致性：存儲器訪問次序同程序執(zhí)行次序不一致。3. 實際系統(tǒng)中的問題 在單機系統(tǒng)中，一個取數(shù)指令返回的總是對同一存儲單元最近一次寫指令所寫的值。 但實際系統(tǒng)

46、中，采用Cache、寫緩沖和pipeline等技術(shù)在不破壞數(shù)據(jù)相關(guān)性的同時，允許存儲器操作不按程序指定的順序發(fā)出。 在多處理機環(huán)境下，一個存儲單元可以被多個處理機訪問，“最近一次寫操作”、“下一次寫操作”、“之后的讀操作”這些概念的含義是不清楚的，可能出現(xiàn)多個處理機發(fā)出的多個存儲請求不按要求的順序執(zhí)行，這就要求重新定義存儲器一致性模型：當n個處理機同時發(fā)出存儲訪問請求時，什么樣的訪問順序是合法的？4. 多機系統(tǒng)中的難點 在多機系統(tǒng)中，只檢測多處理機的內(nèi)部相關(guān)性是不夠的，順序一致性比較難維持，這是因為： （1）多個指令流的執(zhí)行次序并不一定一樣，如無同步，大量指令交叉執(zhí)行可能發(fā)生。 （2）如想改善

47、性能，每臺處理機中指令執(zhí)行的次序與程序次序不同，則會發(fā)生更多的指令交叉執(zhí)行。 （3）由于互連網(wǎng)絡(luò)對不同的存儲器訪問而引起不一樣且無法預測的延遲（如沖突），可能存儲器訪問命令按程序次序發(fā)生，但到達存儲器的次序不一樣了。 （4）存儲器訪問對Cache-based的系統(tǒng)就不是原子訪問，如并非所有的Cache副本同時修改或失效，則可按程序發(fā)出訪問命令并到達Memory，但完成不一定按程序次序，不同處理機觀察到的將是不同的交叉。此時，一個程序可能會產(chǎn)生多種執(zhí)行情況。7.1.2 存儲器訪問的原子性問題 如果所有處理機同時看到一份數(shù)據(jù)拷貝，則系統(tǒng)中的存儲器訪問是原子性的。 如果存操作所寫的值對所有處理機同時

48、可讀，則此寫操作是原子操作。 如果存儲器更新時為所有處理機所知道，那么這就是原子共享存儲器訪問。 所以原子存儲器成為順序一致的充分必要條件是要所有存儲器訪問的執(zhí)行都必須保持所有各個程序的次序。 因此：在Cache-based系統(tǒng)中，不存在原子性。 例：如下的程序。P1a: A=1b: Print B CP2c: B=1d: Print A CP3e: C=1f: Print A B 假設(shè)指令執(zhí)行的順序為a，c，e，b，d，f，開始時，A=B=C=0，在非原子系統(tǒng)中： P1 executes b, P1s copy of B has not been updated, P1s copy of C

49、 has been updated. P2 executes d, P2s copy of C has not been updated, P2s copy of A has been updated. P3 executes f, P3s copy of A has not been updated, P3s copy of B has been updated. 這里指令按程序次序執(zhí)行，但其他處理機并不按程序次序觀察到結(jié)果，執(zhí)行結(jié)果為0110017.1.3 存儲器存取操作的三個階段 一個存儲器存取操作可以分為三個不同的階段：形成、發(fā)生和完成。 形成：當一個處理機提出存儲器訪問請求，就說該存

50、儲器請求“形成”了，這個請求的完成不由該處理機控制。 發(fā)生：當一個已形成的請求離開了處理機（包括CPU及本地緩沖），正在向存儲器系統(tǒng)傳送時，就說這個已形成的請求“發(fā)生”了。 完成：對一個讀操作，當對同一地址發(fā)出的寫請求不會影響該讀操作的返回值，就說該讀操作在此刻“完成”了；對于寫操作，在該寫操作之后，在下一個對同一地址的寫操作之前，所發(fā)出的對同一地址的讀操作都返回該寫操作所寫的值，就說該寫操作“完成”了。1. 如何確定write的結(jié)束點 （1）對本臺處理機（進程）而言，則是在處理機和Cache之間的寫緩沖器中寫入新值。 With respect to a process - writes th

51、e new value to a write buffer between processor and Cache. （2）對存儲器而言，則是值進入Cache。 With respect to memory - The value enters Cache. （3）對其它處理機而言，則是使其它Cache副本更新或失效。 With respect to other processor(s) - updates or invalidates other cached copies. （4）全局結(jié)束則是所有處理機對它們Cache的修改。換言之，當寫修改值傳給所有處理機時，則write全局完成。 Al

52、l processor finish updating the copies of their cache lines. In other words, a write is globally performanced when its modification has been propagated to all processors.2. 如何確定read的結(jié)束點 （1）對除了發(fā)出read之外的所有處理機而言，發(fā)read的處理機可訪問并Cache命中，其它處理機不能改變回送值。 With respect to all processors other than the issueing p

53、rocessor the issueing processor is granted access and has a Cache hit, so no other processor can change the value to be returned.（2）對指定處理機在Cache缺失時，供給Cache副本的指定處理機不能再改變回送值 With respect to a designated processor during Cache miss the designated processor to supply the cache copy is no longer able to

54、change the value to be returned. （3）對所有處理機，則無處理機能改變回送值 With respect to all processor No processor is able to change the value to be returned. （4）全局結(jié)束，沒有一臺處理機發(fā)送對同一地址讀命令，而得到此單元變量的前一個值。換言之，在讀的值限定以及寫此值的寫操作全局完成時，read才全局完成。 Globally complete No processor that has a read to the same address will be able to

55、 see an earlier value of the variable. In other words, a read is globally performed when the value it returns is bound and the write that wrote this value is globally performed.3. 區(qū)分“對某個處理機完成”與“全局完成” 對于非原子的存取操作，需要區(qū)分“對某個處理機來講完成”和“全局完成”（1）處理機i的寫操作對于處理機k來講完成：當處理機k隨后發(fā)出的對同一地址的讀操作返回該寫操作所寫的值。（2）處理機i的讀操作對于處

56、理機k來講完成：當處理機k隨后發(fā)出的對同一地址的寫操作不會影響該讀操作返回的值。（3）一個寫操作是全局完成的：如果它對于所有處理機來講完成（即所有處理機隨后發(fā)出的對同一地址的讀操作返回該寫操作所寫的值）。（4）一個讀操作是全局完成的：如果它對于所有處理機來講完成（即所有處理機對同一地址的寫操作不會影響該讀操作返回的值），并且決定該讀操作返回值的寫操作已經(jīng)全局完成。7.1.4 例:多處理機中的存儲器系統(tǒng)訪問次序P1a: A=1b: Print B CP2c: B=1d: Print A CP3e: C=1f: Print A BShared MemoryA，B，C是存儲器中的共享變量（初始時 A

57、=B=C=0）開關(guān)在原子系統(tǒng)中： Print語句在同一周期內(nèi)不可分割地輸出二個變量。 如果把三臺處理機的輸出按P1，P2，P3的次序串連起來，則輸出就形成一個二進制向量的6元組。 有26=64種可能的輸出組合。 (1)如果所有處理機按各自的程序次序執(zhí)行指令： 會出現(xiàn)的執(zhí)行交叉為：a,b,c,d,e,f ，產(chǎn)生的輸出向量為001011。 會出現(xiàn)的執(zhí)行交叉為：a,c,e,b,d,f ，產(chǎn)生的輸出向量為111111。 (2)如果允許處理機不按程序次序執(zhí)行指令（假設(shè)重新排序后指令之間不存在數(shù)據(jù)相關(guān)） 如執(zhí)行交叉為：b,d,f,e,a,c ，產(chǎn)生的輸出向量為000000。 這個例子一共有6！=720種交

58、叉執(zhí)行可能，其中90種可保持各自的程序次序。 輸出011001不可能，如下圖：P1輸出01b before ce before bP2輸出01a before dd before eP3輸出01f before ac before fe before ca before ec before aa before c矛盾*7.1.5 多處理機存儲器的行為（1）所有處理機都保持程序次序，并且有相同的執(zhí)行次序。（2）所有處理機都可以不按程序次序執(zhí)行，但有相同的執(zhí)行次序。 （3）不同處理機都可以不按程序次序執(zhí)行，并且有不同的執(zhí)行次序。 原子存儲器成為順序一致性的充分必要條件是所有存儲器訪問的執(zhí)行都必須保

59、持所有多個程序的次序。 在非原子存儲器訪問的多處理機中，遵守各自的程序次序并不是順序一致性的充分條件。7.2 四種一致性模型7.2.1 順序一致性模型1.定義 順序一致性存儲模型（Sequential Consistency，SC）中，所有處理機的取、存和交換操作（原子取存）都可以看作是按一種單一的全局存儲次序在順序的執(zhí)行，這種存儲次序與處理機各自的程序次序是相符合的，如圖所示：單端口存儲器P1P2P3Pn存儲器的訪問次序與程序的執(zhí)行次序一致 Lamport定義（1979）：如果任意一次執(zhí)行的結(jié)果都象所有處理機的（memory）操作是以某種順序執(zhí)行所得到的一樣，而且就在這個序列中，多臺處理機的

60、（memory）操作都按照它的程序所指定的次序出現(xiàn)，那么這樣的多處理機是順序一致性系統(tǒng)。A multiprocessor system is sequentially consistent if the result of any execution is the same as if the operation of all the processors were executed in some sequential order, and the operations of each individual processor appear in this sequence in the o