計算機操作系統(tǒng)課件：第5章存儲器管理03-虛擬存儲器

1、第五章 存儲管理(三)- 虛擬存儲器知識回顧與展開在上一節(jié)課中我們主要介紹了：1 分頁式存儲管理方式2 分段式存儲管理方式3 段頁式存儲管理方式以上方法的共同缺點：都要求將一個作業(yè)全部裝入內(nèi)存后方能運行。解決方法：虛擬存儲技術 1 局部性原理 2 虛擬存儲器的基本原理 3 請求分頁系統(tǒng) 4 頁面調(diào)度策略本節(jié)課的主要內(nèi)容局部性原理： 指在一較短的時間內(nèi)，程序的執(zhí)行僅局限于某個部分；程序所訪問的存儲空間也局限于某個特定的區(qū)域。1.局部性原理1.局部性原理可表現(xiàn)為兩方面 時間局限性： 一條指令的一次執(zhí)行和下次執(zhí)行，一個數(shù)據(jù)的 一次訪問和下次訪問都集中在一個較短時期內(nèi)。如循環(huán)、子程序、累計變量等。 空

2、間局限性： 若某一存儲單元被訪問，那么與該存儲單元相鄰的單元可能也會很快被訪問。基于局部性原理，在程序裝入時，不必將其全部讀入到內(nèi)存，而只需將當前需要執(zhí)行的部分頁或段讀入到內(nèi)存，就可讓程序開始執(zhí)行。虛擬存儲器：是指僅把程序的一部分裝入內(nèi)存便可運行程序的存儲器系統(tǒng)，該系統(tǒng)具有請求調(diào)入功能和置換功能，能從邏輯上對內(nèi)存容量加以擴充的一種存儲器系統(tǒng)。其容量由內(nèi)存容量和外存容量之和所決定，其運行速度接近于內(nèi)存速度，而成本接近于外存。2. 虛擬存儲器的基本原理虛擬存儲技術實現(xiàn)思想： 在程序執(zhí)行過程中，如果需執(zhí)行的指令或訪 問的數(shù)據(jù)尚未在內(nèi)存（稱為缺頁或缺段）， 則程序利用操作系統(tǒng)所提供的請求調(diào)頁（段） 功

3、能，將他們調(diào)入內(nèi)存，然后繼續(xù)執(zhí)行程序。 如果此時內(nèi)存已滿，須利用操作系統(tǒng)的頁 （段）的置換功能，將內(nèi)存中暫時不用的頁或 段調(diào)出保存在外存上，從而騰出空間存放將要 裝入的程序以及將要調(diào)入的頁或段。目的：提高內(nèi)存利用率。虛擬存儲器的特征多次性 指一個程序被分成多次調(diào)入內(nèi)存運行。多次性是虛擬存儲器最重要的特征，任何其它的存儲管理方式都不具有這一特征。因此，我們也可以認為虛擬存儲器是具有多次性特征的存儲器系統(tǒng)。 對換性 指允許在程序的運行過程中進行換進、換出，換進和換出能有效地提高內(nèi)存利用率。 虛擬性 指能夠從邏輯上擴充內(nèi)存容量，使用戶所看到的內(nèi)存容量遠大于實際內(nèi)存容量。這是虛擬存儲器所表現(xiàn)出來的最重

4、要的特征，也是實現(xiàn)虛擬存儲器的最重要的目標。 虛擬存儲器的實現(xiàn)方法 分頁虛擬存儲管理方式 分段虛擬存儲管理方式虛擬存儲器的實現(xiàn)建立在離散分配的存儲器管理方式的基礎上。分頁虛擬存儲管理方式系統(tǒng)需要解決下面兩個問題：當發(fā)現(xiàn)缺頁時，如何把所缺頁面調(diào)入內(nèi)存。當內(nèi)存中沒有空閑的物理塊時，為了要接受一個新頁，需要把老的一頁淘汰出去，根據(jù)什么策略選擇欲淘汰的頁面。注： 缺頁中斷：當CPU要訪問進程的某個頁面不在內(nèi)存中，稱這種現(xiàn)象為缺頁中斷。 虛擬存儲器系統(tǒng)通常定義三種策略來規(guī)定如何（何時）以及怎樣進行頁面調(diào)度。 調(diào)頁策略 內(nèi)存分配及置換策略 頁面置換算法頁面調(diào)度策略 虛擬存儲器的調(diào)入策略決定采用什么樣的方式

5、將所缺頁面由外存調(diào)入到內(nèi)存之中。兩種常用調(diào)頁策略：1.頁面調(diào)入策略 請求調(diào)頁 預調(diào)頁1.請求調(diào)頁 只調(diào)入發(fā)生缺頁時所需的頁面。2.預調(diào)頁 發(fā)生缺頁時，一次調(diào)入該頁及相鄰的幾頁。 如調(diào)入頁以后很少被訪問，造成浪費。1.頁面調(diào)入策略 如果缺頁中斷發(fā)生時內(nèi)存已滿，“置換策略”用于確定必須從內(nèi)存中移出哪個虛頁面，以便為新的頁面騰出空位。 在請求分頁系統(tǒng)中，可采取兩種內(nèi)存分配策略，即:固定分配和可變分配策略。 在進行置換時，也可采取兩種策略，即: 全局置換和局部置換策略。2.內(nèi)存分配及置換策略 1) 固定分配局部置換 (Fixed Allocation, Local Replacement) 2) 可變

6、分配全局置換 (Variable Allocation, Global Replacement) 3) 可變分配局部置換 (Variable Allocation, Local Replacemen）2.內(nèi)存分配及置換策略 1) 固定分配局部置換 為每一進程分配固定物理塊數(shù)的內(nèi)存空間， 在整個運行期間都不再改變。如進程發(fā)生缺頁，只能從該進程在內(nèi)存中的 自己的N個頁面中選出一頁換出，然后再調(diào) 入所缺頁面。 2.內(nèi)存分配及置換策略 2) 可變分配全局置換 先為系統(tǒng)中每個進程分配一定數(shù)量的 物理塊，OS本身保持一個空閑物理塊隊列。 若進程發(fā)生缺頁，則系統(tǒng)從空閑物理塊隊列中，取出一物理塊分配給該進程，

7、直到空閑物理塊用完時才會從內(nèi)存中選中一頁調(diào)出，該頁可能為系統(tǒng)中任意一個進程的頁。 2.內(nèi)存分配及置換策略 3) 可變分配局部置換 為每個進程分配一定數(shù)目的物理塊數(shù)。如進程發(fā)生缺頁，從該進程的頁面中 換出一頁，不影響其他進程運行。如頻繁發(fā)生缺頁，系統(tǒng)再為該進程分配若干物理塊，降低進程的缺頁率。 2.內(nèi)存分配及置換策略 ) 最佳算法 （ OPT，Optimal ）) 最近最久未使用算法 （ LRU，Least Recently Used ）) 先進先出算法（ FIFO ）) 簡單時鐘算法 （ Clock ）) 改進型Clock算法3.頁面置換算法-頁面淘汰算法 1).最佳置換算法(OPT)-向后看

8、 是由Belady于1966年提出的一種理論上的算法，不能被實現(xiàn)，做性能評價依據(jù)。 選擇置換“未來不再使用的”或“在離當前最遠位置上出現(xiàn)的”頁面。采用最佳置換算法，通?？杀ＷC獲得最低的缺頁率。 3.頁面置換算法 例：假定系統(tǒng)為某進程分配了三個物理塊，一作業(yè)要依次訪問如下頁面：7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1。請采用OPT頁面置換算法，求出在訪問過程中發(fā)生缺頁中斷的次數(shù)及缺頁率（缺頁次數(shù)總訪問次數(shù) * 100% ）。1).最佳置換算法(OPT,Optimal)3.頁面置換算法 （提示：進程運行時， 先將7，0，1三個頁面裝入內(nèi)存。進程要訪問頁面2時，

9、將會產(chǎn)生缺頁中斷。此時OS根據(jù)最佳置換算法，將選擇頁面7淘汰。）（新裝入的頁號放在表格中被淘汰頁的位置，狀態(tài)保持未列出。）3.頁面置換算法 N=3頁面訪問的次序初始70120304230321201701NULL72777NULL4NULL3缺頁次1).最佳算法(OPT)-向后看（新裝入的頁號放在表格中被淘汰頁的位置）3.頁面置換算法 缺頁率為9/20*100%=45%2).先進先出算法 (FIFO) 選擇置換裝入最早的頁面?？赏ㄟ^鏈表來表示各頁的裝入時間先后。性能較差。較早調(diào)入的頁往往是經(jīng)常被訪問的頁，這些頁在FIFO算法下被反復調(diào)入和調(diào)出。并且有Belady現(xiàn)象。3.頁面置換算法 Bela

10、dy現(xiàn)象：采用FIFO算法時，如果對一個進程未分配它所要求的全部頁面，有時就會出現(xiàn)分配的內(nèi)存物理塊數(shù)增多，缺頁率反而提高的異?，F(xiàn)象。Belady現(xiàn)象的原因：FIFO算法的置換特征與進程訪問內(nèi)存的動態(tài)特征是矛盾的，即被置換的頁面并不是進程不會訪問的。2).先進先出算法 (FIFO) 3.頁面置換算法 例1：假定系統(tǒng)為某進程分配了三個物理塊,一個作業(yè)要依次訪問如下頁面：，0，。請采用FIFO頁面置換算法，求出在訪問過程中發(fā)生缺頁中斷的次數(shù)及缺頁率。（缺頁率缺頁次數(shù)總訪問次數(shù) * 100%） 2).先進先出算法 (FIFO) 3.頁面置換算法 Belady異常N=3頁面訪問的次序初始01230140

11、1234最新NULL2301444233NULL11230111422最早NULL000123000144缺頁9次2).先進先出算法 (FIFO) 3.頁面置換算法 缺頁率為9/12*100%=75%N=4頁面訪問的次序初始012301401234最新NULL333401234NULL2222340123NULL11111234012最老NULL000000123401缺頁10次Belady異常2).先進先出算法 (FIFO) 3.頁面置換算法 缺頁率為10/12*100%=83%3).最近最久未使用算法(LRU) 選擇置換內(nèi)存中最久未使用的頁面。性能接近最佳算法。需記錄頁面使用時間的先后關系

12、，所以硬件開銷比較大。以下硬件機構幫助實現(xiàn)：）特殊棧）為每一頁面設置移位寄存器3.頁面置換算法 棧：把被訪問的頁面移到棧頂，棧底的 頁面就是最久未使用的頁面。用棧保存當前使用頁面時棧的變化情況 LRU置換算法的硬件支持 3.頁面置換算法 2).最近最久未使用算法(LRU) 例：假定系統(tǒng)為某進程分配了三個物理塊，一作業(yè)要依次訪問如下頁面：7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1。請采用LRU頁面置換算法，求出在訪問過程中發(fā)生缺頁中斷的次數(shù)及缺頁率（缺頁次數(shù)總訪問次數(shù) * 100% ）。3.頁面置換算法 N=3頁面訪問的次序初始7012030423032120

13、1701NULL120304230322070NULL0012030423032120170NULL77701223042203312017缺頁次3).最近最久未使用算法(LRU)（注：新裝入的頁號放在表格中被淘汰頁的位置）3.頁面置換算法 缺頁率為12/20*100%=60%練習題1在一個分頁虛擬存儲管理系統(tǒng)中，進程P共有5頁。頁面訪問序列為：3，2，1，0，3，2，4，3，2，1，0，4時，試采用FIFO和LRU置換算法，計算當分配給該進程的物理塊數(shù)分別為3和4時，求訪問過程中發(fā)生的缺頁中斷次數(shù)和缺頁率。練習題頁面321032432104塊11032444100塊222103222411塊3333210333244缺頁缺頁中斷次數(shù)為9，缺頁率為 9/12*100%= 75% 。分配給該進程的物理塊數(shù)為3時：先進先出算法 (FIFO) 缺頁中斷次數(shù)為10，缺頁率為10/12*100%= 83%。頁面321032432104塊1000432104塊21111043210塊322222104321塊4333333210432缺頁分配給該進程的物理塊數(shù)為4時：練習題分配給該進程的物理塊數(shù)為4時：先進先出算法 (FIFO) 練習題頁面321032432104塊11032432104塊222103243210塊33332