第七章 虛擬存儲器管理

1、 7.1 虛擬存儲器的基本概念虛擬存儲器的基本概念 7.1.1 7.1.1 虛擬存儲器的引入虛擬存儲器的引入 1.1.內(nèi)存容量與需求的矛盾內(nèi)存容量與需求的矛盾 從單一連續(xù)分配到普通分頁、分段管理，都遇到如下從單一連續(xù)分配到普通分頁、分段管理，都遇到如下 問題問題 內(nèi)存空閑容量有限，大作業(yè)無法一次性裝入。內(nèi)存空閑容量有限，大作業(yè)無法一次性裝入。 內(nèi)存空閑容量有限，有大量作業(yè)需要運行，但只能運內(nèi)存空閑容量有限，有大量作業(yè)需要運行，但只能運 行部分作業(yè)，其它在外存等待。行部分作業(yè)，其它在外存等待。 2.2.原因分析原因分析 一次性裝入一次性裝入 作業(yè)駐留內(nèi)存作業(yè)駐留內(nèi)存 3.3.解決辦法解決辦法 （

2、1 1）局部性原理）局部性原理 早在早在19681968年年P(guān) PDenningDenning就指出過，就指出過，程序在執(zhí)行時將呈現(xiàn)程序在執(zhí)行時將呈現(xiàn) 出局部性規(guī)律，即在一段時間內(nèi)，程序的執(zhí)行僅局限于出局部性規(guī)律，即在一段時間內(nèi)，程序的執(zhí)行僅局限于 某個部分；相應(yīng)地，它所訪問的存儲空間也局限于某個某個部分；相應(yīng)地，它所訪問的存儲空間也局限于某個 區(qū)域內(nèi)區(qū)域內(nèi)。那么程序為什么會出現(xiàn)局部性規(guī)律呢？原因可。那么程序為什么會出現(xiàn)局部性規(guī)律呢？原因可 以歸結(jié)為以下幾點：以歸結(jié)為以下幾點： 程序在執(zhí)行時，除了少部分的轉(zhuǎn)移和過程調(diào)用指令外，程序在執(zhí)行時，除了少部分的轉(zhuǎn)移和過程調(diào)用指令外， 大多數(shù)仍是順序執(zhí)行

3、的。大多數(shù)仍是順序執(zhí)行的。 子程序調(diào)用將會使程序的執(zhí)行由一部分內(nèi)存區(qū)域轉(zhuǎn)至另子程序調(diào)用將會使程序的執(zhí)行由一部分內(nèi)存區(qū)域轉(zhuǎn)至另 一部分區(qū)域。但在大多數(shù)情況下，過程調(diào)用的深度都不一部分區(qū)域。但在大多數(shù)情況下，過程調(diào)用的深度都不 超過超過5 5。 程序中存在許多循環(huán)結(jié)構(gòu)，循環(huán)體中的指令被多次執(zhí)行。程序中存在許多循環(huán)結(jié)構(gòu)，循環(huán)體中的指令被多次執(zhí)行。 程序中還包括許多對數(shù)據(jù)結(jié)構(gòu)的處理，如對連續(xù)的存儲程序中還包括許多對數(shù)據(jù)結(jié)構(gòu)的處理，如對連續(xù)的存儲 空間空間數(shù)組的訪問，往往局限于很小的范圍內(nèi)。數(shù)組的訪問，往往局限于很小的范圍內(nèi)。 7.1.1 7.1.1 虛擬存儲器的引入虛擬存儲器的引入-1 所以局限性表現(xiàn)

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

5、序在一即程序在一 段時間內(nèi)所訪問的地址，可能集中在一定的范圍內(nèi)，其典型段時間內(nèi)所訪問的地址，可能集中在一定的范圍內(nèi)，其典型 原因是程序是順序執(zhí)行的。原因是程序是順序執(zhí)行的。 （2）虛擬存儲器的定義虛擬存儲器的定義 根據(jù)局部性原理，一個作業(yè)在運行之前，沒有必要把全根據(jù)局部性原理，一個作業(yè)在運行之前，沒有必要把全 部作業(yè)裝入內(nèi)存，而僅將那些當(dāng)前要運行的那部分頁面或段，部作業(yè)裝入內(nèi)存，而僅將那些當(dāng)前要運行的那部分頁面或段， 先裝入內(nèi)存便可啟動運行，其余部分暫時留在磁盤上。先裝入內(nèi)存便可啟動運行，其余部分暫時留在磁盤上。 7.1.1 7.1.1 虛擬存儲器的引入虛擬存儲器的引入-2 程序在運行時如果它

6、所要訪問的頁（段）已調(diào)入內(nèi)存，程序在運行時如果它所要訪問的頁（段）已調(diào)入內(nèi)存， 便可繼續(xù)執(zhí)行下去；但如果程序所要訪問的頁（段）尚未調(diào)便可繼續(xù)執(zhí)行下去；但如果程序所要訪問的頁（段）尚未調(diào) 入內(nèi)存（稱為缺頁或缺段），此時程序應(yīng)利用入內(nèi)存（稱為缺頁或缺段），此時程序應(yīng)利用OSOS所提供的請所提供的請 求調(diào)頁（段）功能，將它們調(diào)入內(nèi)存，以使進(jìn)程能繼續(xù)執(zhí)行求調(diào)頁（段）功能，將它們調(diào)入內(nèi)存，以使進(jìn)程能繼續(xù)執(zhí)行 下去。下去。 如果此時內(nèi)存已滿，無法再裝入新的頁（段），則還須如果此時內(nèi)存已滿，無法再裝入新的頁（段），則還須 再利用頁（段）的置換功能，將內(nèi)存中暫時不用的頁（段）再利用頁（段）的置換功能，將內(nèi)存中

7、暫時不用的頁（段） 調(diào)出至磁盤上，騰出足夠的內(nèi)存空間后，再將所要訪問的頁調(diào)出至磁盤上，騰出足夠的內(nèi)存空間后，再將所要訪問的頁 （段）調(diào)入內(nèi)存，使程序繼續(xù)執(zhí)行下去。這樣，便可使一個（段）調(diào)入內(nèi)存，使程序繼續(xù)執(zhí)行下去。這樣，便可使一個 大的用戶程序在較小的內(nèi)存空間中運行；也可使內(nèi)存中同時大的用戶程序在較小的內(nèi)存空間中運行；也可使內(nèi)存中同時 裝入更多的進(jìn)程并發(fā)執(zhí)行。從用戶角度看，該系統(tǒng)所具有的裝入更多的進(jìn)程并發(fā)執(zhí)行。從用戶角度看，該系統(tǒng)所具有的 內(nèi)存容量，將比實際內(nèi)存容量大得多，人們把這樣的存儲器內(nèi)存容量，將比實際內(nèi)存容量大得多，人們把這樣的存儲器 稱為虛擬存儲器。稱為虛擬存儲器。 7.1.1 7.

8、1.1 虛擬存儲器的引入虛擬存儲器的引入-3 虛擬存儲器是具有請求調(diào)入功能和置換功能，能僅把作業(yè)的虛擬存儲器是具有請求調(diào)入功能和置換功能，能僅把作業(yè)的 一部分裝入內(nèi)存便可運行作業(yè)的存儲器系統(tǒng)，它能從邏輯上一部分裝入內(nèi)存便可運行作業(yè)的存儲器系統(tǒng)，它能從邏輯上 對內(nèi)存容量進(jìn)行擴充的一種虛擬的存儲器系統(tǒng)對內(nèi)存容量進(jìn)行擴充的一種虛擬的存儲器系統(tǒng)。其邏輯容量。其邏輯容量 由內(nèi)存和外存容量之和所決定，其運行速度接近于內(nèi)存速度，由內(nèi)存和外存容量之和所決定，其運行速度接近于內(nèi)存速度， 而每位的成本卻又接近于外存?？梢?，虛擬存儲技術(shù)是一種而每位的成本卻又接近于外存?？梢姡摂M存儲技術(shù)是一種 性能非常優(yōu)越的存儲器

9、管理技術(shù)，故被廣泛地應(yīng)用于大、中、性能非常優(yōu)越的存儲器管理技術(shù)，故被廣泛地應(yīng)用于大、中、 小型機器和微型機中。小型機器和微型機中。 7.1.2 虛擬存儲虛擬存儲器器實現(xiàn)方式實現(xiàn)方式 1.1.請求分頁系統(tǒng)：請求分頁系統(tǒng)： 它是在分頁系統(tǒng)的基礎(chǔ)上，增加了請求調(diào)頁功能和頁面置換它是在分頁系統(tǒng)的基礎(chǔ)上，增加了請求調(diào)頁功能和頁面置換 功能所形成的頁式虛擬存儲系統(tǒng)。它允許只裝入若干頁（而功能所形成的頁式虛擬存儲系統(tǒng)。它允許只裝入若干頁（而 非全部程序）的用戶程序和數(shù)據(jù)，就可以啟動運行，以后再非全部程序）的用戶程序和數(shù)據(jù)，就可以啟動運行，以后再 通過調(diào)頁功能和頁面置換功能，陸續(xù)把將要運行的頁面調(diào)入通過調(diào)頁功

10、能和頁面置換功能，陸續(xù)把將要運行的頁面調(diào)入 內(nèi)存，同時把暫不運行的頁面置換到外存上，置換時以頁面內(nèi)存，同時把暫不運行的頁面置換到外存上，置換時以頁面 為單位。為單位。 2.2.請求分段系統(tǒng)：請求分段系統(tǒng)： 它是在分段系統(tǒng)的基礎(chǔ)上，增加了請求調(diào)段和分段置換功能它是在分段系統(tǒng)的基礎(chǔ)上，增加了請求調(diào)段和分段置換功能 所形成的段式虛擬存儲系統(tǒng)。它允許只裝入若干段（而非全所形成的段式虛擬存儲系統(tǒng)。它允許只裝入若干段（而非全 部段）的用戶程序和數(shù)據(jù)，就可以啟動運行，以后再通過調(diào)部段）的用戶程序和數(shù)據(jù)，就可以啟動運行，以后再通過調(diào) 段功能和置換功能將不運行的段調(diào)出，同時調(diào)入將要運行的段功能和置換功能將不運行

11、的段調(diào)出，同時調(diào)入將要運行的 段，置換以段為單位。段，置換以段為單位。 3.請求段頁式系統(tǒng)請求段頁式系統(tǒng)：它是在段頁式系統(tǒng)的基礎(chǔ)上，增加了請求調(diào)它是在段頁式系統(tǒng)的基礎(chǔ)上，增加了請求調(diào) 頁和頁面置換功能所形成的段頁式虛擬存儲系統(tǒng)。頁和頁面置換功能所形成的段頁式虛擬存儲系統(tǒng)。 7.1.3 虛擬存儲器的特征虛擬存儲器的特征 多次性多次性：指一個作業(yè)被分成多次調(diào)入內(nèi)存運行，即在作業(yè)運指一個作業(yè)被分成多次調(diào)入內(nèi)存運行，即在作業(yè)運 行時沒有必要將其全部裝入，只須將當(dāng)前要運行的那部分程行時沒有必要將其全部裝入，只須將當(dāng)前要運行的那部分程 序和數(shù)據(jù)裝入內(nèi)存即可。多次性是虛擬存儲器最重要的特征。序和數(shù)據(jù)裝入內(nèi)存

12、即可。多次性是虛擬存儲器最重要的特征。 對換性對換性：指允許在作業(yè)的運行過程中在內(nèi)存和外存的對換區(qū)指允許在作業(yè)的運行過程中在內(nèi)存和外存的對換區(qū) 之間換進(jìn)、換出。之間換進(jìn)、換出。 虛擬性虛擬性：指能夠從邏輯上擴充內(nèi)存容量，使用戶所看到的內(nèi)指能夠從邏輯上擴充內(nèi)存容量，使用戶所看到的內(nèi) 存容量遠(yuǎn)大于實際內(nèi)存容量。存容量遠(yuǎn)大于實際內(nèi)存容量。 離散性離散性: 作業(yè)以離散的方式分配到內(nèi)存中。作業(yè)以離散的方式分配到內(nèi)存中。 7.2 請求分頁存儲管理方式請求分頁存儲管理方式 7.2.1 7.2.1 請求分頁中的硬件支持請求分頁中的硬件支持 它是在純分頁系統(tǒng)的基礎(chǔ)上，增加了請求調(diào)頁功能、頁它是在純分頁系統(tǒng)的基礎(chǔ)

13、上，增加了請求調(diào)頁功能、頁 面置換功能所形成的頁式虛擬存儲系統(tǒng)，它是目前常用的一面置換功能所形成的頁式虛擬存儲系統(tǒng)，它是目前常用的一 種虛擬存儲器的方式。種虛擬存儲器的方式。 1 1請求分頁的頁表機制請求分頁的頁表機制 它是在純分頁的頁表機制上形成的，由于只將應(yīng)用程序的一它是在純分頁的頁表機制上形成的，由于只將應(yīng)用程序的一 部分調(diào)入內(nèi)存，還有一部分仍在磁盤上，故需在頁表中再增部分調(diào)入內(nèi)存，還有一部分仍在磁盤上，故需在頁表中再增 加若干項，供程序加若干項，供程序( (數(shù)據(jù)數(shù)據(jù)) )在換進(jìn)、換出時參考。在請求分頁在換進(jìn)、換出時參考。在請求分頁 系統(tǒng)中的每個頁表項如圖所示。系統(tǒng)中的每個頁表項如圖所示

14、。 頁號頁號 物理塊號物理塊號 狀態(tài)位狀態(tài)位P 訪問字段訪問字段A 修改位修改位M 外存地址外存地址 7.2.1 7.2.1 請求分頁中的硬件支持請求分頁中的硬件支持-1-1 其中各字段說明如下：其中各字段說明如下： 狀態(tài)位（存在位狀態(tài)位（存在位P P）：）：用于指示該頁是否已調(diào)入內(nèi)存，供程用于指示該頁是否已調(diào)入內(nèi)存，供程 序訪問時參考。序訪問時參考。 訪問字段訪問字段A A：用于記錄本頁在一段時間內(nèi)被訪問的次數(shù)，或用于記錄本頁在一段時間內(nèi)被訪問的次數(shù)，或 最近已有多長時間未被訪問，提供給置換算法選擇換出頁面最近已有多長時間未被訪問，提供給置換算法選擇換出頁面 時參考。時參考。 修改位修改位M

15、 M：表示該頁在調(diào)入內(nèi)存后是否被修改過。由于內(nèi)存表示該頁在調(diào)入內(nèi)存后是否被修改過。由于內(nèi)存 中的每一頁都在外存上保留一份副本，因此，若未被修改，中的每一頁都在外存上保留一份副本，因此，若未被修改， 在置換該頁時就不需將該頁寫回到外存上，以減少系統(tǒng)的開在置換該頁時就不需將該頁寫回到外存上，以減少系統(tǒng)的開 銷和啟動磁盤的次數(shù)；若已被修改，則必須將該頁重寫到外銷和啟動磁盤的次數(shù)；若已被修改，則必須將該頁重寫到外 存上，以保證外存中所保留的始終是最新副本。存上，以保證外存中所保留的始終是最新副本。 外存地址外存地址：用于指出該頁在外存上的地址，通常是物理塊號，：用于指出該頁在外存上的地址，通常是物理塊

16、號， 供調(diào)入該頁時使用。供調(diào)入該頁時使用。 請求分頁中的硬件支持請求分頁中的硬件支持-2-2 2 2缺頁中斷機構(gòu)缺頁中斷機構(gòu) 在請求分頁系統(tǒng)中，每當(dāng)所要訪問的頁面不在內(nèi)存時，在請求分頁系統(tǒng)中，每當(dāng)所要訪問的頁面不在內(nèi)存時， 便要產(chǎn)生一缺頁中斷，請求便要產(chǎn)生一缺頁中斷，請求OSOS將所缺頁調(diào)入內(nèi)存。與一般中將所缺頁調(diào)入內(nèi)存。與一般中 斷的主要區(qū)別在于：斷的主要區(qū)別在于： 缺頁中斷在指令執(zhí)行期間產(chǎn)生和處理中斷信號，而一般中斷缺頁中斷在指令執(zhí)行期間產(chǎn)生和處理中斷信號，而一般中斷 在一條指令執(zhí)行完后檢查和處理中斷信號。在一條指令執(zhí)行完后檢查和處理中斷信號。 缺頁中斷返回到該指令的開始重新執(zhí)行該指令，而

17、一般中斷缺頁中斷返回到該指令的開始重新執(zhí)行該指令，而一般中斷 返回到該指令的下一條指令執(zhí)行。返回到該指令的下一條指令執(zhí)行。 一條指令在執(zhí)行期間，可能產(chǎn)生多次缺頁中斷。一條指令在執(zhí)行期間，可能產(chǎn)生多次缺頁中斷。 3 3地址變換機構(gòu)地址變換機構(gòu) 請求分頁系統(tǒng)中的地址變換機構(gòu)，是在分頁系統(tǒng)的地址請求分頁系統(tǒng)中的地址變換機構(gòu)，是在分頁系統(tǒng)的地址 變換機構(gòu)的基礎(chǔ)上，再為實現(xiàn)虛擬存儲器而增加了某些功能變換機構(gòu)的基礎(chǔ)上，再為實現(xiàn)虛擬存儲器而增加了某些功能 所形成的，如產(chǎn)生和處理缺頁中斷，以及從內(nèi)存中換出一頁所形成的，如產(chǎn)生和處理缺頁中斷，以及從內(nèi)存中換出一頁 的功能等等，下圖的功能等等，下圖給給出了請求分頁

18、系統(tǒng)的地址變換過程。出了請求分頁系統(tǒng)的地址變換過程。 開始（程序請求訪問一頁開始（程序請求訪問一頁) 越界中斷越界中斷 CPU檢索快表檢索快表 頁表項是否在快表中？頁表項是否在快表中？ 訪問頁表訪問頁表 頁是否在內(nèi)存中？頁是否在內(nèi)存中？ 修改快表修改快表 修改訪問位和修改位修改訪問位和修改位 形成物理地址形成物理地址 地址變換結(jié)束地址變換結(jié)束 保留保留CPU現(xiàn)場現(xiàn)場 從外存中找到缺頁從外存中找到缺頁 頁號頁號頁表長度？頁表長度？ 內(nèi)存滿否？內(nèi)存滿否？ 選擇一頁換出選擇一頁換出 該頁是否被修改？該頁是否被修改？ 將該頁寫回外存將該頁寫回外存 將一頁從外存換入內(nèi)存將一頁從外存換入內(nèi)存 修改頁表修改

19、頁表 CPU從外存讀缺頁從外存讀缺頁 啟動啟動I/O硬件硬件 否否 是是 是是 否否 是是 否否 是是 否否 恢復(fù)恢復(fù)CPU現(xiàn)場現(xiàn)場 把把指令指針指向發(fā)生指令指針指向發(fā)生 中斷的指令開始并返回中斷的指令開始并返回 7.2.2 7.2.2 頁面分配頁面分配 1.1.最少物理塊數(shù)最少物理塊數(shù) 在為進(jìn)程分配物理塊時，首先應(yīng)該考慮的問題是：能保在為進(jìn)程分配物理塊時，首先應(yīng)該考慮的問題是：能保 證進(jìn)程能正常運行所需的最少物理塊數(shù)（稱為最小物理塊證進(jìn)程能正常運行所需的最少物理塊數(shù)（稱為最小物理塊 數(shù)）。若系統(tǒng)為某進(jìn)程所分配的物理塊數(shù)少于此值時，進(jìn)程數(shù)）。若系統(tǒng)為某進(jìn)程所分配的物理塊數(shù)少于此值時，進(jìn)程 將無

20、法運行，這取決于指令的格式、功能和尋址方式。將無法運行，這取決于指令的格式、功能和尋址方式。 2. 2. 頁面的分配和置換策略頁面的分配和置換策略 在請求分頁系統(tǒng)中，可采取兩種分配策略在請求分頁系統(tǒng)中，可采取兩種分配策略固定和可固定和可 變分配策略。在進(jìn)行置換時，也可采取兩種策略變分配策略。在進(jìn)行置換時，也可采取兩種策略全局置全局置 換和局部置換。于是可組合成以下三種策略。換和局部置換。于是可組合成以下三種策略。 固定分配局部置換策略固定分配局部置換策略：它基于進(jìn)程的類型（交互型或批處它基于進(jìn)程的類型（交互型或批處 理型等），或根據(jù)程序員、系統(tǒng)管理員的建議，為每個進(jìn)程理型等），或根據(jù)程序員、系

21、統(tǒng)管理員的建議，為每個進(jìn)程 分配一固定頁數(shù)的內(nèi)存空間，在整個運行期間都不再改變。分配一固定頁數(shù)的內(nèi)存空間，在整個運行期間都不再改變。 如果進(jìn)程在運行中發(fā)現(xiàn)缺頁，則只能從該進(jìn)程在內(nèi)存的固定如果進(jìn)程在運行中發(fā)現(xiàn)缺頁，則只能從該進(jìn)程在內(nèi)存的固定 頁面中選出一頁換出，然后再調(diào)入另一頁，保證分配給該進(jìn)頁面中選出一頁換出，然后再調(diào)入另一頁，保證分配給該進(jìn) 程的內(nèi)存空間不變。程的內(nèi)存空間不變。 7.2.2 7.2.2 頁面分配頁面分配-1-1 可變分配全局置換策略可變分配全局置換策略：系統(tǒng)為每個進(jìn)程分配一定數(shù)目的物：系統(tǒng)為每個進(jìn)程分配一定數(shù)目的物 理塊，而理塊，而OSOS本身也保持一個空閑物理塊隊列。當(dāng)某進(jìn)

22、程發(fā)現(xiàn)本身也保持一個空閑物理塊隊列。當(dāng)某進(jìn)程發(fā)現(xiàn) 缺頁時，由系統(tǒng)從空閑物理塊隊列中，取出一物理塊分配給缺頁時，由系統(tǒng)從空閑物理塊隊列中，取出一物理塊分配給 該進(jìn)程，并將欲調(diào)入的缺頁裝入其中。當(dāng)空閑物理塊隊列中該進(jìn)程，并將欲調(diào)入的缺頁裝入其中。當(dāng)空閑物理塊隊列中 的物理塊用完時，的物理塊用完時，OSOS才能從內(nèi)存中選擇一頁調(diào)出，該頁可能才能從內(nèi)存中選擇一頁調(diào)出，該頁可能 是系統(tǒng)中任一進(jìn)程的頁。是系統(tǒng)中任一進(jìn)程的頁。 可變分配局部置換可變分配局部置換：根據(jù)進(jìn)程的類型或程序員的要求，為每：根據(jù)進(jìn)程的類型或程序員的要求，為每 個進(jìn)程分配一定數(shù)目的內(nèi)存空間；但當(dāng)某進(jìn)程發(fā)生缺頁時，個進(jìn)程分配一定數(shù)目的內(nèi)存

23、空間；但當(dāng)某進(jìn)程發(fā)生缺頁時， 只允許從該進(jìn)程在內(nèi)存的頁面中選出一頁換出，而不影響其只允許從該進(jìn)程在內(nèi)存的頁面中選出一頁換出，而不影響其 它進(jìn)程的運行。它進(jìn)程的運行。 7.2.2 7.2.2 頁面分配頁面分配-2-2 3 3頁面分配算法頁面分配算法 在采用固定分配策略時，可采用以下幾種物理塊分配方在采用固定分配策略時，可采用以下幾種物理塊分配方 法：法： 平均分配算法平均分配算法：將系統(tǒng)中所有可供分配的物理塊，平：將系統(tǒng)中所有可供分配的物理塊，平 均分配給各個進(jìn)程。均分配給各個進(jìn)程。 按比例分配算法按比例分配算法：這是根據(jù)進(jìn)程的大小按比例分配物：這是根據(jù)進(jìn)程的大小按比例分配物 理塊。理塊。 考慮

24、優(yōu)先權(quán)的分配算法考慮優(yōu)先權(quán)的分配算法：該方法是把內(nèi)存中可供分配：該方法是把內(nèi)存中可供分配 的所有物理塊分成兩部分：一部分按比例分配給各進(jìn)的所有物理塊分成兩部分：一部分按比例分配給各進(jìn) 程；另一部分則根據(jù)各進(jìn)程的優(yōu)先權(quán)，適當(dāng)?shù)卦黾悠涑?；另一部分則根據(jù)各進(jìn)程的優(yōu)先權(quán)，適當(dāng)?shù)卦黾悠?相應(yīng)份額后，分配給各進(jìn)程。相應(yīng)份額后，分配給各進(jìn)程。 7.2.3 7.2.3 頁面調(diào)入策略頁面調(diào)入策略 為能使進(jìn)程運行，必須事先將一部分要執(zhí)行的程序和數(shù)據(jù)調(diào)入為能使進(jìn)程運行，必須事先將一部分要執(zhí)行的程序和數(shù)據(jù)調(diào)入 內(nèi)存。內(nèi)存。 1. 1. 調(diào)入頁面的時機調(diào)入頁面的時機 為了將進(jìn)程運行時所缺的頁面調(diào)入內(nèi)存，可采取策略有：為

25、了將進(jìn)程運行時所缺的頁面調(diào)入內(nèi)存，可采取策略有： 預(yù)調(diào)頁策略預(yù)調(diào)頁策略是一種主動的缺頁調(diào)入策略，即將那些預(yù)計在不是一種主動的缺頁調(diào)入策略，即將那些預(yù)計在不 久的將來會被訪問的程序或數(shù)據(jù)所在的頁面，預(yù)先調(diào)入內(nèi)存。久的將來會被訪問的程序或數(shù)據(jù)所在的頁面，預(yù)先調(diào)入內(nèi)存。 由于預(yù)測的準(zhǔn)確率不高（由于預(yù)測的準(zhǔn)確率不高（50%50%），所以這種策略主要用于進(jìn)程），所以這種策略主要用于進(jìn)程 的首次調(diào)入。有的系統(tǒng)將預(yù)調(diào)頁策略用于請求調(diào)頁，例如在的首次調(diào)入。有的系統(tǒng)將預(yù)調(diào)頁策略用于請求調(diào)頁，例如在 VAX/VMSVAX/VMS操作系統(tǒng)中，采用了一種稱為群頁式的調(diào)頁策略，當(dāng)操作系統(tǒng)中，采用了一種稱為群頁式的調(diào)頁策

26、略，當(dāng) 系統(tǒng)將進(jìn)程所請求的頁面調(diào)入內(nèi)存時，也同時將其相鄰的幾系統(tǒng)將進(jìn)程所請求的頁面調(diào)入內(nèi)存時，也同時將其相鄰的幾 個頁面調(diào)入內(nèi)存。個頁面調(diào)入內(nèi)存。 請求調(diào)頁策略請求調(diào)頁策略是指當(dāng)進(jìn)程在運行中發(fā)生缺頁時，就立即提出是指當(dāng)進(jìn)程在運行中發(fā)生缺頁時，就立即提出 請求，由系統(tǒng)將缺頁調(diào)入內(nèi)存。目前的虛擬存儲器中，大多請求，由系統(tǒng)將缺頁調(diào)入內(nèi)存。目前的虛擬存儲器中，大多 采用此策略。但這種策略在調(diào)頁時須花費較大的系統(tǒng)開銷，采用此策略。但這種策略在調(diào)頁時須花費較大的系統(tǒng)開銷， 如需頻繁啟動磁盤如需頻繁啟動磁盤I/OI/O。 7.2.3 7.2.3 頁面調(diào)入策略頁面調(diào)入策略-2-2 2.2.從何處調(diào)入頁面從何處

27、調(diào)入頁面 在虛擬存儲系統(tǒng)中，外存（硬盤）常常被分成兩在虛擬存儲系統(tǒng)中，外存（硬盤）常常被分成兩 部分；文件區(qū)（用于存放文件）和對換區(qū)（用于存放部分；文件區(qū)（用于存放文件）和對換區(qū)（用于存放 對換頁面）。通常，對換區(qū)的磁盤對換頁面）。通常，對換區(qū)的磁盤I/OI/O速度比文件區(qū)要速度比文件區(qū)要 高。高。 每當(dāng)進(jìn)程發(fā)出缺頁請求時，系統(tǒng)應(yīng)從何處將缺頁調(diào)入每當(dāng)進(jìn)程發(fā)出缺頁請求時，系統(tǒng)應(yīng)從何處將缺頁調(diào)入 內(nèi)存呢？內(nèi)存呢？ 1.1.對換區(qū)足夠大，全部從對換區(qū)調(diào)入對換區(qū)足夠大，全部從對換區(qū)調(diào)入 2.2.對換區(qū)不足夠大，未修改頁面從文件區(qū)調(diào)入，修改對換區(qū)不足夠大，未修改頁面從文件區(qū)調(diào)入，修改 的頁面從對換區(qū)調(diào)入

28、。的頁面從對換區(qū)調(diào)入。 3.3.在在UNIXUNIX系統(tǒng)中，對于從未運行過的頁面，都應(yīng)從硬系統(tǒng)中，對于從未運行過的頁面，都應(yīng)從硬 盤文件區(qū)調(diào)入；對于曾經(jīng)運行過而又被換出的頁面，盤文件區(qū)調(diào)入；對于曾經(jīng)運行過而又被換出的頁面， 可以從對換區(qū)調(diào)入；對于共享頁面，該頁面可能已由可以從對換區(qū)調(diào)入；對于共享頁面，該頁面可能已由 其它進(jìn)程調(diào)入內(nèi)存，此時就無需再從對換區(qū)調(diào)入。其它進(jìn)程調(diào)入內(nèi)存，此時就無需再從對換區(qū)調(diào)入。 7.3 7.3 頁面置換算法頁面置換算法 （Page Replacement AlgorithmsPage Replacement Algorithms） 在進(jìn)程運行過程中，如果發(fā)生缺頁，此時

29、內(nèi)存中在進(jìn)程運行過程中，如果發(fā)生缺頁，此時內(nèi)存中 又無空閑塊時，為了保證進(jìn)程能正常運行，就必須又無空閑塊時，為了保證進(jìn)程能正常運行，就必須 從內(nèi)存中調(diào)出一頁程序或數(shù)據(jù)送磁盤的對換區(qū)。但從內(nèi)存中調(diào)出一頁程序或數(shù)據(jù)送磁盤的對換區(qū)。但 將哪個頁面調(diào)出，則須根據(jù)一定的頁面置換算法來將哪個頁面調(diào)出，則須根據(jù)一定的頁面置換算法來 確定。置換算法的好壞將直接影響系統(tǒng)的性能，不確定。置換算法的好壞將直接影響系統(tǒng)的性能，不 適當(dāng)?shù)乃惴赡軙?dǎo)致進(jìn)程發(fā)生適當(dāng)?shù)乃惴赡軙?dǎo)致進(jìn)程發(fā)生“抖動抖動” （Thrashing)Thrashing)。即即頁面頻繁調(diào)進(jìn)調(diào)出，以致一個進(jìn)頁面頻繁調(diào)進(jìn)調(diào)出，以致一個進(jìn) 程在運行中把大

30、部分時間花費在完成頁面置換的工程在運行中把大部分時間花費在完成頁面置換的工 作上，我們稱該進(jìn)程發(fā)生了作上，我們稱該進(jìn)程發(fā)生了“抖動抖動”。 從理論上講，應(yīng)將那些以后不再被訪問的頁面從理論上講，應(yīng)將那些以后不再被訪問的頁面 換出，或把那些在較長時間內(nèi)不會再被訪問的頁面換出，或把那些在較長時間內(nèi)不會再被訪問的頁面 換出。下面介紹幾種常用的置換算法。換出。下面介紹幾種常用的置換算法。 7.3 7.3 頁面置換算法頁面置換算法-1-1 7.3.1 7.3.1 最佳（最佳（OptimalOptimal）置換算法置換算法 它是一種理想化的算法，性能最好，但在實際上難于實它是一種理想化的算法，性能最好，但在

31、實際上難于實 現(xiàn)。現(xiàn)。即選擇那些永不使用的，或者是在最長時間內(nèi)不再被訪即選擇那些永不使用的，或者是在最長時間內(nèi)不再被訪 問的頁面置換出去問的頁面置換出去。但是要確定哪一個頁面是未來最長時間。但是要確定哪一個頁面是未來最長時間 內(nèi)不再被訪問的，目前來說是很難估計的，所以該算法通常內(nèi)不再被訪問的，目前來說是很難估計的，所以該算法通常 用來評價其它算法。用來評價其它算法。 例：假定系統(tǒng)為某進(jìn)程分配了三個物理塊，并考慮有以下的例：假定系統(tǒng)為某進(jìn)程分配了三個物理塊，并考慮有以下的 頁面號引用串：頁面號引用串：7 7，0 0，l l，2 2，0 0，3 3，0 0，4 4，2 2，3 3，0 0，3 3，

32、2 2， l l，2 2，0 0，l l，7 7，0 0，1 1。如下圖如下圖所示，所示，進(jìn)程運行時先將進(jìn)程運行時先將7 7，0 0， 1 1三個頁面裝入內(nèi)存。當(dāng)進(jìn)程訪問頁面三個頁面裝入內(nèi)存。當(dāng)進(jìn)程訪問頁面2 2時，產(chǎn)生缺頁中斷，時，產(chǎn)生缺頁中斷， 此時此時OSOS根據(jù)最佳置換算法，頁面根據(jù)最佳置換算法，頁面7 7將在第將在第1818次才被訪問，是三次才被訪問，是三 頁中將最久不被訪問的頁面，所以被淘汰。接著訪問頁面頁中將最久不被訪問的頁面，所以被淘汰。接著訪問頁面0 0時，時， 發(fā)現(xiàn)已在內(nèi)存中，而不會產(chǎn)生缺頁中斷，以此類推。發(fā)現(xiàn)已在內(nèi)存中，而不會產(chǎn)生缺頁中斷，以此類推。從從圖可圖可 以看出，

33、采用最佳置換算法，只發(fā)生了以看出，采用最佳置換算法，只發(fā)生了6 6次頁面置換。次頁面置換。 7.3.1 7.3.1 最佳（最佳（OptimalOptimal）置換算法）置換算法-1-1 頁 面 引用 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 7 7 7 2 2 2 2 2 2 2 2 2 2 2 2 2 2 7 7 7 0 0 0 0 0 0 4 4 4 0 0 0 0 0 0 0 0 0 0 物 理 塊 1 1 1 3 3 3 3 3 3 3 3 1 1 1 1 1 1 1 缺頁x x x xxxxxx 發(fā)生了6次面置換，9次缺頁中斷。 7.3.2 7.

34、3.2 先進(jìn)先出（先進(jìn)先出（FIFOFIFO）置換算法置換算法 該算法總是淘汰最先進(jìn)入內(nèi)存的頁面，即選擇在內(nèi)存中駐留時 間最久的頁面予以淘汰。該算法實現(xiàn)簡單，只須把一個進(jìn)程已 調(diào)入內(nèi)存的頁面，按先后次序鏈接成一個隊列，并設(shè)置一個指 針即可。它是一種最直觀，性能最差的算法，它有 BELADY 異常 現(xiàn)象：對頁面訪問序列 A B C D A B E A B C D E ，物理塊從 3塊增加到4塊，缺頁次數(shù)增加。 頁面 引用 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 7 0 1 2 2 3 0 4 2 3 0 0 0 1 2 2 2 7 0 1 7 0 1 1

35、2 3 0 4 2 3 3 3 0 1 1 1 2 7 0 物理 塊 7 0 0 1 2 3 0 4 2 2 2 3 0 0 0 1 2 7 缺頁 x x x xx x x x x xx xx x x 發(fā)生了12次頁面置換，缺頁次數(shù)15次。 該 算 法 是 選 擇 最 近 最 久 未 使 用 的 頁 面 予 以 淘 汰 ， 系 統(tǒng) 在 每 個 頁 面 設(shè) 置 一 個 訪 問 字 段 ， 用 以 記 錄 這 個 頁 面 自 上 次 被 訪 問 以 來 所 經(jīng) 歷 的 時 間 T， 當(dāng) 要 淘 汰 一 個 頁 面 時 ， 選 擇T 最 大 的 頁 面 。 但 在 實 現(xiàn) 時 需 要 硬 件 的 支

36、 持 （ 寄 存 器 或 棧 ） 。 利 用LRU 算 法 對 上 例 進(jìn) 行 頁 面 置 換 的 結(jié) 果 如 下 ： 頁面引 用 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 物 理 塊 7 0 1 2 2 3 0 4 2 2 0 3 3 1 2 0 1 7 缺 頁x x x xxx x x xxxx 發(fā) 生 了9次 面 置 換 ， 缺 頁 次 數(shù)12次 7.3.3 7.3.3 最近最久未使用置換算法最近

37、最久未使用置換算法 LRULRU（Least Recently UsedLeast Recently Used） 這是一種 LRU 的近似算法。該算法為每個頁面設(shè)置一位訪問 位，將內(nèi)存中的所有頁面都通過鏈接指針鏈成一個循環(huán)隊列。 當(dāng)某頁被訪問時，其訪問位置“1” 。在選擇一頁淘汰時，就檢 查其訪問位，如果是“0” ，就選擇該頁換出；若為“1” ，則重 新置為“0” ，暫不換出該頁，在循環(huán)隊列中檢查下一個頁面， 直到訪問位為“0”的頁面為止。由于該算法只有一位訪問位， 只能用它表示該頁是否已經(jīng)使用過，而置換時是將未使用過的 頁面換出去，所以把該算法稱為最近未用算法。 7.3.4 Clock7.3

38、.4 Clock置換算法置換算法 （最近未用算法（最近未用算法NRCNRC（Not Recently UsedNot Recently Used） ClockClock置換算法置換算法-1-1 塊號頁號訪問位指針替換指針 0 1 2404 3 42 10 6 5 6 5601 7 7112 指 向 最 近 被 替 換的 4 號頁所 在塊的塊號 2 26 被 調(diào) 入 頁 的 頁 號為 6 簡單 Clock 置換算法的數(shù)據(jù)結(jié)構(gòu)存儲器分塊表 7.3.5 LFU最少使用置換算法最少使用置換算法 該算法選擇最近時期使用最少的頁面作為淘汰 頁。需要為內(nèi)存中每個頁面設(shè)置一個移位寄存 器來記錄頁面被訪問的頻率

39、。每次訪問某頁時， 將該頁對應(yīng)的移位寄存器最高位置成1，每個 一定時間右移一位。移位寄存器值最小的就是 使用最少的頁面。 7.3.6 頁面緩沖算法頁面緩沖算法 （Page Buffering Algorithm） 該算法在頁面分配時，采用可變分配和局部置換的方式該算法在頁面分配時，采用可變分配和局部置換的方式。首首 先為每個作業(yè)分配一個工作集（進(jìn)程在一段時間內(nèi)運行，要先為每個作業(yè)分配一個工作集（進(jìn)程在一段時間內(nèi)運行，要 用到的部分頁面的集合），每個工作集的塊數(shù)相對固定的用到的部分頁面的集合），每個工作集的塊數(shù)相對固定的 （在一段時間內(nèi)），塊號是可變的。系統(tǒng)自己也保留一部分（在一段時間內(nèi)），塊號

40、是可變的。系統(tǒng)自己也保留一部分 存儲塊作為頁面緩沖，并把頁面緩沖組織成兩個隊列：空閑存儲塊作為頁面緩沖，并把頁面緩沖組織成兩個隊列：空閑 隊列和已修改的頁面隊列。隊列和已修改的頁面隊列。 經(jīng)過一段時間的運行，經(jīng)過一段時間的運行，OS把一些暫時不訪問的頁面（在每個把一些暫時不訪問的頁面（在每個 工作集采用工作集采用FIFO算法進(jìn)行選擇）放入頁面緩沖，如果頁面未算法進(jìn)行選擇）放入頁面緩沖，如果頁面未 被修改，就將它直接放入空閑隊列中；否則，便放入已修改被修改，就將它直接放入空閑隊列中；否則，便放入已修改 的頁面隊列中。注意，這時頁面在內(nèi)存中并未做物理上的移的頁面隊列中。注意，這時頁面在內(nèi)存中并未做

41、物理上的移 動，而只是將頁表中的表項移到上述兩個隊列之一中。圖中動，而只是將頁表中的表項移到上述兩個隊列之一中。圖中 是頁面緩沖算法的某個狀態(tài)，有三個作業(yè)（是頁面緩沖算法的某個狀態(tài)，有三個作業(yè)（A，B，C）的工的工 作集和頁面緩沖的兩個隊列。作集和頁面緩沖的兩個隊列。 7.3.6 頁面緩沖算法頁面緩沖算法-1 A B C 頁面緩沖頁面緩沖 已修改的頁面隊列已修改的頁面隊列 空閑隊列空閑隊列 頁面修改位頁面修改位=“1” 頁面修改位頁面修改位=“0” 當(dāng)進(jìn)程要訪問頁面時，先到工作集中去找，如果找到就可以當(dāng)進(jìn)程要訪問頁面時，先到工作集中去找，如果找到就可以 直接訪問。否則，到頁面緩沖的兩個隊列中去

42、找，如果找到直接訪問。否則，到頁面緩沖的兩個隊列中去找，如果找到 也可以直接訪問，并將該頁在頁表中的表項鏈接到工作集隊也可以直接訪問，并將該頁在頁表中的表項鏈接到工作集隊 列的末尾，而把工作集隊列的隊首的頁表表項鏈入頁面緩沖列的末尾，而把工作集隊列的隊首的頁表表項鏈入頁面緩沖 的兩個隊列中。的兩個隊列中。 40 3 19 22 61 20 24 41 5 23 7 12 13 30 10 1 32 14 9 43 39 8 16 工作集 頁面緩沖算法頁面緩沖算法-2 如果還是沒找到，則啟動磁盤如果還是沒找到，則啟動磁盤I/OI/O，將缺頁讀入空閑隊列第將缺頁讀入空閑隊列第 一個物理塊中（利用一

43、個物理塊中（利用FIFOFIFO），），并將該頁在頁表中的表項鏈接并將該頁在頁表中的表項鏈接 到工作集隊列的末尾。到工作集隊列的末尾。 利用這種方法可使已修改的頁面和未修改的頁面，都仍留在利用這種方法可使已修改的頁面和未修改的頁面，都仍留在 內(nèi)存中。當(dāng)該進(jìn)程要再次訪問這些頁面時，便只須花較小的內(nèi)存中。當(dāng)該進(jìn)程要再次訪問這些頁面時，便只須花較小的 開銷就可以使這些頁面又返回到該進(jìn)程的工作集中。當(dāng)在頁開銷就可以使這些頁面又返回到該進(jìn)程的工作集中。當(dāng)在頁 面緩沖的已修改頁面達(dá)到一定數(shù)量時，例如面緩沖的已修改頁面達(dá)到一定數(shù)量時，例如6464個頁面，可以個頁面，可以 將它們一起寫回到磁盤，從而顯著地減少

44、了磁盤將它們一起寫回到磁盤，從而顯著地減少了磁盤I/OI/O的操作的操作 次數(shù)。次數(shù)。 頁面緩沖算法是一個較簡單的近似于頁面緩沖算法是一個較簡單的近似于LRULRU頁面緩沖算法，它頁面緩沖算法，它 與與LRULRU和和ClockClock置換算法相比，無需硬件的支持，又大大減少置換算法相比，無需硬件的支持，又大大減少 了頁面置換的開銷。在性能上又比了頁面置換的開銷。在性能上又比FIFOFIFO要好，有效地改善了要好，有效地改善了 請求式分頁系統(tǒng)的性能。著名的請求式分頁系統(tǒng)的性能。著名的VAXVAXVMSVMS和和Windows NTWindows NT便是便是 使用這種算法，而在使用這種算法，

45、而在 MACHMACH操作系統(tǒng)實現(xiàn)中，只是它沒有區(qū)操作系統(tǒng)實現(xiàn)中，只是它沒有區(qū) 分已修改頁面和末修改頁面。分已修改頁面和末修改頁面。 (6)性能分析性能分析 1.1.缺頁率對有效訪問時間的影響缺頁率對有效訪問時間的影響 在請求分頁系統(tǒng)中，假設(shè)存儲器的訪問時間ma為100ns（一般 為10ns幾百ns），缺頁率為p，缺頁中斷時間為25ms，則有 效訪問時間就可以表示為： 有效訪問時間 =（1一p）ma十p缺頁中斷時間 =（1一p）0.1十p25000 = 0.1十24999.9 p 由上式可以看出，有效訪問時間與缺頁率成正比。如果缺頁 率為0.1%，則有效訪問時間約為25s，與直接訪問存儲器的

46、有效訪問時間（0.1s ）相比的時間，程序執(zhí)行的性能將受 到嚴(yán)重的影響。如果希望在缺頁時，僅使有效訪問時間延長 不超過10%，則可計算出缺頁率p=0.0000004，由此得出，要 求在2500000次的訪問中才發(fā)生一頁缺頁，即請求分頁方式應(yīng) 保持非常低的缺頁率；否則，將使程序執(zhí)行速度受到嚴(yán)重影 響。此外，提高磁盤I/O的速度，對改善請求分頁系統(tǒng)的性能 至關(guān)重要。為此，應(yīng)選用高速磁盤和高速磁盤接口。 性能分析性能分析-1-1 2. 2. 工作集工作集 程序在運行中所產(chǎn)生的缺頁情況，會影響程序的運行速度及 系統(tǒng)性能，而缺頁率的高低又將是與每個進(jìn)程所占用的物理 塊數(shù)目有關(guān)。這里我們簡單地分析一下應(yīng)為

47、每個進(jìn)程分配多 少個物理塊，才能把缺頁率保持在一個合理的水平上。 缺頁率與進(jìn)程所分得的物理塊數(shù)目有密切關(guān)系。下圖說明了 的缺頁率與進(jìn)程分得的物理塊數(shù)目N之間的關(guān)系曲線。從圖中 可以看出，缺頁率隨著所分得的物理塊數(shù)目的減少而遞增， 并在所分到的物理塊數(shù)目較少處，出現(xiàn)一個拐點。在拐點上 限以左時，隨著分到的物理塊數(shù)目的增加，缺頁率明顯地減 少；而過了拐點，在下限以右時，隨著分到的物理塊數(shù)目的 增加，卻對缺頁率的改善并不明顯。所以，為進(jìn)程分配的物 理塊數(shù)，應(yīng)取在該曲線的拐點左右。 性能分析性能分析-2-2 缺頁率 拐點 所分得的物理塊數(shù) 工作集的理論是在1968年由Denning提出來的。他認(rèn)為，程

48、序 在運行時對頁面的訪問是不均勻的，即往往在某段時間內(nèi)的 訪問僅局限于較少的若干個頁面，如果能夠預(yù)知程序在某段 時間間隔內(nèi)要訪問哪些頁面，并能將它們提前調(diào)入內(nèi)存，將 會大大地降低缺頁率，從而減少置換工作，提高 CPU的利用 率。 性能分析性能分析-3-3 所謂工作集是指，在某段時間間隔（所謂工作集是指，在某段時間間隔（）里，進(jìn)程實際要里，進(jìn)程實際要 訪問的頁面的集合。訪問的頁面的集合。 Denning認(rèn)為，雖然程序只需有少量的 幾頁在內(nèi)存就可以運行，但為了使程序能夠有效地運行，較 少地產(chǎn)生缺頁、就必須使程序的工作集全部在內(nèi)存中。把某 進(jìn)程在時間t的工作集記為w（t，），把變量稱為工作集 “窗口

49、尺寸”（Windows Size）。正確選擇工作集窗口（） 的大小，對存儲器的有效利用和系統(tǒng)吞吐量的提高，都將產(chǎn) 生重要的影響。 在Windows NT中，虛擬存儲管理程序（Virtual Memory Manager)為每一個進(jìn)程分配固定數(shù)量的頁面，并且這個數(shù)目 可以進(jìn)行動態(tài)的調(diào)整。那么這個數(shù)量如何確定？又如何進(jìn)行 動態(tài)的調(diào)整呢？這個數(shù)目就是由每個進(jìn)程的工作集來確定， 并且根據(jù)主存的負(fù)荷和進(jìn)程的缺頁情況動態(tài)地調(diào)整其工作集。 性能分析性能分析-4-4 其具體的作法是：一個進(jìn)程在創(chuàng)建時就指定了一個最小工 作集，該工作集的大小是保證進(jìn)程運行在主存中應(yīng)有的最小 頁面數(shù)。但在主存負(fù)荷不太大（頁面不太滿

50、）時，虛存管理 程序還允許進(jìn)程擁有盡可能多的頁面作為其最大工作集。當(dāng) 主存負(fù)荷發(fā)生變化時，如空閑頁架（塊）不多了，虛存管理 程序就使用“自動調(diào)整工作集”的技術(shù)來增加主存中可用的 自由頁架。方法是檢查主存中的每個進(jìn)程，將它當(dāng)前工作集 大小與其最小工作集進(jìn)行比較。如果大于最小值，則從它們 的工作集中移去一些頁面作為主存自由頁面，可為其它進(jìn)程 所使用。若主存自由頁面仍然太小，則不斷進(jìn)行檢查，直到 每個進(jìn)程的工作集都達(dá)到最小值為止。 當(dāng)每個工作集都已達(dá)到最小值時，虛存管理程序跟蹤進(jìn)程的 缺頁數(shù)量，根據(jù)內(nèi)存中自由頁面數(shù)量可以適當(dāng)增加其工作集 的大小。 （四）請求分段存儲管理方式（四）請求分段存儲管理方式

51、 請求分段系統(tǒng)在分段系統(tǒng)的基礎(chǔ)上實現(xiàn)的虛擬存儲器，是以分 段為單位進(jìn)行換入、換出的。在程序運行之前只要先調(diào)入若 干個分段（不必調(diào)入所有的分段），便可啟動運行。當(dāng)所訪 問的段不在內(nèi)存時可請求OS將所缺的段調(diào)入內(nèi)存。為實現(xiàn)請 求分段存儲管理方式，同樣需要一定的硬件支持和相應(yīng)的軟 件，有段表機制、缺段中斷機構(gòu)以及地址變換機構(gòu)。 （1 1）請求分段中的硬件支持）請求分段中的硬件支持 1 1段表機制段表機制 在請求分段式管理中在段表中增加若干項，以供程序在調(diào)進(jìn)、 調(diào)出時參考。請求分段的段表項如下： 段 段 段的 存取 訪問 修改 存在 增補 外存 名 長 基址 方式 字段A 位M 位P 位 起址 請求分

52、段中的硬件支持請求分段中的硬件支持-1-1 在段表項中，除了段名(號)、段長、段在內(nèi)存的起始地址外， 還增加了以下幾項： 存取方式：用于標(biāo)識本分段的存取屬性是只執(zhí)行、只讀，還 是允許讀寫。 訪問字段A：用于記錄該段被訪問的頻繁程度。 修改位M：用于表示該段進(jìn)入內(nèi)存后，是否已被修改過。 存在位P：說明本段是否已調(diào)入內(nèi)存。 增補位：用于表示本段在運行過程中，是否進(jìn)行過動態(tài)增長。 外存起址：指示本段在外存中的起始地址，即起始盤塊號。 2.2.缺段中斷機構(gòu)缺段中斷機構(gòu) 在請求分段系統(tǒng)中，采用的是請求調(diào)段策略。即當(dāng)進(jìn)程所要 訪問的段未調(diào)入內(nèi)存時，便由缺段中斷機構(gòu)產(chǎn)生一缺段中斷 信號，由缺斷中斷處理程序?qū)?/p>

53、所需的段調(diào)入內(nèi)存。缺段中斷 的處理過程如下圖： 請求分段中的硬件支持請求分段中的硬件支持-1-1 拼接后形成合適拼接后形成合適 大小的空閑區(qū)大小的空閑區(qū) 淘汰一個或幾個段淘汰一個或幾個段 以形成合適大小的以形成合適大小的 空閑區(qū)空閑區(qū) 虛段不在內(nèi)存中虛段不在內(nèi)存中 阻塞請求的進(jìn)程阻塞請求的進(jìn)程 內(nèi)存中有合適的空閑區(qū)？內(nèi)存中有合適的空閑區(qū)？ 從外存讀入段從外存讀入段 修改段表和內(nèi)存空閑鏈修改段表和內(nèi)存空閑鏈 喚醒請求進(jìn)程喚醒請求進(jìn)程 返回返回 空閑區(qū)大小總和能否滿足？空閑區(qū)大小總和能否滿足？ N N 請求分段中的硬件支持請求分段中的硬件支持-2-2 3。地址變換機構(gòu)地址變換機構(gòu) 請求分段系統(tǒng)中的

54、地址變換機構(gòu)，是在分段系統(tǒng)地址變換機構(gòu) 的基礎(chǔ)上形成的。由于被訪問的段并非全在內(nèi)存，所以在地 址變換時，若發(fā)現(xiàn)所要訪問的段不在內(nèi)存時，必須先將所缺 的段調(diào)入內(nèi)存，并修改了段表之后，才能再利用段表進(jìn)行地 址變換。為此，在地址變換機制中又增加了某些功能，如缺 段中斷的請求及其處理等。 請求分段中的硬件支持請求分段中的硬件支持-3-3 4。段的動態(tài)鏈接。段的動態(tài)鏈接 經(jīng)過編釋或匯編得到的一組目標(biāo)程序需經(jīng)鏈接程序，連接 裝配成一個一維的線性連續(xù)地址空間，這一過程稱為靜態(tài)鏈靜態(tài)鏈 接接，但是這種連接裝配過程既復(fù)雜又費時，還經(jīng)常發(fā)生許多 被連接好的摸塊在作業(yè)運行過程中根本不用，而造成連接時 的機時和主存空

55、間的浪費，所以最好能采用什么時候用到那 一段責(zé)連接該段的方法，這種方法稱為動態(tài)連接方法。段的段的 動態(tài)鏈接是指動態(tài)鏈接是指“在一個程序運行開始時，只將主程序裝配好在一個程序運行開始時，只將主程序裝配好 并調(diào)入主存，其它各段的裝配是在主程序段運行過程中逐步并調(diào)入主存，其它各段的裝配是在主程序段運行過程中逐步 進(jìn)行的，每當(dāng)需要調(diào)用一個新段時，再將該段裝配好，并與進(jìn)行的，每當(dāng)需要調(diào)用一個新段時，再將該段裝配好，并與 主程序段連接。主程序段連接。在分段存儲管理環(huán)境中，由于邏輯地址空間 是二維的，每段有自己的段名，因而實現(xiàn)動態(tài)連接比較容易。 5。請求段頁請求段頁式地址變換機構(gòu)式地址變換機構(gòu)如下圖： 啟動

56、要處理指令啟動要處理指令 計算有效地址計算有效地址 訪問地址訪問地址v= (s,p,d) S段表長嗎？段表長嗎？ 段連接了嗎？段連接了嗎？ 段在主存嗎？段在主存嗎？ P頁表長嗎？頁表長嗎？ 訪問類型合訪問類型合 法嗎？法嗎？ 頁在主存嗎？頁在主存嗎？ 缺頁中斷處理缺頁中斷處理 執(zhí)行下一條指令執(zhí)行下一條指令 訪問該地址訪問該地址 完成指令完成指令 形成主存地址形成主存地址 出錯處理出錯處理 越界中斷處理越界中斷處理 連接中斷處理連接中斷處理 缺段中斷處理缺段中斷處理 允 許 動 態(tài)允 許 動 態(tài) 增增 長嗎？長嗎？ 出錯處理出錯處理 N N N N N N N （2）分段共享與保護(hù)分段共享與保護(hù)

57、 分段存儲管理方式實現(xiàn)分段的共享和保護(hù)只須在每個進(jìn)程的 段表中，用相應(yīng)的表項來指向共享段在內(nèi)存中的起始地址。 為了實現(xiàn)分段共享，應(yīng)配置相應(yīng)的共享段表，用來對共享段 進(jìn)行操作。 1.1.共享段表共享段表 在系統(tǒng)中，用共享段表來記錄了每一個共享段的段號和段長、 內(nèi)存始址、存在位等信息，并記錄共享此分段的每個進(jìn)程的 情況。共享段表如下圖所示。 分段共享與保護(hù)分段共享與保護(hù)-1-1 其中： 共享進(jìn)程計數(shù)器COUNT：記錄有多少個進(jìn)程需要共享該分段。 存取控制字段：說明不同的進(jìn)程對該分段不同的存取權(quán)限。 段號：對于同一個共享段，不同的進(jìn)程可以使用不同的段號 去共享該段。 段名 段長 內(nèi)存起址 狀態(tài) 外存

58、起址 共享進(jìn)程計數(shù)器 COUNT 狀態(tài) 進(jìn)程名 進(jìn)程號 段號 存取控制 分段共享與保護(hù)分段共享與保護(hù)-2-2 2.共享段的分配和回收共享段的分配和回收 （1）分配 首次請求：分配空閑分區(qū)，調(diào)入內(nèi)存，初始化 進(jìn)程段表，在共享段表中增加一表項，初始化 數(shù)據(jù)， count=1，在共享段表中添加調(diào)用進(jìn)程信 息 非首次請求， count+1，在共享段表中添加調(diào)用 進(jìn)程信息。 （2）回收 count=count-1，取消調(diào)用進(jìn)程信息，若count=0, 則在共享段表中取消該共享段表項，同時釋放 它所占內(nèi)存。 分段共享與保護(hù)分段共享與保護(hù)-3-3 3、分段保護(hù)、分段保護(hù) 越界檢查越界檢查 存取控制檢查存取控

59、制檢查 段表中有“存取控制”字段規(guī)定訪問權(quán)限：只讀、只執(zhí) 行、讀寫。 環(huán)保護(hù)機構(gòu)環(huán)保護(hù)機構(gòu) 低編號環(huán)具有高優(yōu)先訪問權(quán)。一般OS內(nèi)核處于0環(huán)，系 統(tǒng)服務(wù)和某些重要實用程序占據(jù)中間環(huán)，而一般程序處 于外環(huán)。規(guī)則 （1）一個程序可以訪問處于相同環(huán)或較低特權(quán)環(huán)中的數(shù) 據(jù)。 （2） ）一個程序可以調(diào)用處于相同環(huán)或較高特權(quán)環(huán)中 的服務(wù) 7.6.3 Windows 2000/XP的內(nèi)存空間分配的內(nèi)存空間分配 1Windows 2000/XP系統(tǒng)用戶空間分配系統(tǒng)用戶空間分配 在Windows 2000/XP系統(tǒng)中有三種應(yīng)用程序內(nèi)存管理方法。 （1）虛頁內(nèi)存分配：最適合管理大型對象數(shù)據(jù)或動態(tài)結(jié)構(gòu)數(shù)組。 在虛頁內(nèi)

60、存分配中，內(nèi)存管理器用一組虛地址描述符（virtual address descriptor）來描述每個進(jìn)程的虛地址空間狀態(tài)，包括地 址范圍、該地址范圍是共享還是私有、子進(jìn)程能否繼承該地址 范圍、地址范圍內(nèi)應(yīng)用于頁面的保護(hù)限制等。為了快速查找虛 地址，虛地址描述符構(gòu)造成一棵二叉樹，如圖7.18所示。當(dāng)進(jìn) 程保留地址空間或映射一個內(nèi)存區(qū)域時，內(nèi)存管理器創(chuàng)建一個 虛地址描述符來保存分配請求提供的信息。當(dāng)線程首次訪問一 個地址時，內(nèi)存管理器必須為包含此地址的頁面創(chuàng)建一個頁表 項，并將虛地址描述符中相應(yīng)的虛地址空間狀態(tài)寫入頁表項中。 如果該地址沒有落在虛地址描述符所覆蓋的地址范圍，或所在 的地址范圍僅