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

2、了內(nèi)存總?cè)萘浚鳂I(yè)不能全部被裝入內(nèi)存，致使該作內(nèi)存總?cè)萘浚鳂I(yè)不能全部被裝入內(nèi)存，致使該作業(yè)無法運(yùn)行；業(yè)無法運(yùn)行；(2) 有大量作業(yè)要求運(yùn)行，但由于內(nèi)存容量不足有大量作業(yè)要求運(yùn)行，但由于內(nèi)存容量不足以容納所有這些作業(yè)，只能將少數(shù)作業(yè)裝入內(nèi)存讓以容納所有這些作業(yè)，只能將少數(shù)作業(yè)裝入內(nèi)存讓它們先運(yùn)行，而將其它大量的作業(yè)留在外存上等待它們先運(yùn)行，而將其它大量的作業(yè)留在外存上等待。35.1.1 常規(guī)存儲管理方式的特征和局部性原理1. 1. 常規(guī)存儲器管理方式的特征常規(guī)存儲器管理方式的特征我們把前一章中所介紹的各種存儲器管理方我們把前一章中所介紹的各種存儲器管理方式統(tǒng)稱為傳統(tǒng)存儲器管理方式，它們?nèi)季哂?/p>

3、如式統(tǒng)稱為傳統(tǒng)存儲器管理方式，它們?nèi)季哂腥缦聝蓚€(gè)共同的特征：下兩個(gè)共同的特征：(1) 一次性一次性(2) 駐留性駐留性 42. 2. 局部性原理局部性原理程序運(yùn)行時(shí)存在的局部性現(xiàn)象，很早就已被程序運(yùn)行時(shí)存在的局部性現(xiàn)象，很早就已被人發(fā)現(xiàn)，但直到人發(fā)現(xiàn)，但直到1968年，年，P.Denning才真正指出才真正指出：程序在執(zhí)行時(shí)將呈現(xiàn)出局部性規(guī)律，即在一較：程序在執(zhí)行時(shí)將呈現(xiàn)出局部性規(guī)律，即在一較短的時(shí)間內(nèi)，程序的執(zhí)行僅局限于某個(gè)部分，相短的時(shí)間內(nèi)，程序的執(zhí)行僅局限于某個(gè)部分，相應(yīng)地，它所訪問的存儲空間也局限于某個(gè)區(qū)域。應(yīng)地，它所訪問的存儲空間也局限于某個(gè)區(qū)域。 5局限性又表現(xiàn)在下述兩個(gè)方面：局

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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