第3章存儲系統(tǒng)課件

第三章存儲系統(tǒng)3.1存儲系統(tǒng)原理

3.2虛擬存儲器

3.3高速緩沖存儲器

3.4三級存儲系統(tǒng)

3.1存儲系統(tǒng)的原理3.1.1存儲系統(tǒng)的定義3.1.2存儲系統(tǒng)的層次結(jié)構(gòu)3.1.3頻帶平衡3.1.4并行存儲器3.1.5交叉訪問存儲器與1980年的64KBDRAM相比，在時延方面性能增長為年均7%。而處理器方面到1986年性能每年增長1.25倍，到2004年每年增長1.52倍，2004年以后增長率變?yōu)?.20倍。以1980年為基準(zhǔn)，存儲器和處理器性能差距隨時間變化曲線4存在的問題：系統(tǒng)結(jié)構(gòu)設(shè)計的關(guān)鍵問題：如何以合理的價格，設(shè)計出容量和速度都滿足計算機系統(tǒng)要求的存儲器系統(tǒng)？人們對這三個指標(biāo)的要求：容量大、速度快、價格低三個要求是相互矛盾的！5較經(jīng)濟的解決方法：利用局部性原理和存儲器成本性能分析技術(shù)，采用存儲器層次結(jié)構(gòu)。局部性原理和“越小的硬件速度越快”的原則，共同導(dǎo)致了基于不同速度和容量的存儲器層次結(jié)構(gòu)的產(chǎn)生。3.1.1存儲系統(tǒng)的定義6存儲系統(tǒng)的基本知識存儲系統(tǒng)的多級層次結(jié)構(gòu)演示多級存儲層次7一個多級存儲層次結(jié)構(gòu)：距離處理器越遠(yuǎn)的層次，存儲容量越大，訪問速度越慢訪問時間單位在ps到ms之間變化，容量在B和TB之間變化8組成存儲系統(tǒng)的關(guān)鍵：把速度、容量和價格不同的多個物理存儲器組織成一個存儲器系統(tǒng)，其中每一層都比下一層容量更小，速度更快，每字節(jié)成本也更高。這樣的系統(tǒng)表現(xiàn)出來的性能：訪問速度與最快層次的存儲器接近，卻具有幾乎相當(dāng)于最便宜存儲器層次的價格。每一層都要從一個較大的存儲器空間把地址映射到一個較小但是更快的上層存儲器。作為地址映射的一部分，存儲器層次結(jié)構(gòu)應(yīng)該進行地址檢查。所以用于檢查地址的保護機制也是存儲器層次結(jié)構(gòu)的一部分。9存儲器的主要性能：速度、容量、價格速度用存儲器的訪問周期、讀出時間、頻帶寬度等表示。

容量用字節(jié)B、千字節(jié)KB、兆字節(jié)MB和千兆字節(jié)GB等單位表示。

價格用單位容量的價格表示，例如：$C/bit。存儲器的性能參數(shù)10存儲系統(tǒng)的定義兩個或兩個以上速度、容量和價格各不相同的存儲器用硬件、軟件、或軟件與硬件相結(jié)合的方法連接起來成為一個存儲系統(tǒng)。這個存儲系統(tǒng)對應(yīng)用程序員是透明的，并且，從應(yīng)用程序員看，它是一個存儲器，這個存儲器的速度接近速度最快的那個存儲器，存儲容量與容量最大的那個存儲器相等，單位容量的價格接近最便宜的那個存儲器。虛擬存儲器系統(tǒng)：對應(yīng)用程序員透明

Cache存儲系統(tǒng)：對系統(tǒng)程序員以上均透明11Cache存儲系統(tǒng)：由Cache和主存儲器構(gòu)成主要目的：提高存儲器速度12虛擬存儲系統(tǒng)：由主存儲器和硬盤構(gòu)成主要目的：擴大存儲器容量13“Cache－主存”層次：彌補主存速度的不足主存－輔存”層次：彌補主存容量的不足存儲層次CPU對第二級的

訪問方式比較項目目的存儲管理實現(xiàn)

訪問速度的比值

(第一級和第二級)典型的塊(頁)大小不命中時CPU是否切換“Cache－主存”層次“主存－輔存”層次為了彌補主存速度的不足為了彌補主存容量的不足主要由專用硬件實現(xiàn)主要由軟件實現(xiàn)幾比一幾萬比一幾十個字節(jié)幾百到幾千個字節(jié)可直接訪問均通過第一級不切換切換到其他進程“Cache－主存”與“主存－輔存”層次的區(qū)別151存儲容量目的：提供盡可能大的地址空間、能夠隨機訪問Cache存儲系統(tǒng)編址：面向系統(tǒng)程序員，選擇對主存儲器編址，對Cache在內(nèi)部采用相聯(lián)訪問方式管理。從系統(tǒng)程序員看Cache存儲系統(tǒng)，看到是主存儲器的地址空間，存儲系統(tǒng)的容量就是主存儲器的容量。虛擬存儲系統(tǒng)：磁盤的地址空間而并不能被一般的指令訪問，而主存儲器的地址空間對于使用者來說又太小。所以虛擬存儲器系統(tǒng)為使用者另外設(shè)計一個虛擬地址空間，比主存儲器的實際空間大很多，采用與主存儲器同樣的隨機訪問方式。16當(dāng)S2》S1時，C≈C22存儲系統(tǒng)的價格173存儲系統(tǒng)的速度命中率定義：CPU訪問存儲系統(tǒng)時，在M1中找到所需信息的概率。其中：N1是對M1存儲器的訪問次數(shù)

N2是對M2存儲器的訪問次數(shù)整個存儲系統(tǒng)的訪問時間可以采用M1和M2的訪問周期T1、T2及命中率H來表示：T＝HT1＋(1－H)T218訪問效率主要與命中率和兩級存儲器的速度之比有關(guān)存儲系統(tǒng)的訪問效率：19例：假設(shè)T2＝５T１，在命中率H為0.9和0.99兩種情況下，分別計算存儲系統(tǒng)的訪問效率。解：當(dāng)H＝0.9時，

e1＝1／(0.9＋5(1－0.9))＝0.72

當(dāng)H＝0.99時，

e2＝1／(0.99＋5(1－0.99))＝0.9620提高存儲系統(tǒng)速度的兩條途徑：一是提高命中率H二是兩個存儲器的速度不要相差太大其中：第二條有時做不到(如虛擬存儲器)，這時，只能依靠提高命中率21例：在虛擬存儲系統(tǒng)中，兩個存儲器的速度相差特別懸殊，例如：T2＝105T１。如果要使訪問效率到達e＝0.9，問需要有多高的命中率？解：計算得：

H＝0.999998888877777…≈0.99999922采用預(yù)取技術(shù)提高命中率方法：不命中時，把M2存儲器中相鄰多個單元組成的一個數(shù)據(jù)塊取出來送入M1存儲器中。（程序的局部性原理）有該關(guān)系式存在：其中：H’是采用預(yù)取技術(shù)之后的命中率

H是原來的命中率

n為數(shù)據(jù)塊大小與數(shù)據(jù)重復(fù)使用次數(shù)的乘積23通過預(yù)取提高Cache存儲系統(tǒng)的命中率例：在一個Cache存儲系統(tǒng)中，當(dāng)Cache的塊大小為一個字時，命中率H＝0.8；假設(shè)數(shù)據(jù)的重復(fù)利用率為5，T2＝5T1。計算塊大小為４個字時，Cache存儲系統(tǒng)的命中率？并分別計算訪問效率。解：n＝4×5＝20，采用預(yù)取技術(shù)之后，命中率提高到：24解：n＝4×5＝20，采用預(yù)取技術(shù)之后，命中率提高到0.99

當(dāng)Cache塊大小為1個字時，H=0.8

訪問效率：當(dāng)Cache塊大小為4個字時，H=0.99

訪問效率：25在虛擬存儲器中的應(yīng)用對于虛擬存儲系統(tǒng)，磁盤是以塊為單位訪問的，邏輯上為1KB-16KB。磁盤存儲器的尋址時間長，但一旦定位好，數(shù)據(jù)的傳輸率比較高。所以可以在不命中的時候通過操作系統(tǒng)的調(diào)用，把將要使用的大批程序和數(shù)據(jù)調(diào)入主存，這要求主存的容量較大還要能多次重復(fù)使用。從而提高命中率。雖然不命中會造成花費較長的時間進行調(diào)度，但是由于總體的命中率高，還是能保證系統(tǒng)的速度等同于主存的訪問速度。26例：在一個虛擬存儲系統(tǒng)中，T2＝105T1，原來的命中率只有0.8，如果訪問磁盤存儲器的數(shù)據(jù)塊大小為4K字，并要求訪問效率不低于0.9，計算數(shù)據(jù)在主存儲器中的重復(fù)利用率至少為多少？解：假設(shè)數(shù)據(jù)在主存儲器中的重復(fù)利用率為m，根據(jù)前面給出的關(guān)系，有如下方程組：27并行主存系統(tǒng)一個單體單字寬的存儲器字長與CPU的字長相同。每一次只能訪問一個存儲字。假設(shè)該存儲器的訪問周期是TM，字長為W位，則其帶寬為：

普通存儲器28并行主存系統(tǒng)在相同的器件條件（即TM相同）下，可以采用兩種并行存儲器結(jié)構(gòu)來提高主存的帶寬：單體多字存儲器多體交叉存儲器29單體多字存儲器一個單體m字（這里m=4）存儲器

將存儲器的字方向擴展m倍，成為m×w位，同時地址數(shù)相應(yīng)減少n倍，成為L/m個地址。在一個存儲周期內(nèi)訪問m個字。30存儲器能夠每個存儲周期讀出m個CPU字。因此其最大帶寬提高到原來的m倍。單體多字存儲器的實際帶寬比最大帶寬小優(yōu)缺點優(yōu)點：實現(xiàn)簡單缺點：訪存效率不高

31如果一次讀取的m個指令字中有分支指令，而且分支成功，那么該分支指令之后的指令是無用的。一次取出的m個數(shù)據(jù)不一定都是有用的。另一方面，當(dāng)前執(zhí)行指令所需要的多個操作數(shù)也不一定正好都存放在同一個長存儲字中。寫入有可能變得復(fù)雜。當(dāng)要讀出的數(shù)據(jù)字和要寫入的數(shù)據(jù)字處于同一個長存儲字內(nèi)時，讀和寫的操作就無法在同一個存儲周期內(nèi)完成。存在問題：323.1.5交叉訪問存儲器多體交叉存儲器：由多個單字存儲體構(gòu)成，每個體都有自己的地址寄存器以及地址譯碼和讀/寫驅(qū)動等電路。編址方案：高位交叉存儲器低位交叉存儲器（可以有效的解決訪問沖突問題）33并行存儲器的編址技術(shù)高位交叉編址：主要用來擴大存儲器容量。低位交叉編址：主要是提高存儲器速度。34高位交叉：4*80011100110001010010000011000100000100000765432100111101110011010110001011010100100101000151413121110981011110110101011010010011100101000110000232221201918171611111111101110111100110111101011001110003130292827262524存儲器接口請求35高位交叉存儲器MBR存儲體0MARMBR存儲體n-1MARMBR存儲體1MAR……譯碼器（高位）存儲器地址寄存器（低位）……36每個存儲模塊都具備各自獨立的控制部件，包括地址寄存器、地址譯碼器、驅(qū)動電路、放大電路、讀寫控制電路、數(shù)據(jù)寄存器等，有些還具備校驗及校正電路、高速緩沖存儲部件等，每個模塊可以獨立的工作。由于程序的連續(xù)性和局部性，在程序的執(zhí)行過程中，被訪問的指令序列和數(shù)據(jù)絕大多數(shù)都分布在同一個存儲模塊中，因此大多數(shù)情況是：一個存儲模塊很忙碌，其余的模塊空閑。單任務(wù)系統(tǒng)中，高位交叉訪問方式主要目的用于擴充容量。多任務(wù)或多用戶系統(tǒng)中，可以通過把不同的任務(wù)分配給不同的存儲體來提高存儲器的訪問速度37

低位交叉：4*81110011000101001000001100010000010000000282420161284011101110011010110001011010100100101000012925211713951111101101010110100100111001010001100001030262218141062111111101110111100110111101011001110001131272319151173存儲器接口請求38低位交叉存儲器MBR存儲體0MARMBR存儲體n-1MARMBR存儲體1MAR……存儲器地址寄存器（高位）譯碼器（低位）……由8個存儲體構(gòu)成的低位交叉編址398個存儲體構(gòu)成的低位交叉編址891011121314150123456724……3116…19…2332……3940……4748……5556……63主存儲器數(shù)據(jù)寄存器體內(nèi)地址（3位）模塊地址（3位）返回40為了提高主存的帶寬，需要多個或所有存儲體能并行工作。

在每一個存儲周期內(nèi)，分時啟動m個存儲體。如果每個存儲體的訪問周期是TM，則各存儲體的啟動間隔為：

t=TM/m。n個存儲體分時啟動41層次存儲系統(tǒng)必須解決的四個問題：當(dāng)把一個塊（頁）調(diào)入高一層（靠近CPU）存儲器時，可以放在哪些位置上？當(dāng)所要訪問的塊（頁）在高一層存儲器中時，如何找到該塊（頁）？當(dāng)發(fā)生不命中，并也高一層存儲器已經(jīng)滿了，要調(diào)入新的一塊（頁），應(yīng)該替換哪一塊（頁）？當(dāng)進行寫訪問時，應(yīng)該進行哪些操作？3.2虛擬存儲器也稱為虛擬存儲系統(tǒng)、虛擬存儲體系等，其概念由英國曼徹斯特大學(xué)的Kilbrn等人于1961年提出，到70年代廣泛應(yīng)用于大中型計算機系統(tǒng)?，F(xiàn)在微型機也使用虛擬存儲器。虛擬存儲器由主存儲器和磁盤存儲器共同構(gòu)成，這兩個存儲器在硬件和系統(tǒng)軟件的共同管理下，對于應(yīng)用人員可以看作是一個單一存儲量很大的主存儲器。其中必須的地址變換則是自動完成的。3.2虛擬存儲器3.2.1虛擬存儲器工作原理3.2.2地址的映象和變換方法3.2.3加快內(nèi)部地址變換的方法3.2.4頁面替換算法及其實現(xiàn)3.2.5提高主存命中率的方法44虛擬存儲器是一種存儲器共享技術(shù)，將物理存儲器分塊并分配給不同的進程使用?？梢杂行У臏p少程序啟動時間，因為程序運行之前不需要將所有的代碼和數(shù)據(jù)都載入物理寄存器。使得程序的加載更加簡單。程序可以被放在物理存儲器和磁盤的任何地方，只需要改變地址之間的映射關(guān)系。45一個擁有4個頁面的程序在虛擬存儲器和物理存儲器之間的地址映射圖463.2.1虛擬存儲器的工作原理多用戶虛擬地址主存地址程序執(zhí)行時要根據(jù)虛擬地址找到主存地址虛擬地址和主存地址之間的關(guān)系由地址映像體現(xiàn)出，而在程序執(zhí)行時通過地址變換將用戶程序中的虛擬地址變成主存的實地址473.2.2地址的映像與變換三種地址空間：虛擬地址空間，主存儲器地址空間，輔存地址空間地址映象：把虛擬地址空間映象到主存地址空間地址變換：程序運行時將虛擬地址變換成主存實地址三種虛擬存儲器：段式虛擬存儲器、頁式虛擬存儲器、段頁式虛擬存儲器。481頁式虛擬存儲器頁式虛擬存儲器把虛擬地址空間劃分成一個個固定大小的塊,每塊稱為一頁,把主存儲器的地址空間也按虛擬地址空間同樣的大小劃分為頁。頁是一種邏輯上的劃分，它可以由系統(tǒng)軟件任意指定。目前的計算機系統(tǒng)中，一頁的大小通常為1KB-16KB虛擬地址空間中的頁稱為虛頁，主存地址空間中的頁稱為實頁。49關(guān)于存儲層次的結(jié)構(gòu)必須解決的問題1：當(dāng)把一個塊調(diào)入高一層(靠近CPU)存儲器時，

可以放在哪些位置上?地址的映像規(guī)則思路：由于虛擬存儲器發(fā)生頁面失效時需要讀取磁盤，所以延遲很大。系統(tǒng)的設(shè)計者通常會避免因缺失代價過高而選擇較低的缺失率。操作系統(tǒng)允許將塊存放在內(nèi)存中的任意位置。即全相聯(lián)的映像方式。50關(guān)于存儲層次的結(jié)構(gòu)必須解決的問題2：如何在內(nèi)存中查找一個塊？510頁1頁2頁3頁頁號主存頁號0123用戶程序主存儲器頁表頁式虛擬存儲器的地址映象520頁1頁2頁3頁頁號主存頁號0123用戶程序主存儲器頁表頁式虛擬存儲器的地址映象53虛擬地址和主存地址用戶號U虛頁號P頁內(nèi)偏移D多用戶虛擬地址Av的組成實頁號p頁內(nèi)偏移d主存地址A的組成頁表記錄了虛頁號和實頁號之間的對應(yīng)關(guān)系。從而可以根據(jù)頁表找到每個實頁的地址。實地址為實頁號拼上頁內(nèi)偏移54頁式存儲器的地址變換每個用戶使用一個基址寄存器（在CPU內(nèi)），通過用戶號U可以直接找到與這個用戶程序相對應(yīng)的基址寄存器，從這個基址寄存器中讀出頁表起始地址。訪問這個頁表地址，把得到的主存頁號p與虛地址中的頁內(nèi)偏移直接拼接起來得到主存實地址。內(nèi)部地址變換的實現(xiàn)：Pa裝入位修改位主存頁號各種標(biāo)志用戶號U虛頁號P頁內(nèi)偏移D頁內(nèi)偏移d1pPa頁表基址寄存器頁表實頁號p1、操作系統(tǒng)會為每道程序分配一個用戶號，根據(jù)用戶號找到與程序?qū)?yīng)的基址寄存器，從基址寄存器中讀出頁表的起始地址。Pa裝入位修改位主存頁號各種標(biāo)志用戶號U虛頁號P頁內(nèi)偏移D頁內(nèi)偏移d1pPa頁表基址寄存器頁表實頁號p2、用戶程序的每一頁在頁表中都有對應(yīng)的一行，并且頁表是按照用戶程序的頁號順序存放的，所以可以去掉虛存頁號字段。Pa裝入位修改位主存頁號各種標(biāo)志用戶號U虛頁號P頁內(nèi)偏移D頁內(nèi)偏移d1pPa頁表基址寄存器頁表實頁號p3根據(jù)主存頁號和虛存的頁內(nèi)偏移得出主存的地址。58若某虛頁對應(yīng)的實頁已經(jīng)裝入主存，頁表的裝入位是1，則進行內(nèi)部地址變換即可。頁表的大?。簽樘摂M地址空間中的頁數(shù)。假設(shè)虛擬地址為32位，頁大小為4KB，頁表的每一項是4個字節(jié)，則頁表的大小為：232/212×22=222字節(jié)，即4MB頁表存放在內(nèi)存中59若某虛頁對應(yīng)的實頁已經(jīng)裝入主存，頁表的裝入位是1，則進行內(nèi)部地址變換即可。否則需要進行外部地址變換。即從輔存中找到需要的數(shù)據(jù)并調(diào)入主存。外部地址變換：首先查外頁表得到磁盤存儲器實地址

把磁盤存儲器實地址和主存儲器實頁號送入輸入輸出處理機

把要訪問數(shù)據(jù)所在的一整頁都從磁盤存儲器調(diào)入到主存儲器60頁式虛擬存儲器的工作原理P10911、用戶程序給出虛擬地址。2、在操作系統(tǒng)和有關(guān)硬件的共同管理下，首先進行內(nèi)部地址變換。23、若命中，即頁表的裝入位是“1”，進行內(nèi)部地址變換，找到主存地址，得到所需數(shù)據(jù)。34、若未命中，即頁表中的裝入位為“0”，要訪問磁盤存儲器，進行外部地址變換。該過程均用軟件實現(xiàn)：查外頁表得到與虛頁號P對應(yīng)的磁盤存儲器實地址，再查內(nèi)頁表，看主存是否有空頁。445、若主存有空頁，找到空頁號，將磁盤存儲器的實地址和主存儲器實頁號送入輸入輸出處理機（輸入輸出通道）等，在輸入輸出處理機的控制下，將要訪問數(shù)據(jù)的一整頁從磁盤存儲器調(diào)入到主存儲器56、若沒有空頁，采用某種頁面替換算法，選出一頁寫回到磁盤存儲器的原位置，騰出空位存放新頁。若該頁從來沒有被修改過，（從頁表的修改位可以體現(xiàn)出來）就不需要送回磁盤存儲器，直接調(diào)入的新頁覆蓋原頁即可。67、若磁盤存儲器未命中，在操作系統(tǒng)的控制下，啟動磁帶機、光盤存儲器等，將所需的數(shù)據(jù)相關(guān)文件調(diào)入磁盤存儲器。7692段式虛擬存儲器地址映象方法：每個程序段都從0地址開始編址，長度可長可短，可以在程序執(zhí)行過程中動態(tài)改變程序段的長度。段的長短可以變化，處理器支持的最大范圍從216字節(jié)到232字節(jié)不等，最小的段可以只有1字節(jié)。70主程序

(0段)1k1段2段3段0500020002000段名段長起址01k8k150016k22009k320030k08k9k16k30k程序

空間主存儲器段表段式虛擬存儲器的地址映像71段式虛擬存儲器地址變換方法多用戶虛擬地址的構(gòu)成：用戶號U、段號S、段內(nèi)偏移D地址變換方法：由用戶號找到基址寄存器

從基址寄存器中讀出段表的起始地址

把起始地址與多用戶虛地址中段號相加得到該段的所有信息。把段表中給出的該段在內(nèi)存中的起始地址與段內(nèi)偏移D相加就能得到主存實地址

0段表

長度段表

基址5As段名起始地址裝入

位段長訪問

方式用戶號U段號S段內(nèi)偏移D多用戶

虛地址主存實地址432101n-1As段表基址寄存器一個用戶（一道作業(yè)）的段表73頁式虛擬存儲器段式虛擬存儲器(1)程序的模塊化性能好

(2)便于程序和數(shù)據(jù)的共享

(3)程序的動態(tài)鏈接和調(diào)度比較容易

(4)便于實現(xiàn)信息保護(1)地址變換所花費的時間比較長，做兩次加法運算

(2)主存儲器的利用率往往比較低

(3)對輔存（磁盤存儲器）的管理比較困難(1)主存儲器的利用率比較高

(2)頁表相對比較簡單

(3)地址變換的速度比較快

(4)對磁盤的管理比較容易(1)程序的模塊化性能不好

(2)頁表很長，需要占用很大的存儲空間。例如：虛擬存儲空間4GB，頁大小1KB，每頁在頁表中占一個字（4個字節(jié)），則頁表的容量為4M字，16MB743段頁式虛擬存儲器目的：要同時獲得段式虛擬存儲器在程序模塊化方面的優(yōu)點和頁式虛擬存儲器在管理主存和輔存物理空間方面的優(yōu)點。思路：虛擬存儲空間采用分段的方法管理，主存儲器的物理空間采用分頁的方法管理。一個段由若干個頁組成。實現(xiàn)手段：用戶按段寫程序,每段分成幾個固定大小的頁地址映象方法：每個程序段在段表中占一行，在段表中給出頁表長度和頁表的起始地址，頁表中給出每一頁在主存儲器中的實頁號。

地址變換方法：先查段表，得到頁表起始地址和頁表長度，再查頁表找到要訪問的主存實頁號，把實頁號p與頁內(nèi)偏移d拼接得到主存實地址。77采用段頁式，可以不必連續(xù)存儲，簡化了替換操作，也不需要整個段都存放在內(nèi)存中。現(xiàn)在也可以采用混合方法提供多種容量的頁：較大的頁面大小是最小頁面的大小乘以2的冪。如IBM405CR嵌入式處理器所使用的頁面大小有：1KB，4KB（22×1KB），16KB（24×1KB），64KB（26×1KB），256KB（28×1KB），1024KB（210×1KB），4096KB（212×1KB），784外部地址變換在操作系統(tǒng)中，把頁面失效當(dāng)作一種異常故障來處理。每個用戶程序都有一張外頁表，虛擬地址空間中的每一頁或每個程序段，在外頁表中都有對應(yīng)的一個存儲字。每一個存儲字除了磁盤存儲器的地址之外，至少還包括一個裝入位。79裝入磁盤實地址用戶號頁內(nèi)偏移1虛頁號外部地址

變換（軟

件實現(xiàn)）磁盤號柱面號磁頭號塊號多用戶

虛地址外頁表外部地址變換803.2.3加快內(nèi)部地址變換的方法頁表通常比較大，需要存放在內(nèi)存中，有時對頁表本身也需要分頁。假設(shè)虛擬地址為32位，頁大小為4KB，頁表的每一項是4個字節(jié)，則頁表的大小為：232/212×22=222字節(jié)，即4MB對頁表的訪問意味著多次訪存：當(dāng)從存儲器中取一個指令或者數(shù)據(jù)或者寫結(jié)果需要訪存兩次：一次訪存獲取物理地址，另一次訪存獲取數(shù)據(jù)。81解決思路：將這些地址轉(zhuǎn)換保存在一個專門的Cache中，這個特殊的地址變換Cache就是TLB（TranslationLookasideBuffer）旁視緩沖器，也稱為快表。快表：根據(jù)程序局部性的特點，對頁表的訪問也不是隨機的，只是局限在少數(shù)幾個存儲字內(nèi)。將經(jīng)常訪問的頁面地址存放在一個小容量的高速存儲器中。構(gòu)成快表。按內(nèi)容訪問。快表的內(nèi)容是慢表的一個副本。與慢表構(gòu)成兩級存儲系統(tǒng)，采用到了局部性原理。82P118采用快慢表的地址變換過程83實例：AMDOpteron的數(shù)據(jù)TLB的組織結(jié)構(gòu)TLB中的項由兩部分構(gòu)成：標(biāo)識和數(shù)據(jù)標(biāo)識中存放的是虛地址的一部分。數(shù)據(jù)部分中存放的則是物理頁幀號、有效位、存儲保護信息、使用位、修改位等。AMDOpteron的數(shù)據(jù)TLB的組織結(jié)構(gòu)包含40個項采用全相聯(lián)映象AMDOpteron的地址轉(zhuǎn)換過程

8485關(guān)于存儲層次的結(jié)構(gòu)必須解決的問題3：當(dāng)發(fā)生虛擬存儲器訪問失效時應(yīng)該替換哪一個塊？原則：盡量減少頁面失效的情況發(fā)生。863.2.4頁面替換算法及其實現(xiàn)1頁面替換發(fā)生時間：

當(dāng)發(fā)生頁面失效時，要從磁盤中調(diào)入一頁到主存。如果主存所有頁面都已經(jīng)被占用，必須從主存儲器中淘汰掉一個不常使用的頁面，以便騰出主存空間來存放新調(diào)入的頁面。2評價頁面替換算法好壞的標(biāo)準(zhǔn)：

一是命中率要高

二是算法要容易實現(xiàn)873什么情況可能需要使用頁面替換算法(1)虛擬存儲器中，主存頁面的替換，一般用軟件實現(xiàn)。(2)Cache中的塊替換，一般用硬件實現(xiàn)。(3)虛擬存儲器的快慢表中，快表存儲字的替換，用硬件實現(xiàn)。(4)虛擬存儲器中，用戶基地址寄存器的替換，用硬件實現(xiàn)。884主要頁面替換算法(1)隨機算法（RANDrandomalgorithm）算法簡單，容易實現(xiàn)。沒有利用歷史信息，沒有反映程序的局部性命中率低。(2)先進先出算法

(FIFOfirst-infirst-outalgorithm)

容易實現(xiàn)，利用了歷史信息，沒有反映局部性。最先調(diào)入的頁面，很可能也是要使用的頁面89(3)最久沒有使用算法(LFUleastfrequentlyusedalgorithm)：選擇近期最久沒有訪問的頁面作為替換頁面。通過操作系統(tǒng)周期性清除使用位然后記錄該位，可以確定在特定的時間周期內(nèi)究竟用到了那些頁，從而確定近期最久沒有使用的頁面。(4)最優(yōu)替換算法（OPToptimalreplacementalgorithm）：選擇將來最久不被訪問的頁面作為替換頁面。90例：

一個程序共有5個頁面組成，程序執(zhí)行過程中的頁地址流如下：

P1,P2,P1,P5,P4,P1,P3,P4,P2,P4

假設(shè)分配給這個程序的主存儲器共有3個頁面。給出FIFO、LRU、OPT三種頁面替換算法對這3頁主存的使用情況，包括調(diào)入、替換和命中等。92顛簸對于循環(huán)程序，一次使用P1、P2、P3、P4四個頁面，主存分配了3個頁面，在使用FIFO和LRU算法調(diào)度時，可能出現(xiàn)現(xiàn)象：總發(fā)生下次就要使用的頁面本次被替換出去了。舉例：解決辦法：增加主存的分配給該程序的頁面數(shù)。問題：分配給程序的主存頁數(shù)越多，命中率就越高？返回顛簸現(xiàn)象945堆棧型替換算法符合：隨著分配給程序的主存頁面數(shù)的增加，主存的命中率也隨之提高，至少不下降。由P124圖3.25可以看出，F(xiàn)IFO不屬于堆棧型算法。系統(tǒng)使用LFU算法，可以更好的管理和調(diào)度。953.2.5提高命中率的方法影響主存命中率的主要因素：

(1)程序執(zhí)行過程中的頁地址流分布情況

(2)所采用的頁面替換算法

(3)頁面大小

(4)主存儲器的容量

(5)所采用的頁面調(diào)度方式961頁面大小與命中率的關(guān)系頁面大小為某個值時，命中率達到最大。隨著頁面增大，兩次相鄰訪問存儲器的地址處在一個頁面的可能性就增大，則H提高。隨著頁面大小的進一步增大，主存的頁面數(shù)必將減少，頁面的替換從而也會更加頻繁。頁面大小SP命中率H1S2S97

當(dāng)Sp比較小的時候，前一種情況是主要的，Ｈ隨著Sp的增大而提高。

當(dāng)Sp達到某一個最大值之后，后一種情況成為主要的，Ｈ隨著Sp的增大而降低。

當(dāng)頁面大小增大時，造成的浪費也要增加。

當(dāng)頁面大小

減小時，頁表和

頁面表在主存儲

器中所占的比例

將增加。頁面大小SP命中率H1S2S98頁面大小選擇頁面設(shè)置大的理由：頁表的大小與頁大小成反比，選擇較大的頁能夠節(jié)省頁表存儲器（或其他用于存儲器映射的資源）。在存儲器和輔存間傳送一個較大的頁比傳送較小頁的效率高。TLB項的個數(shù)受限制，較大頁意味著更多的存儲器信息被有效映射，可以減少TLB的失效次數(shù)。99頁面大小選擇頁面設(shè)置小的理由：節(jié)省存儲空間，減少內(nèi)部存儲碎片的量，并節(jié)省I/O帶寬。減少進程啟動時間：許多進程比較小，所以較大的頁延長調(diào)用一個進程的時間。近來許多處理器支持多種頁的大小。100主存命中率H隨著分配給該程序的主存容量S的增加而單調(diào)上升。在S比較小的時候，

H提高得非?？臁?/p>

隨著S的逐漸增

加，H提高的速

度逐漸降低。當(dāng)

S增加到某一個

值之后，H幾乎

不再提高。命中率H主存容量S1.02、主存容量與命中率的關(guān)系1013、頁面調(diào)度方式與命中率的關(guān)系請求式：

當(dāng)使用到的時候，再調(diào)入主存預(yù)取式：

在程序重新開始運行之前，把上次停止運行前一段時間內(nèi)用到的頁面先調(diào)入到主存儲器，然后才開始運行程序。

可以避免在程序開始運行時，頻繁發(fā)生頁面失效的情況。

如果調(diào)入的頁面用不上，浪費了調(diào)入的時間，占用了主存資源。102關(guān)于存儲層次的結(jié)構(gòu)必須解決的問題4：寫操作的實現(xiàn)思路？寫直達法、寫回法采用寫回法。對磁盤的訪問需要花費數(shù)百萬個時鐘周期，對下級存儲器冗余訪問的代價太高。所以虛擬存儲器系統(tǒng)通常包括一個重寫位來標(biāo)志裝入存儲器后被修改過的塊，在退出內(nèi)存的時候才寫磁盤。3.3高速緩沖存儲器3.3.1基本工作原理3.3.2地址映像與變換方法3.3.3Cache替換算法及其實現(xiàn)3.3.4Cache系統(tǒng)的加速比3.3.5Cache的一致性問題3.3.6Cache的預(yù)取算法1053.3.1Cache的基本工作原理Cache和主存均被分割成大小相同的塊。信息以塊為單位調(diào)入Cache。塊大小通常以一個存儲周期中能訪問的數(shù)據(jù)長度為限。106Cache工作原理高速緩沖存儲器主存儲器塊號B塊內(nèi)位移W主存/Cache

地址變換塊號b塊內(nèi)地址wCache替

換策略替換塊裝入塊已滿未滿未命中命中數(shù)據(jù)送CPU主存地址

來自CPU107存儲器層次結(jié)構(gòu)的四個基本問題1塊的放置——在內(nèi)存中的一個塊可以被放在Cache的什么地方？由映像規(guī)則來指明1083.3.2地址映像與變換地址映象：

把存放在主存中的程序按照某種規(guī)則裝入到Cache中，并建立主存地址與Cache地址之間的對應(yīng)關(guān)系地址變換：

當(dāng)程序已經(jīng)裝入到Cache之后，在實際運行過程中，把主存地址變換成Cache地址在選取地址映象方法要考慮的主要因素：

地址變換的硬件容易實現(xiàn)；地址變換的速度要快；Cache空間利用率要高；發(fā)生塊沖突的概率要小109全相聯(lián)：主存中的任一塊可以被放置到Cache中的任意一個位置。舉例特點：空間利用率最高，沖突概率最低，實現(xiàn)最復(fù)雜。1全相聯(lián)映象1101全相聯(lián)映像及其變換塊0Cache塊1……塊Cb-1塊0塊1……塊i……塊Mb-1主存儲器主存的任意一塊可以映象到Cache中的任意一塊。若Cache的塊數(shù)為Cb，主存的塊數(shù)為Mb，映象關(guān)系有Cb×Mb種有效位塊號B塊內(nèi)地址主存地址目錄表（由相聯(lián)存儲器組成，共Cb個字）主存塊號BB塊號b塊內(nèi)地址wCache塊號bb相聯(lián)比較命中Cache地址全相聯(lián)地址變換用硬件實現(xiàn)非常復(fù)雜1122直接映象直接映象：主存中的每一塊只能被放置到Cache中唯一的一個位置。舉例（循環(huán)分配）特點：空間利用率最低，沖突概率最高，實現(xiàn)最簡單。主存塊號為B，Cache塊號為b，則映像關(guān)系為:

b＝BmodCb

（Cb為Cache的塊數(shù)）113設(shè)Cb=2m，則當(dāng)表示為二進制數(shù)時，b實際上就是B的低m位:

Cb為Cache的塊數(shù)，b為Cache的塊號，B為主存的塊號。例子：Cb=8，則b為B中的低三位Cache地址與主存地址的低位完全相同bB：m位114塊0Cache塊1……塊Cb-1塊0……塊Cb-1主存儲器直接相聯(lián)映象方式塊Cb……塊2Cb-1塊Mb-Cb……塊Mb-1……區(qū)0區(qū)1區(qū)Me-1115區(qū)號Me=B/Cb（所得商的整數(shù)）塊號：b=BmodCb塊號BMeb塊內(nèi)偏移主存地址IndexTag1利用索引查表。2比較標(biāo)識是否相同，相同則意味著命中。有效位區(qū)號E塊內(nèi)地址w1主存

地址區(qū)表存儲器區(qū)號E(按地址訪問)E塊號b塊內(nèi)地址w命中Cache地址區(qū)內(nèi)塊號b相等比較塊失效比較相等且

有效位為1，

訪問Cache1、用主存地址中的塊號B去訪問區(qū)號存儲器，把讀出來的區(qū)號與主存地址中的區(qū)號E進行比較有效位區(qū)號E塊內(nèi)地址w1主存

地址區(qū)表存儲器區(qū)號E(按地址訪問)E塊號b塊內(nèi)地址w命中Cache地址區(qū)內(nèi)塊號b相等比較塊失效比較相等且

有效位為1，

訪問Cache2、比較結(jié)果相等,且有效位為1,則Cache命中。Cache地址與主存的低位地址完全相同。118其余情況均為Cache未命中：若區(qū)號比較相等，有效位為0：則此塊作廢。這時將主存中讀出的新塊按照Cache的塊地址裝入Cache中，并將有效位置1。若區(qū)號比較結(jié)果不相等，有效位為0，表示Cache的這一塊是空的。此時將從主存中讀出的新塊裝入Cache中，將有效位置1，同時將主存區(qū)號寫到區(qū)表存儲器的相應(yīng)單元中。若區(qū)號比較結(jié)果不相等，但是有效位為1，表示原來在Cache中存放的那一塊是有效的。此時要先將這一塊寫到主存儲器的對應(yīng)單元中，將新塊裝入。同時將主存的區(qū)號寫到區(qū)號存儲器的相應(yīng)單元中。119直接映象方法的主要優(yōu)點：

硬件實現(xiàn)很簡單,不需要相聯(lián)訪問存儲器

訪問速度也比較快,實際上不做地址變換直接映象方式的主要缺點:

塊的沖突率較高有效位區(qū)號E塊內(nèi)地址w1按地址訪問的Cache區(qū)號E塊號b塊內(nèi)地址w相等塊號B相等比較訪主存數(shù)據(jù)0D0數(shù)據(jù)1D1…………數(shù)據(jù)w-1Dw-11/w…送CPU返回1213組相聯(lián)映象組相聯(lián)：主存中的每一塊可以被放置到Cache中唯一的一個組中的任何一個位置。

組相聯(lián)是直接映象和全相聯(lián)的一種折衷組0組1組2組3組0組1組2組3區(qū)0區(qū)11主存的組和Cache的組采用直接映像方式。2在主存的一組與Cache的一組建立了直接映像方式后，兩個對應(yīng)的組內(nèi)部采用全相聯(lián)映像方式。組0組1組2組3組0組1組2組3區(qū)0區(qū)1主存的第0組只能進入Cache的0組，主存的第1組只能進入Cache的1組。而組內(nèi)的各塊如0、1和8、9可以進入Cache的0、1中任意一塊。區(qū)號主存地址組號組內(nèi)塊號塊內(nèi)偏移Cache地址組號組內(nèi)塊號塊內(nèi)偏移

組相聯(lián)映象的地址變換用組號G按地址訪問塊表存儲器。從中讀出一組字，字的個數(shù)等于組內(nèi)塊數(shù)Gb。

組相聯(lián)映象的地址變換將主存地址中的區(qū)號E和塊號B進行相聯(lián)比較，若相等，則Cache命中。此時將該單元中的Cache的塊號b取出，與組號G（G=g）和塊內(nèi)偏移w拼接就得到了Cache地址。

提高Cache訪問速度的一種方法：用多個相等比較器來代替相聯(lián)訪問位選擇組相聯(lián)映射組相聯(lián)映像

位選擇組相聯(lián)的地址映象規(guī)則主存中的一個組與Cache的一個組之間是多個塊到多個塊的映像。主存中的一個塊到Cache的一個組之間是一個塊到多個塊的映像，映像關(guān)系更為簡單，實現(xiàn)起來更容易一些。130組的選擇常采用位選擇算法若主存第i

塊映象到第k

組，則:

k＝imod（G）（G為Cache的組數(shù)）設(shè)G＝2g，則當(dāng)表示為二進制數(shù)時，k實際上就是i的低g位:低g位以及直接映象中的低m位通常稱為索引。

ki：g位n路組相聯(lián)：每組中有n個塊(n＝M/G)。

n稱為相聯(lián)度。相聯(lián)度越高，Cache空間的利用率就越高，塊沖突概率就越低，不命中率也就越低。絕大多數(shù)計算機的Cache:n≤4想一想：相聯(lián)度一定是越大越好？全相聯(lián)直接映象

組相聯(lián)n(路數(shù))G(組數(shù))MM111＜n＜M1＜G＜M當(dāng)CPU訪問Cache時，如何確定Cache中是否有所要訪問的塊？若有的話，如何確定其位置？通過查找目錄表來實現(xiàn)目錄表的結(jié)構(gòu)主存塊的塊地址的高位部分，稱為標(biāo)識。每個主存塊能唯一地由其標(biāo)識來確定查找算法只需查找候選位置所對應(yīng)的目錄表項并行查找與順序查找提高性能的重要思想：主候選位置(MRU塊)

（前瞻執(zhí)行）并行查找的實現(xiàn)方法相聯(lián)存儲器目錄由2g個相聯(lián)存儲區(qū)構(gòu)成，每個相聯(lián)存儲區(qū)的大小為n×（h+log2n）位。根據(jù)所查找到的組內(nèi)塊地址，從Cache存儲體中讀出的多個信息字中選一個，發(fā)送給CPU。

單體多字存儲器＋比較器舉例：４路組相聯(lián)并行標(biāo)識比較（比較器的個數(shù)及位數(shù)）４路組相聯(lián)Cache的查找過程直接映象Cache的查找過程優(yōu)缺點不必采用相聯(lián)存儲器，而是用按地址訪問的存儲器來實現(xiàn)。所需要的硬件為：大小為2g×n×h位的存儲器和n個h位的比較器。當(dāng)相聯(lián)度n增加時，不僅比較器的個數(shù)會增加，而且比較器的位數(shù)也會增加。138相聯(lián)度概念：Cache分組中每組的塊數(shù)。相聯(lián)度越高，Cache空間的利用率就越高，塊沖突概率就越低，不命中率也就越低。相聯(lián)度一定是越大越好？當(dāng)相聯(lián)度為Cb時，則為全相聯(lián)映像；當(dāng)相聯(lián)度為1時，則為組相聯(lián)映像139組相聯(lián)映象方式的優(yōu)點：

塊的沖突概率比較低

塊的利用率大幅度提高

塊失效率明顯降低組相聯(lián)映象方式的缺點：

實現(xiàn)難度和造價要比直接映象方式高140存儲器層次結(jié)構(gòu)的四個問題3發(fā)生Cache失效，哪個塊應(yīng)該被替換？替換算法。141所要解決的問題：當(dāng)新調(diào)入一塊，而Cache又已被占滿時，替換哪一塊？直接映象Cache中的替換不存在選擇問題在組相聯(lián)和全相聯(lián)Cache中，則有多個塊供選擇。主要的替換算法有三種隨機法優(yōu)點：實現(xiàn)簡單先進先出法FIFO3.3.3Cache替換算法及其實現(xiàn)142最近最少使用法LRU選擇近期最少被訪問的塊作為被替換的塊。

（實現(xiàn)比較困難）實際上：選擇最久沒有被訪問過的塊作為被替換的塊。即LFU

優(yōu)點：命中率較高143LRU和隨機法分別因其不命中率低和實現(xiàn)簡單而被廣泛采用。模擬數(shù)據(jù)表明，對于容量很大的Cache，LRU和隨機法的命中率差別不大。對于小容量的Cache，LRU替換策略最優(yōu)，F(xiàn)IFO比隨機算法性能略好一點。Cache替換算法的主要特點：全部用硬件實現(xiàn)144堆棧法用一個堆棧來記錄組相聯(lián)Cache的同一組中各塊被訪問的先后次序。用堆棧元素的物理位置來反映先后次序棧底記錄的是該組中最早被訪問過的塊，次棧底記錄的是該組中第二個被訪問過的塊，…，棧頂記錄的是剛訪問過的塊。當(dāng)需要替換時，從棧底得到應(yīng)該被替換的塊（塊地址）。LRU算法的硬件實現(xiàn)145146堆棧中的內(nèi)容必須動態(tài)更新當(dāng)Cache訪問命中時，通過用塊地址進行相聯(lián)查找，在堆棧中找到相應(yīng)的元素，然后把該元素的上面的所有元素下壓一個位置，同時把本次訪問的塊地址抽出來，從最上面壓入棧頂。而該元素下面的所有元素則保持不動。如果Cache訪問不命中，則把本次訪問的塊地址從最上面壓入棧頂，堆棧中所有原來的元素都下移一個位置。如果Cache中該組已經(jīng)沒有空閑塊，就要替換一個塊。這時從棧底被擠出去的塊地址就是需要被替換的塊的塊地址。147存儲器層次結(jié)構(gòu)的問題4寫操作時會發(fā)生什么？148和“讀”操作不同，“寫”操作必須在確認(rèn)是命中后才可進行寫通常比讀會花費更長的時間：寫無法和檢查標(biāo)識同時進行。并且處理器必須給出要寫的數(shù)據(jù)的大?。ㄍǔＴ?到8字節(jié)之間），只有塊中的這一部分可以被改寫。但是讀可以讀取比所需字節(jié)數(shù)更多的信息。“寫”訪問有可能導(dǎo)致Cache和主存內(nèi)容的不一致兩種寫策略寫直達法寫回法

149寫策略是區(qū)分不同Cache設(shè)計方案的一個重要標(biāo)志。寫直達法執(zhí)行“寫”操作時，不僅寫入Cache，而且也寫入內(nèi)存。寫回法執(zhí)行“寫”操作時，只寫入Cache。僅當(dāng)Cache中相應(yīng)的塊被替換時，才寫回主存。(設(shè)置“修改位”)

150寫回法與寫直達法的比較在寫回法中，對同一塊中的多次寫操作僅僅需要對下層存儲器一次操作，所以寫回法需要較小的存儲帶寬，在多處理器的服務(wù)器系統(tǒng)中更具有吸引力。同時，對其他存儲層次和存儲總線使用較少，節(jié)省了功耗，因而非常適用于嵌入式應(yīng)用程序。寫直達法比寫回法更易實現(xiàn)。并且下一級存儲有最新的當(dāng)前數(shù)據(jù)副本，簡化了數(shù)據(jù)的一致性。這對處理器和I/O都非常重要。因為寫操作不需要數(shù)據(jù)，所以在寫訪問Cache不命中時，通常采用兩種策略：151“寫”操作時的調(diào)塊按寫分配(寫時取)寫不命中時，先把所寫單元所在的塊調(diào)入Cache，再行寫入。不按寫分配(繞寫法)寫不命中時，直接寫入下一級存儲器而不調(diào)塊。寫策略與調(diào)塊寫回法──按寫分配寫直達法──不按寫分配152DEC的AlphaAXP21064中的內(nèi)部數(shù)據(jù)Cache153參數(shù)：容量：8KB塊大小：32B塊數(shù)：256映象方法：直接映象寫緩沖器大?。?個塊主存地址位數(shù)：34位寫策略：寫直達法地址分析154工作過程“讀”訪問命中（完成4步需要2個時鐘周期）“寫”訪問命中155設(shè)置了一個寫緩沖器（提高“寫”訪問的速度）按字尋址的，它含有4個塊，每塊大小為4個字。當(dāng)要進行寫入操作時，如果寫緩沖器不滿，那么就把數(shù)據(jù)和完整的地址寫入緩沖器。對CPU而言，本次“寫”訪問已完成，CPU可以繼續(xù)往下執(zhí)行。由寫緩沖器負(fù)責(zé)把該數(shù)據(jù)寫入主存。在寫入緩沖器時，要進行寫合并檢查。即檢查本次寫入數(shù)據(jù)的地址是否與緩沖器內(nèi)某個有效塊的地址匹配。如果匹配，就把新數(shù)據(jù)與該塊合并。156發(fā)生讀不命中與寫不命中時的操作讀不命中：向CPU發(fā)出一個暫停信號，通知它等待，并從下一級存儲器中新調(diào)入一個數(shù)據(jù)塊（32字節(jié)）。寫不命中：采用寫直達法（不按寫分配的策略），將使數(shù)據(jù)直接寫入主存。157AMDopteron處理器中的數(shù)據(jù)Cache容量：64KB

塊大小：64字節(jié)

LRU替換策略

主要區(qū)別采用2路組相聯(lián)采用寫回法

沒有寫緩沖器主存地址：40位（減少地址也可以簡化虛地址映射設(shè)計）159Cache性能分析：不能純粹通過命中率來評價Cache存儲系統(tǒng)。通過平均訪問時間評價：平均訪問時間=命中時間+不命中率×不命中開銷可以從三個方面來提高Cache的性能：