文章目錄

• • • 1 局部性原理性能分析
    • 2 Cache工作原理（簡易版）
    • 3 地址映射
    • 4 替換算法
    • • • 4.1 替換算法（十進制）舉例
        • 4.2 Cache工作原理（加強版）
        • • 4.2.1寫策略-命中
          • 4.2.2 寫策略-未命中
        • 4.3 替換算法（二進制）例題
        • 4.4 Cache工作原理（高配版）
        • 4.5 Cache例題小結
    • 5 虛擬存儲器
    • • • 5.1 頁式虛擬存儲器
        • 5.2 段式虛擬存儲器
        • 5.3 段頁式虛擬存儲器
        • 5.4 快表TLB
        • 5.5 頁式虛擬存儲器-例題

1 局部性原理性能分析

• 空間局部性：在最近的未來要用到的信息（指令和數據），很可能與現在正在使用的信息在存儲空間上是鄰近的
• 時間局部性：在最近的未來要用到的信息，很可能是現在正在使用的信息

高速緩沖技術就是利用程序訪問的局部性原理，把程序中正在使用的部分存放在一個高速的，容量較小的Cache中，使CPU訪存操作大多數針對Cache進行，從而大大提高程序的執行速度

2 Cache工作原理（簡易版）

Cache工作原理類似操作系統分頁存儲快表機制

CPU與Cache之間的數據交換以字為單位，而Cache與主存之間的數據交換則以Cache塊為單位

命中率H:CPU欲訪問的信息已在Cache中的比率
設一個程序執行期間，Cache的總命中次數為N_c，訪問主存的總次N_m
則H=N_c/N_c+N_m

缺失率：M=1-H

設t_c為命中時的Cache訪問時間，t_m為未命中時的訪問時間
Cache—主存系統的平均訪問時間Ta為T_a=Ht_c+（1-H）t_m

假設Cache的速度是主存的5倍，且Cache的命中率為95%，則采用Cache后，存儲器性能提高多少（設Cache和主存同時被訪問，若Cache命中則中斷訪問主存）？

若采用先訪問Cache再訪問主存的方式：

不命中時，訪問cache耗時為t，發現不命中后再訪問主存耗時為5t，總耗時為6t
故系統的平均訪問時間為 T2 = 0.95×t+0.05×6t = 1.25t
故性能為原來的 5t / 1.25t = 4倍，即提高了3倍。

Cache三大核心問題：

主存中的塊放到Cache中哪個位置？
（1）空位隨意放：全相聯映射
（2）對號入座：直接映射
（3）按號分組，組內隨意放：組相聯映射

對于（1），Cache滿了如何處理？對于（2）（3），對應位置被占用如何處理？
隨機（RAND）算法、先進先出（FIFO）算法、近期最少使用（LRU）算法、最不經常使用（LFU）算法。

修改Cache中的內容后，如何保持主存中相應內容的一致性？

命中：
全寫法（write-through）
寫回法（write-back）

不命中：
寫分配法（write-allocate）
非寫分配法（not-write-allocate）

3 地址映射

Cache高三位確定行號，低6位確定行內地址，對應這行中的哪個單元
主存：

低的6位表示每一行中的具體哪個位置，對應這行的哪個單元
中的3位對應Cache的行號
高的19位就是主存比Cache多出來的地址位數

全相聯映射：

主存中內容可以往Cache中隨意放，但需要設置一個有效位，如果是0表示空閑，如果是1表示已經占滿；
根據有效位可以判斷是否放了東西，根據有效位后的標號對應主存的地址（主存的地址高位作為一個標記，存放在Cache相應的單元）

Cache需要保存地址高位，綠+藍都要存

直接映射：

由于主存中多塊可以放在Cache中同一位置，為了區分具體來自主存中哪一位置，把主存中的塊存過去后，立刻把主存地址高位存到對應的Cache行，作為標記項

Cache需要保存地址高位，一一對應的無需保存，存綠

組相聯映射：按號分組，組內任意放（綜合了上面兩者優勢）

高的兩位做組號，0 1對應0組（高兩位00） ，2 3對應1組（高兩位01）…

三種方式地址映射：

有效位告訴機器此塊數據要使用，不能被其他數據覆蓋（Cache中只要放了數據就置有效位1）
標記位告訴機器，Cache中數據來自主存具體哪一位置

4 替換算法

隨機算法（RAND）：隨機地確定替換的Cache塊。它的實現比較簡單，但沒有依據程序訪問的局部性原理，故可能命中率較低。

先進先出算法（FIFO）：選擇最早調入的行進行替換。它比較容易實現，但也沒有依據程序訪問的局部性原理，可能會把一些需要經常使用的程序塊（如循環程序）也作為最早進入Cache的塊替換掉。

近期最少使用算法（LRU）：依據程序訪問的局部性原理選擇近期內長久未訪問過的存儲行作為替換的行，平均命中率要比FIFO要高，是堆棧類算法。
LRU算法對每行設置一個計數器，Cache每命中一次，命中行計數器清o，而其他各行計數器均加1，需要替換時比較各特定行的計數值，將計數值最大的行換出。

最不經常使用算法（LFU）：將一段時間內被訪問次數最少的存儲行換出。每行也設置一個計數器，新行建立后從0開始計數，每訪問一次，被訪問的行計數器加1，需要替換時比較各特定行的計數值，將計數值最小的行換出。

4.1 替換算法（十進制）舉例

說明：
直接映射：

（1）主存塊號/總塊數 余數→Cache塊號
（2）商→對應的標記位

• 訪問4,6號，由于Cache為空，未命中，標記置為0，再訪問12，對應Cache中4號單元，雖然有效位1，但是標記位0與12除8商1不一樣，則發生替換，12替換4，并把標記位改1，未命中
• 訪問4未命中，4號單元標記位改0，訪問8…
  每次訪問一個單元，用商更新一下被訪問的標記位

FIFO：

每新進來一個元素，先往下放，如果之前有元素，就把之前有的元素往上抬，則下面的元素始終是新放入的，往上抬時，自然而然替換了
訪問第四個4時，因為里面有4和12，命中，訪問接下來的8把最上面12替換出去…

LRU:

把即將要替換的放上面，把最近使用過的放下面
訪問12時，12根4相比，是剛剛使用的，把12放下面，接下來訪問4，12是最近不太用的，往上抬，且4命中；訪問8時，8往下放，替換12…

---

4.2 Cache工作原理（加強版）

4.2.1寫策略-命中

全寫法（寫直通法，write-through）：當CPU對Cache寫命中時，必須把數據同時寫入Cache和主存，一般使用寫緩沖（write buffer）

寫回法（write-back）：當CPU對Cache寫命中時，只修改Cache的內容，而不立即寫入主存，只有當此塊被換出時才寫回主存

4.2.2 寫策略-未命中

寫分配法（write-allocate）：把主存中的塊調入Cache，在Cache中修改。
搭配寫回法使用。

非寫分配法（not-write-allocate）：只寫入主存，不調入Cache。
搭配全寫法使用。

4.3 替換算法（二進制）例題

設主存地址空間大小為1KB，按字節編址，Cache由8個塊構成，每個Cache塊大小為16B，CPU依次訪問以下地址：0001001110、1001110010、0001001111、0011000010、0101001000、1011110010、1111010000、0011001001（十進制為78、626、79、194、328、754、976、201），求：

（1）假設地址映射方式為全相聯映射，在采用FIF0、LRU、LFU替換算法時，分別求Cache命中次數。

首先分析地址結構：

訪問0001001110時，有效位由0改為1，標記位就是地址前六位000100
訪問1001110010時，有效位由0改為1，標記位就是地址前六位100111
訪問0001001111時，標記位地址前六位000100，已在Cache中，命中，或者用十進制角度，64~79為一塊，訪問78，再訪問79，命中（調入的一塊同標記位的地址，而不是一個地址）

全相聯模式下，可能不會發生替換，Cache是一點一點用完

（2）假設地址映射方式為直接映射，求Cache命中次數。

首先分析地址結構：

訪問0001001110時，由100可知放在Cache中4號塊，把標記置為000，有效位1
訪問1001110010時，由111可知放在Cache中7號塊，把標記置為100，有效位1
訪問0001001111時，由100可知放在Cache中4號塊，此時有效位1，Cache標記位000與當前地址標記位000同，命中
訪問0011000010時，由100可知放在Cache中4號塊，此時有效位1，Cache標記位001與當前地址標記位000不同，未命中，替換，把001替換000

直接映射：對號入座→有沖突直接替換，不涉及替換策略

首先分析地址結構：

• 訪問0001001110時，由組號00可知放在Cache中0號塊，把標記置為0001，有效位1，在組內采用全相聯映射，放0號組的1號塊和2號塊都可以，假設放在1號塊
• 訪問1001110010時，由11可知放在Cache中3號組，把標記置為1001，有效位1,
• 訪問0001001111時，由00可知放在Cache中0號組，此時有效位1，Cache標記位0001與當前地址標記位0001同，命中
• 訪問0011000010時，由00可知放在Cache中0號組，此時有效位1，Cache標記位0011與當前地址標記位0001不同，未命中，把它放在0組中的2號塊（1號塊已放了）
• 訪問0101001000時，由00可知放在Cache中0號組，第0組已滿，但當前標記與Cache兩個標記都不同，需要替換，

若采用FIFO（替換最早調入的）：最早調入的塊標記是0001，故替換之。
若采用LRU（替換最近未使用的）：剛用過0011，故替換0001
LFU（比較次數，替換使用次數最少的）

（4）假設其它配置同（3），采用寫回法和直寫法時，Cache的總容量分別為多少？

標記項：有效位1位固定，標記位由地址映射方式決定，維護位由替換算法決定，替換位由替換策略決定

4.4 Cache工作原理（高配版）

4.5 Cache例題小結

5 虛擬存儲器

• 虛擬存儲器是一個邏輯模型（關注功能，不關注實現）
• 功能：用戶給出一個地址，叫做虛地址或邏輯地址，虛擬存儲器要給出該地址對應的數據。
• 實現：由輔助硬件將虛地址映射到主存當中的某個單元，主存單元地址稱為實地址或物理地址。

5.1 頁式虛擬存儲器

虛擬空間與主存空間都被劃分成同樣大小的頁，主存的頁稱為實頁，虛存的頁稱為虛頁。

虛地址到物理地址映射過程：

5.2 段式虛擬存儲器

• 段式虛擬存儲器中的段是按程序的邏輯結構劃分的，各個段的長度因程序而異。
• 虛擬地址分為兩部分：段號和段內地址。
• 段表：每一行記錄了與某個段對應的段號、裝入位、段起點和段長等信息。
  由于段的長度可變，所以段表中要給出各段的起始地址與段的長度。

地址映射過程：

5.3 段頁式虛擬存儲器

• 把程序按邏輯結構分段，每段再劃分為固定大小的頁，主存空間也劃分為大小相等的頁，程序對主存的調入、調出仍以頁為基本傳送單位。
• 每個程序對應一個段表，每段對應一個頁表。
• 虛擬地址：段號+段內頁號+頁內地址

5.4 快表TLB

• 頁表、段表存放在主存中，收到虛擬地址后要先訪問主存，查詢頁表、段表，進行虛實地址轉換。
• 放在主存中的頁表稱為慢表（Page）。
• 提高變換速度→用高速緩沖存儲器存放常用的頁表項→快表（TLB）

5.5 頁式虛擬存儲器-例題

地址變換第一步，在于分析地址結構
標記對應虛頁號，頁框對應實頁號
有效位0，快表未命中，接下來查詢頁表，若命中，頁表完成虛實轉換，若未命中，主存中調出來

實頁號與虛頁號相互替換，頁內地址保持不變

總結

以上是生活随笔為你收集整理的4 计算机组成原理第三章 存储系统 高速缓冲存储器 虚拟存储器的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。