系統(tǒng)結構第3章

1、3.1 存儲系統(tǒng)原理,3.1.1 存儲系統(tǒng)的定義3.1.2 存儲系統(tǒng)的層次結構3.1.3 存儲系統(tǒng)的頻帶平衡3.1.4 并行訪問存儲器 3.1.5 交叉訪問存儲器 3.1.6 無沖突訪問存儲器,3.1.1 存儲系統(tǒng)的定義,在一臺計算機中，通常有多種存儲器種類：主存儲器、Cache、通用寄存器、緩沖存儲器、磁盤存儲器、磁帶存儲器、光盤存儲器等材料工藝：ECL、TTL、MOS、磁表面、激光，SRAM，DRA

2、M訪問方式：隨機訪問、直接譯碼、先進先出、 相聯(lián)訪問、 塊傳送、文件組,存儲器的主要性能：速度、容量、價格 速度用存儲器的訪問周期、讀出時間、頻帶寬度等表示。 容量用字節(jié)B、千字節(jié)KB、兆字節(jié)MB和千兆字節(jié)GB等單位表示。 價格用單位容量的價格表示，例如：$C/bit。 組成存儲系統(tǒng)的關鍵：把速度、容量和價格不同的多個物理存儲器組織成一個存儲器，這個存儲器的速度最快，存儲容量最大，單位容量的價格最便宜。,1. 存儲系統(tǒng)

3、的定義 兩個或兩個以上速度、容量和價格各不相同的存儲器用硬件、軟件、或軟件與硬件相結合的方法連接起來成為一個存儲系統(tǒng)。這個存儲系統(tǒng)對應用程序員是透明的，并且，從應用程序員看，它是一個存儲器，這個存儲器的速度接近速度最快的那個存儲器，存儲容量與容量最大的那個存儲器相等，單位容量的價格接近最便宜的那個存儲器。虛擬存儲器系統(tǒng)：對應用程序員透明Cache存儲系統(tǒng)：對系統(tǒng)程序員以上均透明,由多個存儲器構成的存儲系統(tǒng),在一般計算機系統(tǒng)中

4、，有兩種存儲系統(tǒng)：Cache存儲系統(tǒng)：由Cache和主存儲器構成 主要目的：提高存儲器速度,虛擬存儲系統(tǒng)：由主存儲器和硬盤構成 主要目的：擴大存儲器容量,2.存儲系統(tǒng)的容量要求：提供盡可能大的地址空間能夠隨機訪問方法有兩種：只對系統(tǒng)中存儲容量最大的那個存儲器進行編址，其他存儲器只在內部編址或不編址 Cache存儲系統(tǒng)另外設計一個容量很大的邏輯地址空間，把相關存儲器都映射這個地址空間中 虛擬存儲系統(tǒng),3.存儲系

5、統(tǒng)的價格計算公式：當S2》S1時，C≈C2 S2與S1不能相差太大,4. 存儲系統(tǒng)的速度表示方法：訪問周期、存取周期、存儲周期、存取時間等命中率定義：在M1存儲器中訪問到的概率 其中：N1是對M1存儲器的訪問次數(shù) N2是對M2存儲器的訪問次數(shù)訪問周期與命中率的關系： T＝HT1＋(1－H)T2 當命中率H→1時，T→T1,存儲系統(tǒng)的訪問效率：訪問效率主要與

6、命中率和兩級存儲器的速度之比有關例3.1：假設T2＝５T１，在命中率H為0.9和0.99兩種情況下，分別計算存儲系統(tǒng)的訪問效率。解：,當H＝0.9時，e1＝1／(0.9＋5(1－0.9))＝0.72,當H＝0.99時，e2＝1／(0.99＋5(1－0.99))＝0.96,提高存儲系統(tǒng)速度的兩條途徑：一是提高命中率H，二是兩個存儲器的速度不要相差太大其中：第二條有時做不到(如虛擬存儲器)，這時，只能依靠提高命中率例3.2

7、：在虛擬存儲系統(tǒng)中，兩個存儲器的速度相差特別懸殊，例如：T2＝105 T１。如果要使訪問效率到達e＝0.9，問需要有多高的命中率？,解：,0.9H＋90000(1-H)＝189999.1 H＝89999計算得： H＝0.999998888877777… ≈0.999999,5. 采用預取技術提高命中率 方法：不命中時，把M2存儲器中相鄰多個單元組成的一個數(shù)據(jù)塊取出來送入M1存儲器中。,計算公式： 其中：

8、H’是采用預取技術之后的命中率 H是原來的命中率 n為數(shù)據(jù)塊大小與數(shù)據(jù)重復使用次數(shù)的乘積,例3.3：在一個Cache存儲系統(tǒng)中，當Cache的塊大小為一個字時，命中率H＝0.8；假設數(shù)據(jù)的重復利用率為5，T2＝5T1。計算塊大小為４個字時，Cache存儲系統(tǒng)的命中率？并分別計算訪問效率。,解：n＝4×5＝20， 采用預取技術之后，命中率提高到：,3.1.2 存儲系統(tǒng)的層次結構,多個層次的存儲器：　 第

9、1層：Register Files(寄存器堆) 第2層： Buffers(Lookahead)(先行緩沖站)　 第3層： Cache(高速緩沖存儲器) 第4層： Main Memory(主存儲器) 第5層： Online Storage(聯(lián)機存儲器) 第6層： Off-line Storage(脫機存儲器)用i表示層數(shù)，則有：工作周期Ti＜Ti+1， 存儲容量：Si＜Si+1，單位價格：

10、Ci＞Ci+1,各級存儲器的主要主要性能特性 CPU與主存儲器的速度差距越來越大 目前相差兩個數(shù)量級 今后CPU與主存儲器的速度差距會更大,3.1.3 存儲系統(tǒng)的頻帶平衡,例3.5：Pentium4的指令執(zhí)行速度為8GIPS，CPU取指令8GW/s，訪問數(shù)據(jù)16GW/s，各種輸入輸出設備訪問存儲器1GW/s，三項相加，要求存儲器的頻帶寬度不低于25GW/s。 如果采用PC133內存，主存與CPU速度差188倍

11、 如果采用PC266內存，主存與CPU速度差94倍解決存儲器頻帶平衡方法 (1)多個存儲器并行工作（本節(jié)下面介紹） (2)設置各種緩沖存儲器（第五章介紹） (3)采用存儲系統(tǒng)（本章第二、第三節(jié)介紹）,3.1.4 并行訪問存儲器,方法：把m字w位的存儲器改變成為m/n字n×w位的存儲器邏輯實現(xiàn)：把地址碼分成兩個部分，一部分作為存儲器的地址另一部分負責選擇數(shù)據(jù)主要缺點：訪問沖突大 (1)取指令沖突

12、(2)讀操作數(shù)沖突 (3)寫數(shù)據(jù)沖突 (4)讀寫沖突,并行訪問存儲器結構框圖,1. 高位交叉訪問存儲器主要目的：擴大存儲器容量實現(xiàn)方法：用地址碼的高位部分區(qū)分存儲體號參數(shù)計算方法: m：每個存儲體的容量， n：總共的存儲體個數(shù)， j：存儲體的體內地址，j＝0，1，2，...，m-1 k：存儲體的體號，k＝0，1，2，...，n-1 存儲器的地址：A＝m×k＋j 存儲

13、器的體內地址：Aj＝A mod m。 存儲器的體號： Ak＝,3.1.5 交叉訪問存儲器,高位交叉訪問存儲器結構框圖,例3.6：用4M字×4位的存儲芯片組成16M×32位的主存儲器。共用存儲芯片：用最高2位地址經譯碼后產生的信號，控制各組存儲芯片CS。每組中的32根數(shù)據(jù)線分別對應直接相連，稱為“線或”方式。,2. 低位交叉訪問存儲器 主要目的：提高存儲器訪問速度 實現(xiàn)方法：用地址碼的低位部分區(qū)

14、分存儲體號 參數(shù)計算: m：每個存儲體的容量， n：總共的存儲體個數(shù)， j：存儲體的體內地址，j＝0，1，2，...，m-1 k：存儲體的體號，k＝0，1，2，...，n-1 存儲器地址A的計算公式為：A＝n×j＋k 存儲器的體內地址：Aj＝ 存儲器的體號：Ak＝A mod n,低位交叉訪問存儲器結構框圖,地址是編碼方法： 由8個存儲體構成的低位交叉編址方式,n個存儲體分時啟動

15、 一種采用流水線方式工作的并行存儲器 每存儲體的啟動間隔為：t＝ 其中： Tm為每個存儲體的訪問周期, n為存儲體個數(shù)。,訪問沖突 共有n個存儲體，每個存儲周期只能取到k個有效字,其余n-k個存儲體有沖突。假設p(k)是k的概率密度函數(shù)，即p(1)是k＝1的概率，p(2)是k＝2的概率，…,p(n)是k＝n的概率。k的平均值為：N是每個存儲周期能夠訪問到的平均有效字的個數(shù)。通常把

16、 N稱為并行存儲器的加速比。,定義轉移概率為g，即讀出的是轉移指令，且轉移成功的概率。這時有： p(1)＝g p(2)＝(1-p(1))g＝(1-g)g p(3)＝(1-p(1)-p(2))g＝(1-g)2g …… p(k)＝(1-g)k-1g (k＝1,2,…,n－1) …… p(n)＝(1-g)n-1,Ｎ＝g＋(1-g)g＋(1-g)2g＋…＋(1-g)n-2g

17、 ＋(1-g)g＋(1-g)2g＋…＋(1-g)n-2g ＋(1-g)2g＋…＋(1-g)n-2g … ＋(1-g)n-2g ＋n(1-g)n-1以上共n行，前n-2行分別為等比級數(shù)把n-1行拆分成2項,則：Ｎ＝1g＋2

18、(1-g)g＋3(1-g)2g＋… ＋(n-1)(1-g)n-2g＋n(1-g)n-1,Ｎ＝1-(1-g)n-1 ＋(1-g)-(1-g)n-1 ＋(1-g)2-(1-g)n-1 … ＋(1-g)n-2-(1-g)n-1 ＋n(1-g)n-1,Ｎ＝1＋(1-g)＋(1-g)2＋…(1-g)n-2＋(1-g)n-1,3.1.6 無沖突訪問存儲器,1. 一維數(shù)組(向量)的無沖突

19、訪問存儲器 按連續(xù)地址訪問，沒有沖突， 位移量為2的變址訪問，速度降低一倍，…,具體方法： 存儲體的個數(shù)取質數(shù)，且n≥向量長度。 原因：變址位移量必然與存儲體個數(shù)互質 例如：Burroughs公司巨型科學計算機BSP 存儲體個數(shù)為17 向量長度≤16我國研制的銀河巨型向量機 存儲體的個數(shù)為37 向量長度≤32,2. 二維數(shù)組的無沖突訪問存儲器要求：一個n×n的二維數(shù)組，按行、列、對角線和反

20、對角線訪問，并且在不同的變址位移量情況下，都能實現(xiàn)無沖突訪問。順序存儲：按行、對角線訪問沒有沖突，但按列訪問每次沖突,錯位存儲： 按行、按列訪問無沖突， 但按對角線訪問有沖突,n×n二維數(shù)組無沖突訪問存儲方案 ( P· Budnik 和 D· J· Kuck提出 ) ： 并行存儲體的個數(shù)m≥n，并且取質數(shù)，同時還要在行、列方向上錯開一定的距離存儲數(shù)組元素。 設同一列相鄰

21、元素在并行存儲器中錯開d1個存儲體存放，同一行相鄰元素在并行存儲器中錯開d2個存儲體存放。當m＝22p＋1（p為任意自然數(shù)）時，能夠同時實現(xiàn)按行、按列、按對角線和按反對角線無沖突訪問的充要條件是：d1＝2P，d2＝1。,例如：4×4的二維數(shù)組，取并行存儲體的個數(shù)m＝5，由關系式m＝22P＋1，解得到p＝1，計算得到： d1＝21＝2 d2＝1,,,,n×n數(shù)組中的任意一個元素aij在無沖突并行存儲器中

22、的體號地址和體內地址的計算公式： 體號地址：(2P i＋j＋k) MOD m 體內地址：i 其中：0≤i≤n－1， 0≤j≤n－1， k是數(shù)組的第一個元素a00所在體號地址， m是并行存儲體的個數(shù)，要求m≥n且為質數(shù)， p是滿足m＝22P＋1關系的任意自然數(shù)。 主要缺點：浪費存儲單元 對于n×n數(shù)組,有(m-n) × m個存儲單

23、元浪費 主要優(yōu)點：實現(xiàn)簡單 列元素順序存儲，行元素按地址取模順序存儲,3. 二維數(shù)組的無沖突訪問存儲器(之二)規(guī)則：對于任意一個n×n的數(shù)組，如果能夠找到滿足n＝22P關系的任意自然數(shù)p，則這個二維數(shù)組就能夠使用n個并行存儲體實現(xiàn)按行、列、對角線和反對角線的無沖突訪問。4×4數(shù)組用4個存儲體的無訪問沖突存儲方案,3.2.1 虛擬存儲器工作原理3.2.2 地址的映象和變換方法3.2.3 加快內部地址變換的

24、方法3.2.4 頁面替換算法及其實現(xiàn)3.2.5 提高主存命中率的方法,3.2 虛擬存儲器,3.2.1 虛擬存儲器工作原理,也稱為虛擬存儲系統(tǒng)、虛擬存儲體系等其概念由英國曼徹斯特大學的Kilbrn等人于1961年提出到70年代廣泛應用于大中型計算機系統(tǒng)目前，許多微型機也使用虛擬存儲器把主存儲器、磁盤存儲器和虛擬存儲器都劃分成固定大小的頁 主存儲器的頁稱為實頁 虛擬存儲器中的頁稱為虛頁,內部地址變換： 多用戶虛擬地址

25、Av變換成主存實地址A 多用戶虛擬地址中的頁內偏移D直接作為主存實地址中的頁內偏移d， 主存實頁號p與它的頁內偏移d直接拼接起來就得到主存實地址A。,3.2.2 地址的映象與變換,三種地址空間：虛擬地址空間 主存儲器地址空間 輔存地址空間地址映象： 把虛擬地址空間映象到主存地址空間地址變換： 在程序運行時，把虛地址變換成主存實地址三種虛擬存儲器： 頁式虛擬存

26、儲器 段式虛擬存儲器 段頁式虛擬存儲器,1. 段式虛擬存儲器地址映象方法：每個程序段都從0地址開始編址，長度可長可短，可以在程序執(zhí)行過程中動態(tài)改變程序段的長度。,地址變換方法：由用戶號找到基址寄存器，讀出段表起始地址，與虛地址中段號相加得到段表地址，把段表中的起始地址與段內偏移D相加就能得到主存實地址。,主要優(yōu)點： (1)程序的模塊化性能好。 (2)便于程

27、序和數(shù)據(jù)的共享。 (3)程序的動態(tài)鏈接和調度比較容易。 (4)便于實現(xiàn)信息保護。 主要缺點： (1)地址變換所花費的時間長，兩次加法 (2)主存儲器的利用率往往比較低。 (3)對輔存（磁盤存儲器）的管理比較困難。,2. 頁式虛擬存儲器 地址映象方法：,地址變換方法：,主要優(yōu)點： (1)主存儲器的利用率比較高 (2)頁表相對比較簡單 (3)地址變換的速度比較快 (4)對磁盤的管理比較容易

28、 主要缺點： (1)程序的模塊化性能不好 (2)頁表很長，需要占用很大的存儲空間 例如：虛擬存儲空間4GB，頁大小1KB，則頁表的容量為4M字，16MB。,3. 段頁式虛擬存儲器 用戶按段寫程序, 每段分成幾個固定大小的頁 地址映象方法：每個程序段在段表中占一行， 在段表中給出頁表長度和頁表的起始地址， 頁表中給出每一頁在主存儲器中的實頁號。,地址變換方法： 先查段表，得到頁表起始地址和頁表長度

29、， 再查頁表找到要訪問的主存實頁號， 把實頁號p與頁內偏移d拼接得到主存實地址。,4. 外部地址變換 每個程序有一張外頁表，每一頁或每個程序段，在外頁表中都有對應的一個存儲字。,3.2.3 加快內部地址變換的方法,造成虛擬存儲器速度降低的主要原因： (1) 要訪問主存儲器必須先查段表或頁表， (2) 可能需要多級頁表。頁表級數(shù)的計算公式： 其中： Nv為虛擬存儲空間大小，

30、 Np為頁面的大小， Nd為一個頁表存儲字的大小,例如：虛擬存儲空間大小Nv＝4GB，頁的大小Np＝1KB，每個頁表存儲字占用4個字節(jié)。計算得到頁表的級數(shù)：通常僅把1級頁表和2、3級頁表中的一小部分駐留在主存中,1.目錄表 基本思想：用一個小容量高速存儲器存放頁表,地址變換過程： 把多用戶虛地址中U與P拼接，相聯(lián)訪問目錄表。讀出主存實頁號p，把p與多用戶虛地址中的D拼接得到主存實地址。

31、如果相聯(lián)訪問失敗，發(fā)出頁面失效請求。主要優(yōu)點： 與頁表放在主存中相比，查表速度快。主要缺點： 可擴展性比較差, 主存儲器容量大時，目錄表造價高，速度低。,2. 快慢表,快表：TLB(Translation Lookaside Buffer)： 小容量(幾～幾十個字)， 高速硬件實現(xiàn)， 采用相聯(lián)方式訪問。 慢表： 當快表中查不到時，從主存的慢表中查找； 慢表按地址訪問；用軟件實現(xiàn)。

32、 快表與慢表也構成一個兩級存儲系統(tǒng)。 主要存在問題：相聯(lián)訪問實現(xiàn)困難，速度低,3. 散列函數(shù) 目的：把相聯(lián)訪問變成按地址訪問 散列(Hashing)函數(shù)：Ah＝H(Pv),采用散列變換實現(xiàn)快表按地址訪問 避免散列沖突：采用相等比較器 地址變換：相等比較與訪問存儲器同時進行,3.2.4 頁面替換算法及其實現(xiàn),1. 頁面替換發(fā)生時間： 當發(fā)生頁面失效時，要從磁盤中調入一頁到主存。如果主存儲器的所有頁面都已經被占

33、用，必須從主存儲器中淘汰掉一個不常使用的頁面，以便騰出主存空間來存放新調入的頁面。2. 評價頁面替換算法好壞的標準： 一是命中率要高， 二是算法要容易實現(xiàn)。,3. 頁面替換算法的使用場合：(1)虛擬存儲器中，主存頁面的替換，一般用軟件實現(xiàn)。(2)Cache中的塊替換，一般用硬件實現(xiàn)。(3)虛擬存儲器的快慢表中，快表存儲字的替換，用硬件實現(xiàn)。(4)虛擬存儲器中，用戶基地址寄存器的替換，用硬件實現(xiàn)。(5)在有些虛擬存

34、儲器中，目錄表的替換。,4. 主要頁面替換算法(1)隨機算法（RAND random algorithm） 算法簡單，容易實現(xiàn)。 沒有利用歷史信息，沒有反映程序的局部性 命中率低。(2)先進先出算法 (FIFO first-in first-out algorithm) 容易實現(xiàn)，利用了歷史信息， 沒有反映局部性。 最先調入的頁面，很可能也是要使用的頁面,(3)近期最少使用算法(LFU l

35、east frequently used algorithm)：既充分利用了歷史信息，又反映了程序的局部性實現(xiàn)起來非常困難。(4)最久沒有使用算法(LRU least recently used algorithm)：把LFU算法中的“多”與“少”簡化成“有”與“無”，實現(xiàn)比較容易(5)最優(yōu)替換算法（OPT optimal replacement algorithm）：是一種理想算法，僅用作評價其它頁面替換算法好壞的標準。

36、 在虛擬存儲器中，實際上可能采用的只有FIFO和LRU兩種算法。,例3.9：一個程序共有5個頁面組成，在程序執(zhí)行過程中，頁面地址流如下： P1，P2，P1，P5，P4，P1，P3，P4，P2，P4 假設分配給這個程序的主存只有3個頁面。(1)給出用FIFO、LRU和OPT三種頁面替換算法對這3個主存頁面的調度情況表，并統(tǒng)計頁面命中次數(shù)。(2)計算這LRU頁面替換算法的頁面命中率。(3)假設每個數(shù)據(jù)平均被訪問30次，為了

37、使LRU算法的失效率小于10-5，計算頁面大小至少應該為多少？,解：(1)FIFO、LRU和OPT的頁面命中次數(shù)分別為2次、4次和5次 (2)LRU頁面替換算法的頁面命中率為： Hp＝4/10＝0.4(3) 解得 P > 2000字 頁面大小應該為2K字。,例3.10：一個循環(huán)程序，依次使用P1，P2，P3， P4頁面，分配給它的主存頁面數(shù)只有2個。在 F

38、IFO和LRU算法中，發(fā)生“顛簸”現(xiàn)象。,5. 堆棧型替換算法 定義：對任意一個程序的頁地址流作兩次主存頁面數(shù)分配，分別分配 m 個主存頁面和 n 個主存頁面，并且有 m≤n。如果在任何時刻 t，主存頁面數(shù)集合 Bt 都滿足關系： Bt（m）? Bt（n），則這類算法稱為堆棧型替換算法。 堆棧型算法的基本特點是： 隨著分配給程序的主存頁面數(shù)增加，主存的命中率也提高，至少不下降。,3.2.5 提高主存命中率

39、的方法,影響主存命中率的主要因素：(1)程序在執(zhí)行過程中的頁地址流分布情況。(2)所采用的頁面替換算法。(3)頁面大小。(4)主存儲器的容量(5)所采用的頁面調度算法 以下，對后三個因素進行分析。1.頁面大小與命中率的關系 頁面大小為某個值時，命中率達到最大。,頁面大小與命中率關系的解釋： 假設At和At+1是相鄰兩次訪問主存的邏輯地址， d＝｜At－At+1｜。如果ｄ＜Sp，隨著Sp增大，At 和

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

41、2. 主存容量與命中率的關系 主存命中率H隨著分配給該程序的主存容量S的增加而單調上升。 在S比較小的時候，H提高得非?？臁ｋS著S的逐漸增加，H提高的速度逐漸降低。當S增加到某一個值之后，H幾乎不再提高。,3. 頁面調度方式與命中率的關系 請求式：當使用到的時候，再調入主存 預取式：在程序重新開始運行之前，把上次 停止運行前一段時間內用到的頁面先調入到 主存儲器，然后才開始運行程序。 預取式的主要優(yōu)點

42、： 可以避免在程序開始運行時，頻繁發(fā)生頁面 失效的情況。 預取式的主要缺點： 如果調入的頁面用不上，浪費了調入的時間， 占用了主存的資源。,3.3 高速緩沖存儲器,3.3.1 基本工作原理3.3.2 地址映象與變換方法3.3.3 Cache替換算法及其實現(xiàn)3.3.4 Cache存儲系統(tǒng)的加速比3.3.5 Cache的一致性問題3.3.6 Cache的預取算法,,3.3.1 基本

43、工作原理,3.3.2 地址映象與變換方法,地址映象： 把主存中的程序按照某種規(guī)則裝入到Cache中，并建立主存地址與Cache地址之間的對應關系。 地址變換： 當程序已經裝入到Cache之后，在程序運行過程中，把主存地址變換成Cache地址。在選取地址映象方法要考慮的主要因素： 地址變換的硬件實現(xiàn)容易、速度要快， 主存空間利用率要高， 發(fā)生塊沖突的概率要小。,1. 全相聯(lián)映象及其變換 映象

44、規(guī)則：主存的任意 一塊可以映象到Cache 中的任意一塊。（映象關系有Cb×Mb種）,地址變換規(guī)則 用硬件實現(xiàn)非常復雜,2. 直接映象及其變換 映象規(guī)則： 主存儲器中一塊只能映象到Cache的一個特定的塊中。 Cache地址的計算公式： b＝B mod Cb 其中：b為Cache塊號， B是主存塊號， Cb

45、是Cache塊數(shù)。 實際上，Cache地址與主存儲器地址的低位部分完全相同。,直接映象方式的地址映象規(guī)則,直接映象方式的地址變換過程：用主存地址中的塊號B去訪問區(qū)號存儲器，把讀出來的區(qū)號與主存地址中的區(qū)號E進行比較：比較結果相等，有效位為1，則Cache命中，否則該塊已經作廢。比較結果不相等，有效位為1，Cache中的該塊是有用的，否則該塊是空的。,直接映象方式的地址變換規(guī)則,提高Cache速度的一種方法： 把區(qū)號存儲器

46、與Cache合并成一個存儲器,2. 直接映象及其變換的優(yōu)缺點 ? 主要優(yōu)點： 硬件實現(xiàn)很簡單，不需要相聯(lián)訪問存儲器 訪問速度也比較快，實際上不需要進行地址變換 ? 主要缺點： 塊的沖突率比較高。,3. 組相聯(lián)映象及其變換 映象規(guī)則： 主存和Cache按同樣大小劃分成塊和組。 主存和Cache的組之間采用直接映象方式。 在兩個對應的組內部采用全相聯(lián)映象

47、方式。 組相聯(lián)映象方式的優(yōu)點： 塊的沖突概率比較低， 塊的利用率大幅度提高， 塊失效率明顯降低。 組相聯(lián)映象方式的缺點： 實現(xiàn)難度和造價要比直接映象方式高。,組相聯(lián)映象的地址變換過程：用主存地址中的組號G按地址訪問塊表存儲器。 把讀出來的一組區(qū)號和塊號與主存地址中的區(qū)號和塊號進行相聯(lián)比較。如果有相等的，表示Cache命中；如果全部不相等，表示Cache沒有命中。,組相聯(lián)映象的地址變

48、換,提高Cache訪問速度的一種方法： 用多個相等比較器來代替相聯(lián)訪問,4. 位選擇組相聯(lián)映象及其變換地址映象規(guī)則：主存和Cache都按同樣大小分塊，Cache在分塊的基礎上再分組，主存按照Cache的組容量分區(qū)。主存的塊與Cache的組之間采用直接映象方式，主存中的塊與Cache中組內部的各個塊之間采用全相聯(lián)映象方式。與組相聯(lián)映象方式比較： 映象關系明顯簡單，實現(xiàn)起來容易。 在塊表中存放和參與相聯(lián)比較的

49、只有區(qū)號E,位選擇組相聯(lián)的地址映象規(guī)則,位選擇組相聯(lián)的地址變換規(guī)則,5. 段相聯(lián)映象及其變換映象規(guī)則： 主存和Cache都按同樣大小分塊和段 段之間采用全相聯(lián)映象方式 段內部的塊之間采用直接映象方式地址變換過程：用主存地址中的段號與段表中的主存段號進行相聯(lián)比較如果有相等的，用主存地址的段內塊號按地址訪問Cache的段號部分。把讀出的段號s與主存地址的段內塊號b及塊內地址w拼接起來得到Cache地址；,段相聯(lián)映

50、象地址映象規(guī)則,段相聯(lián)映象地址變換過程,段相聯(lián)映象方式的優(yōu)缺點主要優(yōu)點： 段表比較簡單，實現(xiàn)的成本低。 例如：一個容量為256KB的Cache，分成8個段，每段2048塊，每塊16B。 在段表存儲器中只需要存8個主存地址的段號, 而在塊表中要存儲8×2048＝16384個區(qū)號， 兩者相差2000多倍。主要缺點： 當發(fā)生段失效時，要把本段內已經建立起來的所有映象關系全部撤消。,3.3.

51、3 Cache替換算法及其實現(xiàn),使用的場合： 直接映象方式實際上不需要替換算法 全相聯(lián)映象方式的替換算法最復雜 主要用于組相聯(lián)、段相聯(lián)等映象方式中要解決的問題：記錄每次訪問Cache的塊號在訪問過程中，對記錄的塊號進行管理根據(jù)記錄和管理結果，找出替換的塊號主要特點：全部用硬件實現(xiàn),1. 輪換法及其實現(xiàn) 用于組相聯(lián)映象方式中，有兩種實現(xiàn)方法。方法一：每塊一個計數(shù)器在塊表內增加一個替換計數(shù)器字段，

52、 計數(shù)器的長度與Cache地址中的組內塊號字段的長度相同。替換方法及計數(shù)器的管理規(guī)則：新裝入或替換的塊，它的計數(shù)器清0，同組其它塊的計數(shù)器都加“1”。在同組中選擇計數(shù)器的值最大的塊作為被替換的塊。,方法二：每組一個計數(shù)器替換規(guī)則和計數(shù)器的管理： 本組有替換時，計數(shù)器加“1”， 計數(shù)器的值就是要被替換出去的塊號。輪換法的優(yōu)點：實現(xiàn)比較簡單，能夠利用歷史上的塊地址流情況輪換法的缺點：沒有利用程序的局部性特點,2.

53、 LRU算法及其實現(xiàn)為每一塊設置一個計數(shù)器 計數(shù)器的長度與塊號字段的長度相同計數(shù)器的使用及管理規(guī)則：新裝入或替換的塊，計數(shù)器清0，同組中其它塊的計數(shù)器加1。命中塊的計數(shù)器清0，同組的其它計數(shù)器中，凡計數(shù)器的值小于命中塊計數(shù)器原來值的加1，其余計數(shù)器不變。需要替換時，在同組的所有計數(shù)器中選擇計數(shù)值最大的計數(shù)器，它所對應的塊被替換。,LRU算法的優(yōu)缺點主要優(yōu)點： (1)命中率比較高， (2)能夠比較正確地利用程

54、序的局部性特點， (3)充分地利用歷史上塊地址流的分布情況， (4)是一種堆棧型算法，隨著組內塊數(shù)增加，命中率單調上升。主要缺點： 控制邏輯復雜，因為增加了判斷和處理是否命中的情況。,3. 堆棧法堆棧法的管理規(guī)則：把本次訪問的塊號與堆棧中保存的所有塊號進行相聯(lián)比較。如果有相等的，則Cache命中。把本次訪問塊號從棧頂壓入，堆棧內各單元中的塊號依次往下移，直至與本次訪問的塊號相等的那個單元為止，再往下的單元直止棧

55、底都不變。如果沒有相等的，則Cache塊失效。本次訪問的塊號從棧頂壓入，堆棧內各單元的塊號依次往下移，直至棧底，棧底單元中的塊號被移出堆棧，它就是要被替換的塊號。,例如：每組為4塊，則堆棧有4個存儲單元， 每個單元2位。,堆棧法的主要優(yōu)點： 塊失效率比較低，因為它采用了LRU算法。 硬件實現(xiàn)相對比較簡單。堆棧法的主要缺點： 速度比較低，因為它需要進行相聯(lián)比較。堆棧法與比較對法所用觸發(fā)器的比例：

56、 其中，Gb是Cache每一組的塊數(shù)。當Gb大于8時，堆棧法所用的器件明顯少于比較對法。,3.3.4 Cache存儲系統(tǒng)的加速比,1. 加速比與命中率的關系Cache存儲系統(tǒng)的加速比SP為： 其中：Tm為主存儲器的訪問周期， Tc為Cache的訪問周期， T為Cache存儲系統(tǒng)的等效訪問周期， H為命中率。提高加速比的最好途徑

57、是提高命中率,加速比 SP 能夠接近于期望值是： 加速比SP與命中率H的關系,2. Cache命中率與容量的關系 Cache的命中率隨它的容量的增加而提高。 關系曲線可以近似地表示為：,3. Cache命中率與塊大小的關系 在組相聯(lián)方式中, 塊大小對命中率非常敏感 塊很小時，命中率很低。 隨著塊大小增加命中率也增加, 有一個極大值 當塊非常大時

58、, 進入Cache中的數(shù)據(jù)可能無用 當塊大小等于Cache容量時, 命中率將趨近零4. Cache命中率與組數(shù)的關系 在組相聯(lián)方式中, 組數(shù)對命中率的影響很明顯 隨著組數(shù)的增加，Cache的命中率要降低。 當組數(shù)不太大時(小于512), 命中率的降低很少 當組數(shù)超過一定數(shù)量時, 命中率的下降非常快,Cache命中率與塊大小的關系,3.3.5 Cache的一致性,造成Cache與主存的不一致的原因：

59、 (1) 由于CPU寫Cache，沒有立即寫主存 (2) 由于IO處理機或IO設備寫主存,Cache的更新算法 (1)寫直達法，寫通過法，WT(Write-through) CPU的數(shù)據(jù)寫入Cache時，同時也寫入主存 (2) 寫回法，抵觸修改法，WB(Write-Back) CPU的數(shù)據(jù)只寫入Cache，不寫入主存，僅當替換時，才把修改過的Cache塊寫回主存寫回法與寫直達法的優(yōu)缺點比較

60、： (1)可靠性，寫直達法優(yōu)于寫回法。寫直達法能夠始終保證Cache是主存的副本。如果Cache發(fā)生錯誤，可以從主存得到糾正。,(2)與主存的通信量，寫回法少于寫直達法。對于寫回法： 大多數(shù)操作只需要寫Cache，不需要寫主存； 當發(fā)生塊失效時，可能要寫一個塊到主存； 即使是讀操作，也可能要寫一個塊到主存。對于寫直達法： 每次寫操作，必須寫、且只寫一個字到主存。實際上： 寫直達法的

61、寫次數(shù)很多、每次只寫一個字； 寫回法是的寫次數(shù)很少、每次要寫一個塊。舉例說明：,(3)控制的復雜性, 寫直達法比寫回法簡單。對于寫回法： 要為每塊設置一個修改位，而且要對修改位進行管理； 為了保證Cache的正確性，通常要采用比較復雜的校驗方式或校正方式。對于寫直達法： 不需要設置修改位； 只需要采用簡單的奇偶校驗即可。由于Cache始終是主存的副本，Cache一旦有錯誤可以從主存得到糾正。,(4)

62、硬件實現(xiàn)的代價, 寫回法要比寫直達法好。對于寫直達法： 為了縮短寫Cache流水段的時間，通常要設置一個小容量的高速寄存器堆（后行寫數(shù)緩沖站），每個存儲單元要有數(shù)據(jù)、地址和控制狀態(tài)等3部分組成。 每次寫主存時，首先把寫主存的數(shù)據(jù)和地址寫到高速寄存器堆中。 每次讀主存時，要首先判斷所讀數(shù)據(jù)是否在這個高速寄存器堆中。寫回法不需要設置高速緩沖寄存器堆。,寫Cache的兩種方法： (1)不按寫分配法： 在

63、寫Cache不命中時，只把所要寫的字寫入主存。 (2)按寫分配法： 在寫Cache不命中時，還把一個塊從主存讀入Cache。 目前，在寫回法中采用按寫分配法， 在寫直達法中采用不按寫分配法。,解決Cache與主存不一致的主要方法： (1)共享Cache法。能根本解決Cache不一致， 共享Cache可能成為訪問的瓶頸，硬件復雜 (2)作廢法。當某一處理機寫局

64、部Cache時， 同時作廢其他處理機的局部Cache。 (3)播寫法。把寫Cache的內容和地址放到公共總線上，各局部Cache隨時監(jiān)聽公共總線 (4)目錄表法。在目錄表中存放Cache一致性的全部信息。 (5)禁止共享信息放在局部Cache中。 Cache對系統(tǒng)程序員不透明。,3.3.6 Cache的預取算法,預取算法有如下幾種： (1)按需取。當出現(xiàn)Cache不命中時，才把需要的一個塊

65、取到Cache中。 (2)恒預取。無論Cache是否命中，都把下一塊取到Cache中。 (3)不命中預取。當出現(xiàn)Cache不命中，把本塊和下一塊都取到Cache中。主要考慮因素： 命中率是否提高，Cache與主存間通信量。 恒預取能使Cache不命中率降低75～85％ 不命中預取能使Cache不命中率降低30～40％,3.4 三級存儲系統(tǒng),虛擬存儲系統(tǒng)和Cache存儲系統(tǒng)可同時存在存儲系統(tǒng)可以有多種

66、構成方法不同的構成只是實現(xiàn)技術不同,3.4.1 存儲系統(tǒng)的組織方式,兩個存儲系統(tǒng)的組織方式： 又稱為：物理地址Cache存儲系統(tǒng) 目前的大部分處理機采用這種兩級存儲系統(tǒng)一個存儲系統(tǒng)組織方式： 又稱為：虛擬地址Cache存儲系統(tǒng) 如Intel公司的i860等處理機采用這種組織方式全Cache系統(tǒng)： 沒有主存儲器， 由Cache和磁盤組成存儲系統(tǒng)。,1. 兩個存儲系統(tǒng)的組織方式

67、2. 一個存儲系統(tǒng)組織方式3. 全Cache系統(tǒng),3.4.2 虛擬地址Cache,虛擬存儲器采用位選擇組相聯(lián)方式 虛擬存儲器中的一頁等于主存儲器的一個區(qū)用虛擬地址中的虛頁號訪問快表如果快表命中，把塊表中的主存區(qū)號E與快表中的主存實頁號P進行比較。若比較結果相等，則Cache命中。讀出Cache的塊號b，并與B、b、W拼接得到Cache地址。若Cache不命中，則用主存實頁號P、及B和W拼接，得到主存實地址。若快

68、表沒有命中，通過軟件查主存中的慢表,3.4.3 全Cache存儲系統(tǒng),建立存儲系統(tǒng)的目的：獲得一個速度接近Cache，容量等于虛擬地址空間的存儲器。這個存儲器如何構成，具體分成幾級來實現(xiàn)，只是具體的實現(xiàn)技術而已。隨著計算機硬件和軟件技術的發(fā)展，存儲系統(tǒng)的實現(xiàn)技術也在不斷改變。最直接最簡單的方法：用一個速度很高，存儲容量很大的存儲器來實現(xiàn)。全Cache(all-Cache)是一種理想的存儲系統(tǒng)。,一種多處理機系統(tǒng)中的全Cache存