1、第三章第三章 存儲系統(tǒng)存儲系統(tǒng) 存儲器概述存儲器概述主存儲器的基本構(gòu)造和操作主存儲器的基本構(gòu)造和操作 主存儲器組織主存儲器組織 高速緩沖存儲器高速緩沖存儲器Cache Cache 高速存儲器高速存儲器半導體存儲器芯片半導體存儲器芯片虛擬存儲器虛擬存儲器3.5 Cache3.5 Cache存儲器存儲器3.5.1 3.5.1 多級存儲體系結(jié)構(gòu)多級存儲體系結(jié)構(gòu)3.5.2 Cache3.5.2 Cache工作原理工作原理3.5.3 3.5.3 主存與主存與CacheCache的地址映射和地址變換的地址映射和地址變換3.5.4 Cache3.5.4 Cache的替換策略及寫操作策略的替換策略及寫操作策略

2、中央處理器中央處理器主存主存外存外存cachecacheCPUCPUM1M1M2M3M3輔助輔助硬件硬件輔助輔助軟硬件軟硬件3.5.1 3.5.1 多級存儲體系結(jié)構(gòu)多級存儲體系結(jié)構(gòu)為解決存儲容量、存取速度和價格之間的矛盾為解決存儲容量、存取速度和價格之間的矛盾,通常通常將各種不同存儲容量、不同存取速度的存儲器將各種不同存儲容量、不同存取速度的存儲器,按一按一定的體系結(jié)構(gòu)組織起來定的體系結(jié)構(gòu)組織起來,形成一個統(tǒng)一整體形成一個統(tǒng)一整體.典型的三級存儲系統(tǒng)典型的三級存儲系統(tǒng): :圖圖3.25 三級存儲系統(tǒng)示意圖三級存儲系統(tǒng)示意圖 Cache-Cache-主存層次主存層次 CacheCache一般由一

3、般由SRAMSRAM構(gòu)成構(gòu)成, ,容量小容量小, ,存取速度快，依存取速度快，依據(jù)程序局部性原理據(jù)程序局部性原理, ,存放的是主存中當前最需要執(zhí)存放的是主存中當前最需要執(zhí)行的信息副本行的信息副本. . 目的：主存容量不足的問題目的：主存容量不足的問題. 利用輔助硬件和操作系統(tǒng)中的存儲管理軟件利用輔助硬件和操作系統(tǒng)中的存儲管理軟件, ,將將 主存和輔存構(gòu)成一個整體主存和輔存構(gòu)成一個整體. .目的：解決目的：解決CPUCPU和主存速度不匹配的問題和主存速度不匹配的問題. . 主存主存- -輔存層次輔存層次 總體效果：存取速度接近總體效果：存取速度接近Cache,Cache,而存儲容量接而存儲容量接

4、 近于輔存近于輔存, ,整體價格也較合理整體價格也較合理. .3.5 Cache3.5 Cache存儲器存儲器3.5.1 3.5.1 多級存儲體系結(jié)構(gòu)多級存儲體系結(jié)構(gòu)3.5.2 Cache3.5.2 Cache工作原理工作原理3.5.3 3.5.3 主存與主存與CacheCache的地址映射和地址變換的地址映射和地址變換3.5.4 Cache3.5.4 Cache的替換策略及寫操作策略的替換策略及寫操作策略 3.5.2 Cache3.5.2 Cache工作原理工作原理CacheCache的工作機制的工作機制 CacheCache工作是以工作是以程序訪問的局部性原理程序訪問的局部性原理為基礎的為

5、基礎的, ,即即, , 一個程序的指令大都順序存放、順序執(zhí)行一個程序的指令大都順序存放、順序執(zhí)行, ,與程序與程序相關(guān)的數(shù)據(jù)在存儲器中也相對集中相關(guān)的數(shù)據(jù)在存儲器中也相對集中. .所以程序運行時所以程序運行時,尤其有循環(huán)程序段和子程序段時尤其有循環(huán)程序段和子程序段時,在在較短時間區(qū)間內(nèi)較短時間區(qū)間內(nèi),常會對局部范圍的存儲器頻繁訪問常會對局部范圍的存儲器頻繁訪問,而此范圍之外的地址訪問甚少而此范圍之外的地址訪問甚少.這種現(xiàn)象稱為這種現(xiàn)象稱為程序訪程序訪問的局部性問的局部性.把局部范圍的主存內(nèi)容從主存放到一個高速小容量把局部范圍的主存內(nèi)容從主存放到一個高速小容量存儲器中存儲器中, ,使使CPUCP

6、U在這一段時間內(nèi)直接訪問它在這一段時間內(nèi)直接訪問它, ,以減少以減少或不去訪問慢速的主存或不去訪問慢速的主存 , ,程序運行速度將明顯提高程序運行速度將明顯提高. . 2. Cache2. Cache工作原理工作原理例例: :某機主存容量為某機主存容量為1MB, Cache1MB, Cache容量為容量為8KB,8KB,若以字節(jié)編若以字節(jié)編址址, ,每每512B512B為一塊為一塊, ,則主存有則主存有20482048塊塊, Cache, Cache有有1616塊塊. .塊塊0 000000H 00001H. 001FFH塊塊20472047FFE00HFFE01HFFFFFH主存主存塊塊0

7、00000H 0001H.01FFH塊塊15151E00H1E01H1FFFH Cache Cache 塊的概念塊的概念一般將主存和一般將主存和CacheCache的存儲空間分塊的存儲空間分塊, ,每塊大小相同每塊大小相同, ,包括相同數(shù)量的存儲單元包括相同數(shù)量的存儲單元. . Cache Cache構(gòu)成及工作過程構(gòu)成及工作過程CPUCPU主主存存主存主存地址地址寄存寄存器器MARMAR主存主存CacheCache地址變換地址變換機構(gòu)機構(gòu)( (塊表塊表) )CacheCache存儲器存儲器CacheCache地址地址寄存器寄存器替換控制部件替換控制部件ABDB單字寬單字寬多多字字寬寬不不命命中

8、中命命中中(塊塊) CacheCache包括包括CacheCache存儲器及存儲器及相應控制部件相應控制部件, ,全部由全部由硬件組成硬件組成, ,速度快速度快, ,對所有程序員均透明對所有程序員均透明. .CARCAR CacheCache命中率命中率 設設NcNc為為Cache Cache 完成存取的總次數(shù)完成存取的總次數(shù),Nm,Nm為主存完為主存完成存取的總次數(shù)成存取的總次數(shù), ,h h為命中率為命中率, ,則有則有: : 設設r=tm/tcr=tm/tc表示主存慢于表示主存慢于CacheCache的倍率的倍率, ,e e表示訪問表示訪問效率效率, ,則有則有: : 高速緩存命中率高速緩

9、存命中率:CPU:CPU訪存時訪存時, ,信息恰巧在信息恰巧在CacheCache中的概率中的概率. .h=Nc/(Nc+Nm)h=Nc/(Nc+Nm) 若若tc tc表示命中時的表示命中時的CacheCache訪問時間訪問時間,tm,tm表示未命中表示未命中時的主存訪問時間時的主存訪問時間,1-h,1-h表示未命中率表示未命中率, ,則則Cache /Cache /主存系主存系統(tǒng)的統(tǒng)的平均訪問時間平均訪問時間tata為為: :ta=htc+(1-h)tmta=htc+(1-h)tm e=tc/ta=tc/htc+(1-h)tm=1/h+(1-h)r=1/r+(1-r)he=tc/ta=tc/

10、htc+(1-h)tm=1/h+(1-h)r=1/r+(1-r)h例：例：CPUCPU執(zhí)行一段程序時執(zhí)行一段程序時,Cache,Cache完成存取的次完成存取的次數(shù)數(shù)19001900次次, ,主存完成存取的次數(shù)為主存完成存取的次數(shù)為100100次次, ,已知已知CacheCache的存取周期為的存取周期為1ns,1ns,主存存取周期為主存存取周期為5ns,5ns,求求Cache/Cache/主存系統(tǒng)的效率和平均訪問時間主存系統(tǒng)的效率和平均訪問時間. .解：解：h=Nc/(Nc+Nm)=1900/(1900+100) h=Nc/(Nc+Nm)=1900/(1900+100) =0.95=0.95

11、 r=tm/tc=5ns/1ns=5r=tm/tc=5ns/1ns=5 e=1/r+(1-r)h=1/5+(1-5)X0.95=83.3% e=1/r+(1-r)h=1/5+(1-5)X0.95=83.3% ta=tc/e=1ns/0.833=1.2ns ta=tc/e=1ns/0.833=1.2ns例例: :某計算機的存儲系統(tǒng)由某計算機的存儲系統(tǒng)由CacheCache和主存組成和主存組成, ,某程某程序執(zhí)行過程中訪存序執(zhí)行過程中訪存10001000次次, ,其中訪問其中訪問CacheCache缺失缺失( (未命中未命中)50)50次次, ,則則CacheCache的命中率是的命中率是( ).

12、( ). A.5% B.9.5% C.50% D.95% A.5% B.9.5% C.50% D.95% 影響影響 CacheCache命中率的因素命中率的因素 Cache的大小的大小 容量相對較大的容量相對較大的Cache,命中率也相應提高命中率也相應提高,但容量但容量太大太大,成本會變得不合理成本會變得不合理. 程序的特點程序的特點 遵循局部性原理的程序在運行時遵循局部性原理的程序在運行時Cache的命中率的命中率也會很高也會很高,相反相反,在程序中頻繁且無規(guī)則地使用在程序中頻繁且無規(guī)則地使用Call或或JMP命令命令,將嚴重影響基于將嚴重影響基于Cache的系統(tǒng)性能的系統(tǒng)性能. Cach

13、e的組織結(jié)構(gòu)的組織結(jié)構(gòu) Cache組織結(jié)構(gòu)的好壞組織結(jié)構(gòu)的好壞,對命中率也會產(chǎn)生較大影對命中率也會產(chǎn)生較大影響響. Cache的組織結(jié)構(gòu)有三種類型的組織結(jié)構(gòu)有三種類型:全相聯(lián)映射、直接映全相聯(lián)映射、直接映射和組相聯(lián)映射射和組相聯(lián)映射. 3.5 Cache3.5 Cache存儲器存儲器3.5.1 3.5.1 多級存儲體系結(jié)構(gòu)多級存儲體系結(jié)構(gòu)3.5.2 Cache3.5.2 Cache工作原理工作原理3.5.3 3.5.3 主存與主存與CacheCache的地址映射和地址變換的地址映射和地址變換3.5.4 Cache3.5.4 Cache的替換策略及寫操作策略的替換策略及寫操作策略 3.5.3 3

14、.5.3 主存與主存與CacheCache的地址映射和地址變換的地址映射和地址變換1. 1. 全相聯(lián)映射全相聯(lián)映射: :允許主存中的每一個塊可以映射到允許主存中的每一個塊可以映射到CacheCache的任何一塊位置上的任何一塊位置上. .映射過程如下圖所示映射過程如下圖所示: : 一一. .全相聯(lián)映射及其地址變換全相聯(lián)映射及其地址變換l 二者密切相關(guān)二者密切相關(guān)- -地址變換由地址映射方式?jīng)Q定地址變換由地址映射方式?jīng)Q定. .主存主存-Cache-Cache地址變換地址變換: :程序運行時程序運行時, ,根據(jù)地址映射把主根據(jù)地址映射把主存地址變換成存地址變換成CacheCache地址地址. .

15、主存主存-Cache-Cache地址映射地址映射(mapping):(mapping):把存放在主存中的把存放在主存中的程序按某種規(guī)則裝入程序按某種規(guī)則裝入CacheCache中中, ,并依此建立主存地址與并依此建立主存地址與CacheCache地址的對應關(guān)系地址的對應關(guān)系, ,即塊表即塊表. . 塊表塊表存放數(shù)據(jù)或指令在內(nèi)存中所在單元地址的存儲存放數(shù)據(jù)或指令在內(nèi)存中所在單元地址的存儲器器, ,用于判斷用于判斷CacheCache命中以及實現(xiàn)地址映射命中以及實現(xiàn)地址映射, ,其字數(shù)等于其字數(shù)等于CacheCache的塊數(shù)的塊數(shù). .塊塊0 塊塊1塊塊15塊塊0塊塊1塊塊2047CacheCac

16、he主存主存全相聯(lián)映射全相聯(lián)映射 2.2.全相聯(lián)映射方式下的地址變換全相聯(lián)映射方式下的地址變換主存塊號主存塊號塊內(nèi)地址塊內(nèi)地址 (1) (1) 主存地址格式主存地址格式: : (標志字段標志字段)圖圖3.26 全相聯(lián)映射示意圖全相聯(lián)映射示意圖l例例: :某機主存容量為某機主存容量為1MB, Cache1MB, Cache容量為容量為8KB8KB，若以字，若以字節(jié)編址，每節(jié)編址，每512B512B為一塊為一塊, ,則主存有則主存有20482048塊塊, Cache, Cache有有1616塊。塊。v主存地址格式：主存地址格式： 0000 0000 000 0000 0000 000 0 0000

17、 00000 0000 0000 0000 0000 000 0000 0000 000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1塊號塊號(0塊塊)塊內(nèi)存儲單元塊內(nèi)存儲單元(0-511)(0-511)塊號塊號(1塊塊) 塊內(nèi)存儲單元塊內(nèi)存儲單元( 0-511)( 0-511)0000 0000 001 0000 0000 001 0 0000 00000 0000 00000000 0000 001 0000 0000 001 1 1 1 1 1 1 1 1 11 1 1 1 1 1 1 1 1塊號塊號(2047塊塊)塊內(nèi)存儲單元塊內(nèi)存儲單元(0-511)(0-5

18、11)1 1 1 1 1 1 1 1 111 1 1 1 1 1 1 1 1 111 0 0000 00000 0000 00001 1 1 1 1 1 1 1 111 1 1 1 1 1 1 1 1 111 1 1 1 1 1 1 1 1 11 1 1 1 1 1 1 1 1CacheCache塊號塊號塊內(nèi)地址塊內(nèi)地址 主存塊號轉(zhuǎn)換為主存塊號轉(zhuǎn)換為CacheCache塊號塊號, ,塊內(nèi)地址不變塊內(nèi)地址不變(3) (3) 地址變換地址變換( (將主存地址轉(zhuǎn)換為將主存地址轉(zhuǎn)換為CacheCache地址地址): ): (2) Cache(2) Cache地址格式地址格式: :塊號塊號(0塊塊)塊內(nèi)

19、存儲單元塊內(nèi)存儲單元(0-511)(0-511)塊號塊號(1塊塊) 塊內(nèi)存儲單元塊內(nèi)存儲單元( 0-511)( 0-511) 0 00 1 0 00 1 0 0000 00000 0000 0000 0 00 1 0 00 1 1 1 1 1 1 1 1 1 11 1 1 1 1 1 1 1 1塊號塊號(15塊塊)塊內(nèi)存儲單元塊內(nèi)存儲單元(0-511)(0-511) 1 1 1 1 1 1 1 1 0 0000 00000 0000 0000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 11 1 1 1 1 1 1 1 1 0 00 0 0 0000 0000 0 00 0

20、 0 0000 0000 0 00 0 1 1 1 1 1 1 1 1 10 00 0 1 1 1 1 1 1 1 1 1主存塊號主存塊號B(B(標志字段標志字段) )塊內(nèi)地址塊內(nèi)地址WWCacheCache塊號塊號b b塊內(nèi)地址塊內(nèi)地址ww主存塊號主存塊號B BCacheCache塊號塊號b bB Bb b比較比較命中命中MARMARCARCAR 圖圖3.27 3.27 全相聯(lián)映射的地址變換全相聯(lián)映射的地址變換塊表塊表(塊表容塊表容量的計算：量的計算：字數(shù)等于字數(shù)等于高緩塊數(shù)，高緩塊數(shù)，字長由主字長由主存塊數(shù)和存塊數(shù)和高緩塊數(shù)高緩塊數(shù)決定決定)不命中則不命中則訪問主存訪問主存注意注意: :在

21、全相聯(lián)映射中在全相聯(lián)映射中, ,主存塊號作為主存塊號作為識別是否命中的標志識別是否命中的標志, ,標志位的長度由主存塊數(shù)決定標志位的長度由主存塊數(shù)決定. .字塊字塊0 0字塊字塊1 1字塊字塊2 2C C -1 -1標記標記標記標記標記標記設設CacheCache有有2 2C C-1 -1塊塊, ,主存有主存有2 2mm-1 -1塊塊, ,即即CacheCache塊地址有塊地址有c c位位, ,主存塊地址有主存塊地址有mm位位. .字塊字塊0 0字塊字塊1 1字塊字塊2 2C C -1 -1字塊字塊2 2mm -1 -1主存地址格式：主存地址格式：主存字塊標記主存字塊標記 塊內(nèi)地址塊內(nèi)地址mm

22、位位圖圖3.28 3.28 全相聯(lián)映射的另一種常見圖解全相聯(lián)映射的另一種常見圖解 3.3.全相聯(lián)映射的優(yōu)缺點全相聯(lián)映射的優(yōu)缺點 i= j mod m (m(m為為CacheCache中總塊數(shù)中總塊數(shù)) ) 映射規(guī)則映射規(guī)則: :主存中任何一組的第主存中任何一組的第i i塊只能放入塊只能放入Cache Cache 的的第第i i塊塊. . 主存第主存第j j塊塊( (大排塊數(shù)大排塊數(shù)) )和和CacheCache第第i i塊有如下函數(shù)關(guān)塊有如下函數(shù)關(guān)系系: :1. 1.直接映射直接映射: :首先首先, ,主存在分塊的基礎上分組主存在分塊的基礎上分組, ,每組大小與每組大小與CacheCache的

23、大小相同。的大小相同。二二. . 直接映射及其地址變換直接映射及其地址變換 (2) (2) 缺點缺點: :塊表的查找時間長塊表的查找時間長, ,速度慢速度慢. .(1) 1) 優(yōu)點優(yōu)點: :塊沖突概率最低塊沖突概率最低, ,只有當只有當CacheCache中全部裝滿后中全部裝滿后, , 才有可能出現(xiàn)塊沖突才有可能出現(xiàn)塊沖突, ,塊分配靈活；塊分配靈活；其中其中,商為主存第商為主存第j塊所在主存的組數(shù)塊所在主存的組數(shù),余數(shù)為在該組的塊數(shù)余數(shù)為在該組的塊數(shù).塊塊0塊塊1塊塊15CacheCache.0 0組組1 1組組127127組組塊塊 0 塊塊 1 塊塊15 塊塊16塊塊17 塊塊31 塊塊2

24、047主存主存塊塊2032塊塊2033圖圖3.29 直接映射示意直接映射示意圖圖2.2.直接聯(lián)映射方式下的地址變換直接聯(lián)映射方式下的地址變換 CacheCache塊號塊號 組組號號塊內(nèi)地址塊內(nèi)地址CacheCache塊號塊號塊內(nèi)地址塊內(nèi)地址組內(nèi)塊號組內(nèi)塊號 (2) Cache(2) Cache地址格式地址格式: :(1) (1) 主存地址格式主存地址格式: :塊號塊號(0塊塊)塊內(nèi)存儲單元塊內(nèi)存儲單元(0-511)(0-511)塊號塊號(1塊塊) 塊內(nèi)存儲單元塊內(nèi)存儲單元( 0-511)( 0-511)0000 0000000 0000 0010 001 0 0000 00000 0000 0

25、0000000 0000000 0000 0010 001 1 1 1 1 1 1 1 1 11 1 1 1 1 1 1 1 1塊號塊號(2047塊塊)塊內(nèi)存儲單元塊內(nèi)存儲單元(0-511)(0-511)1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1111 111 0 0000 00000 0000 00001 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1111 111 1 1 1 1 1 1 1 1 11 1 1 1 1 1 1 1 1主存地址格式：主存地址格式：0000 0000000 0000 0 000000 0 0000 00000 0000 00000

26、000 0000000 0000 0 000000 1 1 1 1 1 1 1 1 11 1 1 1 1 1 1 1 1組號組號(0-127)組內(nèi)塊號組內(nèi)塊號(0-15)(3) (3) 地址變換地址變換( (將主存地址轉(zhuǎn)換為將主存地址轉(zhuǎn)換為CacheCache地址地址): ):CacheCache塊號塊號b b組號組號G G( (標志字段標志字段) )MARMARCache塊號塊號b塊內(nèi)地址塊內(nèi)地址w w CAR CAR命中命中不命中不命中訪問主存訪問主存塊內(nèi)地址塊內(nèi)地址W W比較比較組號組號GCache地址地址根據(jù)根據(jù)CARCAR的內(nèi)容訪問的內(nèi)容訪問CacheCache 主存地址中的主存地址

27、中的“組內(nèi)塊號組內(nèi)塊號(Cache(Cache塊號塊號)+)+塊內(nèi)地址塊內(nèi)地址”= Cache= Cache地址地址注意：在直接映射中注意：在直接映射中, ,主存組號主存組號作為識別是否命中的標志，標作為識別是否命中的標志，標志位的長度由主存組數(shù)決定志位的長度由主存組數(shù)決定. .3.3.直接映射的優(yōu)缺點：直接映射的優(yōu)缺點：塊內(nèi)地址塊內(nèi)地址(9位位) 組內(nèi)塊號組內(nèi)塊號(4位位)組號組號(7位位) CacheCache地址格式地址格式塊內(nèi)地址塊內(nèi)地址(9位位) 塊號塊號(4位位)解解:(1) :(1) 主存地址格式主存地址格式 (1) (1) 分別寫出主存地址格式和分別寫出主存地址格式和Cache

28、Cache地址格式地址格式; ; (2) (2) 畫出直接映射及地址變換圖畫出直接映射及地址變換圖; ; (3) (3)主存地址為主存地址為0022AH0022AH的單元在的單元在CacheCache中什么位置中什么位置? ?例題例題: :某機主存容量為某機主存容量為1MB, Cache1MB, Cache容量為容量為8KB8KB，每塊，每塊512B,512B,如果采用直接映射如果采用直接映射, ,請回答請回答: :(2)(2)缺點缺點:Cache:Cache的空間利用率低的空間利用率低, ,塊沖突較多塊沖突較多, ,命中率也低命中率也低. .(1)(1)優(yōu)點優(yōu)點: :硬件實現(xiàn)簡單硬件實現(xiàn)簡單

29、, ,成本低成本低. .塊塊0塊塊1塊塊15Cache.0組組1組組塊塊 0 塊塊 1 塊塊15 塊塊16塊塊17 塊塊31 塊塊2047塊塊2032塊塊2033 127組組主存主存7位位4位位9位位組號組號G組內(nèi)塊號組內(nèi)塊號b塊內(nèi)地址塊內(nèi)地址主存地址主存地址比較比較組號組號不命不命中中,訪訪問主問主存存Cache地址地址01b15(2) (2) 直接映射及地址變換示意圖直接映射及地址變換示意圖命中命中,MARCAR4位位9位位則根據(jù)則根據(jù)CAR的內(nèi)容訪問的內(nèi)容訪問Cache地址映射地址映射地址變換地址變換 (3) 主存地址為主存地址為0022AH的單元在的單元在Cache中什么中什么位置位置

30、組組(0組組)組內(nèi)塊號組內(nèi)塊號(1塊塊)塊內(nèi)地址塊內(nèi)地址(42字字)另外一種求法另外一種求法: 0022AH=(0000 0000 0010 0010 1010)2因為主存第因為主存第j塊和塊和Cache第第i塊有如下函數(shù)關(guān)系塊有如下函數(shù)關(guān)系: i= j mod m (m為為Cache中總塊數(shù)中總塊數(shù))這里這里,j=1,m=16,所以所以i=1 mod 16=1例例: :設一個設一個CacheCache中有中有8 8個塊個塊, ,訪問主存進行讀操作的塊地址訪問主存進行讀操作的塊地址序列為序列為2222、2626、2222、2626、1616、4 4、1616、18,18,求每次訪問后求每次訪問

31、后CacheCache中的內(nèi)容中的內(nèi)容( (設設CacheCache初始為空初始為空). ).解：解：地址地址命中與否命中與否地址轉(zhuǎn)換關(guān)系地址轉(zhuǎn)換關(guān)系 不命中不命中 22 MOD 8=622 MOD 8=6 不命中不命中 26 MOD 8=226 MOD 8=2 22 22 命中命中 22 MOD 8=6 22 MOD 8=6 命中命中 26 MOD 8=226 MOD 8=216 16 不命中不命中 16 MOD 8=016 MOD 8=04 4 不命中不命中 4 MOD 8=4 4 MOD 8=4 16 16 命中命中 16 MOD 8=016 MOD 8=0 18 18 不命中不命中 1

32、8 MOD 8=2 18 MOD 8=2 直接映象下直接映象下CacheCache訪問情況訪問情況 直接映象的塊分配情況直接映象的塊分配情況 訪問順序訪問順序 1 2 3 4 5 6 7 81 2 3 4 5 6 7 8 地址地址 22 26 22 26 16 4 16 1822 26 22 26 16 4 16 18塊分配塊分配 情況情況 2222操作操作狀態(tài)狀態(tài)調(diào)調(diào)進進22222626調(diào)調(diào)進進22222626命命中中22222626命命中中222226261616調(diào)調(diào)進進22224 416162626調(diào)調(diào)進進2222161626264 4命命中中2222161618184 4替替換換練習練

33、習1. 1. 設有一個設有一個CacheCache的容量為的容量為2K2K字字, ,每塊每塊1616字字, ,在直接映在直接映象方式下象方式下, ,求求: :(1)(1)該該CacheCache可容納多少個塊可容納多少個塊? ?(2)(2)如果主存的容量為如果主存的容量為256K256K字字, ,則有多少個塊則有多少個塊? ?(3)(3)主存的地址格式主存的地址格式? Cache? Cache的地址格式的地址格式? ?(4) (4) 主存中的第主存中的第032AB032AB單元映象到單元映象到CacheCache中哪一塊中哪一塊? ?練習練習2. 2. 設計算機的存儲器為設計算機的存儲器為64

34、K64K1616位位, ,直接地址映射直接地址映射的的CacheCache容量為容量為1K1K字字, ,每塊每塊4 4字字, ,問問: : (1) (1) 主存中地址的標志字段、塊號和塊內(nèi)地址字段分主存中地址的標志字段、塊號和塊內(nèi)地址字段分別有多少位？別有多少位？ （2 2）CacheCache中可裝入多少塊數(shù)據(jù)？中可裝入多少塊數(shù)據(jù)？三三. . 組相聯(lián)映射組相聯(lián)映射及其地址變換及其地址變換n n路組相聯(lián)路組相聯(lián): :每組中有每組中有n n塊塊. .有有全相聯(lián)映射全相聯(lián)映射: :主存第主存第g g組第組第i i塊可映射到塊可映射到CacheCache第第i i組中任組中任一塊的位置一塊的位置.

35、. 有直接映射有直接映射: :主存第主存第g g組第組第i i塊只能映射到塊只能映射到CacheCache第第i i組組. . 1. 1.組相聯(lián)映射組相聯(lián)映射:Cache:Cache分成大小相等的組分成大小相等的組, ,各組再分成大各組再分成大小相等的塊小相等的塊. . 主存在分塊的基礎上分組主存在分塊的基礎上分組, ,每組塊數(shù)等于每組塊數(shù)等于Cache Cache 組數(shù)組數(shù). . 映射規(guī)則映射規(guī)則:Cahe:Cahe分為分為mm組組, ,每組有每組有n n塊塊, ,則有以下關(guān)系則有以下關(guān)系: : i=j mod m i=j mod m 其中其中,i ,i為為CacheCache組號組號,j

36、,j為主存塊號為主存塊號( (大排大排). ).商為主存第商為主存第j j塊塊所在組數(shù)所在組數(shù), ,余數(shù)為該組所在塊數(shù)余數(shù)為該組所在塊數(shù). . 塊塊0 0塊塊1 1塊塊2 2塊塊3 3塊塊1414塊塊1515 0 0組組1 1組組7 7組組CacheCache主存主存塊塊0 0塊塊1 1塊塊2 2塊塊3 3塊塊7 7塊塊8 8塊塊1515塊塊1616塊塊1717塊塊20472047圖圖3.30 3.30 組相聯(lián)映射示意圖組相聯(lián)映射示意圖同上例同上例, ,采用采用2 2路組相聯(lián)路組相聯(lián) 塊塊9 90 0組組1 1組組 2.2.組相聯(lián)映射方式下的地址變換組相聯(lián)映射方式下的地址變換塊內(nèi)地址塊內(nèi)地址

37、( (CacheCache組號組號) )(1) (1) 主存地址格式主存地址格式: :(主存字塊標記主存字塊標記) (2) Cache(2) Cache地址格式地址格式: :塊內(nèi)地址塊內(nèi)地址組號組號組內(nèi)塊號組內(nèi)塊號 組號組號組內(nèi)塊號組內(nèi)塊號(3) (3) 地址變換地址變換( (將主存地址轉(zhuǎn)換為將主存地址轉(zhuǎn)換為CacheCache地址地址): ):塊內(nèi)地址塊內(nèi)地址組號組號組內(nèi)塊號組內(nèi)塊號塊內(nèi)地址塊內(nèi)地址 ( (CacheCache組號組號) )(主存字塊標記主存字塊標記) 組號組號組內(nèi)塊號組內(nèi)塊號主存字塊標記主存字塊標記組號組號G G塊內(nèi)地址塊內(nèi)地址WWMARMAR組號組號g g組內(nèi)塊號組內(nèi)塊號

38、b b塊內(nèi)地址塊內(nèi)地址wwCARCAR比較比較不命中不命中訪問主存訪問主存命中命中主存字塊標記主存字塊標記CacheCache組內(nèi)塊號組內(nèi)塊號b b訪問訪問CacheCache圖圖3.31 3.31 組相聯(lián)映射的地址變換示意圖組相聯(lián)映射的地址變換示意圖塊表塊表v 例例(2009):(2009):某計算機的某計算機的CacheCache共有共有1616塊塊, ,采采用用2 2路組相聯(lián)路組相聯(lián)( (即每組即每組2 2塊塊). ).每個主存塊大每個主存塊大小為小為3232字節(jié)字節(jié), ,按字節(jié)編址按字節(jié)編址. .主存主存129129號單元號單元所在主存應裝入到得所在主存應裝入到得CacheCache組

39、號是組號是( ).( ).vA. 0 B.2 C.4 D.6A. 0 B.2 C.4 D.6v 例例: :在下列因素中在下列因素中, ,與與CacheCache的命中率無關(guān)的命中率無關(guān)的是的是( ).( ).v A. Cache A. Cache塊的大小塊的大小v B. CacheB. Cache的容量的容量v C. C. 主存的存取時間主存的存取時間v 例：假設主存容量為例：假設主存容量為512K512K1616位位,Cache,Cache容量容量為為409640961616位位, ,塊長為塊長為4 4個個1616位的字位的字, ,訪存地址訪存地址為字地址為字地址. .v(1)(1)在直接映

40、射方式下在直接映射方式下, ,設計主存地址格式設計主存地址格式. .v(2)(2)在全相聯(lián)映射方式下在全相聯(lián)映射方式下, ,設計主存地址格式設計主存地址格式. .v(3)(3)在在2 2路組相聯(lián)映射方式下路組相聯(lián)映射方式下, ,設計主存地址格設計主存地址格式式. .v 解解:(1):(1)在直接映射方式下在直接映射方式下,Cache,Cache分分4096/4=24096/4=21010塊塊, ,主存分主存分2 21919/4=2/4=21717塊塊, ,主存分主存分2 21919/2/21212=2=27 7組組. .v 故主存地址格式故主存地址格式: :主存組數(shù)主存組數(shù)(7(7位位) )組

41、內(nèi)塊數(shù)組內(nèi)塊數(shù)(10(10位位) )塊內(nèi)地址塊內(nèi)地址(2(2位位) )v(2)(2)在全相聯(lián)方式下在全相聯(lián)方式下, ,CacheCache分分4096/4=24096/4=21010塊塊, ,主存分主存分2 21919/4=2/4=21717塊塊. .v故主存地址格式故主存地址格式: :主存塊數(shù)主存塊數(shù)(17(17位位) )塊內(nèi)地址塊內(nèi)地址(2(2位位) ) (3)(3)在組相聯(lián)映射方式下在組相聯(lián)映射方式下, , CacheCache分分4096/4=24096/4=21010塊塊,2,2塊一組塊一組,Cache,Cache分分2 21010/2=2/2=29 9組組; ;主主存分存分2 21

42、919/4=2/4=21717塊塊, ,每組分每組分2 29 9塊塊, ,主存分主存分2 21717/2/29 9=2=28 8組組. .v故主存地址格式故主存地址格式: :塊內(nèi)地址塊內(nèi)地址 ( (CacheCache組號組號) )(主存字塊標記主存字塊標記)組號組號(8位位)組內(nèi)塊號組內(nèi)塊號(9位位) (2位位)練習練習1. 1. 設有一個設有一個CacheCache的容量為的容量為2K2K字字, ,每塊每塊1616字字, ,在直接在直接映象方式下映象方式下, ,求求: :(1)(1)該該CacheCache可容納多少個塊可容納多少個塊? ?(2)(2)如果主存的容量為如果主存的容量為256

43、K256K字字, ,則有多少個塊則有多少個塊? ?(3)(3)主存的地址格式主存的地址格式? Cache? Cache的地址格式的地址格式? ?(4) (4) 主存中的第主存中的第032ABH032ABH單元映象到單元映象到CacheCache中哪一塊中哪一塊? ? 解解:(1):(1) CacheCache可容納的塊數(shù)為可容納的塊數(shù)為:2K/16=2:2K/16=27 7=128(=128(塊塊) )(2) (2) 主存的可容納的塊數(shù)為主存的可容納的塊數(shù)為: 256K/16=2: 256K/16=21414( (塊塊) ) (3) (3) 主存地址格式為主存地址格式為: :塊內(nèi)地址塊內(nèi)地址(

44、4位位) 組內(nèi)塊號組內(nèi)塊號(7位位)組號組號(7位位) CacheCache地址格式為地址格式為: :塊內(nèi)地址塊內(nèi)地址(4位位) 組內(nèi)塊號組內(nèi)塊號(7位位)(4) 主存中的主存中的032ABH單元單元:032ABH=(0000 0011 0010 1010 1011)2 6 6組組 42 42塊塊1111字字另外一種求法另外一種求法: :因為主存第因為主存第j j塊和塊和CacheCache第第i i塊有如下函數(shù)關(guān)系塊有如下函數(shù)關(guān)系: : i= j mod m (m i= j mod m (m為為CacheCache中總塊數(shù)中總塊數(shù)) )這里這里,j=2,j=29 9+2+28 8+2+25

45、5+2+23 3+2+21 1=810,m=128,=810,m=128,所以所以i=1 mod m=810 mod 128=42i=1 mod m=810 mod 128=42 3.5 Cache3.5 Cache存儲器存儲器3.5.1 3.5.1 多級存儲體系結(jié)構(gòu)多級存儲體系結(jié)構(gòu)3.5.2 Cache3.5.2 Cache工作原理工作原理3.5.3 3.5.3 主存與主存與CacheCache的地址映射和地址變換的地址映射和地址變換3.5.4 Cache3.5.4 Cache的替換策略及寫操作策略的替換策略及寫操作策略3.5.4 3.5.4 CacheCache的替換策略及寫操作策略的替換

46、策略及寫操作策略LRU-Least Recently UsedLRU-Least Recently UsedFIFO-First In First OutFIFO-First In First OutRANDRAND 常用替換算法常用替換算法: : 注意注意: :只有全相聯(lián)和組相聯(lián)的高速緩存中有替換策略只有全相聯(lián)和組相聯(lián)的高速緩存中有替換策略問題問題. . 替換策略替換策略(replacement policy): Cache(replacement policy): Cache地址變換中地址變換中一旦發(fā)生不命中一旦發(fā)生不命中, ,需將主存中一個新塊調(diào)入需將主存中一個新塊調(diào)入Cache,Cac

47、he,如如果此時發(fā)生塊沖突果此時發(fā)生塊沖突, , 決定從決定從CacheCache中選擇哪一個數(shù)據(jù)中選擇哪一個數(shù)據(jù)塊塊, ,并將其從并將其從CacheCache中移去中移去, ,將新的數(shù)據(jù)塊寫入的方法將新的數(shù)據(jù)塊寫入的方法. . 一一. Cache. Cache的替換策略的替換策略 1. RAND1. RAND算法算法 特點特點: :符合局部性原理符合局部性原理, ,命中率較高命中率較高. . 方法方法: :根據(jù)局部性原理選擇近期用的最少的數(shù)據(jù)塊根據(jù)局部性原理選擇近期用的最少的數(shù)據(jù)塊作為替換的塊作為替換的塊. .具體做法具體做法: :為每一塊設置一個計數(shù)器為每一塊設置一個計數(shù)器, ,當當某一塊

48、命中時某一塊命中時, ,其計數(shù)器清其計數(shù)器清0,0,其它各塊的計數(shù)器增其它各塊的計數(shù)器增1, 1,當當需要替換時需要替換時, ,將計數(shù)值大的塊替換出將計數(shù)值大的塊替換出. .3. 3. LRULRU算法算法 特點特點: :較簡單較簡單, ,但沒有體現(xiàn)程序局部性規(guī)律但沒有體現(xiàn)程序局部性規(guī)律, ,不能提不能提高高CacheCache命中率命中率. .方法方法: :選擇最早調(diào)入選擇最早調(diào)入CacheCache的塊進行替換的塊進行替換. . 2. 2. FIFOFIFO算法算法 方法方法: :隨機地確定替換塊隨機地確定替換塊. .特點特點: :容易實現(xiàn)容易實現(xiàn), ,執(zhí)行速度快執(zhí)行速度快, ,但沒有體現(xiàn)

49、程序局部性規(guī)律但沒有體現(xiàn)程序局部性規(guī)律, ,不能提高不能提高CacheCache命中率命中率. .二、二、CacheCache的寫操作策略的寫操作策略 CacheCache內(nèi)容是主存部分內(nèi)容的副本內(nèi)容是主存部分內(nèi)容的副本, ,在命中的情在命中的情況下況下, ,如果如果CPUCPU對對CacheCache寫入寫入, ,改變了改變了Cache (dirty block)Cache (dirty block)的內(nèi)容的內(nèi)容, ,如何保證主存內(nèi)容與如何保證主存內(nèi)容與CacheCache內(nèi)容一致內(nèi)容一致. .缺點缺點: :當當CPUCPU向主存寫操作時向主存寫操作時, Cache, Cache無高速緩沖無

50、高速緩沖功能功能, ,降低了降低了CacheCache的功效的功效. . 優(yōu)點優(yōu)點: :寫主存與寫寫主存與寫CacheCache同步同步. . 1. 1.直達法直達法(write through)(write through)(通過式寫入通過式寫入): ):每次寫入每次寫入CacheCache時同時寫入主存時同時寫入主存, ,使主存與使主存與CacheCache相關(guān)塊內(nèi)容始終保持一相關(guān)塊內(nèi)容始終保持一致致. . 2. 2. 寫回法寫回法(write back)(write back)(標志交換方式標志交換方式): Cache): Cache中每一塊各作一個標記中每一塊各作一個標記( (清清未修

51、改過未修改過; ;濁濁修修改過改過), ),命中需將信息寫入主存時命中需將信息寫入主存時, ,暫只寫入暫只寫入 Cache, Cache, 并不寫入主存并不寫入主存, , 只有當該塊需要從只有當該塊需要從CacheCache中替換出來時中替換出來時, ,若其標記為若其標記為”濁濁”, ,再一次性寫入再一次性寫入主存主存. . 缺點缺點: :存在存在CacheCache與主存數(shù)據(jù)不一致的隱患與主存數(shù)據(jù)不一致的隱患. .優(yōu)點優(yōu)點: :減少對主存的寫操作次數(shù)減少對主存的寫操作次數(shù), , 工作速度較快工作速度較快. .作業(yè)作業(yè)1: 1:某一某一Cache-Cache-主存采用組相聯(lián)的方法進行地址轉(zhuǎn)換主存采用組相聯(lián)的方法進行地址轉(zhuǎn)換.