組成第十四講：快速緩沖存儲器

第七章存儲系統(tǒng)7.1存儲系統(tǒng)的層次結(jié)構(gòu)7.2高級緩沖存儲器7.3虛擬存儲器7.4相聯(lián)存儲器7.1存儲系統(tǒng)的層次結(jié)構(gòu)1.主存和輔存的概念2.主存和輔存在操作系統(tǒng)的控制下，通過軟硬件把主存和輔存統(tǒng)一成為一個整體，形成一個存儲層次。這個層次擁有接近于主存的速度和輔存的容量，價格也接近于輔存的價格。3.在CPU和主存之間有高速緩沖存儲器cache，這完全是由硬件來完成的。Cache－主存的速度接近于cache，而容量與價格接近于主存。

Cache的速度接近于CPU。1.三級結(jié)構(gòu)的存儲器系統(tǒng)：將高速緩緩沖存儲器、主存儲器和輔助（虛擬）存儲器組成的統(tǒng)一管理、調(diào)度的一體化三級結(jié)構(gòu)的存儲器系統(tǒng)。3.三種存儲器的比較

(1)高速緩存（Cache）：速度快，容量小，用于臨時存放運行中的指令和少量數(shù)據(jù)；

(2)主存：速度、容量一般，用于臨時存放運行中的大量程序和數(shù)；

(3)輔存：速度慢，容量大，用于永久存放大型程序軟件和數(shù)據(jù)庫。4.采用三級結(jié)構(gòu)的目的和方法

(1)Cache-主存層次：解決CPU與主存間速度不匹配問題，使系統(tǒng)具有主存容量和接近于Cache速度。采用地址映像方式，以字塊為基本信息單位。

(2)虛擬存儲器-主存層次：解決主存容量小、運行成本高的問題，使系統(tǒng)具有輔存容量和接近主存速度，且造價和運行成本低。采用地址變換方式，以段、頁為基本信息單位。局部性原理、一致性原則和包含性原則1.局部性原理——三級結(jié)構(gòu)存儲器系統(tǒng)運行原理基礎(chǔ)(1)時間局部性：在較小的時間間隔內(nèi)，最近被訪問的指令和數(shù)據(jù)很可能再次被訪問；(2)空間局部性：這些最近被訪問的指令和數(shù)據(jù)往往集中在一小片存儲區(qū)域中；(3)指令執(zhí)行方式局部性：順序執(zhí)行較轉(zhuǎn)移執(zhí)行可能性大。3.一致性原則：同時存放在三類存儲器中的信息，在三類存儲器中必須保持同值。

2.包含性原則：處在內(nèi)層的存儲器的信息一定包含在各外層存儲器中。即內(nèi)層存儲器中信息是外層存儲器所存信息的一小部分的副本。

Cache：一種容量小、速度快，用靜態(tài)存儲器器件實現(xiàn)的存儲器。作用：解決CPU與主存速度不匹配的問題，使系統(tǒng)速度接近于CPU，容量接近于主存。高速緩沖存儲器（cache）目前，組成主存的DRAM存取速度一般落后于CPU的處理速度，CPU訪問主存時不得不插入等待周期來適應(yīng)主存的速度，致使系統(tǒng)整體下降。高速緩沖存儲器Cache：是為解決CPU和DRAM之間的速度匹配而采用的一項重要技術(shù)；是發(fā)揮CPU高速高效的性能而設(shè)置的一種介于CPU和DRAM之間的高速小容量緩沖存儲器；存取速度要比主存快，由高速的SRAM組成；全部功能由硬件實現(xiàn)，保證了其高速度。高速緩沖存儲器（cache）cache的工作機制cache基本原理地址映象（映射）與地址變換cache與主存數(shù)據(jù)的一致性替換策略高速緩沖器cache的構(gòu)成cache的工作機制高速緩沖存儲器cache的工作機制基于程序訪問的局部性原則。一個運行程序的代碼大都順序存放在地址連續(xù)的存儲器中，與程序相關(guān)的數(shù)據(jù)在存儲器中也相對集中。程序運行時，尤其有循環(huán)程序段和子程序段時，在較短的時間區(qū)間內(nèi)，常會對局部范圍的存儲器頻繁訪問，某存儲單元被訪問了，該單位可能會被再次訪問，大多數(shù)存取又是在緊接著上次存取地址附近，而此范圍之外的地址訪問甚少。這種現(xiàn)象稱程序訪問的局部性。cache的工作機制根據(jù)局部性原理，可以在主存和CPU之間設(shè)置一個高速的容量相對較小的存儲器，如果當前正在執(zhí)行的程序和數(shù)據(jù)存放在這個存儲器中，在程序運行時，不必從主存儲器取指令和取數(shù)據(jù)，只需訪問這個高速存儲器，以提高程序運行速度。這個存儲器稱作高速緩沖存儲器Cache。Cache由高速的SRAM組成，它的工作速度數(shù)倍于主存，全部功能由硬件實現(xiàn)，并且對程序員是透明的。cache的工作機制cache基本原理Cache結(jié)構(gòu)設(shè)計必須解決的問題：如何存放，如何訪問，如何替換，如何改寫？數(shù)據(jù)塊在Cache中存放在哪個位置？即定位問題（地址映象）。如果一個塊存放在某一Cache中，怎樣確定并找到該塊，即尋址問題（地址變換）。不命中時將從主存儲器中訪問，并將該塊調(diào)入Cache中，但是如果Cache中已無空閑空間，則勢必將Cache中的某一塊調(diào)出，但應(yīng)調(diào)出那一塊，即替換問題。在寫訪問時，寫入Cache必須在適當?shù)臅r候?qū)懟刂鞔鎯ζ?，何時寫？寫操作時采用什么策略保證兩級存儲器間的數(shù)據(jù)一致性。寫操作失配時是否將訪問塊取入高層存儲器。cache基本原理高速緩沖存儲器包括：cache控制部件cache存儲器cache基本原理cache控制部件包括：主存地址寄存器主存－cache地址變換機構(gòu)替換控制部件cache地址寄存器控制部件均由硬件組成cache基本原理cache存儲器多采用與CPU相同類型的半導(dǎo)體集成電路制成的高速存儲元件SRAM；存取速度比主存快且與CPU接近；整個cache存儲器介于CPU和主存之間，直接接受CPU訪問；CPU不僅與cache相接，而且與主存仍然保持通路。cache基本原理在主存－cache存儲體系中，所有的程序和數(shù)據(jù)都在主存中，cache存儲器只存放主存一部分程序塊和數(shù)據(jù)塊的副本，這種以塊為單位的存儲方式是基于計算機程序的局部性。從程序局部性可知，cache中的程序塊和數(shù)據(jù)塊使CPU要訪問的內(nèi)容在大多數(shù)情況下已經(jīng)在cache存儲器里，CPU讀寫操作主要在CPU和cache之間進行。cache基本原理cache的命中任何時候都有一些主存塊處在Cache中。CPU訪問存儲體系時首先訪問cache，送出訪問單元的地址由地址總線打入cache存儲器的主存地址寄存器MA；主存－cache地址變換機構(gòu)從主存地址寄存器MA獲取地址判斷該單元內(nèi)容是否已在cache中存放副本，如果副本已經(jīng)在cache中了，稱為命中；反之稱不命中或命中失效。cache基本原理cache基本原理cache的命中率命中率指CPU所要訪問的信息在Cache中的比率；所要訪問的信息不在Cache中的比率稱為失效率。增加cache的目的，就是在性能上使主存的平均讀出時間盡可能接近cache的讀出時間。因此，cache的命中率應(yīng)接近于1。由于程序訪問的局部性，這是可能的。cache基本原理當命中時立即把訪問地址變換成它在cache的地址，然后驅(qū)動cache存儲體。當是讀操作時，CPU從cache中直接讀取信息；若是寫操作，不但要把新內(nèi)容寫入cache存儲器中，而且必須同時寫入主存，使主存和cache內(nèi)容同時修改，保證主存和副本內(nèi)容一致，這種方法也叫直達法。cache基本原理有的機器考慮到當寫入操作很頻繁或者寫入的是中間結(jié)果，每次寫入主存很浪費時間，于是設(shè)計成每次只改寫cache的內(nèi)容并不立即修改主存中相應(yīng)的單元，只有當cache中被寫過的塊要被新進入cache的信息塊取代時才一次寫回主存里，這種方法稱回寫法。cache基本原理如果CPU要訪問的內(nèi)容根本不在cache中，即“不命中”，那么CPU轉(zhuǎn)去直接訪問主存。若是讀操作，CPU則從主存讀取信息的同時，cache控制部件把該地址所在那塊存儲內(nèi)容從主存一次調(diào)進cache存儲器，以存儲塊為單位調(diào)入cache存儲器可以提高下次訪問的命中率。若是寫操作，則處理就簡單多了，很多計算機系統(tǒng)只向主存寫入信息，不必同時把這個地址所在的存儲內(nèi)容再調(diào)入cache存儲器中。cache基本原理直達法：優(yōu)點：數(shù)據(jù)不會出現(xiàn)不一致缺點：對寫操作沒有高速緩存的作用回寫法：優(yōu)點：速度快缺點：存在數(shù)據(jù)不一致隱患cache基本原理對于共享一個主存的多處理機系統(tǒng)，因為處理機各自擁有cache存儲器，所以必須采用寫直達法將任何一個cache中修改的內(nèi)容同時寫入主存，保證其他cache向主存調(diào)用信息塊時是修改過的而不是失效的信息。這點對于擁有多個處理機而共享一個主存的計算機系統(tǒng)特別重要。7.2高速緩沖存儲器（cache）cache的工作機制cache基本原理地址映象（映射）與地址變換cache與主存數(shù)據(jù)的一致性替換策略高速緩沖器cache的構(gòu)成地址映象(映射)與地址變換地址映象把主存塊按照某種規(guī)則（函數(shù)或方法）裝入或定位到Cache中的過程稱地址映象。地址變換信息按這種映象關(guān)系裝入Cache后，執(zhí)行程序時，將主存地址變換成Cache地址的變換過程叫做地址變換。地址映象和變換密切相關(guān)。地址映象(映射)與地址變換使用Cache的動力在于它的高速，因此也要求這個地址變換過程盡可能地快，故此過程是以硬件完成的。這帶來的另一好處是Cache的透明性，除了程序運行速度提高之外，用戶包括系統(tǒng)軟件編制人員，絲毫未感覺到Cache的存在。地址映象(映射)與地址變換在高速緩沖存儲器中把Cache和主存機械等分為相同大小的塊，每一塊是由若干個字（或字節(jié)）組成。例：某機主存容量為1MB，劃分為2048塊，每塊512B；Cache容量為8KB，劃分為16塊，每塊512B。塊0塊1塊15Cache標記標記標記塊0塊1塊2047主存m位

塊…字0字1字511地址映象(映射)與地址變換由于Cache的塊數(shù)遠小于主存的塊數(shù)，因此一個Cache不能唯一地、永久地只對應(yīng)一個貯存塊，在Cache中，每一塊外加有一個標記，指明它是主存的哪一塊的副本（拷貝）。塊0塊1塊15Cache標記標記標記塊0塊1塊2047主存m位

塊…字0字1字511地址映象(映射)與地址變換標記的有效位每個標記設(shè)置有一個有效位。機器加電啟動時，Reset信號將所有標記的有效位置“0”，即無效。程序執(zhí)行過程中，Cache不命中時，逐步將指令塊或數(shù)據(jù)塊從主存調(diào)入Cache中的某一塊，并將這一塊標記的有效位置“1”，當再次用到這一塊中的指令或數(shù)據(jù)時，可直接從Cache中取指令或數(shù)據(jù)。字塊0字塊1字塊Lm-1~~~~.........標記Cache012r-1

標記有效位地址映象(映射)與地址變換因剛加電時所有標記位都為“0”，開始執(zhí)行程序時，命中率較低。另外Cache的命中率還與程序本身有關(guān)，即不同的程序，其命中率可能不同。地址映象(映射)與地址變換基本的地址映象方式：直接映象全相連映象組相連映象地址映象(映射)與地址變換直接映射方式這是一種多對一的映射關(guān)系，一個主存塊只能映象到Cache的一個特定塊位置上去。在這種映象方式中：主存的第0塊，第16塊，第32塊，…，只能映象到Cache的第0塊；而主存的第1塊，第17塊，第33塊，…，只能映象到Cache的第1塊；……地址映象(映射)與地址變換直接映象7位Cache地址4位9位主存地址7位4位9位11位9位主存地址地址映象(映射)與地址變換直接映象的地址變換方法地址映象(映射)與地址變換優(yōu)點：實現(xiàn)簡單，只需利用主存地址按某些字段直接判斷，即可確定所需字塊是否已在Cache中。缺點：不夠靈活，主存的多個字塊只能對應(yīng)唯一的Cache字塊，因此，即使Cache別的地址空著也不能占用。Cache存儲空間得不到充分利用，降低了命中率。地址映象(映射)與地址變換全相聯(lián)映象方式塊0塊1塊15Cache標記標記標記標記標記標記.........塊0塊1塊15塊16塊17塊31塊2047主存TagCache地址4位9位11位9位主存地址允許主存中的每一個字塊映象到Cache的任何一個字塊位置上，最靈活但成本最高的一種方式。地址映象(映射)與地址變換全相聯(lián)映象的地址變換方法地址映象(映射)與地址變換全相聯(lián)映象的地址變換方法的優(yōu)缺點：優(yōu)點：靈活，塊沖突概率小。只有當Cache中全部裝滿后，才有可能出現(xiàn)塊沖突；缺點：要作相聯(lián)搜索，速度慢，代價高。地址映象(映射)與地址變換這只是一個理想的方案。兩個原因使其實際上很少采用：標記位數(shù)從7位增加到11位，使Cache標記容量加大；訪問Cache時，需要和Cache的全部標記進行“比較”才能判斷出所訪主存地址的內(nèi)容是否已在Cache中。由于Cache速度要求高，通常由“按內(nèi)容尋址”的相聯(lián)存儲器完成，所需硬件邏輯電路很多，以至于無法用于cache中。實際的Cache組織則是采取各種措施來減少所需比較的地址數(shù)目。地址映象(映射)與地址變換組相聯(lián)映射方式組間全相聯(lián)，組內(nèi)直接映像直接映象和全相聯(lián)映象方式的一種折衷方案。地址映象(映射)與地址變換注意：當Cache只有一個組并且每組16塊時，此時為直接映像；當Cache有16組并且每組一個塊時，則為全相聯(lián)映像。8位3位9位1位3位9位7.2高速緩沖存儲器（cache）cache的工作機制cache基本原理地址映象（映射）與地址變換cache與主存數(shù)據(jù)的一致性替換策略高速緩沖器cache的構(gòu)成cache與主存數(shù)據(jù)的一致性cache中存放的是主存中部分信息的副本。為了保證CPU存取的數(shù)據(jù)準確無誤，要求cache中每一個地址上的數(shù)據(jù)與主存中相應(yīng)存儲單元的數(shù)據(jù)保持完全相同，這種性質(zhì)稱cache與主存數(shù)據(jù)的一致性。寫直達法和回寫法是常見的保持數(shù)據(jù)一致性的算法。cache與主存數(shù)據(jù)的一致性cache與主存數(shù)據(jù)的不一致的情況：CPU從cache讀入數(shù)據(jù)重新寫入修改后的新數(shù)據(jù)時；主存數(shù)據(jù)修改。例如多處理機系統(tǒng)，其中一個cache內(nèi)容修改后立即用寫直達法寫入主存又導(dǎo)致主存數(shù)據(jù)可能與其他cache的副本不一致。又例如，計算機的DMA訪問直接修改了主存數(shù)據(jù)，也可能造成與cache數(shù)據(jù)的不一致性。cache與主存數(shù)據(jù)的一致性通常采用的處理辦法有：主存監(jiān)視法：利用硬件機構(gòu)使cache控制器能監(jiān)視所有設(shè)備對主存的操作或訪問，凡對主存的寫入也立即對cache中相應(yīng)單元進行拷貝，從而保證數(shù)據(jù)的一致性設(shè)置“不可cache區(qū)”：即在主存中開辟一塊存儲區(qū)域，該區(qū)域數(shù)據(jù)不能調(diào)入cache，不受cache控制器管理，但其他設(shè)備進入的數(shù)據(jù)只能直接寫入該區(qū)域。所以不會產(chǎn)生與cache中數(shù)據(jù)的不一致性?！安豢蒫ache區(qū)”可以通過BIOS設(shè)置程序來設(shè)置。7.2高速緩沖存儲器（cache）cache的工作機制cache基本原理地址映象（映射）與地址變換cache與主存數(shù)據(jù)的一致性替換策略高速緩沖器cache的構(gòu)成替換策略在主存－cache存儲體系工作過程中，主存和cache存儲器之間信息以塊為單位調(diào)度，信息塊的長度取決于主存的結(jié)構(gòu)設(shè)計，主存常設(shè)計成多體交叉存儲結(jié)構(gòu)。當信息塊需要調(diào)入cache存儲器而cache存儲器中已經(jīng)占滿信息時，cache存儲器的替換控制部件將按一定的替換策略淘汰cache中舊有的一塊信息，被更新的舊信息塊應(yīng)該是下一段時間內(nèi)估計是最少使用的，然后用新的信息塊覆蓋掉。替換策略常用的替換策略有兩種：

先進先出策略－FIFO策略總是更換掉當前cache中最先進入的信息塊這種方法控制簡單，實現(xiàn)容易近期最少使用策略－LRU策略替換策略近期最少使用策略－LRU策略：遵循的規(guī)則是新信息塊替代的是當前cache存儲器中被使用次數(shù)最少的，即最不活躍的那塊信息；使用LRU方法的cache存儲器每一個字塊都要附設(shè)一個計數(shù)器記錄被使用的情況，每當cache中的一塊信息被命中時，比命中塊計數(shù)值低的信息塊均加1，而命中塊計數(shù)器清0；顯然，這種技術(shù)方法各信息塊的計數(shù)值總是不相同的。替換策略一旦不命中情況發(fā)生時，新信息塊從主存調(diào)入cache存儲器替換計數(shù)值最大的那片存儲區(qū)，新信息塊計數(shù)值為0，其余信息塊計數(shù)均加1，保證了那些活躍的信息塊－－經(jīng)常被命中或最近被命中的信息塊計數(shù)值要小，而近來越來越不活躍的信息塊計數(shù)值越大；LRU策略是目前使用較多的一種策略，能夠有效的提高命中率。替換策略無論FIFO策略還是LRU策略，其實最先被調(diào)入cache的信息塊或最近最少使用的信息塊都不能肯定是最近將絕不會使用，所以替換策略不能作為最合理最優(yōu)秀的。但是研究表明，F(xiàn)IFO和LRU策略明顯地提高了cache存儲器的命中率，可以達到百分之九十左右，其中LRU策略的命中率比FIFO更高一些。替換策略Cache的命中率反映了CPU需要訪問的數(shù)據(jù)在cache中能直接找到的概率。影響命中率的因素有：替換策略cache的結(jié)構(gòu)因素包括cache高速緩沖存儲器大小、傳送塊的大小若cache的存儲容量越大，保存副本越多，命中率就越高訪問程序和數(shù)據(jù)