存儲(chǔ)系統(tǒng)必修課公開課一等獎(jiǎng)優(yōu)質(zhì)課大賽微課獲獎(jiǎng)?wù)n件

1、第4章 存放系統(tǒng)教學(xué)目標(biāo)與要求：了解：?jiǎn)误w多字并行存放器和交叉編址并行存放器工作原理； 了解：程序局部性和存放器系統(tǒng)層次結(jié)構(gòu)及其性能指標(biāo)掌握：存放體系組成及其設(shè)計(jì)標(biāo)準(zhǔn)訪存局部性原理。Cache基本結(jié)構(gòu)和工作原理，研究地址映象與變換、替換策略和更新策略工作原理和設(shè)計(jì)方法，分析影響Cache性能指標(biāo)原因及優(yōu)化方法。先進(jìn)Cache結(jié)構(gòu)和一致性處理方法。虛擬存放器結(jié)構(gòu)與實(shí)現(xiàn)技術(shù)。 第1頁(yè)第4章 存放系統(tǒng)教學(xué)目標(biāo)與要求：重點(diǎn)：地址映象與變換、替換策略和更新策略工作原理和設(shè)計(jì)方法；頁(yè)式存放器工作原理及替換算法；Cache存放器3種地址映象規(guī)則以及對(duì)應(yīng)地址變換方法難點(diǎn)：虛擬存放器和Cache存放器地址映象規(guī)

2、則以及對(duì)應(yīng)地址變換方法第2頁(yè)4.1存放系統(tǒng)層次結(jié)構(gòu)與性能指標(biāo) 長(zhǎng)久存在問(wèn)題：在合理總價(jià)格限制下，單純性主存設(shè)備速度跟不上CPU發(fā)展，容量不能滿足軟件尺寸擴(kuò)大。 本章學(xué)習(xí)兩種提升主存系統(tǒng)性能/價(jià)格比結(jié)構(gòu)化方法：并行存放器與存放層次技術(shù)。后者為主。 存放系統(tǒng)設(shè)計(jì)目標(biāo)：以較小成本使存放系統(tǒng)工作速度與處理機(jī)速度相匹配；同時(shí)要求存放系統(tǒng)有盡可能大容量；價(jià)格盡可能低。 存放系統(tǒng)定義 兩個(gè)或兩個(gè)以上速度、容量和價(jià)格各不相同存放器用硬件、軟件、或軟件與硬件相組合方法連接起來(lái)成為一個(gè)存放系統(tǒng)。 特點(diǎn)：這個(gè)存放系統(tǒng)對(duì)應(yīng)用程序員是透明，而且，從應(yīng)用程序員角度看，它是一個(gè)存放器，這個(gè)存放器速度靠近速度最快那個(gè)存放器，

3、存放容量與容量最大那個(gè)相等，單位容量?jī)r(jià)格靠近最廉價(jià)那個(gè)存放器。第3頁(yè)4.1存放系統(tǒng)層次結(jié)構(gòu)與性能指標(biāo)一、存放系統(tǒng)層次結(jié)構(gòu)基本概念與定義： 時(shí)間局部性：程序最近未來(lái)要用到信息很可能是現(xiàn)在正在使用信息 空間局部性：程序最近未來(lái)要用到信息很可能出現(xiàn)在正在使用信息在存放空間位置上是相鄰。 存放容量S：以字節(jié)數(shù)表示，單位為B、KB、MB、GB、TB等。 存放器速度T：存放器訪問(wèn)周期，與命中率相關(guān)。 存放器價(jià)格C：表示單位容量平均價(jià)值單位為C/bit或C/KB。計(jì)算機(jī)存放系統(tǒng)三個(gè)基本參數(shù)：第4頁(yè)4.1存放系統(tǒng)層次結(jié)構(gòu)與性能指標(biāo)1. 從用戶角度來(lái)看，存放器三個(gè)主要指標(biāo)是： 容量，速度，價(jià)格(每位價(jià)格)2.

4、人們對(duì)這三個(gè)指標(biāo)期望：這個(gè)存放器速度靠近速度最快那個(gè)存放器，存放容量與容量最大那個(gè)相等，單位容量?jī)r(jià)格靠近最廉價(jià)那個(gè)存放器。3. 這三個(gè)指標(biāo)相互矛盾4. 處理方法： 采取各種存放器技術(shù)，組成存放層次。 演示 演示 (局部性原理)第5頁(yè)4.1存放系統(tǒng)層次結(jié)構(gòu)與性能指標(biāo)一、存放系統(tǒng)層次結(jié)構(gòu)第6頁(yè)第一層第二層第三層第四層第五層存放系統(tǒng)層次結(jié)構(gòu)速 度 提 高容 量 增 加 通用存放器M1高速緩沖存放器M2 主存放器M3 脫機(jī)大容量存放器M5 輔助存放器M4 每級(jí)存放器性能參數(shù)能夠表示為Ti，Si，Ci。存放系統(tǒng)性能可表示為：TiTi+1；SiCi+1。第7頁(yè)4.1存放系統(tǒng)層次結(jié)構(gòu)與性能指標(biāo)第8頁(yè)4.1存

5、放系統(tǒng)層次結(jié)構(gòu)與性能指標(biāo)一、存放系統(tǒng)層次結(jié)構(gòu) 三級(jí)存放系統(tǒng)：當(dāng)前多數(shù)計(jì)算機(jī)有Cache、主存放器和輔存組成。它一個(gè)實(shí)現(xiàn)方式是組織成2個(gè)獨(dú)立二級(jí)存放器。1. 從主存角度來(lái)看 “Cache主存”層次：填補(bǔ)主存速度不足 “主存輔存”層次： 填補(bǔ)主存容量不足2. “Cache主存”層次 主存與CPU速度差距第9頁(yè)4.1存放系統(tǒng)層次結(jié)構(gòu)與性能指標(biāo)第10頁(yè) “Cache - 主存”層次第11頁(yè)3. “主存輔存”層次第12頁(yè)4.1存放系統(tǒng)層次結(jié)構(gòu)與性能指標(biāo)存放層次CPU對(duì)第二級(jí)訪問(wèn)方式比較項(xiàng)目目存放管理實(shí)現(xiàn) 訪問(wèn)速度比值(第一級(jí)和第二級(jí))經(jīng)典塊(頁(yè))大小失效時(shí)CPU是否切換“Cache 主存”層次“主存輔存

6、”層次為了填補(bǔ)主存速度不足為了填補(bǔ)主存容量不足主要由專用硬件實(shí)現(xiàn)主要由軟件實(shí)現(xiàn)幾比一幾百比一幾十個(gè)字節(jié)幾百到幾千個(gè)字節(jié)可直接訪問(wèn)均經(jīng)過(guò)第一級(jí)不切換切換到其它進(jìn)程“Cache主存”與“主存輔存”層次區(qū)分第13頁(yè)4.1存放系統(tǒng)層次結(jié)構(gòu)與性能指標(biāo)二、存放系統(tǒng)性能指標(biāo) 1.存放系統(tǒng)容量S要求：提供盡可能大地址空間，（靠近M2）能進(jìn)行隨機(jī)訪問(wèn)2.存放器帶寬：存放器提供數(shù)據(jù)傳輸速率3.每位價(jià)格C 設(shè)：S 容量 TA 訪問(wèn)時(shí)間 C 每位價(jià)格下面僅考慮由M1和M2組成兩級(jí)存放層次： M1參數(shù)：S1，TA1，C1 M2參數(shù)：S2，TA2，C2則每位價(jià)格C： C C1S1C2S2S1S2第14頁(yè)4.1存放系統(tǒng)層次

7、結(jié)構(gòu)與性能指標(biāo)二、存放系統(tǒng)性能指標(biāo) 4. 命中率 H 和失效率 F 命中率H定義為CPU產(chǎn)生邏輯地址在存放器M1中訪問(wèn)到指定信息概率。HN1/(N1N2) N1 訪問(wèn)M1次數(shù) N2 訪問(wèn)M2次數(shù) 失效率 F1H第15頁(yè)4.1存放系統(tǒng)層次結(jié)構(gòu)與性能指標(biāo)第16頁(yè)4.1存放系統(tǒng)層次結(jié)構(gòu)與性能指標(biāo)二、存放系統(tǒng)性能指標(biāo) 5. 等效訪問(wèn)周期T（平均訪問(wèn)時(shí)間）二級(jí)存放器等效訪問(wèn)周期T為 THT1(1H )T2T1 M1存放器訪問(wèn)周期 T2 M2存放器訪問(wèn)周期第17頁(yè)4.1存放系統(tǒng)層次結(jié)構(gòu)與性能指標(biāo)第18頁(yè)4.1存放系統(tǒng)層次結(jié)構(gòu)與性能指標(biāo)二、存放系統(tǒng)性能指標(biāo) 6. 訪問(wèn)效率二級(jí)存放器訪問(wèn)效率為T1 M1存放器

8、訪問(wèn)周期 T2 M2存放器訪問(wèn)周期e T1HT1(1-H)T2T1T第19頁(yè)4.2 并行存放器一、單體多字并行存放器 頻帶寬度：?jiǎn)挝粫r(shí)間內(nèi)所能訪問(wèn)數(shù)據(jù)量。并行存放器：在一個(gè)存放器訪問(wèn)周期內(nèi)能并行訪問(wèn)到多個(gè)存放字存放器，能有效提升帶寬。第20頁(yè)4.2 并行存放器一、單體多字并行存放器 定義：把存放器存放字長(zhǎng)增加n倍，以存放n個(gè)指令字或數(shù)據(jù)字 優(yōu)點(diǎn)：簡(jiǎn)單、輕易。缺點(diǎn)：訪問(wèn)沖突大。主要沖突：取指令沖突（條件轉(zhuǎn)移時(shí)）讀操作數(shù)沖突（需要多個(gè)操作數(shù)不一定都存放在同一個(gè)存放字中）寫數(shù)據(jù)沖突（必須湊齊n個(gè)數(shù)才一起寫入存放器）讀寫沖突（要讀出一個(gè)字和要寫入一個(gè)字處于同一個(gè)存放字內(nèi)時(shí)，無(wú)法在一個(gè)存放周期內(nèi)完成）。

9、第21頁(yè)4.2 并行存放器e T1HT1(1-H)T2T1T第22頁(yè)4.2 并行存放器二、多體并行存放器 定義：指由多個(gè)存放體組成一個(gè)更大容量主存。方法：采取交叉編址方式分類：1.地址碼高位交叉編址 2.地址碼地位交叉編址第23頁(yè)4.2 并行存放器e T1HT1(1-H)T2T1T第24頁(yè)一、高位交叉訪問(wèn) 低位部分：體內(nèi)地址 b=log2n高位部分：存放體體號(hào) a=log2mm: 體數(shù)n：每個(gè)體容量數(shù)據(jù)總線地址總線 WMDR0 0 1 2 3 n-1MDR1 n n+1 n+2 n+3 2n-1MAR0MAR3MDRm-1n(m-1)n(m-1)+1n(m-1)+2n(m-1)+3 n(m-1

10、)MARm-1譯碼 a b第25頁(yè)二、低位交叉訪問(wèn) 低位交叉存放器結(jié)構(gòu) 低位部分：存放體體號(hào) b=log2m高位部分：體內(nèi)地址 a=log2n W MDR0 0 m 2m 3m (n-1)m MDR1 1 m+1 2m+1 3m+1 (n-1)m+1MAR0MAR3 MDRm-1 m-1 2m-1 3m-1 4m-1 nm-1 MARm-1譯碼 a b數(shù)據(jù)總線地址總線分時(shí)訪問(wèn)第26頁(yè)比如，n=8 m=4多體并行低位交叉編址 012345678910111213141516171819202122232425262728293031 b a09182712510304個(gè)體并行2個(gè)體并行第27頁(yè)存

11、放層次四個(gè)問(wèn)題當(dāng)把一個(gè)塊調(diào)入高一層(靠近CPU)存放器時(shí)，能夠放在哪些位置上? (地址映象，映象規(guī)則)實(shí)際運(yùn)行中，地址怎樣找到? (地址變換，查找算法)3. 當(dāng)發(fā)生失效時(shí)，應(yīng)替換哪一塊？ (替換算法)4. 當(dāng)進(jìn)行寫訪問(wèn)時(shí)，應(yīng)進(jìn)行哪些操作? (寫策略)1. 2.并行存放器與存放層次技術(shù)存放層次技術(shù)：虛擬存放器、Cache存放器第28頁(yè)4.3 虛擬存放器基本概念 虛空間：程序所能利用空間。又稱虛存空間或虛擬存放器空間，它是應(yīng)用程序員用來(lái)編寫程序地址空間，這個(gè)地址空間非常大。虛地址：虛存空間上地址，又稱為虛存地址。編程序時(shí)程序員所用地址，在編譯程序中由處理機(jī)生成。一個(gè)用戶程序要訪問(wèn)虛擬存放器時(shí)，必須

12、給出多用戶虛地址主存放器地址空間：也稱主存地址空間、主存物理空間或?qū)嵈娴刂房臻g實(shí)地址：主存物理空間編址；又稱為主存實(shí)地址、主存物理地址、主存放器地址輔存地址空間：也就是磁盤存放器地址空間磁盤存放器地址：又稱為磁盤地址、輔存地址 第29頁(yè)4.3 虛擬存放器基本概念： 地址映象：虛地址與實(shí)地址之間對(duì)應(yīng)關(guān)系規(guī)則 地址變換：在程序被裝入主存放器之后，在實(shí)際運(yùn)行時(shí)，把多用戶虛地址變換成主存實(shí)地址（內(nèi)部地址變換）或磁盤存放器地址（外部地址變換）。 訪問(wèn)失效：按虛地址訪問(wèn)數(shù)據(jù)不在主存中（未命中） 外部地址變換：訪問(wèn)失效時(shí)，需要訪問(wèn)磁盤存放器，這時(shí)把虛地址變換為磁盤存放器物理地址（普通為軟件實(shí)現(xiàn)） 內(nèi)部地址變

13、換：把虛地址變換為主存物理地址 主存沖突：有新數(shù)據(jù)調(diào)入，主存卻沒有對(duì)應(yīng)空閑位置 替換算法：當(dāng)發(fā)生主存沖突時(shí)，應(yīng)替換主存哪一塊 地址變換和替換算法是虛擬存放器兩個(gè)主要技術(shù)第30頁(yè) 1961年英國(guó)曼徹斯特大學(xué)Kilbrn等人提出。到了70年代被廣泛地應(yīng)用于大中型計(jì)算機(jī)系統(tǒng)中。當(dāng)前，許多小型計(jì)算機(jī)，甚至微型機(jī)也開始使用虛擬存放器。 4.3.1虛擬存放器地址映象與地址變換4.3.2頁(yè)面替換算法及其命中率4.3 虛擬存放器第31頁(yè)4.3 虛擬存放器虛擬存放器由主存放器和聯(lián)機(jī)工作外部存放器共同組成。把主存放器、磁盤存放器和虛擬存放器都劃分成固定大小頁(yè) 主存放器頁(yè)稱為實(shí)頁(yè)，虛擬存放器中頁(yè)稱為虛頁(yè)。一個(gè)主存地

14、址A由兩部分組成，實(shí)頁(yè)號(hào)p和頁(yè)內(nèi)偏移d一個(gè)虛地址Av由三部分組成，用戶號(hào)U、虛頁(yè)號(hào)P和頁(yè)內(nèi)偏移D第32頁(yè)一個(gè)用戶程序要訪問(wèn)虛擬存放器時(shí)，必須給出多用戶虛擬地址Av。內(nèi)部地址變換： (1)多用戶虛擬地址Av變換成實(shí)地址A (2)多用戶虛擬地址中頁(yè)內(nèi)偏移D直接作為主存實(shí)地址中頁(yè)內(nèi)偏移d (3)主存實(shí)頁(yè)號(hào)與它頁(yè)內(nèi)偏移d直接拼接起來(lái)就得到主存實(shí)地址A第33頁(yè)外部地址變換：首先查外頁(yè)表得到磁盤存放器實(shí)地址把磁盤存放器實(shí)地址和主存放器實(shí)頁(yè)號(hào)送入輸入輸出處理機(jī)把要訪問(wèn)數(shù)據(jù)所在一整頁(yè)都從磁盤存放器調(diào)入到主存放器第34頁(yè)4.3 虛擬存放器第35頁(yè)4.3 虛擬存放器 CPU存放管理主存 輔 存I或DI或DVAPA

15、外存地址虛擬存放器中CPU、MS、輔存間關(guān)系 第36頁(yè)4.3.1 地址映象與變換虛擬存放器中有三種地址空間，虛擬地址空間，主存放器地址空間，輔存地址空間 虛擬地址空間：又稱虛存空間或虛擬存放器空間，它是應(yīng)用程序員用來(lái)編寫程序地址空間，這個(gè)地址空間非常大。主存放器地址空間：也稱主存地址空間、主存物理空間或?qū)嵈娴刂房臻g輔存地址空間：也就是磁盤存放器地址空間虛擬地址：虛存空間上地址，又稱為虛存地址或者虛地址主存地址：又稱為主存實(shí)地址、主存物理地址、主存放器地址磁盤存放器地址：又稱為磁盤地址、輔存地址第37頁(yè)地址映像：把虛擬地址空間映象到主存地址空間，詳細(xì)地說(shuō)，就是把用戶用虛擬地址編寫程序按照某種規(guī)則

16、裝入到主存放器中，并建立多用戶虛地址與主存實(shí)地址之間對(duì)應(yīng)關(guān)系。地址變換：在程序被裝入主存放器之后，在實(shí)際運(yùn)行時(shí)，把多用戶虛地址變換成主存實(shí)地址（內(nèi)部地址變換）或磁盤存放器地址（外部地址變換）。第38頁(yè)4.3 虛擬存放器一、虛擬存放器地址變換 虛擬存放器能夠分為三類：段式，頁(yè)式、段頁(yè)式1.段式虛擬存放器地址映象和地址變換地址映象方法：每個(gè)程序段都從0地址開始編址，長(zhǎng)度可長(zhǎng)可短，能夠在程序執(zhí)行過(guò)程中動(dòng)態(tài)改變程序段長(zhǎng)度 第39頁(yè)4.3 虛擬存放器一、虛擬存放器地址變換1.段式虛擬存放器地址變換 每個(gè)程序都用一個(gè)段表（通常在主存中）來(lái)存放該程序各段裝入主存相關(guān)信息地址變換方法：由用戶號(hào)找到基址存放器（

17、CPU內(nèi)）從基址存放器中讀出段表起始地址把起始地址與多用戶虛擬地址中段號(hào)相加得到段表地址把段表中給出起始地址與段內(nèi)偏移D相加就能得到主存實(shí)地址 第40頁(yè)4.3 虛擬存放器一、虛擬存放器地址變換1.段式虛擬存放器地址變換地址變換方法圖示第41頁(yè)4.3 虛擬存放器 段式管理主要優(yōu)點(diǎn)： 程序模塊化性能好，各段在功效上是相互獨(dú)立； 便于程序與數(shù)據(jù)共享； 程序動(dòng)態(tài)鏈接比較輕易； 便于實(shí)現(xiàn)存放保護(hù)。地址變換所需時(shí)間比較長(zhǎng)。 主存空間利用不充分。對(duì)輔存(磁盤)管理比較困難。段式管理主要缺點(diǎn)：第42頁(yè)4.3 虛擬存放器一、虛擬存放器地址變換2.頁(yè)式虛擬存放器地址映象和地址變換地址映象方法：把虛擬地址空間劃分成

18、一個(gè)個(gè)固定大小塊，每塊稱為一頁(yè)（Page），把主存放器地址空間也按虛擬地址空間一樣大小劃分為頁(yè)。頁(yè)是一個(gè)邏輯上劃分，它能夠由系統(tǒng)管理軟件任意指定。 第43頁(yè)4.3 虛擬存放器一、虛擬存放器地址變換2.頁(yè)式虛擬存放器地址映象和地址變換每個(gè)程序都用一個(gè)頁(yè)表（通常在主存中）來(lái)存放該程序各個(gè)虛頁(yè)裝入主存實(shí)頁(yè)位置等相關(guān)信息地址變換方法：由用戶號(hào)找到基址存放器（CPU內(nèi)）從基址存放器中讀出頁(yè)表基地址Pa把頁(yè)表基地址Pa與多用戶虛擬地址中頁(yè)號(hào)P相加得到頁(yè)表地址把頁(yè)表中給出主存實(shí)頁(yè)號(hào)p與虛地址中頁(yè)內(nèi)偏移D拼接起來(lái)就得到主存實(shí)地址A 第44頁(yè)4.3 虛擬存放器第45頁(yè)4.3 虛擬存放器一、虛擬存放器地址變換2.

19、頁(yè)式虛擬存放器地址映象和地址變換 頁(yè)式管理主要優(yōu)點(diǎn)1、 主存放器利用率比較高 2、 頁(yè)表相對(duì)比較簡(jiǎn)單 3、 地址映象和變換速度比較快 4、 對(duì)輔存（磁盤存放器）管理比較輕易 頁(yè)式管理主要缺點(diǎn) 1、 程序模塊化性能不好 2、 頁(yè)表很長(zhǎng)，需要占用很大存放空間第46頁(yè)4.3 虛擬存放器一、虛擬存放器地址變換3.段頁(yè)式虛擬存放器地址映象和地址變換 其基本思想是對(duì)用戶原來(lái)編寫程序虛擬存放空間采取分段方法管理 ，每個(gè)程序段分成幾個(gè)固定大小頁(yè)。地址變換方法：1.先查段表，得到該程序段頁(yè)表起始地址和頁(yè)表長(zhǎng)度2.再查頁(yè)表找到要訪問(wèn)主存實(shí)頁(yè)號(hào)3.最終把實(shí)頁(yè)號(hào)p與頁(yè)內(nèi)偏移d拼接得到主存實(shí)地址第47頁(yè)4.3 虛擬存放

20、器3.段頁(yè)式虛擬存放器地址映象和地址變換 頁(yè)式管理主要優(yōu)點(diǎn)1、 主存放器利用率比較高 第48頁(yè)第49頁(yè) 外部地址變換目標(biāo)是要找到輔存（磁盤存放器）實(shí)地址，而且把需要訪問(wèn)那一頁(yè)或那一個(gè)程序段調(diào)入到主存放器中。在操作系統(tǒng)中，通常把頁(yè)面失效看成一個(gè)異常故障來(lái)處理。 每個(gè)用戶程序都有一張外頁(yè)表，虛擬地址空間中每一頁(yè)或每個(gè)程序段，在外頁(yè)表中都有對(duì)應(yīng)一個(gè)存放字。每一個(gè)存放字除了磁盤存放器地址之外，最少還包含一個(gè)裝入位 第50頁(yè)4.3 虛擬存放器一、虛擬存放器地址變換4.加緊地址變換方法 1.目錄表基本思想是：壓縮頁(yè)表存放容量，用一個(gè)容量比較小高速存放器來(lái)存放頁(yè)表，從而加緊頁(yè)表查表速度。第51頁(yè)4.3 虛擬

21、存放器一、虛擬存放器地址變換4.加緊地址變換方法 2.快慢表 用多用戶虛頁(yè)號(hào)同時(shí)去查快表和慢表。因?yàn)榭毂聿楸硭俣纫嚷砜斓枚?，假如在快表中查到與多用戶虛地址相等存放字，就馬上終止慢表查表過(guò)程，并讀出該存放字中實(shí)頁(yè)號(hào)p送入到主存放器地址存放器中。假如在快表中沒有查到，就到存放在主存放器中慢表中去找。假如在慢表中查到了，則把查到實(shí)頁(yè)號(hào)p送入主存放器地址存放器，同時(shí)，也把這個(gè)實(shí)頁(yè)號(hào)連同多用戶虛地址等信息送入快表中。這時(shí)，若快表已滿，則要采取某種替換算法，替換掉其中一個(gè)不慣用存放字。 第52頁(yè)4.3 虛擬存放器一、虛擬存放器地址變換4.加緊地址變換方法快慢表：快表：TLB（translation L

22、ookaside buffer）高速硬件實(shí)現(xiàn)，采取相聯(lián)訪問(wèn)方式慢表：當(dāng)快表中查不到時(shí)，從主存慢表查找，軟件實(shí)現(xiàn)快表與慢表也組成一個(gè)兩極存放系統(tǒng) 第53頁(yè)4.3 虛擬存放器二、頁(yè)面替換算法及其命中率1.頁(yè)面替換發(fā)生時(shí)間：（問(wèn)題提出） 當(dāng)發(fā)生頁(yè)面失效時(shí)，要從磁盤中調(diào)入一頁(yè)到主存。假如主存全部頁(yè)面已經(jīng)被占用，必須從主存中淘汰掉一個(gè)不常使用頁(yè)面，方便騰出主存空間來(lái)存放新調(diào)入頁(yè)面2.評(píng)價(jià)頁(yè)面替換算法好壞標(biāo)準(zhǔn)： 一是命中率 二是算法要輕易實(shí)現(xiàn) 第54頁(yè)4.3 虛擬存放器二、頁(yè)面替換算法及其命中率1.幾個(gè)頁(yè)面替換算法 1、 隨機(jī)算法，即RAND算法（Random algorithm）。利用軟件或硬件隨機(jī)數(shù)發(fā)

23、生器來(lái)確定主存放器中被替換頁(yè)面。這種算法最簡(jiǎn)單，而且輕易實(shí)現(xiàn)。不過(guò)，這種算法完全沒有利用主存放器中頁(yè)面調(diào)度情況歷史信息，也沒有反應(yīng)程序局部性，所以命中率比較低。2、 先進(jìn)先出算法，即FIFO算法（First-In First-Out algorithm）。這種算法選擇最先調(diào)入主存放器頁(yè)面作為被替換頁(yè)面。它優(yōu)點(diǎn)是比較輕易實(shí)現(xiàn)，能夠利用主存放器中頁(yè)面調(diào)度情況歷史信息，不過(guò)，沒有反應(yīng)程序局部性。因?yàn)樽钕日{(diào)入主存頁(yè)面，很可能也是經(jīng)常要使用頁(yè)面。 第55頁(yè)4.3 虛擬存放器二、頁(yè)面替換算法及其命中率1.幾個(gè)頁(yè)面替換算法 3、 近期最少使用算法，即LRU算法這種算法選擇近期最少訪問(wèn)頁(yè)面作為被替換頁(yè)面。顯然

24、，這是一個(gè)非常合理算法，因?yàn)榈疆?dāng)前為止最少使用頁(yè)面，很可能也是未來(lái)最少訪問(wèn)頁(yè)面。該算法既充分利用了主存中頁(yè)面調(diào)度情況歷史信息，又正確反應(yīng)了程序局部性。不過(guò)，這種算法實(shí)現(xiàn)起來(lái)非常困難。它要為每個(gè)頁(yè)面設(shè)置一個(gè)很長(zhǎng)計(jì)數(shù)器，而且要選擇一個(gè)固定時(shí)鐘為每個(gè)計(jì)數(shù)器定時(shí)計(jì)數(shù)。在選擇被替換頁(yè)面時(shí)，要從全部計(jì)數(shù)器中找出一個(gè)計(jì)數(shù)值最大計(jì)數(shù)器。所以，通常采取另外一個(gè)變通方法，就是下面LRU算法。 第56頁(yè)4.3 虛擬存放器二、頁(yè)面替換算法及其命中率1.幾個(gè)頁(yè)面替換算法 4、 最久沒有使用算法，也稱為L(zhǎng)RU算法（Least Recently Used algorithm）。這種算法把近期最久沒有被訪問(wèn)過(guò)頁(yè)面作為被替換頁(yè)

25、面。它把LRU算法中要統(tǒng)計(jì)數(shù)量上“多”與“少”簡(jiǎn)化成判斷“有”與“無(wú)”，所以，實(shí)現(xiàn)起來(lái)比較輕易。 5、 最優(yōu)替換算法，即OPT算法（OPTimal replacemant algorithm）。最好算法應(yīng)該是選擇未來(lái)最久不被訪問(wèn)頁(yè)面作為被替換頁(yè)面。這種替換算法命中率一定是最高。這就是最優(yōu)替換算法，簡(jiǎn)稱OPT算法。 要實(shí)現(xiàn)OPT算法，唯一方法是讓程序先執(zhí)行一遍，統(tǒng)計(jì)下實(shí)際頁(yè)地址流情況。 第57頁(yè)4.4 高速緩沖存放器舉例說(shuō)明： 設(shè)有一道程序，有1至5共五頁(yè)，執(zhí)行時(shí)頁(yè)地址流（即執(zhí)行時(shí)依次用到程序頁(yè)頁(yè)號(hào)）為： 2，3，2，1，5，2，4，5，3，2，5，2若分配給該道程序主存有3頁(yè)，分別采取FIFO

26、和LRU替換算法表示這3頁(yè)使用和替換過(guò)程。說(shuō)明： （1）隨機(jī)算法：用隨機(jī)數(shù)確定要替換塊； （2）FIFO算法：替換最早裝入主存頁(yè)； （3）LRU算法：依據(jù)各塊使用情況，選擇最近最少使用塊替換。第58頁(yè)時(shí)間t 1 2 3 4 5 6 7 8 9 10 11 12頁(yè)地址流 2 3 2 1 5 2 4 5 3 2 5 2先進(jìn)先出 FIFO調(diào)進(jìn)調(diào)進(jìn)調(diào)進(jìn)命中替換替換替換替換命中命中替換替換2232322*313*1551*25*24245*2*43342*34*53*52命中命中命中命中3次近期最少使用LRU2調(diào)進(jìn)23調(diào)進(jìn)232命中23*1調(diào)進(jìn)2*15替換51*2命中25*4替換2*45命中54*3替換

27、35*2替換3*25命中523*命中命中命中命中命中命中命中5次2第59頁(yè)4.3 虛擬存放器第60頁(yè)4.3 虛擬存放器第61頁(yè)4.3 虛擬存放器第62頁(yè)4.3 虛擬存放器LRU和OPT算法是堆棧型算法，F(xiàn)IFO不是堆棧型算法 普通情況，操作系統(tǒng)在失效率較高時(shí)會(huì)增加分配給某個(gè)程序頁(yè)面，以降低其失效率（即提升命中率）第63頁(yè)4.4 高速緩沖存放器表:Cache與虛擬存放器主要區(qū)分存放系統(tǒng)Cache虛擬存放器要抵達(dá)目標(biāo)提升（主存）速度擴(kuò)大（主存）容量實(shí)現(xiàn)方法全部硬件軟件為主兩級(jí)存放器速度比310倍10000倍頁(yè)（塊）大小116字1KB16KB等效存放容量主存放器虛擬存放器透明性系統(tǒng)和應(yīng)用程序員僅對(duì)應(yīng)

28、用程序員不命中時(shí)處理方式等候主存放器任務(wù)切換可直接訪問(wèn)均經(jīng)過(guò)第一級(jí)CPU對(duì)第二級(jí)訪問(wèn)可直接訪問(wèn)均經(jīng)過(guò)第一級(jí)第64頁(yè)4.4 高速緩沖存放器一、Cache地址映象與地址變換基本工作原理：當(dāng)CPU要訪問(wèn)Cache時(shí)，送來(lái)主存地址放入主存地址存放器。經(jīng)過(guò)主存Cache地址變換部件把主存地址中塊號(hào)B變換成Cache塊號(hào)b放入Cache地址存放器中，而且把主存地址中塊內(nèi)地址W直接作為Cache塊內(nèi)地址w裝入到Cache地址存放器中。假如變換成功（稱為Cache命中），就用所得到Cache地址去訪問(wèn)Cache，從Cache中取出數(shù)據(jù)送往CPU。假如變換不成功，則產(chǎn)生Cache失效信息，而且用主存地址訪問(wèn)主存

29、放器。從主存放器中讀出一個(gè)字送往CPU。同時(shí)，把包含被訪問(wèn)字在內(nèi)一整塊都從主存放器中讀出來(lái)，裝入到Cache中去。這時(shí)，假如Cache已經(jīng)滿，則要采取某種Cache替換算法把不慣用一塊先調(diào)入主存放器中原來(lái)存放它地方。方便騰出空間來(lái)存放新調(diào)入塊。 第65頁(yè)4.4 高速緩沖存放器一、Cache地址映象與地址變換第66頁(yè)4.4 高速緩沖存放器一、Cache地址映象與地址變換地址映象：把存放在主存中程序按照某種規(guī)則裝入到Cache中，并建立主存地址與Cache地址之間對(duì)應(yīng)關(guān)系 地址變換：是指當(dāng)程序已經(jīng)裝入到Cache之后，在實(shí)際運(yùn)行過(guò)程中，把主存地址怎樣變換成Cache地址。選取地址映象方法考慮主要原

30、因： 地址變換硬件要輕易實(shí)現(xiàn)， 速度要快 主存空間利用率是否高， 發(fā)生塊沖突概率要小 第67頁(yè)4.4 高速緩沖存放器一、Cache地址映象與地址變換 全相聯(lián)方式 直接相聯(lián) 組相聯(lián)三種地址映象：1. 全相聯(lián)映象 全相聯(lián)：主存中任一塊能夠被放置到Cache中任意一個(gè)位置。(主存與緩存分成相同大小數(shù)據(jù)塊) 舉例 對(duì)比： 閱覽室位置 隨便坐 特點(diǎn)： 空間利用率最高，沖突概率最低， 實(shí)現(xiàn)最復(fù)雜。第68頁(yè)4.4 高速緩沖存放器一、Cache地址映象與地址變換全相聯(lián)映象方式 ：映象規(guī)則：主存中任意一塊能夠映象到Cache中任意一塊。假如Cache塊數(shù)為Cb，主存塊數(shù)為MB，映象關(guān)系共有CbMB種。B（b）：

31、塊號(hào)C：Cache容量M：主存容量 塊0 塊1 ： 塊i：塊MB-1 塊0 塊1 ：塊Cb-1Cache主存放器第69頁(yè)4.4 高速緩沖存放器一、Cache地址映象與地址變換全相聯(lián)地址變換 塊號(hào) 塊內(nèi)地址主存地址 塊號(hào) 塊內(nèi)地址Cache地址 Bi bi 1 主存塊號(hào)B Cache塊號(hào)b 有效位目錄表第70頁(yè)4.4 高速緩沖存放器一、Cache地址映象與地址變換2. 直接映象 直接映象：主存中每一塊只能被放置到 Cache中唯一一個(gè)位置。 舉例 (循環(huán)分配) 對(duì)比：閱覽室位置 只有一個(gè)位置可 以坐 特點(diǎn)：空間利用率最低，沖突概率最高， 實(shí)現(xiàn)最簡(jiǎn)單。第71頁(yè)4.4 高速緩沖存放器一、Cache地

32、址映象與地址變換映象規(guī)則：主存中一塊只能映象到Cache一個(gè)特定塊中。 計(jì)算公式：bB mod Cb 其中：b為Cache塊號(hào)，B是主存塊號(hào)，Cb是Cache塊數(shù)。 整個(gè)Cache地址與主存地址低位部分完全相同。第72頁(yè)4.4 高速緩沖存放器直接相聯(lián)地址映象主存放器 塊0 塊1 : 塊C/B-1 塊C/B 塊C/B+1 :塊2C/B-1 : 塊M/B-C/B 塊M/B-C/B+1 : 塊M/B-1區(qū)0區(qū)1區(qū)M/C-1 塊0 塊1 : 塊C/B-1cache第73頁(yè)4.4 高速緩沖存放器一、Cache地址映象與地址變換地址變換過(guò)程：用主存地址中塊號(hào)B去訪問(wèn)區(qū)號(hào)存放器把讀出來(lái)區(qū)號(hào)與主存地址中區(qū)號(hào)E

33、進(jìn)行比較 比較結(jié)果相等，且有效位為1，則Cache命中。 比較結(jié)果相等，有效位為0，表示Cache中這一塊已經(jīng)作廢。 比較結(jié)果不相等，有效位為0，表示Cache中這一塊是空。 比較結(jié)果不相等，有效位為1，表示Cache中這一塊是有用 第74頁(yè)4.4 高速緩沖存放器 直接相聯(lián)地址變換 目錄表存放器塊失效相等比較區(qū)號(hào)Ei 塊號(hào)i 塊內(nèi)地址塊號(hào)i 塊內(nèi)地址 主存地址Cache地址相等 Ei 1 區(qū)號(hào)（按地址訪問(wèn)） 有效位訪問(wèn)Cache第75頁(yè)例3-3 設(shè)有一個(gè)cache容量為2K字，每個(gè)塊為16字，求(1) 該cache可容納多少個(gè)塊？(2) 假如主存容量是256K字，則有多少個(gè)塊？(3) 主存字地

34、址有多少位？Cache 字地址有多少位？(4) 在直接映象方式下，主存中第i塊映象到cache中哪一個(gè)塊中？(5) 進(jìn)行地址映象時(shí)，存放器地址分成哪幾段？各段分別有多少位？解：(1) cache中有2048/16=128個(gè)塊。(2) 主存有256K/16=16384個(gè)塊。(3)主存：字地址為18位，256K=218字。 cache：字地址為11位，2K=211字。(4) 主存中第i塊映象到cache中第 i mod 128個(gè)塊中。(5) 存放器字地址分成三段：區(qū)號(hào)、塊號(hào)、塊內(nèi)字地址。區(qū)號(hào)長(zhǎng)度為18-11=7位，塊號(hào)為7位。塊內(nèi)字地址為4位。第76頁(yè)4.4 高速緩沖存放器一、Cache地址映象與

35、地址變換 組相聯(lián)：主存中每一塊能夠被放置到Cache 中唯一一個(gè)組中任何一個(gè)位置。 舉例 組相聯(lián)是直接映象和全相聯(lián)一個(gè)折衷3. 組相聯(lián)映象第77頁(yè)4.4 高速緩沖存放器一、Cache地址映象與地址變換組相聯(lián)映象規(guī)則 1. 主存與緩存分成相同大小塊;2. 主存與緩存分成相同大小組;3. 主存容量是緩存容量整數(shù)倍，將主存空間按緩存大小分成區(qū)，主存中每一區(qū)組數(shù)與緩存組數(shù)相同。4. 組間直接相聯(lián)；組內(nèi)全相聯(lián)。 思索題： 當(dāng)組相聯(lián)映象組內(nèi)塊數(shù)大到等于Cache時(shí)，就變成什么映象？而當(dāng)塊數(shù)小到只有一塊時(shí)就變成了什么映象？第78頁(yè)組相聯(lián)地址映象 區(qū)0區(qū)Me1組1組0組C/B1 塊0 塊B1 塊B 塊2B1

36、Cache塊0塊B1 塊B 塊2B1組1組C/B1組0組C/B(Me1)組C/BMeC/B+1組C/BMe1第79頁(yè)4.4 高速緩沖存放器一、Cache地址映象與地址變換地址變換過(guò)程：用主存地址中組號(hào)G按地址訪問(wèn)塊表存放器。把讀出來(lái)一組區(qū)號(hào)和塊號(hào)與主存地址中區(qū)號(hào)和塊號(hào)進(jìn)行相聯(lián)比較。假如有相等，表示Cache命中。假如沒有相等，表示Cache沒有命中。3. 組相聯(lián)映象第80頁(yè)4.4 高速緩沖存放器組相聯(lián)映象地址轉(zhuǎn)換 相等不等Cache地址區(qū)號(hào) 組號(hào) 組內(nèi)塊號(hào) 塊內(nèi)地址主存地址 組號(hào) 組內(nèi)塊號(hào) 塊內(nèi)地址相聯(lián)比較區(qū)號(hào)E 組內(nèi)塊號(hào) 組內(nèi)塊號(hào) EiBi bi塊表第81頁(yè)4.4 高速緩沖存放器一、Cach

37、e地址映象與地址變換 組相聯(lián)映象方式優(yōu)點(diǎn)：塊沖突概率比較低，塊利用率大幅度提升，塊失效率顯著降低。 組相聯(lián)映象方式缺點(diǎn)：實(shí)現(xiàn)難度和造價(jià)要比直接映象方式高。3. 組相聯(lián)映象第82頁(yè)4.4 高速緩沖存放器二、Cache替換算法及其實(shí)現(xiàn)隨機(jī)法：(Random,RAND法) 先進(jìn)先出法(First-In First-Out,FIFO法) 近期最少使使用方法(Least Recently Used,LRU法) 所要處理問(wèn)題：當(dāng)新調(diào)入一塊，而Cache又已被占滿時(shí)，替換哪一塊？第83頁(yè)4.4 高速緩沖存放器舉例說(shuō)明： 設(shè)有一道程序，有1至5共五頁(yè)，執(zhí)行時(shí)頁(yè)地址流（即執(zhí)行時(shí)依次用到程序頁(yè)頁(yè)號(hào)）為： 2，3，

38、2，1，5，2，4，5，3，2，5，2若分配給該道程序主存有3頁(yè)，分別采取FIFO和LRU替換算法表示這3頁(yè)使用和替換過(guò)程。說(shuō)明： （1）隨機(jī)算法：用隨機(jī)數(shù)確定要替換塊； （2）FIFO算法：替換最早裝入主存頁(yè)； （3）LRU算法：依據(jù)各塊使用情況，選擇最近最少使用塊替換。第84頁(yè)時(shí)間t 1 2 3 4 5 6 7 8 9 10 11 12頁(yè)地址流 2 3 2 1 5 2 4 5 3 2 5 2先進(jìn)先出 FIFO調(diào)進(jìn)調(diào)進(jìn)調(diào)進(jìn)命中替換替換替換替換命中命中替換替換2232322*313*1551*25*24245*2*43342*34*53*52命中命中命中命中3次近期最少使用LRU2調(diào)進(jìn)23調(diào)進(jìn)232命中23*1調(diào)進(jìn)2*15替換51*2命中25*4替