1、3.23.13.43.33.63.53.73.23.13.43.33.63.53.7 第第3 3章章 存儲系統存儲系統3.23.13.43.33.63.53.73.23.13.43.33.63.53.73.23.13.43.33.63.53.73.23.13.43.33.63.53.7 一個存儲器的性能通常有三個主要參一個存儲器的性能通常有三個主要參數：容量、價格和速度。數：容量、價格和速度。 存儲器容量存儲器容量SM=Wlm。 其中，其中，W為存儲體的字長為存儲體的字長(單位為位或字節單位為位或字節)，l為每個存儲體的字數，為每個存儲體的字數，m為并行工作的存儲體個為并行工作的存儲體個數。數

2、。3.23.13.43.33.63.53.7 存儲器的速度存儲器的速度可以用訪問時間可以用訪問時間TA、存取周期、存取周期TM和和頻寬頻寬(也稱帶寬也稱帶寬)Bm來描述。來描述。 TA是存儲器從接到訪存讀是存儲器從接到訪存讀申請，到信息被讀到數據總線上所需的時間。這段時申請，到信息被讀到數據總線上所需的時間。這段時間是處理機在啟動訪存申請后必須等待的時間。間是處理機在啟動訪存申請后必須等待的時間。 TM則是連續啟動一個存儲體所需要的間隔時間，它則是連續啟動一個存儲體所需要的間隔時間，它一般總比一般總比TA大。大。3.23.13.43.33.63.53.7 存儲器頻寬存儲器頻寬是存儲器可提供的數

3、據傳送速率，是存儲器可提供的數據傳送速率，一般用每秒鐘傳送的信息位數一般用每秒鐘傳送的信息位數(或字節數或字節數)來衡來衡量，又分最大頻寬量，又分最大頻寬(或稱極限頻寬或稱極限頻寬)和實際頻寬。和實際頻寬。 最大頻寬最大頻寬Bm是存儲器連續訪問時能提供的頻是存儲器連續訪問時能提供的頻寬。單體的寬。單體的Bm=W/TM。m個存儲體并行工作時個存儲體并行工作時可達到的最大頻寬可達到的最大頻寬Bm=Wm/TM。由于存儲器不。由于存儲器不一定總能連續滿負荷地工作，所以，實際頻寬一定總能連續滿負荷地工作，所以，實際頻寬往往要低于最大頻寬。往往要低于最大頻寬。3.23.13.43.33.63.53.7 存

4、儲器的價格存儲器的價格可以用總價格可以用總價格C或每位價格或每位價格c來表示。具有來表示。具有SM位的存儲器每位價格位的存儲器每位價格c=C/SM。存儲器價格包含了存儲單元本身及為該存儲器存儲器價格包含了存儲單元本身及為該存儲器操作所必須的外圍電路的價格。操作所必須的外圍電路的價格。3.23.13.43.33.63.53.7 計算機系統總希望存儲器能在盡可能低的價格下，計算機系統總希望存儲器能在盡可能低的價格下，提供盡量高的速度和盡量大的存儲容量。在速度上應提供盡量高的速度和盡量大的存儲容量。在速度上應盡量和盡量和CPUCPU匹配，容量上應盡可能放得下所有系統軟匹配，容量上應盡可能放得下所有系

5、統軟件和多個用戶軟件及其運行時所需的空間。件和多個用戶軟件及其運行時所需的空間。 只用一種存儲器無法解決上述高速度、大容量、低只用一種存儲器無法解決上述高速度、大容量、低價格的要求。價格的要求。 有兩個途徑，有兩個途徑，一個是用多種類型的存儲器組成一個是用多種類型的存儲器組成具有具有一定層次的存儲系統一定層次的存儲系統，組合實現存儲器的大容量、高，組合實現存儲器的大容量、高速度和低價格要求，一個是發展速度和低價格要求，一個是發展并行存儲體系并行存儲體系，通過，通過并行訪存來提高存儲器的性能。并行訪存來提高存儲器的性能。 3.23.13.43.33.63.53.73.23.13.43.33.63

6、.53.7從外部看從外部看T,S,CM1(T1,S1,C1)M2(T2,S2,C2)Mn(Tn,Sn,Cn)3.23.13.43.33.63.53.73.23.13.43.33.63.53.72221221121221111CCSSCSSCSSSCSCC3.23.13.43.33.63.53.7),()1 (1)1 (12122111TTHfTTHHTHHTTTTe3.23.13.43.33.63.53.73.23.13.43.33.63.53.7CPU內部通用寄存器堆通用寄存器堆指令和數據緩沖棧指令和數據緩沖棧主存主存 脫機外存脫機外存Cache訪訪問問速速度度、每每位位價價格格存存儲儲容容

7、量量3.23.13.43.33.63.53.73.23.13.43.33.63.53.73.23.13.43.33.63.53.73.23.13.43.33.63.53.73.23.13.43.33.63.53.7實頁號實頁號p 頁內偏移頁內偏移d用戶號用戶號U 虛頁號虛頁號P 頁內偏移頁內偏移D3.23.13.43.33.63.53.7內部地址變換內部地址變換U、Pp外部地址變換（查外頁表）外部地址變換（查外頁表）U、P外存實地址外存實地址聯機外存地址聯機外存地址主存頁面表主存頁面表頁面替頁面替換算法換算法I/O通道通道啟動脫機外啟動脫機外存存 U P DAv多用戶虛地址多用戶虛地址命中命中

8、訪問主存訪問主存選主存頁選主存頁頁內頁內地址地址主存主存未未命命中中未命中未命中訪聯機外存訪聯機外存主存頁面失效，查內頁表主存頁面失效，查內頁表命中命中主存未主存未滿，有滿，有空頁號空頁號主存主存滿滿主存頁號主存頁號調入頁調入頁被替換頁被替換頁選頁選頁X用用戶戶頁頁Y用用戶戶頁頁:聯聯機機外外存存p d3.23.13.43.33.63.53.73.23.13.43.33.63.53.73.23.13.43.33.63.53.73.23.13.43.33.63.53.70段段1段段2段段3段段0123段號段號8K16K9K30K起始地址起始地址程序段通過段表與主存中的區域唯一對應程序段通過段表與

9、主存中的區域唯一對應如第如第i程序段對應段表中段號為程序段對應段表中段號為i的一行，由起始的一行，由起始地址和段長即可找到主存中對應的段。地址和段長即可找到主存中對應的段。1K500200200段長段長08K9K16K30K01K050002000200程序空間程序空間段表段表主存儲器主存儲器3.23.13.43.33.63.53.7虛地址虛地址U、S、D段表基址寄存器堆段表基址寄存器堆該用戶或作業的段表該用戶或作業的段表主存實地址主存實地址用戶號用戶號U段號段號S段內偏移段內偏移D段表長度段表長度 段表基地址段表基地址6As段名段名 起始地址起始地址 5 4裝入位裝入位 段長段長 訪問方式訪

10、問方式 2 1 0 3段表基址寄存器段表基址寄存器一個用戶（一道作業）的段表一個用戶（一道作業）的段表多用戶虛地址多用戶虛地址主存實地址主存實地址+U=6S=3As3.23.13.43.33.63.53.73.23.13.43.33.63.53.73.23.13.43.33.63.53.73.23.13.43.33.63.53.70頁頁1頁頁2頁頁3頁頁0123頁號頁號主存頁號主存頁號程序分頁程序分頁頁表映像頁表映像主存頁主存頁3.23.13.43.33.63.53.7虛地址虛地址U、P、D頁表基址寄存器堆頁表基址寄存器堆該該用戶或作業的頁表用戶或作業的頁表主存實地址主存實地址用戶號用戶號U虛

11、頁號虛頁號P頁內偏移頁內偏移DPa裝入位裝入位 修改位修改位 主存頁號主存頁號 各種標志各種標志 1 p頁表基址寄存器頁表基址寄存器頁表頁表多用戶多用戶虛地址虛地址Av實頁號實頁號p+Pa主存實地址主存實地址A頁內偏移頁內偏移d3.23.13.43.33.63.53.73.23.13.43.33.63.53.73.23.13.43.33.63.53.7頁表地址頁表地址程序分段、頁程序分段、頁查段表查段表查該段頁表查該段頁表主存頁主存頁段頁式虛存地址映像方法段頁式虛存地址映像方法0段段(12K)1段段(10K)2段段(5K)用戶程序用戶程序頁表地址頁表地址3320段段0頁頁0段段1頁頁0段段2頁

12、頁段表段表0段頁表段頁表1段段0頁頁1段段1頁頁1段段2頁頁1段頁表段頁表2段段0頁頁2段段1頁頁2段頁表段頁表主存主存3.23.13.43.33.63.53.7地址變換：地址變換：多用戶虛地址：用戶號多用戶虛地址：用戶號U，段號，段號S，虛，虛頁號頁號P，頁內偏移，頁內偏移D 段表基址寄存器段表基址寄存器該用戶或作業的段表該用戶或作業的段表該用戶或作業的頁表該用戶或作業的頁表主存實地址：實頁號主存實地址：實頁號p，頁內偏移，頁內偏移d3.23.13.43.33.63.53.7多用戶虛地址多用戶虛地址U、S、P、D段表基址寄存器段表基址寄存器該用戶或作業的段表該用戶或作業的段表相應的頁表相應的

13、頁表主存實地址主存實地址段頁式虛存地址變換過程段頁式虛存地址變換過程用戶號用戶號U段號段號S頁內偏移頁內偏移D段表基址寄存器段表基址寄存器多用戶頁表多用戶頁表多用戶虛地址多用戶虛地址+主存地址主存地址AAs虛頁號虛頁號PAs裝入位裝入位 修改位修改位 標志標志 頁表長頁表長 頁表地址頁表地址1 0 / 1 Ap多用戶段表多用戶段表頁內偏移頁內偏移d實頁號實頁號p裝入位裝入位 實頁號實頁號 修改位修改位 標志標志1 p 0 / 1 Ap3.23.13.43.33.63.53.73.23.13.43.33.63.53.73.23.13.43.33.63.53.7頁表基地頁表基地址寄存器址寄存器第第

14、1級頁表級頁表第第2級頁表級頁表3.23.13.43.33.63.53.7NvNpNpNvg2222loglogloglog32101032loglogloglog2222NvNpNpNvg3.23.13.43.33.63.53.73.23.13.43.33.63.53.7虛地址虛地址U、P拼接拼接目錄表目錄表實頁號實頁號主存實地址主存實地址采用目錄表的地址變換過程采用目錄表的地址變換過程用戶號用戶號U虛頁號虛頁號P頁內偏移頁內偏移D多用戶虛頁號（多用戶虛頁號（U,P拼接）修改位拼接）修改位 實頁號實頁號p 其它標志其它標志 U，P 0/1 p目錄表（按內容訪問的相聯存儲器）目錄表（按內容訪問

15、的相聯存儲器）多用戶多用戶虛地址虛地址Av實頁號實頁號p相聯訪問相聯訪問主存實地址主存實地址A頁內偏移頁內偏移d3.23.13.43.33.63.53.73.23.13.43.33.63.53.73.23.13.43.33.63.53.7 磁盤號磁盤號 柱面號柱面號 磁頭號磁頭號 塊號塊號3.23.13.43.33.63.53.7用戶號用戶號U外頁表始地址，虛頁號外頁表始地址，虛頁號P外頁表記錄（存儲字）外頁表記錄（存儲字）外部地址變換過程外部地址變換過程用戶號用戶號U虛頁號虛頁號P頁內偏移頁內偏移D外部地址變換外部地址變換（用軟件實現）（用軟件實現）裝入位裝入位 磁盤實地址磁盤實地址 1 外

16、頁表外頁表多用戶多用戶虛地址虛地址Av磁盤實地址磁盤實地址磁頭號磁頭號塊號塊號柱面號柱面號磁盤號磁盤號找到該用戶程序找到該用戶程序的外頁表首址的外頁表首址找到與該頁對找到與該頁對應的存儲字應的存儲字裝入位為裝入位為1可得磁盤實地址，裝入位為可得磁盤實地址，裝入位為0須將脫機外存調須將脫機外存調入入3.23.13.43.33.63.53.73.23.13.43.33.63.53.73.23.13.43.33.63.53.73.23.13.43.33.63.53.73.23.13.43.33.63.53.73.23.13.43.33.63.53.73.23.13.43.33.63.53.7)()(

17、nBmBtt3.23.13.43.33.63.53.73.23.13.43.33.63.53.73.23.13.43.33.63.53.73.23.13.43.33.63.53.7解：解：分別采用分別采用FIFO、LRU、OPT算法對主算法對主存存3頁的使用和替換過程如圖頁的使用和替換過程如圖3-13所示。將所示。將主存頁面數由主存頁面數由3頁改為頁改為4頁，仍然采用頁，仍然采用3種算種算法分別對主存法分別對主存4頁使用和替換，如圖頁使用和替換，如圖3-14所所示。比較二圖，可知隨著主存頁數由示。比較二圖，可知隨著主存頁數由3頁增頁增加到加到4頁，頁，LRU、OPT算法的命中率增加了，算法的命

18、中率增加了，而而FIFO算法的命中率不增加反而減少了。算法的命中率不增加反而減少了。可見可見LRU、OPT替換算法屬于堆棧型替換替換算法屬于堆棧型替換算法，而算法，而FIFO算法不是堆棧型替換算法。算法不是堆棧型替換算法。 3.23.13.43.33.63.53.73.23.13.43.33.63.53.7H12SSSp3.23.13.43.33.63.53.7H1S3.23.13.43.33.63.53.73.23.13.43.33.63.53.73.23.13.43.33.63.53.73.23.13.43.33.63.53.73.23.13.43.33.63.53.73.23.13.43

19、.33.63.53.7 塊號塊號B 塊內地址塊內地址W 塊號塊號b 塊內地址塊內地址w3.23.13.43.33.63.53.7Bb命中？命中？CPU訪存訪存調入調入Cache替換替換CacheCache滿？滿？YNYN3.23.13.43.33.63.53.73.23.13.43.33.63.53.7塊塊0塊塊1塊塊Cb-1Cache塊塊0塊1塊iMb-1主存儲器主存儲器3.23.13.43.33.63.53.7查目錄表：查目錄表： 命中，以命中，以b訪問訪問Cache；未命中，以主存地；未命中，以主存地址訪存，備份裝入址訪存，備份裝入Cache全相聯地址變換全相聯地址變換塊號塊號B塊內地址

20、塊內地址W 主存塊號主存塊號B Cache塊號塊號b 有效位有效位 B b 1目錄表（由相聯存儲器構成，共目錄表（由相聯存儲器構成，共Cb個字）個字）主存地址主存地址塊號塊號b相聯比較相聯比較Cache地址地址塊內地址塊內地址w查到相等查到相等的塊號的塊號有效位有效位為為1表示表示映像有效映像有效3.23.13.43.33.63.53.73.23.13.43.33.63.53.7 塊號塊號b 塊內地址塊內地址w 區號區號E 塊號塊號B 塊內地址塊內地址W3.23.13.43.33.63.53.7塊塊0塊塊1塊塊Cb-1Cache主存儲器主存儲器塊塊2Cb-1塊塊Mb-Cb塊塊Mb-Cb+1塊塊

21、Mb-1塊塊1塊塊Cb-1塊塊Cb塊塊Cb +1塊塊0區區0區區1區區Me-13.23.13.43.33.63.53.7直接相聯地址變換直接相聯地址變換塊號塊號B塊內地址塊內地址W有效位有效位 區號區號E（按地址訪問）（按地址訪問） E 1區表存儲器（共區表存儲器（共Cb個字）個字）主存地址主存地址塊號塊號b相等相等Cache地址地址塊內地址塊內地址w區號區號E相等比較相等比較塊失效塊失效訪問訪問Cache若相等且有效位為若相等且有效位為1，即即 命中，以命中，以Cache地地址訪問址訪問Cache；讀出；讀出數據送往數據送往CPU。以塊號以塊號B訪問區訪問區表，讀出區號進表，讀出區號進行比較

22、行比較 不等不等3.23.13.43.33.63.53.7區號區號E 組號組號G 塊號塊號B 塊內地址塊內地址W組號組號g 塊號塊號b 塊內地址塊內地址w3.23.13.43.33.63.53.7組相聯映像方式地址變換組相聯映像方式地址變換組內塊號組內塊號B塊內地址塊內地址W組內塊號組內塊號b 區號區號E，組內塊號，組內塊號B Gb個塊個塊 塊表塊表主存地址主存地址組內塊號組內塊號b相等相等Cache地址地址塊內地址塊內地址w組號組號G相聯比較相聯比較塊失效塊失效若相等即若相等即 命中，以命中，以g,b,w組成組成Cache地址地址訪問訪問Cache；讀出數；讀出數據送往據送往CPU。以組號以

23、組號B訪問塊訪問塊表，讀出一組字表，讀出一組字與與E,B進行比較進行比較不等不等區號區號E組號組號g3.23.13.43.33.63.53.73.23.13.43.33.63.53.73.23.13.43.33.63.53.7ACBCABACBCABTTTTTT,3.23.13.43.33.63.53.7BCACBCACABBCACABLRUTTTTTTTTCBCABLRUTTBACABLRUTTA3.23.13.43.33.63.53.70 1TAB0 1TAC0 1TBC&訪問訪問A訪問訪問B訪問訪問CALRU SBLRUCLRU S S R R R圖圖3-24 比較對法實現比較對

24、法實現LRU算法算法3.23.13.43.33.63.53.73.23.13.43.33.63.53.73.23.13.43.33.63.53.73.23.13.43.33.63.53.7圖圖3-25 用用堆棧法實現堆棧法實現LRU算法算法本次訪問的塊號本次訪問的塊號最近訪問過的塊號最近訪問過的塊號最久未被訪問的塊號最久未被訪問的塊號棧底棧底棧頂棧頂壓入到與本次訪問壓入到與本次訪問的塊號相等處的塊號相等處3.23.13.43.33.63.53.73.23.13.43.33.63.53.73.23.13.43.33.63.53.73.23.13.43.33.63.53.73.23.13.43.3

25、3.63.53.73.23.13.43.33.63.53.73.23.13.43.33.63.53.73.23.13.43.33.63.53.73.23.13.43.33.63.53.7 0.5 1 命中率命中率HSp期望值期望值86420Cache的加速比的加速比Sp與命中率與命中率H的關系的關系3.23.13.43.33.63.53.73.23.13.43.33.63.53.7 容量容量SCache命中率命中率H與容量與容量S的關系的關系命中率命中率H 13.23.13.43.33.63.53.7 塊大小塊大小命中率命中率H 1初始初始最佳最佳3.23.13.43.33.63.53.73.

26、23.13.43.33.63.53.73.23.13.43.33.63.53.73.23.13.43.33.63.53.73.23.13.43.33.63.53.73.23.13.43.33.63.53.73.23.13.43.33.63.53.73.23.13.43.33.63.53.73.23.13.43.33.63.53.73.23.13.43.33.63.53.7CPUMMUCache主存儲器主存儲器數據或指令數據或指令數據或指令數據或指令虛擬地址虛擬地址物理地址物理地址物理地址物理地址存儲管理部件，存儲管理部件，能將虛擬地址變能將虛擬地址變換為主存物理地換為主存物理地址址若未命中若未

27、命中Cache，則訪問主存則訪問主存塊替換塊替換3.23.13.43.33.63.53.7CPUMMUCache主存儲器主存儲器數據或指令數據或指令數據或指令數據或指令虛擬地址虛擬地址物理地址物理地址3.23.13.43.33.63.53.73.23.13.43.33.63.53.73.23.13.43.33.63.53.73.23.13.43.33.63.53.73.23.13.43.33.63.53.73.23.13.43.33.63.53.73.23.13.43.33.63.53.73.23.13.43.33.63.53.7數據寄存器數據寄存器MBR存儲體存儲體（m字字w位）位）地址寄存

28、器地址寄存器MAR一般存儲器一般存儲器3.23.13.43.33.63.53.7多路選擇器多路選擇器存儲體（存儲體（m/n字字nw位）位） MAR并行訪問存儲器并行訪問存儲器MBR 3.23.13.43.33.63.53.7如果每個存儲體都有獨立的地址如果每個存儲體都有獨立的地址寄存器和控制邏輯，即由多個存寄存器和控制邏輯，即由多個存儲體組成存儲器，顯然，沒有寫儲體組成存儲器，顯然，沒有寫數據沖突和讀寫沖突，其它沖突數據沖突和讀寫沖突，其它沖突也會緩解。這時，對存儲器的訪也會緩解。這時，對存儲器的訪問通常采用交叉方式。問通常采用交叉方式。 3.23.13.43.33.63.53.7個字bawm

29、23.23.13.43.33.63.53.73.23.13.43.33.63.53.73.23.13.43.33.63.53.7MAR01m-1MBRM0MARmm+12m-1MBRM1MAR(n-1)m(n-1)m+1nm-1MBRMn-1塊內字地塊內字地址譯碼器址譯碼器字字模塊模塊地址地址ab數據總線數據總線存儲器數據緩沖器存儲器數據緩沖器模塊地址緩沖器模塊地址緩沖器3.23.13.43.33.63.53.7 mAkA向下取整向下取整3.23.13.43.33.63.53.73.23.13.43.33.63.53.7字地址譯碼器MAR0nn(m-1)MBRM0MAR1n+1n(m-1)+1MBRM1MARn-12n-1nm-1MBRMn-1字字模塊模塊地址ab數據總線數據總線存儲器數據緩沖器模塊地址緩沖器3.23.13.43.33.63.53.7 nAjA 向下取整向下取整3.23.13.43.33.63.53.73.23.13.43.33.63.53.70856存儲器地址寄存器存儲器地址寄存器(6位位)M01957M121058M231159M341260M451361M56146