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

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