1. 在組相聯(lián)cache中，用于替換cache line的算法有哪些？

• LRU(Least Recently Used)算法：該算法會跟蹤每個cache line的age(年齡)情況，并在需要時替換掉近期最少使用的cache line。
• MRU(Most Recently Used)算法：這與LRU相反，最年輕的cache line會優(yōu)先被替換掉。
• PLRU(Pseudo LRU)算法：這與LRU相似，它沒有age跟蹤cache line(這樣開銷較大)，只有1個或2個bit來跟蹤cache line使用情況。
• LFU(Least Frequently Used)算法：該算法會跟蹤一個cache line訪問的頻率，并決定替換使用次數(shù)最少的cache line。
• Random replacement算法：該算法不存儲任何信息，當(dāng)需要替換時隨機(jī)選擇一個cache line。

2. Cache coherency的問題是什么？

在SMP(Shared Multiprocessor systems)中，多個處理器都有自己的cache，同一數(shù)據(jù)(同一地址)的多個副本可能同時存在于不同的cache中。如果允許每個處理器自由更新cache，則可能導(dǎo)致數(shù)據(jù)一致性被破壞了。例如：如果允許兩個處理器向相同的地址寫入值，那么在不同的處理器上讀取相同的地址可能會看到不同的值。

3. 基于snoop的緩存一致性協(xié)議和基于directory的緩存一致性協(xié)議有什么區(qū)別？

在基于Snoop的一致性協(xié)議中，來自處理器的數(shù)據(jù)請求被發(fā)送到共享系統(tǒng)里的所有其它處理器。其它處理器根據(jù)這個請求查看自己是否有數(shù)據(jù)的副本，并做出相應(yīng)的響應(yīng)。因此，每個處理器都試圖保持內(nèi)存的一致性視圖。

在基于directory的一致性協(xié)議中，directory用于跟蹤哪些處理器正在訪問和緩存哪些地址。任何發(fā)出新請求的處理器都將檢查該directory，以了解是否有任何其它處理器用于數(shù)據(jù)副本，然后可以向該處理器發(fā)送點(diǎn)到點(diǎn)請求，以獲取最新的數(shù)據(jù)副本。

兩者的優(yōu)缺點(diǎn)為：基于snoop的一致性協(xié)議用于較小的系統(tǒng)的話，如果有足夠的帶寬用于傳遞請求，它會更快。但對于較大的SMP系統(tǒng)不具有可伸縮性，因此需要為每個請求廣播消息，可能會使系統(tǒng)過載阻塞?；赿irectory的一致性協(xié)議由于在發(fā)送消息之前需要查找記錄的表，可能會有較長的延遲。但它沒有廣播消息，可伸縮性更好，通常用于較大的SMP系統(tǒng)中。

4. 什么是MESI協(xié)議？

MESI協(xié)議是具有多個write-back 類型cache的設(shè)計中最常用的cache一致性協(xié)議。MESI表示在所有cache中跟蹤每個cache line并用于響應(yīng)snoop請求的狀態(tài)。這些不同的狀態(tài)可以解釋如下：

• M(Modified)：表示cache line數(shù)據(jù)相對于memory數(shù)據(jù)被修改過了，為dirty的。
• E(Exclusive)：此狀態(tài)表示cache line數(shù)據(jù)相對于內(nèi)存是clean的，且只在該cache中存在。Exclusive屬性允許該cache所在的處理器對該cache line進(jìn)行寫操作。
• S(Shared)：該狀態(tài)表示cache line被多個cache共享，并且相對memory也是clean的。由于這是在所有cache共享的，因此協(xié)議不允許直接對該cache line進(jìn)行寫操作。
• I(Invalid)：該狀態(tài)表示cache line無效，沒有任何有效數(shù)據(jù)。
• 當(dāng)cache line處于除Invalid之外的任何狀態(tài)時，cache都可以處理讀請求。當(dāng)cache line處于Modified或Exclusive狀態(tài)時，才可以處理寫請求。

5. 什么是MESIF和MOESIF協(xié)議？

這兩個協(xié)議都是MESI協(xié)議的擴(kuò)展，引入了兩個新的狀態(tài)”F”和”O(jiān)”，解釋如下：

• F(Forward)：F狀態(tài)時S狀態(tài)的一種特殊形式，表明cache應(yīng)該通過轉(zhuǎn)發(fā)數(shù)據(jù)來充當(dāng)給定cache line的任何請求的指定反饋者。如果系統(tǒng)中有多個cache具有處于S狀態(tài)的同一cache line，則將其中一個指定為F狀態(tài)，以便為來自不同處理器的新請求轉(zhuǎn)發(fā)數(shù)據(jù)。該協(xié)議確保，如果任何cache保存的cache line為S狀態(tài)，那么最多只有一個(其他)cache保存的cache line為F狀態(tài)。這種狀態(tài)有助于減少對memory帶寬的占用，因為沒有F狀態(tài)，即使一條cache line在多個cache中處于S狀態(tài)，它們都不能將數(shù)據(jù)轉(zhuǎn)發(fā)給請求讀或?qū)懙牟煌幚砥鳌＃ㄕ堊⒁?，cache中的S狀態(tài)cache line只能服務(wù)于相同的處理器讀取）
• O(Owned)：O狀態(tài)時一種特殊的狀態(tài)，它是為了在不需要寫回memory的情況下在系統(tǒng)的不同cache中移動修改過的或dirty的數(shù)據(jù)而引入的。如果cache line還與其它可以使cache line保持S狀態(tài)的cache共享，則cache line需要從M狀態(tài)轉(zhuǎn)換到O狀態(tài)。O狀態(tài)有助于將修改后的數(shù)據(jù)推遲寫回memory，直到真正需要時再寫。

6. 什么是RFO？

RFO代表Read for Ownership。這是cache一致性協(xié)議中的一種操作。它是由處理器試圖寫入共享或無效狀態(tài)的cache line時發(fā)出的，這將導(dǎo)致所有其它處理器將該cache line的狀態(tài)設(shè)置為Invalid。RFO是意圖寫入該memory地址的讀操作。因此，該操作是排他的，它將數(shù)據(jù)讀到cache中，并使持有該memory地址的所有其它處理器的cache無效掉這個cache line。