1、高速緩沖存儲器和虛擬存儲器第1頁，共40頁，2022年，5月20日，1點(diǎn)12分，星期五本章主要內(nèi)容高速緩沖存儲器（Cache）高速緩存的基本運(yùn)行原理高速緩存的3種映像方式高速緩存使用中的幾個問題虛擬存儲器虛擬存儲器概述段式存儲管理頁式存儲管理2第2頁，共40頁，2022年，5月20日，1點(diǎn)12分，星期五微電子技術(shù)發(fā)展趨勢CPU與DRAM性能比較3第3頁，共40頁，2022年，5月20日，1點(diǎn)12分，星期五程序的局部性原理程序在一定時間段內(nèi)通常只訪問較小的地址空間兩種局部性：時間局部性和空間局部性時間局部性：最近被訪問的信息很可能還要被訪問。將最近被訪問的信息項裝入到Cache中。空間局部性：最

2、近被訪問的信息臨近的信息也可能被訪問。將最近被訪問的信息項臨近的信息一起裝入到Cache中。地址空間訪問概率4第4頁，共40頁，2022年，5月20日，1點(diǎn)12分，星期五高速緩沖存儲器（Cache）用途：設(shè)置在 CPU 和 主存儲器之間，完成高速與 CPU 交換信息，盡量避免 CPU不必要地多次直接訪問慢速的主存儲器，從而提高計算機(jī)系統(tǒng)的運(yùn)行效率。實現(xiàn)：這是一個存儲容量很小，但讀寫速度更快的，以 關(guān)聯(lián)存儲器方式 運(yùn)行、用靜態(tài)存儲器芯片實現(xiàn)的存儲器系統(tǒng)。要求：有足夠高的命中率，既當(dāng) CPU需用主存中的數(shù)據(jù)時，多數(shù)情況可以直接從CACHE中得到，稱二者之比為命中率。5第5頁，共40頁，2022年，

3、5月20日，1點(diǎn)12分，星期五CACHE的基本運(yùn)行原理Cache存儲單元的組成部分?jǐn)?shù)據(jù)字段：保存從主存單元復(fù)制過來的數(shù)據(jù)標(biāo)志字段：保存相應(yīng)主存單元的地址信息有效位字段：標(biāo)識數(shù)據(jù)字段和標(biāo)志字段是否有效提高Cache性能，降低成本Cache單元的大小：cache line size（幾個主存字，減少標(biāo)志位位數(shù)，較少Cache總?cè)萘浚〤ache與主存交換數(shù)據(jù)的單位： cache line size（充分利用空間局部性）Cache單元與主存單元的對應(yīng)關(guān)系，例如：完全隨意對應(yīng)、一對多硬性對應(yīng)和多對多有限隨意對應(yīng)Cache的容量、分層組織、接入方式等方面6第6頁，共40頁，2022年，5月20日，1點(diǎn)12

4、分，星期五CACHE的基本運(yùn)行原理MEMORY CACHE CONTROL數(shù)據(jù)總線譯碼選一單元比較選一行讀過程為例地址總線ADDR DATA CACHE CPU 7第7頁，共40頁，2022年，5月20日，1點(diǎn)12分，星期五CACHE的3種映像方式地址映像：把一主存單元的數(shù)據(jù)復(fù)制到CACHE中時，還要把該主存單元的地址，經(jīng)過某種函數(shù)關(guān)系處理后寫進(jìn)CACHE的標(biāo)志字段，這一過程被稱為CACHE的地址映像。地址變換：在程序執(zhí)行時，還要把主存地址變換為訪問CACHE的地址，這一過程被叫做CACHE的地址變換。 CACHE存儲器通常使用3種映像方式，它們是全相聯(lián)映像方式、直接映像方式、多路組相聯(lián)映像方

5、式，3種映像方式有各自的優(yōu)缺點(diǎn)。8第8頁，共40頁，2022年，5月20日，1點(diǎn)12分，星期五全相聯(lián)映像方式全相聯(lián)映像方式：是指主存的一個字塊可以映像到整個CACHE的任何一個字塊中。全相聯(lián)映像方式特點(diǎn)：主存的字塊可以和Cache的任何字塊對應(yīng)，利用率高，方式靈活。標(biāo)志位較長，比較電路的成本太高。如果主存空間有2m塊，則標(biāo)志位要有m位。同時，如果Cache有n塊，則需要有n個比較電路。使用成本太高9第9頁，共40頁，2022年，5月20日，1點(diǎn)12分，星期五全相聯(lián)映像方式C P U數(shù)據(jù)主存字塊標(biāo)記有效位主存儲器CACHE比較譯碼標(biāo)志數(shù)據(jù)主存字塊標(biāo)記塊內(nèi)地址主存地址10第10頁，共40頁，202

6、2年，5月20日，1點(diǎn)12分，星期五全相聯(lián)硬件實現(xiàn)舉例11第11頁，共40頁，2022年，5月20日，1點(diǎn)12分，星期五直接映像方式直接映像方式：是指主存的一個字塊只能映像到CACHE的一個準(zhǔn)確確定的字塊中。直接映像方式特點(diǎn)：主存的字塊只可以和固定的Cache字塊對應(yīng)，方式直接，利用率低。標(biāo)志位較短，比較電路的成本低。如果主存空間有2m塊，Cache中字塊有2c塊，則標(biāo)志位只要有m-c(2m/2c)位。且僅需要比較一次。利用率低，命中率低，效率較低12第12頁，共40頁，2022年，5月20日，1點(diǎn)12分，星期五直接映像方式C P U數(shù)據(jù)有效位主存儲器CACHE比較譯碼譯碼cache字塊地址主

7、存字塊標(biāo)記標(biāo)志數(shù)據(jù)主存字塊標(biāo)記塊內(nèi)地址主存地址cache字塊地址13第13頁，共40頁，2022年，5月20日，1點(diǎn)12分，星期五直接映像硬件實現(xiàn)舉例14第14頁，共40頁，2022年，5月20日，1點(diǎn)12分，星期五多路組相聯(lián)映像方式多路組相聯(lián)映像方式：是對全相聯(lián)映像和直接映想象的一種折衷的處理方案。既不在主存和CACHE之間實現(xiàn)字塊的完全隨意對應(yīng)，也不在主存和CACHE之間實現(xiàn)字塊的多對一的硬性對應(yīng)，而是實現(xiàn)一種有限度的隨意對應(yīng)。 多路組相聯(lián)映像方式特點(diǎn)：折衷方案。組間為全相連，組內(nèi)為直接映像。集中了兩個方式的優(yōu)點(diǎn)。成本也不太高。最常用的CACHE映像方式15第15頁，共40頁，2022年，

8、5月20日，1點(diǎn)12分，星期五組地址兩路組相聯(lián)映像方式C P U數(shù)據(jù)有效位主存儲器CACHE譯碼比較比較譯碼譯碼標(biāo)志數(shù)據(jù)主存地址主存字塊標(biāo)記塊內(nèi)地址組地址主存字塊標(biāo)記16第16頁，共40頁，2022年，5月20日，1點(diǎn)12分，星期五多路組相聯(lián)硬件實現(xiàn)舉例17第17頁，共40頁，2022年，5月20日，1點(diǎn)12分，星期五三種映像方式比較全相聯(lián)映射主存中的一塊可以映射到Cache中任何一個位置直接映像主存中的一塊只能映射到Cache中唯一的一個位置定位時，不需要判斷，只需替換多路組相聯(lián)映射主存中的一塊可以選擇映射到Cache中多個位置全相聯(lián)映射和多路組相聯(lián)映射的失效處理從主存中取出新塊為了騰出Ca

9、che空間，需要替換出一個Cache塊不唯一，則需要判斷應(yīng)替出哪塊18第18頁，共40頁，2022年，5月20日，1點(diǎn)12分，星期五CACHE使用中的幾個問題CACHE的重要技術(shù)指標(biāo)：命中率影響 CACHE 命中率的因素CACHE 的容量，大一些好CACHE 與主存儲器每次交換信息的單位量(Cache Line Size)適中CACHE 不同的組織方式，多路組相聯(lián)更好CACHE 的多級組織可提高命中率CACHE 裝滿后的替換算法19第19頁，共40頁，2022年，5月20日，1點(diǎn)12分，星期五cache的容量與命中率的關(guān)系 Cache Size in KBHit Rate20第20頁，共40頁

10、，2022年，5月20日，1點(diǎn)12分，星期五 cache line size與缺失率的關(guān)系 cache 容量 21第21頁，共40頁，2022年，5月20日，1點(diǎn)12分，星期五多級的cache結(jié)構(gòu)與命中率的關(guān)系 為增加計算機(jī)系統(tǒng)中的cache容量，通常可以在已有的cache存儲器系統(tǒng)之外，再增加一個容量更大的cache。此時原有cache為第一級cache（例如奔騰機(jī)微處理機(jī)芯片內(nèi)的cache），新增加的cache則成為第二級的cache。第二級cache的容量比第一級cache的容量要大得多，在第一級cache中保存的信息也一定保存在第二級cache中，但保存有比第一級cache中更多的信息

11、。當(dāng)CPU訪問第一級cache出現(xiàn)缺失情況時，就去訪問第二級cache。若第一級、第二級cache的命中率為90%，則它們合起來后的命中率為-（-90）（-90）=99，而不會是81。22第22頁，共40頁，2022年，5月20日，1點(diǎn)12分，星期五Cache替換算法隨機(jī)替換（RAND）隨機(jī)找一個Cache塊進(jìn)行替換，比較盲目。先進(jìn)先出算法（FIFO）將最早調(diào)入Cache的字塊替換出去，采用循環(huán)電路容易實現(xiàn)，開銷小。最近最少使用算法（LRU）需要計算字塊的使用次數(shù)，開銷大，但平均命中率比FIFO要高。23第23頁，共40頁，2022年，5月20日，1點(diǎn)12分，星期五改寫主存儲器的策略若 CPU

12、 改寫了 Cache 一單元內(nèi)容（寫命中）后且尚未改變主存相應(yīng)單元內(nèi)容，則出現(xiàn)數(shù)據(jù)不一致性。有兩種解決辦法：直接改寫主存單元內(nèi)容（Write Through）： 簡便易行，數(shù)據(jù)一致性容易保證，但可能帶來系統(tǒng)運(yùn)行效率不高的問題，Cache對寫操作沒有提高性能。拖后改寫主存單元內(nèi)容（Write Back）：一直拖到有另外的設(shè)備要讀該內(nèi)容過時的主存單元時，則首先停止這一讀操作，接下來改寫主存內(nèi)容，之后再起動已停下來的讀操作。矛盾是如何檢查是否是讀無效內(nèi)存單元的操作，這是通過監(jiān)視地址總線完成的，記下無效單元地址用于比較。控制復(fù)雜些，但可以提供更高的系統(tǒng)運(yùn)行效率。24第24頁，共40頁，2022年，5月

13、20日，1點(diǎn)12分，星期五CACHE 接入系統(tǒng)的體系結(jié)構(gòu)側(cè)接法：象入出設(shè)備似的連接到總線上，優(yōu)點(diǎn)是結(jié)構(gòu)簡單，成本低，缺點(diǎn)是不利于降低總線占用率。CPUMEMORYCACHEBus Master 1Bus Master 2總線25第25頁，共40頁，2022年，5月20日，1點(diǎn)12分，星期五CACHE 接入系統(tǒng)的體系結(jié)構(gòu)隔斷法：把原來的總線打斷為兩段，使 CACHE 處在兩段之間。優(yōu)點(diǎn)是有利于提高總線利用率，支持總線并發(fā)操作；缺點(diǎn)是結(jié)構(gòu)復(fù)雜，成本較高。CPUMEMORYBus Master 1Bus Master 2總線CACHE26第26頁，共40頁，2022年，5月20日，1點(diǎn)12分，星期五

14、本章主要內(nèi)容高速緩沖存儲器（Cache）高速緩存的基本運(yùn)行原理高速緩存的3種映像方式高速緩存使用中的幾個問題虛擬存儲器虛擬存儲器概述段式存儲管理頁式存儲管理27第27頁，共40頁，2022年，5月20日，1點(diǎn)12分，星期五虛擬存儲器概述虛擬存儲器是指用磁盤的存儲空間來彌補(bǔ)主存空間的不足，使得程序人員能夠使用比主存實際空間更大的存儲空間來編寫和運(yùn)行程序。根據(jù)“程序運(yùn)行的局部性原理”，只把一小段時間內(nèi)用到的程序和數(shù)據(jù)裝入主存；其他程序和數(shù)據(jù)在操作系統(tǒng)的支持下，在磁盤和主存之間按程序運(yùn)行的需要自動成批量地完成交換。虛擬存儲器經(jīng)常使用兩種基本管理技術(shù)，核心問題都在于處理數(shù)據(jù)的存放與調(diào)度。段式存儲管理頁

15、式存儲管理綜合起來：段頁式存儲管理28第28頁，共40頁，2022年，5月20日，1點(diǎn)12分，星期五段式存儲管理段是程序模塊化設(shè)計的結(jié)果，即把程序中邏輯上相對獨(dú)立的部分設(shè)計為不同的段，再經(jīng)過連接程序連接成更大的程序。此時用段作為信息調(diào)入主存的單位是合適的，以段為單位分配與管理主存儲器被稱為段式存儲管理。段式存儲管理的核心問題在于設(shè)立和管理段表；段表也是主存中的可再定位的一段信息，用于變換程序中的虛地址（邏輯地址）為主存單元的實地址（物理地址）。29第29頁，共40頁，2022年，5月20日，1點(diǎn)12分，星期五段式存儲管理30第30頁，共40頁，2022年，5月20日，1點(diǎn)12分，星期五段表內(nèi)容

16、及其管理段號 段內(nèi)地址+邏輯地址段始地址 段長 裝入位段表主存實際地址段表基地址31第31頁，共40頁，2022年，5月20日，1點(diǎn)12分，星期五段式存儲管理提高性能的方法使用段地址寄存器，保存一段的起始地址，以后使用這一段的數(shù)據(jù)不必再查段表，直接計算主存地址段式存儲管理的特點(diǎn)優(yōu)點(diǎn)：段的分界與程序的自然分界對應(yīng) 段邏輯上的獨(dú)立性有利于內(nèi)存保護(hù) 便于實現(xiàn)對段的信息共享缺點(diǎn) 段長不確定，主存分配和管理不便 容易在段間形成難以利用的碎片32第32頁，共40頁，2022年，5月20日，1點(diǎn)12分，星期五頁式存儲管理頁式存儲管理是把虛擬空間和主存空間都分成大小相同的頁（為2的整數(shù)冪個字），并以頁為單位進(jìn)

17、行虛存與主存間的信息交換。此時虛存邏輯地址和主存物理地址分別被分為“虛存頁號頁內(nèi)地址”和“主存頁號頁內(nèi)地址”，虛、實二頁號會不同，但使用相同的頁內(nèi)地址。與段式存儲管理不一樣，頁不是程序本身的結(jié)構(gòu)特性，而是從管理的角度人為劃分的結(jié)果。設(shè)置和管理好頁表是頁式存儲管理的關(guān)鍵技術(shù)。33第33頁，共40頁，2022年，5月20日，1點(diǎn)12分，星期五頁式存儲管理34第34頁，共40頁，2022年，5月20日，1點(diǎn)12分，星期五頁表內(nèi)容和頁式管理+（在內(nèi)存中）控制位 有效位頁表虛地址 (程序中給出)實地址 (讀寫內(nèi)存用)按地址讀實頁號虛頁號 頁內(nèi)地址實頁號 頁內(nèi)地址頁表基地址控制位：包括修改位、替換位有效位

18、：表示該頁是否已裝入主存35第35頁，共40頁，2022年，5月20日，1點(diǎn)12分，星期五頁式存儲管理頁式存儲管理的特點(diǎn)優(yōu)點(diǎn)：只要有空白頁新頁就可以調(diào)入內(nèi)存 只有程序的最后一頁可能有零頭浪費(fèi)缺點(diǎn)：頁不是邏輯上的獨(dú)立程序?qū)嶓w 處理、保護(hù)和共享信息不如段式方便提高性能的方法為了克服讀取一次數(shù)據(jù)訪問兩次內(nèi)存的問題(一次查頁表,一次讀內(nèi)存)，引入快速頁表（轉(zhuǎn)換旁路緩沖器TLB：translation lookaside buffer）TLB完全由快速硬件實現(xiàn)，但容量較小，采用類似于Cache的關(guān)聯(lián)存儲器方式進(jìn)行訪問36第36頁，共40頁，2022年，5月20日，1點(diǎn)12分，星期五頁表內(nèi)容和頁式管理+（在內(nèi)存中）控制位 有效位虛 頁號 實 頁號慢表虛地址 (程序中給出)實地址 (讀寫內(nèi)存用)快表(專設(shè)硬件)比較(按內(nèi)容選)按地址讀實頁號虛頁號 頁內(nèi)地址實頁號 頁內(nèi)地址頁表基地址37第37頁，共40頁，2022年，5月20日，1點(diǎn)12分，星期五虛擬存儲器與高速緩沖存儲器區(qū)別Cache虛擬存儲器功能提高了主存儲器的速度 擴(kuò)大了主存儲器的容量 實現(xiàn)技術(shù)硬件 以軟件為主 透明性透明不透明地址轉(zhuǎn)換簡單復(fù)雜、速度慢數(shù)據(jù)交換頻率高、數(shù)量少頻率低、數(shù)量多38第38頁，共40頁，20