1、計(jì)算機(jī)系統(tǒng)結(jié)構(gòu),主講 蔡啟先,第3章 存儲(chǔ)系統(tǒng),3.1 存儲(chǔ)系統(tǒng)原理,3.2 虛擬存儲(chǔ)系統(tǒng),3.3 高速緩沖存儲(chǔ)器Cache,第 3 章 存 儲(chǔ) 系 統(tǒng),3.4 三級(jí)存儲(chǔ)系統(tǒng),3.7 存儲(chǔ)域網(wǎng)絡(luò)（SAN）,3.5 并行存儲(chǔ)器,3.6 RAID系統(tǒng),本章重點(diǎn),存儲(chǔ)系統(tǒng)原理和層次結(jié)構(gòu) 虛擬存儲(chǔ)器的概念、基本結(jié)構(gòu)、地址變換、替換算法 Cache的概念、基本結(jié)構(gòu)、設(shè)計(jì)與地址變換、替換算法,3.1 存儲(chǔ)系統(tǒng)原理,3.1.1 存儲(chǔ)系統(tǒng)的概念,3.1.2 存儲(chǔ)器的層次結(jié)構(gòu),一個(gè)存儲(chǔ)器的性能通常有三個(gè)主要參數(shù)：容量、價(jià)格和速度。 存儲(chǔ)器容量SM=Wlm。 其中，W為存儲(chǔ)體的字長(zhǎng)(單位為位或字節(jié))，l為每個(gè)存儲(chǔ)

2、體的字?jǐn)?shù)，m為并行工作的存儲(chǔ)體個(gè)數(shù)。,3.1.1 存儲(chǔ)系統(tǒng)的概念,存儲(chǔ)器的速度可以用訪問(wèn)時(shí)間TA、存取周期TM和頻寬(也稱帶寬)Bm來(lái)描述。 TA是存儲(chǔ)器從接到訪存讀申請(qǐng)，到信息被讀到數(shù)據(jù)總線上所需的時(shí)間。這段時(shí)間是處理機(jī)在啟動(dòng)訪存申請(qǐng)后必須等待的時(shí)間。 TM則是連續(xù)啟動(dòng)一個(gè)存儲(chǔ)體所需要的間隔時(shí)間，它一般總比TA大。,存儲(chǔ)器頻寬是存儲(chǔ)器可提供的數(shù)據(jù)傳送速率，一般用每秒鐘傳送的信息位數(shù)(或字節(jié)數(shù))來(lái)衡量，又分最大頻寬(或稱極限頻寬)和實(shí)際頻寬。 最大頻寬Bm是存儲(chǔ)器連續(xù)訪問(wèn)時(shí)能提供的頻寬。單體的Bm=W/TM。m個(gè)存儲(chǔ)體并行工作時(shí)可達(dá)到的最大頻寬Bm=Wm/TM。由于存儲(chǔ)器不一定總能連續(xù)滿負(fù)荷地

3、工作，所以，實(shí)際頻寬往往要低于最大頻寬。,存儲(chǔ)器的價(jià)格可以用總價(jià)格C或每位價(jià)格c來(lái)表示。具有SM位的存儲(chǔ)器每位價(jià)格c=C/SM。存儲(chǔ)器價(jià)格包含了存儲(chǔ)單元本身及為該存儲(chǔ)器操作所必須的外圍電路的價(jià)格。,計(jì)算機(jī)系統(tǒng)總希望存儲(chǔ)器能在盡可能低的價(jià)格下，提供盡量高的速度和盡量大的存儲(chǔ)容量。在速度上應(yīng)盡量和CPU匹配，容量上應(yīng)盡可能放得下所有系統(tǒng)軟件和多個(gè)用戶軟件及其運(yùn)行時(shí)所需的空間。 只用一種存儲(chǔ)器無(wú)法解決上述高速度、大容量、低價(jià)格的要求。 有兩個(gè)途徑，一個(gè)是用多種類型的存儲(chǔ)器組成具有一定層次的存儲(chǔ)系統(tǒng)，組合實(shí)現(xiàn)存儲(chǔ)器的大容量、高速度和低價(jià)格要求，一個(gè)是發(fā)展并行存儲(chǔ)體系，通過(guò)并行訪存來(lái)提高存儲(chǔ)器的性能。,

4、存儲(chǔ)系統(tǒng)的定義,多個(gè)性能各不相同的存儲(chǔ)器用硬件或軟件方法連接成一個(gè)系統(tǒng)。這個(gè)系統(tǒng)對(duì)應(yīng)用程序員透明。在應(yīng)用程序員看來(lái)，它是一個(gè)存儲(chǔ)器，其速度接近速度最快的那個(gè)存儲(chǔ)器，存儲(chǔ)容量與容量最大的那個(gè)存儲(chǔ)器相等或接近，單位容量的價(jià)格接近最便宜的那個(gè)存儲(chǔ)器。,設(shè)n個(gè)存儲(chǔ)器M1(T1,S1,C1)、M2(T2,S2,C2)、Mn(Tn,Sn,Cn)構(gòu)成一個(gè)存儲(chǔ)器系統(tǒng)， 從外部看： 該存儲(chǔ)器的存儲(chǔ)周期 Tmin(T1,T2,Tn) 存儲(chǔ)器的容量 Smax(S1,S2,Sn) 存儲(chǔ)器每位的價(jià)格 Cmin(C1,C2,Cn),從外部看 T,S,C,M1 (T1,S1,C1),M2 (T2,S2,C2),Mn (Tn

5、,Sn,Cn),例：兩種存儲(chǔ)系統(tǒng),Cache存儲(chǔ)系統(tǒng)：由Cache與主存儲(chǔ)器構(gòu)成，目標(biāo)是提高速度，全部采用硬件調(diào)度，對(duì)系統(tǒng)程序員透明。 虛擬存儲(chǔ)系統(tǒng)：由主存儲(chǔ)器與外存儲(chǔ)器構(gòu)成，目標(biāo)是擴(kuò)大存儲(chǔ)容量，采用軟硬件結(jié)合方法調(diào)度，對(duì)應(yīng)用程序員透明。,對(duì)S、C、T的討論,設(shè)M1和M2構(gòu)成一個(gè)存儲(chǔ)器，其中： S1C2 T1T2 存儲(chǔ)容量 S=S2（選擇大容量存儲(chǔ)器進(jìn)行編址） 單位容量的平均價(jià)格CC2,3. 訪問(wèn)周期T,1）命中率H：在M1（較高速度存儲(chǔ)器）中訪問(wèn)到的概率 設(shè)N1、N2分別為訪問(wèn)M1、M2的次數(shù)，則 H=N1/(N1+N2) 2) 存儲(chǔ)系統(tǒng)的訪問(wèn)周期T T=HT1+(1-H) T2 H為命中率

6、 當(dāng)H1時(shí)，TT1 3) T與T1接近程度用訪問(wèn)效率e表征,e=f(H,T2/T1),說(shuō)明：要使T接近T1，一是提高命中率，二是兩個(gè)存儲(chǔ)器速度之比不能過(guò)大 改進(jìn)方法： 對(duì)虛擬存儲(chǔ)器，加大調(diào)用塊與改進(jìn)替換算法等 對(duì)Cache存儲(chǔ)系統(tǒng)，采用多級(jí)Cache、加大Cache、預(yù)取技術(shù)、改進(jìn)替換算法等,CPU 內(nèi)部,通用寄存器堆 指令和數(shù)據(jù)緩沖棧,主存,脫機(jī)外存,聯(lián)機(jī)外存,Cache,訪 問(wèn) 速 度 、 每 位 價(jià) 格,存 儲(chǔ) 容 量,3.1.2 存儲(chǔ)器的層次結(jié)構(gòu),存儲(chǔ)層次之間的關(guān)系,工作速度：TiCi+1,虛擬存儲(chǔ)系統(tǒng)：主存與聯(lián)機(jī)外存共同組成 主存：DRAM，容量小、速度快、價(jià)格高 外存：磁盤，容量大

7、、速度慢、價(jià)格低 虛擬存儲(chǔ)器完成主存-輔存的存儲(chǔ)層次工作。 目標(biāo)：增加快速的存儲(chǔ)器容量。 虛擬存儲(chǔ)器的建立和管理主要基于軟件，因此對(duì)系統(tǒng)程序員是不透明的。,3.2 虛擬存儲(chǔ)系統(tǒng),3.2.1 虛擬存儲(chǔ)器的工作原理 3.2.2 地址映象及地址變換 3.2.3 頁(yè)面替換算法 3.2.4 提高主存命中率的方法,3.2 虛擬存儲(chǔ)系統(tǒng),3.2.1 虛擬存儲(chǔ)器的工作原理,虛擬存儲(chǔ)器的地址空間有三種： 虛地址空間，它是應(yīng)用程序員編程的地址空間，這個(gè)地址空間非常大； 主存地址空間，又稱實(shí)存地址空間； 輔存地址空間，即磁盤地址空間。,以頁(yè)式虛存為例 頁(yè)（Page）：固定大小的塊（116KB） 主存分頁(yè)：實(shí)頁(yè) 虛存

8、分頁(yè)：虛頁(yè) 主存地址A 虛地址Av,內(nèi)部地址變換 U、Pp,外部地址變換（查外頁(yè)表） U、P外存實(shí)地址,聯(lián)機(jī)外存地址,主存頁(yè)面表,頁(yè)面替 換算法,I/O通道,啟動(dòng)脫機(jī)外存,命中 訪問(wèn)主存,選主存頁(yè),頁(yè)內(nèi) 地址,主存,未 命 中,未命中,訪聯(lián)機(jī)外存,主存頁(yè)面失效，查內(nèi)頁(yè)表,命中,主存未 滿，有 空頁(yè)號(hào),主存 滿,主存頁(yè)號(hào),調(diào)入頁(yè),被替換頁(yè),選頁(yè),頁(yè)式虛存的工作過(guò)程,虛地址Av 內(nèi)部地址變換未命中 外部地址變換查外頁(yè)表 命中 得到P對(duì)應(yīng)的實(shí)地址 無(wú) 實(shí)頁(yè)號(hào)p、d 查內(nèi)頁(yè)表 啟動(dòng)脫機(jī)外存 訪問(wèn)主存 有空頁(yè)號(hào) 無(wú)空頁(yè)號(hào) 調(diào)入主存 替換調(diào)入,3.2.2 地址映象及地址變換,地址映像：程序裝入時(shí)，建立用戶

9、虛地址與主存實(shí)地址的對(duì)應(yīng)關(guān)系，便于取指令。 地址變換：程序運(yùn)行時(shí)，用戶虛地址變換為主存實(shí)地址(內(nèi)部地址變換)或輔存地址(外部地址變換) ，便于數(shù)據(jù)存取。 三種類型的虛存：（1）段式虛擬存儲(chǔ)器 （2）頁(yè)式虛擬存儲(chǔ)器 （3）段頁(yè)式虛擬存儲(chǔ)器,1。段式虛擬存儲(chǔ)器,基本原理: 按程序內(nèi)容分段，長(zhǎng)度可長(zhǎng)可短。 建立段表（段號(hào)、段長(zhǎng)、段起始地址、段訪問(wèn)方式及標(biāo)志） 地址映像方法（示意） 地址變換過(guò)程（示意） ：,0段,1段,2段,3段,0,1,2,3,段號(hào),8K,16K,9K,30K,起始地址,程序段通過(guò)段表與主存中的區(qū)域唯一對(duì)應(yīng) 如第i程序段對(duì)應(yīng)段表中段號(hào)為i的一行，由起始地址和段長(zhǎng)即可找到主存中對(duì)應(yīng)的

10、段。,1K,500,200,200,段長(zhǎng),0 8K 9K 16K 30K,0 1K 0 500 0 200 0 200,程序空間,段表,主存儲(chǔ)器,地址映像方法,虛地址U、S、D段表基址寄存器堆 該用戶或作業(yè)的段表主存實(shí)地址,地址變換過(guò)程,用戶號(hào)U,段號(hào)S,段內(nèi)偏移D,6,As,段表基址寄存器,一個(gè)用戶（一道作業(yè)）的段表,多用戶虛地址,主存實(shí)地址,+,+,U=6,S=3,As,段表有關(guān)字段作用： 起始地址、段長(zhǎng)：位置保護(hù) 訪問(wèn)方式：保護(hù)級(jí)別 裝入位：程序段是否在主存中 標(biāo)志：是否修改,段式虛存的主要優(yōu)點(diǎn)： 程序的模塊化性能好 便于程序和數(shù)據(jù)的共享 程序的動(dòng)態(tài)鏈接和調(diào)度比較容易 便于實(shí)現(xiàn)信息保護(hù)

11、段式虛存的主要缺點(diǎn)： 地址變換費(fèi)時(shí) 主存利用率低 對(duì)輔存管理較困難,2。頁(yè)式虛擬存儲(chǔ)器,頁(yè)：虛實(shí)地址空間分為固定大小的塊，Page,一般為0.5kB的整數(shù)倍，116kB 地址映像方法 地址變換過(guò)程：,0頁(yè),1頁(yè),2頁(yè),3頁(yè),0,1,2,3,頁(yè)號(hào),主存頁(yè)號(hào),程序分頁(yè)頁(yè)表映像主存頁(yè),地址映像方法,虛地址U、P、D頁(yè)表基址寄存器堆該用戶或作業(yè)的頁(yè)表主存實(shí)地址,地址變換過(guò)程,用戶號(hào)U,虛頁(yè)號(hào)P,頁(yè)內(nèi)偏移D,Pa,頁(yè)表基址寄存器,頁(yè)表,多用戶 虛地址Av,實(shí)頁(yè)號(hào)p,+,Pa,主存實(shí)地址A,頁(yè)內(nèi)偏移d,頁(yè)式虛擬存儲(chǔ)器主要優(yōu)點(diǎn) 主存利用率高 頁(yè)表簡(jiǎn)單 地址映象與變換速度快 對(duì)輔存管理容易 頁(yè)式虛擬存儲(chǔ)器主要

12、缺點(diǎn) 程序的模塊化性能不好 頁(yè)表很長(zhǎng),3。 段頁(yè)式虛擬存儲(chǔ)器,段頁(yè)式虛存： 用戶虛存采用分段管理，主存采用分頁(yè)管理 地址映像方法 程序分段、頁(yè)查段表查該段頁(yè)表主存頁(yè),頁(yè)表地址,程序分段、頁(yè)查段表查該段頁(yè)表主存頁(yè),段頁(yè)式虛存地址映像方法,0段(12K),1段(10K),2段(5K),用戶程序,頁(yè)表地址,3,3,2,0段0頁(yè),0段1頁(yè),0段2頁(yè),段表,0段頁(yè)表,1段0頁(yè),1段1頁(yè),1段2頁(yè),1段頁(yè)表,2段0頁(yè),2段1頁(yè),2段頁(yè)表,主存,地址變換： 多用戶虛地址：用戶號(hào)U，段號(hào)S，虛頁(yè)號(hào)P，頁(yè)內(nèi)偏移D 段表基址寄存器 該用戶或作業(yè)的段表 該用戶或作業(yè)的頁(yè)表 主存實(shí)地址：實(shí)頁(yè)號(hào)p，頁(yè)內(nèi)偏移d,多用戶虛

13、地址U、S、P、D段表基址寄存器 該用戶或作業(yè)的段表相應(yīng)的頁(yè)表主存實(shí)地址,段頁(yè)式虛存地址變換過(guò)程,用戶號(hào)U,段號(hào)S,頁(yè)內(nèi)偏移D,段表基址寄存器,多用戶頁(yè)表,多用戶虛地址,+,+,主存地址A,As,虛頁(yè)號(hào)P,As,多用戶段表,頁(yè)內(nèi)偏移d,實(shí)頁(yè)號(hào)p,Ap,段頁(yè)式虛擬存儲(chǔ)器主要優(yōu)點(diǎn) 程序的模塊化較好 主存利用率高 對(duì)輔存管理容易 段頁(yè)式虛擬存儲(chǔ)器主要缺點(diǎn) 訪主3次：訪段表頁(yè)表各1次，再訪主存實(shí)地址，查表速度有待改進(jìn),4. 內(nèi)部地址變換方法的改進(jìn),（1）虛存速度降低的原因 多次訪主（多次查表） 頁(yè)表或段表容量超過(guò)一個(gè)頁(yè)面大小時(shí)，相加求地址方法不成立,（2） 減小頁(yè)表的解決辦法：,多級(jí)頁(yè)表：樹(shù)型結(jié)構(gòu)的多

14、級(jí)頁(yè)表,頁(yè)表基地 址寄存器,第1級(jí)頁(yè)表,第2級(jí)頁(yè)表,設(shè)虛存空間Nv，頁(yè)大小Np，頁(yè)表存儲(chǔ)字大小Nd，則頁(yè)表級(jí)數(shù)g： 如：設(shè)虛擬存儲(chǔ)空間Nv=4GB，頁(yè)面大小Np=1KB，頁(yè)表存儲(chǔ)字大小Nd=4B，則： 做法：一級(jí)頁(yè)表駐內(nèi)存，二級(jí)相關(guān)頁(yè)表調(diào)入內(nèi)存，其它放外存,（3）加快查表的方法,1）目錄表 壓縮頁(yè)表的存儲(chǔ)容量，頁(yè)表只含有已經(jīng)在主存的虛頁(yè)號(hào)，以便用Cache存放頁(yè)表,虛地址U、P拼接目錄表實(shí)頁(yè)號(hào)主存實(shí)地址,采用目錄表的地址變換過(guò)程,用戶號(hào)U,虛頁(yè)號(hào)P,頁(yè)內(nèi)偏移D,目錄表（按內(nèi)容訪問(wèn)的相聯(lián)存儲(chǔ)器）,多用戶 虛地址Av,實(shí)頁(yè)號(hào)p,相聯(lián)訪問(wèn),主存實(shí)地址A,頁(yè)內(nèi)偏移d,2）快慢表 U、P拼接的快表在Ca

15、che中，采用與目錄表相同的相聯(lián)方式訪問(wèn)，慢表（頁(yè)表）在主存儲(chǔ)器中。快、慢表同時(shí)查。若快表找到則終止慢表查詢，否則訪問(wèn)慢表。 3）散列函數(shù) 把多用戶虛頁(yè)號(hào)Pv變成快表地址Ah Ah=H(Pv) 若發(fā)生散列沖突，則查慢表,5。 外部地址變換,1）外部地址變換：在內(nèi)部地址變換未命中時(shí)（即發(fā)生頁(yè)面失效），找到輔存實(shí)地址，把所需頁(yè)或段調(diào)入主存中 2）嚴(yán)重頁(yè)面失效故障及其解決： 嚴(yán)重頁(yè)面失效故障：在指令跨頁(yè)、執(zhí)指跨頁(yè)時(shí)可能發(fā)生，作為異常故障處理 處理關(guān)鍵：保存和恢復(fù)故障點(diǎn)的現(xiàn)場(chǎng) 3種方法： 硬件緩沖寄存器：保存現(xiàn)場(chǎng)，處理后完整恢復(fù) 保存部分現(xiàn)場(chǎng)：處理后，再?gòu)念^執(zhí)行未完成的指令 指令預(yù)判技術(shù)：經(jīng)預(yù)判，事先

16、做好頁(yè)面失效處理,3）磁盤存儲(chǔ)器的格式 4）外部地址變換過(guò)程 用軟件實(shí)現(xiàn)，以頁(yè)式為例 用戶號(hào)U外頁(yè)表始地址 虛頁(yè)號(hào)P外頁(yè)表記錄（存儲(chǔ)字） 裝入位為1可得磁盤實(shí)地址 裝入位為0須將脫機(jī)外存調(diào)入 可采用多級(jí)頁(yè)表技術(shù) 若無(wú)需脫機(jī)外存裝入，則內(nèi)頁(yè)表和外頁(yè)表可合二為一,用戶號(hào)U外頁(yè)表始地址，虛頁(yè)號(hào)P外頁(yè)表記錄（存儲(chǔ)字）,外部地址變換過(guò)程,用戶號(hào)U,虛頁(yè)號(hào)P,頁(yè)內(nèi)偏移D,外部地址變換 （用軟件實(shí)現(xiàn)）,外頁(yè)表,多用戶 虛地址Av,磁盤實(shí)地址,找到該用戶程序 的外頁(yè)表首址,找到與該頁(yè)對(duì) 應(yīng)的存儲(chǔ)字,裝入位為1可得磁盤實(shí)地址，裝入位為0須將脫機(jī)外存調(diào)入,3.2.3 頁(yè)面替換算法,頁(yè)面替換要解決的問(wèn)題： 由于虛擬

17、存儲(chǔ)空間的頁(yè)數(shù)大大多于主存空間的頁(yè)數(shù)，一般主存空間必然全占用，因此當(dāng)發(fā)生頁(yè)面失效時(shí)，必須從輔存中調(diào)入新頁(yè)替換主存中不常用的頁(yè)。 評(píng)價(jià)頁(yè)面替換算法的主要標(biāo)準(zhǔn)： 命中率高 算法容易實(shí)現(xiàn),1。頁(yè)面替換算法,常用的頁(yè)面替換算法 1）隨機(jī)算法RAND（random algorithm）： 由隨即函數(shù)決定替換頁(yè)，最簡(jiǎn)單，但命中率低 2）先進(jìn)先出算法FIFO（first-in first-out algorithm）： 替換最先調(diào)入的頁(yè)，容易實(shí)現(xiàn)，但未反映程序的局部性,3）近期最少使用算法LRU（least recently used algorithm）： 選擇近期最少使用的頁(yè)進(jìn)行替換，算法能比較正確地反

18、映程序的局部性。最初為每頁(yè)設(shè)一個(gè)計(jì)數(shù)器，定時(shí)計(jì)數(shù)，調(diào)換時(shí)選計(jì)數(shù)時(shí)間最長(zhǎng)的頁(yè)替換，實(shí)現(xiàn)較復(fù)雜，且計(jì)數(shù)器字長(zhǎng)很長(zhǎng)，占空間。實(shí)際用到的LRU算法簡(jiǎn)化了計(jì)數(shù)方式，實(shí)現(xiàn)時(shí)在頁(yè)表或目錄表中對(duì)每一頁(yè)增設(shè)一個(gè)“使用次數(shù)”計(jì)數(shù)器字段，某頁(yè)調(diào)入時(shí)，該字段清0。這一頁(yè)被訪問(wèn)一次，該頁(yè)的計(jì)數(shù)器字段加1。計(jì)數(shù)值最小也即訪問(wèn)次數(shù)最少的頁(yè)就是替換頁(yè)，LRU算法較合理，也較易實(shí)現(xiàn)，被廣泛采用。 4）最優(yōu)替換算法OPT（optional replacement algorithm）： 理想算法，常用于做替換算法比較基準(zhǔn),例3.1 設(shè)某一道程序有15個(gè)虛頁(yè)，程序執(zhí)行時(shí)的訪存的頁(yè)地址流為：P1-P2-P1-P5-P4-P1-P3-

19、P4-P2- P4。若主存頁(yè)面數(shù)為3，請(qǐng)分別采用FIFO、LRU、OPT算法說(shuō)明對(duì)這3頁(yè)的使用和替換過(guò)程，并分別算出命中率。,例4.3 FIFO、LFU、OPT算法比較,程序執(zhí)行的頁(yè)地址流： P1-P2-P1-P5-P4-P1-P3-P4-P2-P4 主存頁(yè)面數(shù)為3 LFU算法的命中率接近OPT算法，說(shuō)明算法較好,解：分別采用FIFO、LRU、OPT算法對(duì)主存3頁(yè)的使用和替換過(guò)程如圖3-12所示。其中用“*”號(hào)標(biāo)記的虛頁(yè)是由該替換算法確定的被替換頁(yè)，“入”、“換”、“中”分別表示頁(yè)的調(diào)入、替換和命中情況。該程序訪存共10次，各算法的命中率如下： FIFO法：H=2/10=0.2 LRU法：H=

20、4/10=0.4 OPT法：H=5/10=0.5 比較可知，LRU算法的命中率接近OPT算法，說(shuō)明算法較好。,2。堆棧型替換算法,定義：對(duì)任意一個(gè)程序的頁(yè)地址流作兩次主存頁(yè)面數(shù)分配，分別分配m個(gè)主存頁(yè)面和n個(gè)主存頁(yè)面，并且有mn。如果在任何時(shí)刻t，主存頁(yè)面數(shù)集合都滿足關(guān)系： 則這類算法稱為堆棧型替換算法 特點(diǎn)：隨著分配給程序的主存頁(yè)面數(shù)增加，主存的命中率也提高，至少不下降 LFU、LRU、OPT算法都是堆棧型算法 FIFO算法不是堆棧型算法,例3.2 設(shè)某一道程序有15個(gè)虛頁(yè)，程序執(zhí)行時(shí)的訪存的頁(yè)地址流為：1，2，3，4，1，2，5，1，2，3，4，5。求出分配給該程序的主存頁(yè)面數(shù)分別為3頁(yè)和

21、4頁(yè)時(shí)的使用和替換過(guò)程，請(qǐng)分別采用FIFO、LRU、OPT算法進(jìn)行對(duì)比說(shuō)明。,例4.3 FIFO、LFU、OPT算法比較,程序執(zhí)行的頁(yè)地址流： P1-P2-P1-P5-P4-P1-P3-P4-P2-P4 主存頁(yè)面數(shù)為3 LFU算法的命中率接近OPT算法，說(shuō)明算法較好,例4.3 FIFO、LFU、OPT算法比較,程序執(zhí)行的頁(yè)地址流： P1-P2-P1-P5-P4-P1-P3-P4-P2-P4 主存頁(yè)面數(shù)為3 LFU算法的命中率接近OPT算法，說(shuō)明算法較好,解：分別采用FIFO、LRU、OPT算法對(duì)主存3頁(yè)的使用和替換過(guò)程如圖3-13所示。將主存頁(yè)面數(shù)由3頁(yè)改為4頁(yè)，仍然采用3種算法分別對(duì)主存4頁(yè)

22、使用和替換，如圖3-14所示。比較二圖，可知隨著主存頁(yè)數(shù)由3頁(yè)增加到4頁(yè)，LRU、OPT算法的命中率增加了，而FIFO算法的命中率不增加反而減少了?？梢?jiàn)LRU、OPT替換算法屬于堆棧型替換算法，而FIFO算法不是堆棧型替換算法。,3.2.4 提高主存命中率的方法,為何要提高主存命中率？ 對(duì)公式 T=HT1+(1-H)T2 分析，必須提高H 影響主存命中率的主要因素 程序執(zhí)行中的頁(yè)地址流分布 所采用的頁(yè)面替換算法 頁(yè)面大小 主存容量 所采用的頁(yè)面調(diào)度方法,（1）頁(yè)面大小的選擇 頁(yè)面大小Sp與主存容量S、命中率H的關(guān)系曲線。 主存大，命中率高 頁(yè)面大小應(yīng)適當(dāng),H 1,2S,S,Sp,（2）主存容量

23、 主存容量S增加到一定程度，命中率H提高變緩。,H 1,S,（3）頁(yè)面調(diào)度方式 分頁(yè)式： 整個(gè)程序鏈接裝入主存后才運(yùn)行，命中率100%，但主存利用率低，程序長(zhǎng)度必須小于主存安排空間 請(qǐng)求頁(yè)式： 發(fā)生頁(yè)面失效時(shí)，才進(jìn)行頁(yè)面調(diào)換 預(yù)取式調(diào)度 預(yù)先調(diào)入相關(guān)頁(yè)面，防止程序掛起后重新運(yùn)行時(shí)頻繁調(diào)入頁(yè)面,一種動(dòng)態(tài)頁(yè)面調(diào)度方法：頁(yè)面失效頻率法PFF(Page Fault Frequency)： 動(dòng)態(tài)給每個(gè)程序分配主存頁(yè)面數(shù)。命中率低于某個(gè)限定值，則增加分配頁(yè)面數(shù)，否則減少分配的主存頁(yè)面數(shù)。使命中率和主存利用率都能提高。,3.3 高速緩沖存儲(chǔ)器Cache,問(wèn)題的提出： CPU與主存速度相差100倍左右 采用的

24、解決辦法 CPU中設(shè)計(jì)寄存器堆，緩解訪存壓力 先行緩沖存儲(chǔ)器，速度差縮小30倍 采用Cache存儲(chǔ)系統(tǒng),Cache與虛存的比較,3.3 高速緩沖存儲(chǔ)器Cache,3.3.1 基本工作原理,3.3.2 Cache的一致性及性能分析,3.3.3 11種先進(jìn)的Cache性能優(yōu)化方法,3.3.1 基本工作原理,主存與Cache之間以塊為單位進(jìn)行數(shù)據(jù)交換 主存地址： Cache地址：,地址變換過(guò)程,Bb,命中？,CPU,訪存,調(diào)入Cache,替換,Cache,Cache滿？,Y,N,Y,N,1。 地址映象與變換方法,地址映像：把主存地址空間映像到Cache地址空間，即建立主存地址與Cache地址的對(duì)應(yīng)關(guān)

25、系，以便程序裝入Cache 地址變換：程序裝入Cache后，運(yùn)行中如何將主存地址變換成Cache地址 （1）全相連映象及其變換 （2）直接映象及其變換 （3）組相連映象及其變換 （4）位選擇組相連映象及其變換（略） （5）段相連映象及其變換（略）,（1）全相連映象及其變換,任意B可映象到任意b，映象關(guān)系共有CbMb種。,查目錄表： 命中，以b訪問(wèn)Cache；未命中，以主存地址訪存，備份裝入Cache,全相聯(lián)地址變換,塊號(hào)B,塊內(nèi)地址W,目錄表（由相聯(lián)存儲(chǔ)器構(gòu)成，共Cb個(gè)字）,主存地址,塊號(hào)b,相聯(lián)比較,Cache地址,塊內(nèi)地址w,查到相等 的塊號(hào),有效位 為1表示 映像有效,全相聯(lián)映象及其變換

26、 優(yōu)點(diǎn)：塊沖突率最小 缺點(diǎn)：相聯(lián)比較費(fèi)時(shí) （為虛存采用）,（2）直接映象及其變換,直接映象： 主存中1塊只映象到Cache的特定塊中 b=B mod Cb Mb應(yīng)是Cb的整數(shù)倍。 主存分區(qū)：Me=Cb，分區(qū)中的塊號(hào)Be與Cache中的塊號(hào)b相同 主存地址： Cache地址：,直接相聯(lián)映象方式,區(qū)0,區(qū)1,區(qū)Me-1,直接相聯(lián)地址變換,塊號(hào)B,塊內(nèi)地址W,區(qū)表存儲(chǔ)器（共Cb個(gè)字）,主存地址,塊號(hào)b,相等,Cache地址,塊內(nèi)地址w,區(qū)號(hào)E,相等比較,塊失效,訪問(wèn)Cache,若相等且有效位為1，即 命中，以Cache地址訪問(wèn)Cache；讀出數(shù)據(jù)送往CPU。,以塊號(hào)B訪問(wèn)區(qū)表，讀出區(qū)號(hào)進(jìn)行比較,不等

27、,（3）組相聯(lián)映象及其變換,組相聯(lián)映象：主存、Cache分組，每組塊數(shù)同。 主存組對(duì)Cache組直接映像，組內(nèi)全相聯(lián)映像 地址變換過(guò)程： 主存地址： Cache地址：,組相聯(lián)映像方式地址變換,組內(nèi)塊號(hào)B,塊內(nèi)地址W,塊表,主存地址,組內(nèi)塊號(hào)b,相等,Cache地址,塊內(nèi)地址w,組號(hào)G,相聯(lián)比較,塊失效,若相等即 命中，以g,b,w組成Cache地址訪問(wèn)Cache；讀出數(shù)據(jù)送往CPU。,以組號(hào)B訪問(wèn)塊表，讀出一組字與E,B進(jìn)行比較,不等,區(qū)號(hào)E,組號(hào)g,加快訪問(wèn)的方法： Cache地址變換與訪Cache并行 多塊同時(shí)比較 優(yōu)缺點(diǎn)介于直接映象和全相聯(lián)映像之間 當(dāng)每組塊容量Gb為1時(shí)，成直接映像方式

28、 當(dāng)每組塊容量Gb與Cache的塊容量Cb相等時(shí)，成全相聯(lián)映像方式。 一般， Gb越大，塊的沖突概率和塊失效率越低，但組內(nèi)映像關(guān)系就越復(fù)雜，實(shí)現(xiàn)成本越高。應(yīng)注意合理分配組的塊容量,2。 Cache替換算法,直接映像方式實(shí)際上不需替換算法 全相聯(lián)映像替換算法最復(fù)雜 在組相聯(lián)和位選擇組相聯(lián)映象及地址變換方式中要考慮替換算法 Cache替換算法用硬件實(shí)現(xiàn)。 兩種基于LRU算法的全硬實(shí)現(xiàn)方法： （1）比較對(duì)法 （2）堆棧法,比較對(duì)法,LRU算法實(shí)際上要把同一組內(nèi)的各個(gè)塊按照被訪問(wèn)過(guò)的時(shí)間順序排序，從而找出最久沒(méi)有被訪問(wèn)的塊。一個(gè)兩態(tài)的器件（如RS觸發(fā)器）能夠記錄上兩塊之間的先后順序，多個(gè)塊之間的先后順

29、序可用多個(gè)兩態(tài)器件的組合來(lái)實(shí)現(xiàn)。 以三個(gè)塊 (分別命名為A、B、C塊)為例。設(shè)TAB表示B塊比A塊更久沒(méi)有被使用過(guò)，其它類似。則A、B、C三塊共有6種排列：,比較對(duì)法,如果訪問(wèn)過(guò)的次序?yàn)锳 B C，A為最近訪問(wèn)過(guò)的塊，C為最久未被訪問(wèn)過(guò)的塊，則此時(shí)必有TAB=1, TAC=1, TBC=1。 因此以最久未被訪問(wèn)過(guò)的塊C作為被替換掉的塊的話，用布爾代數(shù)式必有 同理，,當(dāng)每組的塊數(shù)達(dá)到8個(gè)時(shí)，需要的觸發(fā)器個(gè)數(shù)為28個(gè)，與門的輸入端個(gè)數(shù)為7，硬件成本增大，可采用分級(jí)辦法解決，但同時(shí)要考慮分級(jí)帶來(lái)的遲延。 比較法的特點(diǎn)是 用LRU法塊失效率比較低； 全硬件工作速度比較高； 當(dāng)每組塊數(shù)較多時(shí)，硬件實(shí)現(xiàn)相

30、對(duì)復(fù)雜，需要很多的觸發(fā)器。,堆棧法,堆棧法用棧頂至棧底的先后次序來(lái)記錄Cache同一組內(nèi)的各個(gè)塊被訪問(wèn)的先后順序。棧頂是最近訪問(wèn)過(guò)的，棧底是最久沒(méi)有被訪問(wèn)過(guò)的。替換時(shí)，從棧頂壓入新的塊，而棧底的塊自然就被擠出。該方法有自己的管理規(guī)則，并不與FIFO法相同。,堆棧法管理規(guī)則 把本次訪問(wèn)的塊號(hào)與堆棧中保存的所有塊號(hào)進(jìn)行相聯(lián)比較，如發(fā)現(xiàn)有相等的，則表示命中。其壓入方式如圖3-25所示，并非壓到棧底。 如果相聯(lián)比較沒(méi)有發(fā)現(xiàn)相等，則Cache塊失效。這時(shí)，從棧頂壓入將棧底擠出。 這樣，棧底永遠(yuǎn)保存著最久沒(méi)有被訪問(wèn)過(guò)的塊號(hào)，也即下次要被替換的塊號(hào)。 堆棧法的特點(diǎn)是 用LRU法命中率較高； 硬件實(shí)現(xiàn)相對(duì)簡(jiǎn)單

31、； 由于逐級(jí)下壓，速度相對(duì)較慢。,3.3.2 Cache的一致性及性能分析,1。Cache的一致性 2。Cache的取算法 3。Cache的性能分析,1。Cache的一致性,問(wèn)題的提出 對(duì)Cache塊的修改，未及時(shí)更新相應(yīng)主存塊 解決辦法：選擇合適的Cache更新算法 （1）寫回法（write back） 指寫Cache時(shí)不寫主存，而當(dāng)Cache數(shù)據(jù)被替換出去時(shí)，才寫回主存。采用寫回法，Cache塊表中一般要設(shè)一個(gè)“修改位”。一旦塊被修改，該塊的修改位就被置1，否則保持為0。這樣替換該塊時(shí)，若修改位是1，則必須把該塊寫回主存，并更新主存中的原塊。若修改位是0，則不必寫回，直接調(diào)入新塊。,（2）

32、寫直達(dá)法（write through） 即寫操作時(shí)將數(shù)據(jù)既寫入Cache同時(shí)又寫入主存。 寫回法若不發(fā)生塊失效，速度比寫直達(dá)法要快；CPU對(duì)Cache中的一個(gè)數(shù)據(jù)塊的多次寫操作只需一次寫入主存，減少了主存的寫操作次數(shù)。但Cache中的數(shù)據(jù)在未替換時(shí)，可能與主存中的相應(yīng)數(shù)據(jù)不一致，可靠性不如寫直達(dá)法。同時(shí)，CPU如果讀Cache發(fā)生塊失效的話，將引起數(shù)據(jù)塊的寫回操作。 采用寫直達(dá)法，Cache塊表中無(wú)需設(shè)“修改位”，塊替換時(shí)，無(wú)需把被替換塊寫回主存，因此寫直達(dá)法比寫回法簡(jiǎn)單，控制容易；但是寫直達(dá)法的硬件代價(jià)高，因?yàn)闉榱斯?jié)省同時(shí)寫主存的時(shí)間，通常要增設(shè)一個(gè)高速小容量的緩沖存儲(chǔ)器來(lái)暫存寫主存的數(shù)據(jù)和

33、地址。,當(dāng)出現(xiàn)寫Cache不命中時(shí)，是否要把包括所寫字在內(nèi)的一個(gè)塊從主存讀入Cache問(wèn)題，有按寫分配法和不按寫分配法等兩種處理方法。 按寫分配法是指發(fā)生寫Cache不命中時(shí)，先把所要寫的字寫入主存，再把包括所寫字在內(nèi)的一個(gè)塊從主存讀入Cache，此法可以提高Cache的命中率。 不按寫分配法則在寫Cache不命中時(shí)，只把所要寫的字寫入主存，而不把包括所寫字在內(nèi)的一個(gè)塊讀入Cache，此法可簡(jiǎn)化Cache結(jié)構(gòu)，省掉了將數(shù)據(jù)塊讀入Cache的操作。 一般在寫回法中采用按寫分配法，在寫直達(dá)法中為了減少同時(shí)寫主存的開(kāi)銷而采用不按寫分配法。,采用寫直達(dá)法還是寫回法與系統(tǒng)應(yīng)用有關(guān)。 單處理機(jī)系統(tǒng)多數(shù)采用

34、寫回法以節(jié)省成本， 共享主存的多處理機(jī)系統(tǒng)為保證各處理機(jī)經(jīng)主存交換信息時(shí)不出錯(cuò)，多采用寫直達(dá)法。,2。Cache的取算法,基本的Cache取算法是按需取。即在訪問(wèn)Cache不命中時(shí)，根據(jù)訪問(wèn)的局部性原理，把包括所訪問(wèn)的字在內(nèi)的一個(gè)塊從主存讀入Cache。如果進(jìn)一步采用某種預(yù)取算法就能較大地提高Cache命中率。具體算法有2種。 （1）恒預(yù)取。當(dāng)CPU訪問(wèn)Cache時(shí)，無(wú)論是否命中，都把緊接著訪問(wèn)字所在塊的下一塊從主存讀入Cache。 （2）不命中預(yù)取。僅僅在Cache不命中時(shí)，才把訪問(wèn)字所在塊及其鄰接的下一塊從主存讀入Cache。,影響預(yù)取法效果的因素： （1）塊的大小。每塊的字節(jié)數(shù)最好不超過(guò)

35、256。 （2）預(yù)取開(kāi)銷。要預(yù)取就要有訪主存開(kāi)銷和將它取進(jìn)Cache的訪Cache開(kāi)銷，還要加上把被替換塊寫回主存的開(kāi)銷。 模擬結(jié)果表明，恒預(yù)取法使不命中率降低75%80%，而不命中預(yù)取法使不命中率降低30%40%。但前者所引起的Cache、主存間傳輸量的增加要比后者大得多。,3. Cache系統(tǒng)的性能分析,（1）Cache系統(tǒng)的加速比 設(shè) Cache的等效訪問(wèn)周期T， Cache訪問(wèn)周期Tc，主存訪問(wèn)周期Tm T=HTc+(1-H)Tm Cache系統(tǒng)的加速比 Sp=Tm/T =1/(1-H)+HTc/Tm)=f(H,Tm/Tc) 對(duì)Sp的分析：Tm、Tc由器件決定，最有效的途徑是提高H,一

36、般H0.9，達(dá)0.99以上，Sp接近Tm/Tc,Cache的加速比Sp與命中率H的關(guān)系,影響Cache命中率的因素分析,影響Cache命中率的因素 程序執(zhí)行過(guò)程中的地址流分布 替換算法 Cache容量 組相聯(lián)映象方式中塊的大小和分組數(shù)目 Cache預(yù)取算法,1）Cache命中率與容量的關(guān)系,關(guān)系曲線近似為H=1-S-0.5 S達(dá)到一定程度后，H提高很少,Cache命中率H與容量S的關(guān)系,2） Cache命中率與塊大小的關(guān)系,存在最佳塊大小，H達(dá)到最大,初始,最佳,3）Cache命中率與組數(shù)的關(guān)系 組數(shù)增加（512），H降低明顯,3.3.3 11種先進(jìn)的Cache性能優(yōu)化方法,可從三個(gè)方面來(lái)優(yōu)化

37、Cache性能，即減少命中時(shí)的訪問(wèn)時(shí)間（簡(jiǎn)稱命中時(shí)間）、降低缺失率（不命中率）和減小缺失代價(jià)（即不命中時(shí)付出的開(kāi)銷），總結(jié)了11種先進(jìn)的Cache性能優(yōu)化方法,1小而簡(jiǎn)單的Cache減少命中時(shí)間 現(xiàn)代計(jì)算機(jī)中，一級(jí)Cache應(yīng)盡可能小，這樣塊表小，查表速度快；同時(shí)也應(yīng)使二級(jí)Cache盡可能小，使之能與CPU處于同一芯片內(nèi)，避免片外時(shí)間代價(jià)。在快速時(shí)鐘頻率下，通過(guò)動(dòng)態(tài)執(zhí)行隱藏一級(jí)Cache缺失和使用二級(jí)Cache來(lái)避免直接訪問(wèn)主存。 2路預(yù)測(cè)(way predicting)減少命中時(shí)間 路預(yù)測(cè)要求Cache塊中預(yù)留一個(gè)塊預(yù)測(cè)位，用來(lái)預(yù)測(cè)下一次訪問(wèn)Cache時(shí)可能用到的方式或塊，以便提前使用多路選

38、擇器來(lái)選擇所需的塊。若預(yù)測(cè)正確，則有最快的命中時(shí)間，若失敗，將選擇其它的塊。模擬表明對(duì)于2路組相聯(lián)來(lái)說(shuō)，組預(yù)測(cè)的精度有85%。Pentium 4使用了路預(yù)測(cè)技術(shù)。,3蹤跡Cache（trace cache）減少命中時(shí)間 在指令級(jí)并行的情況下，蹤跡Cache的應(yīng)用為轉(zhuǎn)移預(yù)測(cè)提供了方便。蹤跡Cache更好地利用了指令Cache中的長(zhǎng)塊，在它的塊中包含了對(duì)已執(zhí)行指令的動(dòng)態(tài)跟蹤信息，而不是在存儲(chǔ)器中的靜態(tài)指令序列。Pentium 4采用了蹤跡Cache，并使用譯碼微操作，節(jié)省了譯碼時(shí)間。但是蹤跡Cache成本較高，硬件復(fù)雜，其它處理器幾乎沒(méi)有用到它。 4流水線Cache訪問(wèn) 此方法將流水線、Cache

39、訪問(wèn)、使一級(jí)Cache命中時(shí)的有效時(shí)延分散到幾個(gè)時(shí)鐘周期。它提供了較短的周期和高帶寬，但是命中時(shí)間長(zhǎng)。若流水線產(chǎn)生阻塞，可能有更多的時(shí)鐘周期代價(jià)。,5利用非阻塞Cache（lockup-free cache）增加Cache帶寬 對(duì)于允許亂序執(zhí)行的流水線機(jī)器（見(jiàn)第5章）來(lái)說(shuō)，處理器是不需用在Cache缺失時(shí)停頓的。比如處理器在等待數(shù)據(jù)Cache返回?cái)?shù)據(jù)的同時(shí)，可以繼續(xù)從指令Cache中取指令。非阻塞Cache在缺失時(shí)繼續(xù)保持Cache命中，減少了缺失代價(jià)。如果Cache能重疊多個(gè)缺失，則會(huì)進(jìn)一步降低缺失代價(jià)，實(shí)現(xiàn)“多重缺失仍命中”或“缺失時(shí)仍缺失”。通常，亂序執(zhí)行的處理器若能在二級(jí)Cache中命

40、中，則能隱藏一級(jí)Cache所產(chǎn)生的缺失代價(jià)。 6利用多組Cache增加Cache帶寬 此法類似對(duì)存儲(chǔ)器的并行存取，將Cache分為若干個(gè)獨(dú)立的存儲(chǔ)體以支持并發(fā)訪問(wèn)，增加Cache帶寬。如AMD Opteron的二級(jí)Cache有2個(gè)存儲(chǔ)體，Sun的Niagara有4個(gè)存儲(chǔ)體。,7關(guān)鍵字優(yōu)先和提前重啟動(dòng)以減小缺失代價(jià) 此技術(shù)來(lái)源于經(jīng)驗(yàn)數(shù)據(jù)：處理器在同一時(shí)刻只需要塊中的一個(gè)字，因此不必等到全部塊裝入就將所需字送出，然后重新啟動(dòng)處理器訪問(wèn)。具體有兩種策略： （1）關(guān)鍵字優(yōu)先。首先向主存請(qǐng)求缺失的字，一旦它到達(dá)即送處理器，使得處理器在裝入其它字的同時(shí)能夠繼續(xù)執(zhí)行。 （2）提前重啟動(dòng)。以正常順序獲取字，塊

41、中所需字一旦到達(dá)即送處理器，使得處理器在裝入其它字的同時(shí)能夠繼續(xù)執(zhí)行。 一般上述技術(shù)只適用于較大Cache塊的情況。因?yàn)樵谔畛涫Ｓ鄩K的時(shí)候，Cache還會(huì)繼續(xù)支持其它塊的訪問(wèn)。,8合并寫緩沖區(qū)（merging write buffers）以降低缺失代價(jià) 采用寫直達(dá)法的Cache要有一個(gè)寫緩沖區(qū)，寫回法Cache在替換塊時(shí)也要用到一個(gè)簡(jiǎn)單的寫緩沖區(qū)。如果寫緩沖區(qū)為空，可將被替換掉的數(shù)據(jù)和地址放到寫緩沖區(qū)中，寫操作即結(jié)束，寫緩沖區(qū)準(zhǔn)備將數(shù)據(jù)寫回存儲(chǔ)器時(shí)，處理器可繼續(xù)工作。如果寫緩沖區(qū)里還有其它修改過(guò)的數(shù)據(jù)，應(yīng)檢查新數(shù)據(jù)的地址是否與寫緩沖區(qū)中的某一合法項(xiàng)數(shù)據(jù)地址相匹配。若匹配，新數(shù)據(jù)就合并到該項(xiàng)中，

42、這就是寫合并。此法可一次寫多個(gè)字，并減少了因?qū)懢彌_區(qū)已滿而產(chǎn)生的訪Cache停頓。,9編譯器優(yōu)化以降低缺失率 此法試圖采用軟件方法來(lái)優(yōu)化Cache性能。在編譯器中設(shè)法在不影響程序正確性的前提下進(jìn)行程序代碼和數(shù)據(jù)重組，以改善空間局部性。 10指令和數(shù)據(jù)硬件預(yù)取以降低缺失代價(jià)或缺失率 將Cache的預(yù)取算法發(fā)展到多個(gè)流緩沖區(qū)中。例如Pentium 4能從8個(gè)分別來(lái)自不同的4KB頁(yè)面的流中，預(yù)取數(shù)據(jù)到二級(jí)Cache。,11編譯控制預(yù)取降低缺失代價(jià)或缺失率 此法利用編譯器來(lái)插入預(yù)取指令，提前發(fā)出數(shù)據(jù)請(qǐng)求。有寄存器預(yù)?。ò褦?shù)據(jù)與渠道寄存器中）和Cache預(yù)取（只把數(shù)據(jù)預(yù)取到Cache中）兩種方式。目前大

43、多數(shù)處理器采用非故障性Cache預(yù)取技術(shù)。當(dāng)然編譯控制預(yù)取的目的是使指令執(zhí)行和預(yù)取數(shù)據(jù)能夠重疊進(jìn)行，循環(huán)程序就很適宜預(yù)取優(yōu)化。 然而生成預(yù)取指令會(huì)帶來(lái)指令的開(kāi)銷，因此應(yīng)謹(jǐn)慎使用以保證開(kāi)銷在可接受的范圍內(nèi)。,Cache-主存-磁盤三級(jí)存儲(chǔ)系統(tǒng) 組織方式 1）兩個(gè)存儲(chǔ)系統(tǒng)組織方式 Cache-主存存儲(chǔ)系統(tǒng)和主存-磁盤存儲(chǔ)系統(tǒng),CPU,MMU,Cache,主存儲(chǔ)器,數(shù)據(jù)或指令,數(shù)據(jù)或指令,虛擬地址,物理地址,物理地址,存儲(chǔ)管理部件，能將虛擬地址變換為主存物理地址,若未命中Cache，則訪問(wèn)主存,塊替換,3.4 三級(jí)存儲(chǔ)系統(tǒng),2）一個(gè)存儲(chǔ)系統(tǒng)組織方式 Cache-主存-磁盤存儲(chǔ)系統(tǒng),CPU,MMU,C

44、ache,主存儲(chǔ)器,3）全Cache系統(tǒng) Cache-磁盤存儲(chǔ)系統(tǒng) （無(wú)主存儲(chǔ)器） 在嵌入式系統(tǒng)中較多應(yīng)用。,3.5 并行存儲(chǔ)器,3.5.1 存儲(chǔ)器的頻帶平衡,3.5.2 并行存儲(chǔ)器,3.5.1 存儲(chǔ)器的頻帶平衡,計(jì)算機(jī)運(yùn)行中至少有4種訪問(wèn)源，即訪存取指令、訪存取操作數(shù)、訪存寫結(jié)果，I/O設(shè)備也要與主存交換數(shù)據(jù)。 如何讓存儲(chǔ)器訪問(wèn)速度跟得上系統(tǒng)的需要，一直是設(shè)計(jì)者關(guān)注的問(wèn)題。現(xiàn)代計(jì)算機(jī)普遍采用指令并行技術(shù)，對(duì)存儲(chǔ)器的頻帶寬度提出了更高的要求。 存儲(chǔ)器的頻帶：訪問(wèn)源對(duì)存儲(chǔ)器訪問(wèn)的速度，用MW/S（百萬(wàn)字每秒）或MB/S （百萬(wàn)字節(jié)每秒）表示 存儲(chǔ)器頻帶寬度的計(jì)算：各訪問(wèn)源的頻帶之和 存儲(chǔ)器的頻帶

45、平衡：存儲(chǔ)器速度與系統(tǒng)需要相適應(yīng),3.5.1 存儲(chǔ)器的頻帶平衡,例如，設(shè)一臺(tái)計(jì)算機(jī)的執(zhí)行速度為200MIPs(2億指令/秒)，要求： CPU取指令速度為200MW/S（設(shè)每條指令的長(zhǎng)度為一個(gè)字)； CPU取/存操作數(shù)速度為400MW /S（平均每條指令訪問(wèn)周期2 個(gè)操作數(shù)）； 各種I/O設(shè)備訪問(wèn)存貯器速度為5MW /S； 可求得存貯器的總頻寬應(yīng)為605MW /S，即要求訪存周期T16.5ns。目前DRAM的訪存周期是達(dá)不到這一要求的。,解決存儲(chǔ)器頻帶平衡的三條途徑： 并行存儲(chǔ)器 緩沖存儲(chǔ)器 Cache存儲(chǔ)系統(tǒng),3.5.2 并行存儲(chǔ)器,并行存儲(chǔ)器：多個(gè)獨(dú)立的存儲(chǔ)器并行工作，同一存儲(chǔ)周期內(nèi)可訪問(wèn)多

46、個(gè)數(shù)據(jù)。 有三種并行存儲(chǔ)器： 1 單體多字并行存儲(chǔ)器 2 交叉訪問(wèn)存儲(chǔ)器 3 無(wú)沖突訪問(wèn)存儲(chǔ)器,1 單體多字并行存儲(chǔ)器,原理：增加存儲(chǔ)器字長(zhǎng)，實(shí)現(xiàn)同時(shí)讀寫多個(gè)字 原mw字 改為 m/n nw字 m：存儲(chǔ)單元數(shù)，w：字長(zhǎng) 訪問(wèn)方法：地址碼高位訪問(wèn)存儲(chǔ)單元，低位控制多路選擇器選擇其中數(shù)據(jù),一般存儲(chǔ)器訪問(wèn),設(shè)存儲(chǔ)器為1MB，每字8位 即220字8位 數(shù)據(jù)寄存器MBR為8位 地址寄存器MAR為20位,單體多字并行存儲(chǔ)器訪問(wèn),設(shè)存儲(chǔ)器為1MB， 每字64位 即 220/8字88位 = 217字64位 數(shù)據(jù)寄存器MBR 為8個(gè)字節(jié) 地址寄存器MAR 若仍為20位，則 MAR高17位選字 MAR低3位控制多

47、路選擇器8中選1,并行訪問(wèn)寄存器分析,主要優(yōu)點(diǎn)：簡(jiǎn)單容易 主要缺點(diǎn)：訪問(wèn)的沖突大 取指令沖突（例如轉(zhuǎn)移時(shí)同時(shí)讀出的指令，后面的指令將可能無(wú)用）：概率小 讀操作數(shù)沖突（同時(shí)讀出的數(shù)據(jù)不一定都有用）：概率大 寫數(shù)據(jù)沖突。（只寫1個(gè)或2個(gè)字節(jié)時(shí)需讀出再寫入，需專門控制） 讀寫沖突（讀寫同一個(gè)存儲(chǔ)字內(nèi)的內(nèi)容無(wú)法在同一周期內(nèi)完成，需專門控制） 原因：只有一套地址寄存器和控制邏輯,如果每個(gè)存儲(chǔ)體都有獨(dú)立的地址 寄存器和控制邏輯，即由多個(gè)存 儲(chǔ)體組成存儲(chǔ)器，顯然，沒(méi)有寫 數(shù)據(jù)沖突和讀寫沖突，其它沖突 也會(huì)緩解。這時(shí)，對(duì)存儲(chǔ)器的訪 問(wèn)通常采用交叉方式。,2 交叉訪問(wèn)存儲(chǔ)器,主存儲(chǔ)器由多個(gè)模塊構(gòu)成。 假設(shè)主存儲(chǔ)

48、器包含m=2a個(gè)存儲(chǔ)器模塊，每個(gè)模塊包含w=2b個(gè)存儲(chǔ)單元（字），則總存儲(chǔ)容量為 字地址位數(shù)為a+b,兩種組織方式 交叉訪問(wèn)的存儲(chǔ)器可以分為兩種： (1)高位交叉方式 (2)低位交叉方式,1）高位交叉訪問(wèn)存儲(chǔ)器 存儲(chǔ)器地址的高a位作為存儲(chǔ)器模塊地址，鄰接的存儲(chǔ)器單元被分配在同一個(gè)存儲(chǔ)器模塊中，在每個(gè)存儲(chǔ)器周期內(nèi)，只能對(duì)各模塊存取一個(gè)字。所以不支持鄰接單元的成塊存取。 高位n路交叉存取如下圖：,各個(gè)存儲(chǔ)模塊有獨(dú)立的控制部件，地址碼高位指示存儲(chǔ)體號(hào)，地址碼低位是各存儲(chǔ)體的體內(nèi)地址（高位譯碼選體） 設(shè)：m:存儲(chǔ)體容量 n: 存儲(chǔ)體個(gè)數(shù) j: 體內(nèi)地址 0m-1 k: 存儲(chǔ)體體號(hào) 0n-1 存儲(chǔ)單元地

49、址 A=mk+j 若已知A，則存儲(chǔ)體體內(nèi)地址： Aj=A mod m 存儲(chǔ)體體號(hào)： 對(duì)多任務(wù)多用戶，可提高訪問(wèn)速度，對(duì)單任務(wù)可擴(kuò)大容量,向下取整,2) 低位交叉訪問(wèn)存儲(chǔ)器 存儲(chǔ)器地址的低a位用來(lái)指明存儲(chǔ)器模塊，高b位是每個(gè)模塊內(nèi)的字地址。 低位n路交叉存取如下圖：,字地址譯碼器,各個(gè)存儲(chǔ)模塊有獨(dú)立的控制部件，地址碼低位指示存儲(chǔ)體號(hào)，地址碼高位是各存儲(chǔ)體的體內(nèi)地址（低位譯碼選體） 存儲(chǔ)單元地址：A=nj+k 存儲(chǔ)體體內(nèi)地址： 存儲(chǔ)體體號(hào)：Ak=A mod n,向下取整,如8路交叉，n=8，m=8，a=b=3， 8路低位交叉存取如下圖：,分時(shí)啟動(dòng)，啟動(dòng)間隔 Tm：存儲(chǔ)體訪問(wèn)周期 低位交叉以流水線方

50、式支持成塊存取,低位交叉流水線方式示意圖：,時(shí)間,Tm為主周期，t= Tm/n為小周期，n為交叉存取度,低位交叉訪問(wèn)有可能將速度提高n倍，實(shí)際上低于n，因?yàn)榇嬖谠L問(wèn)沖突,低位交叉訪問(wèn)存儲(chǔ)器訪問(wèn)沖突分析,設(shè)每個(gè)存儲(chǔ)周期只能取到k個(gè)有效字（k=1n），p(k)是k的概率密度函數(shù)，N是k的平均值，又稱并行存儲(chǔ)器的加速比，g為程序的轉(zhuǎn)移概率，則：,討論： 1）g=0即不發(fā)生轉(zhuǎn)移，N=n 2) g=1即每條指令都是轉(zhuǎn)移指令且轉(zhuǎn)移成功，N=1,同單個(gè)存儲(chǔ)體 結(jié)論：必須把并行和交叉訪存與Cache存儲(chǔ)系統(tǒng)配合起來(lái)才能組成高速主存,3 無(wú)沖突訪問(wèn)存儲(chǔ)器（略）,產(chǎn)生沖突的原因：程序轉(zhuǎn)移和數(shù)據(jù)的隨機(jī)性 一種解決方

51、法：主存儲(chǔ)器的存儲(chǔ)體個(gè)數(shù)為質(zhì)數(shù),3.6 RAID系統(tǒng),在服務(wù)器中為了提高磁盤存儲(chǔ)器的容量和機(jī)器可靠性，通常采用磁盤陣列（Disk Array），或者稱為獨(dú)立冗余磁盤陣列（RAID，Redundant Array of Independent Disks）。 RAID系統(tǒng)采用多個(gè)低成本硬盤，以陣列形式排列，能夠提供一個(gè)獨(dú)立的大型存儲(chǔ)設(shè)備解決方案。它將數(shù)據(jù)分散展開(kāi)在多臺(tái)磁盤上進(jìn)行并行的讀寫操作，類似于存儲(chǔ)器中的寬字存儲(chǔ)器和多體交叉技術(shù)，提高了數(shù)據(jù)傳輸?shù)膸捄痛疟P操作的處理能力。 RAID系統(tǒng)具有容量大、數(shù)據(jù)傳輸率高、可靠性高、數(shù)據(jù)安全，易于磁盤管理等優(yōu)點(diǎn)。,3.6 RAID系統(tǒng),RAID的關(guān)鍵技術(shù)

52、是對(duì)多臺(tái)磁盤機(jī)進(jìn)行數(shù)據(jù)的同步控制，包括使用緩沖器使數(shù)據(jù)同步，采用冗余技術(shù)提高可靠性。 RAID技術(shù)經(jīng)過(guò)不斷的發(fā)展，現(xiàn)在已擁有了從 RAID 0 到 RAID 6七種基本的RAID級(jí)別。不同RAID 級(jí)別代表著不同的存儲(chǔ)性能、數(shù)據(jù)安全性和存儲(chǔ)成本。,（1）RAID 0：非冗余的磁盤陣列 RAID 0是把N塊同樣的硬盤用硬件的形式通過(guò)磁盤控制器或用操作系統(tǒng)中的磁盤驅(qū)動(dòng)程序以軟件的方式串聯(lián)在一起創(chuàng)建一個(gè)大的卷集。在使用中電腦數(shù)據(jù)依次寫入到各塊硬盤中，它的最大優(yōu)點(diǎn)就是可以整倍地提高硬盤的容量。此方式成本低、效率高。RAID 0沒(méi)有提供冗余或錯(cuò)誤修復(fù)能力，其最大的缺點(diǎn)在于任何一塊硬盤出現(xiàn)故障，整個(gè)系統(tǒng)將

53、會(huì)受到破壞，可靠性僅為單獨(dú)一塊硬盤的1/N。,（1）RAID 0：非冗余的磁盤陣列 RAID 0的另一種模式是在N塊硬盤上選擇合理的帶區(qū)來(lái)創(chuàng)建帶區(qū)集。其原理就是將原先順序?qū)懭氲臄?shù)據(jù)被分散到所有的N塊硬盤中同時(shí)進(jìn)行讀寫。N塊硬盤的并行操作使同一時(shí)間內(nèi)磁盤讀寫的速度提升了N倍。但是頻繁進(jìn)行讀寫操作時(shí)，很容易使控制器或總線的負(fù)荷超載。可增加磁盤控制器。最好每一塊硬盤都配備一個(gè)專門的磁盤控制器。 RAID 0一般用于要求容量大但對(duì)數(shù)據(jù)安全性要求不高的情況。,（2）RAID 1：鏡像磁盤冗余陣列 磁盤鏡像的原理是數(shù)據(jù)在寫入一塊磁盤的同時(shí)，會(huì)在另一塊配對(duì)的磁盤上生成鏡像文件。這種磁盤配對(duì)有主從式結(jié)構(gòu)，數(shù)據(jù)

54、優(yōu)先讀寫主盤，再讀寫備份盤；也有對(duì)等式結(jié)構(gòu)。這兩種方式都能使一個(gè)盤讀/寫時(shí)，另一個(gè)盤作校驗(yàn)工作。這就在不影響性能情況下，最大限度地保證系統(tǒng)的可靠性和可修復(fù)性。當(dāng)然，成本也會(huì)明顯增加，磁盤利用率為50%。另外，出現(xiàn)硬盤故障的RAID系統(tǒng)不再可靠，應(yīng)當(dāng)及時(shí)的更換損壞的硬盤，否則剩余的鏡像盤也出現(xiàn)問(wèn)題，那么整個(gè)系統(tǒng)就會(huì)崩潰。更換新盤后原有數(shù)據(jù)會(huì)需要很長(zhǎng)時(shí)間同步鏡像，外界對(duì)數(shù)據(jù)的訪問(wèn)不會(huì)受到影響，只是這時(shí)整個(gè)系統(tǒng)的性能有所下降。因此，RAID 1多用在保存關(guān)鍵性的重要數(shù)據(jù)的場(chǎng)合。,（3）RAID 2：采用海明碼糾錯(cuò)冗余的磁盤陣列 它將數(shù)據(jù)按位交叉，分別寫入不同的磁盤中，成倍提高了數(shù)據(jù)傳輸率。陣列中專門

55、設(shè)置了幾個(gè)磁盤存放海明碼糾錯(cuò)信息，訪問(wèn)時(shí)進(jìn)行按位的出錯(cuò)校驗(yàn)。它比鏡像磁盤陣列的冗余度小，但增加了海明碼的編碼和解碼開(kāi)銷，一般適合于大量順序數(shù)據(jù)訪問(wèn)。,（4）RAID 3：采用奇偶校驗(yàn)冗余的磁盤陣列 它也采用數(shù)據(jù)按位交叉，使用一個(gè)專門的磁盤用于存儲(chǔ)其他n個(gè)磁盤上對(duì)應(yīng)字節(jié)的異或（XOR），這個(gè)第n1個(gè)磁盤被稱為奇偶盤。如果任何一個(gè)磁盤發(fā)生了故障，可以通過(guò)對(duì)其他磁盤上的對(duì)應(yīng)位執(zhí)行異或來(lái)重構(gòu)故障磁盤的每一位。這種陣列冗余度小，特別是磁盤較多時(shí)。 RAID 3所存在的最大一個(gè)不足是校驗(yàn)盤很容易成為整個(gè)系統(tǒng)的瓶頸。對(duì)于那些經(jīng)常需要執(zhí)行大量寫入操作的應(yīng)用來(lái)說(shuō)，校驗(yàn)盤的負(fù)載將會(huì)很大。因此，RAID 3更適合于

56、那些寫操作較少、讀操作較多的應(yīng)用環(huán)境，例如數(shù)據(jù)庫(kù)和WEB服務(wù)器等。,（5）RAID 4：獨(dú)立傳送磁盤陣列 與RAID 3不同之處是它將數(shù)據(jù)按塊而不是按位交叉存儲(chǔ)在多個(gè)磁盤上，且校驗(yàn)數(shù)據(jù)以塊為單位存放在一個(gè)校驗(yàn)盤上。在數(shù)據(jù)不沖突時(shí)，多個(gè)磁盤可并行獨(dú)立讀/寫。和RAID 3一樣，校驗(yàn)盤為整個(gè)系統(tǒng)的瓶頸。而且對(duì)于只寫一個(gè)磁盤的少量數(shù)據(jù)訪問(wèn)操作，校驗(yàn)數(shù)據(jù)的計(jì)算需要根據(jù)原數(shù)據(jù)計(jì)算出差值，這需要對(duì)磁盤上的原數(shù)據(jù)進(jìn)行讀操作，再讀取校驗(yàn)盤上數(shù)據(jù)，然后將數(shù)據(jù)寫入數(shù)據(jù)盤，并計(jì)算出新的校驗(yàn)數(shù)據(jù)，最后寫入校驗(yàn)盤，需要4次訪問(wèn)磁盤的操作。因此雖然RAID 4適合于小塊數(shù)據(jù)的讀/寫，但用得較少。,（6）RAID 5：另一

57、種獨(dú)立傳送磁盤陣列 它與RAID 4一樣采用數(shù)據(jù)按塊交叉存儲(chǔ)，這種拆分方式對(duì)某些應(yīng)用來(lái)說(shuō)可能更加高效。例如，如果有很多并發(fā)執(zhí)行的事務(wù)，每個(gè)事務(wù)需要讀取數(shù)據(jù)的一段，則可以并行地滿足這些數(shù)據(jù)讀取請(qǐng)求。但與RAID 4不同的是，奇偶校驗(yàn)信息本身被拆分并依次存儲(chǔ)在每個(gè)盤上，避免了把所有奇偶信息存儲(chǔ)在一個(gè)獨(dú)立的奇偶盤上而導(dǎo)致的瓶頸。RAID 5的冗余度小，這種方式也適合于小塊數(shù)據(jù)的讀/寫，但對(duì)控制器要求較高。,（7）RAID 6：高效容錯(cuò)的磁盤陣列該陣列 采用兩級(jí)數(shù)據(jù)冗余和新的數(shù)據(jù)編碼以解決數(shù)據(jù)恢復(fù)問(wèn)題，其最大特點(diǎn)是能實(shí)現(xiàn)兩個(gè)磁盤容錯(cuò)，即有兩個(gè)磁盤出故障時(shí)仍能正常工作。在進(jìn)行寫操作時(shí)，RAID 6分別進(jìn)

58、行兩個(gè)獨(dú)立的校驗(yàn)核算，形成兩個(gè)獨(dú)立的冗余數(shù)據(jù)，寫入兩個(gè)磁盤。比如在Intel的80333IOP芯片中，有一種稱為P+Q的冗余技術(shù)，采用兩種不同分組大小的“Reed-Solomon”循環(huán)碼編碼，可以在兩個(gè)磁盤同時(shí)出故障時(shí)恢復(fù)數(shù)據(jù)。校驗(yàn)數(shù)據(jù)還可以采用二維的算法，將數(shù)據(jù)組織成矩陣格式后，分別按行按列計(jì)算，生成冗余數(shù)據(jù)。,另外，還有一些基本RAID級(jí)別的組合形式，如RAID 10、RAID 0+1、RAID 50等。 RAID 10是先組織成鏡像備份的RAID 1，再將兩個(gè)RAID 1組織成擴(kuò)展容量的RAID 0。RAID 0+1則先組織成RAID 0，再組成RAID 1。 RAID 0+1在具有RAID 0的高性能的同時(shí)也具有RAID 1的冗余和鏡像能力。RAID 10模式同RAID 0+1模式一樣具有良好的數(shù)據(jù)傳輸性能，但卻比RAID 0+1具有更高的可靠性。它們的磁盤利用率都為50，且至少由4個(gè)硬盤驅(qū)動(dòng)器構(gòu)成。,RAID系統(tǒng)中的關(guān)鍵部件是RAID控制器，它根據(jù)主機(jī)的訪問(wèn)要