第6章存儲系統(tǒng)

存儲系統(tǒng)第

6

章6.1存儲系統(tǒng)層次結(jié)構(gòu)6.2高速緩沖存儲器6.3.1Cache概述6.3.2Cache的工作原理6.3.3Cache的組織方式6.3.4替換算法和更新策略

6.3虛擬存儲器6.4.1虛擬存儲器概述6.4.2段式虛擬存儲器6.4.3頁式虛擬存儲器6.4.4段頁式虛擬存儲器6.4.5快表與慢表掌握cache的基本原理、地址映射、替換策略；掌握虛擬存儲器的基本概念以及段式、頁式、段頁式虛擬存儲器的原理；了解只讀存儲器、閃速存儲器的原理及存儲保護的原理。了解外存儲設(shè)備的發(fā)展動態(tài)。

教學要求第6.1節(jié)存儲系統(tǒng)的層次結(jié)構(gòu)存儲系統(tǒng)的層次結(jié)構(gòu)衡量存儲器有三個指標:容量、速度和價格/位.單一的存儲器很難同時滿足三個指標.

因為存取時間越短,每位的價格就越高;容量越大,每位的價格就越低;容量越大,存取時間就越長.存儲系統(tǒng)實現(xiàn)：存儲系統(tǒng)不是硬件的簡單堆積，是硬軟件相結(jié)合的方法連接而成的系統(tǒng)。這個系統(tǒng)對應(yīng)用程序員透明。這個存儲器的速度接近速度最快的那個存儲器,存儲器容量與容量最大的那個存儲器相等或接近,單位容量的價格接近最便宜的那個存儲器.存儲系統(tǒng)的層次結(jié)構(gòu)主板內(nèi)存儲器寄存器Cache主存儲器主板外存儲器磁盤CD-ROMCD-RWDVD-RWDVD-RAM離線存儲器磁帶MO(光－磁盤)WORM(一寫多讀光盤)第6.2節(jié)Cache高速緩沖存儲器內(nèi)存主要是DRAM，價格低、容量大，但存取速度難以提高；而CPU速度提高很快。目前CPU的速度比DRAM要快一個數(shù)量級以上，導致兩者速度不匹配。只有雙極型TTLSRAM，存取速度與CPU處于同一量級，但價格較貴，功耗很大，集成度低，所以不能將所有DRAM都采用SRAM。折中的辦法是分級處理，在主存和CPU之間加一個容量相對小的雙極型SRAM作為高速緩沖存儲器Cache。

目前Cache的分為一級Cache、二級Cache等。Cache的命中率可達到90%-98%，這樣就大大提高了CPU訪問數(shù)據(jù)的速度。Cache高速緩沖存儲器6.2.1Cache概述6.21.使用Cache的必要性Cache高速緩沖存儲器6.2.1Cache概述時間局部性:在一小段時間內(nèi)，最近被訪問過的程序和數(shù)據(jù)很可能再次被訪問；空間局部性:這些最近被訪問過的程序和數(shù)據(jù)，往往集中在一小片存儲區(qū)域中；

指令執(zhí)行順序方面：指令順序執(zhí)行比轉(zhuǎn)移執(zhí)行的可能性要大（大約為5:1），因此，合理地把數(shù)據(jù)和程序放在不同的存儲介質(zhì)中。這種對局部范圍的存儲器地址頻繁訪問，而對此范圍以外的地址則訪問甚少的現(xiàn)象就稱為程序訪問的局部性。6.22.程序訪問的局部性3.Cache-CPU-主存之間的關(guān)系關(guān)系CPUCache主存字傳送塊傳送…...…...主存塊Cache標記結(jié)構(gòu)6.2.1CACHE概述1.cache基本結(jié)構(gòu)

Cache和主存分同樣大小的塊；主存中只有一小部分塊的內(nèi)容可放在Cache中.在cache中每一塊都有一個標記,

指明它是主存的哪一塊的副本，該標記的內(nèi)容相當于主存中塊的編號，設(shè)主存地址為n位，且n=m+b，則主存的塊數(shù)M=2n/2b=2m

，塊內(nèi)字節(jié)數(shù)B=2b。

cache地址碼=（c+b）位。cache的塊數(shù)為2c。塊內(nèi)字節(jié)數(shù)與主存相同。6.2.2高速緩存工作原理2.Cache工作原理它由cache存儲體、地址映像變換機構(gòu)、cache替換機構(gòu)模塊組成。6.2.2CACHE的工作原理3.Cache的設(shè)計要素Cache容量映射功能直接映射組相聯(lián)映射全相聯(lián)映射替換算法最近最少使用（LRU）先進先出（FIFO）最不經(jīng)常使用（LFU）隨機寫策略寫通過(writethrough)回寫(writeback)寫一次塊大小Cache數(shù)目一級或二級統(tǒng)一或分離6.2.2CACHE的工作原理塊長：塊的大小，塊長一般取一個主存周期所能調(diào)出的信息長度。Pentium為32個字節(jié)。cache的容量和塊的大小是影響cache的效率的重要因素。通常用“命中率”來測量cache的效率。命中率：指CPU所要訪問的信息在cache中的比率。失效率：將所要訪問的信息不在cache中的比率。cache的存儲容量比主存的容量小得多；太小會使命中率太低；過大不僅會增加成本，且當容量超過一定位后，命中率隨容量的增加將不會有明顯地增長。4.cache的容量和塊大小6.2.2CACHE的工作原理5.cache的命中率增加cache的目的是在性能上使主存的平均讀出時間盡可能接近cache的讀出時間。因此cache的命中率應(yīng)接近于1。在一個程序執(zhí)行期間命中率Hc＝Nc/(Nc+Nm)

Nc表示Cache完成存取的總次數(shù)

Nm表示主存完成存取的總次數(shù)設(shè)Tc為Cache的存取周期，Hc為Cache的命中率，Tm為主存的存取時間，則平均存取時間T為：

T＝Hc*Tc+(1-Hc)Tm

追求的目標是：以較小的硬件代價使cache/主存系統(tǒng)的平均訪問時間T越接近Tc越好。cache的命中率還與程序有關(guān)，不同程序命中率可能不同。6.2.2CACHE的工作原理6.2.3cache存儲器組織主存的地址和cache地址間建立一種確定的邏輯關(guān)系，必須應(yīng)用某種函數(shù)把主存地址映像到cache，這樣的邏輯關(guān)系稱作地址映像。在信息按照這種映像關(guān)系裝入cache后，執(zhí)行程序時，將主存地址變換成cache地址，這個變換過程叫做地址變換。地址的映像和變換是密切相關(guān)的。地址映像方式：直接映像、全相聯(lián)映像、組相聯(lián)映像設(shè)主存儲器空間被分為Mm(0),Mm(1),…,Mmi),…,Mm(2m－1)，共2m塊,字塊大小為2b個字;設(shè)Cache存儲空間被分為Mc(0),Mc(1),…,Mc(j),…,Mc(2c－1，共2c個同樣大小的塊.6.2.3cache存儲器組織

直接映像：一個主存塊只能映像到cache中的唯一一個指定塊的地址映像方式。若這個位置已有內(nèi)容，則產(chǎn)生塊沖突，原來的塊將無條件到被替換出去。

直接相聯(lián)是一種最強的約束關(guān)系，它規(guī)定每個虛頁只對應(yīng)唯一的實頁。地址映像方法一般是將主存塊地址對cache的塊數(shù)取模得到cache中的塊地址，這相當于將主存的空間按cache的尺寸分區(qū)，每區(qū)內(nèi)相同的塊號映像到cache中相同的位置。在這種映像方式中，主存的第0塊，第2c塊，第2c+1塊，…，只能映像到cache的第0塊，而主存的第1塊，第2c+1塊，第2c+1+1塊，…，只能映像到cache的第1塊。以此類推。

1.直接映像6.2.3cache存儲器組織（1）直接映像cache組織

字塊0字塊1﹕字塊2c-1字塊0字塊1﹕字塊2c-1標記標記標記﹕﹕字塊2c+1-1字塊2c字塊2c+1主存字塊標記cache字塊地址塊內(nèi)地址t位c位b位m位主存地址比較器（t位）＝≠有效位=1主存儲器命中不命中cache存儲器字塊2c+1字塊2c+1+1﹕字塊2m-11主存分為M個區(qū)，每個區(qū)有2c個塊，總共有M2c塊，編號從0到M2c-1。Cache有2c個塊。第0區(qū)第1區(qū)第M-1區(qū)6.2.3cache存儲器組織這是一種多對一的映射關(guān)系，但一個主存塊只能映象到Cache的一個特定塊位置上去。

Cache的第i塊和主存的第j塊有如下函數(shù)關(guān)系：i=jmodm

(m為Cache的總塊數(shù)）

i=0,1,2,…,m-1

j=0,1,2,…,n-1在這種映象方式中：主存的第0塊，第16塊，第32塊，…，只能映象到Cache的第0塊；而主存的第1塊，第17塊，第33塊，…，只能映象到Cache的第1塊；……6.2.3cache存儲器組織直接映像方式Cache地址4位9位主存地址7位4位9位11位9位主存地址7位6.2.3cache存儲器組織主存地址分成三段：區(qū)號、塊號和塊內(nèi)地址。區(qū)號(組號)作為標志存放在地址映象表中，用于判斷命中與否。塊號直接用于查地址映象表;塊內(nèi)地址用于塊內(nèi)尋址。在訪存操作時，根據(jù)主存地址中的塊號讀出塊表中的區(qū)號，并與當前地址的區(qū)號進行比較，結(jié)果相同表cache命中，訪問可對cache進行；不相同則表示不命中，訪問需對主存進行。6.2.3cache存儲器組織（2）直接映像的地址變換方法比較相等且有效位相等6.2.3cache存儲器組織CPU送來的主存地址和讀／寫命令后，只需根據(jù)中間c位字段找到cache存儲器字塊，然后,看其標記是否與主存地址高t位符合:

如果符合且有效位為“1”，則可根據(jù)b位塊內(nèi)地址，從cache中取得所需指令或數(shù)據(jù)；如果不符合或有效位為“0”，就從主存讀入新的字塊來替換舊的字塊，并將CPU所需數(shù)據(jù)送往CPU，同時修改cache標記。假如原來有效位為“0”，還要將有效位改置成“1”。直接映像方式的缺點是不夠靈活，即主存的2t個字塊只能對應(yīng)惟一的cache存儲器字塊，因此，即使cache存儲器別的許多地址空著也不能占用。這使得cache存儲空間得不到充分利用，并降低了命中率。（2）直接映像地址變換方法（續(xù)）6.2.3cache存儲器組織優(yōu)點:硬件實現(xiàn)簡單，只需利用主存地址按某些字段直接判斷，即可確定所需字塊是否已在Cache中。成本低

缺點：不夠靈活，主存的多個字塊只能對應(yīng)唯一的Cache字塊，塊沖突率很高，降低了命中率。（3）直接映像的特點6.2.3cache存儲器組織【例1】設(shè)一個cache的容量為2KB，每個塊為16B，求：①該cache可容納多少個塊？②如果主存容量是256KB，則主存有多少個塊？③主存的地址有多少位？cache地址有多少位？④進行地址映象時，存儲器的地址分成哪幾段？各段分別有多少位？【解】①cache中有2048/16=128個塊②主存有256K/16=16384個塊③主存容量為256KB=218字節(jié)，主存字節(jié)地址有18位。

cache容量為2KB=211字節(jié)，cache的字節(jié)地址為11位。④存儲器的字地址分三段：區(qū)號、塊號、塊內(nèi)字地址。區(qū)號的長度為18-11=7位，塊號為7位。塊內(nèi)字地址為4位。

全相聯(lián)映像是指主存中的任何一個字（字塊）均可以映像到CACHE中的任何一個字（字塊）的位置上，也允許從確實已被占滿的cache存儲器中替換出任何一個舊字塊。反過來說，CACHE的一個字（字塊）中，在不同時刻可能存放的是整個主存中的任何一個字（字塊）中的內(nèi)容，即二者的對應(yīng)關(guān)系是完全隨意的，沒有任何強制性的限制條件。

全相聯(lián)映像方式是最靈活但成本最高的一種方式。2.全相聯(lián)映像6.2.3cache存儲器組織塊0塊1塊15Cache標記標記標記標記標記標記.........塊0塊1塊15塊16塊17塊31塊2047主存Tag(1）全相聯(lián)映像方式Cache地址4位9位11位9位主存地址11位允許主存中的每一個字塊映象到Cache的任何一個字塊位置上最靈活但成本最高的一種方式。6.2.3cache存儲器組織（2）全相聯(lián)映像cache組織

字塊0字塊1﹕字塊i字塊0字塊1﹕字塊2c-1標記標記標記﹕字塊2m-1﹕﹕主存字塊標記塊內(nèi)地址m=t+c位b位主存地址比較器（m位）＝≠有效位=1主存儲器命中不命中cache存儲器m=t+c所有標記6.2.3cache存儲器組織（3）全相聯(lián)映像的地址變換方法6.2.3cache存儲器組織1.對CACHE的使用可以有最大的靈活性。只要CACHE中有空閑的單元，可確保進行寫操作。當CACHE已滿，要寫入時可以方便地選擇一個CACHE單元進行騰空。2.Cache的塊沖突概率最低，空間利用率最高，地址變換速度慢.3.比較操作的電路過多、過于復雜，實現(xiàn)成本高難以實現(xiàn)。

CACHE讀寫操作時，用原本讀主存的整個（或部分）地址去與CACHE的標志字段的內(nèi)容實現(xiàn)比較時，必須與整個CACHE中每一個單元的標志字段都比較，才能知道要讀的信息是否已在CACHE中。4.使用條件：由于僅在CACHE容量很小時方可選用。（4）全相聯(lián)映像方式的特點6.2.3cache存儲器組織組相聯(lián)映像將主存空間按cache大小等分成區(qū)后，再將cache空間和主存空間中的每一區(qū)都等分成大小相等的組。讓主存各區(qū)中某組中的任何一塊，均可直接映像裝入cache中對應(yīng)的任何一塊位置上。

組相聯(lián)映像方式是直接映像和全相聯(lián)映像方式的一種折衷方案。特點：

1.組相聯(lián)映像方式的性能與復雜性介于直接映像與全相聯(lián)映像兩種方式之間。2.組相聯(lián)映像方式的優(yōu)缺點介于直接映像與全相聯(lián)映像兩種方式之間。3.cache的命中率除了與地址映像的方式有關(guān)外，還與cache的容量有關(guān)。cache容量大，命中率高，但達到一定容量后，命中率的提高就不明顯了。3.組相聯(lián)映像6.2.3cache存儲器組織（1）組間全相聯(lián)，組內(nèi)直接映像8位3位9位8位1位3位9位注意：當只有一個組并且每組16塊時，此時為直接映像；當有16組并且每組一個塊時,則為全相聯(lián)映像。6.2.3cache存儲器組織組相聯(lián)映像Cache組織001213……147151681718919……301531…………203210162033203410172035……204610232047001213……14715設(shè)主存為1MB=220Cache為8KB=213塊長為0.5KB=29塊數(shù)=8KB/0.5KB=16Cache為二路組相聯(lián)組數(shù)=塊數(shù)/路數(shù)=16/2=8主存地址格式19131210980主存高位組號塊號塊內(nèi)地址Cache地址格式1210980組號塊號塊內(nèi)地址注:塊號是組內(nèi)塊號的縮稱組號是Cache內(nèi)組號的縮稱組組第0區(qū)第1區(qū)第127區(qū)塊塊

Cache與主存均分組,主存中一個組內(nèi)的塊數(shù)與Cache的分組數(shù)相同,主存中的各塊與Cache的組號有固定的映象像關(guān)系,但可自由映像到對應(yīng)的Cache組中任一塊.（2）組間直接映像，組內(nèi)全相聯(lián)注意：當只有一個組并且每組16塊時，此時為全相聯(lián)映像；當有16組并且每組一個塊時,則為直接映像。1位1位9位Cache組號塊號塊內(nèi)地址區(qū)號6位1位1位9位組號塊號塊內(nèi)地址主存塊0塊1塊Cache標記標記標記標記標記標記0組塊0塊1塊3塊4塊127Tag標記塊230組1組塊21組塊5塊6塊7..0組1組塊124塊125塊1261組0組0區(qū)1區(qū)63區(qū)..6.2.3cache存儲器組織目前微機中Cache一般裝在主板上，在Intel486CPU中集成了8KB的數(shù)據(jù)和指令共用的Cache；在PentiumCPU中集成了8KB的數(shù)據(jù)Cache和8KB的指令Cache，與主板上的Cache形成兩級Cache結(jié)構(gòu)。當CPU發(fā)出讀請求時，將主存地址m位（或m位中的一部分）與cache某塊的標記相比較，根據(jù)其比較結(jié)果是否相等而區(qū)分出兩種情況：①當比較結(jié)果相等時，說明需要的數(shù)已在cache中，那么直接訪問cache就行了，在CPU與cache之間，通常一次傳送一個字；這種情況稱為訪問cache命中。②當比較結(jié)果不相等時，說明需要的數(shù)據(jù)尚未調(diào)入cache，那么就要把該數(shù)據(jù)所在的整個字塊從主存一次調(diào)進來。這種情況稱為訪問cache不命中。1.cache的讀工作原理6.2.4替換算法和更新策略

cache存儲器中保存的字塊是主存中相應(yīng)字塊的一個副本。如果程序執(zhí)行過程中要對該字塊的某個單元進行寫操作，就會遇到如何保持cache與主存的一致性問題。寫入方式通常有兩種：暫時只向cache存儲器寫入，并用標志加以注明，直到經(jīng)過修改的字塊被從cache中替換出來時才一次寫入主存；這種方式稱為標志交換（flag-swap）方式。每次寫入cache同時寫入主存，使cache和主存保持一致。稱為通過式寫（write-through），又稱寫直達法。

當被修改的單元根本就不在cache時，寫操作直接對主存進行，而不寫入cache存儲器。2.cache的寫策略6.2.4替換算法和更新策略

有效位:為了說明標記是否有效.當機器剛加電時,Reset信號將所有標記的有效位置“0”,使標記無效。在程序執(zhí)行的過程中,當Cache不命中時逐步將指令塊或數(shù)據(jù)塊從主存調(diào)入Cache中的某一塊,并將這一塊標記中的有效位置“1”.剛加電后所有標記位都為“0”，因此開始執(zhí)行程序時，命中率較低。6.2.4替換算法和更新策略cache的標記

在從主存讀出新的字塊調(diào)入cache存儲器時，如果遇到cache存儲器中相應(yīng)的位置已被其他字塊占有，那么就必須去掉一個舊的字塊，讓位于一個新的字塊。這種替換應(yīng)該遵循一定的規(guī)則，最好能使被替換的字塊是下一段時間內(nèi)估計最少使用的。這些規(guī)則稱為替換策略或替換算法，由替換部件加以實現(xiàn)。6.2.4替換算法和更新策略3.替換策略當一個新的主存塊要調(diào)入到cache，而允許存放此塊的行位置都被其它主存塊占滿時，就要產(chǎn)生替換，因為cache工作原理要求它應(yīng)盡量保存最新的