挑戰408——組成原理(15)——Cache塊中的替換演算法

其他的兩種方式,都需要考慮替換演算法 常見的替換演算法有:

- FIFO演算法:即先進先出的演算法,選擇最早調入Cahce的字塊進行替換,這種方式實現簡單。但是由於總是以最早調入的Cache塊為替換目標,沒有按照程序的局部性進行。所以並不能提高Cache的命中率。因為最早調入的信息,以後可能還會用到。

- LRU演算法:近期最少使用演算法,這種做法替換的是近期用的最少的字塊,較好的利用了局部性原理,但是需要時刻記錄Cache各個字塊的使用情況,以便確定那哪個字塊是近期最少使用的。

- LFU演算法:將一段時間內訪問次數最少的存儲塊換出,每行設立一個計時器,每訪問一次,計時器的數值加1,替換的時候,將最數值最小的Cache塊替換出去。

- Rand演算法:顧名思義,隨機替換。

注意:Cache對於用戶來說是透明的,用戶編程的時候,所用的地址是主存地址,用戶並不知道這些主存塊是否已經調入了Cache塊中,因為主存與Cache之間的替換是由機器自動實現的。

Cache寫策略

Cache的寫操作比較複雜,因為對Cache塊內寫入信息,必須與映射的主存塊內的信息完全一致,那麼如何使得cache與主存的內容一致呢?目前常用的方式有以下兩種:

1. 全寫法(write—through):又稱寫直達法,即在進行寫操作的同時,寫入Cache和主存,這樣主存中的數據與Cache中的數據就能時刻保持一致。但是這樣會導致訪存次數的增加。

2. 寫回法(write—back):即寫操作的時候,只把數據寫入Cache中,待到Cache塊要被換出的時候,再寫出到主存中,,為了識別Cahce中的數據是否與主存中的一致,於是在Cache中每一塊都增設一個標誌位(也稱為「臟」位)。臟位有兩種狀態,清:表示未被修改過,這個塊當然也與主存間的數據塊的內容一致了;濁:則表示被修改過,內容與主存不一致,於是替換演算法就將此塊替換出去。並將濁位置為清。顯然在計算機中用0和 1 來表示這兩種狀態

而上面的兩種狀態,都是對應於寫命中的情況(也就是CPU要寫的單元都在Cache上面),那麼當CPU訪問的數據塊不在Cache中,那又該如何?

我們也常常有兩種做法:

- 寫分配法:載入主存的塊到Cache中,然後更新這一塊。(所以常常跟寫回法一同使用 )

- 寫不分配法:對應於上面的做法,這個做法就是只是將要修改的內容寫入到主存塊而已,不進行與Cache之間的調塊

Cache的改進

Cache的特性決定了它不能大容量的存儲,所以目前我們普遍採用多個Cache,主要的改進方面有1,增加Cache的級數。2將統一的Cache變成分立的Cache。於是有了多級緩存的概念。將緩存分為多個級別,越接近CPU,速度就越快,容量也就越小。所以指令Cahce和數據Cache一般都在L1(靠近CPU)的那一級別。隨著集成電路的發展,又把一級緩存直接與CPU做 在同一個晶元上,稱為片內緩存。其他的稱之為片外緩存。

下面來看一道Cahce——主存映射的題目

其實有三問,但是我們只需要了解一問就好了。接下來讀題:

第一,主存容量為16mb,也就是2的24次方b,所以主存地址的總欄位長度為24位。(不然表示不了那麼多的地址)

第二,Cache容量的為8kb,根據前面的數據,我們可以知道這個機器是用位元組存儲的,所以每個字塊8個字,每個字32位。32位就是4個位元組,即8 X 4B.,所以塊內地址一共需要5位。

第三,我們要確定組內地址,也就是說Cache要被分成幾組。我們剛剛得到了塊內的地址,那麼這個時候我們就知道了Cache一共有8kb/2^5 =2的8次方,也就是2的8次方塊。 於是的得出組數為:2的8次方除以4(4塊為一組) = 2的6次方。 所以組內地址欄位為6.

第四,用總長度減去已知的兩個長度,於是得到標記欄位。