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

Cache的速度接近于CPU。1.三級結構的存儲器系統：將高速緩緩沖存儲器、主存儲器和輔助（虛擬）存儲器組成的統一管理、調度的一體化三級結構的存儲器系統。3.三種存儲器的比較

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

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

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

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

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

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

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

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

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

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

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