第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)： 段頁式和頁式虛擬存儲(chǔ)器的原理；頁式虛擬存段頁式和頁式虛擬存儲(chǔ)器的原理；頁式虛擬存儲(chǔ)器的地址映像；儲(chǔ)器的地址映像；LRU/FIFO/OPTLRU/FIFO/OPT替換算法進(jìn)行頁替換算法進(jìn)行頁面替換的過程模擬；面替換的過程模擬；LRULRU算法對頁地址流的堆棧算法對頁地址流的堆棧處理模擬及性能分析；處理模擬及性能分析；CacheCache存儲(chǔ)器的直接和組存儲(chǔ)器的直接和組相聯(lián)地址映

2、像；相聯(lián)地址映像；LRULRU替換算法的硬件實(shí)現(xiàn)及替換替換算法的硬件實(shí)現(xiàn)及替換過程模擬；過程模擬；CacheCache存儲(chǔ)器的性能分析等。存儲(chǔ)器的性能分析等。本章難點(diǎn)：本章難點(diǎn)： 段頁式和頁式中虛實(shí)地址的計(jì)算；各種頁面替段頁式和頁式中虛實(shí)地址的計(jì)算；各種頁面替換算法的模擬和頁面命中率的計(jì)算；換算法的模擬和頁面命中率的計(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ǔ)體的字長，單位為：存儲(chǔ)體的字長，單位為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è)方面來描述從下面三個(gè)方面來描述： 1)1)訪問時(shí)間訪問時(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í)間間隔。一般來說是連續(xù)啟動(dòng)一個(gè)存儲(chǔ)體所需要的時(shí)間間隔。一般來說總比總比T TA A大。大。 3)3)存儲(chǔ)器頻寬存儲(chǔ)器頻寬 是指存儲(chǔ)器可以提供的數(shù)據(jù)傳送率，一般用每秒鐘所傳是指存儲(chǔ)器可以提供的數(shù)據(jù)傳送率，一般用每秒鐘所傳送的信息位數(shù)來衡量。送的信息位數(shù)來衡量。 a)a)最大頻寬最大頻寬B BM M( (極限頻寬極限頻寬) ) 是存儲(chǔ)器連續(xù)訪問時(shí)能提供的頻寬。是存儲(chǔ)器連續(xù)訪問時(shí)能提供的頻寬。 單體：單體： 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來表示。具有來表示。具有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 從速度來說，主存遠(yuǎn)遠(yuǎn)跟不上從速度來說，主存遠(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ǔ)器字長存儲(chǔ)器字長W W與與CPUCPU字長字長W W 相同相同, ,一次訪問一個(gè)存儲(chǔ)器一次訪問一個(gè)存儲(chǔ)器 字字, ,主存最大頻寬主存最大頻寬B BM M =W/T =W/TM MW位讀出寄存器讀出寄存器地址寄存器單體單字存儲(chǔ)器單體單字存儲(chǔ)器l 2) 2)單體多字單體多字 存儲(chǔ)器字長等于存儲(chǔ)器字長等于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位單字長寄存器單字長寄存器 3)3)多體單字交叉多體單字交叉總線控制地址寄存器0 地址寄存器1 地址寄存器2地址寄存器3M0M1M2M3主控(主存控制部件) CPUIOP多體多體(m=4)(m=4)交叉存儲(chǔ)器交叉存儲(chǔ)器 a) a)存儲(chǔ)器字長等于存儲(chǔ)器字長等于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ù)總線越長，導(dǎo)致傳輸越高，存儲(chǔ)器數(shù)據(jù)總線越長，導(dǎo)致傳輸 延遲增加；延遲增加； 2)2)系統(tǒng)效率問題，對于順序取指，效率可以系統(tǒng)效率問題，對于順序取指，效率可以 提高提高m m倍，但遇到轉(zhuǎn)移指令，效率就會(huì)下降。倍，但遇到轉(zhuǎn)移指令，效率就會(huì)下降。3.3.模型分析模型分析 對于對于m m個(gè)獨(dú)立分體的主存系統(tǒng)，處理機(jī)發(fā)出一個(gè)獨(dú)立分體的主存系統(tǒng)，處理機(jī)發(fā)出一 串地址為串地址為A A1 1,A,A2 2, A Aq q的訪存申請隊(duì)，在每個(gè)主的訪存申請隊(duì)，在每個(gè)主 存周期到來前，申請隊(duì)被掃描，截取從隊(duì)頭起存周期到來前，申請隊(duì)被掃描，截取從隊(duì)頭起 的的A A1 1,A,A2 2, A A

12、k k的申請序列。申請序列是個(gè)在要的申請序列。申請序列是個(gè)在要 求訪存申請的求訪存申請的k k個(gè)地址中，沒有兩個(gè)或兩個(gè)以上個(gè)地址中，沒有兩個(gè)或兩個(gè)以上 的地址處于同一分體中的最長序列。顯然的地址處于同一分體中的最長序列。顯然k k表示表示 可以同時(shí)訪問的分體個(gè)數(shù)的隨機(jī)變量，不大于可以同時(shí)訪問的分體個(gè)數(shù)的隨機(jī)變量，不大于m m， 系統(tǒng)效率取決于系統(tǒng)效率取決于k k的均值的均值B B，其值越大，可訪問，其值越大，可訪問 的分體個(gè)數(shù)越多，系統(tǒng)效率越高。的分體個(gè)數(shù)越多，系統(tǒng)效率越高。 1)1)數(shù)學(xué)模型數(shù)學(xué)模型 設(shè)設(shè)p(k)p(k)表示申請序列長度為表示申請序列長度為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è)主存周期所訪問的平均字?jǐn)?shù)。而實(shí)際就是每個(gè)主存周期所訪問的平均字?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來提高并行主存系來提高并行主存系統(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)，拉長程序運(yùn)行時(shí)間，也難以使用更度和負(fù)擔(dān)，拉長程序運(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)行。因此主輔存間的地址定位可以改由輔助軟硬件來完成，如圖。的地址定位可以改由輔助軟硬件來完成，如圖。這樣就構(gòu)成了存儲(chǔ)體系，或存儲(chǔ)層次。這樣就構(gòu)成了存儲(chǔ)體系，或存儲(chǔ)層次。主存主存輔存輔存輔助軟硬設(shè)備輔助軟硬設(shè)備從整體來看，從整體來看，速度是主存的速度是主存的容量是輔存的容量是輔存的主存主存輔存存儲(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ī)器指令的地址碼對整統(tǒng)。這樣程序員就可以用機(jī)器指令的地址碼對整個(gè)程序統(tǒng)一編址，這一空間遠(yuǎn)大于實(shí)際主存空間。個(gè)程序統(tǒng)一編址，這一空間遠(yuǎn)大于實(shí)際主存空間。這種指令地址碼稱為虛地址、邏輯地址、程序地這種指令地址碼稱為虛地址、邏輯地址、程序地址等，其對應(yīng)的存儲(chǔ)容量稱為虛存容量或程序空址等，其對應(yīng)的存儲(chǔ)容量稱為虛存容量或程序空間；而實(shí)際主存的地址稱為物理地址、實(shí)間；而實(shí)際主存的地址稱為物理地址、實(shí)( (存存) )地地址，其對應(yīng)的存儲(chǔ)容量稱為主存容量、實(shí)存容量址，其對應(yīng)的

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

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

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

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

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

24、在正在使用的信息在程序空間上相鄰或相近，這是由于指令通常是順序執(zhí)行的。相近，這是由于指令通常是順序執(zhí)行的。 利用程序局部性，可以預(yù)知下一步要訪問的利用程序局部性，可以預(yù)知下一步要訪問的程序塊而在程序塊而在M M1 1中做好準(zhǔn)備。中做好準(zhǔn)備。時(shí)間局部性：存放近期使用過的塊或頁。時(shí)間局部性：存放近期使用過的塊或頁?？臻g局部性：從空間局部性：從M M2 2級把訪問字所在頁或塊一同取級把訪問字所在頁或塊一同取 到到M M1 1中。中。4.1.4 4.1.4 存儲(chǔ)體系的性能參數(shù)存儲(chǔ)體系的性能參數(shù) 以以如圖如圖所示的二級體系所示的二級體系(M(M1 1,M,M2 2) )為例來分析為例來分析 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，使得頁表，使得頁表 中絕大部分行中實(shí)頁號(hào)中絕大部分行中實(shí)頁號(hào)n nv v字段及其它字段都不字段及其它字段都不 再有用了，這就會(huì)大大降低頁表的空間利用率。再有用了，這就會(huì)大大降低頁表的空間利用率。 c)解決辦法解決辦法 將頁表中裝入位為將頁表中裝入位為0的行用實(shí)頁號(hào)的行用實(shí)頁號(hào)n nv v字段存放字段存放該程序此虛頁在輔存中的實(shí)地址，以便調(diào)頁時(shí)該程序此虛頁在輔存中的

26、實(shí)地址，以便調(diào)頁時(shí)實(shí)現(xiàn)用戶虛頁號(hào)到輔存實(shí)地址的變換。實(shí)現(xiàn)用戶虛頁號(hào)到輔存實(shí)地址的變換。 相聯(lián)目錄表法相聯(lián)目錄表法: :把頁表壓縮成只存放已裝入主把頁表壓縮成只存放已裝入主存的那些虛頁存的那些虛頁( (用基號(hào)用基號(hào)b b和和N Nv v標(biāo)識(shí)標(biāo)識(shí)) )與實(shí)頁位置與實(shí)頁位置(n(nv v) )的對應(yīng)關(guān)系。這樣該表最多為的對應(yīng)關(guān)系。這樣該表最多為2 2n nv v行，簡稱行，簡稱為目錄表法，采用按內(nèi)容訪問的相聯(lián)存儲(chǔ)器構(gòu)為目錄表法，采用按內(nèi)容訪問的相聯(lián)存儲(chǔ)器構(gòu)成。成。如下圖：如下圖：基號(hào)基號(hào)用戶虛頁號(hào)用戶虛頁號(hào)頁內(nèi)位移頁內(nèi)位移某用戶虛地址某用戶虛地址基號(hào)用戶基號(hào)用戶 虛頁號(hào)虛頁號(hào)實(shí)頁號(hào)實(shí)頁號(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è)單元對應(yīng)的虛頁號(hào)字段內(nèi)容比較進(jìn)行個(gè)單元對應(yīng)的虛頁號(hào)字段內(nèi)容比較進(jìn)行 相聯(lián)查找。如有相符的即相聯(lián)查找到時(shí)，表示此相聯(lián)查找。如有相符的即相聯(lián)查找到時(shí)，表示此 虛頁已裝入主存，該單元存放的實(shí)頁號(hào)虛頁已裝入主存，該單元存放的實(shí)頁號(hào)n nv v就是此就是此 虛頁所存放的實(shí)頁位置，將其讀出拼接

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

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

30、映 像關(guān)系，用于內(nèi)部地址變換。像關(guān)系，用于內(nèi)部地址變換。 由于虛擬存儲(chǔ)器的頁面失效率很低，很少調(diào)用由于虛擬存儲(chǔ)器的頁面失效率很低，很少調(diào)用 外頁表進(jìn)行地址變換，因此外頁表存放在輔存中，外頁表進(jìn)行地址變換，因此外頁表存放在輔存中， 當(dāng)某道程序初始運(yùn)行時(shí)，才把外頁表的內(nèi)容轉(zhuǎn)錄當(dāng)某道程序初始運(yùn)行時(shí)，才把外頁表的內(nèi)容轉(zhuǎn)錄 到已建立內(nèi)頁表的實(shí)頁號(hào)地址字段中，這也是前到已建立內(nèi)頁表的實(shí)頁號(hào)地址字段中，這也是前 述當(dāng)內(nèi)頁表裝入位為述當(dāng)內(nèi)頁表裝入位為0時(shí)讓實(shí)頁號(hào)地址字段改放時(shí)讓實(shí)頁號(hào)地址字段改放 該虛頁在輔存中的實(shí)地址的原因。而且對外頁表該虛頁在輔存中的實(shí)地址的原因。而且對外頁表 速度要求低，可以用軟件實(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)) )已裝入已裝入外頁表外頁表虛地址到輔存實(shí)地址的變換虛地址到輔存實(shí)地址的變換2Nv2.替換算法替換算法 1)解決問題解決問題 當(dāng)處理機(jī)要用到的指令或數(shù)據(jù)不在主存中時(shí)，當(dāng)處理機(jī)要用到的指令或數(shù)據(jù)不在主存中時(shí)， 就會(huì)產(chǎn)生頁面失效，應(yīng)去輔存中將包含該指令就會(huì)產(chǎn)生頁面失效，應(yīng)去輔存中將包含該指令 或數(shù)據(jù)的一頁調(diào)入主存。由于虛存空間比主存或數(shù)據(jù)的一頁調(diào)入

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

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

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

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

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

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

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

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

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

41、讓程序運(yùn)行一遍得到實(shí)際的頁地址流，然，這只有讓程序運(yùn)行一遍得到實(shí)際的頁地址流， 才能找到為實(shí)現(xiàn)這種替換算法所需要的各頁使用才能找到為實(shí)現(xiàn)這種替換算法所需要的各頁使用 信息，這是不現(xiàn)實(shí)的。所以，優(yōu)化替換算法只是信息，這是不現(xiàn)實(shí)的。所以，優(yōu)化替換算法只是 一種理想化的算法，它可以被用作評價(jià)其它替換一種理想化的算法，它可以被用作評價(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頁，執(zhí)行時(shí)的頁，執(zhí)行時(shí)的 頁地址流頁地址流( (即執(zhí)行時(shí)依次使用到的程序頁頁號(hào)即執(zhí)行時(shí)依次使用到的程序頁頁號(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頁，如下圖表示分頁，如下圖表示分別用別用FIFO,LRU,OPT3FIFO,LRU,OPT3種替換算法對這種替換算法對這3 3頁的使用頁的使用和替換過程。和替換過程。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次次頁地址流頁地址流 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種替換算法對同一頁地址流的替換過程種替換算法對同一頁地址流的替換過程 b)命中率與頁地址流有關(guān)命中率與頁地址流有關(guān) 例如例如一個(gè)循環(huán)程序，當(dāng)所需頁數(shù)大于分配給一個(gè)循環(huán)程序，當(dāng)所需頁數(shù)大于分配給 它的主存頁數(shù)時(shí)，無論是它的主存頁數(shù)時(shí)，無論是FIFO還是還是LRU算法的算法的 命中率都明顯低于命中率都明顯低于OPT的。的。如下圖如下圖所示，所示，LRU 和和FIFO一次都沒有命中，因?yàn)樗『每偸菍ⅠR一次都沒

45、有命中，因?yàn)樗『每偸菍ⅠR 上要用到的頁面給替換出去了，從而連續(xù)不斷上要用到的頁面給替換出去了，從而連續(xù)不斷 的出現(xiàn)頁面失效，產(chǎn)生所謂的的出現(xiàn)頁面失效，產(chǎn)生所謂的顛簸現(xiàn)象顛簸現(xiàn)象。 1* *2312142* *3413* *4* *1231* *2342* * FIFO無命中無命中121121 LRU無命中無命中 OPT命中命中3次次頁地址流頁地址流 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命中命中 命中率與頁地址流有關(guān)命中率與頁地址流有關(guān)124* *1* *2342* *3413* *

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

47、給該道程序的主存頁數(shù)的增加，命中率一般配給該道程序的主存頁數(shù)的增加，命中率一般都會(huì)得到提高，至少不會(huì)降低。都會(huì)得到提高，至少不會(huì)降低。121* *21413* *4* *1251* *251* *2命中命中51* *2命中命中532* *5* *345* *34命中命中 n=3命中命中3次次12121 n=4命中命中2次次頁地址流頁地址流 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í)頁數(shù)增加，命中率反而有可能下降法的實(shí)頁數(shù)增加，命中率反而有可能下降 5)堆棧型替換算法堆棧型替換算法 a)定義定義 A A：長度為：長度為L的任意一個(gè)頁面地址流的任意一個(gè)頁面地址流 t： 已處理過已處理過t1個(gè)頁面的時(shí)間點(diǎn)個(gè)頁面的時(shí)間點(diǎn) n：分配給該地址流的主存頁面數(shù)：分配給該地址流的主存頁面數(shù) Bt(n)：在：在t時(shí)間點(diǎn)、在時(shí)間點(diǎn)、在n頁的主存中的頁面集合頁的主存中的頁面集合 Lt：到：到t時(shí)刻已遇到的地址流中相異頁的頁數(shù)時(shí)刻已遇到的地址流中相異頁的頁數(shù) 若若 n= Lt時(shí)，時(shí)， Bt(n1) = Bt(n) 成立，則此替成立，則此替換算法屬于堆棧型的替換算法。換算法

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

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

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

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

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

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

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

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

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

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

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

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