1、第第5章章 虛擬存儲器虛擬存儲器 25.1 虛擬存儲器概述虛擬存儲器概述5.2 請求分頁存儲管理方式請求分頁存儲管理方式5.3 頁面置換算法頁面置換算法5.4 “抖動抖動”與工作集與工作集5.5 請求分段存儲管理方式請求分段存儲管理方式習題習題5.1 虛擬存儲器概述第四章所介紹的各種存儲器管理方式有一個共第四章所介紹的各種存儲器管理方式有一個共同的特點，即它們都要求將一個作業全部裝入內存同的特點，即它們都要求將一個作業全部裝入內存后方能運行。于是，出現了下面這樣兩種情況：后方能運行。于是，出現了下面這樣兩種情況：(1) 有的作業很大，其所要求的內存空間超過了有的作業很大，其所要求的內存空間超過

2、了內存總容量，作業不能全部被裝入內存，致使該作內存總容量，作業不能全部被裝入內存，致使該作業無法運行；業無法運行；(2) 有大量作業要求運行，但由于內存容量不足有大量作業要求運行，但由于內存容量不足以容納所有這些作業，只能將少數作業裝入內存讓以容納所有這些作業，只能將少數作業裝入內存讓它們先運行，而將其它大量的作業留在外存上等待它們先運行，而將其它大量的作業留在外存上等待。35.1.1 常規存儲管理方式的特征和局部性原理1. 1. 常規存儲器管理方式的特征常規存儲器管理方式的特征我們把前一章中所介紹的各種存儲器管理方我們把前一章中所介紹的各種存儲器管理方式統稱為傳統存儲器管理方式，它們全都具有

3、如式統稱為傳統存儲器管理方式，它們全都具有如下兩個共同的特征：下兩個共同的特征：(1) 一次性一次性(2) 駐留性駐留性 42. 2. 局部性原理局部性原理程序運行時存在的局部性現象，很早就已被程序運行時存在的局部性現象，很早就已被人發現，但直到人發現，但直到1968年，年，P.Denning才真正指出才真正指出：程序在執行時將呈現出局部性規律，即在一較：程序在執行時將呈現出局部性規律，即在一較短的時間內，程序的執行僅局限于某個部分，相短的時間內，程序的執行僅局限于某個部分，相應地，它所訪問的存儲空間也局限于某個區域。應地，它所訪問的存儲空間也局限于某個區域。 5局限性又表現在下述兩個方面：局

4、限性又表現在下述兩個方面：(1) 時間局限性時間局限性。如果程序中的某條指令一旦執行，則不久的將來該指令可能如果程序中的某條指令一旦執行，則不久的將來該指令可能再次被執行；如果某個存儲單元被訪問，則不久以后該存儲再次被執行；如果某個存儲單元被訪問，則不久以后該存儲單元可能再次被訪問。產生時間局限性的典型原因是在程序單元可能再次被訪問。產生時間局限性的典型原因是在程序中存在著大量的循環操作。中存在著大量的循環操作。(2) 空間局限性空間局限性。一旦程序訪問了某個存儲單元，則在不久的將來，其附近的一旦程序訪問了某個存儲單元，則在不久的將來，其附近的存儲單元也最有可能被訪問。存儲單元也最有可能被訪問

5、。 即程序在一段時間內所訪問的即程序在一段時間內所訪問的地址，可能集中在一定的范圍內，其典型原因是程序是順序地址，可能集中在一定的范圍內，其典型原因是程序是順序執行的。執行的。63. 3. 虛擬存儲器的基本工作情況虛擬存儲器的基本工作情況 基于局部性原理可知，應用程序在運行之前基于局部性原理可知，應用程序在運行之前沒有必要將之全部裝入內存，而僅須將那些當前沒有必要將之全部裝入內存，而僅須將那些當前要運行的少數頁面或段先裝入內存便可運行，其要運行的少數頁面或段先裝入內存便可運行，其余部分暫留在盤上。余部分暫留在盤上。 75.1.2 虛擬存儲器的定義和特征1. 1. 虛擬存儲器的定義虛擬存儲器的定

6、義當用戶看到自己的程序能在系統中正常運行當用戶看到自己的程序能在系統中正常運行時，他會認為，該系統所具有的內存容量一定比時，他會認為，該系統所具有的內存容量一定比自己的程序大，或者說，用戶所感覺到的內存容自己的程序大，或者說，用戶所感覺到的內存容量會比實際內存容量大得多。但用戶所看到的大量會比實際內存容量大得多。但用戶所看到的大容量只是一種錯覺，是虛的，故人們把這樣的存容量只是一種錯覺，是虛的，故人們把這樣的存儲器稱為虛擬存儲器。儲器稱為虛擬存儲器。8所謂所謂虛擬存儲器虛擬存儲器，是指具有請求調入功能和置換功，是指具有請求調入功能和置換功能，對內外存統一管理，能從邏輯上對內存容量能，對內外存統

7、一管理，能從邏輯上對內存容量加以擴充的一種存儲器系統。從用戶角度上看，加以擴充的一種存儲器系統。從用戶角度上看，系統具備了比實際內存容量大得多的存儲器，人系統具備了比實際內存容量大得多的存儲器，人們把這樣的存儲器稱為虛擬存儲器。們把這樣的存儲器稱為虛擬存儲器。2. 2. 虛擬存儲器的特征虛擬存儲器的特征與傳統的存儲器管理方式比較，虛擬存儲器與傳統的存儲器管理方式比較，虛擬存儲器具有以下三個重要特征：具有以下三個重要特征：(1) 多次性。多次性。(2) 對換性。對換性。(3) 虛擬性。虛擬性。105.1.3 虛擬存儲器的實現方法1. 1. 分頁請求系統分頁請求系統2. 2. 請求分段系統請求分段

8、系統115.2 請求分頁存儲管理方式5.2.1 5.2.1 請求分頁中的硬件支持請求分頁中的硬件支持為了實現請求分頁，系統必須提供一定的硬為了實現請求分頁，系統必須提供一定的硬件支持。計算機系統除了要求一定容量的內存和件支持。計算機系統除了要求一定容量的內存和外存外，還需要有請求頁表機制、缺頁中斷機構外存外，還需要有請求頁表機制、缺頁中斷機構以及地址變換機構。以及地址變換機構。121. 1. 請求頁表機制請求頁表機制在請求分頁系統中的每個頁表應含以下諸項：在請求分頁系統中的每個頁表應含以下諸項：2. 2. 缺頁中斷機構缺頁中斷機構(1) 在指令執行期間產生和處理中斷信號。在指令執行期間產生和處

9、理中斷信號。(2) 一條指令在執行期間可能產生多次缺頁一條指令在執行期間可能產生多次缺頁中斷。中斷。133. 3. 地址變換機構地址變換機構請求分頁系統中的地址變換機構是在分頁系請求分頁系統中的地址變換機構是在分頁系統地址變換機構的基礎上，為實現虛擬存儲器，統地址變換機構的基礎上，為實現虛擬存儲器，再增加了某些功能所形成的，如產生和處理缺頁再增加了某些功能所形成的，如產生和處理缺頁中斷，以及從內存中換出一頁的功能等等。中斷，以及從內存中換出一頁的功能等等。14155.2.2 請求分頁中的內存分配1. 1. 最小物理塊數的確定最小物理塊數的確定一個顯而易見的事實是，隨著為每個進程所分配的物理塊的

10、一個顯而易見的事實是，隨著為每個進程所分配的物理塊的減少，將使進程在執行中的缺頁率上升，從而會降低進程減少，將使進程在執行中的缺頁率上升，從而會降低進程的執行速度。為使進程能有效地工作，應為它的執行速度。為使進程能有效地工作，應為它分配一定數分配一定數目的物理塊目的物理塊。2. 2. 內存分配策略內存分配策略 在請求分頁系統中，可采取兩種內存分配策略，即在請求分頁系統中，可采取兩種內存分配策略，即固定和固定和可變分配策略可變分配策略。在進行置換時，也可采取兩種策略，即。在進行置換時，也可采取兩種策略，即全全局置換和局部置換局置換和局部置換。3. 3. 物理塊分配算法物理塊分配算法在采用固定分配

11、策略時，在采用固定分配策略時， 可采用可采用平均分配算法平均分配算法和和按按比例分配算法比例分配算法。165.2.3 頁面調入策略為使進程能夠正常運行，必須事先將要執行的為使進程能夠正常運行，必須事先將要執行的那部分程序和數據所在的頁面調入內存。現在的那部分程序和數據所在的頁面調入內存。現在的問題是：問題是：(1) 系統應在何時調入所需頁面；系統應在何時調入所需頁面；(2) 系統應從何處調入這些頁面；系統應從何處調入這些頁面；(3) 是如何進行調入的。是如何進行調入的。171. 1. 何時調入頁面何時調入頁面(1) 預調頁策略。預調頁策略。(2) 請求調頁策略請求調頁策略。 當進程在運行過程中

12、需要訪問某部分程序和數當進程在運行過程中需要訪問某部分程序和數據時，據時，若發現其所在的頁面不在內存，便立即提若發現其所在的頁面不在內存，便立即提出請求，由出請求，由OS將其所需頁面調入內存。將其所需頁面調入內存。由請求調由請求調頁策略所確定的頁是一定會被訪問頁策略所確定的頁是一定會被訪問 的，再加之請的，再加之請求調頁策略比較易于實現，故在目前求調頁策略比較易于實現，故在目前 的虛擬存儲的虛擬存儲器中，大多采用該策略。器中，大多采用該策略。182. 2. 缺頁率缺頁率假設一個進程的邏輯空間為假設一個進程的邏輯空間為n頁，系統為其頁，系統為其分配的內存物理塊數為分配的內存物理塊數為m(mn)。

13、如果在進程的。如果在進程的運行過程中，訪問頁面成功運行過程中，訪問頁面成功(即所訪問頁面在內存即所訪問頁面在內存中中)的次數為的次數為S，訪問頁面失敗，訪問頁面失敗(即所訪問頁面不在即所訪問頁面不在內存中，需要從外存調入內存中，需要從外存調入)的次數為的次數為F，則該進程，則該進程總的頁面訪問次數為總的頁面訪問次數為A=S+F，那么該進程在其，那么該進程在其運行過程中的缺頁率即為運行過程中的缺頁率即為19AFf 在進程運行過程中，若其所要訪問的頁面不在內存在進程運行過程中，若其所要訪問的頁面不在內存，而需把它們調入內存，但內存已無空閑空間時，而需把它們調入內存，但內存已無空閑空間時，為了保證該

14、進程能正常運行，系統必須從內存，為了保證該進程能正常運行，系統必須從內存中調出一頁程序或數據送到磁盤的對換區中。但中調出一頁程序或數據送到磁盤的對換區中。但應將哪個頁面調出，須根據一定的算法來確定。應將哪個頁面調出，須根據一定的算法來確定。通常，把選擇換出頁面的算法稱為通常，把選擇換出頁面的算法稱為頁面置換算法頁面置換算法5.3 頁面置換算法1. 最佳置換算法最佳置換算法2. 先進先出置換算法先進先出置換算法3. LRU（最近最少使用）置換算法（最近最少使用）置換算法4.最少使用算法最少使用算法5.Clock算法算法211. 1. 最佳最佳(Optimal)(Optimal)置換算法置換算法最

15、佳置換算法是由最佳置換算法是由Belady于于1966年提出的一種理年提出的一種理論上的算法。其所選擇的被淘汰頁面將是以后永論上的算法。其所選擇的被淘汰頁面將是以后永不使用的，或許是在最長不使用的，或許是在最長(未來未來)時間內不再被訪時間內不再被訪問的頁面。采用最佳置換算法通常可保證獲得最問的頁面。采用最佳置換算法通常可保證獲得最低的缺頁率。但由于人們目前還低的缺頁率。但由于人們目前還無法預知無法預知，一個，一個進程在內存的若干個頁面中，哪一個頁面是未來進程在內存的若干個頁面中，哪一個頁面是未來最長時間內不再被訪問的，因而該算法是無法實最長時間內不再被訪問的，因而該算法是無法實現的，但可以利

16、用該算法去評價其它算法。現的，但可以利用該算法去評價其它算法。 222先進先出算法（先進先出算法（FIFO算法）算法）這種算法的基本思想是：總是先淘汰那些駐留在內這種算法的基本思想是：總是先淘汰那些駐留在內存時間最長的頁，即先進入內存的頁先被置換掉存時間最長的頁，即先進入內存的頁先被置換掉。理由是：最先進入內存的頁不再被訪問的可能。理由是：最先進入內存的頁不再被訪問的可能性最大。性最大。 q下一頁下一頁24圖圖5-4 利用利用FIFO置換算法時的置換圖置換算法時的置換圖【例例1】主存塊數主存塊數m=3，置換算法采用，置換算法采用FIFO算法，算法，缺頁中斷次數及缺頁率如圖所示。缺頁中斷次數及缺

17、頁率如圖所示。在圖中，在圖中，P行表示頁面走向，行表示頁面走向，M行表示在主存中的行表示在主存中的頁面號，其中帶有頁面號，其中帶有+的表示新調入頁面，在的表示新調入頁面，在M行的行的各列按調入的順序排列，帶有圓圈的數字表示下各列按調入的順序排列，帶有圓圈的數字表示下一時刻將被淘汰頁面，一時刻將被淘汰頁面，F行表示是否引起缺頁中行表示是否引起缺頁中斷，帶斷，帶號的表示引起缺頁中斷。號的表示引起缺頁中斷。q下一頁下一頁qFIFO算法性能分析（算法性能分析（m=3）q下一頁下一頁從圖可以看出，缺頁中斷頁數為從圖可以看出，缺頁中斷頁數為9次，缺頁率次，缺頁率f=9/12=75%。【例例2】設設m=4，

18、仍采用，仍采用FIFO算法，缺頁中斷次算法，缺頁中斷次數及缺頁率如圖所示。數及缺頁率如圖所示。q下一頁下一頁可以算出，在分配給該作業的內存塊數增加到可以算出，在分配給該作業的內存塊數增加到4時，時，缺頁中斷由圖的缺頁中斷由圖的9次反而增加到了次反而增加到了10次，缺頁率由次，缺頁率由75%增加到增加到10/12=83%，這就是，這就是FIFO算法的一種算法的一種異常現象異常現象。隨著分配的主存塊數的增加，缺頁中。隨著分配的主存塊數的增加，缺頁中斷次數不但沒有降低，反而增加了。這與該算法斷次數不但沒有降低，反而增加了。這與該算法定全不考慮程序的動態特征有關。定全不考慮程序的動態特征有關。3最近最

19、久未使用頁面置換算法最近最久未使用頁面置換算法（LRULeast Recently UsedLeast Recently Used算法）算法） 這種算法的基本思想是，如果某一頁被訪問了，那么它很這種算法的基本思想是，如果某一頁被訪問了，那么它很可能馬上又被訪問；反之，如果某一頁很長時間沒有被訪可能馬上又被訪問；反之，如果某一頁很長時間沒有被訪問，那么最近也不太可能會被訪問。這種算法考慮了程序問，那么最近也不太可能會被訪問。這種算法考慮了程序設計的局部性原理。其實質是，當需要置換一頁時，選擇設計的局部性原理。其實質是，當需要置換一頁時，選擇在最近一段時間最久未使用的頁面予以淘汰。在最近一段時間最

20、久未使用的頁面予以淘汰。實現這種算法可通過周期性地對實現這種算法可通過周期性地對“引用位引用位”進行檢查，并利進行檢查，并利用它來記錄一頁面自上次被訪問以來所經歷的時間用它來記錄一頁面自上次被訪問以來所經歷的時間t，淘，淘汰時選擇汰時選擇t最大的頁面。最大的頁面。 q下一頁下一頁30圖圖5-5LRU頁面置換算法頁面置換算法【例例3】設設m=3，采用，采用LRU算法，缺頁中斷次數算法，缺頁中斷次數及缺頁率如圖所示。及缺頁率如圖所示。q缺頁率：缺頁率： 10/12=83%q下一頁下一頁【例例4】設設m=4，其余同例，其余同例3，則缺頁中斷次數及，則缺頁中斷次數及缺頁率如圖所示。缺頁率如圖所示。 q

21、缺頁率：缺頁率：7/12=58%q返回本節返回本節練習 如果一個作業在執行過程中，按下列的頁號依如果一個作業在執行過程中，按下列的頁號依次訪問主存：次訪問主存：1，2，3，4，2，1，5，6，2，1，2，3，7，6，3，2，1，2，3，6。作業固定占用。作業固定占用 4 個內存頁面個內存頁面(塊塊)，試問分別采用，試問分別采用FIFO、LRU算算法時，各產生多少次缺頁中斷？并計算相應的缺法時，各產生多少次缺頁中斷？并計算相應的缺頁中斷率，并圖示訪問示意圖。頁中斷率，并圖示訪問示意圖。 5.5 請求分段存儲管理方式5.5.1 5.5.1 請求分段中的硬件支持請求分段中的硬件支持為了實現請求分段式存儲管理，應在系統中為了實現請求分段式存儲管理，應在系統中配置多種硬件機構，以支持快速地完成請求分段配置多種硬件機構，以支持快速地完成請求分段功能