1. 先修知識(shí)
- b位的二進(jìn)制數(shù)可以表示2^b個(gè)數(shù)。
相應(yīng)的B個(gè)數(shù)需要log2(B)位來(lái)表示沈自。 - k代表2的10次方畦韭， M代筆2的20次方，G代表2的30次方
- 一個(gè)字節(jié)等于8位苗沧，一個(gè)字一般為4個(gè)字節(jié)
2. 存儲(chǔ)器模型
2.1 cpu與存儲(chǔ)器的關(guān)系
經(jīng)典的馮諾依曼模型將計(jì)算機(jī)分為運(yùn)算器、存儲(chǔ)器炭晒、控制器待逞、輸入和輸出。cpu分為運(yùn)算器和控制器网严，cpu需要從內(nèi)存中讀取數(shù)據(jù)识樱。
2.2 cpu與內(nèi)存的連接
cpu與內(nèi)存的連接通過(guò)數(shù)據(jù)線連接，主要包括：
地址線震束，數(shù)據(jù)線怜庸，控制線。各種線的作用如下：
- 地址線傳輸?shù)刂沸畔ⅲㄒ簿褪且x取哪一個(gè)地址的數(shù)據(jù)）
- 數(shù)據(jù)線傳輸讀取出的數(shù)據(jù)
- 控制線（負(fù)責(zé)告訴內(nèi)存是讀 還是寫(xiě)）
注意:
地址線的位數(shù)決定存儲(chǔ)器可以尋址的空間垢村，b位的地址可以尋址2^b個(gè)地址割疾。
數(shù)據(jù)線的位數(shù)決定了一次可以讀取的數(shù)據(jù)量的大小。例如8根數(shù)據(jù)線嘉栓，一次可以讀取8位宏榕，也就是一個(gè)字節(jié)，32根的 就是一次可以讀取4個(gè)字節(jié)
假設(shè)地址線a根侵佃，數(shù)據(jù)線d根担扑，那么存儲(chǔ)器可以存儲(chǔ)的位數(shù)位： 2^a*d。 字節(jié)數(shù)需要除以8
**所以可以將內(nèi)存想象成二維的矩陣,然后行代表每一個(gè)地址趣钱， 列代表了這個(gè)地址的存儲(chǔ)單元每一位保存的數(shù)據(jù) **
存儲(chǔ)器模型如圖所示：
以下介紹一個(gè)真實(shí)的內(nèi)存讀過(guò)程：
- cpu控制器將內(nèi)存的地址信息放到地址線上
- 內(nèi)存將地址線映射到某一行去涌献。例如三個(gè)地址線101的將映射到內(nèi)存的第5行。
- cpu控制器將控制信號(hào)（“讀”）放到控制信號(hào)
- 此時(shí)開(kāi)始讀首有， 數(shù)據(jù)通過(guò)數(shù)據(jù)線到達(dá)cpu.
3. 緩存設(shè)計(jì)原理
3.1 緩存的初衷
- cpu和內(nèi)存速度之間的差異
- 存儲(chǔ)介質(zhì)的矛盾（速度燕垃，價(jià)格，容量）
3.2 緩存可行的原因
- 局部行原理
3.3 緩存的設(shè)計(jì)過(guò)程
下面都假設(shè)一個(gè)地址讀取一個(gè)字節(jié)的數(shù)據(jù)：也就是數(shù)據(jù)線只有8根
- 首先設(shè)計(jì)決定緩存和內(nèi)存之間移動(dòng)數(shù)據(jù)塊的大小井联。假設(shè)為B字節(jié)的數(shù)據(jù)卜壕，那么就是連續(xù)的B個(gè)地址的數(shù)據(jù)放到一個(gè)塊中去。因?yàn)榈刂肥沁B續(xù)的增長(zhǎng)的烙常，所以可以使用地址最低b=log2(B)位來(lái)代表該塊哪一個(gè)字節(jié)轴捎。
- 確定了塊的大小鹤盒，我們?cè)诳赐ㄓ镁彺娴脑O(shè)計(jì)，緩存被設(shè)計(jì)成為S組侦副，每組E行侦锯，如下圖
**注意： **這是一種通用的緩沖區(qū)的結(jié)構(gòu)，隨著M秦驯， E的變化尺碰，該結(jié)構(gòu)可以到特殊的情行。例如以下的特殊情況：1. S=1 ; 2. E=1译隘。
該通用緩存結(jié)構(gòu)的規(guī)定是：
某一內(nèi)存塊只能放到某一具體的組亲桥，但是可以放到該組E行中的任意一行。
- 現(xiàn)在我們確定了塊大小固耘，和使用物理地址的后b位確定一個(gè)塊中的哪一個(gè)字節(jié)（我們強(qiáng)調(diào)過(guò)题篷，一個(gè)地址對(duì)應(yīng)一個(gè)字節(jié)）。現(xiàn)在想像一下厅目，數(shù)據(jù)塊從內(nèi)存到緩存中的過(guò)程番枚，該過(guò)程首先要決定將數(shù)據(jù)放到相應(yīng)的那個(gè)組中去，然后才決定放到哪一行中去璧瞬。對(duì)于S組，我們需要s=log2（S）為來(lái)表示放到哪一組中去渐夸。
現(xiàn)在我們退出來(lái)嗤锉，從地址的規(guī)律的角度思考如何設(shè)計(jì)該如何決定將數(shù)據(jù)塊放到哪一個(gè)緩存組中。
下面是一個(gè)5位的地址墓塌，共可以表示32個(gè)地址瘟忱，以下是地址的遞增到末尾。我們假設(shè)一個(gè)塊保存四個(gè)字節(jié)苫幢， 也就是四個(gè)地址的數(shù)據(jù)访诱，下面我們已經(jīng)將每塊通過(guò)空行分割。同樣我們假設(shè)緩沖區(qū)的分為四組韩肝，也就是S=4触菜，所以需要兩位來(lái)表示哪一個(gè)組（緩沖區(qū)的組數(shù)是硬件設(shè)計(jì)人員決定的，當(dāng)然可以是任何的組數(shù)哀峻，但是一般是2的冪次方個(gè)涡相。）
我們通過(guò)下面的地址可以很清晰的看出，
每個(gè)塊的后兩位的十進(jìn)制就是0-3剩蟀，確實(shí)可以用來(lái)標(biāo)注一個(gè)塊中的第幾個(gè)字節(jié)催蝗，其實(shí)這個(gè)是因?yàn)榈刂肥沁B續(xù)增加，且低位先變化育特，這個(gè)和十進(jìn)制的遞增是一樣的丙号。
比較每一塊的第一個(gè)地址的中間的兩個(gè)數(shù)， 其也在遞增，取值也是0-3犬缨，然后同一塊內(nèi)的是相同的喳魏，所以使用這兩個(gè)數(shù)作為組號(hào)是可行的。
第一塊和第五塊的數(shù)據(jù)中間數(shù)字會(huì)被隱射到同一個(gè)組內(nèi)遍尺，因?yàn)橹虚g的位的數(shù)字是相同的截酷，這時(shí)就需要高位來(lái)區(qū)分。第一塊的高位為0乾戏，第五塊的高位為1迂苛， 高位也被稱為標(biāo)記。 為什么標(biāo)記一定能保證唯一的確定一個(gè)數(shù)據(jù)塊呢鼓择？ 首先因?yàn)榈刂肥沁B續(xù)增加的三幻，沒(méi)有重復(fù)；當(dāng)中間的組號(hào)再次循環(huán)到某一組號(hào)時(shí)呐能，地址會(huì)向前進(jìn)位念搬，所以標(biāo)記位會(huì)不同。
標(biāo)記的位數(shù)：地址的位數(shù) - 塊偏移的位數(shù) - 組的位數(shù)
注意： 我們是先確定塊的大小摆出，進(jìn)而得到塊偏移的位數(shù)
然后由組數(shù)朗徊，確定組的位數(shù)
最后才是有上述的關(guān)系 得到 標(biāo)記的位數(shù)。
標(biāo)記 組號(hào) 塊偏移
(1)
0 00 00
0 00 01
0 00 10
0 00 11
0 01 00
0 01 01
0 01 10
0 01 11
0 10 00
0 10 01
0 10 10
0 10 11
0 11 00
0 11 01
0 11 10
0 11 11
（5）
1 00 00
1 00 01
1 00 10
1 00 11
1 01 00
1 01 01
1 01 10
1 01 11
1 10 00
1 10 01
1 10 10
1 10 11
1 11 00
1 11 01
1 11 10
1 11 11
- 現(xiàn)在我們已經(jīng)知道放到哪一組中去偎漫，下面需要知道放到哪一行中去爷恳，因?yàn)橥ㄓ镁彌_區(qū)約定，放到該組E行中的任意一行象踊，所以當(dāng)該組中有空閑的空間時(shí)温亲，就直接存放就行了。
問(wèn)題： 如何判斷一個(gè)緩沖區(qū)有效（即存放有數(shù)據(jù)）杯矩？
這就是緩沖區(qū)中有效位的作用,該位為1表示有效栈虚，0表示無(wú)效。
所以只需遍歷該組內(nèi)所有行史隆，若有行中的有效位為0魂务，則將數(shù)據(jù)放到該行即可 - 上面我們討論的是有空閑的時(shí)候，那么如果沒(méi)有空閑泌射，此時(shí)需要替換算法來(lái)決定將哪一個(gè)緩沖塊踢掉头镊，替換算法, 替換算法一般有最近最少使用， FIFO等算法魄幕。
緩沖區(qū)設(shè)計(jì)完成
下面來(lái)討論數(shù)據(jù)的讀取
-
組選擇
從地址中選擇中間的s位相艇，轉(zhuǎn)換為十進(jìn)制的第i組 -
行匹配
從該組中依次匹配每一行，當(dāng)且僅當(dāng)有效位和標(biāo)志位全部一致纯陨，才表示數(shù)據(jù)塊匹配 -
字抽取
從地址最低的b位坛芽，轉(zhuǎn)化到十進(jìn)制j留储，表示數(shù)據(jù)是該塊的第j個(gè)，讀取出來(lái)咙轩。
4. 特殊的緩沖區(qū)結(jié)構(gòu)
本大節(jié)討論的是對(duì)于通用型緩存結(jié)構(gòu)的特化
4.1 直接映射緩沖區(qū)
直接映射緩沖區(qū)是指 有S組緩沖區(qū)获讳，每組只有一個(gè)緩沖塊。
4.2 組相連
組相連是指有S組活喊，每組E行丐膝，E>1.
4.3 全相連緩沖區(qū)
全相連緩沖區(qū) 是指只有一個(gè)組
