cache一致性協議實現的基本方法

Cache一致性協議實現的基本方法主講：周艷芳副講：繳萬鑫知識回顧（一）解決主存速度與CPU速度差距的辦法：Cache--主存存儲層次：采用高速緩沖存儲器方式知識回顧（二）Cache存儲器中保存的字塊是主存中相應字塊的一個副本。如果程序執(zhí)行過程中要對該字塊的某個單元進行讀寫操作，就會遇到如何保持Cache與主存的一致性問題。1)不命中時：直接把待寫的信息寫入主存。2)命中時：有兩種寫入方式。①寫回法：只更新Cache單元，并加以標記，當該塊從Cache移出時，再更新相應的主存單元。②寫直達法：Cache單元與主存單元同時寫。寫回法速度快，但有一段時間主存內容與Cache內容不一致；寫直達法能隨時保持主存數據的正確性，但有可能增加多次不必要的寫主存。

問題引出Cache數據與主存數據一致是指：在采用Cache的系統(tǒng)中，同樣一個數據可能既存在于Cache中，也存在于主存中，兩者數據相同則具有一致性，數據不相同就叫做不一致性。如果不能保證數據的一致性，那么，后續(xù)程序的運行就要出現問題。

Cache一致性

目前，在并行系統(tǒng)的產品中大多數都采用基于總線的存儲器結構?？偩€是保證高速緩存一致性的最方便的設備，它允許系統(tǒng)中各個處理機能夠監(jiān)測對存儲器進行的所有操作，如果這些操作破壞了本地高速緩存中數據的一致性狀態(tài)，高速緩存控制器就可以采取相應的動作維護高速緩存的一致性。采用這種機制維護高速緩存一致性的協議的系統(tǒng)中，每個高速緩存都在監(jiān)聽其它高速緩存的操作，所以稱為監(jiān)聽總線協議。而對于可擴展多處理機系統(tǒng)，常常采用互連網絡實現多處理機互連，其網絡帶寬隨著處理機數目的增加而增大，但是這些網絡沒有方便的監(jiān)聽機制，也難于進行有效的廣播，所以常常采用基于目錄的協議。下面分別對這兩類協議進行介紹。

解決Cache一致性問題的兩種協議

如果接在共享總線上的處理機具有自己的本地高速緩存，那么可以采用兩種方法：1.寫無效策略和寫更新策略：1）寫無效（Writeinvalidate）當任何一個處理機寫自己的高速緩存時，由它負責把其他的高速緩存復本變成無效的，使其他高速緩存中（和主存中）的復本都是“過時”的。根據對于主存中復本的處理不同，又可以分成寫通過和寫回策略：——寫通過：更新主存中的復本，最后的狀態(tài)是一個高速緩存中的復本和主存中的復本是有效的，其他復本都是無效的?！獙懟兀核怪鞔嬷械膹捅疽矡o效，最終只有一個高速緩存中的復本使有效的。2）寫更新

當任何一個處理機寫自己的高速緩存時，改寫其它所有的復本。所以操作的結果是所有數據塊的復本都是“有效”的。監(jiān)聽總線協議

這兩種策略都存在缺點和問題。寫無效的問題在于兩個方面：使各個高速緩存中數據塊的復本無效的開銷比較大；由于無效復本引起缺失造成的開銷。而寫更新的問題在于更新所有復本的開銷比較大。2、寫一次協議結合了上面介紹的協議的優(yōu)點，JamesGoodman在1983年提出了一種基于總線的多處理機系統(tǒng)的高速緩存一致性協議。它的主要思想和作法是：高速緩存塊的第一次寫采用寫通過策略，產生一份正確的主存復本，并且使其他高速緩存的復本無效；之后，就采用寫回策略：其他高速緩存和主存中的復本均無效。在設計、分析高速緩存一致性協議時要考慮和解決的幾個主要問題有

1）高速緩存可能出現的狀態(tài)集合

2）共享主存的狀態(tài)

3）為維護一致性而引起的狀態(tài)轉換下面分別結合寫一次協議進行說明1）每個高速緩存復本可能出現的四種狀態(tài)（1）有效（Valid）與主存復本一致的高速緩存復本，即該復本未經修改，所以這個復本不是唯一的正確復本。別的高速緩存中也可能存在該數據塊的有效復本。（2）保留（Reserved）這一高速緩存的復本是第一次被修改，并采用寫通過方法寫入主存。所以這個高速緩存中的復本與主存中的復本是一致的。而且系統(tǒng)中也只有這兩個復本是有效的。（3）重寫（Dirty）高速緩存中的復本不止一次被修改過，由于不再采用寫通過的方法，所以這個高速緩存中的復本是唯一的有效復本，與主存和其他高速緩存中的復本都不一致。主存中的復本也是無效的。（4）無效（Invalid）與主存中和其他高速緩存中的復本不一致或在高速緩存中根本沒有該復本。2）進行高速緩存操作時用到的信號（1）P-Write：本地處理機寫自己的高速緩存復本（2）P-Read：本地處理機讀自己的高速緩存復本這兩條命令都是局部/本地命令（3）Write-inv：遠程高速緩存在寫命中時在總線上廣播一個無效命令（4）Read-inv：遠程高速緩存在寫缺失時在總線上廣播一個無效命令（5）Read-blk：從另外一個高速緩存中讀出一份有效復本。這兩條屬于一致性命令3）寫操作可能遇到的幾種情況（1）如果C1為VALID，寫C1時，則寫命中（Write

hit）

a.如果內存單元所在的塊在高速緩存中，則可以寫高速緩存命中。

b.如果內存單元所在的塊不在高速緩存中，則寫缺失，將內存單元所在塊讀入高速緩存，再進行寫操作發(fā)P-Write修改C1內容，修改內存，發(fā)Write-Inv給所有高速緩存，使它們的狀態(tài)變?yōu)闊o效。同時使本地的高速緩存中數據塊的狀態(tài)變Reserved。（2）如果C1為Reserved，對C1進行寫操作時，則寫命中。發(fā)P-Write命令修改C1內容，不修改內存中的復本，C1狀態(tài)變?yōu)镈irty（3）如果C1為Dirty，寫C1時則寫命中。發(fā)出P-Write命令修改C1的內容，不修改主存中的復本，C1保持Dirty狀態(tài)（4）如果C1為Invalid，則寫不命中。如果其他高速緩存中也沒有該數據塊的復本，只有主存中有該數據塊的復本，則將主存中的復本復制到C1中，再將要寫入的內容13寫入C1，這是C1和主存內容不一致。把C1狀態(tài)置為Dirty。寫入后，C1與主存中的內容至少有一個單元不一致。（5）如果C1為Invalid，C2為Dirty，這時主存中的內容與C2中的不一致。將C2中的數據塊復制到C1中，將C1的狀態(tài)置為Dirty，發(fā)Read-inv使其他高速緩存的有關復本變成無效（6）如果C1為Invalid，C2為Reserved，這時主存中的內容和C2的一致，將C1的狀態(tài)置為Dirty，發(fā)Read-inv，使其他高速緩存中的有關復本變成無效狀態(tài)。4）讀操作可能遇到的情況（1）