課件第5章使用1

1、 5.1存儲系統(tǒng)原理存儲系統(tǒng)原理 5.2虛擬存儲器虛擬存儲器5.2高速緩沖存儲器高速緩沖存儲器Cache 5.3降低降低Cache失效率的方法失效率的方法5.4減少減少Cache失效開銷失效開銷5.5減少命中時間減少命中時間5.6主存主存 第五章第五章 存儲層次存儲層次( (系統(tǒng)）系統(tǒng)） 5.1 5.1 存儲系統(tǒng)原理存儲系統(tǒng)原理5.1.1 存儲系統(tǒng)的定義存儲系統(tǒng)的定義5.1.2 存儲系統(tǒng)的層次結構存儲系統(tǒng)的層次結構 5.1.1 5.1.1 存儲系統(tǒng)的定義存儲系統(tǒng)的定義 現(xiàn)代的計算機以存儲器為中心?，F(xiàn)代的計算機以存儲器為中心。 在一臺計算機中，通常有多種存儲器。在一臺計算機中，通常有多種存儲器。

2、 種類：主存儲器、種類：主存儲器、CacheCache、通用寄存器、緩沖、通用寄存器、緩沖存存 儲器、磁盤存儲器、磁帶存儲器、光盤存儲器儲器、磁盤存儲器、磁帶存儲器、光盤存儲器等。等。 材料工藝：材料工藝：ECLECL、TTLTTL、MOSMOS、磁表面、激光，、磁表面、激光，SRAMSRAM，DRAMDRAM。 訪問方式：隨機訪問、直接譯碼、先進先出、訪問方式：隨機訪問、直接譯碼、先進先出、 相聯(lián)訪問、相聯(lián)訪問、 塊傳送、文件組。塊傳送、文件組。 主存儲器的性能指標1、存儲容量：指存儲器可容納的二進制信息量，描述存儲容量的單位是字節(jié)或位。量化單位：1K210 1M220 1G230 1T24

3、0存儲器芯片的存儲容量存儲單元個數(shù)每個存儲單元的位數(shù) 兆兆千兆千兆太太 主存儲器的性能指標2、存儲速度：由以下3個方法來衡量。存取時間（Memory Access Time-TA）：指啟動一次存儲器操作到完成該操作所需的全部時間。存取時間愈短，其性能愈好。通常存取時間用納秒（ns109s）為單位。存儲周期（Memory Cycle Time-TC）：指存儲器進行連續(xù)兩次獨立的存儲器操作所需的最小間隔時間。通常存取周期TC大于存取時間TA ，即TCTA。存儲器帶寬：是單位時間里存儲器所能存取的最大信息量，存儲器帶寬的計量單位通常是位/秒（bps）或字節(jié)/秒，它是衡量數(shù)據(jù)傳輸速率的重要技術指標。

4、主存儲器的性能指標3、存儲器的價格：用每位的價格來衡量。設存儲器容量為S，總價格為C，則位價為C/S(分/位)。它不僅包含了存儲元件的價格，還包括為該存儲器操作服務的外圍電路的價格。4、可靠性：指存儲器正常工作（正確存?。┑男阅堋?、功耗：存儲器工作的耗電量。存儲容量、速度和價格的關系：速度快的存儲器往往價格較高，容量也較小。容量、速度和價格三個指標是相互制約的。 任何計算機系統(tǒng)中，對存儲器的要求可概括為“大容量、高速度、低成本”。一般來說，要求存儲器速度很高，存儲容量就不可能很大，價格也不可能很低；如果要求存儲器容量很大，存儲速度就不可能很高，成本也不能很低，三者之間是相互矛盾的。為了能較好

5、地滿足上述三個方面的要求，有效的辦法是采用由不同介質形成的存儲器構成存儲器的層次結構（存儲體系/系統(tǒng)）。 最簡單的二級存儲層次如下圖所示： 二級存儲層次二級存儲層次 這個整個存儲系統(tǒng)由主存儲器和輔助存儲器兩級構成。主存儲器一般由半導體存儲器構成（DRAM），它速度快，但容量較小，成本較高，通常用來存放程序的“活躍部分”，直接與CPU交換信息；輔助存儲器一般由磁表面存儲器構成，它速度慢，但容量大、成本低，通常用來存放程序的“不活躍部分”，即暫時不執(zhí)行的程序或暫時不用的數(shù)據(jù)，需要時，將程序或數(shù)據(jù)、信息以塊為單位從輔助存儲器調入主存儲器中。 那么，什么時候應將輔存中的信息塊調入主那么，什么時候應將輔

6、存中的信息塊調入主存，什么時間將主存中已用完的信息塊調入存，什么時間將主存中已用完的信息塊調入輔存，所有這些操作都是由圖的上方所示的輔存，所有這些操作都是由圖的上方所示的輔助軟硬件來完成，只有這樣，由主、輔存輔助軟硬件來完成，只有這樣，由主、輔存構成的兩級存儲層次才成為一個完整的存儲構成的兩級存儲層次才成為一個完整的存儲系統(tǒng)，對系統(tǒng)，對CPUCPU來說，訪問存儲器的速度是主存來說，訪問存儲器的速度是主存儲器的，而存儲器的容量和成本是輔助存儲儲器的，而存儲器的容量和成本是輔助存儲器的，較好地滿足上述三個方面的要求。器的，較好地滿足上述三個方面的要求。 由于半導體存儲器構成的主存儲器的訪問速度與C

7、PU相比還是有一定差距，希望能進一步提高存儲系統(tǒng)的等效速度，有效的辦法是在CPU和主存儲器之間增設一級高速緩沖存儲器cache(SRAM)，如圖所示。 三級存儲層次三級存儲層次 在三級存儲層次中，高速緩沖存儲器的訪問速度可與CPU相匹配，但是其容量比主存儲器更小，任何時候cache中的信息是主存儲器中一部分信息的副本。當CPU需要訪問主存儲器時，根據(jù)給定的主存儲器地址迅速判定該地址中的信息是否已進入cache中，如果已進入cache中，則經(jīng)地址變換后立即訪問cache，如果cache不命中，則直接訪問主存儲器。顯然，顯然，cachecache命中率越高越好。為提高訪問命中率越高越好。為提高訪問

8、cachecache的速度，需要在的速度，需要在cachecache與主存儲器之間與主存儲器之間設置一塊輔助硬件。由它來完成主存與設置一塊輔助硬件。由它來完成主存與cachecache之間的地址變換功能。這樣就構成了之間的地址變換功能。這樣就構成了“cache“cache一主存一輔存一主存一輔存”三級存儲層次。在理想情況三級存儲層次。在理想情況下，訪問主存儲器的速度決定于下，訪問主存儲器的速度決定于cachecache，而其，而其容量和成本則決定于輔存，它能更好地滿足容量和成本則決定于輔存，它能更好地滿足“高速度、大容量、低成本高速度、大容量、低成本”三方面的要求。三方面的要求。 組成存儲系統(tǒng)

9、的關鍵：組成存儲系統(tǒng)的關鍵：把速度、容量和價格不同的多個物理存儲器組把速度、容量和價格不同的多個物理存儲器組織成一個存儲器，這個存儲器的速度最快，存織成一個存儲器，這個存儲器的速度最快，存儲容量最大，單位容量的價格最便宜。儲容量最大，單位容量的價格最便宜。1. 1. 存儲層次（系統(tǒng)）的定義存儲層次（系統(tǒng)）的定義 兩個或兩個以上速度、容量和價格各兩個或兩個以上速度、容量和價格各不相同的存儲器用硬件、軟件、或軟件與不相同的存儲器用硬件、軟件、或軟件與硬件相結合的方法連接起來成為一個存儲硬件相結合的方法連接起來成為一個存儲系統(tǒng)。這個存儲系統(tǒng)對應用程序員是透明系統(tǒng)。這個存儲系統(tǒng)對應用程序員是透明的，并

10、且，從應用程序員看，它是一個存的，并且，從應用程序員看，它是一個存儲器，這個存儲器的速度接近速度最快的儲器，這個存儲器的速度接近速度最快的那個存儲器，存儲容量與容量最大的那個那個存儲器，存儲容量與容量最大的那個存儲器相等，單位容量的價格接近最便宜存儲器相等，單位容量的價格接近最便宜的那個存儲器。的那個存儲器。 虛擬存儲器系統(tǒng)：對應用程序員透明虛擬存儲器系統(tǒng)：對應用程序員透明, ,對對系系 統(tǒng)程序員不透明。統(tǒng)程序員不透明。 Cache Cache存儲系統(tǒng)：對系統(tǒng)程序員以上均透存儲系統(tǒng)：對系統(tǒng)程序員以上均透明明 從從外外部部看看 T Tm mi in n（T T1 1，T T2 2，T Tn n）

11、 ，用用存存儲儲周周期期表表示示 S Sm ma ax x（S S1 1，S S2 2，S Sn n） ，用用M MB B或或G GB B表表示示 C Cm mi in n（C C1 1，C C2 2，C Cn n） ，用用每每位位的的價價格格表表示示1 1( (T T1 1, ,S S1 1, ,C C1 1) )2 2( (T T2 2, ,S S2 2, ,C C2 2) )n n( (T Tn n, ,S Sn n, ,C Cn n) )由多個存儲器構成的存儲系統(tǒng)由多個存儲器構成的存儲系統(tǒng) 存儲體系的構成依賴程序局部性原理。存儲體系的構成依賴程序局部性原理。程序的局部性原理程序的局部性

12、原理程序執(zhí)行時所訪問的存儲器地址分布不是隨程序執(zhí)行時所訪問的存儲器地址分布不是隨機機的，而是相對地簇聚。的，而是相對地簇聚。程序的時間局部性程序的時間局部性程序即將用到的信息很可能就是目前正在使程序即將用到的信息很可能就是目前正在使用的信息。用的信息。程序的空間局部性程序的空間局部性程序即將用到的信息很可能與目前正在使用程序即將用到的信息很可能與目前正在使用的信息的信息在空間上相鄰或者臨近。在空間上相鄰或者臨近。 系系 統(tǒng)統(tǒng) 程程 序序 員員 看看 ： 速速 度度 接接 近近 C Ca ac ch he e 的的 速速 度度 ， 存存 儲儲 容容 量量 是是 主主 存存 的的 容容 量量 ，

13、每每 位位 價價 格格 接接 近近 主主 存存 儲儲 器器 。C Ca ac ch he e 存存 儲儲 系系 統(tǒng)統(tǒng)C Ca ac ch he e主主 存存 儲儲 器器 在一般計算機系統(tǒng)中，有兩種存儲系統(tǒng)：在一般計算機系統(tǒng)中，有兩種存儲系統(tǒng)：CacheCache存儲系統(tǒng)：由存儲系統(tǒng)：由CacheCache和主存儲器構成和主存儲器構成 主要目的：提高存儲器速度主要目的：提高存儲器速度輔助硬件輔助硬件 應應用用程程序序員員看看： 速速度度接接近近主主存存儲儲器器的的速速度度， 存存儲儲容容量量是是虛虛擬擬地地址址空空間間， 每每位位價價格格接接近近磁磁盤盤存存儲儲器器。虛虛擬擬存存儲儲系系統(tǒng)統(tǒng)主主

14、存存儲儲器器磁磁盤盤存存儲儲器器虛擬存儲系統(tǒng)：由主存儲器和硬盤構成虛擬存儲系統(tǒng)：由主存儲器和硬盤構成 主要目的：擴大存儲器容量主要目的：擴大存儲器容量輔助軟硬件輔助軟硬件 從原理上看，主存從原理上看，主存外存層次和外存層次和cachecache主存層次有主存層次有很多相似之處，它們采用的地址變換及映射方法和替換很多相似之處，它們采用的地址變換及映射方法和替換策略，從原理上看是相同的，且都基于程序局部性原理。策略，從原理上看是相同的，且都基于程序局部性原理。它們遵循的原則又是它們遵循的原則又是: : (1) (1)把程序中最近常用的部分駐留在高速的存儲器中。把程序中最近常用的部分駐留在高速的存儲

15、器中。 (2) (2)一旦這部分變得不常用了，把它們送回到低速的存儲一旦這部分變得不常用了，把它們送回到低速的存儲器中。器中。 (3) (3)這種換入換出是由硬件或操作系統(tǒng)完成的，對用戶是這種換入換出是由硬件或操作系統(tǒng)完成的，對用戶是透明的。透明的。 (4) (4)力圖使存儲系統(tǒng)的性能接近高速存儲器，價格接近低力圖使存儲系統(tǒng)的性能接近高速存儲器，價格接近低速存儲器。速存儲器。 然而，兩種存儲系統(tǒng)中的設備性能有所不同，管理方案的實施細節(jié)也有差異，所以虛擬存儲系統(tǒng)中不能直接照搬cache中的技術。兩種存儲系統(tǒng)的主要區(qū)別在于：主存的存取時間是cache存取時間的510倍，而磁盤的存取時間是主存存取時

16、間的上千倍，因而未命中時系統(tǒng)的相對性能損失有很大的不同。具體說，在虛擬存儲器中未命中的性能損失要遠大于cache系統(tǒng)中未命中的損失。Cache和主存速度的對比：和主存速度的對比：測試用的是測試用的是Core 2 Duo E6320,A-DATA DDRII 800 存儲層次存儲層次CPU對第二級的對第二級的訪問方式訪問方式比較項目比較項目目的目的存儲管理實現(xiàn)存儲管理實現(xiàn) 訪問速度的比值訪問速度的比值(第一級和第二級第一級和第二級)典型的塊典型的塊(頁頁)大小大小失效時失效時CPU是否切換是否切換“Cache 主存主存”層次層次“主存輔存主存輔存”層次層次為了彌補主存速度的不足為了彌補主存速度的

17、不足 為了彌補主存容量的不足為了彌補主存容量的不足主要由專用硬件實現(xiàn)主要由專用硬件實現(xiàn)主要由軟件實現(xiàn)主要由軟件實現(xiàn)幾比一幾比一幾百比一幾百比一幾十個字節(jié)幾十個字節(jié)幾百到幾千個字節(jié)幾百到幾千個字節(jié)可直接訪問可直接訪問均通過第一級均通過第一級不切換不切換切換到其他進程切換到其他進程“Cache“Cache主存主存”與與“主存輔存主存輔存”層次的區(qū)別層次的區(qū)別2.2.存儲系統(tǒng)的容量存儲系統(tǒng)的容量要求：要求： * *提供盡可能大的地址空間提供盡可能大的地址空間 * *能夠隨機訪問能夠隨機訪問方法有兩種：方法有兩種：CacheCache存儲系統(tǒng)存儲系統(tǒng)-只對系統(tǒng)中存儲容量最只對系統(tǒng)中存儲容量最大的那個存

18、儲器進行編址，其他存儲器大的那個存儲器進行編址，其他存儲器只在內部編址或不編址。也就是：只對只在內部編址或不編址。也就是：只對主存編址，主存編址，cachecache采用相聯(lián)管理方式。采用相聯(lián)管理方式。虛擬存儲系統(tǒng)虛擬存儲系統(tǒng)-另外設計一個容量很大的另外設計一個容量很大的邏輯地址空間，把相關存儲器都映射這邏輯地址空間，把相關存儲器都映射這個地址空間中。個地址空間中。 3.3.存儲系統(tǒng)的價格存儲系統(tǒng)的價格計算公式：計算公式：當當S2S2S1S1時，時，CC2CC2 （S S，C C，T T）由由兩兩個個存存儲儲器器構構成成的的存存儲儲系系統(tǒng)統(tǒng)M1（S1，C1，T1）M2（S2，C2，T2）CC

19、SC SSS1122124. 4. 存儲系統(tǒng)的速度存儲系統(tǒng)的速度命中率定義：在命中率定義：在M1M1存儲器中訪問到的存儲器中訪問到的概率概率 其中：其中： N1 N1：是對：是對M1M1存儲器的訪問存儲器的訪問次數(shù)次數(shù) N2 N2：是對：是對M2M2存儲器的訪問存儲器的訪問次數(shù)次數(shù)訪問周期與命中率的關系：訪問周期與命中率的關系： T THT1HT1(1(1H)T2H)T2 當命中率當命中率H1H1時，時，TT1TT1失效率（不命中率）失效率（不命中率）F=1-HF=1-HHNNN112 平均訪問時間平均訪問時間TATA TA TA HTA1 HTA1（1 1H H）（）（TA1TA1TMTM）

20、 TA1 TA1（1 1H H）TMTM 或或 TA TA TA1 TA1FTMFTM分兩種情況來考慮分兩種情況來考慮CPUCPU的一次訪存：的一次訪存：當命中時，訪問時間即為當命中時，訪問時間即為TA1TA1（命中時間）（命中時間）當不命中時，情況比較復雜。當不命中時，情況比較復雜。 不命中時的訪問時間為：不命中時的訪問時間為：TA2TA2TBTBTA1TA1TA1TA1TM TM TM TM TA2TA2TBTBTM TM （失效開銷）：從向（失效開銷）：從向M2M2發(fā)出訪問請求到發(fā)出訪問請求到把整個數(shù)據(jù)把整個數(shù)據(jù) 塊調入塊調入M1M1中所需的時間。中所需的時間。TBTB：傳送一個信息塊所

21、需的時間。：傳送一個信息塊所需的時間。 存儲系統(tǒng)的訪問效率：存儲系統(tǒng)的訪問效率：訪問效率主要與命中率和兩級存儲器的速度之訪問效率主要與命中率和兩級存儲器的速度之比有關比有關例例5.15.1：假設：假設T2T2T T，在命中率，在命中率H H為為0.90.9和和0.990.99兩種情況下，分別計算存儲系統(tǒng)的訪問兩種情況下，分別計算存儲系統(tǒng)的訪問效率。效率。解：解：eTTTH TH THHf HTTTT11111122121()()(,)當當H H0.90.9時，時，e1e11 1(0.9(0.95(15(10.9)0.9)0.720.72當當H H0.990.99時，時，e2e21 1(0.99

22、(0.995(15(10.99)0.99)0.960.96提高存儲系統(tǒng)速度的兩條途徑：提高存儲系統(tǒng)速度的兩條途徑：一是提高命中率一是提高命中率H H，二是兩個存儲器的速度不要相差太大二是兩個存儲器的速度不要相差太大其中：第二條有時做不到其中：第二條有時做不到( (如虛擬存儲器如虛擬存儲器) )，這，這時，只能依靠提高命中率時，只能依靠提高命中率例例5.25.2：在虛擬存儲系統(tǒng)中，兩個存儲器的速：在虛擬存儲系統(tǒng)中，兩個存儲器的速度相差特別懸殊，例如：度相差特別懸殊，例如：T2T2105 T105 T。如。如果要使訪問效率到達果要使訪問效率到達e e0.90.9，問需要有多高，問需要有多高的命中率

23、？的命中率？解：解：0.9H90000(1-H)189999.1 H89999計算得：計算得： H0.999998888877777 0.9999990 9111 05.()HH 5.1.2 5.1.2 存儲系統(tǒng)的層次結構存儲系統(tǒng)的層次結構 多個層次的存儲器：多個層次的存儲器： 第第1層：層：Register Files(寄存器堆寄存器堆) 第第2層：層： Buffers(Lookahead)(先行緩沖站先行緩沖站) 第第3層：層： Cache(高速緩沖存儲器高速緩沖存儲器) 第第4層：層： Main Memory(主存儲器主存儲器) 第第5層：層： Online Storage(聯(lián)機存儲器聯(lián)

24、機存儲器) 第第6層：層： Off-line Storage(脫機存儲器脫機存儲器)用用i表示層數(shù)，則有：工作周期表示層數(shù)，則有：工作周期TiTi+1， 存儲容量：存儲容量：SiSi+1，單位價格：，單位價格：CiCi+1 第第 1 層層 第第 2 層層 第第 3 層層 第第 4 層層 第第 5 層層 第第 6 層層CPU內內部部通通用用寄寄存存器器堆堆聯(lián)聯(lián)機機外外部部存存儲儲器器（磁磁盤盤存存儲儲器器等等）脫脫機機外外部部存存儲儲器器（磁磁帶帶，光光盤盤存存儲儲器器等等）指指令令和和數(shù)數(shù)據(jù)據(jù)緩緩沖沖棧棧C Ca ac ch he e（靜靜態(tài)態(tài)隨隨機機存存儲儲器器）SRAM）主主存存儲儲器器（

25、動動態(tài)態(tài)隨隨機機存存儲儲器器 DRAM）存存儲儲容容量量越越來來越越大大每每位位的的價價格格越越來來越越便便宜宜訪訪問問速速度度越越來來越越快快各級存儲器的主要主要性能特性各級存儲器的主要主要性能特性 CPU CPU與主存儲器的速度差距越來越大與主存儲器的速度差距越來越大 目前相差兩個數(shù)量級目前相差兩個數(shù)量級 今后今后CPUCPU與主存儲器的速度差距會更大與主存儲器的速度差距會更大存存儲儲器器層層次次 通通用用寄寄存存器器 緩緩沖沖棧棧 C Ca ac ch he e 主主存存儲儲器器 磁磁盤盤存存儲儲器器 脫脫機機存存儲儲器器 存存儲儲周周期期 1 10 0n ns s 1 10 0n ns

26、 s 1 10 06 60 0n ns s 6 60 03 30 00 0n ns s 1 10 03 30 0m ms s 2 22 20 0m mi in n 存存儲儲容容量量 5 51 12 2B B 5H*0.00 0.17 0.42 0.50 0.58 0.585. 5. 堆棧型替換算法堆棧型替換算法 定義：對任意一個程序的頁地址流作兩次主存頁面定義：對任意一個程序的頁地址流作兩次主存頁面數(shù)分配，分別分配數(shù)分配，分別分配 m m 個主存頁面和個主存頁面和 n n 個主存頁面，個主存頁面，并且有并且有 mn mn。如果在任何時刻。如果在任何時刻 t t，主存頁面數(shù)集合，主存頁面數(shù)集合

27、Bt Bt 都滿足關系：都滿足關系： Bt Bt（m m） Bt Bt（n n），），則這類算法稱為堆棧型替換算法。則這類算法稱為堆棧型替換算法。 堆棧型算法的基本特點是：堆棧型算法的基本特點是： 隨著分配給程序的主存頁面數(shù)增加，主存的命中隨著分配給程序的主存頁面數(shù)增加，主存的命中率也提高，至少不下降。率也提高，至少不下降。時時間間t t1 12 23 34 45 56 67 78 89 91 10 01 11 11 12 2實實際際頁頁地地址址流流P P1 1P P2 2P P3 3P P4 4P P1 1P P2 2P P5 5P P1 1P P2 2P P3 3P P4 4P P5 5命

28、命中中次次數(shù)數(shù)1 11 11 1* *4 44 44 4* *5 55 55 55 55 5* *5 5* *主主存存頁頁面面數(shù)數(shù)2 22 22 2* *1 11 11 1* *1 1* *1 1* *3 33 33 3N N3 33 33 33 3* *2 22 22 22 22 2* *4 44 4調調入入調調入入調調入入替替換換替替換換替替換換替替換換命命中中命命中中替替換換替替換換命命中中3 3次次1 11 11 11 11 1* *1 1* *5 55 55 55 5* *4 44 4主主存存頁頁面面數(shù)數(shù)2 22 22 22 22 2* *2 2* *1 11 11 11 1* *5

29、 5N N4 43 33 33 33 33 33 3* *2 22 22 22 2* *4 44 44 44 44 44 4* *3 33 33 3調調入入調調入入調調入入調調入入命命中中命命中中替替換換替替換換替替換換替替換換替替換換替替換換2 2次次F FI IF FO O算算法法在在主主存存頁頁面面數(shù)數(shù)增增加加時時命命中中率率反反而而下下降降5.2.5 5.2.5 提高主存命中率的方法提高主存命中率的方法影響主存命中率的主要因素：影響主存命中率的主要因素：(1)(1)程序在執(zhí)行過程中的頁地址流分布情況。程序在執(zhí)行過程中的頁地址流分布情況。(2)(2)所采用的頁面替換算法。所采用的頁面替換

30、算法。(3)(3)頁面大小。頁面大小。(4)(4)主存儲器的容量主存儲器的容量(5)(5)所采用的頁面調度算法所采用的頁面調度算法 以下，對后三個因素進行分析。以下，對后三個因素進行分析。1.1.頁面大小與命中率的關系頁面大小與命中率的關系 頁面大小為某個值時，命中率達到最大。頁面大小為某個值時，命中率達到最大。頁面大小與命中率關系的解釋：頁面大小與命中率關系的解釋： 假設假設AtAt和和At+1At+1是相鄰兩次訪問主存的邏輯地址，是相鄰兩次訪問主存的邏輯地址， d dAtAtAt+1At+1。如果如果Sp(Sp(頁面大?。?，隨著頁面大小），隨著SpSp增大，增大，At At 和和 At+1

31、 At+1在同一頁面的可能性增加，即隨著在同一頁面的可能性增加，即隨著SpSp的增大而提的增大而提高。高。如果如果SpSp，AtAt和和At+1At+1一定不在同一個頁面內。隨著一定不在同一個頁面內。隨著SpSp增大，主存頁面數(shù)減少，頁面替換更加頻繁。增大，主存頁面數(shù)減少，頁面替換更加頻繁。隨著隨著SpSp的增大而降低。的增大而降低。當Sp比較小的時候，前一種情況是主要的，隨著Sp的增大而提高。當Sp達到某一個最大值之后，后一種情況成為主要的，隨著Sp的增大而降低。當頁面增大時，造 成的浪費也要增加當頁面減小時，頁 表和頁面表在主存 儲器中所占的比例 將增加頁面大小頁面大小 SP命中率命中率1

32、S2 S2. 2. 主存容量與命中率的關系主存容量與命中率的關系 主存命中率主存命中率H H隨著分配給該程序的主存容量隨著分配給該程序的主存容量S S的增加的增加而單調上升。而單調上升。 在在S S比較小的時候，比較小的時候，H H提高得非?？臁ｋS著提高得非?？?。隨著S S的逐漸的逐漸增加，增加，H H提高的速度逐漸降低。當提高的速度逐漸降低。當S S增加到某一個值之增加到某一個值之后，后，H H幾乎不再提高。幾乎不再提高。1.0命命中中率率H 主存容量 S5. 5. 頁面調度方式與命中率的關系頁面調度方式與命中率的關系 請求式：當使用到的時候，再調入主存請求式：當使用到的時候，再調入主存 預

33、取式：在程序重新開始運行之前，把上次預取式：在程序重新開始運行之前，把上次 停止運行前一段時間內用到的頁面先調入到停止運行前一段時間內用到的頁面先調入到 主存儲器，然后才開始運行程序。主存儲器，然后才開始運行程序。 預取式的主要優(yōu)點：預取式的主要優(yōu)點： 可以避免在程序開始運行時，頻繁發(fā)生頁面可以避免在程序開始運行時，頻繁發(fā)生頁面 失效的情況。失效的情況。 預取式的主要缺點：預取式的主要缺點： 如果調入的頁面用不上，浪費了調入的時間，如果調入的頁面用不上，浪費了調入的時間， 占用了主存的資源。占用了主存的資源。5.3 5.3 高速緩沖存儲器高速緩沖存儲器5.5.1 基本工作原理基本工作原理5.5

34、.2 地址映象與變換方法地址映象與變換方法5.5.3 Cache替換算法及其實現(xiàn)替換算法及其實現(xiàn)5.5.4 Cache存儲系統(tǒng)的加速比存儲系統(tǒng)的加速比5.5.5 Cache的一致性問題的一致性問題5.5.6 Cache的預取算法的預取算法Cache 存儲系統(tǒng)與虛擬存儲系統(tǒng)的比較存儲系統(tǒng)與虛擬存儲系統(tǒng)的比較 存儲系統(tǒng)存儲系統(tǒng) Cache 存儲系統(tǒng)存儲系統(tǒng) 虛擬存儲虛擬存儲系統(tǒng)系統(tǒng) 要達到的目標要達到的目標 提高速度提高速度 擴大容量擴大容量 實現(xiàn)方法實現(xiàn)方法 全部硬件全部硬件 軟件為主軟件為主, 硬件為輔硬件為輔 兩級存儲器速度比兩級存儲器速度比 310 倍倍 105倍倍 頁（塊）大小頁（塊）大

35、小 116 字字 1KB16KB 等效存儲容量等效存儲容量 主存儲器主存儲器 虛擬存儲器虛擬存儲器 透明性透明性 對系統(tǒng)和應用程序員對系統(tǒng)和應用程序員 僅對應用程序員僅對應用程序員 不命中時處理方式不命中時處理方式 等待主存儲器等待主存儲器 任務切換任務切換 主存儲器地址（來自主存儲器地址（來自 CPU） 塊號塊號 B 塊內地址塊內地址 W 主存地址主存地址 未命中未命中 主存主存Cache 地址變換地址變換 命中命中 已滿已滿 未滿未滿 塊號塊號 b 塊內地址塊內地址 w Cache地址地址 Cache 替換策略替換策略 替換塊替換塊 裝入塊裝入塊 Cache 數(shù)據(jù)送數(shù)據(jù)送 CPU（一個字）

36、（一個字） 主存儲器 5.5.1 5.5.1 基本工作原理基本工作原理5.5.2 5.5.2 地址映象與變換方法地址映象與變換方法 地址映象：地址映象： 把主存中的程序按照某種規(guī)則裝入到把主存中的程序按照某種規(guī)則裝入到Cache中，并建立主存地址與中，并建立主存地址與Cache地址之間的對應關系。地址之間的對應關系。 地址變換：地址變換： 當程序已經(jīng)裝入到當程序已經(jīng)裝入到Cache之后，在程序運行過程中，把主存地址變換成之后，在程序運行過程中，把主存地址變換成Cache地址。地址。在選取地址映象方法要考慮的主要因素：在選取地址映象方法要考慮的主要因素： 地址變換的硬件實現(xiàn)容易、速度要快，地址變

37、換的硬件實現(xiàn)容易、速度要快， 主存空間利用率要高，主存空間利用率要高， 發(fā)生塊沖突的概率要小。發(fā)生塊沖突的概率要小。1. 1. 全相聯(lián)映象及其變換全相聯(lián)映象及其變換 映象規(guī)則：主存的任意映象規(guī)則：主存的任意 一塊可以映象到一塊可以映象到CacheCache 中的任意一塊。（映象關系有中的任意一塊。（映象關系有CbCbMbMb種）種）塊塊 0塊塊 1塊塊 0塊塊 1塊塊 i塊塊 Cb-1Cache塊塊 Mb-1主主存存儲儲器器 地址變換規(guī)則地址變換規(guī)則 用硬件實現(xiàn)非常復雜用硬件實現(xiàn)非常復雜 塊塊號號 B 塊塊內內地地址址W 主主存存地地址址 Cache 地地址址 塊塊號號 b 塊塊內內地地址址

38、w 相相聯(lián)聯(lián)比比較較 命命中中 B b 主主存存塊塊號號 B Cache 塊塊號號 b 有有效效位位 目目錄錄表表（由由相相聯(lián)聯(lián)存存儲儲器器構構成成，共共 Cb個個字字） 2. 2. 直接映象及其變換直接映象及其變換 映象規(guī)則：映象規(guī)則： 主存儲器中一塊只能映象到主存儲器中一塊只能映象到CacheCache的一個特定的的一個特定的塊中。塊中。 Cache Cache地址的計算公式：地址的計算公式： b bB mod CbB mod Cb 其中：其中：b b為為CacheCache塊號，塊號， B B是主存塊號，是主存塊號， Cb Cb是是CacheCache塊數(shù)。塊數(shù)。 實際上，實際上，Cac

39、heCache地址與主存儲器地址的低位部分完地址與主存儲器地址的低位部分完全相同。全相同。 直接映象方式的地址映象規(guī)則直接映象方式的地址映象規(guī)則 塊塊 0 塊塊 1 區(qū)區(qū) 0 塊塊 Cb-1 塊塊 0 塊塊 Cb 塊塊 1 塊塊 Cb+1 區(qū)區(qū) 1 塊塊 Cb-1 塊塊 2Cb-1 Cache 塊塊 Mb-Cb 塊塊 Mb-Cb+1 區(qū)區(qū) Me-1 塊塊 Mb-1 主主存存儲儲器器 直接映象方式的地址變換過程：直接映象方式的地址變換過程：用主存地址中的塊號用主存地址中的塊號B去訪問區(qū)號存儲器，把去訪問區(qū)號存儲器，把讀出來的區(qū)號與主存地址中的區(qū)號讀出來的區(qū)號與主存地址中的區(qū)號E進行比進行比較：較

40、：比較結果相等，有效位為比較結果相等，有效位為1，則，則Cache命中，命中，否則該塊已經(jīng)作廢。否則該塊已經(jīng)作廢。比較結果不相等，有效位為比較結果不相等，有效位為1，Cache中的該中的該塊是有用的，否則該塊是空的。塊是有用的，否則該塊是空的。 主主存存地地址址 區(qū)區(qū)號號 E 塊塊號號 B 塊塊內內地地址址W Cache 地地址址 塊塊號號 b 塊塊內內地地址址 w 塊塊失失效效 相相等等比比較較 比比較較相相等等且且有有效效為為 1 E 1 訪訪問問 Cache 區(qū)區(qū)號號 E（按按地地址址訪訪問問） 有有效效位位 區(qū)區(qū)表表存存儲儲器器 直接映象方式的地址變換規(guī)則直接映象方式的地址變換規(guī)則 提

41、高提高Cache速度的一種方法：速度的一種方法： 把區(qū)號存儲器與把區(qū)號存儲器與Cache合并成一個存儲器合并成一個存儲器 區(qū)區(qū)號號 E 塊塊號號 B 塊塊內內地地址址W Cache 地地址址 塊塊號號 b 塊塊內內地地址址 w 送送 CPU 訪訪問問主主存存 相相等等比比較較 相相等等 1/w 選選擇擇 1 E D0 D1 Dw-1 有有效效位位 區(qū)區(qū)號號 E 數(shù)數(shù)據(jù)據(jù) D0 數(shù)數(shù)據(jù)據(jù) D1 數(shù)數(shù)據(jù)據(jù) Dw-1 按按地地址址訪訪問問的的 Cache 2. 2. 直接映象及其變換的優(yōu)缺點直接映象及其變換的優(yōu)缺點 主要優(yōu)點：主要優(yōu)點： 硬件實現(xiàn)很簡單，不需要相聯(lián)訪問存儲器硬件實現(xiàn)很簡單，不需要相聯(lián)

42、訪問存儲器 訪問速度也比較快，實際上不需要進行地址訪問速度也比較快，實際上不需要進行地址變換變換 主要缺點：主要缺點： 塊的沖突率比較高。塊的沖突率比較高。5. 5. 組相聯(lián)映象及其變換組相聯(lián)映象及其變換 映象規(guī)則：映象規(guī)則： 主存和主存和CacheCache按同樣大小劃分成塊和組。按同樣大小劃分成塊和組。 主存和主存和CacheCache的組之間采用直接映象方式。的組之間采用直接映象方式。 在兩個對應的組內部采用全相聯(lián)映象方式。在兩個對應的組內部采用全相聯(lián)映象方式。 組相聯(lián)映象方式的優(yōu)點：組相聯(lián)映象方式的優(yōu)點： 塊的沖突概率比較低，塊的沖突概率比較低， 塊的利用率大幅度提高，塊的利用率大幅度

43、提高， 塊失效率明顯降低。塊失效率明顯降低。 組相聯(lián)映象方式的缺點：組相聯(lián)映象方式的缺點： 實現(xiàn)難度和造價要比直接映象方式高。實現(xiàn)難度和造價要比直接映象方式高。 塊塊 0 組組 0 Gb-1 Gb 組組 1 2Gb-1 區(qū)區(qū) 0 塊塊 0 GbCg-Gb 組組 0 組組 Cg-1 Gb-1 Cb-1=GbCg-1 Gb 1 2Gb-1 GbCg(Me-1) Cg(Me-1) GbCg(Me-1)+Gb-1 Cb-Gb=CgGb-Gb GbCg(Me-1)+Gb Cg-1 CgMe-Cg+1 Cb-1=CgGb-1 GbCg(Me-1)+2Gb-1 塊塊 2（ Cb-1） Me-1 Cache

44、Me-Gb=GbCgMe-Gb CgMe-1 Mb-1=GbCgMe-1 主主 存存 儲儲 器器 組組 相相 聯(lián)聯(lián) 映映 象象 方方 式式 組相聯(lián)映象的地址變換過程：組相聯(lián)映象的地址變換過程：用主存地址中的組號用主存地址中的組號G按地址訪問塊表存儲器。按地址訪問塊表存儲器。 把讀出來的一組區(qū)號和塊號與主存地址中的把讀出來的一組區(qū)號和塊號與主存地址中的區(qū)號和塊號進行相聯(lián)比較。區(qū)號和塊號進行相聯(lián)比較。如果有相等的，表示如果有相等的，表示Cache命中；命中；如果全部不相等，表示如果全部不相等，表示Cache沒有命中。沒有命中。 區(qū)區(qū)號號 E 組組號號 G 組組內內塊塊號號 B 塊塊內內地地址址 W

45、 主主存存地地址址 組組號號 g 組組內內塊塊號號 b 塊塊內內地地址址 w Cache 地地址址 不不等等 相相聯(lián)聯(lián)比比較較 相相等等 相相聯(lián)聯(lián)比比較較(Gb個個塊塊) 區(qū)區(qū)號號 E,組組內內塊塊號號 B 組組內內塊塊號號 b 塊塊 表表 組相聯(lián)映象的地址變換組相聯(lián)映象的地址變換 提高提高Cache訪問速度的一種方法：訪問速度的一種方法： 用多個相等比較器來代替相聯(lián)訪問用多個相等比較器來代替相聯(lián)訪問區(qū)區(qū)號號 E區(qū)區(qū)內內組組號號 G組組內內塊塊號號 B塊塊內內地地址址 W 主主存存地地址址 塊塊失失效效組組號號 g組組內內塊塊號號 b塊塊內內地地址址 w 與與Cache 地地址址或或相相等等比

46、比較較相相等等比比較較相相等等比比較較 E, B beE, Bb E, B be 塊塊表表(按按地地址址訪訪問問,讀讀出出的的多多個個字字段段進進行行相相聯(lián)聯(lián)比比較較,e 為為有有效效位位)組相聯(lián)映象方式組相聯(lián)映象方式典型機器的典型機器的 Cache 分組情況分組情況 機器型號機器型號 Cache 塊數(shù)塊數(shù) Cb 每組的塊數(shù)每組的塊數(shù) Gb Cache 組數(shù)組數(shù) Cg DEC VAX-11/780 1024 2 512 Amdahl 470/V6 512 2 256 Intel i860 D-Cache 256 2 128 Honeywell 66/60 512 4 128 Amdahl 47

47、0/V7 2048 4 512 IBM 370/168 1024 8 128 IBM3033 1024 16 64 Motolola 88110 256 2 128 4. 4. 位選擇組相聯(lián)映象及其變換位選擇組相聯(lián)映象及其變換地址映象規(guī)則：地址映象規(guī)則：主存和主存和CacheCache都按同樣大小分塊，都按同樣大小分塊，CacheCache在分塊的基礎上再分組，在分塊的基礎上再分組，主存按照主存按照CacheCache的組容量分區(qū)。的組容量分區(qū)。主存的塊與主存的塊與CacheCache的組之間采用直接映象方式，的組之間采用直接映象方式，主存中的塊與主存中的塊與CacheCache中組內部的各個

48、塊之間采用全相聯(lián)中組內部的各個塊之間采用全相聯(lián)映象方式。映象方式。與組相聯(lián)映象方式比較：與組相聯(lián)映象方式比較： 映象關系明顯簡單，實現(xiàn)起來容易。映象關系明顯簡單，實現(xiàn)起來容易。 在塊表中存放和參與相聯(lián)比較的只有區(qū)號在塊表中存放和參與相聯(lián)比較的只有區(qū)號E E 位選擇組相聯(lián)的地址映象規(guī)則位選擇組相聯(lián)的地址映象規(guī)則 塊塊 0 1 區(qū)區(qū) 0 塊塊 0 組組 0 Cg-1 Gb-1 Cg Gb Cg+1 組組 1 區(qū)區(qū) 1 2Gb-1 2Cg-1 Cb-Gb=CgGb-Gb Cg-1 Cg(Mb-1) Cb-1=CgGb-1 Cg(Mb-1)+1 Cache 區(qū)區(qū) Me-1 Mb-1=CgMe-1 主主

49、存存儲儲器器 區(qū)區(qū)號號 E區(qū)區(qū)內內塊塊號號 B塊塊內內地地址址 W 主主存存地地址址 塊塊失失效效組組號號 g組組內內塊塊號號 b塊塊內內 w 與與Cache 地地址址或或相相等等比比較較相相等等比比較較 相相等等比比較較 E b E b E b區(qū)區(qū)號號E塊塊號號be區(qū)區(qū)號號E塊塊號號be區(qū)區(qū)號號E塊塊號號be塊塊表表(按按地地址址訪訪問問,讀讀出出的的多多個個區(qū)區(qū)號號進進行行相相聯(lián)聯(lián)比比較較,e 是是有有效效位位) 位選擇組相聯(lián)的地址變換規(guī)則位選擇組相聯(lián)的地址變換規(guī)則5. 5. 段相聯(lián)映象及其變換段相聯(lián)映象及其變換映象規(guī)則：映象規(guī)則： 主存和主存和CacheCache都按同樣大小分塊和段都按

50、同樣大小分塊和段 段之間采用全相聯(lián)映象方式段之間采用全相聯(lián)映象方式 段內部的塊之間采用直接映象方式段內部的塊之間采用直接映象方式地址變換過程：地址變換過程：用主存地址中的段號與段表中的主存段號進行相聯(lián)比用主存地址中的段號與段表中的主存段號進行相聯(lián)比較較如果有相等的，用主存地址的段內塊號按地址訪問如果有相等的，用主存地址的段內塊號按地址訪問CacheCache的段號部分。的段號部分。把讀出的段號把讀出的段號s s與主存地址的段內塊號與主存地址的段內塊號b b及塊內地址及塊內地址w w拼接起來得到拼接起來得到CacheCache地址；地址； 段相聯(lián)映象地址映象規(guī)則段相聯(lián)映象地址映象規(guī)則 塊塊 0

51、段段 0 Sb-1 塊塊 0 Sb 段段 0 段段 1 Sb-1 2Sb-1 Sb 段段 1 2Sb-1 Cb-Sb=Sb(Cs-1) Cs-1 Cb-1=SbCs-1 Cache Mb-Sb=Sb(Ms-1) Ms-1 Mb-1=SbMs-1 主主 存存 儲儲 器器 主主 存存 地地 址址段段 號號 S段段 內內 塊塊 號號 B塊塊 內內 地地 址址 W段段 號號 s段段 內內 塊塊 號號 b塊塊 內內 地地 址址 wC ache 地地 址址相相 聯(lián)聯(lián) 比比 較較 段段 0 S 按按 地地 址址 訪訪 問問 段段 1s1 主主 存存 段段 號號 SC ache 段段 號號 s有有 效效 位位

52、 Ms-1 段段 表表 （ 按按 地地 址址 和和 相相 聯(lián)聯(lián) 兩兩 種種 訪訪 問問 方方 式式 ）段段相相聯(lián)聯(lián)映映象象地地址址變變換換過過程程段相聯(lián)映象方式的優(yōu)缺點段相聯(lián)映象方式的優(yōu)缺點主要優(yōu)點：主要優(yōu)點： 段表比較簡單，實現(xiàn)的成本低。段表比較簡單，實現(xiàn)的成本低。 例如：一個容量為例如：一個容量為256KB的的Cache，分成，分成8個段，每段個段，每段2048塊，每塊塊，每塊16B。 在段表存儲器中只需要存在段表存儲器中只需要存8個主存地址的段號個主存地址的段號, 而在塊表中要存儲而在塊表中要存儲8204816384個區(qū)號，個區(qū)號， 兩者相差兩者相差2000多倍。多倍。主要缺點：主要缺點

53、： 當發(fā)生段失效時，要把本段內已經(jīng)建立起來當發(fā)生段失效時，要把本段內已經(jīng)建立起來的所有映象關系全部撤消。的所有映象關系全部撤消。5.5.3 Cache5.5.3 Cache替換算法及其實現(xiàn)替換算法及其實現(xiàn)使用的場合：使用的場合： 直接映象方式實際上不需要替換算法直接映象方式實際上不需要替換算法 全相聯(lián)映象方式的替換算法最復雜全相聯(lián)映象方式的替換算法最復雜 主要用于組相聯(lián)、段相聯(lián)等映象方式中主要用于組相聯(lián)、段相聯(lián)等映象方式中要解決的問題：要解決的問題：記錄每次訪問記錄每次訪問Cache的塊號的塊號在訪問過程中，對記錄的塊號進行管理在訪問過程中，對記錄的塊號進行管理根據(jù)記錄和管理結果，找出替換的塊

54、號根據(jù)記錄和管理結果，找出替換的塊號主要特點：全部用硬件實現(xiàn)主要特點：全部用硬件實現(xiàn)1. 1. 輪換法及其實現(xiàn)輪換法及其實現(xiàn) 用于組相聯(lián)映象方式中，有兩種實現(xiàn)方法。用于組相聯(lián)映象方式中，有兩種實現(xiàn)方法。方法一：每塊一個計數(shù)器方法一：每塊一個計數(shù)器在塊表內增加一個替換計數(shù)器字段，在塊表內增加一個替換計數(shù)器字段， 計數(shù)器的長度與計數(shù)器的長度與CacheCache地址中的組內塊號字段的長地址中的組內塊號字段的長度相同。度相同。替換方法及計數(shù)器的管理規(guī)則：替換方法及計數(shù)器的管理規(guī)則：新裝入或替換的塊，它的計數(shù)器清新裝入或替換的塊，它的計數(shù)器清0 0，同組其它塊的，同組其它塊的計數(shù)器都加計數(shù)器都加“1”

55、“1”。在同組中選擇計數(shù)器的值最大的塊作為被替換的塊。在同組中選擇計數(shù)器的值最大的塊作為被替換的塊。例例5.11：Solar-16/65小型機的小型機的Cache采用位選采用位選擇組相聯(lián)映象方式。擇組相聯(lián)映象方式。Cache每組的塊數(shù)為每組的塊數(shù)為4，因此，每塊用一個因此，每塊用一個2位的計數(shù)器。位的計數(shù)器。 序列序列 初始值初始值 裝入塊裝入塊00 裝入塊裝入塊01 裝入塊裝入塊10 裝入塊裝入塊11 替換塊替換塊00 塊塊 00 00 00 01 10 11 00 塊塊 01 00 01 00 01 10 11 塊塊 10 00 01 10 00 01 10 塊塊 11 00 01 10

56、11 00 01 方法二：每組一個計數(shù)器方法二：每組一個計數(shù)器替換規(guī)則和計數(shù)器的管理：替換規(guī)則和計數(shù)器的管理： 本組有替換時，計數(shù)器加本組有替換時，計數(shù)器加“1”， 計數(shù)器的值就是要被替換出去的塊號。計數(shù)器的值就是要被替換出去的塊號。例例5.12：NOVA3機的機的Cache采用組相聯(lián)映象方采用組相聯(lián)映象方式，式，Cache每組的塊數(shù)為每組的塊數(shù)為8，每組設置一個，每組設置一個3位計數(shù)器。在需要替換時，計數(shù)器的值加位計數(shù)器。在需要替換時，計數(shù)器的值加“1”，用計數(shù)器的值直接作為被替換塊的塊，用計數(shù)器的值直接作為被替換塊的塊號。號。輪換法的優(yōu)點：實現(xiàn)比較簡單，能夠利用歷史輪換法的優(yōu)點：實現(xiàn)比較簡

57、單，能夠利用歷史上的塊地址流情況上的塊地址流情況輪換法的缺點：沒有利用程序的局部性特點輪換法的缺點：沒有利用程序的局部性特點2. LRU2. LRU算法及其實現(xiàn)算法及其實現(xiàn)為每一塊設置一個計數(shù)器為每一塊設置一個計數(shù)器 計數(shù)器的長度與塊號字段的長度相同計數(shù)器的長度與塊號字段的長度相同計數(shù)器的使用及管理規(guī)則：計數(shù)器的使用及管理規(guī)則：新裝入或替換的塊，計數(shù)器清新裝入或替換的塊，計數(shù)器清0 0，同組中其它塊的計，同組中其它塊的計數(shù)器加數(shù)器加1 1。命中塊的計數(shù)器清命中塊的計數(shù)器清0 0，同組的其它計數(shù)器中，凡計數(shù)，同組的其它計數(shù)器中，凡計數(shù)器的值小于命中塊計數(shù)器原來值的加器的值小于命中塊計數(shù)器原來值的

58、加1 1，其余計數(shù)，其余計數(shù)器不變。器不變。需要替換時，在同組的所有計數(shù)器中選擇計數(shù)值最大需要替換時，在同組的所有計數(shù)器中選擇計數(shù)值最大的計數(shù)器，它所對應的塊被替換。的計數(shù)器，它所對應的塊被替換。LRU算法的優(yōu)缺點算法的優(yōu)缺點主要優(yōu)點：主要優(yōu)點： (1)命中率比較高，命中率比較高， (2)能夠比較正確地利用程序的局部性特點，能夠比較正確地利用程序的局部性特點， (3)充分地利用歷史上塊地址流的分布情況，充分地利用歷史上塊地址流的分布情況， (4)是一種堆棧型算法，隨著組內塊數(shù)增加，是一種堆棧型算法，隨著組內塊數(shù)增加，命中率單調上升。命中率單調上升。主要缺點：主要缺點： 控制邏輯復雜，因為增加了

59、判斷和處理是否控制邏輯復雜，因為增加了判斷和處理是否命中的情況。命中的情況。 例例5.13：IBM 370/165機的機的Cache采用組相聯(lián)采用組相聯(lián)映象方式。每組有映象方式。每組有4塊，為了實現(xiàn)塊，為了實現(xiàn)LRU替換替換算法，在塊表中為每一塊設置一個算法，在塊表中為每一塊設置一個 2 位的計位的計數(shù)器。在訪問數(shù)器。在訪問Cache的過程中，塊的裝入、的過程中，塊的裝入、替換及命中時，計數(shù)器的工作情況如表：替換及命中時，計數(shù)器的工作情況如表：塊塊地地址址流流主主存存塊塊1主主存存塊塊2主主存存塊塊3主主存存塊塊4主主存存塊塊5主主存存塊塊4塊塊號號 計計數(shù)數(shù)器器 塊塊號號 計計數(shù)數(shù)器器 塊塊

60、號號 計計數(shù)數(shù)器器 塊塊號號 計計數(shù)數(shù)器器 塊塊號號 計計數(shù)數(shù)器器 塊塊號號 計計數(shù)數(shù)器器Cache塊塊0100101110111500501Cache塊ache塊塊20110300301310310Cache塊塊3011011400401400裝裝入入裝裝入入裝裝入入裝裝入入替替換換命命中中5. 5. 比較對法比較對法 以三個塊為例，分別稱為塊以三個塊為例，分別稱為塊A A、塊、塊B B、塊、塊C C 表示方法：用表示方法：用TABTAB1 1表示表示 B B塊比塊比 A A 塊更久沒有被塊更久沒有被訪問過。如果表示塊訪問過。如果表示塊 C C 最久沒