階層化存儲結構
首先，問小夥伴們一個問題：計算機的存儲結構為什麼需要進行階層化的劃分呢？
說的直接一點：就是為了減少經濟成本。如果說，CPU的價格非常便宜的話，根本就不需要記憶體了。可以把所有的記憶體容量全部都做到CPU裡面去，就可以了。但是，事實上，CPU的記憶體是很金貴的，至今為止，CPU中基本上還是一級緩存和二級緩存。三級緩存比較少見。而且，CPU中的存儲容量是非常小的，基本都是KB級别的存儲，CPU的記憶體容量也就幾KB，MB級别的CPU記憶體也是比較少見的。是以，出于經濟成本的考慮，計算機中的存儲結構是按照層次進行劃分的。
為了能夠讓小夥伴們更加清晰的了解階層化存儲結構，我們先來看一張圖。
由上圖，可以看出：
（1）階層化的存儲結構可以分為：CPU、Cache（高速緩存）、主存（記憶體）、外存（輔存）。
（2）從上往下，速度越來越慢，容量越來越大。
局部性原理是階層化存儲結構的支撐。
局部性原理
一個編寫良好的計算機程式常常具有良好的局部性。也就是說。它們傾向于引用臨近于其他最近引用過的資料項的資料項，或者最近引用過的資料項本身。這彙總傾向性，就被稱為局部性原理，這是一個持久的概念，對硬體和軟體系統的設計和性能都有着極大的影響。
之是以有這個規律，很多人認為原因是：程式的指令大部分時間是順序執行的，而且程式的集合，如數組等各種資料結構是連續存放的。
局部性原理講的是：在一段時間内，整個程式的執行僅限于程式的某一部分，相應地，程式通路的存儲空間也局限于某個記憶體區域。主要分為兩類：
- 時間局部性：如果程式中的某條指令一旦執行，則不久之後該指令可能再次被執行；如果某資料被通路，則不久之後該資料可能再次被通路。
- 空間局部性：是指一旦程式通路了某個存儲單元，則不久之後，其附近的存儲單元也将被通路。
Cache
針對Cache相關的技術，我們主要來聊聊Cache的概念和映像相關的技術。
Cache-概念
這裡的Cache表示的是高速緩沖，在計算機的存儲體系系統中，Cache是除寄存器外通路速度最快的層次。使用Cache改善系統性能的依據是程式的局部性原理 。
如果以h代表對Cache的通路命中率，t1表示Cache的周期時間，t2表示主存儲器的周期時間，以讀操作為例，使用“Cache+主存儲器”的系統的平均周期為t3，則可以得出如下運算公式。
t3 = h * t1 + (1 - h) * t2 其中。(1 - h)又稱為失效率，也就是未命中率。
Cache-映像
Cache的映像分為三種，分别是：直接相聯映像、全相聯映像、組相聯映像。
- 直接相聯映像：硬體電路比較簡單，但沖突率最高。
- 全相連映像：電路難于設計和實作，隻适用于小容量的Cache，沖突率比較低。
- 組相聯映像：直接相聯與全相聯的折中。
位址映像是将主存與Cache的存儲空間劃分為若幹大小相同的頁（或稱為塊）。
例如，一台計算機的主存容量為1GB，劃分為2048頁，每頁512KB；Cache的容量為8MB，劃分為16頁，每頁512KB。接下來，我們由此來詳細圖解直接相聯映像、全相聯映像群組相聯映像。
直接相聯映像
我們可以畫一組圖來表示Cache的直接映像。首先，我們先來簡單畫一個主存标記、Cache頁号和頁内位址的示意圖。如下所示。
如上圖所示，主存标記為7位，Cache頁号為4位，頁内位址為19位。
記錄主存區号的示意圖如下所示。
有了上面兩張圖的基礎後，我們再來看直接相聯映像的示意圖如下所示。
這裡，我們将容量為1GB的主存劃分成2048頁，總共127個區，每頁的容量為512KB。将容量為8MB的Cache劃分為16頁，每頁容量為512KB。
所謂直接相聯映像是指Cache中的0頁隻能存儲主存中0頁的内容，這裡主存中0頁指的是每個區的0頁，比如上圖中的0區的0頁，1區的16頁，127區的2032頁等。
在直接相聯映像中，隻需要記錄主存标記、Cache頁号和頁内位址就能夠快速的找到主存中的資料。
使用直接相聯映像有個缺點：那就是如果Cache中的0頁，存儲了主存中0區0頁的内容時，如果此時需要存儲主存1區中的16頁内容，就隻能将主存0區中0頁的内容從Cache的0頁中清除，然後将主存1區中16頁的内容存儲到Cache中的0頁内。沖突率比較高。細心的小夥伴會發現：這其實是違背局部性原理的。
直接相聯映像通路速度最快，但沖突率最高。
全相連映像
我們先來看下全相聯映像的主存頁标記和頁内位址的示意圖，如下所示。
此時，使用11位來辨別主存頁标記，使用19位來辨別頁内位址。
使用全相連映像需要記錄主存與Cache的對應關系，如下圖所示。
接下來，我們來看看全相連映像的示意圖，如下所示。
從圖中可以看出，Cache中的任何一個也，都可以存儲主存中的任何一個頁。
使用全相連映像通路速度最慢，沖突率最低。
組相聯映像
組相聯映像本質上是直接相聯映像和全相聯映像的折中。同樣的，我們先來看組相連映像的存儲示意圖。
此時，在組相連映像中，Cache組号使用3位表示，組内頁号使用1位表示，頁内位址使用19位表示。其中，3位的Cache組号，1位的組内頁号和前面的7位構成了主存頁标記；3位的Cache組号，1位的組内頁号和19号的頁内位址構成了Cache位址。
接下來，我們再來看看主存與Cache的對應關系，如下圖所示。
組相連的映像示意圖如下所示。
由上圖可知，在組相連映像中，主存的組與Cache的組是直接相聯映像關聯，而在組内則是通過全相聯映像來通路和存儲資料。們來一起聊聊計算機中的階層化存儲結構。