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

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

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

2. Cache coherency的問(wèn)題是什么？

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

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

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

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

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

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

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

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

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

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

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

6. 什么是RFO？

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