制作人員許婷朱曉華白婧.ppt

制作人員：許婷 朱曉華 白婧,處理機的Cache一致性,Cache作為提高系統(tǒng)性能的一種常用手段在計算機系統(tǒng)中得到普遍的使用。但是，在多處理機中，不僅Cache同共享存儲器中同一數(shù)據(jù)拷貝可能不一致，而且由于多個處理機異步地相互獨立操作，也使多個Cache中同一份存儲塊的拷貝可能不一致，這就是Cache一致性問題。,問題提出,一、Cache一致性問題的原因,共享可寫的數(shù)據(jù) 進程遷移 I/O傳輸,要解決多處理機的Cache一致性問題，首先要研究一致性問題的由來。出現(xiàn)不一致的原因有3個：,1.共享可寫數(shù)據(jù)引起的不一致性,以擁有兩個處理機的系統(tǒng)為例，處理機帶有各自的私有Cache，并共享一個主存儲器。,P1,X,P2,X,X,P1,X,P2,X,X,P1和P2的本地高速緩存存儲器C1和C2中分別有共享主存的某個數(shù)據(jù)X的拷貝。,P1改寫C1中的X，使之變?yōu)閄。,X,若P1采用“寫通過”策略，即處理機改寫Cache中的數(shù)據(jù)時同時修改內(nèi)存中相應(yīng)的數(shù)據(jù)，那么，內(nèi)存中的X也同時變?yōu)閄，但是，處理機P2的本地高速緩沖存儲器C2中的X仍然是X。,X,當P2要讀X時，它是從C2中去讀取，這就導(dǎo)致了P2從C2中讀取的X同內(nèi)存中的X不一致。,P1,X,P2,X,X,X,若P1采用“寫回”策略，即處理改寫Cache中的數(shù)據(jù)時并不同時修改內(nèi)存中相應(yīng)的數(shù)據(jù)，而是在包含該數(shù)據(jù)的數(shù)據(jù)塊調(diào)出Cache時才寫回內(nèi)存，那么，內(nèi)存中的X還是X,導(dǎo)致C1中的X同內(nèi)存中的X的不一致,2.進程遷移引起的不一致性,情況一：,P1,X,P2,X,若P1的進程對X進行了修改，使之變?yōu)閄,X,采用“寫回”策略，暫時沒有對內(nèi)存中的X進行修改。,由于某種原因，該進程遷移到了P2上運行,P2上的該進程運行時將從內(nèi)存中讀取X并將X調(diào)入C2,那么，這個遷移了的進程此時讀取的是X，而不是它先前修改過的X。,X,P1的C1中有共享數(shù)據(jù)X的拷貝，而P2的C2中沒有該共享數(shù)據(jù),情況二：,以上兩種情況都是由于進程遷移引起的數(shù)據(jù)不一致。,P1,X,P2,X,X,P1的C1和P2的C2中都有共享數(shù)據(jù)X的拷貝,X,P2的進程修改了C2中的X，改變?yōu)閄,并采用“寫通過”策略，使內(nèi)存中的X也修改為X,X,由于某種原因該進程遷移到P1上,此時P1的C1中仍然是X，而不是它先修改過的X。,3. I/O傳輸引起的不一致性,若P1的C1和P2的C2中都有共享數(shù)據(jù)X的拷貝,P1,P2,X,X,X,I/O,存儲器,X,I/O處理機將一個新的數(shù)據(jù)X寫入內(nèi)存代替X,X,內(nèi)存和Cache之間的數(shù)據(jù)不一致性。,P1,X,P2,X,X,I/O,存儲器,處理機P1運行過程中修改了X的值，使之變?yōu)閄,X,P1采用“寫回”策略，那么，C1中的X同內(nèi)存中的X是不一致的,若I/O處理機要求輸出X，那么，內(nèi)存就會將內(nèi)存中的X的值傳送給I/O處理機,X,傳送給I/O處理機的將不是修改后的X,若C1和C2中都有X的拷貝,I/O傳輸引起數(shù)據(jù)不一致是因為處理機P1和P2共享I/O處理機，I/O傳輸發(fā)生在I/O處理機和內(nèi)存之間。,把I/O處理機（IOP1和IOP2）分別連接到私有高速緩存C1和C2上，使處理機和I/O處理機共享高速緩存。這樣，只要能保證各Cache之間以及Cache和內(nèi)存之間的數(shù)據(jù)一致性，就能夠保證I/O操作不會引起不一致。,一種解決I/O操作引起不一致的方法：,為了解決多處理機Cache一致性問題，提出了兩類解決Cache一致性問題的協(xié)議機制：監(jiān)聽協(xié)議和基于目錄的協(xié)議。,監(jiān)聽協(xié)議 基于目錄的協(xié)議。,概述 采用寫通過策略的Cache狀態(tài) 采用寫回策略的Cache狀態(tài) 寫一次協(xié)議,二、 監(jiān)聽協(xié)議,概述,監(jiān)聽協(xié)議通過總線監(jiān)聽機制實現(xiàn)高速緩存和共享存儲器之間的數(shù)據(jù)一致性,監(jiān)聽協(xié)議的兩種策略 寫無效(Write-Invalidate)策略 寫無效策略是在本地Cache的數(shù)據(jù)塊修改時,使所有相應(yīng)的遠程數(shù)據(jù)塊拷貝都無效 寫更新(Write-Update)策略 寫更新策略是在本地Cache的數(shù)據(jù)塊修改時,通過總線把改寫的數(shù)據(jù)塊廣播到含有該數(shù)據(jù)塊拷貝的所有其他Cache,例子,Write-Update,監(jiān)聽協(xié)議分別采用寫無效策略和寫更新策略的區(qū)別,P1,P2,X,X,X,更新之前,X,X,P1將它的高速緩存C1中的X修改成X,Write-Invalidate,Cache的寫通過策略同時將內(nèi)存中的X也修改成X,I,寫無效策略則將遠程高速緩存C2中的X變成無效（無效數(shù)據(jù)塊用I表示）,寫更新策略將包含X1的新數(shù)據(jù)塊通過總線廣播到所有的高速緩存，更新其中的X為X1,X,數(shù)據(jù)塊的兩種狀態(tài):,采用寫通過策略的Cache狀態(tài),有效 表示該數(shù)據(jù)塊內(nèi)容正確 無效 表示該數(shù)據(jù)塊內(nèi)容已“過時”或不在本地Cache中,處理機P1對本地高速緩存C1中數(shù)據(jù)塊的讀操作R1和寫操作W1,以及其他處理機Pr對它的高速緩存Cr中同一數(shù)據(jù)塊拷貝的讀操作Rr和寫操作Wr都可能引起高速緩存C1中該數(shù)據(jù)塊的狀態(tài)變化.,狀態(tài)轉(zhuǎn)移圖,對有效塊的所有讀操作R1，Rr之后，數(shù)據(jù)塊仍然是有效塊 P1對C1中的有效塊X寫操作W1，使C1中的X變?yōu)閄1 若P1對本地高速緩存C1中無效數(shù)據(jù)塊讀操作R1和寫操作W1時，則將該數(shù)據(jù)塊由無效轉(zhuǎn)變?yōu)橛行А５?，其他處理機Pr對自己的高速緩存Cr中數(shù)據(jù)塊讀操作Rr和寫操作Wr時，C1中的無效數(shù)據(jù)塊拷貝仍無效,R1,W1,Rr,Rr,Wr,R1 W1,Wr,寫通過策略的Cache狀態(tài)圖,有效,無效,說明：,采用寫回策略的Cache狀態(tài),Cache采用寫回策略 Cache中的數(shù)據(jù)塊被修改時不同時修改內(nèi)存中相應(yīng)的數(shù)據(jù)塊拷貝，當Cache中的數(shù)據(jù)塊被替換時，才將該數(shù)據(jù)塊寫回內(nèi)存。 Cache中數(shù)據(jù)塊的兩種有效狀態(tài)： 讀/寫狀態(tài) 該數(shù)據(jù)塊至少被修改過一次，尚未寫回，內(nèi)存中的相應(yīng)數(shù)據(jù)塊還沒有被修改，在整個系統(tǒng)中只有一個數(shù)據(jù)塊拷貝是正確的 只讀狀態(tài)整個系統(tǒng)中不止一個數(shù)據(jù)塊拷貝是正確的,采用寫回策略的Cache狀態(tài)圖,R1,W1,Rr,R1,W1,Wr,W1,Wr,Wr,Rr,R1,Rr,采用寫回策略的Cache狀態(tài)圖,讀-寫,無效,只讀,P1對C1中的X讀操作R1，C1仍為讀-寫狀態(tài) P1對C1中的X寫操作W1，使X修改為X，但此時X未寫回內(nèi)存, C1的數(shù)據(jù)塊X狀態(tài)仍為讀/寫狀態(tài) 其他處理機Pr對自己 的高速緩存Cr中的數(shù)據(jù)塊拷貝X讀操作Rr , C1數(shù)據(jù)塊狀態(tài)改為只讀狀態(tài) Pr對Cr中的X寫操作Wr，使Cr中的X修改為X1，且未寫回內(nèi)存, C1中的數(shù)據(jù)塊X狀態(tài)改為無效,P1的本地高速緩存C1中的數(shù)據(jù)塊X為讀-寫狀態(tài),C1中的數(shù)據(jù)塊X為只讀狀態(tài),P1對C1中的X讀操作R1，不會改變其狀態(tài)，仍為只讀狀態(tài) Pr對Cr中的X讀操作Rr，不會改變C1中的X的只讀狀態(tài) P1對C1中的X寫操作W1，使X修改為X1，且未寫回內(nèi)存,系統(tǒng)中只有一個正確拷貝，即C1中剛修改的X1 ,C1中的數(shù)據(jù)塊X1狀態(tài)改為讀-寫狀態(tài) Pr對Cr中的X寫操作Wr，使Cr中的X修改為X1，故而C1中的數(shù)據(jù)塊拷貝X過時了，所以，C1中的數(shù)據(jù)塊X狀態(tài)改為無效,C1中的數(shù)據(jù)塊X為無效狀態(tài),P1對C1中的X讀操作R1 , C1中的數(shù)據(jù)塊狀態(tài)改為只讀狀態(tài) P1對C1中的X寫操作W1 ,使C1中的X修改為X1，但此時X1未寫回內(nèi)存,C1中的相應(yīng)的數(shù)據(jù)塊狀態(tài)仍為無效 Pr對Cr中的數(shù)據(jù)塊讀操作Rr和寫操作Wr，C1中的相應(yīng)的數(shù)據(jù)塊狀態(tài)仍為無效,采用寫回策略的監(jiān)聽協(xié)議保持Cache一致性的方法,當內(nèi)存擁有一個數(shù)據(jù)塊時，每個高速緩存只有該數(shù)據(jù)塊的只讀狀態(tài)的拷貝，有拷貝的本地處理機P1和遠程處理機Pr都可以安全地讀這份拷貝,本地的寫操作W1使其拷貝變?yōu)樽x/寫狀態(tài)，遠程的寫操作Wr使本地高速緩存的拷貝變?yōu)闊o效狀態(tài) 如果某個Cache中的某個數(shù)據(jù)塊處于有效狀態(tài)（讀-寫或只讀），則遠程寫操作Wr，使該Cache中的這個數(shù)據(jù)塊變?yōu)闊o效 系統(tǒng)中可能擁有一份處于讀/寫狀態(tài)的數(shù)據(jù)塊拷貝。對于處于讀-寫狀態(tài)的數(shù)據(jù)塊，本地的讀/寫操作（R1和W1）都是安全的，遠程讀操作Rr使其變?yōu)橹蛔x狀態(tài)，遠程寫操作Wr使其變?yōu)闊o效,寫一次協(xié)議,特點是：為了減少總線流量，Cache的第一次寫采取寫通過策略，其后的寫則采取寫回策略 為了區(qū)分是否第一次寫，協(xié)議把讀-寫狀態(tài)分為兩種狀態(tài)：保留和重寫,寫一次協(xié)議的Cache中的數(shù)據(jù)塊的4種狀態(tài) 有效（Valid）：從內(nèi)存讀入的并與內(nèi)存拷貝一致的Cache數(shù)據(jù)塊是有效狀態(tài) 無效（Invalid）：在Cache中找不到或Cache中的數(shù)據(jù)塊內(nèi)容已過時的塊是無效狀態(tài) 保留（Reserved）：若數(shù)據(jù)塊從內(nèi)存讀入Cache后只被寫過一次，且Cache中的拷貝與內(nèi)存中的拷貝一致且正確，則是保留狀態(tài) 重寫（Dirty）：若Cache中的數(shù)據(jù)塊不只一次被寫過，且它是系統(tǒng)中唯一正確的數(shù)據(jù)塊，則是重寫狀態(tài),寫一次協(xié)議的狀態(tài)圖,無效,有效,重寫,保留,Rr,Wr,R1,W1,R1,Wr,W1 Rr,R1,Rr,W1,Rr,Wr,R1,W1,Wr,寫一次協(xié)議的優(yōu)缺點,優(yōu)點是：第一次寫采用寫通過策略，以后的寫操作都采用寫回策略，由協(xié)議規(guī)定的狀態(tài)，此時整個系統(tǒng)中只有本地Cache的數(shù)據(jù)塊是唯一正確的拷貝，它的狀態(tài)是重寫狀態(tài)。因此，減少了總線的無效操作，降低了總線的流量，提高了總線的效率 缺點是：當內(nèi)存中的數(shù)據(jù)塊無效時，讀缺失引起的總線讀操作必須禁止對內(nèi)存的操作，而大多數(shù)總線不支持這種操作,基于目錄的協(xié)議,基本思想：,使用Cache目錄來存放有關(guān)數(shù)據(jù)塊拷貝駐留在Cache中的信息，把使其他Cache數(shù)據(jù)塊無效的一致性命令只發(fā)給存放有相應(yīng)數(shù)據(jù)塊的Cache，從而支持Cache的一致性。根據(jù)目錄的結(jié)構(gòu)特點，基于目錄的協(xié)議可分為3類：全映射（full-map）目錄、有限(limited)目錄和鏈式（chained）目錄。,全映射目錄協(xié)議,有限目錄協(xié)議,鏈式目錄,全映射目錄協(xié)議,2019/7/10,全映射目錄協(xié)議規(guī)定共享存儲器中的每個數(shù)據(jù)塊都有由若干位組成的目錄項，每個目錄項中有一位重寫位C和N個處理機位。 1.若重寫位C=1，則表示該數(shù)據(jù)塊已重寫； 2.若C=0，則表示該數(shù)據(jù)塊未被重寫。 N個處理機位分別表示對應(yīng)N個處理機的Cache中是否有該數(shù)據(jù)塊的拷貝，若某個處理機位=1，則表示對應(yīng)的處理機Cache中有該數(shù)據(jù)塊拷貝。,? 全映射目錄協(xié)議是怎樣保持Cache一致性的。,(1) 處理機從存儲器調(diào)入Cache塊,(2) 處理機寫Cache塊,第1步 使該數(shù)據(jù)塊目錄項的重寫位C=1，相應(yīng)處理機位=1。 第2步 使調(diào)入Cache的數(shù)據(jù)塊的有效位=1，允許寫位=0。,若Cache塊的有效位=1，允許寫位=0，那么，執(zhí)行下述過程： 第1步 Cache向存儲器模塊發(fā)出寫請求，并暫停處理機的工作； 第2步 存儲器根據(jù)該數(shù)據(jù)塊目錄項中N位處理機位的值，向那些處理位 =1的相應(yīng)Cache發(fā)出無效請求，使相應(yīng)Cache中的該塊拷貝的有效位=0， 并發(fā)回答信號給存儲器； 第3步 存儲器收到回答信號后，使該塊目錄項的重寫位C=1，并置其他處 理機位=0，發(fā)允許寫信號給相應(yīng)Cache； 第4步 Cache收到允許寫信號后，使該塊允許寫位=1，并激活處理機執(zhí)行 暫停的寫操作。 可見，對Cache塊寫操作時，系統(tǒng)根據(jù)Cache塊目錄項提供的指針將所 有其他有相同內(nèi)容的數(shù)據(jù)塊拷貝置為無效來保持Cache的一致性。,若Cache塊的有效位=1，允許寫位=1，則可直接執(zhí)行寫操作。 若Cache塊的有效位=0，則觸發(fā)寫缺失，需要從存儲器調(diào)入 相應(yīng)Cache塊。,(3) 處理機讀Cache塊,若Cache塊的有效位=1，則可直接執(zhí)行讀操作。 若Cache塊的有效位=0，則觸發(fā)讀缺失，需要從存儲器調(diào)入相應(yīng)的Cache塊。,舉個例子吧,X,C - - - 數(shù)據(jù),共享數(shù)據(jù)庫,Cache,Cache,Cache,P1,P2,P3,1中系統(tǒng)中所有的Cache都沒有數(shù)據(jù)塊X的拷貝。,當3個處理機都對X有讀請求之后，目錄協(xié)議的狀態(tài)如第二個圖所示，X的目錄項中3個處理機位都被置為1，表示3個Cache中都有X的拷貝。,X,C - - - 數(shù)據(jù),共享數(shù)據(jù)庫,Cache,Cache,Cache,P1,P2,P3,ReadX ReadX ReadX,Write,X,C 數(shù)據(jù),共享數(shù)據(jù)庫,Cache,Cache,Cache,P1,P2,P3,當處理機P3對X有寫請求之后，目錄協(xié)議的狀態(tài)如第三個圖所示，該狀態(tài)表示P3獲得了對X的寫權(quán)利，此狀態(tài)下，P3就可以寫X了。,全映射目錄協(xié)議的目錄的存儲器容量開銷與處理機數(shù)目N的平方成正比。因為目錄項的項數(shù)與處理機數(shù)N成正比，而目錄項的大小又與N成正比，所以目錄的存儲器開銷為O(N)。由于全映射目錄項中的處理機位是同處理機一一對應(yīng)的，增加處理機就要隨之增加所有目錄項的處理機位，所以全映射目錄協(xié)議不具有可擴展性。,結(jié)論：,返回,有限目錄協(xié)議,有限目錄的目錄項中，除一位的重寫位C之外，有數(shù)目固定的若干處理機指針，每個指針實際上是一個處理機編號。若有N個處理機，則每個處理機指針為log2N位，因此，目錄項的大小正比于Nlog2N，目錄的存儲器開銷為O(Nlog2N)。當某個處理機從存儲器調(diào)入一個Cache塊時，就將該處理機編號記入該數(shù)據(jù)塊目錄項的一個指針域中，建立該指針。有N個指針域的目錄項只能允許該數(shù)據(jù)塊最多可裝入N個Cache中。雖然目錄項中指針域的數(shù)目是固定的，但指針域并不是與處理機是一一對應(yīng)關(guān)系，任何一個指針域可為任何要求裝入該數(shù)據(jù)塊的處理機建立指針，因此，有限目錄具有可擴展性。 需要指出的是，若某個目錄項的所有指針域都已建立指針后，另有一個處理機要求裝入該數(shù)據(jù)塊，那么，有限目錄協(xié)議需要對這個目錄項實行指針替換，這種指針替換過程稱為驅(qū)逐。,以目錄項只有兩個指針域為例說明驅(qū)逐,X,C 數(shù)據(jù),共享數(shù)據(jù)庫,Cache,Cache,Cache,P1,P2,P3,ReadX,P1和P2的Cache中都有X的拷貝,若P3請求X的拷貝，則協(xié)議必須在C1和C2中選擇一個X拷貝使之無效，并用P3的指針替換無效X的指針。,鏈式目錄,鏈式目錄的優(yōu)點在于既不限制共享數(shù)據(jù)塊的拷貝數(shù)目，又保持了可擴展性。其主要方法是通過維護一個目錄指針鏈來跟蹤共享的數(shù)據(jù)塊拷貝。,鏈式目錄的目錄指針鏈若采用最簡單的單向鏈，那么，目錄項中除一位重寫位C之外，只需要一個指針域。因此，目錄的存儲器開銷為O(Nlog2N)。,采用單向鏈的鏈式目錄如下圖所示。,X,C 數(shù)據(jù),X Cache,CT,P1,P2,P3,共享存儲器,P1是第一個讀X的處理機,存儲器送一份X拷貝給C1，并附加一個鏈結(jié)束標志