第4章存貯體系

1、第 4 章 存 貯 體 系 第第 4 章章 存存 貯貯 體體 系系 4.1 存貯體系的形成與性能存貯體系的形成與性能 4.2 虛擬存貯器虛擬存貯器 4.3 高速緩沖存貯器高速緩沖存貯器(Cache) 4.4 主存保護主存保護 第 4 章 存 貯 體 系 主要內容：存貯器的存貯層次虛擬存貯系統高速緩沖存貯器Cache多級層次的原理和結構進行討論、分析和評價地址映象及變換方法替換算法Cache的透明性第 4 章 存 貯 體 系 目的： 掌握存儲體系的基本的分析、設計方法 儲器是計算機的核心部件之一。其性能直接關系到整個計算機系統性能的高低。如何以合理的價格，設計出容量和速度滿足計算機系統要求的存儲

2、器系統，始終是計算機體系結構設計中的關鍵問題之一。 計算機軟件設計者和計算機用戶對于存儲器容量的需求是無止境的，他們希望容量越大越好，而且速度還要快，價格要便宜。僅用單一的一種存儲器是很難達到這一目標的。較好的方法是采用存儲層次，用多種存儲器構成存儲器的層次結構。 第 4 章 存 貯 體 系 4.1 存貯體系的形成與性能存貯體系的形成與性能 4.1.1 發(fā)展存貯體系的必要性發(fā)展存貯體系的必要性1.存貯器的性能要求存貯器的性能要求 1)大容量大容量 2)高速度高速度 3)低價格低價格 存貯器容量SM=Wlm。其中，W為存貯體的字長(單位為位或字節(jié))， l為每個存貯體的字數， m為并行工作的存貯體

3、個數。 第 4 章 存 貯 體 系 存貯器的速度可以用訪問時間TA、存貯周期TM和頻寬(也稱帶寬)Bm來描述。TA是存貯器從接到訪存讀申請，到信息被讀到數據總線上所需的時間。這是確定處理機與存貯器時間關系的一個重要指標。這段時間是處理機在啟動訪存申請后必須等待的時間。TM則是連續(xù)啟動一個存貯體所需要的間隔時間，它一般總比TA大。存貯器頻寬是存貯器可提供的數據傳送速率，一般用每秒鐘傳送的信息位數(或字節(jié)數)來衡量，又分最大頻寬(或稱極限頻寬)和實際頻寬。最大頻寬Bm是存貯器連續(xù)訪問時能提供的頻寬。單體的Bm=W/TM。m個存貯體并行工作時可達到的最大頻寬Bm=Wm/TM。由于存貯器不一定總能連續(xù)

4、滿負荷地工作， 所以，實際頻寬往往要低于最大頻寬。 第 4 章 存 貯 體 系 存貯器的價格可以用總價格C或每位價格c來表示。具有SM位的存貯器每位價格c=C/SM。存貯器價格包含了存貯單元本身及為該存貯器操作所必須的外圍電路的價格。 計算機系統總希望存貯器能在盡可能低的價格下，提供盡量高的速度和盡量大的存貯容量。在速度上應盡量和CPU匹配，否則CPU的高速性能難以發(fā)揮。容量上應盡可能放得下所有系統軟件及多個用戶軟件。同時，存貯器的價格又只能占整個計算機系統硬件價格中一個較小而合理的比例。然而，價格、速度和容量的要求是互相矛盾的。在存貯器件一定的條件下，容量越大，因其延遲增大而使速度越低。容量

5、越大，存貯器總價格當然也就會越大。 存取速度越高，價格也將越高。同等容量的情況下存貯器的速度大體上按雙極型、MOS型、電荷耦合器件(CCD)、 磁泡、 定頭磁盤、 動頭磁盤、 磁帶的順序依次下降。 第 4 章 存 貯 體 系 2.容量 SM=W l m W：存貯體的字長，單位為bit或Byte。 l：每個存貯體的字數。 m：并行工作的存貯體的個數。 3.速度 從下面三個方面來描述： 1)訪問時間TA TA是存貯器接到訪存到信息被讀到數據總線上 所需的時間。是確定CPU與存貯器時間關系的重 要指標。第 4 章 存 貯 體 系 2)存貯周期TM TM是連續(xù)啟動一個存貯體所需要的時間間隔。一般來說總

6、比TA大。 3)存貯器頻寬 是指存貯器可以提供的數據傳送率，一般用每秒鐘所傳送的信息位數來衡量。 a)最大頻寬BM(極限頻寬) 是存貯器連續(xù)訪問時能提供的頻寬。 單體： BM =W/TM m體并行工作：BM =mW/TM b)實際頻寬 實際頻寬小于最大頻寬BM 第 4 章 存 貯 體 系 4.結論結論 由于存貯器的價格、速度和容量的要求是由于存貯器的價格、速度和容量的要求是矛盾的，為了同時滿足三方面的要求，在一個矛盾的，為了同時滿足三方面的要求，在一個完整的存貯體系中，完整的存貯體系中，必須采用不同工藝的存貯器，使得信息以各種必須采用不同工藝的存貯器，使得信息以各種方式分布于不同的存貯體。方式

7、分布于不同的存貯體。第 4 章 存 貯 體 系 比如： 主存 當前活躍的信息，快，少 輔存 暫時不用的信息，慢，多 虛存 swap 從速度來說，主存遠遠跟不上CPU的要求，為 了彌補這一差距，特引入并行和重疊技術，構 成并行主存系統，但這種并行主存的方法提高 頻寬是有限的，因此還需從系統結構入手，發(fā) 展存貯體系。第 4 章 存 貯 體 系 4.1.2并行主存系統頻寬的分析 1.類型 1)單體單字 存貯器字長W與CPU字長W 相同,一次訪問一個存貯器 字,主存最大頻寬BM =W/TMW位讀出寄存器讀出寄存器地址寄存器單體單字存貯器單體單字存貯器l第 4 章 存 貯 體 系 圖4.1是一個字長為W

8、位的單體主存，一次可以訪問一個存貯器字，所以主存最大頻寬Bm=W/TM。假設，此存貯器字長W與CPU所要訪問的字(數據字或指令字，簡稱CPU字)的字長W相同， 則CPU從主存獲得信息的速率就為W/TM。我們稱這種主存是單體單字存貯器。 第 4 章 存 貯 體 系 提高主存帶寬的措施主要有提高主存帶寬的措施主要有：1.增加存儲器的數據寬度。(也就是增加數據位數) 單體多字 2.采用存儲器的多體交叉技術。第 4 章 存 貯 體 系 要想提高主存頻寬Bm，使之與CPU速度匹配，顯然可以想到，在同樣的器件條件(即同樣的TM)下，只有設法提高存貯器的字長W才行。 例如，改用圖4.2的方式組成，這樣，主存

9、在一個存貯周期內就可以讀出4個CPU字， 相當于CPU從主存中獲得信息的最大速率提高到原來的4倍，即Bm=4W/TM。我們稱這種主存為單體多字存貯器。第 4 章 存 貯 體 系 2)單體多字 存貯器字長等于m個 CPU字,BM =mW/TM W位W位W位W位地址寄存器單體多字單體多字(m=4)(m=4)存貯器存貯器 W位單字長寄存器單字長寄存器第 4 章 存 貯 體 系 邏輯實現：邏輯實現：把地址碼分成兩個部分， 一部分仍作為存儲器的地址 另一部分負責從m個數據中選擇一個數據 第 4 章 存 貯 體 系 圖 4.3 多體(m=4)交叉存貯器 總線控制地址寄存器0 地址寄存器1 地址寄存器2地址

10、寄存器3M0M1M2M3主控(主存控制部件) CPUIOP3)多體單字交叉多體單字交叉第 4 章 存 貯 體 系 存儲器的每個存儲單元都要給定一個地址才能被訪問到。并行存儲器是由多個存儲體組成，并行存取可以加快存取速度，但是這和編址方法有關。 比如主存空間有8個存儲單元，那么整個存儲空間地址就由一組3位二進制數組成：從000到111， 如果這個空間用兩個存儲體實現，有兩種編址方法。 第 4 章 存 貯 體 系 一種是高位交叉編址，就是把地址的碼的前一位數分配給兩個存儲體，第一個為0，第二個為1(如果有四個存儲體的話，就要分給前面的兩位數，依次類推)第一個存儲體里面的單元就是以這個碼開始的編碼：

11、000，001，010，011 (第一位數都是0)；第二個存儲體的存儲單元的四個地址是：100，101，110，111。第 4 章 存 貯 體 系 這樣，當訪問兩個地址相鄰存儲單元的數據時，比如110和111兩個單元的數據，都放在第二個存儲體中，只能在這個體中存取，而第一個存儲體就閑著沒人訪問了。而一般在存放數據時，多是將數據存放在地址連續(xù)的內存區(qū)域中的。所以：高位交叉編址的存儲器適合于多機系統，就是說，因為各處理機通常訪問各自所需的數據，這些數據放在不同的存儲體中時，兩個存儲器可以同時工作，也就加快了速度。 第 4 章 存 貯 體 系 另一種方法就是低位交叉編址。如上的例子，地址碼的最后一位

12、就是分配給存儲體的地址碼，第一個存儲器里的存儲單元就是000，010，100，110(最后一位總是0)， 第二個存儲器里的存儲單元就是001，011，101，111，這種方法使得相鄰地址的存儲單元分布在不同的存儲體中，所以在訪問相鄰單元的數據時，多個并行存儲體可以同時工作進行存取，因此比較適于單處理機內的高速數據存取。 第 4 章 存 貯 體 系 具體實現方法：具體實現方法：高位交叉訪問存儲器高位交叉訪問存儲器 實現方法：實現方法：用地址碼的高位部分區(qū)分存儲體號 參數計算方法參數計算方法n：每個存儲體的容量，地址碼的低log2 n位為體內地址m：總共的存儲體個數，地址碼的高log2 m位控制各

13、個存儲體工作j：存儲體的體內地址，j0，1，2，.，n-1k：存儲體的體號，k0，1，2，.，m-1存儲器的地址：存儲器的地址：Ankj存儲器的體內地址：存儲器的體內地址：A mod n。Am。第 4 章 存 貯 體 系 第 4 章 存 貯 體 系 第 4 章 存 貯 體 系 4) 4)多體多字交叉多體多字交叉 多個存貯體，每個存貯體有多個存貯體，每個存貯體有CPUCPU字。字。 上述能并行讀出多個上述能并行讀出多個CPUCPU字的單體多字和多體字的單體多字和多體單字或多體多字的交叉存貯主存系統統稱為單字或多體多字的交叉存貯主存系統統稱為并行并行主存系統主存系統。第 4 章 存 貯 體 系 2

14、.2.分析分析 提高提高m m值，可以提高主存系統的最大頻率，但值，可以提高主存系統的最大頻率，但并不能線性提高實際頻率。并不能線性提高實際頻率。 原因：原因： 1)1)模模m m越高，存貯器數據總線越長，導致傳輸越高，存貯器數據總線越長，導致傳輸 延遲增加；延遲增加； 2)2)系統效率問題，對于順序取指，效率可以系統效率問題，對于順序取指，效率可以 提高提高m m倍，但遇到轉移指令，效率就會下降。倍，但遇到轉移指令，效率就會下降。第 4 章 存 貯 體 系 m個存儲體分時啟動個存儲體分時啟動實際上是一種采用流水線方式工作的并行存儲器理論上，存儲器的速度可望提高m倍每存儲體的啟動間隔為：tmT

15、m其中： Tm為每個存儲體的訪問周期, m為存儲體個數。 第 4 章 存 貯 體 系 圖 4.4 4個分體分時啟動的時間關系 第 4 章 存 貯 體 系 3.3.模型分析模型分析 對于對于m m個獨立分體的主存系統，處理機發(fā)出一個獨立分體的主存系統，處理機發(fā)出一 串地址為串地址為A A1 1,A,A2 2, , A Aq q的訪存申請隊，在每個主的訪存申請隊，在每個主 存周期到來前，申請隊被掃描，截取從隊頭起存周期到來前，申請隊被掃描，截取從隊頭起 的的A A1 1,A,A2 2, , A Ak k的申請序列。申請序列是個在要的申請序列。申請序列是個在要 求訪存申請的求訪存申請的k k個地址中

16、，沒有兩個或兩個以上個地址中，沒有兩個或兩個以上 的地址處于同一分體中的最長序列。顯然的地址處于同一分體中的最長序列。顯然k k表示表示 可以同時訪問的分體個數的隨機變量，不大于可以同時訪問的分體個數的隨機變量，不大于m m， 系統效率取決于系統效率取決于k k的均值的均值B B，其值越大，可訪問，其值越大，可訪問 的分體個數越多，系統效率越高。的分體個數越多，系統效率越高。第 4 章 存 貯 體 系 設p(k)表示申請序列長度為k的概率密度函數，其中k=1, 2, ， m。 即p(1)是k=1的概率，p(2)是k=2的概率，p(m)是k=m的概率。 k的平均值用B表示，則 mkkpkB1)(

17、 它實際上就是每個主存周期所能訪問到的平均字數，正比于主存實際頻寬。p(k)與程序的狀態(tài)密切相關，如果訪存申請隊都是指令的話，那么影響最大的是轉移概率，它定義為給定指令的下條指令地址為非順序地址的概率。 第 4 章 存 貯 體 系 申請隊中如果第一條就是轉移指令且轉移成功，與第一條指令并行讀出的其他m-1條指令就是沒用的，相當于k=1，所以p(1)=(1-)0；k=2的概率自然是第一條沒有轉移(其概率為1-)，第二條是轉移指令且轉移成功的情況，所以，p(2)=(1-p(1)=(1-)1；同理，p(3)=(1-p(1)-p(2)=(1-)2。如此類推，p(k)=(1-)k-1，其中1km。如果前

18、m-1條均不轉移，則不管第m條是否轉移，k都等于m，故p(m)=(1-)m-1。 第 4 章 存 貯 體 系 這樣， 1221)1 ()1)(1()1 (3)1 (21)(mmmkmmkpkB經數學歸納法化簡可得 10)1 (miiB這是一個等比級數， 因此 mB)1 (1第 4 章 存 貯 體 系 分析：p772)討論：討論： a)若每條指令都是轉移指令且轉移成功，即若每條指令都是轉移指令且轉移成功，即p=1,則則B=1，就是并行多體交叉存取的實際頻寬，就是并行多體交叉存取的實際頻寬降到和單體單字一樣；降到和單體單字一樣； b)若所有指令都不轉移，即若所有指令都不轉移，即p=0，則，則B=m

19、，此時，此時多體交叉存貯的效率最高。多體交叉存貯的效率最高。3)結論結論 由于程序的轉移概率不會很低，數據分布的離由于程序的轉移概率不會很低，數據分布的離散性較大，所以單純靠增大散性較大，所以單純靠增大m來提高并行主存系來提高并行主存系統的頻寬是有限的，而且性價比還會隨統的頻寬是有限的，而且性價比還會隨m的增大的增大而下降。如果采用并行主存系統仍不能滿足速度而下降。如果采用并行主存系統仍不能滿足速度上的要求，就必須從系統結構上改進，采用存貯上的要求，就必須從系統結構上改進，采用存貯體系。體系。訪問數據比取指令的沖突更為嚴重第 4 章 存 貯 體 系 4.1.3 存貯體系的形成與分支存貯體系的形

20、成與分支 形成及發(fā)展 一、形成為解決同一種存貯器的價格、容量及速度間的矛盾，利用多種存貯器 二、發(fā)展 第 4 章 存 貯 體 系 1早期主存。外存（輔存）則作為外設的一部分兩者沒有關系，內存分配、程序調度、覆蓋均由程序員完成，兩者構成存貯系統但不是存貯體系 2I/O處理機的出現I/O處理機可與CPU進行并行操作，以提高機器的吞吐量第 4 章 存 貯 體 系 3多道程序、監(jiān)控程序、OS發(fā)展地址變換、程序定位由OS完成，形成主存輔存層次 形成“虛擬存貯系統”概念性要求：把主、輔統一成一個整體，速度接近主存，容量接近輔存 “主輔”層次 彌補容量不足速度問題第 4 章 存 貯 體 系 4速度問題 一個

21、數量級（主存與CPU）解決方法 1）設置通用寄存器問題：主存寄存器數據交換由程序員完成，數目過多編譯復雜化 2）并行多體交叉存貯器問題：因指令有轉移第 4 章 存 貯 體 系 進一步存貯層次 Cache 完全由硬件實現 速度接近Cache，容量接近主存 “Cache主存”層次 彌補速度不足第 4 章 存 貯 體 系 采用多種存貯器 構成存貯器層次、軟硬結合等僅采用一種工藝的單一存貯器是行不通的從速度上：必須從系統結構采取措施從容量上：主存容量在相當快的擴大 主存容量的增大程序的不斷擴大 在系統結構上采用“主存和輔存”結構第 4 章 存 貯 體 系 圖 4.6 主存輔存存貯層次 第 4 章 存

22、貯 體 系 Cache主存存貯層次 通過在CPU與主存間加一級速度高、容量小、每個價格較高的高速緩沖存貯器(Cache)，借助于硬件是Cache和主存構成一個整體。信息在Cache與主存間的傳送全部由硬件完成，所以Cache對應用程序員和系統程序員都是透明的。高速緩沖高速緩沖 CacheCache 主主 存存 M M輔助硬件輔助硬件CPUCPU從從CPUCPU來看，來看，速度是速度是Cache的的容量是主存的容量是主存的第 4 章 存 貯 體 系 “Cache-主存主存”“主存主存-輔存輔存”目目 的的為了彌補主存速度為了彌補主存速度的不足的不足 為了彌補主存容量的不為了彌補主存容量的不足足存

23、儲管理實現存儲管理實現全部由專用硬件實全部由專用硬件實現現主要由軟件實現主要由軟件實現訪問速度的比值訪問速度的比值（第一級比第二級）（第一級比第二級）大小大小幾比一幾比一 幾百比一幾百比一 典型的塊（頁）典型的塊（頁）幾十個字節(jié)幾十個字節(jié)幾百到幾千個字節(jié)幾百到幾千個字節(jié) CPU對第二級的對第二級的訪問方式訪問方式 可直接訪問可直接訪問均通過第一級均通過第一級失效時失效時CPU是否切換是否切換不切換不切換 切換到其它進程切換到其它進程 第 4 章 存 貯 體 系 多級存貯層次 從M1到Mn，速度變慢，容量增大，價格降低。CPUCPUM M1 1M M2 2M M3 3M Mn n從從CPU來看，

24、來看，速度是速度是M M1 1的，的，容量是容量是M Mn n的，的，價格價格是M Mn n的第 4 章 存 貯 體 系 4.1.4 存貯體系的性能參數存貯體系的性能參數 圖 4.9 二級存貯體系的評價 以如圖所示的二級體系(M1,M2)為例來分析 1.存貯體系的每位 平均價格c c1 SM1 +c2 SM2 SM1 +SM2 1)M2容量大且便宜，所以， SM12nv，使得頁表 中絕大部分行中實頁號nv字段及其它字段都不 再有用了，這就會大大降低頁表的空間利用率。第 4 章 存 貯 體 系 c)解決辦法 將頁表中裝入位為0的行用實頁號nv字段存放該程序此虛頁在輔存中的實地址，以便調頁時實現用

25、戶虛頁號到輔存實地址的變換。 相聯目錄表法:把頁表壓縮成只存放已裝入主存的那些虛頁(用基號b和Nv標識)與實頁位置(nv)的對應關系。這樣該表最多為2nv行，簡稱為目錄表法，采用按內容訪問的相聯存貯器構成。如下圖：第 4 章 存 貯 體 系 基號基號用戶虛頁號用戶虛頁號頁內位移頁內位移某用戶虛地址某用戶虛地址基號用戶基號用戶 虛頁號虛頁號實頁號實頁號其它其它信息信息目錄表目錄表( (存在相聯存貯器中存在相聯存貯器中) )相聯比較相聯比較查找到查找到目錄表法目錄表法NvbNrnvnvnr(Nr)npb+Nv2 2n nv v行行第 4 章 存 貯 體 系 d)相聯存貯器 在一個存貯周期內能將給定

26、的Nv同時與目錄表 的全部2nv個單元對應的虛頁號字段內容比較進行 相聯查找。如有相符的即相聯查找到時，表示此 虛頁已裝入主存，該單元存放的實頁號nv就是此 虛頁所存放的實頁位置，將其讀出拼接上Nr就可 形成訪存實地址np；如無相符的即相聯查找不到， 表示此虛頁未裝入主存，發(fā)生頁面失效，請求從 輔存中調頁。由此可見，采用目錄表法不用設置 裝入位了。第 4 章 存 貯 體 系 6)虛頁的調入虛頁的調入 當發(fā)生頁面失效時，要想把該道程序的虛頁當發(fā)生頁面失效時，要想把該道程序的虛頁 調入主存，必須給出該頁在輔存中的實際地址。調入主存，必須給出該頁在輔存中的實際地址。 為了提高調頁效率，輔存一般是按信

27、息塊編址為了提高調頁效率，輔存一般是按信息塊編址 的，且塊的大小等于頁面大小。以磁盤為例，的，且塊的大小等于頁面大小。以磁盤為例， 輔存實輔存實( (塊塊) )地址格式地址格式NvNvd d為：為： 這樣就需要將多用戶虛頁號這樣就需要將多用戶虛頁號N Nv v變換成輔存實變換成輔存實 地址地址NvNvd d 。磁盤號磁盤號柱面號柱面號磁頭號磁頭號塊塊 號號NvNvd d第 4 章 存 貯 體 系 外頁表外頁表:存放用戶虛頁號存放用戶虛頁號N Nv v與輔存實地址與輔存實地址NvNvd d的的 映像關系，用于外部地址變換。映像關系，用于外部地址變換。 內頁表內頁表:存放用戶虛頁號存放用戶虛頁號N

28、 Nv v與主存實頁號與主存實頁號n nv v的映的映 像關系，用于內部地址變換。像關系，用于內部地址變換。 由于虛擬存貯器的頁面失效率很低，很少調用由于虛擬存貯器的頁面失效率很低，很少調用 外頁表進行地址變換，因此外頁表存放在輔存中，外頁表進行地址變換，因此外頁表存放在輔存中， 當某道程序初始運行時，才把外頁表的內容轉錄當某道程序初始運行時，才把外頁表的內容轉錄 到已建立內頁表的實頁號地址字段中，這也是前到已建立內頁表的實頁號地址字段中，這也是前 述當內頁表裝入位為述當內頁表裝入位為0時讓實頁號地址字段改放時讓實頁號地址字段改放 該虛頁在輔存中的實地址的原因。而且對外頁表該虛頁在輔存中的實地

29、址的原因。而且對外頁表 速度要求低，可以用軟件實現。如下圖：速度要求低，可以用軟件實現。如下圖：第 4 章 存 貯 體 系 磁盤號磁盤號柱面號柱面號 磁頭號磁頭號 塊號塊號NvNvd d多用戶虛地址多用戶虛地址輔存地址輔存地址NrNSuNvNvNvd d1 1裝入位裝入位輔存實地址輔存實地址 地址變換地址變換( (軟件實現軟件實現) )已裝入已裝入外頁表外頁表虛地址到輔存實地址的變換虛地址到輔存實地址的變換2Nv第 4 章 存 貯 體 系 2.替換算法替換算法 1)解決問題解決問題 當處理機要用到的指令或數據不在主存中時，當處理機要用到的指令或數據不在主存中時， 就會產生頁面失效，應去輔存中將

30、包含該指令就會產生頁面失效，應去輔存中將包含該指令 或數據的一頁調入主存。由于虛存空間比主存或數據的一頁調入主存。由于虛存空間比主存 空間大得多，必然會出現主存頁面位置已全被空間大得多，必然會出現主存頁面位置已全被 占用后又發(fā)生頁面失效，這時再將輔存中的一占用后又發(fā)生頁面失效，這時再將輔存中的一 頁調入主存時就發(fā)生頁面爭用。只用強制騰出頁調入主存時就發(fā)生頁面爭用。只用強制騰出 主存中某頁后才能接納從輔存調來的新頁。具主存中某頁后才能接納從輔存調來的新頁。具 體選擇主存中哪一頁作為被替換的頁，就是替體選擇主存中哪一頁作為被替換的頁，就是替 換算法要解決的問題。換算法要解決的問題。第 4 章 存

31、貯 體 系 2)原則原則 a)有高的主存命中率有高的主存命中率 b)算法便于實現算法便于實現 c)輔助軟、硬件成本盡量低輔助軟、硬件成本盡量低 3)常用算法常用算法 a)隨機算法隨機算法( (Random,RAND) ) 用軟的或硬的隨機數產生器來形成主存中要用軟的或硬的隨機數產生器來形成主存中要被替換頁的頁號。這種算法簡單，易于實現，被替換頁的頁號。這種算法簡單，易于實現，但沒有利用主存使用情況的歷史信息，反映不但沒有利用主存使用情況的歷史信息，反映不了程序的局部性，使主存命中率低，很少采用。了程序的局部性，使主存命中率低，很少采用。 第 4 章 存 貯 體 系 b)先進先出算法先進先出算法

32、(First In First Out,FIFO) 選擇最早裝入的頁作為被替換的頁。這種算法選擇最早裝入的頁作為被替換的頁。這種算法 實現方便，雖然利用了主存使用情況的歷史信息，實現方便，雖然利用了主存使用情況的歷史信息， 但是不一定能正確反映出程序的局部性，因為最但是不一定能正確反映出程序的局部性，因為最 先進入的頁很可能是現在經常要用到的頁先進入的頁很可能是現在經常要用到的頁。 實頁號實頁號 占用位占用位 程序號程序號 段頁號段頁號 計數器計數器(使用位使用位)程序優(yōu)先位程序優(yōu)先位 HS其它信息其它信息012nv-1主存頁面表主存頁面表第 4 章 存 貯 體 系 c)近期最少使用算法近期最

33、少使用算法(Least Recently Used, ,LRU) ) 選擇近期最少訪問的頁作為被替換的頁。這種選擇近期最少訪問的頁作為被替換的頁。這種 算法能比較正確的反映程序的局部性，因為當前算法能比較正確的反映程序的局部性，因為當前 最少使用的頁一般來說未來也將很少訪問，但完最少使用的頁一般來說未來也將很少訪問，但完 全按此算法實現比較困難，需要為每個實頁都配全按此算法實現比較困難，需要為每個實頁都配 置一個字長很長的計數器字段才行。所以一般采置一個字長很長的計數器字段才行。所以一般采 用它的變形，即近期最久沒被訪問過的頁作為被用它的變形，即近期最久沒被訪問過的頁作為被 替換的頁。這樣把替

34、換的頁。這樣把“多多”和和“少少”簡化成簡化成“有有”和和“無無” 之后，實現起來比較方便。之后，實現起來比較方便。第 4 章 存 貯 體 系 主存頁面表主存頁面表 OS為實現主存管理而設置的，是對主存而言為實現主存管理而設置的，是對主存而言 的，整個主存只有一個。每一行用來記錄主存中的，整個主存只有一個。每一行用來記錄主存中 各頁的使用狀況。而頁表是對程序空間而言的，各頁的使用狀況。而頁表是對程序空間而言的， 每道程序都有一個，是用來存貯地址映像關系和每道程序都有一個，是用來存貯地址映像關系和 實現地址變換的。實現地址變換的。 實頁號實頁號:主存頁號是順序的，可以省略主存頁號是順序的，可以省

35、略 占用位占用位:表示該主存頁面是否被占用表示該主存頁面是否被占用 程序號程序號/段頁號段頁號:該主存頁被哪道程序的哪段該主存頁被哪道程序的哪段 哪頁占用哪頁占用 使用位使用位:表示該主存頁近期是否被使用過表示該主存頁近期是否被使用過 第 4 章 存 貯 體 系 開始時所有頁的使用位全為開始時所有頁的使用位全為“0”0”，只要某個頁，只要某個頁的的 任何單元被訪問過，硬件就自動將該頁使用位置任何單元被訪問過，硬件就自動將該頁使用位置 “ “1”1”。由于采用全相聯映像，調入頁可進入對。由于采用全相聯映像，調入頁可進入對應應 于主存頁面表中任何占用位為于主存頁面表中任何占用位為“0”0”的實頁位

36、置，的實頁位置， 一旦裝入主存某實頁上，就置該實頁的占用位為一旦裝入主存某實頁上，就置該實頁的占用位為 “ “1”1”。只有當所有占用位都是。只有當所有占用位都是1 1且又發(fā)生頁面失且又發(fā)生頁面失效效 時才有頁面替換問題，這時就要用到使用位，只時才有頁面替換問題，這時就要用到使用位，只 需替換使用位為需替換使用位為“0”0”的頁即可。的頁即可。第 4 章 存 貯 體 系 使用位全使用位全“1 ”處理處理 一種辦法是由硬件強制全部使用位都為一種辦法是由硬件強制全部使用位都為“0”。 從概念上看，近期最少使用的從概念上看，近期最少使用的“期期”是從上次使用是從上次使用 位全位全0到這次使用位全到這

37、次使用位全0的這段時間。由于這個期的這段時間。由于這個期 的長短是隨機的，所以稱為隨機期法。的長短是隨機的，所以稱為隨機期法。 另一種辦法是它定期的置全部使用位為另一種辦法是它定期的置全部使用位為“0”。 由由“未用過計數器未用過計數器”HS(或稱為歷史位或稱為歷史位)，定期地每，定期地每 隔隔t掃視使用位掃視使用位，對使用位為對使用位為0的頁，則加的頁，則加1Hs， 并讓使用位繼續(xù)為并讓使用位繼續(xù)為0；對使用位為；對使用位為1的頁，則置的頁，則置 0Hs，同時置，同時置0使用位。掃描結束所有使用位為使用位。掃描結束所有使用位為0， Hs大的就是最久未訪問過的，作為替換頁。大的就是最久未訪問過

38、的，作為替換頁。第 4 章 存 貯 體 系 d)優(yōu)化替換算法優(yōu)化替換算法(OPT) 定義定義 無論是無論是“近期最少使用近期最少使用”還是還是“近期最久未近期最久未用過用過” 都屬于都屬于LRU，與，與FIFO類似，都是根據頁面使用類似，都是根據頁面使用 的歷史情況來預估未來的頁面使用狀況，只是的歷史情況來預估未來的頁面使用狀況，只是 比比FIFO更好反映局部性而已。然而，這種更好反映局部性而已。然而，這種“近近期期”畢竟是過去了的近期，如果能根據未來實畢竟是過去了的近期，如果能根據未來實際使用情況，替換出近期不用的頁，主存命中際使用情況，替換出近期不用的頁，主存命中率會更高，這就是優(yōu)化替換算

39、法率會更高，這就是優(yōu)化替換算法(Optimal Replacement Algorithm,OPT)第 4 章 存 貯 體 系 方法方法 在時刻在時刻t找出主存中每個頁面將要用到的時刻找出主存中每個頁面將要用到的時刻ti， 然后選擇然后選擇tit最大的那一頁作為被替換的頁。顯最大的那一頁作為被替換的頁。顯 然，這只有讓程序運行一遍得到實際的頁地址流，然，這只有讓程序運行一遍得到實際的頁地址流， 才能找到為實現這種替換算法所需要的各頁使用才能找到為實現這種替換算法所需要的各頁使用 信息，這是不現實的。所以，優(yōu)化替換算法只是信息，這是不現實的。所以，優(yōu)化替換算法只是 一種理想化的算法，它可以被用作

40、評價其它替換一種理想化的算法，它可以被用作評價其它替換 算法好壞的標準，看看哪種替換算法能使主存的算法好壞的標準，看看哪種替換算法能使主存的 命中率接近于優(yōu)化替換算法。命中率接近于優(yōu)化替換算法。第 4 章 存 貯 體 系 4)影響命命中率的因素影響命命中率的因素 a)與替換算法有關與替換算法有關 例：設有一道程序，有例：設有一道程序，有1 1至至5 5共共5 5頁，執(zhí)行時的頁，執(zhí)行時的 頁地址流頁地址流( (即執(zhí)行時依次使用到的程序頁頁號即執(zhí)行時依次使用到的程序頁頁號) )為：為： 2 2，3 3，2 2，1 1，5 5，2 2，4 4，5 5，3 3，2 2，5 5，2 2 若分配給該道程序

41、的主存有若分配給該道程序的主存有3 3頁，如下圖表示頁，如下圖表示分別用分別用FIFO,LRU,OPT3FIFO,LRU,OPT3種替換算法對這種替換算法對這3 3頁的使頁的使用和替換過程。用和替換過程。FIFOFIFO的命中率最低，而的命中率最低，而LRULRU的的接近于接近于OPTOPT的。的。第 4 章 存 貯 體 系 2* *312323命中命中2調進調進 調進調進調進調進53* *1替換替換521* *替換替換5* *24替換替換5* *24命中命中32* *4替換替換32* *4命中命中354* *替換替換3* *52替換替換 FIFO命中命中3次次2323命中命中2調進調進 調進

42、調進2323命中命中2調進調進 調進調進 LRU命中命中5次次 OPT命中命中6次次頁地址流頁地址流 2 3 2 1 5 2 4 5 3 2 5 2時間時間t 1 2 3 4 5 6 7 8 9 10 11 1223* *1調進調進2* *51替換替換251* *命中命中25* *4替換替換2* *54命中命中354* *替換替換35* *2替換替換3* *52命中命中3* *52命中命中231* *調進調進23* *5替換替換2* *35命中命中4* *35替換替換4* *35命中命中4* *35命中命中23* *5替換替換235命中命中235命中命中3 3種替換算法對同一頁地址流的替換過程

43、種替換算法對同一頁地址流的替換過程第 4 章 存 貯 體 系 b)命中率與頁地址流有關命中率與頁地址流有關 例如一個循環(huán)程序，當所需頁數大于分配給例如一個循環(huán)程序，當所需頁數大于分配給 它的主存頁數時，無論是它的主存頁數時，無論是FIFO還是還是LRU算法的算法的 命中率都明顯低于命中率都明顯低于OPT的。如下圖所示，的。如下圖所示，LRU 和和FIFO一次都沒有命中，因為它恰好總是將馬一次都沒有命中，因為它恰好總是將馬 上要用到的頁面給替換出去了，從而連續(xù)不斷上要用到的頁面給替換出去了，從而連續(xù)不斷 的出現頁面失效，產生所謂的顛簸現象。的出現頁面失效，產生所謂的顛簸現象。 第 4 章 存 貯

44、 體 系 1* *2322142* *3413* *4* *1231* *2342* * FIFO無命中無命中121121 LRU無命中無命中 OPT命中命中3次次頁地址流頁地址流 1 2 3 4 1 2 3 4時間時間t 1 2 3 4 5 6 7 812* *4134* *123* *1* *24命中命中命中命中13* *4命中命中 命中率與頁地址流有關命中率與頁地址流有關124* *1* *2342* *3413* *4* *1231* *2342* *第 4 章 存 貯 體 系 c)與主存容量與主存容量(即分配給程序的主存頁數即分配給程序的主存頁數)有關有關 一般來說，分配給程序的主存

45、頁數越多，虛一般來說，分配給程序的主存頁數越多，虛頁裝入主存的機會就越多，命中率也可能就越頁裝入主存的機會就越多，命中率也可能就越高。但具體還與所采用的替換算法有很大關系。高。但具體還與所采用的替換算法有很大關系。如下圖所示，當分配給程序的主存頁數如下圖所示，當分配給程序的主存頁數n由由3增增加到加到4時，時，FIFO的命中率反而由的命中率反而由3/12降到降到2/12;而而LRU的命中率卻不會發(fā)生這種情況，隨著分的命中率卻不會發(fā)生這種情況，隨著分配給該道程序的主存頁數的增加，命中率一般配給該道程序的主存頁數的增加，命中率一般都會得到提高，至少不會降低。都會得到提高，至少不會降低。第 4 章

46、存 貯 體 系 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時間時間t 1 2 3 4 5 6 7 8 9 10 11 121* *23命中命中342* *3341* *234命中命中1* *23452* *34513* *45124* *5* *12341* *23452* *3FIFO法的實頁數增加，命中率反而有可能下降法的實頁數增加，命中率反而有可能下降第 4 章 存 貯 體 系

47、5)堆棧型替換算法堆棧型替換算法 a)定義定義 A A：長度為：長度為L的任意一個頁面地址流的任意一個頁面地址流 t： 已處理過已處理過t1個頁面的時間點個頁面的時間點 n：分配給該地址流的主存頁面數：分配給該地址流的主存頁面數 Bt(n)：在：在t時間點、在時間點、在n頁的主存中的頁面集合頁的主存中的頁面集合 Lt：到：到t時刻已遇到的地址流中相異頁的頁數時刻已遇到的地址流中相異頁的頁數 若若 n= Lt時，時， Bt(n1) = Bt(n) 成立，則此替成立，則此替換算法屬于堆棧型的替換算法。換算法屬于堆棧型的替換算法。第 4 章 存 貯 體 系 b)優(yōu)點優(yōu)點 命中率隨主存頁數的增加只可能

48、提高，至少不命中率隨主存頁數的增加只可能提高，至少不會下降。會下降。 只需采用堆棧處理技術對地址流模擬處理一次，只需采用堆棧處理技術對地址流模擬處理一次，即可同時獲得對此地址流在不同主存頁數時的即可同時獲得對此地址流在不同主存頁數時的命中率，大大節(jié)省存貯體系設計的工作量。命中率，大大節(jié)省存貯體系設計的工作量。 對頁地址流對頁地址流A A在在t t時刻的時刻的A At t頁是否命中，只需看頁是否命中，只需看S St-1t-1( (主存在主存在t-1t-1時刻的堆棧時刻的堆棧) )的前的前n n項是否有項是否有A At t，若有則命中。若有則命中。第 4 章 存 貯 體 系 c)LRU算法算法 屬

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

50、率。第 4 章 存 貯 體 系 5)頁面失效頻率法頁面失效頻率法(PFF) 由于堆棧型替換算法具有隨分配給該道程序的實由于堆棧型替換算法具有隨分配給該道程序的實頁數頁數n n的增加，命中率的增加，命中率H H會單調上升的特點，所以可會單調上升的特點，所以可對對LRULRU算法加以改進和發(fā)展：根據各道程序運行中算法加以改進和發(fā)展：根據各道程序運行中的主存頁面失效率的高低，由的主存頁面失效率的高低，由OSOS來動態(tài)調節(jié)分配給來動態(tài)調節(jié)分配給每道程序的實頁數。當主存頁面失效率超過某個限每道程序的實頁數。當主存頁面失效率超過某個限值時就自動增加給該道程序的主存頁數來提高其命值時就自動增加給該道程序的主

51、存頁數來提高其命中率；而當主存頁面失效率低于某個限值時就自動中率；而當主存頁面失效率低于某個限值時就自動減少分配給該道程序的主存頁數，以便釋放出這部減少分配給該道程序的主存頁數，以便釋放出這部分主存頁面位置給其它程序用，從而使整個系統總分主存頁面位置給其它程序用，從而使整個系統總的主存命中率和主存利用率得到提高。的主存命中率和主存利用率得到提高。第 4 章 存 貯 體 系 3.虛擬存貯器工作的全過程虛擬存貯器工作的全過程 具體過程見下頁圖：具體過程見下頁圖：第 4 章 存 貯 體 系 NvNvd d輔存實地址輔存實地址 外部地址變換外部地址變換虛地址虛地址=輔存實地址輔存實地址用戶標志用戶標志

52、u虛頁號虛頁號NvNr 6 多用戶多用戶虛地址虛地址N NS S 內部地址變換內部地址變換虛頁號虛頁號=主存實頁號主存實頁號nvnrnp 5 2 1 2頁面頁面02 2n nv v-1 2 2n nr r個字個字2 2n nv v個頁個頁 3 3 2是否在是否在 主存？主存？ “是是”( (訪主存訪主存) ) “否否”( (主存頁主存頁 面失效面失效) ) 4 5主存主存(頁式頁式) 2 2n np p個字個字是否在是否在 輔存？輔存？ 8 6 “否否”(輔存頁輔存頁面失效面失效) “是是”(訪輔存訪輔存)主存頁面表主存頁面表 9 6頁面替頁面替換算法換算法1112已滿已滿未滿未滿10I/O處

53、理機處理機13主存主存頁號頁號頁面頁面0頁面頁面0112Nv-1(選頁選頁) 714調入頁調入頁 714替換頁替換頁 被替換頁退回被替換頁退回若未被修改則不必退回若未被修改則不必退回 輔存輔存2 2N NS S個字個字第 4 章 存 貯 體 系 虛擬存貯器工作全過程 P144 圖4.251、內部地址變換 查內頁表 用戶虛地址主存實地址 裝入位=1 訪問主存 結束結束 裝入位=0 頁面失效，程序換道， 由輔存調頁 第 4 章 存 貯 體 系 2、外部地址變換查外頁表 多用戶虛地址Ns輔存實地址Nvd 裝入位=1 到輔存中選頁 經I/O處理機送入主存 修改內頁表裝入位=0 不在輔存,由海量存貯器調

54、入 修改內外頁表 第 4 章 存 貯 體 系 3、調頁調頁 查OS主存頁面表 未裝滿時 調入新頁裝入主存 裝滿時 替換算法 11 12 把確定的實頁號送入I/O通道 134、替換該頁未被修改過，不送回輔存 該頁已被修改過，需送回輔存 14 第 4 章 存 貯 體 系 4.2.3頁式虛擬存貯器實現中的問題頁式虛擬存貯器實現中的問題 1.頁面失效處理頁面失效處理 1)原因原因 頁面的劃分只是機械的對程序空間和主存空間頁面的劃分只是機械的對程序空間和主存空間進行等分，與程序的邏輯結構毫無關系。這樣，進行等分，與程序的邏輯結構毫無關系。這樣，對于按字節(jié)編址的存貯器就有可能出現一條指令對于按字節(jié)編址的存

55、貯器就有可能出現一條指令橫跨在兩頁上存貯的情況。同理，也會出現一個橫跨在兩頁上存貯的情況。同理，也會出現一個操作數跨在兩頁上存貯。另外，采用間接尋址，操作數跨在兩頁上存貯。另外，采用間接尋址，特別是多重間接尋址時，在尋址的過程中，可能特別是多重間接尋址時，在尋址的過程中，可能出現跨頁、甚至連續(xù)跨多個頁訪問的情況。每當出現跨頁、甚至連續(xù)跨多個頁訪問的情況。每當當前一頁已在主存而跨頁存放的另一頁不在主存當前一頁已在主存而跨頁存放的另一頁不在主存時，就會發(fā)生頁面失效。時，就會發(fā)生頁面失效。第 4 章 存 貯 體 系 2)解決方法解決方法 由于頁面失效可能出現于取指、取操作數、間接由于頁面失效可能出現

56、于取指、取操作數、間接尋址等過程中，即會在一條指令的分析或執(zhí)行中發(fā)尋址等過程中，即會在一條指令的分析或執(zhí)行中發(fā)生。通常的中斷都是依靠在每條指令執(zhí)行的末尾去生。通常的中斷都是依靠在每條指令執(zhí)行的末尾去設置一個訪中斷微操作，來檢查系統中有無未屏蔽設置一個訪中斷微操作，來檢查系統中有無未屏蔽的中斷請求，以便對其進行響應和處理。而頁面失的中斷請求，以便對其進行響應和處理。而頁面失效不能采用這種辦法，否則由于未能對頁面失效進效不能采用這種辦法，否則由于未能對頁面失效進行處理，就不可能調頁，也就無法執(zhí)行到訪中斷微行處理，就不可能調頁，也就無法執(zhí)行到訪中斷微操作，從而就不可能對頁面失效進行響應和處理，操作，

57、從而就不可能對頁面失效進行響應和處理，機器的工作就被停頓下來。所以，頁面失效不能按機器的工作就被停頓下來。所以，頁面失效不能按一般的中斷對待，應看作一種故障，一旦出現，處一般的中斷對待，應看作一種故障，一旦出現，處理機必須立即予以響應和處理。理機必須立即予以響應和處理。 第 4 章 存 貯 體 系 a)后援寄存器技術后援寄存器技術 把發(fā)生頁面失效故障時指令的全部現場都保把發(fā)生頁面失效故障時指令的全部現場都保 存下來。在處理完故障并把所需要的頁調入主存下來。在處理完故障并把所需要的頁調入主 存后，取出后援寄存器的內容恢復故障點現場，存后，取出后援寄存器的內容恢復故障點現場， 然后從故障點處繼續(xù)執(zhí)

58、行完該條指令。然后從故障點處繼續(xù)執(zhí)行完該條指令。 b)預判技術預判技術 執(zhí)行指令前先預判操作數的首尾字符是否都執(zhí)行指令前先預判操作數的首尾字符是否都 已在主存中。如果是，才執(zhí)行這條指令；否則已在主存中。如果是，才執(zhí)行這條指令；否則 就發(fā)生頁面失效，直到調入該頁后才開始執(zhí)行就發(fā)生頁面失效，直到調入該頁后才開始執(zhí)行 這條指令。這條指令。第 4 章 存 貯 體 系 c)替換算法替換算法 不允許出現指令或操作數跨頁存貯的那些頁不允許出現指令或操作數跨頁存貯的那些頁 被輪流從主存中替換出去的被輪流從主存中替換出去的“顛簸顛簸”現象。因現象。因此，此， 給某道程序分配的主存頁數應該有個下限。給某道程序分配

59、的主存頁數應該有個下限。 d)頁面大小不能過大頁面大小不能過大 以便多道程序的道數、每道程序所分配到的以便多道程序的道數、每道程序所分配到的 主存頁數都能在一個適當的范圍內。如果頁面主存頁數都能在一個適當的范圍內。如果頁面 過大，就會使主存中頁數過少，從而出現大量過大，就會使主存中頁數過少，從而出現大量 的頁面失效，嚴重降低虛擬存貯器的訪問速率的頁面失效，嚴重降低虛擬存貯器的訪問速率 和等效速度。和等效速度。第 4 章 存 貯 體 系 2.提高虛擬存貯器等效訪問速度的措施提高虛擬存貯器等效訪問速度的措施 根據根據虛擬存貯器等效訪問速度公式虛擬存貯器等效訪問速度公式 TA=HTA1+(1-H)T

60、A2 希望希望H H提高，提高， TA1 ，TA2縮短縮短 關于高的主存命中率問題，其影響因素很多，關于高的主存命中率問題，其影響因素很多，如地址流、頁面調度策略、替換算法、頁面大小如地址流、頁面調度策略、替換算法、頁面大小及分配給程序的頁數及分配給程序的頁數( (主存容量主存容量) )等。這里主要討等。這里主要討論怎樣縮短訪主存的時間。論怎樣縮短訪主存的時間。第 4 章 存 貯 體 系 從虛擬存貯器工作的全過程可以看到，每次訪從虛擬存貯器工作的全過程可以看到，每次訪問主存時，都必須進行內部地址變換問主存時，都必須進行內部地址變換(因為頁表都因為頁表都存在主存中，每次查頁表就要增加一次訪存。若