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

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

2. Cache coherency的問題是什么？

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

3. 基于snoop的緩存一致性協議和基于directory的緩存一致性協議有什么區別？

在基于Snoop的一致性協議中，來自處理器的數據請求被發送到共享系統里的所有其它處理器。其它處理器根據這個請求查看自己是否有數據的副本，并做出相應的響應。因此，每個處理器都試圖保持內存的一致性視圖。

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

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

4. 什么是MESI協議？

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

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

5. 什么是MESIF和MOESIF協議？

這兩個協議都是MESI協議的擴展，引入了兩個新的狀態”F”和”O”，解釋如下：

• F(Forward)：F狀態時S狀態的一種特殊形式，表明cache應該通過轉發數據來充當給定cache line的任何請求的指定反饋者。如果系統中有多個cache具有處于S狀態的同一cache line，則將其中一個指定為F狀態，以便為來自不同處理器的新請求轉發數據。該協議確保，如果任何cache保存的cache line為S狀態，那么最多只有一個(其他)cache保存的cache line為F狀態。這種狀態有助于減少對memory帶寬的占用，因為沒有F狀態，即使一條cache line在多個cache中處于S狀態，它們都不能將數據轉發給請求讀或寫的不同處理器。（請注意，cache中的S狀態cache line只能服務于相同的處理器讀取）
• O(Owned)：O狀態時一種特殊的狀態，它是為了在不需要寫回memory的情況下在系統的不同cache中移動修改過的或dirty的數據而引入的。如果cache line還與其它可以使cache line保持S狀態的cache共享，則cache line需要從M狀態轉換到O狀態。O狀態有助于將修改后的數據推遲寫回memory，直到真正需要時再寫。

6. 什么是RFO？

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