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訪問(wèn)的頻率，并決定替換使用次數(shù)最少的cache line。
• Random replacement算法：該算法不存儲(chǔ)任何信息，當(dāng)需要替換時(shí)隨機(jī)選擇一個(gè)cache line。

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

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

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

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

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

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

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

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

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

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

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

• F(Forward)：F狀態(tài)時(shí)S狀態(tài)的一種特殊形式，表明cache應(yīng)該通過(guò)轉(zhuǎn)發(fā)數(shù)據(jù)來(lái)充當(dāng)給定cache line的任何請(qǐng)求的指定反饋者。如果系統(tǒng)中有多個(gè)cache具有處于S狀態(tài)的同一cache line，則將其中一個(gè)指定為F狀態(tài)，以便為來(lái)自不同處理器的新請(qǐng)求轉(zhuǎn)發(fā)數(shù)據(jù)。該協(xié)議確保，如果任何cache保存的cache line為S狀態(tài)，那么最多只有一個(gè)(其他)cache保存的cache line為F狀態(tài)。這種狀態(tài)有助于減少對(duì)memory帶寬的占用，因?yàn)闆](méi)有F狀態(tài)，即使一條cache line在多個(gè)cache中處于S狀態(tài)，它們都不能將數(shù)據(jù)轉(zhuǎn)發(fā)給請(qǐng)求讀或?qū)懙牟煌幚砥?。（?qǐng)注意，cache中的S狀態(tài)cache line只能服務(wù)于相同的處理器讀取）
• O(Owned)：O狀態(tài)時(shí)一種特殊的狀態(tài)，它是為了在不需要寫(xiě)回memory的情況下在系統(tǒng)的不同cache中移動(dòng)修改過(guò)的或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ù)推遲寫(xiě)回memory，直到真正需要時(shí)再寫(xiě)。

6. 什么是RFO？

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