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

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

3.2虛擬存儲(chǔ)器

3.3高速緩沖存儲(chǔ)器

3.4三級(jí)存儲(chǔ)系統(tǒng)

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

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

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

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

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

訪問速度的比值

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

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

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

當(dāng)H＝0.99時(shí)，

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

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

H是原來的命中率

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

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

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

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

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

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

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

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

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

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

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

把磁盤存儲(chǔ)器實(shí)地址和主存儲(chǔ)器實(shí)頁號(hào)送入輸入輸出處理機(jī)

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

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

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

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

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

0段表

長度段表

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

位段長訪問

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

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

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

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

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

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

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

(2)頁表相對比較簡單

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

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

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

地址變換方法：先查段表，得到頁表起始地址和頁表長度，再查頁表找到要訪問的主存實(shí)頁號(hào)，把實(shí)頁號(hào)p與頁內(nèi)偏移d拼接得到主存實(shí)地址。77采用段頁式，可以不必連續(xù)存儲(chǔ)，簡化了替換操作，也不需要整個(gè)段都存放在內(nèi)存中?，F(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)作一種異常故障來處理。每個(gè)用戶程序都有一張外頁表，虛擬地址空間中的每一頁或每個(gè)程序段，在外頁表中都有對應(yīng)的一個(gè)存儲(chǔ)字。每一個(gè)存儲(chǔ)字除了磁盤存儲(chǔ)器的地址之外，至少還包括一個(gè)裝入位。79裝入磁盤實(shí)地址用戶號(hào)頁內(nèi)偏移1虛頁號(hào)外部地址

變換（軟

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

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

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

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

一是命中率要高

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

(FIFOfirst-infirst-outalgorithm)

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

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

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

假設(shè)分配給這個(gè)程序的主存儲(chǔ)器共有3個(gè)頁面。給出FIFO、LRU、OPT三種頁面替換算法對這3頁主存的使用情況，包括調(diào)入、替換和命中等。92顛簸對于循環(huán)程序，一次使用P1、P2、P3、P4四個(gè)頁面，主存分配了3個(gè)頁面，在使用FIFO和LRU算法調(diào)度時(shí)，可能出現(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)主存儲(chǔ)器的容量

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

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

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

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

當(dāng)頁面大小

減小時(shí)，頁表和

頁面表在主存儲(chǔ)

器中所占的比例

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

H提高得非常快。

隨著S的逐漸增

加，H提高的速

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

S增加到某一個(gè)

值之后，H幾乎

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

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

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

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

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

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

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

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

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

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

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

b＝BmodCb

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

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

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

有效位為1，

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

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

有效位為1，

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

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

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

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

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

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

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

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

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

塊映象到第k

組，則:

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

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

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

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

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

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

塊的沖突概率比較低

塊的利用率大幅度提高

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

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

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

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

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

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

塊大?。?4字節(jié)

LRU替換策略

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

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