[[380118]]

作者個人研發(fā)的在高并發(fā)場景下，提供的簡單、穩(wěn)定、可擴展的延遲消息隊列框架，具有精準的定時任務(wù)和延遲隊列處理功能。自開源半年多以來，已成功為十幾家中小型企業(yè)提供了精準定時調(diào)度方案，經(jīng)受住了生產(chǎn)環(huán)境的考驗。為使更多童鞋受益，現(xiàn)給出開源框架地址：https://github.com/sunshinelyz/mykit-delay

寫在前面

擼代碼只是程序員的一項最基本的技能，除此之外，還有很多知識需要程序員掌握?！境绦騿T進階系列】專題，旨在分享程序員想要進一步提升自我，突破發(fā)展瓶頸的一系列技術(shù)。今天，我們來一起聊聊計算機中的層次化存儲結(jié)構(gòu)。

文章已收錄到：

https://github.com/sunshinelyz/technology-binghe

https://gitee.com/binghe001/technology-binghe

層次化存儲結(jié)構(gòu)

首先，問小伙伴們一個問題：計算機的存儲結(jié)構(gòu)為什么需要進行層次化的劃分呢?

說的直接一點：就是為了減少經(jīng)濟成本。如果說，CPU的價格非常便宜的話，根本就不需要內(nèi)存了。可以把所有的內(nèi)存容量全部都做到CPU里面去，就可以了。但是，事實上，CPU的內(nèi)存是很金貴的，至今為止，CPU中基本上還是一級緩存和二級緩存。三級緩存比較少見。而且，CPU中的存儲容量是非常小的，基本都是KB級別的存儲，CPU的內(nèi)存容量也就幾KB，MB級別的CPU內(nèi)存也是比較少見的。所以，出于經(jīng)濟成本的考慮，計算機中的存儲結(jié)構(gòu)是按照層次進行劃分的。

為了能夠讓小伙伴們更加清晰的理解層次化存儲結(jié)構(gòu)，我們先來看一張圖。

由上圖，可以看出：

(1)層次化的存儲結(jié)構(gòu)可以分為：CPU、Cache(高速緩存)、主存(內(nèi)存)、外存(輔存)。

(2)從上往下，速度越來越慢，容量越來越大。

局部性原理是層次化存儲結(jié)構(gòu)的支撐。

局部性原理

一個編寫良好的計算機程序常常具有良好的局部性。也就是說。它們傾向于引用臨近于其他最近引用過的數(shù)據(jù)項的數(shù)據(jù)項，或者最近引用過的數(shù)據(jù)項本身。這匯總傾向性，就被稱為局部性原理，這是一個持久的概念，對硬件和軟件系統(tǒng)的設(shè)計和性能都有著極大的影響。

之所以有這個規(guī)律，很多人認為原因是：程序的指令大部分時間是順序執(zhí)行的，而且程序的集合，如數(shù)組等各種數(shù)據(jù)結(jié)構(gòu)是連續(xù)存放的。

局部性原理講的是：在一段時間內(nèi)，整個程序的執(zhí)行僅限于程序的某一部分，相應(yīng)地，程序訪問的存儲空間也局限于某個內(nèi)存區(qū)域。主要分為兩類：

• 時間局部性：如果程序中的某條指令一旦執(zhí)行，則不久之后該指令可能再次被執(zhí)行;如果某數(shù)據(jù)被訪問，則不久之后該數(shù)據(jù)可能再次被訪問。
• 空間局部性：是指一旦程序訪問了某個存儲單元，則不久之后，其附近的存儲單元也將被訪問。

Cache

針對Cache相關(guān)的技術(shù)，我們主要來聊聊Cache的概念和映像相關(guān)的技術(shù)。

Cache-概念

這里的Cache表示的是高速緩沖，在計算機的存儲體系系統(tǒng)中，Cache是除寄存器外訪問速度最快的層次。使用Cache改善系統(tǒng)性能的依據(jù)是程序的局部性原理 。

如果以h代表對Cache的訪問命中率，t1表示Cache的周期時間，t2表示主存儲器的周期時間，以讀操作為例，使用“Cache+主存儲器”的系統(tǒng)的平均周期為t3，則可以得出如下運算公式。

t3 = h * t1 + (1 - h) * t2  

其中。(1 - h)又稱為失效率，也就是未命中率。

Cache-映像

Cache的映像分為三種，分別是：直接相聯(lián)映像、全相聯(lián)映像、組相聯(lián)映像。

• 直接相聯(lián)映像：硬件電路比較簡單，但沖突率最高。
• 全相連映像：電路難于設(shè)計和實現(xiàn)，只適用于小容量的Cache，沖突率比較低。
• 組相聯(lián)映像：直接相聯(lián)與全相聯(lián)的折中。

地址映像是將主存與Cache的存儲空間劃分為若干大小相同的頁(或稱為塊)。

例如，一臺計算機的主存容量為1GB，劃分為2048頁，每頁512KB;Cache的容量為8MB，劃分為16頁，每頁512KB。接下來，我們由此來詳細圖解直接相聯(lián)映像、全相聯(lián)映像和組相聯(lián)映像。

直接相聯(lián)映像

我們可以畫一組圖來表示Cache的直接映像。首先，我們先來簡單畫一個主存標記、Cache頁號和頁內(nèi)地址的示意圖。如下所示。

如上圖所示，主存標記為7位，Cache頁號為4位，頁內(nèi)地址為19位。

記錄主存區(qū)號的示意圖如下所示。

有了上面兩張圖的基礎(chǔ)后，我們再來看直接相聯(lián)映像的示意圖如下所示。

這里，我們將容量為1GB的主存劃分成2048頁，總共127個區(qū)，每頁的容量為512KB。將容量為8MB的Cache劃分為16頁，每頁容量為512KB。

所謂直接相聯(lián)映像是指Cache中的0頁只能存儲主存中0頁的內(nèi)容，這里主存中0頁指的是每個區(qū)的0頁，比如上圖中的0區(qū)的0頁，1區(qū)的16頁，127區(qū)的2032頁等。

在直接相聯(lián)映像中，只需要記錄主存標記、Cache頁號和頁內(nèi)地址就能夠快速的找到主存中的數(shù)據(jù)。

使用直接相聯(lián)映像有個缺點：那就是如果Cache中的0頁，存儲了主存中0區(qū)0頁的內(nèi)容時，如果此時需要存儲主存1區(qū)中的16頁內(nèi)容，就只能將主存0區(qū)中0頁的內(nèi)容從Cache的0頁中清除，然后將主存1區(qū)中16頁的內(nèi)容存儲到Cache中的0頁內(nèi)。沖突率比較高。細心的小伙伴會發(fā)現(xiàn)：這其實是違背局部性原理的。

直接相聯(lián)映像訪問速度最快，但沖突率最高。

全相連映像

我們先來看下全相聯(lián)映像的主存頁標記和頁內(nèi)地址的示意圖，如下所示。

此時，使用11位來標識主存頁標記，使用19位來標識頁內(nèi)地址。

使用全相連映像需要記錄主存與Cache的對應(yīng)關(guān)系，如下圖所示。

接下來，我們來看看全相連映像的示意圖，如下所示。

從圖中可以看出，Cache中的任何一個也，都可以存儲主存中的任何一個頁。

使用全相連映像訪問速度最慢，沖突率最低。

組相聯(lián)映像

組相聯(lián)映像本質(zhì)上是直接相聯(lián)映像和全相聯(lián)映像的折中。同樣的，我們先來看組相連映像的存儲示意圖。

此時，在組相連映像中，Cache組號使用3位表示，組內(nèi)頁號使用1位表示，頁內(nèi)地址使用19位表示。其中，3位的Cache組號，1位的組內(nèi)頁號和前面的7位構(gòu)成了主存頁標記;3位的Cache組號，1位的組內(nèi)頁號和19號的頁內(nèi)地址構(gòu)成了Cache地址。

接下來，我們再來看看主存與Cache的對應(yīng)關(guān)系，如下圖所示。

組相連的映像示意圖如下所示。

由上圖可知，在組相連映像中，主存的組與Cache的組是組相聯(lián)映像關(guān)系，而在組內(nèi)則是通過直接相聯(lián)映像來訪問和存儲數(shù)據(jù)。

本文轉(zhuǎn)載自微信公眾號「冰河技術(shù)」，可以通過以下二維碼關(guān)注。轉(zhuǎn)載本文請聯(lián)系冰河技術(shù)公眾號。