1. 基本概念

1. 存盤系統的體系結構

圖片摘自這篇博客：圖片來源

2. cache在存盤系統中的位置

cache（快取）位于CPU內部，其讀取速度快于主存，但容量小于主存，cache中存放的是程式需要用到的資料，CPU處理時直接從cache中讀取資料速度要快于從主存中讀取，

在CPU和主存之間引入cache是為了：

①避免CPU與外部設備爭搶主存
外設向主存請求資料級別高于CPU，可能導致CPU等待較長時間，
②提高取指令和取資料的速度
主存速度提高跟不上CPU的發展速度，差距總在5倍以上，

3. 程式訪問的區域性原理

之所以可以把CPU當前需要的資料和程式放在cache中，是因為程式訪問具有區域性的原理：

時間區域性 一個存盤單元被訪問，此單元很快就會再次被訪問

空間區域性 一個存盤單元被訪問，該單元臨近的單元也可能很快被訪問，

4. 命中率

如果訪問的資料在cache中，稱為訪問cache命中，

設某Cache的命中率為h，其中訪問Cache的時間為tc，訪問M的時間為tm，設Nc訪問cache命中的總次數，Nm表示訪問cache不命中而訪問M的次數，則有：
h=Nc/(Nc+Nm)×100%
①若CPU在訪問cache不命中時再訪問主存
平均訪存時間ta=h·tc+(1-h)·(tc+tm)=tc+(1-h)·tm
②若CPU同時訪問cache和主存，訪問命中時中止對主存的訪問，
平均訪存時間ta=h·tc+(1-h)·tm

5. 字、字塊、標記、組

字 ：1個字由n個位元組組成（n≥1），字是CPU訪問存盤器時可存取的最小單位

字塊 ：1個字塊包含n個字（n≥1），字塊是主存與cache交換的最小單位

也就是說，cache和主存在交換時是以字塊為單位的，一次交換一個字塊（包含好多個字，利用到了區域性原理），而CPU在訪問cache時，一次只存取一個字，

標記 ：cache中存放的主存塊地址稱為標記，

組 ：多個字塊組成的一個邏輯整體稱為組，

2. cache-主存的三種映射方式

2.1 全相聯映射

思路

允許主存中的每個字塊映像到cache的任何一個字塊位置上，

示意圖

主存地址和cache地址

設定主存地址和cache地址的一個目的是，可以通過主存地址來找到cache地址，這樣才能實作主存和cache字塊的交換，

主存地址：

包括塊標記和字塊內地址兩部分，其中塊標記相當于字塊在主存中的地址，字塊內地址為字塊中某個字的地址，

示意圖：

cache地址：

包括字塊號和字塊內地址，其中，字塊號為字塊在cache中的地址，字塊內地址為字塊中某個字的地址，

注意：主存地址和cache地址中的字塊內地址相同，

示意圖：

相聯存盤器：

既然全相聯映射方式的思路是：主存中的字塊映射在cache中的任一字塊，計算機怎么知道映射到哪一字塊了？到時候怎么操作呢？這就需要一個目錄表來查找主存中的某一字塊與cache中某一字塊的對應關系：

該目錄表由三部分組成：主存字塊標記（主存地址的第一部分），cache字塊地址（cache地址的第一部分），有效位（1位），目錄表的行數為cache的字塊數，這很好理解，因為目錄表的目的就是查找主存字塊和cache字塊的對應關系，

特點

（1）映像方式靈活，主存中的一個字塊可以對應cache的任意一塊；
（2）主存地址映射到cache無規則可言，必須使用相聯存盤器通過按內容查找獲取cache塊號，
（3） 全部由硬體實作，速度快，但硬體實作難度大；
（4）由于使用相聯存盤器存盤目錄表，成本高，當cache容量越大時，所需相聯存盤器的容量也越大，成本也越高，僅適用于小容量cache采用，

2.2 直接映射方式

思路

主存中的一塊只能拷貝到cache中的一個特定行位置，設主存的塊號為i，cache中的塊號為j，cache的總塊數為N，則映射關系為：
j = i mod N

示意圖

主存地址與cache地址

主存地址：

包括塊標記、字塊地址、字塊內地址三部分，其中，塊標記為字塊在主存中的地址，字塊地址為字塊在cache中的地址（計算方法就是上面說的），字塊內地址為字在字塊中的地址，

因此這種映射方法不需要目錄表了，（因為主存地址中存有要映射到cache相應字塊的字塊地址了）

示意圖：

cache地址：

包括字塊地址、字塊內地址兩部分：其中，字塊地址為字塊在cache中的地址，字塊內地址為字在字塊中的地址，

注意：cache地址中的字塊地址和字塊內地址和主存地址中的相同，

示意圖：

特點

（1）映像函式簡單，實作硬體簡單，無需相聯存盤器，實作成本較全相聯映像方式低；
（2）地址變換速度快，如果命中且字塊有效，那么主存地址去掉區號后的低位部分就是cache地址，
（3）塊沖突率高，當兩個或兩個以上的主存塊映射到相同的cache發生沖突時，即使其他cache塊空閑也不能被使用，當兩塊交替映射到同一cache時，造成頻繁置換——抖動，

2.3 組相聯映射方式

思路

組相聯映像方式為前兩種方式的折衷，其方法是將cache按某種規格分組，主存中若干字塊映射到同一個組中，組間為直接映像方式，組內為全相聯映像，

主存字塊在cache組號求法為：主存字塊號 mod cache組數
示意圖

主存地址和cache地址

主存地址：

主存地址包括主存字塊標記、組號和字塊內地址三部分，其中主存字塊標記為字塊在主存中的地址，組號為cache分的組的組號，字塊內地址為字在字塊中的地址，

示意圖：

cache地址：

cache地址包括組號、字塊號和字塊內地址三部分組成，其中，組號為cache分組的組號，字塊號為每組內字塊的地址，字塊內地址為字在字塊中的地址，

注意：主存地址和cache地址中的組號和字塊內地址相同，

示意圖：

特點

（1）因為是兩種映像方式的折衷，因此地址結構較為復雜，比較的情況較多，需要引入相聯存盤器；
（2） 兼顧了映像的靈活性和操作的復雜程度，
（3）目前應用較多，每組具有v個字塊的組相聯映像方式常稱為v路組相聯，v一般取值較小，典型值有2、4、8、16，

3. 三種映射方式例題

【例題】

設主存容量為256K字，cache容量為2K字，塊長為4，按字編制，
①設計cache地址格式，cache可裝入多少塊資料，
②在直接映射方式下，設計主存地址格式，
③在四路組相聯映射方式下，設計主存地址格式
④在全相聯映射方式下，設計主存地址格式

【解答】

因為是按位元組編址，所以主存地址有18位，cache地址有11位，因為塊長為4，說明每個字塊有4個字，故字塊內地址為2位，

① 字塊內地址為2位，故字塊地址有11-2=9位，cache地址如下：

② 直接映射方式下，主存地址包括主存字塊標號、字塊地址和字塊內地址3部分，其中字塊地址和字塊內地址與cache地址相同，故主存字塊標號有18-11=7位，主存地址如下：

③ 四路組相聯，說明cache分為4個組，此時cache地址包括：組號、字塊地址、字塊內地址三部分，

因為分為4組，故組號為2位，因為一個字塊長4位，故字塊內地址為2位，故字塊地址為11-2-2=7位，cache地址如下：

此時主存地址由三部分組成：主存字塊標記、組號、字塊內地址，

組號和字塊內地址和cache地址相同（共7+2=9位），故主存字塊標記有18-9=9位，主存地址如下：

④ 全相聯方式下，主存地址由主存字塊標記和字塊內標記組成，字塊內標記和cache地址相同，為2位，故主存字塊標記為18-2=16位，主存地址如下：