第4章__存儲(chǔ)體系

1、第第4 4章章 存儲(chǔ)體系存儲(chǔ)體系4.1 4.1 存儲(chǔ)體系概念與并行主存系統(tǒng)存儲(chǔ)體系概念與并行主存系統(tǒng)4.2 4.2 虛擬存儲(chǔ)器虛擬存儲(chǔ)器4.3 4.3 高速緩沖存儲(chǔ)器高速緩沖存儲(chǔ)器CacheCache本章重點(diǎn)：本章重點(diǎn)： 段頁(yè)式和頁(yè)式虛擬存儲(chǔ)器的原理；頁(yè)式虛擬存段頁(yè)式和頁(yè)式虛擬存儲(chǔ)器的原理；頁(yè)式虛擬存儲(chǔ)器的地址映像；儲(chǔ)器的地址映像；LRU/FIFO/OPTLRU/FIFO/OPT替換算法進(jìn)行頁(yè)替換算法進(jìn)行頁(yè)面替換的過(guò)程模擬；面替換的過(guò)程模擬；LRULRU算法對(duì)頁(yè)地址流的堆棧算法對(duì)頁(yè)地址流的堆棧處理模擬及性能分析；處理模擬及性能分析；CacheCache存儲(chǔ)器的直接和組存儲(chǔ)器的直接和組相聯(lián)地址映

2、像；相聯(lián)地址映像；LRULRU替換算法的硬件實(shí)現(xiàn)及替換替換算法的硬件實(shí)現(xiàn)及替換過(guò)程模擬；過(guò)程模擬；CacheCache存儲(chǔ)器的性能分析等。存儲(chǔ)器的性能分析等。本章難點(diǎn)：本章難點(diǎn)： 段頁(yè)式和頁(yè)式中虛實(shí)地址的計(jì)算；各種頁(yè)面替段頁(yè)式和頁(yè)式中虛實(shí)地址的計(jì)算；各種頁(yè)面替換算法的模擬和頁(yè)面命中率的計(jì)算；換算法的模擬和頁(yè)面命中率的計(jì)算；CacheCache組相組相聯(lián)映像和塊替換算法的模擬。聯(lián)映像和塊替換算法的模擬。4.1 4.1 存儲(chǔ)體系概念與并行主存系統(tǒng)存儲(chǔ)體系概念與并行主存系統(tǒng)4.1.1 4.1.1 發(fā)展存儲(chǔ)體系的必要性發(fā)展存儲(chǔ)體系的必要性 1.1.存儲(chǔ)器的性能要求存儲(chǔ)器的性能要求 1)1)大容量大容量

3、 2)2)高速度高速度 3)3)低價(jià)格低價(jià)格 2.2.容量容量 S SM M=W l m=W l m W W：存儲(chǔ)體的字長(zhǎng)，單位為：存儲(chǔ)體的字長(zhǎng)，單位為bitbit或或ByteByte。 l l：每個(gè)存儲(chǔ)體的字?jǐn)?shù)。：每個(gè)存儲(chǔ)體的字?jǐn)?shù)。 m m：并行工作的存儲(chǔ)體的個(gè)數(shù)：并行工作的存儲(chǔ)體的個(gè)數(shù)。 3.3.速度速度 從下面三個(gè)方面來(lái)描述從下面三個(gè)方面來(lái)描述： 1)1)訪問(wèn)時(shí)間訪問(wèn)時(shí)間T TA A T TA A是存儲(chǔ)器接到訪存到信息被讀到數(shù)據(jù)總線上是存儲(chǔ)器接到訪存到信息被讀到數(shù)據(jù)總線上 所需的時(shí)間。是確定所需的時(shí)間。是確定CPUCPU與存儲(chǔ)器時(shí)間關(guān)系的重與存儲(chǔ)器時(shí)間關(guān)系的重 要指標(biāo)。要指標(biāo)。 2)2)

4、存儲(chǔ)周期存儲(chǔ)周期T TM M T TM M是連續(xù)啟動(dòng)一個(gè)存儲(chǔ)體所需要的時(shí)間間隔。一般來(lái)說(shuō)是連續(xù)啟動(dòng)一個(gè)存儲(chǔ)體所需要的時(shí)間間隔。一般來(lái)說(shuō)總比總比T TA A大。大。 3)3)存儲(chǔ)器頻寬存儲(chǔ)器頻寬 是指存儲(chǔ)器可以提供的數(shù)據(jù)傳送率，一般用每秒鐘所傳是指存儲(chǔ)器可以提供的數(shù)據(jù)傳送率，一般用每秒鐘所傳送的信息位數(shù)來(lái)衡量。送的信息位數(shù)來(lái)衡量。 a)a)最大頻寬最大頻寬B BM M( (極限頻寬極限頻寬) ) 是存儲(chǔ)器連續(xù)訪問(wèn)時(shí)能提供的頻寬。是存儲(chǔ)器連續(xù)訪問(wèn)時(shí)能提供的頻寬。 單體：?jiǎn)误w： B BM M =W/T =W/TM M m m體并行工作：體并行工作：B BM M =mW/T =mW/TM M b)b)

5、實(shí)際頻寬實(shí)際頻寬 實(shí)際頻寬小于最大頻寬實(shí)際頻寬小于最大頻寬B BM M。 4.4.價(jià)格價(jià)格 可以用總價(jià)格可以用總價(jià)格C C或每位價(jià)格或每位價(jià)格c c來(lái)表示。具有來(lái)表示。具有S SM M 位的存儲(chǔ)器每位價(jià)格位的存儲(chǔ)器每位價(jià)格c=C/Sc=C/SM M。其中包括了存儲(chǔ)。其中包括了存儲(chǔ) 器本身的價(jià)格和為該存儲(chǔ)器操作所必須的外圍器本身的價(jià)格和為該存儲(chǔ)器操作所必須的外圍 電路的價(jià)格。電路的價(jià)格。5.5.結(jié)論結(jié)論 由于存儲(chǔ)器的價(jià)格、速度和容量的要求是矛盾由于存儲(chǔ)器的價(jià)格、速度和容量的要求是矛盾的，為了同時(shí)滿足三方面的要求，在一個(gè)完整的的，為了同時(shí)滿足三方面的要求，在一個(gè)完整的存儲(chǔ)體系中，必須采用不同工藝的

6、存儲(chǔ)器，使得存儲(chǔ)體系中，必須采用不同工藝的存儲(chǔ)器，使得信息以各種方式分布于不同的存儲(chǔ)體。信息以各種方式分布于不同的存儲(chǔ)體。 比如：比如： 主存主存 當(dāng)前活躍的信息，快，少當(dāng)前活躍的信息，快，少 輔存輔存 暫時(shí)不用的信息，慢，多暫時(shí)不用的信息，慢，多 虛存虛存 swapswap 從速度來(lái)說(shuō)，主存遠(yuǎn)遠(yuǎn)跟不上從速度來(lái)說(shuō)，主存遠(yuǎn)遠(yuǎn)跟不上CPUCPU的要求，為的要求，為 了彌補(bǔ)這一差距，特引入并行和重疊技術(shù)，構(gòu)了彌補(bǔ)這一差距，特引入并行和重疊技術(shù)，構(gòu) 成并行主存系統(tǒng)，但這種并行主存的方法提高成并行主存系統(tǒng)，但這種并行主存的方法提高 頻寬是有限的，因此還需從系統(tǒng)結(jié)構(gòu)入手，發(fā)頻寬是有限的，因此還需從系統(tǒng)結(jié)構(gòu)

7、入手，發(fā) 展存儲(chǔ)體系。展存儲(chǔ)體系。4.1.2 4.1.2 并行主存系統(tǒng)頻寬的分析并行主存系統(tǒng)頻寬的分析 1.1.類型類型 1)1)單體單字單體單字 存儲(chǔ)器字長(zhǎng)存儲(chǔ)器字長(zhǎng)W W與與CPUCPU字長(zhǎng)字長(zhǎng)W W 相同相同, ,一次訪問(wèn)一個(gè)存儲(chǔ)器一次訪問(wèn)一個(gè)存儲(chǔ)器 字字, ,主存最大頻寬主存最大頻寬B BM M =W/T =W/TM MW位讀出寄存器讀出寄存器地址寄存器單體單字存儲(chǔ)器單體單字存儲(chǔ)器l 2) 2)單體多字單體多字 存儲(chǔ)器字長(zhǎng)等于存儲(chǔ)器字長(zhǎng)等于m m個(gè)個(gè) CPUCPU字字, ,B BM M =mW/T =mW/TM M W位W位W位W位地址寄存器單體多字單體多字(m=4)(m=4)存儲(chǔ)器存

8、儲(chǔ)器 W位單字長(zhǎng)寄存器單字長(zhǎng)寄存器 3)3)多體單字交叉多體單字交叉總線控制地址寄存器0 地址寄存器1 地址寄存器2地址寄存器3M0M1M2M3主控(主存控制部件) CPUIOP多體多體(m=4)(m=4)交叉存儲(chǔ)器交叉存儲(chǔ)器 a) a)存儲(chǔ)器字長(zhǎng)等于存儲(chǔ)器字長(zhǎng)等于m m個(gè)個(gè)CPUCPU字，字，B BM M =mW/T =mW/TM M。實(shí)際頻。實(shí)際頻寬大于單體多字。寬大于單體多字。 單體多字：并行讀出的單體多字：并行讀出的m m個(gè)字要地址順序的存在個(gè)字要地址順序的存在于同一主存單元。于同一主存單元。 多體單字：多體單字：m m個(gè)個(gè)CPUCPU字地址不必順序存放，只要不字地址不必順序存放，只要

9、不發(fā)生沖突。發(fā)生沖突。 b)b)編址模式編址模式 M Mj j體的編制模式為：體的編制模式為：m i+jm i+j； 其中其中I=0I=0，1 1， ，l-1l-1，表示第，表示第i i個(gè)字；個(gè)字； j=0j=0，1 1， ，m-1m-1，表示第，表示第j j個(gè)分體；個(gè)分體； m m模模 單體多字：一個(gè)主存包含的單體多字：一個(gè)主存包含的CPUCPU字?jǐn)?shù)字?jǐn)?shù) 多體單字：分體體數(shù)多體單字：分體體數(shù)模體模體地址編址序列地址編址序列二進(jìn)制地址碼末二位狀態(tài)二進(jìn)制地址碼末二位狀態(tài)M M0 0M M1 1M M2 2M M3 30,4,8, 12, ,4i+0, 1,5,9, 13, ,4i+1, 2,6,

10、10, 14, ,4i+2, 3,7,11, 15, ,4i+3, 00011011地址的模地址的模4 4低位交叉編址低位交叉編址 4) 4)多體多字交叉多體多字交叉 多個(gè)存儲(chǔ)體，每個(gè)存儲(chǔ)體有多個(gè)存儲(chǔ)體，每個(gè)存儲(chǔ)體有CPUCPU字。字。 上述能并行讀出多個(gè)上述能并行讀出多個(gè)CPUCPU字的單體多字和多體字的單體多字和多體單字或多體多字的交叉存儲(chǔ)主存系統(tǒng)統(tǒng)稱為并行單字或多體多字的交叉存儲(chǔ)主存系統(tǒng)統(tǒng)稱為并行主存系統(tǒng)。主存系統(tǒng)。2.2.分析分析 提高提高m m值，可以提高主存系統(tǒng)的最大頻率，但值，可以提高主存系統(tǒng)的最大頻率，但并不能線性提高實(shí)際頻率。并不能線性提高實(shí)際頻率。 原因：原因： 1)1)模

11、模m m越高，存儲(chǔ)器數(shù)據(jù)總線越長(zhǎng)，導(dǎo)致傳輸越高，存儲(chǔ)器數(shù)據(jù)總線越長(zhǎng)，導(dǎo)致傳輸 延遲增加；延遲增加； 2)2)系統(tǒng)效率問(wèn)題，對(duì)于順序取指，效率可以系統(tǒng)效率問(wèn)題，對(duì)于順序取指，效率可以 提高提高m m倍，但遇到轉(zhuǎn)移指令，效率就會(huì)下降。倍，但遇到轉(zhuǎn)移指令，效率就會(huì)下降。3.3.模型分析模型分析 對(duì)于對(duì)于m m個(gè)獨(dú)立分體的主存系統(tǒng)，處理機(jī)發(fā)出一個(gè)獨(dú)立分體的主存系統(tǒng)，處理機(jī)發(fā)出一 串地址為串地址為A A1 1,A,A2 2, A Aq q的訪存申請(qǐng)隊(duì)，在每個(gè)主的訪存申請(qǐng)隊(duì)，在每個(gè)主 存周期到來(lái)前，申請(qǐng)隊(duì)被掃描，截取從隊(duì)頭起存周期到來(lái)前，申請(qǐng)隊(duì)被掃描，截取從隊(duì)頭起 的的A A1 1,A,A2 2, A A

12、k k的申請(qǐng)序列。申請(qǐng)序列是個(gè)在要的申請(qǐng)序列。申請(qǐng)序列是個(gè)在要 求訪存申請(qǐng)的求訪存申請(qǐng)的k k個(gè)地址中，沒有兩個(gè)或兩個(gè)以上個(gè)地址中，沒有兩個(gè)或兩個(gè)以上 的地址處于同一分體中的最長(zhǎng)序列。顯然的地址處于同一分體中的最長(zhǎng)序列。顯然k k表示表示 可以同時(shí)訪問(wèn)的分體個(gè)數(shù)的隨機(jī)變量，不大于可以同時(shí)訪問(wèn)的分體個(gè)數(shù)的隨機(jī)變量，不大于m m， 系統(tǒng)效率取決于系統(tǒng)效率取決于k k的均值的均值B B，其值越大，可訪問(wèn)，其值越大，可訪問(wèn) 的分體個(gè)數(shù)越多，系統(tǒng)效率越高。的分體個(gè)數(shù)越多，系統(tǒng)效率越高。 1)1)數(shù)學(xué)模型數(shù)學(xué)模型 設(shè)設(shè)p(k)p(k)表示申請(qǐng)序列長(zhǎng)度為表示申請(qǐng)序列長(zhǎng)度為k k的概率密度函數(shù)，的概率密度函數(shù)

13、，其中其中k=1,2,mk=1,2,m。則。則k k的均值的均值B B為為 B=kB=k p(k)p(k) B B實(shí)際就是每個(gè)主存周期所訪問(wèn)的平均字?jǐn)?shù)。而實(shí)際就是每個(gè)主存周期所訪問(wèn)的平均字?jǐn)?shù)。而p(k)p(k)與程序的狀態(tài)密切相關(guān)，特別是指令轉(zhuǎn)移概與程序的狀態(tài)密切相關(guān)，特別是指令轉(zhuǎn)移概率率p p，它定義為給定下條指令地址為非順序地址，它定義為給定下條指令地址為非順序地址的概率。因此的概率。因此 p(k)=(1-p)p(k)=(1-p)k-1k-1 p p， 1km 1km 幾何概率幾何概率 p(m)=(1-p)p(m)=(1-p)m-1m-1k=1k=1m m 所以，所以，B=kB=k p(k

14、)=1p(k)=1 p+2p+2 (1-p)(1-p) p p + +m + +m (1-p)(1-p)m-1m-1 =(1-(1-p)=(1-(1-p)m m)/p)/p 2) 2)討論：討論： a)a)若每條指令都是轉(zhuǎn)移指令且轉(zhuǎn)移成功，即若每條指令都是轉(zhuǎn)移指令且轉(zhuǎn)移成功，即p=1,p=1,則則B=1B=1，就是并行多體交叉存取的實(shí)際頻寬，就是并行多體交叉存取的實(shí)際頻寬降到和單體單字一樣；降到和單體單字一樣； b)b)若所有指令都不轉(zhuǎn)移，即若所有指令都不轉(zhuǎn)移，即p=0p=0，則，則B=mB=m，此時(shí)，此時(shí)多體交叉存儲(chǔ)的效率最高。多體交叉存儲(chǔ)的效率最高。k=1k=1m m 3) )結(jié)論結(jié)論 由

15、于程序的轉(zhuǎn)移概率不會(huì)很低，數(shù)據(jù)分布的離由于程序的轉(zhuǎn)移概率不會(huì)很低，數(shù)據(jù)分布的離散性較大，所以單純靠增大散性較大，所以單純靠增大m m來(lái)提高并行主存系來(lái)提高并行主存系統(tǒng)的頻寬是有限的，而且性價(jià)比還會(huì)隨統(tǒng)的頻寬是有限的，而且性價(jià)比還會(huì)隨m m的增大的增大而下降。如果采用并行主存系統(tǒng)仍不能滿足速度而下降。如果采用并行主存系統(tǒng)仍不能滿足速度上的要求，就必須從系統(tǒng)結(jié)構(gòu)上改進(jìn)，采用存儲(chǔ)上的要求，就必須從系統(tǒng)結(jié)構(gòu)上改進(jìn)，采用存儲(chǔ)體系。體系。4.1.3 4.1.3 存儲(chǔ)體系的形成與分支存儲(chǔ)體系的形成與分支 1.容量需求容量需求 1)程序覆蓋技術(shù)程序覆蓋技術(shù) 方法：方法：將大程序分塊，將大程序分塊， 確定在輔存

16、中的位置并放入輔存，然后根據(jù)要確定在輔存中的位置并放入輔存，然后根據(jù)要 求把當(dāng)前用到的程序和數(shù)據(jù)調(diào)入主存中指定位求把當(dāng)前用到的程序和數(shù)據(jù)調(diào)入主存中指定位 置以覆蓋或替換那些已在主存但現(xiàn)在不用的段。置以覆蓋或替換那些已在主存但現(xiàn)在不用的段。 這只構(gòu)成一個(gè)存儲(chǔ)系統(tǒng)而非存儲(chǔ)體系。主輔存這只構(gòu)成一個(gè)存儲(chǔ)系統(tǒng)而非存儲(chǔ)體系。主輔存 間的調(diào)入調(diào)出完全由程序員安排，增大編程難間的調(diào)入調(diào)出完全由程序員安排，增大編程難 度和負(fù)擔(dān)，拉長(zhǎng)程序運(yùn)行時(shí)間，也難以使用更度和負(fù)擔(dān)，拉長(zhǎng)程序運(yùn)行時(shí)間，也難以使用更 好的算法。好的算法。主存主存輔存輔存程序員程序員 2)增設(shè)輔助軟硬件增設(shè)輔助軟硬件 隨著隨著I/O處理處理機(jī)的出現(xiàn)

17、及多道機(jī)的出現(xiàn)及多道程序的發(fā)展，一道程序的發(fā)展，一道程序的運(yùn)行可以與程序的運(yùn)行可以與另一道程序的調(diào)入調(diào)出同時(shí)進(jìn)行。因此主輔存間另一道程序的調(diào)入調(diào)出同時(shí)進(jìn)行。因此主輔存間的地址定位可以改由輔助軟硬件來(lái)完成，如圖。的地址定位可以改由輔助軟硬件來(lái)完成，如圖。這樣就構(gòu)成了存儲(chǔ)體系，或存儲(chǔ)層次。這樣就構(gòu)成了存儲(chǔ)體系，或存儲(chǔ)層次。主存主存輔存輔存輔助軟硬設(shè)備輔助軟硬設(shè)備從整體來(lái)看，從整體來(lái)看，速度是主存的速度是主存的容量是輔存的容量是輔存的主存主存輔存存儲(chǔ)層次輔存存儲(chǔ)層次 如果存儲(chǔ)層次能以接近于輔存的每位價(jià)格構(gòu)成如果存儲(chǔ)層次能以接近于輔存的每位價(jià)格構(gòu)成等于輔存容量的快速主存，存儲(chǔ)系統(tǒng)的性價(jià)比就等于輔存容量

18、的快速主存，存儲(chǔ)系統(tǒng)的性價(jià)比就會(huì)大大提高。進(jìn)一步完善發(fā)展就形成虛擬存儲(chǔ)系會(huì)大大提高。進(jìn)一步完善發(fā)展就形成虛擬存儲(chǔ)系統(tǒng)。這樣程序員就可以用機(jī)器指令的地址碼對(duì)整統(tǒng)。這樣程序員就可以用機(jī)器指令的地址碼對(duì)整個(gè)程序統(tǒng)一編址，這一空間遠(yuǎn)大于實(shí)際主存空間。個(gè)程序統(tǒng)一編址，這一空間遠(yuǎn)大于實(shí)際主存空間。這種指令地址碼稱為虛地址、邏輯地址、程序地這種指令地址碼稱為虛地址、邏輯地址、程序地址等，其對(duì)應(yīng)的存儲(chǔ)容量稱為虛存容量或程序空址等，其對(duì)應(yīng)的存儲(chǔ)容量稱為虛存容量或程序空間；而實(shí)際主存的地址稱為物理地址、實(shí)間；而實(shí)際主存的地址稱為物理地址、實(shí)( (存存) )地地址，其對(duì)應(yīng)的存儲(chǔ)容量稱為主存容量、實(shí)存容量址，其對(duì)應(yīng)的

19、存儲(chǔ)容量稱為主存容量、實(shí)存容量或?qū)嵒驅(qū)? (主主) )存空間存空間。 由于程序空間遠(yuǎn)大于主存空間，特別多道程序，由于程序空間遠(yuǎn)大于主存空間，特別多道程序，每個(gè)用戶只用到主存空間的一部分，不能將程序每個(gè)用戶只用到主存空間的一部分，不能將程序全部裝入主存，只能把程序空間分成較小的塊或全部裝入主存，只能把程序空間分成較小的塊或頁(yè)，由系統(tǒng)負(fù)責(zé)把所需塊或頁(yè)按需調(diào)入主存。當(dāng)頁(yè)，由系統(tǒng)負(fù)責(zé)把所需塊或頁(yè)按需調(diào)入主存。當(dāng)用虛地址訪問(wèn)主存時(shí)，首先檢查其對(duì)應(yīng)的內(nèi)容是用虛地址訪問(wèn)主存時(shí)，首先檢查其對(duì)應(yīng)的內(nèi)容是否已在主存。若在，就由硬件自動(dòng)把虛地址變換否已在主存。若在，就由硬件自動(dòng)把虛地址變換成實(shí)地址去訪存；否則需經(jīng)輔

20、助軟硬件將包含所成實(shí)地址去訪存；否則需經(jīng)輔助軟硬件將包含所要訪問(wèn)的單元在內(nèi)的那一塊程序由虛存調(diào)入主存，要訪問(wèn)的單元在內(nèi)的那一塊程序由虛存調(diào)入主存，然后進(jìn)行訪問(wèn)。這樣，不論是虛實(shí)地址的變換還然后進(jìn)行訪問(wèn)。這樣，不論是虛實(shí)地址的變換還是程序的調(diào)入都不必程序員安排，而是透明的。是程序的調(diào)入都不必程序員安排，而是透明的。也正符合存儲(chǔ)層次的要求。也正符合存儲(chǔ)層次的要求。2.速度需求速度需求 由于主存和由于主存和CPUCPU的速度差距已達(dá)一個(gè)數(shù)量級(jí)，的速度差距已達(dá)一個(gè)數(shù)量級(jí)， 為了解決這一問(wèn)題，提出了多種辦法：為了解決這一問(wèn)題，提出了多種辦法： 1)在在CPUCPU中設(shè)置通用寄存器中設(shè)置通用寄存器(GR)

21、，讓運(yùn)算直接在，讓運(yùn)算直接在CPUCPU的的GRGR中進(jìn)行，減少與主存的交往。但主存與中進(jìn)行，減少與主存的交往。但主存與GRGR間間的傳送要由程序設(shè)計(jì)者安排，且的傳送要由程序設(shè)計(jì)者安排，且GRGR的數(shù)目不能過(guò)的數(shù)目不能過(guò)多。多。 2)2)采用存儲(chǔ)器的多體交叉并行存取來(lái)提高主存的速采用存儲(chǔ)器的多體交叉并行存取來(lái)提高主存的速度。但這種方法對(duì)速度的改善有限，且有可能使度。但這種方法對(duì)速度的改善有限，且有可能使性價(jià)比下降。性價(jià)比下降。 3)CacheCache主存存儲(chǔ)層次主存存儲(chǔ)層次 通過(guò)在通過(guò)在CPUCPU與主存間加一級(jí)速度高、容量小、每與主存間加一級(jí)速度高、容量小、每個(gè)價(jià)格較高的高速緩沖存儲(chǔ)器個(gè)價(jià)

22、格較高的高速緩沖存儲(chǔ)器(Cache)(Cache)，借助于，借助于硬件是硬件是CacheCache和主存構(gòu)成一個(gè)整體。信息在和主存構(gòu)成一個(gè)整體。信息在CacheCache與主存間的傳送全部由硬件完成，所以與主存間的傳送全部由硬件完成，所以CacheCache對(duì)對(duì)應(yīng)用程序員和系統(tǒng)程序員都是透明的。應(yīng)用程序員和系統(tǒng)程序員都是透明的。高速緩沖高速緩沖 CacheCache 主主 存存 M M輔助硬件輔助硬件CPUCPU從從CPUCPU來(lái)看，來(lái)看，速度是速度是Cache的的容量是主存的容量是主存的 4)多級(jí)存儲(chǔ)層次多級(jí)存儲(chǔ)層次 從從M M1 1到到M Mn n，速度變慢，容量增大，價(jià)格降低。，速度變慢

23、，容量增大，價(jià)格降低。CPUCPUM M1 1M M2 2M M3 3M Mn n從從CPU來(lái)看，來(lái)看，速度是速度是M M1 1的，的，容量是容量是M Mn n的，的，價(jià)格價(jià)格是M Mn n的 程序局部性概念：程序局部性概念： a)a)時(shí)間局部性：在最近的未來(lái)要用到的信息很時(shí)間局部性：在最近的未來(lái)要用到的信息很可能是現(xiàn)在正在使用的信息，這是由程序循環(huán)造可能是現(xiàn)在正在使用的信息，這是由程序循環(huán)造成的，即循環(huán)中的語(yǔ)句要被重復(fù)執(zhí)行。成的，即循環(huán)中的語(yǔ)句要被重復(fù)執(zhí)行。 b)b)空間局部性：在最近的未來(lái)要用到的信息很空間局部性：在最近的未來(lái)要用到的信息很可能與現(xiàn)在正在使用的信息在程序空間上相鄰或可能與現(xiàn)

24、在正在使用的信息在程序空間上相鄰或相近，這是由于指令通常是順序執(zhí)行的。相近，這是由于指令通常是順序執(zhí)行的。 利用程序局部性，可以預(yù)知下一步要訪問(wèn)的利用程序局部性，可以預(yù)知下一步要訪問(wèn)的程序塊而在程序塊而在M M1 1中做好準(zhǔn)備。中做好準(zhǔn)備。時(shí)間局部性：存放近期使用過(guò)的塊或頁(yè)。時(shí)間局部性：存放近期使用過(guò)的塊或頁(yè)?？臻g局部性：從空間局部性：從M M2 2級(jí)把訪問(wèn)字所在頁(yè)或塊一同取級(jí)把訪問(wèn)字所在頁(yè)或塊一同取 到到M M1 1中。中。4.1.4 4.1.4 存儲(chǔ)體系的性能參數(shù)存儲(chǔ)體系的性能參數(shù) 以以如圖如圖所示的二級(jí)體系所示的二級(jí)體系(M(M1 1,M,M2 2) )為例來(lái)分析為例來(lái)分析 1.存儲(chǔ)體系

25、的每位存儲(chǔ)體系的每位 平均價(jià)格平均價(jià)格c c c c1 1 S SM1 M1 +c+c2 2 S SM2M2 S SM1 M1 +S+SM2M2 1)M M2 2容量大且便宜容量大且便宜，所以，所以， S SM1M122n nv v，使得頁(yè)表，使得頁(yè)表 中絕大部分行中實(shí)頁(yè)號(hào)中絕大部分行中實(shí)頁(yè)號(hào)n nv v字段及其它字段都不字段及其它字段都不 再有用了，這就會(huì)大大降低頁(yè)表的空間利用率。再有用了，這就會(huì)大大降低頁(yè)表的空間利用率。 c)解決辦法解決辦法 將頁(yè)表中裝入位為將頁(yè)表中裝入位為0的行用實(shí)頁(yè)號(hào)的行用實(shí)頁(yè)號(hào)n nv v字段存放字段存放該程序此虛頁(yè)在輔存中的實(shí)地址，以便調(diào)頁(yè)時(shí)該程序此虛頁(yè)在輔存中的

26、實(shí)地址，以便調(diào)頁(yè)時(shí)實(shí)現(xiàn)用戶虛頁(yè)號(hào)到輔存實(shí)地址的變換。實(shí)現(xiàn)用戶虛頁(yè)號(hào)到輔存實(shí)地址的變換。 相聯(lián)目錄表法相聯(lián)目錄表法: :把頁(yè)表壓縮成只存放已裝入主把頁(yè)表壓縮成只存放已裝入主存的那些虛頁(yè)存的那些虛頁(yè)( (用基號(hào)用基號(hào)b b和和N Nv v標(biāo)識(shí)標(biāo)識(shí)) )與實(shí)頁(yè)位置與實(shí)頁(yè)位置(n(nv v) )的對(duì)應(yīng)關(guān)系。這樣該表最多為的對(duì)應(yīng)關(guān)系。這樣該表最多為2 2n nv v行，簡(jiǎn)稱行，簡(jiǎn)稱為目錄表法，采用按內(nèi)容訪問(wèn)的相聯(lián)存儲(chǔ)器構(gòu)為目錄表法，采用按內(nèi)容訪問(wèn)的相聯(lián)存儲(chǔ)器構(gòu)成。成。如下圖：如下圖：基號(hào)基號(hào)用戶虛頁(yè)號(hào)用戶虛頁(yè)號(hào)頁(yè)內(nèi)位移頁(yè)內(nèi)位移某用戶虛地址某用戶虛地址基號(hào)用戶基號(hào)用戶 虛頁(yè)號(hào)虛頁(yè)號(hào)實(shí)頁(yè)號(hào)實(shí)頁(yè)號(hào)其它其它信息

27、信息目錄表目錄表( (存在相聯(lián)存儲(chǔ)器中存在相聯(lián)存儲(chǔ)器中) )相聯(lián)比較相聯(lián)比較查找到查找到目錄表法目錄表法NvbNrnvnvnr(Nr)npb+Nv2 2n nv v行行 d)相聯(lián)存儲(chǔ)器相聯(lián)存儲(chǔ)器 在一個(gè)存儲(chǔ)周期內(nèi)能將給定的在一個(gè)存儲(chǔ)周期內(nèi)能將給定的N Nv v同時(shí)與目錄表同時(shí)與目錄表 的全部的全部2 2n nv v個(gè)單元對(duì)應(yīng)的虛頁(yè)號(hào)字段內(nèi)容比較進(jìn)行個(gè)單元對(duì)應(yīng)的虛頁(yè)號(hào)字段內(nèi)容比較進(jìn)行 相聯(lián)查找。如有相符的即相聯(lián)查找到時(shí)，表示此相聯(lián)查找。如有相符的即相聯(lián)查找到時(shí)，表示此 虛頁(yè)已裝入主存，該單元存放的實(shí)頁(yè)號(hào)虛頁(yè)已裝入主存，該單元存放的實(shí)頁(yè)號(hào)n nv v就是此就是此 虛頁(yè)所存放的實(shí)頁(yè)位置，將其讀出拼接

28、上虛頁(yè)所存放的實(shí)頁(yè)位置，將其讀出拼接上N Nr r就可就可 形成訪存實(shí)地址形成訪存實(shí)地址n np p；如無(wú)相符的即相聯(lián)查找不到，；如無(wú)相符的即相聯(lián)查找不到， 表示此虛頁(yè)未裝入主存，發(fā)生頁(yè)面失效，請(qǐng)求從表示此虛頁(yè)未裝入主存，發(fā)生頁(yè)面失效，請(qǐng)求從 輔存中調(diào)頁(yè)。由此可見，采用目錄表法不用設(shè)置輔存中調(diào)頁(yè)。由此可見，采用目錄表法不用設(shè)置 裝入位了。裝入位了。 6)虛頁(yè)的調(diào)入虛頁(yè)的調(diào)入 當(dāng)發(fā)生頁(yè)面失效時(shí)，要想把該道程序的虛頁(yè)當(dāng)發(fā)生頁(yè)面失效時(shí)，要想把該道程序的虛頁(yè) 調(diào)入主存，必須給出該頁(yè)在輔存中的實(shí)際地址。調(diào)入主存，必須給出該頁(yè)在輔存中的實(shí)際地址。 為了提高調(diào)頁(yè)效率，輔存一般是按信息塊編址為了提高調(diào)頁(yè)效率，

29、輔存一般是按信息塊編址 的，且塊的大小等于頁(yè)面大小。以磁盤為例，的，且塊的大小等于頁(yè)面大小。以磁盤為例， 輔存實(shí)輔存實(shí)( (塊塊) )地址格式地址格式NvNvd d為：為： 這樣就需要將多用戶虛頁(yè)號(hào)這樣就需要將多用戶虛頁(yè)號(hào)N Nv v變換成輔存實(shí)變換成輔存實(shí) 地址地址NvNvd d 。磁盤號(hào)磁盤號(hào)柱面號(hào)柱面號(hào)磁頭號(hào)磁頭號(hào)塊塊 號(hào)號(hào)NvNvd d 外頁(yè)表外頁(yè)表:存放用戶虛頁(yè)號(hào)存放用戶虛頁(yè)號(hào)N Nv v與輔存實(shí)地址與輔存實(shí)地址NvNvd d的的 映像關(guān)系，用于外部地址變換。映像關(guān)系，用于外部地址變換。 內(nèi)頁(yè)表內(nèi)頁(yè)表:存放用戶虛頁(yè)號(hào)存放用戶虛頁(yè)號(hào)N Nv v與主存實(shí)頁(yè)號(hào)與主存實(shí)頁(yè)號(hào)n nv v的映的

30、映 像關(guān)系，用于內(nèi)部地址變換。像關(guān)系，用于內(nèi)部地址變換。 由于虛擬存儲(chǔ)器的頁(yè)面失效率很低，很少調(diào)用由于虛擬存儲(chǔ)器的頁(yè)面失效率很低，很少調(diào)用 外頁(yè)表進(jìn)行地址變換，因此外頁(yè)表存放在輔存中，外頁(yè)表進(jìn)行地址變換，因此外頁(yè)表存放在輔存中， 當(dāng)某道程序初始運(yùn)行時(shí)，才把外頁(yè)表的內(nèi)容轉(zhuǎn)錄當(dāng)某道程序初始運(yùn)行時(shí)，才把外頁(yè)表的內(nèi)容轉(zhuǎn)錄 到已建立內(nèi)頁(yè)表的實(shí)頁(yè)號(hào)地址字段中，這也是前到已建立內(nèi)頁(yè)表的實(shí)頁(yè)號(hào)地址字段中，這也是前 述當(dāng)內(nèi)頁(yè)表裝入位為述當(dāng)內(nèi)頁(yè)表裝入位為0時(shí)讓實(shí)頁(yè)號(hào)地址字段改放時(shí)讓實(shí)頁(yè)號(hào)地址字段改放 該虛頁(yè)在輔存中的實(shí)地址的原因。而且對(duì)外頁(yè)表該虛頁(yè)在輔存中的實(shí)地址的原因。而且對(duì)外頁(yè)表 速度要求低，可以用軟件實(shí)現(xiàn)。

31、速度要求低，可以用軟件實(shí)現(xiàn)。如下圖：如下圖：磁盤號(hào)磁盤號(hào)柱面號(hào)柱面號(hào) 磁頭號(hào)磁頭號(hào) 塊號(hào)塊號(hào)NvNvd d多用戶虛地址多用戶虛地址輔存地址輔存地址NrNSuNvNvNvd d1 1裝入位裝入位輔存實(shí)地址輔存實(shí)地址 地址變換地址變換( (軟件實(shí)現(xiàn)軟件實(shí)現(xiàn)) )已裝入已裝入外頁(yè)表外頁(yè)表虛地址到輔存實(shí)地址的變換虛地址到輔存實(shí)地址的變換2Nv2.替換算法替換算法 1)解決問(wèn)題解決問(wèn)題 當(dāng)處理機(jī)要用到的指令或數(shù)據(jù)不在主存中時(shí)，當(dāng)處理機(jī)要用到的指令或數(shù)據(jù)不在主存中時(shí)， 就會(huì)產(chǎn)生頁(yè)面失效，應(yīng)去輔存中將包含該指令就會(huì)產(chǎn)生頁(yè)面失效，應(yīng)去輔存中將包含該指令 或數(shù)據(jù)的一頁(yè)調(diào)入主存。由于虛存空間比主存或數(shù)據(jù)的一頁(yè)調(diào)入

32、主存。由于虛存空間比主存 空間大得多，必然會(huì)出現(xiàn)主存頁(yè)面位置已全被空間大得多，必然會(huì)出現(xiàn)主存頁(yè)面位置已全被 占用后又發(fā)生頁(yè)面失效，這時(shí)再將輔存中的一占用后又發(fā)生頁(yè)面失效，這時(shí)再將輔存中的一 頁(yè)調(diào)入主存時(shí)就發(fā)生頁(yè)面爭(zhēng)用。只用強(qiáng)制騰出頁(yè)調(diào)入主存時(shí)就發(fā)生頁(yè)面爭(zhēng)用。只用強(qiáng)制騰出 主存中某頁(yè)后才能接納從輔存調(diào)來(lái)的新頁(yè)。具主存中某頁(yè)后才能接納從輔存調(diào)來(lái)的新頁(yè)。具 體選擇主存中哪一頁(yè)作為被替換的頁(yè)，就是替體選擇主存中哪一頁(yè)作為被替換的頁(yè)，就是替 換算法要解決的問(wèn)題。換算法要解決的問(wèn)題。 2)原則原則 a)有高的主存命中率有高的主存命中率 b)算法便于實(shí)現(xiàn)算法便于實(shí)現(xiàn) c)輔助軟、硬件成本盡量低輔助軟、硬件成

33、本盡量低 3)常用算法常用算法 a)隨機(jī)算法隨機(jī)算法( (Random,RAND) ) 用軟的或硬的隨機(jī)數(shù)產(chǎn)生器來(lái)形成主存中要被用軟的或硬的隨機(jī)數(shù)產(chǎn)生器來(lái)形成主存中要被替換頁(yè)的頁(yè)號(hào)。這種算法簡(jiǎn)單，易于實(shí)現(xiàn)，但沒替換頁(yè)的頁(yè)號(hào)。這種算法簡(jiǎn)單，易于實(shí)現(xiàn)，但沒有利用主存使用情況的歷史信息，反映不了程序有利用主存使用情況的歷史信息，反映不了程序的局部性，使主存命中率低，很少采用。的局部性，使主存命中率低，很少采用。 b)先進(jìn)先出算法先進(jìn)先出算法(First In First Out,FIFO) 選擇最早裝入的頁(yè)作為被替換的頁(yè)。這種算法選擇最早裝入的頁(yè)作為被替換的頁(yè)。這種算法 實(shí)現(xiàn)方便，雖然利用了主存使用

34、情況的歷史信息，實(shí)現(xiàn)方便，雖然利用了主存使用情況的歷史信息， 但是不一定能正確反映出程序的局部性，因?yàn)樽畹遣灰欢苷_反映出程序的局部性，因?yàn)樽?先進(jìn)入的頁(yè)很可能是現(xiàn)在經(jīng)常要用到的頁(yè)先進(jìn)入的頁(yè)很可能是現(xiàn)在經(jīng)常要用到的頁(yè)。 實(shí)頁(yè)號(hào)實(shí)頁(yè)號(hào) 占用位占用位 程序號(hào)程序號(hào) 段頁(yè)號(hào)段頁(yè)號(hào) 計(jì)數(shù)器計(jì)數(shù)器(使用位使用位) 程序優(yōu)先位程序優(yōu)先位 HS其它信息其它信息012nv-1主存頁(yè)面表主存頁(yè)面表 c)近期最少使用算法近期最少使用算法(Least Recently Used, ,LRU) ) 選擇近期最少訪問(wèn)的頁(yè)作為被替換的頁(yè)。這種選擇近期最少訪問(wèn)的頁(yè)作為被替換的頁(yè)。這種 算法能比較正確的反映程序的局部性，

35、因?yàn)楫?dāng)前算法能比較正確的反映程序的局部性，因?yàn)楫?dāng)前 最少使用的頁(yè)一般來(lái)說(shuō)未來(lái)也將很少訪問(wèn)，但完最少使用的頁(yè)一般來(lái)說(shuō)未來(lái)也將很少訪問(wèn)，但完 全按此算法實(shí)現(xiàn)比較困難，需要為每個(gè)實(shí)頁(yè)都配全按此算法實(shí)現(xiàn)比較困難，需要為每個(gè)實(shí)頁(yè)都配 置一個(gè)字長(zhǎng)很長(zhǎng)的計(jì)數(shù)器字段才行。所以一般采置一個(gè)字長(zhǎng)很長(zhǎng)的計(jì)數(shù)器字段才行。所以一般采 用它的變形，即近期最久沒被訪問(wèn)過(guò)的頁(yè)作為被用它的變形，即近期最久沒被訪問(wèn)過(guò)的頁(yè)作為被 替換的頁(yè)。這樣把替換的頁(yè)。這樣把“多多”和和“少少”簡(jiǎn)化成簡(jiǎn)化成“有有”和和“無(wú)無(wú)” 之后，實(shí)現(xiàn)起來(lái)比較方便。之后，實(shí)現(xiàn)起來(lái)比較方便。 主存頁(yè)面表主存頁(yè)面表 OS為實(shí)現(xiàn)主存管理而設(shè)置的，是對(duì)主存而言為實(shí)現(xiàn)

36、主存管理而設(shè)置的，是對(duì)主存而言 的，整個(gè)主存只有一個(gè)。每一行用來(lái)記錄主存中的，整個(gè)主存只有一個(gè)。每一行用來(lái)記錄主存中 各頁(yè)的使用狀況。而頁(yè)表是對(duì)程序空間而言的，各頁(yè)的使用狀況。而頁(yè)表是對(duì)程序空間而言的， 每道程序都有一個(gè)，是用來(lái)存儲(chǔ)地址映像關(guān)系和每道程序都有一個(gè)，是用來(lái)存儲(chǔ)地址映像關(guān)系和 實(shí)現(xiàn)地址變換的。實(shí)現(xiàn)地址變換的。 實(shí)頁(yè)號(hào)實(shí)頁(yè)號(hào):主存頁(yè)號(hào)是順序的，可以省略主存頁(yè)號(hào)是順序的，可以省略 占用位占用位:表示該主存頁(yè)面是否被占用表示該主存頁(yè)面是否被占用 程序號(hào)程序號(hào)/段頁(yè)號(hào)段頁(yè)號(hào):該主存頁(yè)被哪道程序的哪段該主存頁(yè)被哪道程序的哪段 哪頁(yè)占用哪頁(yè)占用 使用位使用位:表示該主存頁(yè)近期是否被使用過(guò)表示該

37、主存頁(yè)近期是否被使用過(guò) 開始時(shí)所有頁(yè)的使用位全為開始時(shí)所有頁(yè)的使用位全為“0”0”，只要某個(gè)頁(yè)，只要某個(gè)頁(yè)的的 任何單元被訪問(wèn)過(guò)，硬件就自動(dòng)將該頁(yè)使用位置任何單元被訪問(wèn)過(guò)，硬件就自動(dòng)將該頁(yè)使用位置 “ “1”1”。由于采用全相聯(lián)映像，調(diào)入頁(yè)可進(jìn)入對(duì)。由于采用全相聯(lián)映像，調(diào)入頁(yè)可進(jìn)入對(duì)應(yīng)應(yīng) 于主存頁(yè)面表中任何占用位為于主存頁(yè)面表中任何占用位為“0”0”的實(shí)頁(yè)位置，的實(shí)頁(yè)位置， 一旦裝入主存某實(shí)頁(yè)上，就置該實(shí)頁(yè)的占用位為一旦裝入主存某實(shí)頁(yè)上，就置該實(shí)頁(yè)的占用位為 “ “1”1”。只有當(dāng)所有占用位都是。只有當(dāng)所有占用位都是1 1且又發(fā)生頁(yè)面失且又發(fā)生頁(yè)面失效效 時(shí)才有頁(yè)面替換問(wèn)題，這時(shí)就要用到使用位

38、，只時(shí)才有頁(yè)面替換問(wèn)題，這時(shí)就要用到使用位，只 需替換使用位為需替換使用位為“0”0”的頁(yè)即可。的頁(yè)即可。 使用位全使用位全“1 ”處理處理 一種辦法是由硬件強(qiáng)制全部使用位都為一種辦法是由硬件強(qiáng)制全部使用位都為“0”。 從概念上看，近期最少使用的從概念上看，近期最少使用的“期期”是從上次使用是從上次使用 位全位全0到這次使用位全到這次使用位全0的這段時(shí)間。由于這個(gè)期的這段時(shí)間。由于這個(gè)期 的長(zhǎng)短是隨機(jī)的，所以稱為隨機(jī)期法。的長(zhǎng)短是隨機(jī)的，所以稱為隨機(jī)期法。 另一種辦法是它定期的置全部使用位為另一種辦法是它定期的置全部使用位為“0”。 由由“未用過(guò)計(jì)數(shù)器未用過(guò)計(jì)數(shù)器”HS(或稱為歷史位或稱為歷史

39、位)，定期地每，定期地每 隔隔t掃視使用位掃視使用位，對(duì)使用位為對(duì)使用位為0的頁(yè)，則加的頁(yè)，則加1Hs， 并讓使用位繼續(xù)為并讓使用位繼續(xù)為0；對(duì)使用位為；對(duì)使用位為1的頁(yè)，則置的頁(yè)，則置 0Hs，同時(shí)置，同時(shí)置0使用位。掃描結(jié)束所有使用位為使用位。掃描結(jié)束所有使用位為0， Hs大的就是最久未訪問(wèn)過(guò)的，作為替換頁(yè)。大的就是最久未訪問(wèn)過(guò)的，作為替換頁(yè)。 d)優(yōu)化替換算法優(yōu)化替換算法(OPT) 定義定義 無(wú)論是無(wú)論是“近期最少使用近期最少使用”還是還是“近期最久未用近期最久未用過(guò)過(guò)” 都屬于都屬于LRU，與，與FIFO類似，都是根據(jù)頁(yè)面使用類似，都是根據(jù)頁(yè)面使用 的歷史情況來(lái)預(yù)估未來(lái)的頁(yè)面使用狀況，

40、只是的歷史情況來(lái)預(yù)估未來(lái)的頁(yè)面使用狀況，只是 比比FIFO更好反映局部性而已。然而，這種更好反映局部性而已。然而，這種“近近期期”畢竟是過(guò)去了的近期，如果能根據(jù)未來(lái)實(shí)畢竟是過(guò)去了的近期，如果能根據(jù)未來(lái)實(shí)際使用情況，替換出近期不用的頁(yè)，主存命中際使用情況，替換出近期不用的頁(yè)，主存命中率會(huì)更高，這就是優(yōu)化替換算法率會(huì)更高，這就是優(yōu)化替換算法(Optimal Replacement Algorithm,OPT) 方法方法 在時(shí)刻在時(shí)刻t找出主存中每個(gè)頁(yè)面將要用到的時(shí)刻找出主存中每個(gè)頁(yè)面將要用到的時(shí)刻ti， 然后選擇然后選擇tit最大的那一頁(yè)作為被替換的頁(yè)。顯最大的那一頁(yè)作為被替換的頁(yè)。顯 然，這只有

41、讓程序運(yùn)行一遍得到實(shí)際的頁(yè)地址流，然，這只有讓程序運(yùn)行一遍得到實(shí)際的頁(yè)地址流， 才能找到為實(shí)現(xiàn)這種替換算法所需要的各頁(yè)使用才能找到為實(shí)現(xiàn)這種替換算法所需要的各頁(yè)使用 信息，這是不現(xiàn)實(shí)的。所以，優(yōu)化替換算法只是信息，這是不現(xiàn)實(shí)的。所以，優(yōu)化替換算法只是 一種理想化的算法，它可以被用作評(píng)價(jià)其它替換一種理想化的算法，它可以被用作評(píng)價(jià)其它替換 算法好壞的標(biāo)準(zhǔn)，看看哪種替換算法能使主存的算法好壞的標(biāo)準(zhǔn)，看看哪種替換算法能使主存的 命中率接近于優(yōu)化替換算法。命中率接近于優(yōu)化替換算法。 4)影響命命中率的因素影響命命中率的因素 a)與替換算法有關(guān)與替換算法有關(guān) 例：例：設(shè)有一道程序，有設(shè)有一道程序，有1 1

42、至至5 5共共5 5頁(yè)，執(zhí)行時(shí)的頁(yè)，執(zhí)行時(shí)的 頁(yè)地址流頁(yè)地址流( (即執(zhí)行時(shí)依次使用到的程序頁(yè)頁(yè)號(hào)即執(zhí)行時(shí)依次使用到的程序頁(yè)頁(yè)號(hào)) )為：為： 2 2，3 3，2 2，1 1，5 5，2 2，4 4，5 5，3 3，2 2，5 5，2 2 若分配給該道程序的主存有若分配給該道程序的主存有3 3頁(yè)，如下圖表示分頁(yè)，如下圖表示分別用別用FIFO,LRU,OPT3FIFO,LRU,OPT3種替換算法對(duì)這種替換算法對(duì)這3 3頁(yè)的使用頁(yè)的使用和替換過(guò)程。和替換過(guò)程。FIFOFIFO的命中率最低，而的命中率最低，而LRULRU的接近的接近于于OPTOPT的。的。2* *312323命中命中2調(diào)進(jìn)調(diào)進(jìn) 調(diào)進(jìn)

43、調(diào)進(jìn)調(diào)進(jìn)調(diào)進(jìn)53* *1替換替換521* *替換替換5* *24替換替換5* *24命中命中32* *4替換替換32* *4命中命中354* *替換替換3* *52替換替換 FIFO命中命中3次次2323命中命中2調(diào)進(jìn)調(diào)進(jìn) 調(diào)進(jìn)調(diào)進(jìn)2323命中命中2調(diào)進(jìn)調(diào)進(jìn) 調(diào)進(jìn)調(diào)進(jìn) LRU命中命中5次次 OPT命中命中6次次頁(yè)地址流頁(yè)地址流 2 3 2 1 5 2 4 5 3 2 5 2時(shí)間時(shí)間t 1 2 3 4 5 6 7 8 9 10 11 1223* *1調(diào)進(jìn)調(diào)進(jìn)2* *51替換替換251* *命中命中25* *4替換替換2* *54命中命中354* *替換替換35* *2替換替換3* *52命中命中

44、3* *52命中命中231* *調(diào)進(jìn)調(diào)進(jìn)23* *5替換替換2* *35命中命中4* *35替換替換4* *35命中命中4* *35命中命中23* *5替換替換235命中命中235命中命中3 3種替換算法對(duì)同一頁(yè)地址流的替換過(guò)程種替換算法對(duì)同一頁(yè)地址流的替換過(guò)程 b)命中率與頁(yè)地址流有關(guān)命中率與頁(yè)地址流有關(guān) 例如例如一個(gè)循環(huán)程序，當(dāng)所需頁(yè)數(shù)大于分配給一個(gè)循環(huán)程序，當(dāng)所需頁(yè)數(shù)大于分配給 它的主存頁(yè)數(shù)時(shí)，無(wú)論是它的主存頁(yè)數(shù)時(shí)，無(wú)論是FIFO還是還是LRU算法的算法的 命中率都明顯低于命中率都明顯低于OPT的。的。如下圖如下圖所示，所示，LRU 和和FIFO一次都沒有命中，因?yàn)樗『每偸菍ⅠR一次都沒

45、有命中，因?yàn)樗『每偸菍ⅠR 上要用到的頁(yè)面給替換出去了，從而連續(xù)不斷上要用到的頁(yè)面給替換出去了，從而連續(xù)不斷 的出現(xiàn)頁(yè)面失效，產(chǎn)生所謂的的出現(xiàn)頁(yè)面失效，產(chǎn)生所謂的顛簸現(xiàn)象顛簸現(xiàn)象。 1* *2312142* *3413* *4* *1231* *2342* * FIFO無(wú)命中無(wú)命中121121 LRU無(wú)命中無(wú)命中 OPT命中命中3次次頁(yè)地址流頁(yè)地址流 1 2 3 4 1 2 3 4時(shí)間時(shí)間t 1 2 3 4 5 6 7 812* *4134* *123* *1* *24命中命中命中命中13* *4命中命中 命中率與頁(yè)地址流有關(guān)命中率與頁(yè)地址流有關(guān)124* *1* *2342* *3413* *

46、4* *1231* *2342* * c)與主存容量與主存容量(即分配給程序的主存頁(yè)數(shù)即分配給程序的主存頁(yè)數(shù))有關(guān)有關(guān) 一般來(lái)說(shuō)，分配給程序的主存頁(yè)數(shù)越多，虛一般來(lái)說(shuō)，分配給程序的主存頁(yè)數(shù)越多，虛頁(yè)裝入主存的機(jī)會(huì)就越多，命中率也可能就越頁(yè)裝入主存的機(jī)會(huì)就越多，命中率也可能就越高。但具體還與所采用的替換算法有很大關(guān)系。高。但具體還與所采用的替換算法有很大關(guān)系。如下圖所示，當(dāng)分配給程序的主存頁(yè)數(shù)如下圖所示，當(dāng)分配給程序的主存頁(yè)數(shù)n由由3增增加到加到4時(shí)，時(shí)，F(xiàn)IFO的命中率反而由的命中率反而由3/12降到降到2/12;而而LRU的命中率卻不會(huì)發(fā)生這種情況，隨著分的命中率卻不會(huì)發(fā)生這種情況，隨著分配

47、給該道程序的主存頁(yè)數(shù)的增加，命中率一般配給該道程序的主存頁(yè)數(shù)的增加，命中率一般都會(huì)得到提高，至少不會(huì)降低。都會(huì)得到提高，至少不會(huì)降低。121* *21413* *4* *1251* *251* *2命中命中51* *2命中命中532* *5* *345* *34命中命中 n=3命中命中3次次12121 n=4命中命中2次次頁(yè)地址流頁(yè)地址流 1 2 3 4 1 2 5 1 2 3 4 5時(shí)間時(shí)間t 1 2 3 4 5 6 7 8 9 10 11 121* *23命中命中342* *3341* *234命中命中1* *23452* *34513* *45124* *5* *12341* *2345

48、2* *3FIFO法的實(shí)頁(yè)數(shù)增加，命中率反而有可能下降法的實(shí)頁(yè)數(shù)增加，命中率反而有可能下降 5)堆棧型替換算法堆棧型替換算法 a)定義定義 A A：長(zhǎng)度為：長(zhǎng)度為L(zhǎng)的任意一個(gè)頁(yè)面地址流的任意一個(gè)頁(yè)面地址流 t： 已處理過(guò)已處理過(guò)t1個(gè)頁(yè)面的時(shí)間點(diǎn)個(gè)頁(yè)面的時(shí)間點(diǎn) n：分配給該地址流的主存頁(yè)面數(shù)：分配給該地址流的主存頁(yè)面數(shù) Bt(n)：在：在t時(shí)間點(diǎn)、在時(shí)間點(diǎn)、在n頁(yè)的主存中的頁(yè)面集合頁(yè)的主存中的頁(yè)面集合 Lt：到：到t時(shí)刻已遇到的地址流中相異頁(yè)的頁(yè)數(shù)時(shí)刻已遇到的地址流中相異頁(yè)的頁(yè)數(shù) 若若 n= Lt時(shí)，時(shí)， Bt(n1) = Bt(n) 成立，則此替成立，則此替換算法屬于堆棧型的替換算法。換算法

49、屬于堆棧型的替換算法。 b)優(yōu)點(diǎn)優(yōu)點(diǎn) 命中率隨主存頁(yè)數(shù)的增加只可能提高，至少不命中率隨主存頁(yè)數(shù)的增加只可能提高，至少不會(huì)下降。會(huì)下降。 只需采用堆棧處理技術(shù)對(duì)地址流模擬處理一次，只需采用堆棧處理技術(shù)對(duì)地址流模擬處理一次，即可同時(shí)獲得對(duì)此地址流在不同主存頁(yè)數(shù)時(shí)的即可同時(shí)獲得對(duì)此地址流在不同主存頁(yè)數(shù)時(shí)的命中率，大大節(jié)省存儲(chǔ)體系設(shè)計(jì)的工作量。命中率，大大節(jié)省存儲(chǔ)體系設(shè)計(jì)的工作量。 對(duì)頁(yè)地址流對(duì)頁(yè)地址流A A在在t t時(shí)刻的時(shí)刻的A At t頁(yè)是否命中，只需看頁(yè)是否命中，只需看S St-1t-1( (主存在主存在t-1t-1時(shí)刻的堆棧時(shí)刻的堆棧) )的前的前n n項(xiàng)是否有項(xiàng)是否有A At t，若有則命

50、中。若有則命中。 c)LRU算法算法 屬于堆棧型算法，把剛訪問(wèn)過(guò)的頁(yè)面至屬于堆棧型算法，把剛訪問(wèn)過(guò)的頁(yè)面至于棧頂，而把最久未被訪問(wèn)過(guò)的頁(yè)面置于于棧頂，而把最久未被訪問(wèn)過(guò)的頁(yè)面置于棧底。命中率隨著分配給該道程序的主存棧底。命中率隨著分配給該道程序的主存頁(yè)數(shù)頁(yè)數(shù)n n的增加而單調(diào)上升，至少不會(huì)下降，的增加而單調(diào)上升，至少不會(huì)下降，這是堆棧型算法具有的共同特點(diǎn)。這是堆棧型算法具有的共同特點(diǎn)。 d)FIFO算法算法 非堆棧型算法，命中率總趨勢(shì)是會(huì)隨著非堆棧型算法，命中率總趨勢(shì)是會(huì)隨著主存頁(yè)數(shù)主存頁(yè)數(shù)n的增加而提高，但從某個(gè)局部的增加而提高，但從某個(gè)局部來(lái)看，主存頁(yè)數(shù)來(lái)看，主存頁(yè)數(shù)n的增加有時(shí)反倒可能降

51、的增加有時(shí)反倒可能降低其命中率。低其命中率。 5)頁(yè)面失效頻率法頁(yè)面失效頻率法(PFF) 由于堆棧型替換算法具有隨分配給該道程序的實(shí)由于堆棧型替換算法具有隨分配給該道程序的實(shí)頁(yè)數(shù)頁(yè)數(shù)n n的增加，命中率的增加，命中率H H會(huì)單調(diào)上升的特點(diǎn)，所以可會(huì)單調(diào)上升的特點(diǎn)，所以可對(duì)對(duì)LRULRU算法加以改進(jìn)和發(fā)展：根據(jù)各道程序運(yùn)行中算法加以改進(jìn)和發(fā)展：根據(jù)各道程序運(yùn)行中的主存頁(yè)面失效率的高低，由的主存頁(yè)面失效率的高低，由OSOS來(lái)動(dòng)態(tài)調(diào)節(jié)分配給來(lái)動(dòng)態(tài)調(diào)節(jié)分配給每道程序的實(shí)頁(yè)數(shù)。當(dāng)主存頁(yè)面失效率超過(guò)某個(gè)限每道程序的實(shí)頁(yè)數(shù)。當(dāng)主存頁(yè)面失效率超過(guò)某個(gè)限值時(shí)就自動(dòng)增加給該道程序的主存頁(yè)數(shù)來(lái)提高其命值時(shí)就自動(dòng)增加

52、給該道程序的主存頁(yè)數(shù)來(lái)提高其命中率；而當(dāng)主存頁(yè)面失效率低于某個(gè)限值時(shí)就自動(dòng)中率；而當(dāng)主存頁(yè)面失效率低于某個(gè)限值時(shí)就自動(dòng)減少分配給該道程序的主存頁(yè)數(shù)，以便釋放出這部減少分配給該道程序的主存頁(yè)數(shù)，以便釋放出這部分主存頁(yè)面位置給其它程序用，從而使整個(gè)系統(tǒng)總分主存頁(yè)面位置給其它程序用，從而使整個(gè)系統(tǒng)總的主存命中率和主存利用率得到提高。的主存命中率和主存利用率得到提高。3.虛擬存儲(chǔ)器工作的全過(guò)程虛擬存儲(chǔ)器工作的全過(guò)程 具體過(guò)程見下頁(yè)圖：具體過(guò)程見下頁(yè)圖：NvNvd d輔存實(shí)地址輔存實(shí)地址 外部地址變換外部地址變換虛地址虛地址=輔存實(shí)地址輔存實(shí)地址用戶標(biāo)志用戶標(biāo)志u虛頁(yè)號(hào)虛頁(yè)號(hào)NvNr 6 多用戶多用戶虛

53、地址虛地址N NS S 內(nèi)部地址變換內(nèi)部地址變換虛頁(yè)號(hào)虛頁(yè)號(hào)=主存實(shí)頁(yè)號(hào)主存實(shí)頁(yè)號(hào)nvnrnp 5 2 1 2頁(yè)面頁(yè)面02 2n nv v-1 2 2n nr r個(gè)字個(gè)字2 2n nv v個(gè)頁(yè)個(gè)頁(yè) 3 3 2是否在是否在 主存？主存？ “是是”( (訪主存訪主存) ) “否否”( (主存頁(yè)主存頁(yè) 面失效面失效) ) 4 5主存主存(頁(yè)式頁(yè)式) 2 2n np p個(gè)字個(gè)字是否在是否在 輔存？輔存？ 8 6 “否否”(輔存頁(yè)輔存頁(yè)面失效面失效) “是是”(訪輔存訪輔存)主存頁(yè)面表主存頁(yè)面表 9 6頁(yè)面替頁(yè)面替換算法換算法1112已滿已滿未滿未滿10I/O處理機(jī)處理機(jī)13主存主存頁(yè)號(hào)頁(yè)號(hào)頁(yè)面頁(yè)面0頁(yè)

54、面頁(yè)面0112Nv-1(選頁(yè)選頁(yè)) 714調(diào)入頁(yè)調(diào)入頁(yè) 714替換頁(yè)替換頁(yè) 被替換頁(yè)退回被替換頁(yè)退回若未被修改則不必退回若未被修改則不必退回 輔存輔存2 2N NS S個(gè)字個(gè)字4.2.34.2.3頁(yè)式虛擬存儲(chǔ)器實(shí)現(xiàn)中的問(wèn)題頁(yè)式虛擬存儲(chǔ)器實(shí)現(xiàn)中的問(wèn)題 1.頁(yè)面失效處理頁(yè)面失效處理 1)原因原因 頁(yè)面的劃分只是機(jī)械的對(duì)程序空間和主存空間頁(yè)面的劃分只是機(jī)械的對(duì)程序空間和主存空間進(jìn)行等分，與程序的邏輯結(jié)構(gòu)毫無(wú)關(guān)系。這樣，進(jìn)行等分，與程序的邏輯結(jié)構(gòu)毫無(wú)關(guān)系。這樣，對(duì)于按字節(jié)編址的存儲(chǔ)器就有可能出現(xiàn)一條指令對(duì)于按字節(jié)編址的存儲(chǔ)器就有可能出現(xiàn)一條指令橫跨在兩頁(yè)上存儲(chǔ)的情況。同理，也會(huì)出現(xiàn)一個(gè)橫跨在兩頁(yè)上存儲(chǔ)

55、的情況。同理，也會(huì)出現(xiàn)一個(gè)操作數(shù)跨在兩頁(yè)上存儲(chǔ)。另外，采用間接尋址，操作數(shù)跨在兩頁(yè)上存儲(chǔ)。另外，采用間接尋址，特別是多重間接尋址時(shí)，在尋址的過(guò)程中，可能特別是多重間接尋址時(shí)，在尋址的過(guò)程中，可能出現(xiàn)跨頁(yè)、甚至連續(xù)跨多個(gè)頁(yè)訪問(wèn)的情況。每當(dāng)出現(xiàn)跨頁(yè)、甚至連續(xù)跨多個(gè)頁(yè)訪問(wèn)的情況。每當(dāng)當(dāng)前一頁(yè)已在主存而跨頁(yè)存放的另一頁(yè)不在主存當(dāng)前一頁(yè)已在主存而跨頁(yè)存放的另一頁(yè)不在主存時(shí)，就會(huì)發(fā)生頁(yè)面失效。時(shí)，就會(huì)發(fā)生頁(yè)面失效。 2)解決方法解決方法 由于頁(yè)面失效可能出現(xiàn)于取指、取操作數(shù)、間接由于頁(yè)面失效可能出現(xiàn)于取指、取操作數(shù)、間接尋址等過(guò)程中，即會(huì)在一條指令的分析或執(zhí)行中發(fā)尋址等過(guò)程中，即會(huì)在一條指令的分析或執(zhí)行中

56、發(fā)生。通常的中斷都是依靠在每條指令執(zhí)行的末尾去生。通常的中斷都是依靠在每條指令執(zhí)行的末尾去設(shè)置一個(gè)訪中斷微操作，來(lái)檢查系統(tǒng)中有無(wú)未屏蔽設(shè)置一個(gè)訪中斷微操作，來(lái)檢查系統(tǒng)中有無(wú)未屏蔽的中斷請(qǐng)求，以便對(duì)其進(jìn)行響應(yīng)和處理。而頁(yè)面失的中斷請(qǐng)求，以便對(duì)其進(jìn)行響應(yīng)和處理。而頁(yè)面失效不能采用這種辦法，否則由于未能對(duì)頁(yè)面失效進(jìn)效不能采用這種辦法，否則由于未能對(duì)頁(yè)面失效進(jìn)行處理，就不可能調(diào)頁(yè)，也就無(wú)法執(zhí)行到訪中斷微行處理，就不可能調(diào)頁(yè)，也就無(wú)法執(zhí)行到訪中斷微操作，從而就不可能對(duì)頁(yè)面失效進(jìn)行響應(yīng)和處理，操作，從而就不可能對(duì)頁(yè)面失效進(jìn)行響應(yīng)和處理，機(jī)器的工作就被停頓下來(lái)。所以，頁(yè)面失效不能按機(jī)器的工作就被停頓下來(lái)。所

57、以，頁(yè)面失效不能按一般的中斷對(duì)待，應(yīng)看作一種故障，一旦出現(xiàn)，處一般的中斷對(duì)待，應(yīng)看作一種故障，一旦出現(xiàn)，處理機(jī)必須立即予以響應(yīng)和處理。理機(jī)必須立即予以響應(yīng)和處理。 a)后援寄存器技術(shù)后援寄存器技術(shù) 把發(fā)生頁(yè)面失效故障時(shí)指令的全部現(xiàn)場(chǎng)都保把發(fā)生頁(yè)面失效故障時(shí)指令的全部現(xiàn)場(chǎng)都保 存下來(lái)。在處理完故障并把所需要的頁(yè)調(diào)入主存下來(lái)。在處理完故障并把所需要的頁(yè)調(diào)入主 存后，取出后援寄存器的內(nèi)容恢復(fù)故障點(diǎn)現(xiàn)場(chǎng)，存后，取出后援寄存器的內(nèi)容恢復(fù)故障點(diǎn)現(xiàn)場(chǎng)， 然后從故障點(diǎn)處繼續(xù)執(zhí)行完該條指令。然后從故障點(diǎn)處繼續(xù)執(zhí)行完該條指令。 b)預(yù)判技術(shù)預(yù)判技術(shù) 執(zhí)行指令前先預(yù)判操作數(shù)的首尾字符是否都執(zhí)行指令前先預(yù)判操作數(shù)的首

58、尾字符是否都 已在主存中。如果是，才執(zhí)行這條指令；否則已在主存中。如果是，才執(zhí)行這條指令；否則 就發(fā)生頁(yè)面失效，直到調(diào)入該頁(yè)后才開始執(zhí)行就發(fā)生頁(yè)面失效，直到調(diào)入該頁(yè)后才開始執(zhí)行 這條指令。這條指令。 c)替換算法替換算法 不允許出現(xiàn)指令或操作數(shù)跨頁(yè)存儲(chǔ)的那些頁(yè)不允許出現(xiàn)指令或操作數(shù)跨頁(yè)存儲(chǔ)的那些頁(yè) 被輪流從主存中替換出去的被輪流從主存中替換出去的“顛簸顛簸”現(xiàn)象。因此，現(xiàn)象。因此， 給某道程序分配的主存頁(yè)數(shù)應(yīng)該有個(gè)下限。給某道程序分配的主存頁(yè)數(shù)應(yīng)該有個(gè)下限。 d)頁(yè)面大小不能過(guò)大頁(yè)面大小不能過(guò)大 以便多道程序的道數(shù)、每道程序所分配到的以便多道程序的道數(shù)、每道程序所分配到的 主存頁(yè)數(shù)都能在一個(gè)適

59、當(dāng)?shù)姆秶鷥?nèi)。如果頁(yè)面主存頁(yè)數(shù)都能在一個(gè)適當(dāng)?shù)姆秶鷥?nèi)。如果頁(yè)面 過(guò)大，就會(huì)使主存中頁(yè)數(shù)過(guò)少，從而出現(xiàn)大量過(guò)大，就會(huì)使主存中頁(yè)數(shù)過(guò)少，從而出現(xiàn)大量 的頁(yè)面失效，嚴(yán)重降低虛擬存儲(chǔ)器的訪問(wèn)速率的頁(yè)面失效，嚴(yán)重降低虛擬存儲(chǔ)器的訪問(wèn)速率 和等效速度。和等效速度。2.2.提高虛擬存儲(chǔ)器等效訪問(wèn)速度的措施提高虛擬存儲(chǔ)器等效訪問(wèn)速度的措施 根據(jù)根據(jù)虛擬存儲(chǔ)器等效訪問(wèn)速度公式虛擬存儲(chǔ)器等效訪問(wèn)速度公式 TA=HTA1+(1-H)TA2 希望希望H H提高，提高， TA1 ，TA2縮短縮短 關(guān)于高的主存命中率問(wèn)題，其影響因素很多，關(guān)于高的主存命中率問(wèn)題，其影響因素很多，如地址流、頁(yè)面調(diào)度策略、替換算法、頁(yè)面大小如地

60、址流、頁(yè)面調(diào)度策略、替換算法、頁(yè)面大小及分配給程序的頁(yè)數(shù)及分配給程序的頁(yè)數(shù)( (主存容量主存容量) )等。這里主要討等。這里主要討論怎樣縮短訪主存的時(shí)間。論怎樣縮短訪主存的時(shí)間。 從虛擬存儲(chǔ)器工作的全過(guò)程可以看到，每次訪從虛擬存儲(chǔ)器工作的全過(guò)程可以看到，每次訪問(wèn)主存時(shí)，都必須進(jìn)行內(nèi)部地址變換問(wèn)主存時(shí)，都必須進(jìn)行內(nèi)部地址變換(因?yàn)轫?yè)表都因?yàn)轫?yè)表都存在主存中，每次查頁(yè)表就要增加一次訪存。若存在主存中，每次查頁(yè)表就要增加一次訪存。若采用段頁(yè)式虛擬存儲(chǔ)器，查表要增加兩次訪存采用段頁(yè)式虛擬存儲(chǔ)器，查表要增加兩次訪存)，其概率是其概率是100%。從縮短訪主存的時(shí)間來(lái)看，關(guān)。從縮短訪主存的時(shí)間來(lái)看，關(guān)鍵就是