操作系統(tǒng) Operating System課件

1、操作系統(tǒng) Operating System第第4 4章章 存儲(chǔ)管理存儲(chǔ)管理4.1 4.1 存儲(chǔ)管理的原理存儲(chǔ)管理的原理 4.2 4.2 連續(xù)分配存儲(chǔ)管理連續(xù)分配存儲(chǔ)管理 4.3 4.3 離散分配存儲(chǔ)管理離散分配存儲(chǔ)管理4.4 4.4 內(nèi)核主存管理內(nèi)核主存管理4.5 4.5 虛擬存儲(chǔ)技術(shù)虛擬存儲(chǔ)技術(shù)4.6 4.6 虛擬頁(yè)式存儲(chǔ)管理虛擬頁(yè)式存儲(chǔ)管理 4.7 4.7 虛擬段式存儲(chǔ)管理虛擬段式存儲(chǔ)管理4.8 4.8 存儲(chǔ)管理實(shí)例存儲(chǔ)管理實(shí)例4.5 4.5 虛擬存儲(chǔ)技術(shù)虛擬存儲(chǔ)技術(shù)4.5.1 4.5.1 程序局部性原理程序局部性原理 4.5.2 4.5.2 虛擬存儲(chǔ)的實(shí)現(xiàn)虛擬存儲(chǔ)的實(shí)現(xiàn)&虛擬內(nèi)存

2、技術(shù)(Virtual Memory)(Virtual Memory)誕生于1961年。&廣泛使用是從上個(gè)世紀(jì)70年代初以后，今天幾乎所有的操作系統(tǒng)都采用虛擬內(nèi)存技術(shù)來(lái)管理內(nèi)存。&這是一種利用虛擬存儲(chǔ)器來(lái)邏輯擴(kuò)充物理內(nèi)存的技術(shù)。其基本思想是用軟硬件技術(shù)把內(nèi)存與外存這兩級(jí)存儲(chǔ)器當(dāng)成一級(jí)用軟硬件技術(shù)把內(nèi)存與外存這兩級(jí)存儲(chǔ)器當(dāng)成一級(jí)存儲(chǔ)器來(lái)用，從而給用戶提供了一個(gè)比內(nèi)存也比任何應(yīng)用程存儲(chǔ)器來(lái)用，從而給用戶提供了一個(gè)比內(nèi)存也比任何應(yīng)用程序大得多的虛擬存儲(chǔ)器，使得用戶編程時(shí)再也不用考慮內(nèi)存序大得多的虛擬存儲(chǔ)器，使得用戶編程時(shí)再也不用考慮內(nèi)存大小的限制了，給用戶編程帶來(lái)極大的方便。大小的限制

3、了，給用戶編程帶來(lái)極大的方便。&虛擬內(nèi)存技術(shù)的實(shí)現(xiàn)也利用了自動(dòng)覆蓋和交換技術(shù)。 4.5.1 4.5.1 程序局部性原理程序局部性原理&1.1.局部性原理局部性原理(principle of locality)： 指程序在執(zhí)行過(guò)程中的一個(gè)較短時(shí)期內(nèi)，所執(zhí)行的指令地址和指令的操作數(shù)地址，分別局限于一定區(qū)域。&2.2.局部性主要表現(xiàn)：局部性主要表現(xiàn)：F時(shí)間局部性：時(shí)間局部性：是指一段指令在某一時(shí)間段內(nèi)會(huì)被反是指一段指令在某一時(shí)間段內(nèi)會(huì)被反復(fù)執(zhí)行。即程序某一部分的數(shù)據(jù)或指令被重復(fù)性地復(fù)執(zhí)行。即程序某一部分的數(shù)據(jù)或指令被重復(fù)性地訪問(wèn)，它們對(duì)應(yīng)于程序結(jié)構(gòu)中的循環(huán)、子程序、常訪問(wèn)，它

4、們對(duì)應(yīng)于程序結(jié)構(gòu)中的循環(huán)、子程序、常用到的變量及數(shù)據(jù)等用到的變量及數(shù)據(jù)等 ；F空間局部性空間局部性：是指一旦某一個(gè)存儲(chǔ)單元被訪問(wèn)，那是指一旦某一個(gè)存儲(chǔ)單元被訪問(wèn)，那么它附近的單元也將很快被訪問(wèn)。這對(duì)應(yīng)于程序結(jié)么它附近的單元也將很快被訪問(wèn)。這對(duì)應(yīng)于程序結(jié)構(gòu)中的順序執(zhí)行的指令、線性數(shù)據(jù)結(jié)構(gòu)以及在相鄰構(gòu)中的順序執(zhí)行的指令、線性數(shù)據(jù)結(jié)構(gòu)以及在相鄰位置存放的數(shù)據(jù)或變量等。而程序中的分支和調(diào)用位置存放的數(shù)據(jù)或變量等。而程序中的分支和調(diào)用子程序只是將程序的訪問(wèn)空間從一處移到另外一處，子程序只是將程序的訪問(wèn)空間從一處移到另外一處，仍具有局部性。仍具有局部性。F排他性：排他性：程序運(yùn)行不但體現(xiàn)在時(shí)間、空間的局部

5、性，還體現(xiàn)在某些程序段執(zhí)行的排他性。即程序設(shè)計(jì)者編程時(shí)要考慮程序執(zhí)行時(shí)所能遇到的各種情況，但具體到一次程序的執(zhí)行，并不會(huì)發(fā)生所有的狀況。因而某些程序段在進(jìn)程整個(gè)運(yùn)行期間，可能因而某些程序段在進(jìn)程整個(gè)運(yùn)行期間，可能根本不使用，如出錯(cuò)處理、分支語(yǔ)句等。根本不使用，如出錯(cuò)處理、分支語(yǔ)句等。因而，沒(méi)有用到的程序段就不必調(diào)入內(nèi)存。另外，有些程序段僅執(zhí)行一次，以后就再也不會(huì)用到，這樣的程序段也沒(méi)有必要一直占用內(nèi)存空間。 &綜上所述：綜上所述：程序只要裝入內(nèi)存一部分就可以運(yùn)行，程序只要裝入內(nèi)存一部分就可以運(yùn)行，當(dāng)用到不在內(nèi)存的部分時(shí)，再將其裝入內(nèi)存。當(dāng)用到不在內(nèi)存的部分時(shí)，再將其裝入內(nèi)存。換句換句話

6、就是說(shuō)程序全部裝入內(nèi)存并不是程序運(yùn)行的必要話就是說(shuō)程序全部裝入內(nèi)存并不是程序運(yùn)行的必要條件。條件。 4.5.2 4.5.2 虛擬存儲(chǔ)的實(shí)現(xiàn)虛擬存儲(chǔ)的實(shí)現(xiàn)1.1.虛擬存儲(chǔ)技術(shù)虛擬存儲(chǔ)技術(shù)如果把程序部分裝入內(nèi)存，其余大部分放在外存，而程序又能運(yùn)如果把程序部分裝入內(nèi)存，其余大部分放在外存，而程序又能運(yùn)行，這樣我們就擁有了一個(gè)比有限的實(shí)際內(nèi)存空間大得多的、邏行，這樣我們就擁有了一個(gè)比有限的實(shí)際內(nèi)存空間大得多的、邏輯的虛擬內(nèi)存空間。輯的虛擬內(nèi)存空間。即用大容量的外存來(lái)模擬內(nèi)存，這種存儲(chǔ)模即用大容量的外存來(lái)模擬內(nèi)存，這種存儲(chǔ)模式就稱之為虛擬存儲(chǔ)技術(shù)。式就稱之為虛擬存儲(chǔ)技術(shù)。 2.2.虛擬技術(shù)實(shí)現(xiàn)的關(guān)鍵虛擬

7、技術(shù)實(shí)現(xiàn)的關(guān)鍵(1)怎樣才能發(fā)現(xiàn)欲執(zhí)行的指令或數(shù)據(jù)不在內(nèi)存怎樣才能發(fā)現(xiàn)欲執(zhí)行的指令或數(shù)據(jù)不在內(nèi)存? 簡(jiǎn)單有效方法就是進(jìn)行標(biāo)識(shí)簡(jiǎn)單有效方法就是進(jìn)行標(biāo)識(shí)(2)怎樣將不在內(nèi)存的部分調(diào)入進(jìn)來(lái)怎樣將不在內(nèi)存的部分調(diào)入進(jìn)來(lái)。 通常系統(tǒng)采用中斷技術(shù)完成調(diào)入工作。通常系統(tǒng)采用中斷技術(shù)完成調(diào)入工作。(3)在內(nèi)存中的作業(yè)如何組織？在內(nèi)存中的作業(yè)如何組織？一個(gè)進(jìn)程可被分為多次調(diào)入內(nèi)存，這樣很難保證進(jìn)程在內(nèi)存中占一個(gè)進(jìn)程可被分為多次調(diào)入內(nèi)存，這樣很難保證進(jìn)程在內(nèi)存中占據(jù)一個(gè)連續(xù)的空間，實(shí)際上進(jìn)程在內(nèi)存中是離散存儲(chǔ)的。據(jù)一個(gè)連續(xù)的空間，實(shí)際上進(jìn)程在內(nèi)存中是離散存儲(chǔ)的。 虛擬技術(shù)進(jìn)一步說(shuō)明虛擬技術(shù)進(jìn)一步說(shuō)明因而因而系統(tǒng)要

8、提供必要的硬件支持系統(tǒng)要提供必要的硬件支持，如虛擬頁(yè)式，如虛擬頁(yè)式存儲(chǔ)中的頁(yè)表機(jī)制、缺頁(yè)中斷機(jī)構(gòu)以及相應(yīng)存儲(chǔ)中的頁(yè)表機(jī)制、缺頁(yè)中斷機(jī)構(gòu)以及相應(yīng)的地址變換機(jī)構(gòu)。的地址變換機(jī)構(gòu)。虛擬存儲(chǔ)技術(shù)是虛擬存儲(chǔ)技術(shù)是將內(nèi)存與外存有機(jī)地結(jié)合在一將內(nèi)存與外存有機(jī)地結(jié)合在一起，從而得到一個(gè)容量很大的虛擬空間。起，從而得到一個(gè)容量很大的虛擬空間。使使用戶感到有一個(gè)很大的內(nèi)存，不用再考慮內(nèi)用戶感到有一個(gè)很大的內(nèi)存，不用再考慮內(nèi)存的容量限制。存的容量限制。虛存雖然比內(nèi)存要大得多，但不可能無(wú)限大，虛存雖然比內(nèi)存要大得多，但不可能無(wú)限大，其大小要受到外存空間的限制以及其大小要受到外存空間的限制以及CPU地址地址所能表示范圍

9、的限制。所能表示范圍的限制。&大程序：可在較小的可用內(nèi)存中執(zhí)行較大的用戶程序；&大的用戶空間：提供給用戶可用的虛擬內(nèi)存空間通常大于物理內(nèi)存(real memory)&并發(fā)：可在內(nèi)存中容納更多程序并發(fā)執(zhí)行；&易于開(kāi)發(fā)：與覆蓋技術(shù)比較，不必影響編程時(shí)的程序結(jié)構(gòu)3.3.引入虛擬存儲(chǔ)技術(shù)的好處引入虛擬存儲(chǔ)技術(shù)的好處總?cè)萘坎怀^(guò)物理內(nèi)存和外存交換區(qū)容量之和。其總?cè)萘坎怀^(guò)物理內(nèi)存和外存交換區(qū)容量之和。其運(yùn)行速度接近于內(nèi)存，每位的成本又接近于外存，運(yùn)行速度接近于內(nèi)存，每位的成本又接近于外存，是一種性能非常優(yōu)越的存儲(chǔ)管理技術(shù)是一種性能非常優(yōu)越的存儲(chǔ)管理技術(shù) 4. 4. 虛擬存

10、儲(chǔ)技術(shù)的特征虛擬存儲(chǔ)技術(shù)的特征&不連續(xù)性不連續(xù)性：物理內(nèi)存分配的不連續(xù)，虛擬地址空間使用的不連續(xù)（數(shù)據(jù)段和棧段之間的空閑空間，共享段和動(dòng)態(tài)鏈接庫(kù)占用的空間）&部分交換：部分交換：與交換技術(shù)相比較，虛擬存儲(chǔ)的調(diào)入和調(diào)出是對(duì)部分虛擬地址空間進(jìn)行的；&大空間：大空間：通過(guò)物理內(nèi)存和快速外存相結(jié)合，提供大范圍的虛擬地址空間虛擬存儲(chǔ)技術(shù)的種類：虛擬存儲(chǔ)技術(shù)的種類：虛擬頁(yè)式虛擬段式虛擬段頁(yè)式4.6 4.6 虛擬頁(yè)式存儲(chǔ)管理虛擬頁(yè)式存儲(chǔ)管理 4.6.1 4.6.1 虛擬頁(yè)式存儲(chǔ)的實(shí)現(xiàn)虛擬頁(yè)式存儲(chǔ)的實(shí)現(xiàn) 4.6.2 4.6.2 頁(yè)面分配策略頁(yè)面分配策略 4.6.3 4.6.3 頁(yè)面置換

11、方法頁(yè)面置換方法4.6.4 4.6.4 虛擬頁(yè)式存儲(chǔ)的優(yōu)缺點(diǎn)虛擬頁(yè)式存儲(chǔ)的優(yōu)缺點(diǎn)返回&系統(tǒng)自動(dòng)地將作業(yè)的地址空間分頁(yè)，將系統(tǒng)的主存空間分塊，頁(yè)與塊等大小，在作業(yè)運(yùn)行前，只把初始需要的一部分頁(yè)面裝入內(nèi)存塊里，運(yùn)行中需要訪問(wèn)自己地址空間中的但當(dāng)前不在內(nèi)存的頁(yè)面時(shí)產(chǎn)生缺頁(yè)中斷，由缺頁(yè)中斷服務(wù)程序?qū)⑺璧捻?yè)面調(diào)入內(nèi)存，若此時(shí)內(nèi)存中沒(méi)有空閑物理塊安置請(qǐng)求調(diào)入的新頁(yè)面，則系統(tǒng)按預(yù)定的置換策略自動(dòng)選擇一個(gè)或一些在內(nèi)存的頁(yè)面，把它們換出到外存。&這里的請(qǐng)求調(diào)入和置換功能請(qǐng)求調(diào)入和置換功能都是比實(shí)分頁(yè)存儲(chǔ)管理增加的內(nèi)容，是實(shí)現(xiàn)虛擬存儲(chǔ)的主要功能。 4.6.1 4.6.1 虛擬頁(yè)式存儲(chǔ)的實(shí)現(xiàn)虛擬頁(yè)

12、式存儲(chǔ)的實(shí)現(xiàn) &標(biāo)記某頁(yè)是否在內(nèi)存，用于查詢標(biāo)記某頁(yè)是否在內(nèi)存，用于查詢要訪問(wèn)的要訪問(wèn)的頁(yè)在不在內(nèi)存。頁(yè)表如下：頁(yè)在不在內(nèi)存。頁(yè)表如下：頁(yè)號(hào)頁(yè)號(hào) 物理塊號(hào)物理塊號(hào) 狀態(tài)位狀態(tài)位P P 訪問(wèn)位訪問(wèn)位A A 修改位修改位M M外存地址外存地址2.2.頁(yè)表機(jī)制頁(yè)表機(jī)制其中：外存地址指出該頁(yè)在外存的地址，供調(diào)入該頁(yè)時(shí)用；狀態(tài)為指示該頁(yè)是否在內(nèi)存，供程序訪問(wèn)時(shí)用，也是檢查是否缺頁(yè)的標(biāo)志位，如置1表示在內(nèi)存 ；訪問(wèn)位或訪問(wèn)字段則是該頁(yè)被訪問(wèn)過(guò)的標(biāo)志或該頁(yè)被訪問(wèn)過(guò)的次數(shù)；修改位表示該頁(yè)是否被修改過(guò)；存取控制字段則是用來(lái)限制頁(yè)面被安全共享的。 3.3.動(dòng)態(tài)地址變換動(dòng)態(tài)地址變換&在虛擬頁(yè)式存儲(chǔ)中

13、，應(yīng)采用動(dòng)態(tài)地址變換方式，因?yàn)槟骋挥谔摂M頁(yè)式存儲(chǔ)中，應(yīng)采用動(dòng)態(tài)地址變換方式，因?yàn)槟骋挥麍?zhí)行的指令可能不在內(nèi)存，只能在指令執(zhí)行之前完成地址變執(zhí)行的指令可能不在內(nèi)存，只能在指令執(zhí)行之前完成地址變換。換。任一作業(yè)都應(yīng)在自己的虛擬地址空間中執(zhí)行，任一作業(yè)都應(yīng)在自己的虛擬地址空間中執(zhí)行，所以要為所以要為用戶作業(yè)設(shè)置一個(gè)虛擬地址指針用戶作業(yè)設(shè)置一個(gè)虛擬地址指針VP，虛擬地址依然是由頁(yè)號(hào)，虛擬地址依然是由頁(yè)號(hào)和頁(yè)內(nèi)偏移地址組成的。和頁(yè)內(nèi)偏移地址組成的。&系統(tǒng)總是執(zhí)行系統(tǒng)總是執(zhí)行VP虛指針?biāo)赶虻闹噶?，為了將虛擬地址虛指針?biāo)赶虻闹噶?，為了將虛擬地址VP變換為對(duì)應(yīng)的實(shí)存地址，因此變換為對(duì)應(yīng)的實(shí)存地址

14、，因此先要查找頁(yè)表。若從頁(yè)表中查先要查找頁(yè)表。若從頁(yè)表中查出此頁(yè)不在內(nèi)存（狀態(tài)位為出此頁(yè)不在內(nèi)存（狀態(tài)位為0），則產(chǎn)生一個(gè)缺頁(yè)中斷。），則產(chǎn)生一個(gè)缺頁(yè)中斷。此時(shí)，此時(shí)，進(jìn)程暫停當(dāng)前指令執(zhí)行，進(jìn)程暫停當(dāng)前指令執(zhí)行，CPU轉(zhuǎn)去執(zhí)行缺頁(yè)中斷處理程序。轉(zhuǎn)去執(zhí)行缺頁(yè)中斷處理程序。若該頁(yè)已在內(nèi)存，若該頁(yè)已在內(nèi)存，則指令的地址映射過(guò)程與頁(yè)式存儲(chǔ)是一樣則指令的地址映射過(guò)程與頁(yè)式存儲(chǔ)是一樣的。即將塊號(hào)和頁(yè)內(nèi)地址相并接形成物理地址的。即將塊號(hào)和頁(yè)內(nèi)地址相并接形成物理地址IP，處理器再，處理器再?gòu)膹腎P中取指令執(zhí)行。中取指令執(zhí)行。4.4.缺頁(yè)中斷缺頁(yè)中斷 no yes no yes yes no 硬 件 部 分 軟

15、 件 部 分 圖 3 24 缺 頁(yè) 中 斷 處 理 流 程 進(jìn) 程 被 創(chuàng) 建后 ， 進(jìn) 入 就 緒隊(duì) 列 進(jìn) 程 被 調(diào) 度 執(zhí)啟 動(dòng) 待 執(zhí) 行 指 令計(jì) 算 虛 頁(yè)號(hào) 與 頁(yè) 內(nèi)地 址 該 頁(yè) 在 內(nèi) 存 ？ 地 址 映 射 執(zhí) 行 下 一 條 指 令 訪 問(wèn) 內(nèi) 存 完 成 該 指令 保 留 當(dāng) 前 進(jìn) 程 現(xiàn) 場(chǎng) 按 某 算 法選 一 頁(yè) 淘汰 調(diào) 入 所 需 頁(yè) 面 該 頁(yè) 已改 過(guò) 調(diào) 整 頁(yè) 表及 空 閑 頁(yè)面 表 恢 復(fù) 被 中斷 進(jìn) 程 現(xiàn)場(chǎng) 把把 該該 頁(yè)頁(yè)寫(xiě)寫(xiě) 回回 外外存存 有 空 閑頁(yè)面嗎 ？ 5.5.缺頁(yè)率缺頁(yè)率&雖然通過(guò)缺頁(yè)中斷將所需要的頁(yè)調(diào)入內(nèi)存，但缺

16、頁(yè)中雖然通過(guò)缺頁(yè)中斷將所需要的頁(yè)調(diào)入內(nèi)存，但缺頁(yè)中斷的頻繁發(fā)生會(huì)嚴(yán)重影響程序執(zhí)行的效率。為了標(biāo)識(shí)斷的頻繁發(fā)生會(huì)嚴(yán)重影響程序執(zhí)行的效率。為了標(biāo)識(shí)缺頁(yè)中斷發(fā)生的頻度，可以引入缺頁(yè)率來(lái)表示。缺頁(yè)中斷發(fā)生的頻度，可以引入缺頁(yè)率來(lái)表示。 &設(shè)進(jìn)程在其執(zhí)行期間共進(jìn)行了設(shè)進(jìn)程在其執(zhí)行期間共進(jìn)行了S S次訪頁(yè)操作，其中成次訪頁(yè)操作，其中成功訪頁(yè)次數(shù)為功訪頁(yè)次數(shù)為A A（訪問(wèn)時(shí)該頁(yè)在主存），不成功的訪頁(yè)（訪問(wèn)時(shí)該頁(yè)在主存），不成功的訪頁(yè)次數(shù)為次數(shù)為B B（即發(fā)生了缺頁(yè)中斷），顯然有：（即發(fā)生了缺頁(yè)中斷），顯然有：S=A+BS=A+B，&則該進(jìn)程的缺頁(yè)率則該進(jìn)程的缺頁(yè)率f f定義為：定義為：f f

17、B/SB/S。&顯然缺頁(yè)率越低越好。顯然缺頁(yè)率越低越好。4.6.2 4.6.2 頁(yè)面分配策略頁(yè)面分配策略&虛擬存儲(chǔ)管理在進(jìn)行頁(yè)面分配時(shí)，要考慮這虛擬存儲(chǔ)管理在進(jìn)行頁(yè)面分配時(shí)，要考慮這樣的問(wèn)題：空閑頁(yè)面如何管理；采用什么樣樣的問(wèn)題：空閑頁(yè)面如何管理；采用什么樣的分配策略；為進(jìn)程分配多少物理塊比較合的分配策略；為進(jìn)程分配多少物理塊比較合適；在什么時(shí)間進(jìn)行頁(yè)面分配等。適；在什么時(shí)間進(jìn)行頁(yè)面分配等。 1.1.空閑頁(yè)面管理空閑頁(yè)面管理&同頁(yè)式存儲(chǔ)管理相似，虛擬存儲(chǔ)方式下的空閑頁(yè)面的管理也可同頁(yè)式存儲(chǔ)管理相似，虛擬存儲(chǔ)方式下的空閑頁(yè)面的管理也可以采用位示圖或空閑頁(yè)面鏈的形式。以采用

18、位示圖或空閑頁(yè)面鏈的形式。&由于主存中所有進(jìn)程的虛擬地址空間之和遠(yuǎn)大于主存空間，因由于主存中所有進(jìn)程的虛擬地址空間之和遠(yuǎn)大于主存空間，因此進(jìn)程執(zhí)行時(shí)常發(fā)生缺頁(yè)中斷，這樣不斷地調(diào)入新頁(yè)，很快就此進(jìn)程執(zhí)行時(shí)常發(fā)生缺頁(yè)中斷，這樣不斷地調(diào)入新頁(yè)，很快就使主存空間飽和。以后再發(fā)生缺頁(yè)時(shí)，要先淘汰一頁(yè)才能裝入使主存空間飽和。以后再發(fā)生缺頁(yè)時(shí)，要先淘汰一頁(yè)才能裝入新頁(yè)，這使得新頁(yè)，這使得缺頁(yè)處理時(shí)間過(guò)長(zhǎng)，減緩了進(jìn)程的執(zhí)行速度，從缺頁(yè)處理時(shí)間過(guò)長(zhǎng)，減緩了進(jìn)程的執(zhí)行速度，從而影響到系統(tǒng)的性能。而影響到系統(tǒng)的性能。&在實(shí)際的系統(tǒng)中，總是維持一定數(shù)量的空閑塊，而不是耗盡所在實(shí)際的系統(tǒng)中，總是維持一定

19、數(shù)量的空閑塊，而不是耗盡所有的空閑塊。即有的空閑塊。即空閑塊數(shù)可以在某一區(qū)間浮動(dòng)空閑塊數(shù)可以在某一區(qū)間浮動(dòng)，一旦空閑塊數(shù)，一旦空閑塊數(shù)小于下限值，系統(tǒng)就進(jìn)行頁(yè)面置換，以釋放出一些空閑塊，使小于下限值，系統(tǒng)就進(jìn)行頁(yè)面置換，以釋放出一些空閑塊，使得總的空閑塊數(shù)不超過(guò)系統(tǒng)規(guī)定的上限值即可。即系統(tǒng)設(shè)置專得總的空閑塊數(shù)不超過(guò)系統(tǒng)規(guī)定的上限值即可。即系統(tǒng)設(shè)置專門(mén)的獨(dú)立進(jìn)程負(fù)責(zé)頁(yè)面置換，以保證鏈表的適當(dāng)規(guī)模。門(mén)的獨(dú)立進(jìn)程負(fù)責(zé)頁(yè)面置換，以保證鏈表的適當(dāng)規(guī)模。2 2 分配策略分配策略&可變分配：可變分配：是指一個(gè)進(jìn)程所擁有的物理塊數(shù)是不定的，這種是指一個(gè)進(jìn)程所擁有的物理塊數(shù)是不定的，這種分配方式稱之為可

20、變分配。分配方式稱之為可變分配。&固定分配固定分配是指為每個(gè)進(jìn)程分配一固定頁(yè)數(shù)的內(nèi)存空間，在整是指為每個(gè)進(jìn)程分配一固定頁(yè)數(shù)的內(nèi)存空間，在整個(gè)運(yùn)行期間都不再改變。個(gè)運(yùn)行期間都不再改變。& 平均分配算法，平均分配算法，是將系統(tǒng)中所有可供分配的物理塊，平均是將系統(tǒng)中所有可供分配的物理塊，平均分配給每一個(gè)進(jìn)程。例如，當(dāng)系統(tǒng)中有分配給每一個(gè)進(jìn)程。例如，當(dāng)系統(tǒng)中有80個(gè)空閑塊，個(gè)空閑塊，4個(gè)進(jìn)個(gè)進(jìn)程時(shí)，每個(gè)進(jìn)程可分得程時(shí)，每個(gè)進(jìn)程可分得20個(gè)物理塊。這種平均分配方式因其個(gè)物理塊。這種平均分配方式因其未考慮各進(jìn)程本身的大小，會(huì)造成事實(shí)上的不公平。如有一未考慮各進(jìn)程本身的大小，會(huì)造成事實(shí)上的不

21、公平。如有一個(gè)進(jìn)程其大小為個(gè)進(jìn)程其大小為100頁(yè)，只分配給它頁(yè)，只分配給它20個(gè)塊，這樣它必將會(huì)個(gè)塊，這樣它必將會(huì)有很高的缺頁(yè)率；而另一個(gè)進(jìn)程只有有很高的缺頁(yè)率；而另一個(gè)進(jìn)程只有10頁(yè)，卻有頁(yè)，卻有10個(gè)塊在閑個(gè)塊在閑置未用。所以在平均的思想下，還要考慮進(jìn)程的大小。置未用。所以在平均的思想下，還要考慮進(jìn)程的大小。& 按比例分配算法，按比例分配算法，根據(jù)進(jìn)程的大小按比例分配空閑塊。設(shè)根據(jù)進(jìn)程的大小按比例分配空閑塊。設(shè)系統(tǒng)中現(xiàn)有系統(tǒng)中現(xiàn)有m個(gè)進(jìn)程、個(gè)進(jìn)程、n個(gè)空閑塊，每個(gè)進(jìn)程擁有的頁(yè)數(shù)為個(gè)空閑塊，每個(gè)進(jìn)程擁有的頁(yè)數(shù)為Si，則系統(tǒng)中所有進(jìn)程頁(yè)數(shù)之和為：則系統(tǒng)中所有進(jìn)程頁(yè)數(shù)之和為： S = S

22、1 + S2 + S3 + + Sm 則為每個(gè)進(jìn)程分配的物理塊數(shù)為：則為每個(gè)進(jìn)程分配的物理塊數(shù)為： Bi = （Si / S） n ，Bi應(yīng)向下取整。應(yīng)向下取整。& 優(yōu)先權(quán)分配算法，優(yōu)先權(quán)分配算法，為優(yōu)先權(quán)高的作業(yè)分配較多的內(nèi)存空間，為優(yōu)先權(quán)高的作業(yè)分配較多的內(nèi)存空間，這樣可以使重要或緊迫的任務(wù)盡快完成。這時(shí)可以將內(nèi)存中這樣可以使重要或緊迫的任務(wù)盡快完成。這時(shí)可以將內(nèi)存中的空閑塊分成兩部分：一部分按比例分配給各進(jìn)程，另一部的空閑塊分成兩部分：一部分按比例分配給各進(jìn)程，另一部分則根據(jù)各進(jìn)程的優(yōu)先權(quán)，適當(dāng)?shù)貫槠湓黾酉鄳?yīng)份額。分則根據(jù)各進(jìn)程的優(yōu)先權(quán)，適當(dāng)?shù)貫槠湓黾酉鄳?yīng)份額。3.3.工作集工作

23、集&(1)(1)為保證進(jìn)程能正常運(yùn)行最少需要多少物理塊。為保證進(jìn)程能正常運(yùn)行最少需要多少物理塊。從理論上講，進(jìn)程只要獲得一個(gè)物理塊就可以運(yùn)行。但是進(jìn)程從理論上講，進(jìn)程只要獲得一個(gè)物理塊就可以運(yùn)行。但是進(jìn)程正常運(yùn)行所需的最少物理塊數(shù)與計(jì)算機(jī)的硬件結(jié)構(gòu)有關(guān)，取正常運(yùn)行所需的最少物理塊數(shù)與計(jì)算機(jī)的硬件結(jié)構(gòu)有關(guān)，取決于指令的格式、功能和尋址方式。決于指令的格式、功能和尋址方式。由于分頁(yè)是系統(tǒng)的行為由于分頁(yè)是系統(tǒng)的行為，可能會(huì)出現(xiàn)下面的情景：可能會(huì)出現(xiàn)下面的情景：由此可見(jiàn)，由此可見(jiàn)，系統(tǒng)應(yīng)保證任一條指令執(zhí)系統(tǒng)應(yīng)保證任一條指令執(zhí)行時(shí)，其所涉及的虛擬地址所在行時(shí)，其所涉及的虛擬地址所在的頁(yè)都應(yīng)在內(nèi)存

24、中。這個(gè)頁(yè)數(shù)就的頁(yè)都應(yīng)在內(nèi)存中。這個(gè)頁(yè)數(shù)就是進(jìn)程所需要的最小塊數(shù)是進(jìn)程所需要的最小塊數(shù)，若系，若系統(tǒng)為進(jìn)程所分配的物理塊數(shù)少于統(tǒng)為進(jìn)程所分配的物理塊數(shù)少于此值時(shí)，進(jìn)程將無(wú)法運(yùn)行。此值時(shí)，進(jìn)程將無(wú)法運(yùn)行。 123456涉及涉及6 6次缺頁(yè)中斷的指令次缺頁(yè)中斷的指令指令指令copy A to B數(shù)據(jù)數(shù)據(jù)A：數(shù)據(jù)數(shù)據(jù)B：工作集定義工作集定義&(2)(2)為使進(jìn)程能有效地工作，應(yīng)為它分配多少物理塊合適為使進(jìn)程能有效地工作，應(yīng)為它分配多少物理塊合適&隨著為每個(gè)進(jìn)程所分配物理塊數(shù)目的減少，將使進(jìn)程執(zhí)行中隨著為每個(gè)進(jìn)程所分配物理塊數(shù)目的減少，將使進(jìn)程執(zhí)行中的缺頁(yè)率提高，導(dǎo)致非生產(chǎn)性開(kāi)銷過(guò)大，

25、從而降低了進(jìn)程的的缺頁(yè)率提高，導(dǎo)致非生產(chǎn)性開(kāi)銷過(guò)大，從而降低了進(jìn)程的執(zhí)行速度，嚴(yán)重時(shí)導(dǎo)致進(jìn)程不能向前推進(jìn)。最少物理塊數(shù)只執(zhí)行速度，嚴(yán)重時(shí)導(dǎo)致進(jìn)程不能向前推進(jìn)。最少物理塊數(shù)只能保證程序能執(zhí)行下去，而不是最合適的塊數(shù)。能保證程序能執(zhí)行下去，而不是最合適的塊數(shù)。&在在19681968年，年，DenningDenning提出了工作集理論。提出了工作集理論。所謂工作集就是進(jìn)程所謂工作集就是進(jìn)程在某段時(shí)間里實(shí)際上要訪問(wèn)的頁(yè)的集合。在某段時(shí)間里實(shí)際上要訪問(wèn)的頁(yè)的集合。依據(jù)程序執(zhí)行時(shí)的依據(jù)程序執(zhí)行時(shí)的局部特性，可以利用程序過(guò)去的行為來(lái)估計(jì)它未來(lái)的行為。局部特性，可以利用程序過(guò)去的行為來(lái)估計(jì)它未來(lái)的行為

26、。故故定義運(yùn)行進(jìn)程在定義運(yùn)行進(jìn)程在t tw w到到t t這個(gè)時(shí)間間隔內(nèi)所訪問(wèn)的頁(yè)的集合這個(gè)時(shí)間間隔內(nèi)所訪問(wèn)的頁(yè)的集合為該進(jìn)程在時(shí)間為該進(jìn)程在時(shí)間t t的工作集，記為的工作集，記為W W（t t，w w）。）。并把變量并把變量w w稱之稱之為為“工作集窗口尺寸工作集窗口尺寸”，工作集中所包含的頁(yè)面數(shù)稱為，工作集中所包含的頁(yè)面數(shù)稱為“工工作集尺寸作集尺寸”，記為，記為|W(t,w)|W(t,w)|。(3)(3)工作集的應(yīng)用工作集的應(yīng)用&工作集工作集W W（t t，w w）是二元函數(shù)，隨）是二元函數(shù)，隨t t、w w的值而改變。的值而改變。首先工作首先工作集與時(shí)間有關(guān)，即不同時(shí)間的工作集其所

27、包含的頁(yè)面可能不集與時(shí)間有關(guān)，即不同時(shí)間的工作集其所包含的頁(yè)面可能不同，其所包含的頁(yè)面?zhèn)€數(shù)也可能不同；同，其所包含的頁(yè)面?zhèn)€數(shù)也可能不同；其次工作集也是工作其次工作集也是工作集窗口尺寸集窗口尺寸w w的函數(shù)，體現(xiàn)在工作集尺寸的函數(shù)，體現(xiàn)在工作集尺寸|W(t,w)|W(t,w)|隨隨w w的增加的增加而變大，即滿足而變大，即滿足|W(t,w)|W(t,w+a)|W(t,w)|W(t,w+a)|，a0a0。&工作集窗口尺寸與缺頁(yè)率關(guān)系密切，工作集窗口尺寸與缺頁(yè)率關(guān)系密切，若若w w增大，工作集尺寸增大，工作集尺寸|W|W|隨之增加（即所含的頁(yè)面數(shù)增多），缺頁(yè)率就會(huì)下降。隨之增加（即所含的頁(yè)面

28、數(shù)增多），缺頁(yè)率就會(huì)下降。倘倘若若w w含蓋了整個(gè)作業(yè)虛擬空間，缺頁(yè)率降為含蓋了整個(gè)作業(yè)虛擬空間，缺頁(yè)率降為0 0，也就失去了虛，也就失去了虛存意義；存意義；反之若反之若w w選取過(guò)小，將引起頻繁缺頁(yè)，導(dǎo)致系統(tǒng)性能選取過(guò)小，將引起頻繁缺頁(yè)，導(dǎo)致系統(tǒng)性能下降。下降。二者之間的關(guān)系可以如圖所示。二者之間的關(guān)系可以如圖所示。&虛存中并不是要取消缺頁(yè)率，而是要使缺頁(yè)率維持在一個(gè)虛存中并不是要取消缺頁(yè)率，而是要使缺頁(yè)率維持在一個(gè)較低的水平上。因此可以取拐點(diǎn)所對(duì)應(yīng)的工作集尺寸作為較低的水平上。因此可以取拐點(diǎn)所對(duì)應(yīng)的工作集尺寸作為分給進(jìn)程的物理塊數(shù)，實(shí)驗(yàn)分析表明，這個(gè)數(shù)應(yīng)是進(jìn)程總分給進(jìn)程的物理塊數(shù)，

29、實(shí)驗(yàn)分析表明，這個(gè)數(shù)應(yīng)是進(jìn)程總頁(yè)面數(shù)的一半。頁(yè)面數(shù)的一半。即一個(gè)進(jìn)程應(yīng)獲得其所需頁(yè)數(shù)一半的空間即一個(gè)進(jìn)程應(yīng)獲得其所需頁(yè)數(shù)一半的空間時(shí)，再進(jìn)入內(nèi)存執(zhí)行時(shí)，再進(jìn)入內(nèi)存執(zhí)行。 缺 頁(yè) 率 f 拐 點(diǎn) 工 作 集 尺 寸 |W | 圖 3 25 缺 頁(yè) 率 與 工 作 集 尺 寸 之 間 的 關(guān) 系 4.4.頁(yè)面調(diào)入時(shí)機(jī)頁(yè)面調(diào)入時(shí)機(jī) & 預(yù)調(diào)頁(yè)策略預(yù)調(diào)頁(yè)策略 &也稱先行調(diào)度，即一頁(yè)面被訪問(wèn)前就已經(jīng)預(yù)先置入也稱先行調(diào)度，即一頁(yè)面被訪問(wèn)前就已經(jīng)預(yù)先置入內(nèi)存，以減少今后的缺頁(yè)率。內(nèi)存，以減少今后的缺頁(yè)率。&主要適于進(jìn)程的許多頁(yè)存放在外存的連續(xù)區(qū)域中的主要適于進(jìn)程的許多頁(yè)存放在外存的連

30、續(xù)區(qū)域中的情況。有的系統(tǒng)結(jié)合請(qǐng)求調(diào)入使用，即每次缺頁(yè)時(shí)情況。有的系統(tǒng)結(jié)合請(qǐng)求調(diào)入使用，即每次缺頁(yè)時(shí)裝入多個(gè)頁(yè)面。裝入多個(gè)頁(yè)面。&優(yōu)點(diǎn)：優(yōu)點(diǎn)：提高調(diào)頁(yè)的提高調(diào)頁(yè)的I/OI/O效率。效率。&缺點(diǎn)：缺點(diǎn)：基于預(yù)測(cè)，若調(diào)入的頁(yè)在以后很少被訪問(wèn)，基于預(yù)測(cè)，若調(diào)入的頁(yè)在以后很少被訪問(wèn)，則效率低。預(yù)調(diào)頁(yè)的成功率僅約則效率低。預(yù)調(diào)頁(yè)的成功率僅約50%50%，常用于程序裝，常用于程序裝入時(shí)的調(diào)頁(yè)。入時(shí)的調(diào)頁(yè)。& 請(qǐng)求調(diào)頁(yè)策略請(qǐng)求調(diào)頁(yè)策略&當(dāng)發(fā)生頁(yè)面故障時(shí)進(jìn)行調(diào)度，即當(dāng)進(jìn)程訪問(wèn)不在當(dāng)發(fā)生頁(yè)面故障時(shí)進(jìn)行調(diào)度，即當(dāng)進(jìn)程訪問(wèn)不在內(nèi)存的頁(yè)面引發(fā)缺頁(yè)中斷時(shí)，由系統(tǒng)根據(jù)這種訪內(nèi)存的頁(yè)面引發(fā)缺頁(yè)

31、中斷時(shí)，由系統(tǒng)根據(jù)這種訪問(wèn)請(qǐng)求把所缺頁(yè)面裝入內(nèi)存。問(wèn)請(qǐng)求把所缺頁(yè)面裝入內(nèi)存。&優(yōu)點(diǎn)：優(yōu)點(diǎn)：由請(qǐng)求調(diào)入策略裝入的頁(yè)一定會(huì)被訪問(wèn)，由請(qǐng)求調(diào)入策略裝入的頁(yè)一定會(huì)被訪問(wèn)，再加之比較容易實(shí)現(xiàn)，故在目前的虛擬存儲(chǔ)器中，再加之比較容易實(shí)現(xiàn)，故在目前的虛擬存儲(chǔ)器中，大多采用此策略。大多采用此策略。&缺點(diǎn)：缺點(diǎn)：每次僅調(diào)入一頁(yè)，增加了磁盤(pán)每次僅調(diào)入一頁(yè)，增加了磁盤(pán)I/OI/O的啟動(dòng)的啟動(dòng)頻率。頻率。&在請(qǐng)求分頁(yè)系統(tǒng)中，常把在請(qǐng)求分頁(yè)系統(tǒng)中，常把外存分為兩部分：一部分外存分為兩部分：一部分是文件區(qū)，用于存放文件；是文件區(qū)，用于存放文件；另一部分是對(duì)換區(qū)，用另一部分是對(duì)換區(qū)，用于存放對(duì)換頁(yè)面

32、。于存放對(duì)換頁(yè)面。通常，對(duì)換區(qū)的磁盤(pán)輸入輸出速通常，對(duì)換區(qū)的磁盤(pán)輸入輸出速度比文件區(qū)的高，這是因?yàn)閷?duì)換區(qū)所規(guī)定的盤(pán)塊要度比文件區(qū)的高，這是因?yàn)閷?duì)換區(qū)所規(guī)定的盤(pán)塊要比文件區(qū)的大得多。比文件區(qū)的大得多。& 從交換區(qū)調(diào)入從交換區(qū)調(diào)入&若系統(tǒng)擁有足夠的對(duì)換區(qū)空間，可在進(jìn)程運(yùn)行前，若系統(tǒng)擁有足夠的對(duì)換區(qū)空間，可在進(jìn)程運(yùn)行前，將與該進(jìn)程有關(guān)的文件拷貝到對(duì)換區(qū)。以后就從對(duì)將與該進(jìn)程有關(guān)的文件拷貝到對(duì)換區(qū)。以后就從對(duì)換區(qū)調(diào)入所需頁(yè)面，以提高調(diào)頁(yè)速度。換區(qū)調(diào)入所需頁(yè)面，以提高調(diào)頁(yè)速度。 5.5.從何處調(diào)入頁(yè)面從何處調(diào)入頁(yè)面 & 從交換區(qū)及文件區(qū)調(diào)入從交換區(qū)及文件區(qū)調(diào)入&若系統(tǒng)缺少

33、足夠的對(duì)換區(qū)空間，則在交換區(qū)中只保存被修若系統(tǒng)缺少足夠的對(duì)換區(qū)空間，則在交換區(qū)中只保存被修改過(guò)的頁(yè)面。因?yàn)槲幢恍薷牡捻?yè)面在文件區(qū)中有副本。因改過(guò)的頁(yè)面。因?yàn)槲幢恍薷牡捻?yè)面在文件區(qū)中有副本。因此凡是沒(méi)被修改的頁(yè)，均從文件區(qū)調(diào)入；而已修改過(guò)的頁(yè)此凡是沒(méi)被修改的頁(yè)，均從文件區(qū)調(diào)入；而已修改過(guò)的頁(yè)面則從交換區(qū)調(diào)入。面則從交換區(qū)調(diào)入。& UNIX方式方式&與進(jìn)程有關(guān)的文件都放在文件區(qū)，故凡是未運(yùn)行過(guò)的頁(yè)面，與進(jìn)程有關(guān)的文件都放在文件區(qū)，故凡是未運(yùn)行過(guò)的頁(yè)面，都應(yīng)從文件區(qū)調(diào)入。而對(duì)于曾經(jīng)運(yùn)行過(guò)而又被換出的頁(yè)面，都應(yīng)從文件區(qū)調(diào)入。而對(duì)于曾經(jīng)運(yùn)行過(guò)而又被換出的頁(yè)面，總是存放在對(duì)換區(qū)中。因此在下

34、次調(diào)入時(shí)，應(yīng)從對(duì)換區(qū)調(diào)總是存放在對(duì)換區(qū)中。因此在下次調(diào)入時(shí)，應(yīng)從對(duì)換區(qū)調(diào)入。由于在入。由于在UNIX系統(tǒng)中允許頁(yè)面共享，因此，某進(jìn)程所請(qǐng)系統(tǒng)中允許頁(yè)面共享，因此，某進(jìn)程所請(qǐng)求的頁(yè)面有可能已由其它進(jìn)程調(diào)入內(nèi)存，此時(shí)也就無(wú)須再求的頁(yè)面有可能已由其它進(jìn)程調(diào)入內(nèi)存，此時(shí)也就無(wú)須再?gòu)膶?duì)換區(qū)調(diào)入。從對(duì)換區(qū)調(diào)入。&1.1.頁(yè)面置換方式頁(yè)面置換方式當(dāng)內(nèi)存空間已沒(méi)有空閑頁(yè)面而又要調(diào)入新頁(yè)時(shí)，必須當(dāng)內(nèi)存空間已沒(méi)有空閑頁(yè)面而又要調(diào)入新頁(yè)時(shí)，必須采用一定采用一定的算法在內(nèi)存中選擇某一頁(yè)面淘汰，所采用的算法稱之為頁(yè)的算法在內(nèi)存中選擇某一頁(yè)面淘汰，所采用的算法稱之為頁(yè)面置換算法。面置換算法。如果被淘汰的頁(yè)面在內(nèi)存

35、期間曾被修改過(guò)，還要將此頁(yè)重新寫(xiě)如果被淘汰的頁(yè)面在內(nèi)存期間曾被修改過(guò)，還要將此頁(yè)重新寫(xiě)回到外存，以便保留最新的副本。然后再換進(jìn)新的頁(yè)面?；氐酵獯?，以便保留最新的副本。然后再換進(jìn)新的頁(yè)面。(1)頁(yè)面置換方式頁(yè)面置換方式頁(yè)面淘汰可以在整個(gè)內(nèi)存空間范圍內(nèi)進(jìn)行，稱之為全局置換。頁(yè)面淘汰可以在整個(gè)內(nèi)存空間范圍內(nèi)進(jìn)行，稱之為全局置換。也可以只在一個(gè)進(jìn)程空間范圍內(nèi)考慮，稱之為局部置換。也可以只在一個(gè)進(jìn)程空間范圍內(nèi)考慮，稱之為局部置換。即即當(dāng)某一進(jìn)程請(qǐng)求新頁(yè)時(shí)，而該進(jìn)程又沒(méi)有空閑塊，則只能淘當(dāng)某一進(jìn)程請(qǐng)求新頁(yè)時(shí)，而該進(jìn)程又沒(méi)有空閑塊，則只能淘汰自己的一個(gè)頁(yè)面而不能淘汰其它進(jìn)程的頁(yè)面。汰自己的一個(gè)頁(yè)面而不能淘汰

36、其它進(jìn)程的頁(yè)面。 4.6.3 4.6.3 頁(yè)面置換方法頁(yè)面置換方法& (2) (2) 空閑塊分配方式空閑塊分配方式&若為進(jìn)程分配固定的物理塊數(shù)，在其執(zhí)行期間再也不改變，若為進(jìn)程分配固定的物理塊數(shù)，在其執(zhí)行期間再也不改變，則稱為固定分配。則稱為固定分配。初始進(jìn)程塊數(shù)的多少難以確定。若太少，初始進(jìn)程塊數(shù)的多少難以確定。若太少，則缺頁(yè)頻繁，系統(tǒng)開(kāi)銷大；若太多，則并發(fā)進(jìn)程數(shù)目少，則缺頁(yè)頻繁，系統(tǒng)開(kāi)銷大；若太多，則并發(fā)進(jìn)程數(shù)目少，造成造成CPUCPU空閑或其它資源空閑的情況。空閑或其它資源空閑的情況。&為進(jìn)程分配的物理塊數(shù)在其運(yùn)行期間是可變的，則稱為可為進(jìn)程分配的物理塊數(shù)在其運(yùn)行

37、期間是可變的，則稱為可變分配。變分配。進(jìn)程在運(yùn)行中，系統(tǒng)可調(diào)整為該進(jìn)程分配的物理進(jìn)程在運(yùn)行中，系統(tǒng)可調(diào)整為該進(jìn)程分配的物理塊，直至進(jìn)程的缺頁(yè)率達(dá)到適當(dāng)程度。塊，直至進(jìn)程的缺頁(yè)率達(dá)到適當(dāng)程度。在頁(yè)面置換算法討論中，為了比較各種方法的在頁(yè)面置換算法討論中，為了比較各種方法的優(yōu)劣，總是限定為固定分配局部置換。優(yōu)劣，總是限定為固定分配局部置換。固定分配局部置換：固定分配局部置換：固定分配全局置換：固定分配全局置換：可變分配局部置換可變分配局部置換可變分配全局置換可變分配全局置換(3) 內(nèi)存管理策略內(nèi)存管理策略不可能不可能&(1)(1)最佳淘汰算法最佳淘汰算法OPT(Optimal)OPT(Op

38、timal)&這是Belady于1966年提出的一種理論上的算法。該算法每次都淘汰以后永不使用的，或者過(guò)最長(zhǎng)的時(shí)間后才會(huì)被訪問(wèn)的頁(yè)面。&顯然，采用這種算法會(huì)保證最低的缺頁(yè)率，但它是無(wú)法實(shí)現(xiàn)的，因?yàn)樗仨氈理?yè)面“將來(lái)”的訪問(wèn)情況。不過(guò)，該算法仍有一定意義，可作為衡量其他算法優(yōu)劣的一個(gè)標(biāo)準(zhǔn)。 2.2.頁(yè)面置換算法頁(yè)面置換算法 假定系統(tǒng)為某個(gè)進(jìn)程分配了三個(gè)物理塊，進(jìn)程的訪問(wèn)順假定系統(tǒng)為某個(gè)進(jìn)程分配了三個(gè)物理塊，進(jìn)程的訪問(wèn)順序?yàn)樾驗(yàn)? 7，0 0，1 1，2 2，0 0，3 3，0 0，4 4，2 2，3 3，0 0，3 3，2 2，1 1，2 2OPTOPT置換算法示例：置換算法示

39、例：7，0，1， 2，0，3，0，4，2， 3，0 ，3， 2，1， 27 *7 0 *7 0 1 *2 0 1 *2 0 12 0 3 *2 0 32 4 3 *2 4 32 4 32 0 3 *2 0 32 0 32 1 3 *2 1 3缺頁(yè)次數(shù)缺頁(yè)次數(shù)8 8，成功訪問(wèn)次數(shù)，成功訪問(wèn)次數(shù)7 7次，次，缺頁(yè)率缺頁(yè)率f=8/15=53.33%f=8/15=53.33%（2 2）先進(jìn)先出淘汰算法）先進(jìn)先出淘汰算法FIFOFIFO&這是最早出現(xiàn)的淘汰算法。&總是淘汰最先進(jìn)入內(nèi)存的頁(yè)面?？偸翘蕴钕冗M(jìn)入內(nèi)存的頁(yè)面。它實(shí)現(xiàn)簡(jiǎn)單實(shí)現(xiàn)簡(jiǎn)單，只需把進(jìn)程中已調(diào)入內(nèi)存的頁(yè)面，按先后次序鏈成一個(gè)隊(duì)

40、列，并設(shè)置一個(gè)所謂的替換指針，使它總是指向內(nèi)存中最老的頁(yè)面。&缺點(diǎn)：效率不高，缺點(diǎn)：效率不高，因?yàn)樗c進(jìn)程實(shí)際的運(yùn)行規(guī)律不相適應(yīng)，比如常用的全局變量所在的頁(yè)面或者循環(huán)體所在頁(yè)面都可能被它選為淘汰對(duì)象。出現(xiàn)bleady現(xiàn)象。 &BeladyBelady現(xiàn)象：現(xiàn)象：采用FIFO算法時(shí)，如果對(duì)一個(gè)進(jìn)程未分配它所要求的全部頁(yè)面，有時(shí)就會(huì)出現(xiàn)分配的頁(yè)面數(shù)增多，缺頁(yè)率反而提高的異?，F(xiàn)象。&BeladyBelady現(xiàn)象的描述：現(xiàn)象的描述：一個(gè)進(jìn)程P要訪問(wèn)M個(gè)頁(yè)，OS分配N個(gè)內(nèi)存頁(yè)面給進(jìn)程P；對(duì)一個(gè)訪問(wèn)序列S，發(fā)生缺頁(yè)次數(shù)為PE（S,N）。當(dāng)N增大時(shí)，PE(S, N)時(shí)而增大，時(shí)而減小

41、。&BeladyBelady現(xiàn)象的原因：現(xiàn)象的原因：FIFO算法的置換特征與進(jìn)程訪問(wèn)內(nèi)存的動(dòng)態(tài)特征是矛盾的，即被置換的頁(yè)面并不是進(jìn)程不會(huì)訪問(wèn)的。FIFOFIFO淘汰算法示例：淘汰算法示例：7，0，1， 2，0，3，0，4， 2， 3，0 ，3， 2，1， 27 *7 0 *7 0 1 *2 0 1 *2 0 12 3 1 *2 3 0 *4 3 0 *4 2 0 *4 2 3 *0 2 3 *0 2 30 2 30 1 3 *0 1 2 *3 3塊內(nèi)存時(shí)，缺頁(yè)率塊內(nèi)存時(shí)，缺頁(yè)率f=12/15=80%f=12/15=80%；4 4塊塊f=8/15=53.33%f=8/15=53.33%7

42、，0，1， 2，0，3，0，4， 2， 3，0 ，3， 2，1， 27 *7 0 *7 0 1 *7 0 1 2 *7 0 1 23 0 1 2 *3 0 1 2 3 4 1 2 *3 4 1 2 3 4 1 2 3 4 0 2 *3 4 0 23 4 0 23 4 0 1 *2 4 0 1 *(3)(3)最近最久未使用算法最近最久未使用算法(LRU, (LRU, Least Recently UsedLeast Recently Used） 根據(jù)頁(yè)面調(diào)入內(nèi)存后的使用情況，選擇內(nèi)存中最久未使用的頁(yè)面被置換。這是局部性原理的合理近似，性能接近最佳算法。 OPT算法使用頁(yè)面將要被訪問(wèn)的時(shí)間，LRU

43、算法使用頁(yè)面最后一次被訪問(wèn)的時(shí)間。二者唯一的差別是：OPT是向前看的，而LRU是向后看的。 7，0，1， 2，0，3，0，4， 2， 3，0 ，3， 2，1， 27 *7 0 *7 0 1 *2 0 1 *2 0 12 0 3 *2 0 34 0 3 *4 0 2 *4 3 2 *0 3 2 *0 3 20 3 21 3 2 *1 3 2 10次，缺頁(yè)率次，缺頁(yè)率f=10/15=66.67%LRULRU的兩個(gè)實(shí)現(xiàn)算法：的兩個(gè)實(shí)現(xiàn)算法： &計(jì)時(shí)法：計(jì)時(shí)法：對(duì)于每一頁(yè)面增設(shè)一個(gè)訪問(wèn)時(shí)間計(jì)時(shí)器，每當(dāng)一個(gè)頁(yè)面被訪問(wèn)時(shí)，就將當(dāng)時(shí)的絕對(duì)時(shí)鐘拷貝到對(duì)應(yīng)的訪問(wèn)時(shí)間計(jì)時(shí)器中，這樣系統(tǒng)記錄了內(nèi)存中所有頁(yè)面

44、最后一次被訪問(wèn)的時(shí)間。淘汰時(shí)，選取訪問(wèn)時(shí)間計(jì)時(shí)器的值最小的頁(yè)面。&堆棧法：堆棧法：每當(dāng)進(jìn)程訪問(wèn)某頁(yè)面時(shí)，便將該頁(yè)面的頁(yè)號(hào)從棧中移出，將它壓入棧頂。棧頂始終是最新被訪問(wèn)的頁(yè)面的編號(hào)。棧底則是最近最久未被使用的頁(yè)面的頁(yè)面號(hào)。 假定現(xiàn)有一進(jìn)程所訪問(wèn)的頁(yè)面的頁(yè)面號(hào)序列為：假定現(xiàn)有一進(jìn)程所訪問(wèn)的頁(yè)面的頁(yè)面號(hào)序列為：4 4，8 8，0 0，8 8，1 1，0 0，2 2，1 1，2 2，6 6&隨著進(jìn)程的訪問(wèn)，棧中頁(yè)面號(hào)的變化情況隨著進(jìn)程的訪問(wèn)，棧中頁(yè)面號(hào)的變化情況：4，8，0，8，1，0，1，2，1，2，6 2 1 2 6 1 0 1 1 2 1 2 0 8 8 1 0 0 0 0 1

45、8 8 0 0 8 8 8 8 8 0 4 4 4 4 4 4 4 4 4 4 8LRULRU的開(kāi)銷是很大的，必須有硬件的支持，完全由軟件實(shí)的開(kāi)銷是很大的，必須有硬件的支持，完全由軟件實(shí)現(xiàn)其速度至少會(huì)減少現(xiàn)其速度至少會(huì)減少1010倍，因此倍，因此LRULRU近似算法更實(shí)用些。近似算法更實(shí)用些。 &這是一種LRU的近似算法，是通過(guò)對(duì)FIFO算法進(jìn)行簡(jiǎn)單改造，結(jié)合頁(yè)表中的訪問(wèn)位而得來(lái)一種淘汰算法。&該算法首先檢查位于FIFO鏈鏈?zhǔn)椎捻?yè)，如果它的訪問(wèn)位為0，則選擇該頁(yè)淘汰；如果它的訪問(wèn)位為1，則清除其訪問(wèn)位，將它移至FIFO鏈的鏈尾，重復(fù)此算法的查找過(guò)程，直至遇到新鏈?zhǔn)醉?yè)是一個(gè)訪問(wèn)位

46、為0的較早進(jìn)入內(nèi)存的頁(yè)為止，把它選為被淘汰的頁(yè)。 (4)(4)二次機(jī)會(huì)淘汰算法二次機(jī)會(huì)淘汰算法SC(Second Chance)SC(Second Chance)（5 5）時(shí)鐘）時(shí)鐘(Clock)(Clock)淘汰算法淘汰算法 &該算法首先檢測(cè)指針?biāo)傅捻?yè)面，如果它的訪問(wèn)位為0，則淘汰該頁(yè)，新裝入的頁(yè)插入到此位置，然后指針前進(jìn)一個(gè)位置；如果它的訪問(wèn)位為1，則清除為0，并將指針前進(jìn)一個(gè)位置，繼續(xù)檢查訪問(wèn)位。重復(fù)此過(guò)程，直到找到訪問(wèn)位為0的頁(yè)面為止。 &缺點(diǎn)：就是需要把訪問(wèn)位為1的處于鏈?zhǔn)椎捻?yè)移至鏈尾，這需要一定的開(kāi)銷。一種改進(jìn)的方法就是把進(jìn)程所訪問(wèn)的頁(yè)面鏈成一個(gè)環(huán)形鏈表，再設(shè)一個(gè)

47、指針指向最老的頁(yè)面，于是形成了一種簡(jiǎn)單實(shí)用的LRU近似算法時(shí)鐘淘汰算法。(6)(6)最近未用淘汰算法最近未用淘汰算法NUR(NUR(Not Used RecentlyNot Used Recently) ) &它把FIFO算法的思想與頁(yè)面的訪問(wèn)位和修改位結(jié)合起來(lái)確定一個(gè)接近LRU算法的淘汰對(duì)象。&該算法每次都盡量選擇最近最久未被寫(xiě)過(guò)的頁(yè)面淘汰，這種干凈的頁(yè)面可以不被寫(xiě)回到磁盤(pán)。在實(shí)現(xiàn)時(shí)，為每一個(gè)頁(yè)面設(shè)置初始值為0的訪問(wèn)位和修改位。當(dāng)對(duì)某頁(yè)面執(zhí)行寫(xiě)操作時(shí)，其修改位和訪問(wèn)位均由硬件置成1；當(dāng)對(duì)某頁(yè)面執(zhí)行讀操作時(shí)，只有其訪問(wèn)位被硬件置成1。系統(tǒng)每隔固定時(shí)間將所有訪問(wèn)位都清0。按照下列

48、次序選擇被淘汰的頁(yè)面：按照下列次序選擇被淘汰的頁(yè)面：&訪問(wèn)位，修改位；直接淘汰； &訪問(wèn)位，修改位；淘汰后寫(xiě)回；&訪問(wèn)位，修改位；直接淘汰；&訪問(wèn)位，修改位；寫(xiě)回外存后淘汰； 最近未使用淘汰算法就是最近未使用淘汰算法就是LRULRU的一種近似算法，它總是淘汰最近的一種近似算法，它總是淘汰最近未使用的頁(yè)，如果被淘汰的頁(yè)在內(nèi)存期間沒(méi)有被修改過(guò)，該頁(yè)未使用的頁(yè)，如果被淘汰的頁(yè)在內(nèi)存期間沒(méi)有被修改過(guò)，該頁(yè)可不必重新寫(xiě)入外存，將新頁(yè)覆蓋到被淘汰的頁(yè)上即可?？刹槐刂匦聦?xiě)入外存，將新頁(yè)覆蓋到被淘汰的頁(yè)上即可。訪問(wèn)位訪問(wèn)位A A0 0 表示該頁(yè)未被訪問(wèn)過(guò)；表示該頁(yè)未被訪問(wèn)過(guò)；

49、1 1 表示該頁(yè)已被訪問(wèn)過(guò)；表示該頁(yè)已被訪問(wèn)過(guò)；修改位修改位M M 0 0 表示該頁(yè)未被修改過(guò)表示該頁(yè)未被修改過(guò) 1 1 表示該頁(yè)已被修改過(guò)表示該頁(yè)已被修改過(guò)(1)(1)分配給作業(yè)的內(nèi)存塊數(shù)分配給作業(yè)的內(nèi)存塊數(shù) &作業(yè)的缺頁(yè)中斷率與作業(yè)所占內(nèi)存塊數(shù)成反比。分配給作業(yè)的內(nèi)存塊數(shù)太少是導(dǎo)致抖動(dòng)現(xiàn)象發(fā)生的最主要的原因，實(shí)驗(yàn)分析表明：對(duì)所有的程序來(lái)說(shuō)，要使其有效地工作，它在內(nèi)存中的頁(yè)面數(shù)不應(yīng)少于它的總頁(yè)面數(shù)的一半。 3.3.影響缺頁(yè)中斷率的因素影響缺頁(yè)中斷率的因素 (2)(2)頁(yè)面大小的選擇頁(yè)面大小的選擇&雖然缺頁(yè)中斷率與頁(yè)面尺寸成反比，但頁(yè)面尺寸卻不能一味地求大，它一般在0.5KB4

50、KB之間，是個(gè)實(shí)驗(yàn)統(tǒng)計(jì)值。因?yàn)轫?yè)面大時(shí)，頁(yè)表較小，占空間少，查表速度快，缺頁(yè)中斷次數(shù)少，但頁(yè)面調(diào)度時(shí)間長(zhǎng)，頁(yè)內(nèi)碎片較大。頁(yè)面小時(shí)，恰恰相反。 (3)(3)用戶程序編制的方法用戶程序編制的方法 作業(yè)的缺頁(yè)中斷率與程序的局部化（包括時(shí)間局部作業(yè)的缺頁(yè)中斷率與程序的局部化（包括時(shí)間局部化和空間局部化）程度成反比。用戶程序編制的方化和空間局部化）程度成反比。用戶程序編制的方法不合適可能導(dǎo)致程序運(yùn)行的時(shí)空復(fù)雜度高，缺頁(yè)法不合適可能導(dǎo)致程序運(yùn)行的時(shí)空復(fù)雜度高，缺頁(yè)次數(shù)多。次數(shù)多。 &(4)(4)頁(yè)面調(diào)度算法頁(yè)面調(diào)度算法 &抖動(dòng)又叫顛簸，是指一段時(shí)間里，頁(yè)面在內(nèi)存與外存之間頻繁地調(diào)度或換入換

51、出，以至于系統(tǒng)用于調(diào)度頁(yè)面所需要的時(shí)間比進(jìn)程實(shí)際運(yùn)行所占用的時(shí)間還要多。&好的淘汰算法會(huì)維持一個(gè)較低的缺頁(yè)率。若頁(yè)面置換算法不好，會(huì)使系統(tǒng)出現(xiàn)抖動(dòng)現(xiàn)象。 &顯然，抖動(dòng)是由于缺頁(yè)中斷率很高而引起的一種壞現(xiàn)象，它將嚴(yán)重影響系統(tǒng)的效率，甚至可能使系統(tǒng)全面崩潰。 防止抖動(dòng)現(xiàn)象的產(chǎn)生和擴(kuò)展，具體方法防止抖動(dòng)現(xiàn)象的產(chǎn)生和擴(kuò)展，具體方法:&采取局部置換策略采取局部置換策略&這樣，即使有某個(gè)進(jìn)程發(fā)生了這樣，即使有某個(gè)進(jìn)程發(fā)生了“抖動(dòng)抖動(dòng)”，也不致引起其它進(jìn)，也不致引起其它進(jìn)程也產(chǎn)生抖動(dòng)，從而把抖動(dòng)局限于較小的范圍內(nèi)。程也產(chǎn)生抖動(dòng)，從而把抖動(dòng)局限于較小的范圍內(nèi)。&這種方法

52、并不很好，因?yàn)樗荒軓母旧戏乐苟秳?dòng)的發(fā)生；這種方法并不很好，因?yàn)樗荒軓母旧戏乐苟秳?dòng)的發(fā)生；而且在某進(jìn)程發(fā)生抖動(dòng)后，還會(huì)長(zhǎng)期地處于磁盤(pán)輸入輸出的而且在某進(jìn)程發(fā)生抖動(dòng)后，還會(huì)長(zhǎng)期地處于磁盤(pán)輸入輸出的等待隊(duì)列中，這又會(huì)使其它進(jìn)程缺頁(yè)中斷的處理時(shí)間增長(zhǎng)，等待隊(duì)列中，這又會(huì)使其它進(jìn)程缺頁(yè)中斷的處理時(shí)間增長(zhǎng)，從而延長(zhǎng)了等效的訪問(wèn)時(shí)間。從而延長(zhǎng)了等效的訪問(wèn)時(shí)間。& L=S準(zhǔn)則準(zhǔn)則&Denning于于1980年提出了年提出了“L=S準(zhǔn)則準(zhǔn)則”，用來(lái)調(diào)整多道程，用來(lái)調(diào)整多道程序度，以使產(chǎn)生缺頁(yè)的平均時(shí)間序度，以使產(chǎn)生缺頁(yè)的平均時(shí)間L等于系統(tǒng)處理進(jìn)程缺頁(yè)的平等于系統(tǒng)處理進(jìn)程缺頁(yè)的平均時(shí)間均時(shí)

53、間S。理論和實(shí)踐表明，此時(shí)的。理論和實(shí)踐表明，此時(shí)的CPU利用得最好。該準(zhǔn)利用得最好。該準(zhǔn)則也得到其它研究人員的證實(shí)。則也得到其它研究人員的證實(shí)。防止抖動(dòng)現(xiàn)象的產(chǎn)生和擴(kuò)展，具體方法防止抖動(dòng)現(xiàn)象的產(chǎn)生和擴(kuò)展，具體方法:&掛起若干進(jìn)程掛起若干進(jìn)程&當(dāng)多道程序度偏高時(shí)，為了防止發(fā)生當(dāng)多道程序度偏高時(shí)，為了防止發(fā)生“抖抖動(dòng)動(dòng)”，可用的一個(gè)簡(jiǎn)單易行的辦法是掛起一可用的一個(gè)簡(jiǎn)單易行的辦法是掛起一些進(jìn)程，以便騰出內(nèi)存空間來(lái)分配給抖動(dòng)的些進(jìn)程，以便騰出內(nèi)存空間來(lái)分配給抖動(dòng)的進(jìn)程。進(jìn)程。被掛起的進(jìn)程通常是選擇優(yōu)先權(quán)最低被掛起的進(jìn)程通常是選擇優(yōu)先權(quán)最低或較低的；當(dāng)內(nèi)存非常擁擠時(shí)，也可以選擇或較低的

54、；當(dāng)內(nèi)存非常擁擠時(shí)，也可以選擇一個(gè)并不很重要的、但確較大的進(jìn)程掛起，一個(gè)并不很重要的、但確較大的進(jìn)程掛起，以便能一次釋放出較大的內(nèi)存空間；或者是以便能一次釋放出較大的內(nèi)存空間；或者是將具有最多剩余執(zhí)行時(shí)間的進(jìn)程掛起。將具有最多剩余執(zhí)行時(shí)間的進(jìn)程掛起。 4.6.4 4.6.4 虛擬頁(yè)式存儲(chǔ)的優(yōu)缺點(diǎn)虛擬頁(yè)式存儲(chǔ)的優(yōu)缺點(diǎn)&1.1.優(yōu)點(diǎn)優(yōu)點(diǎn)& 主存利用率比較高。主存利用率比較高。平均每個(gè)用戶作業(yè)只浪費(fèi)一平均每個(gè)用戶作業(yè)只浪費(fèi)一半的頁(yè)空間，內(nèi)存規(guī)范易于管理。半的頁(yè)空間，內(nèi)存規(guī)范易于管理。& 對(duì)磁盤(pán)管理比較容易。對(duì)磁盤(pán)管理比較容易。因?yàn)轫?yè)的大小一般取磁盤(pán)因?yàn)轫?yè)的大小一般取磁盤(pán)物理塊

55、大小的整數(shù)倍。物理塊大小的整數(shù)倍。& 地址映射和變換的速度比較快。地址映射和變換的速度比較快。在把用戶程序裝在把用戶程序裝入到主存儲(chǔ)器的過(guò)程中，只要建立用戶程序的虛頁(yè)入到主存儲(chǔ)器的過(guò)程中，只要建立用戶程序的虛頁(yè)號(hào)與主存儲(chǔ)器的實(shí)頁(yè)號(hào)之間的對(duì)應(yīng)關(guān)系即可（拼接號(hào)與主存儲(chǔ)器的實(shí)頁(yè)號(hào)之間的對(duì)應(yīng)關(guān)系即可（拼接得到物理地址），不必使用整個(gè)主存的地址長(zhǎng)度，得到物理地址），不必使用整個(gè)主存的地址長(zhǎng)度，也不必考慮每頁(yè)的長(zhǎng)度等。也不必考慮每頁(yè)的長(zhǎng)度等。& 2. 2.缺點(diǎn)缺點(diǎn)& 程序的模塊化性能不好程序的模塊化性能不好。&由于用戶程序是強(qiáng)制按照固定大小的頁(yè)來(lái)劃分的，而程序段由于用戶程序

56、是強(qiáng)制按照固定大小的頁(yè)來(lái)劃分的，而程序段的實(shí)際長(zhǎng)度一般是不固定的。因此，虛擬頁(yè)式存儲(chǔ)器中一頁(yè)的實(shí)際長(zhǎng)度一般是不固定的。因此，虛擬頁(yè)式存儲(chǔ)器中一頁(yè)通常不能表示一個(gè)完整的程序功能。一頁(yè)可能只是一個(gè)程序通常不能表示一個(gè)完整的程序功能。一頁(yè)可能只是一個(gè)程序段中的一部分，也可能在一頁(yè)中包含了兩個(gè)或兩個(gè)以上程序段中的一部分，也可能在一頁(yè)中包含了兩個(gè)或兩個(gè)以上程序段。段。& 頁(yè)表很長(zhǎng)，需要占用很大的存儲(chǔ)空間。頁(yè)表很長(zhǎng)，需要占用很大的存儲(chǔ)空間。&通常，虛擬存儲(chǔ)器中的每一頁(yè)在頁(yè)表中都要占一個(gè)頁(yè)表項(xiàng)。通常，虛擬存儲(chǔ)器中的每一頁(yè)在頁(yè)表中都要占一個(gè)頁(yè)表項(xiàng)。假設(shè)有一個(gè)虛擬頁(yè)式存儲(chǔ)器，它的虛擬存儲(chǔ)空間大小

57、為假設(shè)有一個(gè)虛擬頁(yè)式存儲(chǔ)器，它的虛擬存儲(chǔ)空間大小為4GB，每一頁(yè)的大小為每一頁(yè)的大小為1KB，則頁(yè)表的容量為，則頁(yè)表的容量為4M（個(gè)頁(yè)表項(xiàng)）。如（個(gè)頁(yè)表項(xiàng)）。如果每個(gè)頁(yè)表項(xiàng)占用果每個(gè)頁(yè)表項(xiàng)占用4個(gè)字節(jié)，則頁(yè)表的存儲(chǔ)容量為個(gè)字節(jié)，則頁(yè)表的存儲(chǔ)容量為16MB。4.7 4.7 虛擬段式存儲(chǔ)管理虛擬段式存儲(chǔ)管理4.7.1 4.7.1 虛擬段式存儲(chǔ)的實(shí)現(xiàn)虛擬段式存儲(chǔ)的實(shí)現(xiàn) 4.7.2 4.7.2 段的共享和保護(hù)段的共享和保護(hù) 4.7.34.7.3虛擬段式存儲(chǔ)管理的優(yōu)缺點(diǎn)虛擬段式存儲(chǔ)管理的優(yōu)缺點(diǎn)4.7.4 4.7.4 虛擬段頁(yè)式存儲(chǔ)管理虛擬段頁(yè)式存儲(chǔ)管理 4.7.1 4.7.1 虛擬段式存儲(chǔ)的實(shí)現(xiàn)虛擬段式

58、存儲(chǔ)的實(shí)現(xiàn)&1.1.虛擬段式存儲(chǔ)原理虛擬段式存儲(chǔ)原理&為了能實(shí)現(xiàn)虛擬存儲(chǔ)，段式邏輯地址空間中為了能實(shí)現(xiàn)虛擬存儲(chǔ)，段式邏輯地址空間中的程序段在運(yùn)行時(shí)并不全部裝入內(nèi)存，而是的程序段在運(yùn)行時(shí)并不全部裝入內(nèi)存，而是如同請(qǐng)求式分頁(yè)存儲(chǔ)管理，首先調(diào)入一個(gè)或如同請(qǐng)求式分頁(yè)存儲(chǔ)管理，首先調(diào)入一個(gè)或若干個(gè)程序段運(yùn)行，在運(yùn)行過(guò)程中調(diào)用到哪若干個(gè)程序段運(yùn)行，在運(yùn)行過(guò)程中調(diào)用到哪段時(shí)，就根據(jù)該段長(zhǎng)度在內(nèi)存分配一個(gè)連續(xù)段時(shí)，就根據(jù)該段長(zhǎng)度在內(nèi)存分配一個(gè)連續(xù)的分區(qū)給它使用。若內(nèi)存中沒(méi)有足夠大的空的分區(qū)給它使用。若內(nèi)存中沒(méi)有足夠大的空閑分區(qū)，則考慮進(jìn)行段的緊湊或?qū)⒛扯位蚰抽e分區(qū)，則考慮進(jìn)行段的緊湊或?qū)⒛扯位?/p>

59、某些段淘汰出去。相應(yīng)于請(qǐng)求式分頁(yè)存儲(chǔ)管理，些段淘汰出去。相應(yīng)于請(qǐng)求式分頁(yè)存儲(chǔ)管理，這種存儲(chǔ)管理技術(shù)稱為請(qǐng)求式分段存儲(chǔ)管理。這種存儲(chǔ)管理技術(shù)稱為請(qǐng)求式分段存儲(chǔ)管理。2.2.段表段表 &類似于請(qǐng)求式分頁(yè)存儲(chǔ)管理的頁(yè)表，為了實(shí)現(xiàn)動(dòng)態(tài)地址變類似于請(qǐng)求式分頁(yè)存儲(chǔ)管理的頁(yè)表，為了實(shí)現(xiàn)動(dòng)態(tài)地址變換和存儲(chǔ)保護(hù)，系統(tǒng)要為每一個(gè)作業(yè)建立一張段表。段表?yè)Q和存儲(chǔ)保護(hù)，系統(tǒng)要為每一個(gè)作業(yè)建立一張段表。段表中的每一個(gè)表目對(duì)應(yīng)著作業(yè)地址空間的一個(gè)程序段，其一中的每一個(gè)表目對(duì)應(yīng)著作業(yè)地址空間的一個(gè)程序段，其一般格式為：般格式為： 邏輯地址同前：邏輯地址同前：段段號(hào)號(hào)存在存在位位P P訪問(wèn)訪問(wèn)位位A A修改修改位位M

60、M存取存取方式方式增補(bǔ)增補(bǔ)位位段段長(zhǎng)度長(zhǎng)度段的段的基址基址外存外存地址地址存在位存在位P P表示該段是否在內(nèi)存，如為表示該段是否在內(nèi)存，如為0 0表示不在，為表示不在，為1 1表示在內(nèi)存；表示在內(nèi)存；存取方式表示可對(duì)該段施加的操作，如只讀、讀寫(xiě)、還是執(zhí)行。存取方式表示可對(duì)該段施加的操作，如只讀、讀寫(xiě)、還是執(zhí)行。增補(bǔ)位表示該段在運(yùn)行期間是否可以擴(kuò)展空間增補(bǔ)位表示該段在運(yùn)行期間是否可以擴(kuò)展空間 3.3.請(qǐng)求式分段動(dòng)態(tài)地址變換過(guò)程請(qǐng)求式分段動(dòng)態(tài)地址變換過(guò)程 4.4.缺段中斷缺段中斷&在虛擬段式存儲(chǔ)系統(tǒng)中，采用的是請(qǐng)求調(diào)段策略。即每當(dāng)進(jìn)在虛擬段式存儲(chǔ)系統(tǒng)中，采用的是請(qǐng)求調(diào)段策略。即每當(dāng)進(jìn)程所要

61、訪問(wèn)的段尚未調(diào)入內(nèi)存時(shí)，便由缺段中斷機(jī)構(gòu)產(chǎn)生一程所要訪問(wèn)的段尚未調(diào)入內(nèi)存時(shí)，便由缺段中斷機(jī)構(gòu)產(chǎn)生一缺段中斷信號(hào)，進(jìn)入缺段中斷信號(hào)，進(jìn)入OS后由缺斷中斷處理程序?qū)⑺璧亩握{(diào)后由缺斷中斷處理程序?qū)⑺璧亩握{(diào)入內(nèi)存。入內(nèi)存。&再調(diào)入新段時(shí)，也會(huì)有內(nèi)存空間不夠用的情況，也需要淘汰再調(diào)入新段時(shí)，也會(huì)有內(nèi)存空間不夠用的情況，也需要淘汰內(nèi)存中的一個(gè)或多個(gè)段。如果此程序段從裝入內(nèi)存起一直沒(méi)內(nèi)存中的一個(gè)或多個(gè)段。如果此程序段從裝入內(nèi)存起一直沒(méi)有被修改過(guò)，只要用新調(diào)入的程序段把它覆蓋掉即可。若這有被修改過(guò)，只要用新調(diào)入的程序段把它覆蓋掉即可。若這個(gè)程序段被修改過(guò)，則必須先把該程序段全部寫(xiě)回到磁盤(pán)存?zhèn)€程序段被修改過(guò)，則必須先把該程序段全部寫(xiě)回到磁盤(pán)存儲(chǔ)器中，才能占用被淘汰段原來(lái)存放的空間。儲(chǔ)器中，才能占用被淘汰段原來(lái)存放的空間。&因?yàn)槎我加眠B續(xù)的空間，因此當(dāng)內(nèi)存中沒(méi)有能夠滿足段長(zhǎng)因?yàn)槎我加眠B續(xù)的空間，因此當(dāng)內(nèi)存中沒(méi)有能夠滿足段長(zhǎng)需要的空閑區(qū)時(shí)，系統(tǒng)還要合并空閑區(qū)，以便滿足分段的需需要的空閑區(qū)時(shí)，系