計(jì)算機(jī)組成原理-課件cache

3.4高速存儲(chǔ)器單機(jī)系統(tǒng)中，主存與CPU速度的不匹配是高速計(jì)算的瓶頸。提高存儲(chǔ)系統(tǒng)性能的主要措施采用更高速的主存和加長(zhǎng)存儲(chǔ)器的字長(zhǎng)采用并行操作的雙端口存儲(chǔ)器采用多模塊交叉存儲(chǔ)器采用高速緩沖存儲(chǔ)器P97應(yīng)用：虛擬存儲(chǔ)器中存放段表、頁(yè)表和快表高速緩存中存入cache行地址相聯(lián)存儲(chǔ)器普通存儲(chǔ)器是以地址為檢索項(xiàng)來(lái)進(jìn)行存取。相聯(lián)存儲(chǔ)器（CAM）的基本原理可將某一存儲(chǔ)項(xiàng)的內(nèi)容作為檢索項(xiàng)來(lái)存取和檢索信息的存儲(chǔ)器。物理地址職工號(hào)姓名出生年月工資數(shù)N800張明1940.22000N+1540王芳1960.11200N+2920李萍1942.51500N+3750趙虹1945.21400普通存儲(chǔ)器的檢索項(xiàng)相聯(lián)存儲(chǔ)器的檢索項(xiàng)3.5高速緩沖存儲(chǔ)器工作原理基于程序局部性原理短時(shí)間內(nèi)，CPU對(duì)存儲(chǔ)器的訪問(wèn)總是局限在某個(gè)較小區(qū)域內(nèi)cache與主存分成大小相同的塊當(dāng)CPU讀取一個(gè)字時(shí)，便發(fā)出此字的內(nèi)存地址到cache和主存?？刂七壿嬇袛啻俗之?dāng)前是否在cache中若在，立即傳送給CPU若不在，則把此字從主存讀到CPU，同時(shí)，把含有該字的數(shù)據(jù)塊從主存送cache。CPU相聯(lián)存儲(chǔ)器主存LRU管理邏輯cacheDBABCache的命中率Cache始終保存主存最活躍的局部區(qū)域的副本，使CPU的訪存操作大多數(shù)針對(duì)Cache，提高整個(gè)程序的執(zhí)行速度。命中率，越接近1越好。Nc——Cache完成存取的總次數(shù)Nm——主存完成存取的總次數(shù)h——命中率系統(tǒng)平均訪問(wèn)時(shí)間越接近c(diǎn)ache訪問(wèn)時(shí)間越好。tc——命中時(shí)，cache訪問(wèn)時(shí)間tm——未命中時(shí)，主存訪問(wèn)時(shí)間ta——系統(tǒng)平均訪問(wèn)時(shí)間Cache的命中率系統(tǒng)訪問(wèn)效率r——Tm/Tc，比值不宜太大，以5~10較好。e——系統(tǒng)訪問(wèn)效率【例5】CPU執(zhí)行一段程序時(shí)，cache完成存取的次數(shù)為1900次，主存完成存取的次數(shù)為100次，已知cache存取周期為50ns，主存存取周期為250ns，求cache/主存系統(tǒng)的效率和平均訪問(wèn)時(shí)間。h=Nc/(Nc+Nm)=1900/(1900+100)=0.95r=tm/tc=250ns/50ns=5e=1/(r+(1-r)h)=1/(5+(1-5)×0.95)=83.3%ta=htc+(1-h)tm=tc/e=50ns/0.833=60ns主存與Cache的地址映射地址映射應(yīng)用某種函數(shù)，將主存地址映像到Cache中定位，從而可以將內(nèi)存地址變換成Cache地址，完成CPU的訪問(wèn)。全相聯(lián)映射直接映射組相聯(lián)映射地址映射過(guò)程對(duì)程序員來(lái)說(shuō)是完全透明的由硬件控制實(shí)現(xiàn)，程序員不需要編程介入全相聯(lián)映射主存中任一塊都可以映射到Cache中任一行上。例：內(nèi)存容量64KB，分為256塊，每塊256B，Cache容量2KB，分為8行，每行也是256B。優(yōu)點(diǎn)：比較靈活Cache利用率高塊沖突概率低使用淘汰算法缺點(diǎn)：Cache標(biāo)記太長(zhǎng)比較電路難于設(shè)計(jì)和實(shí)現(xiàn)M255…7塊…1塊0塊塊號(hào)…塊號(hào)塊號(hào)7行…1行0行Cache標(biāo)記8位全相聯(lián)映射檢索過(guò)程塊號(hào)塊內(nèi)地址內(nèi)存地址8位8位7行塊號(hào)……2行塊號(hào)1行塊號(hào)0行塊號(hào)標(biāo)記塊內(nèi)容量Cache比較命中0塊1塊2塊…L-1塊L塊L+1塊…255M未命中8位直接映射主存分區(qū)，每區(qū)內(nèi)塊數(shù)與Cahce內(nèi)行數(shù)相同。主存中每一個(gè)塊只能映射到Cache中某一個(gè)固定的行。i=jmodmi：Cache的行號(hào)j：主存的塊號(hào)m：Cache的總行數(shù)例：0=8mod8（主存第8塊映像到Cache的第0行）31區(qū)255…249248…15塊…9塊8塊7塊…1塊0塊M0區(qū)1區(qū)…區(qū)號(hào)…區(qū)號(hào)區(qū)號(hào)7行…1行0行Cache標(biāo)識(shí)5位不靈活塊沖突概率高特點(diǎn)地址變換速度快無(wú)需替換算法直接映射檢索過(guò)程內(nèi)存地址區(qū)號(hào)區(qū)內(nèi)塊號(hào)塊內(nèi)地址5位3位8位7行區(qū)號(hào)……2行區(qū)號(hào)1行區(qū)號(hào)0行區(qū)號(hào)標(biāo)記塊內(nèi)容量Cache7塊…1塊0塊…7塊…1塊0塊7塊…1塊0塊M0區(qū)1區(qū)31區(qū)…比較命中未命中組相聯(lián)映射主存分區(qū)，Cache分組，主存每個(gè)區(qū)的塊數(shù)與Cache的分組數(shù)相同。組間采用直接映射組內(nèi)采用全相聯(lián)映射特點(diǎn)：是全相聯(lián)映像與直接映像的折衷。較直接映像靈活較全相聯(lián)映像標(biāo)記位短，速度快255254253252…7塊6塊5塊4塊3塊2塊1塊0塊M0區(qū)1區(qū)63區(qū)…區(qū)號(hào)區(qū)號(hào)區(qū)號(hào)區(qū)號(hào)區(qū)號(hào)1行0行1行0行Cache…1行…0組1組3組0行標(biāo)識(shí)6位區(qū)號(hào)組相聯(lián)映射檢索過(guò)程區(qū)號(hào)區(qū)內(nèi)塊號(hào)Cache組號(hào)塊內(nèi)地址區(qū)號(hào)3塊2塊1塊0塊…3塊2塊1塊0塊3塊2塊1塊0塊區(qū)號(hào)區(qū)號(hào)區(qū)號(hào)區(qū)號(hào)1行0行1行0行CacheM0區(qū)1區(qū)63區(qū)…區(qū)號(hào)…1行…0組1組3組0行比較命中未命中6位2位8位標(biāo)識(shí)6位塊內(nèi)容量Cache地址映射練習(xí)一個(gè)四路組相聯(lián)映射的Cache，由64行構(gòu)成。主存包含4096個(gè)存儲(chǔ)塊，每塊由128字組成。一個(gè)主存地址有多少位？主存地址格式中區(qū)號(hào)、組號(hào)和塊內(nèi)地址位數(shù)？1)19位，4096*128=2192)區(qū)號(hào)8位，組號(hào)4位，塊內(nèi)地址7位15組區(qū)號(hào)4095…40814080…31塊…17塊16塊15塊…1塊0塊區(qū)號(hào)區(qū)號(hào)區(qū)號(hào)區(qū)號(hào)3行2行1行0行CacheM0區(qū)1區(qū)255區(qū)…區(qū)號(hào)…63行…0組62行區(qū)號(hào)區(qū)號(hào)61行60行高速緩存替換算法替換算法：當(dāng)Cache中的可用位置已被占滿時(shí)，需要利用某種算法，將舊的行用新的行來(lái)代替。最不經(jīng)常使用（LFU）算法將一段時(shí)間內(nèi)使用次數(shù)最少的行淘汰。近期最少使用（LRU）算法最近一段時(shí)間，使用機(jī)會(huì)最少的行被淘汰。隨機(jī)算法簡(jiǎn)單地根據(jù)一個(gè)隨機(jī)數(shù)，指定需要替換出去的舊塊。Cache的讀寫(xiě)策略讀操作：CPU發(fā)出讀命令后若Cache命中，直接對(duì)Cache進(jìn)行讀操作未命中，訪問(wèn)內(nèi)存，同時(shí)將內(nèi)存信息調(diào)入Cache若Cache已滿，采用替換算法，換掉原來(lái)的某塊寫(xiě)操作：CPU發(fā)出寫(xiě)命令后寫(xiě)回法:先暫時(shí)寫(xiě)入Cache，并用標(biāo)記注明，直到該塊從Cache中替換出來(lái)時(shí)，才一次寫(xiě)入內(nèi)存。全寫(xiě)法:同時(shí)寫(xiě)入內(nèi)存和Cache。寫(xiě)一次法:是寫(xiě)回法與全寫(xiě)法的結(jié)合。基本同于寫(xiě)回法，但第一次寫(xiě)命中時(shí)要同時(shí)寫(xiě)入主存。3.6虛擬存儲(chǔ)器虛擬存儲(chǔ)系統(tǒng)建立在內(nèi)存——外存層次上的需要輔助硬軟件的支持將內(nèi)存與外存空間統(tǒng)一編址形成一個(gè)龐大的存儲(chǔ)空間用戶可在這個(gè)虛擬的龐大空間里編程，而不必考慮實(shí)際內(nèi)存的大小虛擬地址（邏輯地址）：用戶編程時(shí)使用的地址，在程序真正執(zhí)行時(shí)，在輔助軟硬件支持下，虛擬地址將映射為內(nèi)存的物理地址。實(shí)際地址（物理地址）：內(nèi)存的實(shí)際的地址編號(hào)。頁(yè)表頁(yè)式虛擬存儲(chǔ)器內(nèi)存空間和虛存空間都劃分成若干個(gè)大小相等的頁(yè)。設(shè)置地址變換機(jī)構(gòu)——頁(yè)表。頁(yè)表由多個(gè)頁(yè)表項(xiàng)構(gòu)成。每個(gè)頁(yè)表項(xiàng)包含實(shí)頁(yè)號(hào)、裝入位等。實(shí)頁(yè)號(hào)頁(yè)內(nèi)地址虛頁(yè)號(hào)頁(yè)內(nèi)地址虛地址實(shí)地址頁(yè)表項(xiàng)地址1裝入位1：該頁(yè)在內(nèi)存0：不在內(nèi)存，調(diào)入頁(yè)表起始地址頁(yè)表基址寄存器頁(yè)式虛擬存儲(chǔ)器頁(yè)表的改進(jìn)——快表快速小容量的存儲(chǔ)器保存當(dāng)前最常用的頁(yè)表項(xiàng)是慢表的副本頁(yè)表虛擬存儲(chǔ)的特點(diǎn)頁(yè)大小相等，地址變換簡(jiǎn)單存在頁(yè)零頭頁(yè)的劃分不具有邏輯性，程序處理復(fù)雜段式虛擬存儲(chǔ)器內(nèi)存空間按程序邏輯結(jié)構(gòu)分段，段長(zhǎng)度各異。地址變換機(jī)構(gòu)——段表。段表包括多個(gè)段表項(xiàng)。每個(gè)段表項(xiàng)包含段號(hào)、段起點(diǎn)、段長(zhǎng)、裝入位等。2K1202441K1919233K161202011K110000段長(zhǎng)裝入位段起點(diǎn)段號(hào)段表段0段1段2段3段41K2K3K1K2K程序空間段0段4段2內(nèi)存實(shí)空間1000202440716120919210215段3段式虛擬存儲(chǔ)器段表起始地址段表基址寄存器段號(hào)段內(nèi)地址段表虛地址段表項(xiàng)地址實(shí)地址內(nèi)存地址+優(yōu)點(diǎn)：段的分界與程序邏輯性相符，便于程序管理。缺點(diǎn)：段長(zhǎng)不一，主存空間分配麻煩，存在段間零頭。段頁(yè)式虛擬存儲(chǔ)器程序按邏輯結(jié)構(gòu)先分段，段內(nèi)再劃分為若干大小相等的頁(yè)，內(nèi)存也劃分為同樣大小的頁(yè)。地址變換機(jī)構(gòu)——段表、頁(yè)表段表：每個(gè)程序一個(gè)頁(yè)表：每段一個(gè)優(yōu)點(diǎn)兼?zhèn)漤?yè)式和段式系統(tǒng)的優(yōu)點(diǎn)缺點(diǎn)地址映射過(guò)程中需要多次查表多道程序的段頁(yè)式地址變換SASBSC基址寄存器邏輯地址12dC基號(hào)段號(hào)頁(yè)號(hào)頁(yè)內(nèi)地址+b程序C段表SA+0SA+1SA+2SA+3程序A段表SC+0SC+1SC+2…ca+b+0b+1b+210頁(yè)表a段b段c段a+0a+1c+0c+178物理地址10物理頁(yè)號(hào)d頁(yè)內(nèi)地址虛擬存儲(chǔ)器的頁(yè)面替換算法當(dāng)產(chǎn)生頁(yè)面失效時(shí)，需要進(jìn)行頁(yè)面替換，區(qū)別于Cache的替換至少要訪問(wèn)外存一次，速度慢。由操作系統(tǒng)軟件實(shí)現(xiàn)頁(yè)面替換選擇余地大，屬于一個(gè)進(jìn)程的頁(yè)面都可替換。虛擬存儲(chǔ)器中的替換策略LRU算法LFU算法FIFO算法虛擬存儲(chǔ)器的頁(yè)面替換算法【例7】假設(shè)主存只有a,b,c三個(gè)頁(yè)框，組成a進(jìn)c出的FIFO隊(duì)列，進(jìn)程訪問(wèn)頁(yè)面的序列是0，1，2，4，2，3，0，2，1，3，2號(hào)。若采用①FIFO算法，②FIFO算法+LRU算法，用列表法分別求兩種替換策略情況下的命中率。命中

命中

命中

120