存儲器管理95191

1、第四章 存儲器管理第一節(jié) 基本概念1 程序的裝入和鏈接在多道程序環(huán)境下，要使程序運行，必須創(chuàng)建進程，而創(chuàng)建進程第一件事就是將程序和數(shù)據(jù)裝入內(nèi)存。一個用戶源程序要變?yōu)樵趦?nèi)存中可執(zhí)行的程序，通常要進行以下處理：（1）編譯：由編譯程序?qū)⒂脩粼闯绦蚓幾g成若干個目標模塊（2）鏈接：由鏈接程序?qū)⒛繕四K和相應(yīng)的庫函數(shù)鏈接成裝入模塊（3）裝入：由裝入程序?qū)⒀b入模塊裝入內(nèi)存1.1 一些概念u 邏輯地址-用戶程序經(jīng)編譯后，每個目標模塊以0為基地址進行的順序編址。也就是相對與初始地址的，邏輯地址又稱相對地址，相對基地址而言。u 物理地址-內(nèi)存中各物理存儲單元的地址從統(tǒng)一的基地址進行的順序編址。物理地址又稱絕對地址

2、，它是數(shù)據(jù)在內(nèi)存中的實際存儲地址。u 地址空間（名空間）：指用戶程序使用的全部地址。地址空間中的每個地址單元編號稱為邏輯地址（logical address），由于通常邏輯地址都是相對于程序的起始地址的，故又稱為相對地址（relative address）。u 存儲空間：指內(nèi)存中存儲數(shù)據(jù)的物理單元的集合。這些物理單元的集合稱為物理地址（physical address）或絕對地址（absolute address）。u 重定位：當作業(yè)的地址空間與存儲空間不一致時，所進行的地址調(diào)整以便使作業(yè)能夠執(zhí)行的過程稱為重定位。重定位實質(zhì)是地址變換，即作業(yè)地址空間中的邏輯地址變換為主存空間的物理地址。根據(jù)地

3、址變換進行的時間及采用技術(shù)手段不同，可分為靜態(tài)重定位和動態(tài)重定位兩類。1.2 程序的裝入將裝入模塊裝入內(nèi)存時。可以有以下裝入方式。1.2.1 絕對裝入方式思想:編譯時，若知道程序?qū)Ⅰv留內(nèi)存的什么位置，則編譯程序?qū)a(chǎn)生絕對地址的目標代碼，鏈接得到裝入模塊。絕對裝入程序按照裝入模塊中的地址，將程序和數(shù)據(jù)裝入內(nèi)存。裝入模塊被裝入內(nèi)存后，由于程序中的邏輯地址與實際內(nèi)存地址完全相同，因此不用對程序和數(shù)據(jù)進行修改。適用：單道程序環(huán)境1.2.2重定位裝入方式基本思想：在多道環(huán)境下，不可能預知程序應(yīng)該放在內(nèi)存的哪個位置，裝入程序在裝入時根據(jù)內(nèi)存的實際情況把相對地址（邏輯地址）轉(zhuǎn)換為絕對地址，裝入到適當?shù)奈恢谩?/p>

4、（在裝入時進行地址轉(zhuǎn)換）靜態(tài)重定位。適用：用于多道程序環(huán)境。課本例子見下圖P1041.2.3動態(tài)運行時裝入方式（動態(tài)重定位的裝入方式）思想：在把裝入模塊裝入內(nèi)存后，并不立即進行地址轉(zhuǎn)換，而是把相對地址到絕對地址的的地址轉(zhuǎn)換推遲到程序真正開始運行的時候再進行。需要一個重定位寄存器支持。其本質(zhì)就是在程序運行的過程中進行地址轉(zhuǎn)換。適用：多道環(huán)境中程序在內(nèi)存中改變位置。1.2.4 三種裝入方式的對比絕對裝入方式只能將裝入模塊裝入到內(nèi)存中事先指定的位置，在多道程序環(huán)境下是不可能事先知道每一道程序在內(nèi)存中的位置的，因此這種裝入方式只能用于單道程序環(huán)境。地址轉(zhuǎn)換時機：程序中所使用的絕對地址，既可在編譯或匯編

5、時給出，也可由程序員直接賦予。適用于單道 環(huán)境?？芍囟ㄎ谎b入方式可將裝入模塊裝入到內(nèi)存中任何允許的位置，故可用于多道程序環(huán)境；然而它不允許程序在運行中移動位置。地址轉(zhuǎn)換時機發(fā)生于程序裝入內(nèi)存時發(fā)生。適用于動態(tài)運行時裝入方式允許程序在運行中移動位置，需要特殊硬件的支持。地址轉(zhuǎn)換時機發(fā)生于程序運行時。適用于1.2 程序的鏈接由鏈接程序?qū)⒛繕四K和相應(yīng)的庫函數(shù)鏈接成裝入模塊。按照鏈接時間不同分為三種：1.2.1 靜態(tài)鏈接方式思想：我們常說靜態(tài)鏈接實在生成可執(zhí)行文件時進行的。是一種事先鏈接方式，即在程序運行之前，先將各目標模塊及它們所需的庫函數(shù)，鏈接成一個完整的裝入模塊(執(zhí)行文件)，以后不再拆開。實現(xiàn)

6、靜態(tài)鏈接應(yīng)解決的問題：（1）相對地址的修改。每個模塊中所有相對地址的修改。比如，原起始地址為0，現(xiàn)在為L。則模塊中所有相對地址都要加L。（2）變換外部調(diào)用符號。每個模塊中所用的外部調(diào)用符號也都要變換。存在問題：（1）不便于對目標模塊的修改和更新（2）無法實現(xiàn)對目標模塊的共享如圖 動態(tài)鏈接在裝入或運行時進行鏈接。通常被鏈接的共享代碼稱為動態(tài)鏈接庫(DLL, Dynamic-Link Library)或共享庫(shared library)。優(yōu)點 共享：多個進程可以共用一個DLL，節(jié)省內(nèi)存，減少文件交換。 部分裝入：一個進程可以將多種操作分散在不同的DLL中實現(xiàn)，而只將當前操作相應(yīng)的DLL裝入內(nèi)存

7、。 便于局部代碼修改：即便于代碼升級和代碼重用；只要函數(shù)的接口參數(shù)（輸入和輸出）不變，則修改函數(shù)及其DLL，無需對可執(zhí)行文件重新編譯或鏈接。 便于運行環(huán)境適應(yīng)：調(diào)用不同的DLL，就可以適應(yīng)多種使用環(huán)境和提供不同功能。如：不同的顯示卡只需廠商為其提供特定的DLL，而OS和應(yīng)用程序不必修改。.1 裝入時動態(tài)鏈接思想：指將一組目標模塊在裝入內(nèi)存時，邊裝入邊鏈接的方式。具有便于修改和更新、便于實現(xiàn)對目標模塊的共享。存在問題：由于程序運行所有可能用的目標模塊在裝入時均全部鏈接在一起，所以將會把一些不會運行的目標模塊也鏈接進去。如程序中的錯誤處理模塊1.2.2.2 運行時動態(tài)鏈接思想：在程序運行中需要某些

8、目標模塊時，才對它們進行鏈接的方式。具有高效且節(jié)省內(nèi)存空間的優(yōu)點。第二節(jié) 連續(xù)分配方式1 單一連續(xù)分配（單獨分區(qū)分配）最簡單的一種存儲管理方式，但只能用于單用戶、單任務(wù)的OS中。概念：單一連續(xù)分配就是整個主存區(qū)域的用戶空間均歸一個用戶作業(yè)使用。存儲管理方法：將內(nèi)存分為系統(tǒng)區(qū)（內(nèi)存低端，分配給OS用）和用戶區(qū)（內(nèi)存高端，分配給用戶用）。其中用戶區(qū)是指除了系統(tǒng)區(qū)外的內(nèi)存空間，提供給用戶程序使用。采用靜態(tài)分配方式，即作業(yè)一旦進入內(nèi)存，就要等待它運行結(jié)束后才能釋放內(nèi)存。主要特點：管理簡單，只需小量的軟件和硬件支持，便于用戶了解和使用。但因內(nèi)存中只裝入一道作業(yè)運行，內(nèi)存空間浪費大，各類資源的利用率也不高

9、。例子：一個容量為256KB的內(nèi)存，操作系統(tǒng)占用32KB，剩下224KB全部分配給用戶作業(yè)，如果一個作業(yè)僅需64KB，那么就有160KB的存儲空間被浪費。2 固定分區(qū)分配分區(qū)分配方式是滿足多道程序設(shè)計需要的一種最簡單的存儲管理方法。2.1 思想：將內(nèi)存分成若干個分區(qū)（大小相等/不相等），除OS占一區(qū)外，其余的每一個分區(qū)容納一個用戶程序。這樣來實現(xiàn)多道并發(fā)。2.2 分區(qū)劃分方法：分區(qū)大小相等，分區(qū)大小不等。但事先必須確定，在運行時不能改變。即分區(qū)大小及邊界在運行時不能改變。2.3 內(nèi)存分配：首先：要先建立一張分區(qū)說明表或使用表，以記錄分區(qū)號、分區(qū)大小、分區(qū)的起始地址及狀態(tài)（已分配或未分配）。其次

10、：當某個用戶程序要裝入內(nèi)存時，由內(nèi)存分配程序檢索分區(qū)說明表，從表中找出一個滿足要求的尚未分配的分區(qū)分配該程序，同時修改說明表中相應(yīng)分區(qū)的狀態(tài)；若找不到大小足夠的分區(qū)，則拒絕為該程序分配內(nèi)存。第三：當程序執(zhí)行完畢，釋放占用的分區(qū)，管理程序?qū)⑿薷恼f明表中相應(yīng)分區(qū)的狀態(tài)為未分配，實現(xiàn)內(nèi)存資源的回收。2.4 特點主要特點：管理簡單，但因作業(yè)的大小并不一定與某個分區(qū)大小相等，從而使一部分存儲空間被浪費。所以主存的利用率不高3 動態(tài)分區(qū)分配3.1 基本思想：根據(jù)進程的實際需要，動態(tài)的為其分配內(nèi)存空間。因此分區(qū)大小是動態(tài)可變的，分區(qū)的個數(shù)也是可變的。3.2 主要特點管理簡單，只需小量的軟件和硬件支持，便于用

11、戶了解和使用。進程的大小與某個分區(qū)大小相等，從而主存的利用率有所提高。3.3 分區(qū)分配的數(shù)據(jù)結(jié)構(gòu)為描述空閑分區(qū)合已分配的分區(qū)，引入如下數(shù)據(jù)結(jié)構(gòu)。3.3.1 空閑分區(qū)表用于記錄每個空閑分區(qū)的情況。每個空閑分區(qū)占一個表目，表目重含有分區(qū)序號，分區(qū)起始地址，分區(qū)大小等數(shù)據(jù)項。如下圖3.3.2 空閑分區(qū)鏈用鏈頭指針將系統(tǒng)中的空閑分區(qū)鏈接起來，構(gòu)成空閑分區(qū)鏈。每個空閑分區(qū)的起始部分存放相應(yīng)的控制信息(如大小,指向下一空閑分區(qū)的指針等).就是在分區(qū)頭設(shè)置一個前向指針，分區(qū)尾部設(shè)置一個后向指針，這樣把所有空閑分區(qū)連起來。3.4 分區(qū)分配算法把一個新作業(yè)裝入內(nèi)存，須按照一定的分配算法，從空閑分區(qū)表或空閑分區(qū)鏈

12、中選擇一合適分區(qū)分配給該作業(yè)。有下面三種分配算法：3.4.1 首次適應(yīng)算法算法過程：算法要求空閑分區(qū)（鏈）按地址遞增的次序排列。在進行內(nèi)存分配時,從空閑分區(qū)表/鏈首開始順序查找,直到找到第一個滿足其大小要求的空閑分區(qū)為止。然后再按照作業(yè)大小，從該分區(qū)中劃出一塊內(nèi)存空間分配給請求者，余下的空閑分區(qū)仍留在空閑分區(qū)表（鏈）中。算法的特點優(yōu)先利用內(nèi)存低地址部分的空閑分區(qū),從而保留了高地址部分的大空閑區(qū)。但由于低地址部分不斷被劃分,致使低地址端留下許多難以利用的很小的空閑分區(qū)(碎片或零頭),而每次查找又都是從低地址部分開始,這無疑增加了查找可用空閑分區(qū)的開銷。3.4.2 循環(huán)首次適應(yīng)算法算法過程：由首次

13、適應(yīng)算法發(fā)展而來，每次為進程分配內(nèi)存空間時，不是從鏈首開始，而是從上次找到的空閑分區(qū)的下一個空閑分區(qū)開始查找，直到找到一個滿足要求的空閑分區(qū)。該算法要設(shè)置一個起始查尋指針。用于標識下一次起始查尋的空閑分區(qū)。算法特點使存儲空間的利用更加均衡，不致使小的空閑區(qū)集中在存儲區(qū)的一端，但這會導致缺乏大的空閑分區(qū)。3.4.3 最佳適應(yīng)算法算法過程：算法要求空閑分區(qū)表/鏈按容量大小遞增的次序排列。在進行內(nèi)存分配時，從空閑分區(qū)表/鏈的首開始順序查找，直到找到第一個滿足其大小要求的空閑分區(qū)為止。按這種方式為作業(yè)分配內(nèi)存，就能把既滿足作業(yè)要求又與作業(yè)大小最接近的空閑分區(qū)分配給作業(yè)。如果該空閑分區(qū)大于作業(yè)的大小，則

14、與首次適應(yīng)算法相同，將剩余空閑分區(qū)仍留在空閑分區(qū)表/鏈中。算法特點若存在與作業(yè)大小一致的空閑分區(qū),則它必然被選中，若不存在與作業(yè)大小一致的空閑分區(qū)，則只劃分比作業(yè)稍大的空閑分區(qū)，,從而保留了大的空閑分區(qū),但空閑區(qū)一般不可能正好和它申請的內(nèi)存空間大小一樣,因而將其分割成兩部分時,往往使剩下的空閑區(qū)非常小,從而在存儲器中留下許多難以利用的小空閑區(qū)（碎片或零頭）。3.5 分區(qū)分配操作這里所謂的操作是：分配內(nèi)存和回收內(nèi)存。3.5.1 分配內(nèi)存操作實際上是分區(qū)的分割。具體過程如下：設(shè)請求的分區(qū)大小為u.size，空閑分區(qū)的大小為m.size,若£size(size是事先規(guī)定的不再切割的剩余分區(qū)

15、的大小)，說明多余部分太小，可不再切割，將整個分區(qū)分配給請求者；否則,即多余部分超過size，從該分區(qū)中按請求的大小劃分出一塊內(nèi)存空間分配出去，余下的部分仍留在空閑分區(qū)表/鏈中，然后，將分配區(qū)的首址返回給調(diào)用者。分配流程圖：3.5.2 回收內(nèi)存操作基本過程：當作業(yè)執(zhí)行結(jié)束時，應(yīng)回收已使用完畢的分區(qū)。系統(tǒng)根據(jù)回收分區(qū)的大小及首地址，在空閑分區(qū)表中檢查是否有鄰接的空閑分區(qū)，如有，則合成為一個大的空閑分區(qū)，然后修改有關(guān)的分區(qū)狀態(tài)信息?；厥辗謪^(qū)與已有空閑分區(qū)的相鄰情況有以下四種： 1）回收分區(qū)上鄰接一個空閑分區(qū),合并后首地址為空閑分區(qū)的首地址,大小為二者之和。 2）回收分區(qū)下鄰接一個空閑分區(qū),合并后首

16、地址為回收分區(qū)的首地址,大小為二者之和。 3）回收分區(qū)上下鄰接空閑分區(qū),合并后首地址為上空閑分區(qū)的首地址,大小為三者之和。4）回收分區(qū)不鄰接空閑分區(qū)，這時在空閑分區(qū)表中新建一表項，并填寫分區(qū)大小等信息，并根據(jù)其首地址插入到空閑鏈的適當位置。如下圖：4可重定位分區(qū)分配4.1 動態(tài)重定位的引入在連續(xù)分配方式中，我們必須把一個系統(tǒng)或用戶程序裝入一個連續(xù)的內(nèi)存空間。但是，如果在系統(tǒng)中只有一些小分區(qū)并且這些分區(qū)不相鄰鏈接，即使它們的相加之后的空間大于要裝入的程序，也不可能把程序裝入這些內(nèi)存中。這些小分區(qū)就叫做“零頭”或“碎片”。處理思路“緊湊”：將內(nèi)存中的所有作業(yè)移動到內(nèi)存的另一端，使它們?nèi)肯噜?。這樣

17、，就可以把原來分散的多個小分區(qū)拼接成一個大分區(qū)，這時就可把作業(yè)裝入了。稱為“緊湊”或“拼接”。出現(xiàn)問題：緊湊后，明顯可以看出內(nèi)存中的數(shù)據(jù)和程度的存放位置發(fā)生了變化，如果不對程序和數(shù)據(jù)的地址加以更改，則程序不能運行，因此我們需要重定位。也就是說在每次緊湊之后需要重定位。4.2 動態(tài)重定位的實現(xiàn)引入重定位寄存器，程序在執(zhí)行時，真正訪問的內(nèi)存地址是相對地址和重定位寄存器中的地址相加后的地址。見課本圖p111動態(tài)重定位：地址變換過程是在程序執(zhí)行期間，隨著對每條指令或數(shù)據(jù)的訪問時才進行的。因此稱為動態(tài)重定位。4.3動態(tài)重定位分區(qū)分配算法和動態(tài)分區(qū)分配算法基本相同，只是增加了緊湊功能。算法流程如下：5 對

18、換 了解多道程序環(huán)境下，會出現(xiàn)某些進程未執(zhí)行而占據(jù)內(nèi)存空間，而大量的作業(yè)在外存而不能進入內(nèi)存執(zhí)行。為了充分的利用內(nèi)存空間，我們引入了覆蓋和對換。覆蓋是早期的操作系統(tǒng)中運用，有興趣的同學了解一下對換：將暫時不用的某個進程及數(shù)據(jù)（首先是處于阻塞狀態(tài)優(yōu)先級最低的，根據(jù)系統(tǒng)的采用算法決定）部分（或全部）從內(nèi)存移到到外存（備份區(qū)或?qū)Q區(qū)，采用連續(xù)分配的動態(tài)存儲管理方式）中去，讓出內(nèi)存空間，同時將某個需要的進程調(diào)入到內(nèi)存中，讓其運行。交換到外存的進程需要時可以被再次交換回（選擇換出時間最久的，也是根據(jù)系統(tǒng)采用的算法決定）內(nèi)存中繼續(xù)執(zhí)行。這種內(nèi)存擴充技術(shù)就是交換技術(shù)。6 覆蓋6.1 引入：覆蓋實現(xiàn)了在較小的

19、可用內(nèi)存中運行較大的程序。常用于多道程序系統(tǒng)，與分區(qū)存儲管理配合使用。6.2 原理：一個程序的幾個代碼段或數(shù)據(jù)段，按照時間先后來占用公共的內(nèi)存空間。 將程序的必要部分（常用功能）的代碼和數(shù)據(jù)常駐內(nèi)存； 可選部分（不常用功能）在其他程序模塊中實現(xiàn)，平時存放在外存中（覆蓋文件），在需要用到時才裝入到內(nèi)存； 不存在調(diào)用關(guān)系的模塊不必同時裝入到內(nèi)存，從而可以相互覆蓋。(即不同時用的模塊可共用一個分區(qū))覆蓋示例如下：第三節(jié) 基本分頁存儲管理方式1 基本概念概念：在分頁式存儲管理方式中，如果不具備頁面對換功能，不支持虛擬存儲器功能，在調(diào)度作業(yè)運行時，必須將它的所有頁面一次調(diào)入內(nèi)存，若內(nèi)存沒有足夠的塊，則作

20、業(yè)等待，則稱為純分頁或基本的分頁存儲管理方式。1.1 基本思想就是先劃分在裝塊。n 空間劃分：（1）地址空間的劃分：將一個用戶進程的邏輯地址空間劃分成若干個大小相等的區(qū)域，稱為頁或頁面,并將各頁從0開始編號。（2）物理空間的劃分：內(nèi)存空間也分成若干個與頁大小相等的區(qū)域，稱為（存儲、物理）塊或頁框（frame），同樣從0開始編號。n 內(nèi)存分配：在為進程分配內(nèi)存時,以塊為單位,將進程中若干頁裝入到多個不相鄰的塊中,最后一頁常裝不滿一塊而出現(xiàn)頁內(nèi)碎片。注：需要CPU的硬件支持（地址變換機構(gòu)）。1.2 頁面頁面的概念前面提到了。若頁面較?。?#167; 減少頁內(nèi)碎片和內(nèi)存碎片的總空間，有利于提高內(nèi)存利

21、用率。§ 每個進程頁面數(shù)增多，從而使頁表長增加，占用內(nèi)存就較大。§ 頁面換進換出速度將降低。 若頁面較大：§ 每個進程頁面數(shù)減少，頁表長度減少，占用內(nèi)存就較小。§ 頁面換進換出速度將提高。§ 會增加頁內(nèi)碎片不利于提高內(nèi)存利用率。頁面大小-選擇適中，通常為2的冪，一般在512B-8KB之間。分頁地址的地址結(jié)構(gòu)-如下圖：頁面的大小其實由位移量來確定。課本P131有計算公式，可以看一下。1.3 頁表1.3.1 什么是頁表記錄頁號到物理塊號之間的對應(yīng)關(guān)系，映射的映射表就是頁表，1.3.2 頁表的作用就是實現(xiàn)從進程的頁號到內(nèi)存物理塊號的地址映射。如圖示1

22、.3.3 頁表的性質(zhì)n 記錄了頁面在內(nèi)存中對應(yīng)的塊號。n 頁表一般存放在內(nèi)存中。n 訪問一個字節(jié)的數(shù)據(jù)/指令需訪問內(nèi)存2次(頁表一次,內(nèi)存一次),所以出現(xiàn)內(nèi)存訪問速度降低的問題。n 一般分頁系統(tǒng)中，常在頁表中設(shè)置一個存取控制字段，用于標識對該存儲塊的內(nèi)容保護也就是存取權(quán)限。表示允許讀/寫，只讀等等。2 地址變換機構(gòu)引入：由于由頁號到物理塊號，頁內(nèi)地址到塊內(nèi)地址都是將邏輯地址，變換為內(nèi)存空間的物理地址，因此在系統(tǒng)中必須設(shè)置地址變換機構(gòu)。2.1 地址變換機構(gòu)的基本任務(wù)實現(xiàn)邏輯地址向物理地址的轉(zhuǎn)換（由頁號->塊號）。由于，頁表就是實現(xiàn)從頁號到物理塊號的變換，因此地址變換借助頁表來完成。2.2

23、基本地址變換機構(gòu)過程描述：頁表駐留在內(nèi)存。系統(tǒng)中設(shè)置一個頁表寄存器PTR，在其中存放頁表在內(nèi)存的起始地址和頁表的長度。進程未執(zhí)行時，頁表的起始地址和頁表長度存放再本進程的PCB中，當該進程被調(diào)度時，這兩個數(shù)據(jù)裝入頁表寄存器。當進程執(zhí)行時要訪問某個邏輯地址中的數(shù)據(jù)時，地址變換機構(gòu)會自動把邏輯地址分為頁號和頁內(nèi)地址兩部分。用頁號為索引來檢索頁表。先將頁號和頁表長度比較，若頁號大于等于頁表長度，則表示本次所訪問的地址超過進程的地址空間，越界錯誤中斷。若無，則將頁表起始地址與頁號和頁表項長度的乘積相加，便得到該表項再頁表中的位置，由此可找到該頁的物理塊號。同時頁內(nèi)地址送入物理地址寄存器的塊內(nèi)地址字段中

24、。這樣便完成了邏輯地址到物理地址的轉(zhuǎn)換。如下圖例1： 若在一分頁存儲管理系統(tǒng)中，某作業(yè)的頁表如表所示，已知頁面大小為1024B，試將邏輯地址1011，2148，5012轉(zhuǎn)化為相應(yīng)的物理地址？畫出其地址轉(zhuǎn)換圖。頁號塊號02132136解：分析：頁面大小是1024B,即1M，可知頁面是10bit.由題知邏輯地址為： 物理地址為：（1）邏輯地址1011（十進制）的二進制表示為 00 1111110011 由此可知邏輯地址1011的頁號0，查頁表知該頁放在第2物理塊中，其物理地址的二進制表示為 010 1111110011 所以邏輯地址1011對應(yīng)的物理地址為0BF3H.其地址轉(zhuǎn)換圖如后所示。 （2）

25、略 （3）邏輯地址5012（十進制）的二進制表示為：100 1110010100 可知該邏輯地址的頁號為4，查頁表知該頁為不合法頁，則產(chǎn)生越界中斷。2.3 具有快表的地址變換機構(gòu) 引入基本的地址變換機構(gòu)存在的問題是CPU每次存取一個數(shù)據(jù)時，需要訪問內(nèi)存兩次，一次是訪問內(nèi)存中的頁表，最終得到物理地址，第二次才是真正的訪問數(shù)據(jù)。因此降低了速度。因此為了提高地址變換速度，我們引入了“快表”。 基本原理快表就是一個高速緩沖存儲器，存放當前訪問的那些頁表項，也就是快表中存放的是部分頁表。CPU產(chǎn)生的邏輯地址的頁首先在快表中尋找，若找到（命中），就找出其對應(yīng)的物理塊；若未找到（未命中），再到內(nèi)存的頁表中找

26、其對應(yīng)的物理塊，之后還要修改當前快表，把這個頁表項添加到快表中。圖見課本p133若快表中內(nèi)容滿，則按某種算法淘汰某些頁。2.4 兩級和多級頁表2.4.1 引言當一個計算機系統(tǒng)的邏輯地址空間非常大。則頁表就會很大，要占用大的內(nèi)存空間，而且要采用連續(xù)存儲方式。這實際上是沒法滿足的。因此我們提出兩個解決方法：1、 采用離散分配方式取代找一個大的內(nèi)存空間來存放頁表的問題。2、 只將當前需要的部分頁表放在內(nèi)存，其他頁表駐留在磁盤，需要時調(diào)入。2.4.2 兩級頁表采用的是第一種方法，用離散分配方式解決?；驹恚喊秧摫硪策M行分頁，并離散地將各個頁面分別存放在不同的物理塊中。這樣也就需要為離散分配的頁表再建

27、一個頁表，稱之為外層頁表，其用于記錄頁表頁面所對應(yīng)的物理塊號。如圖示 過程是：利用外層頁號（頁面頁表號），作為外層頁表的索引，從中找到指定頁表分頁的起始地址，再利用內(nèi)層頁號找到指定的頁表項，其中含有該頁所在的塊號，在和頁內(nèi)地址構(gòu)成實際的內(nèi)存物理地址。詳見P134。2.4.3 多級頁表將外層頁表再進行分頁，也將各外層頁表頁面離散地存放在不同的物理塊中，再利用第2級的外層頁表來記錄它們之間的對應(yīng)的關(guān)系。邏輯地址：如圖第四節(jié) 基本分段存儲管理方式1 分段存儲管理方式的引入為什么要引入分段？分段有哪些優(yōu)點？我們現(xiàn)在了解一下。1 方便編程： 因為實際編程中，用戶作業(yè)通常按照邏輯關(guān)系分為幾個段，每個段都是

28、從0開始編址，并有名字和長度，訪問的邏輯地址由段名和段內(nèi)偏移量決定。此存儲管理方式就按邏輯上有聯(lián)系的段來進行管理，方便編程。2 信息共享： 從上面可以得知，段是信息的邏輯單位，也就是段具有實際的邏輯意義。這和前一講的“頁”完全不同。因此要實現(xiàn)段的共享，就要求存儲管理能與用戶程序的分段組織方式相適應(yīng)。3 信息保護： 信息保護同樣是對信息的邏輯單位進行保護，因此分段管理方式能有效的實現(xiàn)信息保護。4 動態(tài)增長： 實際應(yīng)用中，某些段（數(shù)據(jù)段）會不斷增長，前面的存儲管理方法均難以實現(xiàn)。而分段卻可以解決這個問題。5 動態(tài)鏈接： 要求以段為單位。 由此我們理解為什么要引入分段存儲管理。2 分段系統(tǒng)的基本原理

29、2.1 空間劃分（分段）將用戶作業(yè)的地址空間依照相應(yīng)的邏輯信息組的長度來劃分若干個段，各段的長度不等。各段有段名（常用段號代替），段內(nèi)首地址為0。段地址結(jié)構(gòu)如下圖：一般我們常見的有代碼段、數(shù)據(jù)段、共享段等等。允許一個作業(yè)最長又64個段，每個段最大長度是64kB。2.2 內(nèi)存分配在為作業(yè)分配內(nèi)存時，也以段為單位，分配一段連續(xù)的物理地址空間；段間不必連續(xù)。如下圖注意：整個作業(yè)的邏輯地址空間是二維的，其邏輯地址由段號和段內(nèi)地址組成。1、 需要CPU的硬件支持（地址變換機構(gòu)）2.3 段表u 概念：系統(tǒng)中為每個進程建立一張段映射表，就是段表。u 段表內(nèi)容：每個段在表中占有一個表項，其中記錄了該段在內(nèi)存中

30、的起始地址（又叫“基址”）和段的長度。段表如下圖u 存儲位置：可以存儲于寄存器。但一般存放在內(nèi)存。u 作用：記錄了段與內(nèi)存位置的對應(yīng)關(guān)系u 注意：訪問一個字節(jié)的數(shù)據(jù)/指令需訪問內(nèi)存2次(段表一次,內(nèi)存一次),所以也出現(xiàn)內(nèi)存訪問速度降低的問題。利用段表實現(xiàn)地址映射如下圖2.4 地址變換機構(gòu)地址變換過程：系統(tǒng)中設(shè)置段表寄存器，用于存放段表起始地址和段表長度TL。在進行地址變換時，系統(tǒng)將邏輯地址中的段號與段表長度TL進行比較。若S>TL，則訪問越界。否則，根據(jù)段表的起始地址和該段的段號，計算出該段對應(yīng)段表項的位置，從中讀出該段在內(nèi)存中的起始地址。再檢查段內(nèi)地址D是否超過該段的段長SL。若超過則

31、越界，否則將該段的基址和段內(nèi)地址相加，即可得到要訪問的內(nèi)存物理地址。如下圖例1：在一個段式存儲管理系統(tǒng)中，其段表為： 段號 內(nèi)存起始地址 段長 0 210 500 1 2350 20 2 100 90 3 1350 590 4 1938 9504302120試求表中邏輯地址對應(yīng)的物理地址是什么？解：邏輯地址為：段號段內(nèi)地址邏輯地址 0430對應(yīng)的物理地址為：210+430=640邏輯地址 2120因為段內(nèi)地址120>段長90，所為該段為非法段。2.5 分頁和分段的主要區(qū)別3 信息共享與保存3.1共享：分頁系統(tǒng)中雖然也能實現(xiàn)程序和數(shù)據(jù)的共享，但遠不如分段系統(tǒng)方便。分段系統(tǒng)的一個突出優(yōu)點是易

32、于實現(xiàn)段的共享，允許若干個進程共享一個或多個分段，且對段的保護十分簡單易行。分段系統(tǒng)中，實現(xiàn)共享只需要在每個進程的段表中為共享段設(shè)置一個段表項。如圖其中，p1,p2是進程3.2 保護保護方式：地址越界保護；存取控制保護段表的改進，實際就是增加了存取控制字段如圖4 段頁式存儲管理方式引言：段式優(yōu)于頁式，便于共享和保護，沒有內(nèi)碎片，外碎片可以通過內(nèi)存“緊湊”來消除。頁式優(yōu)于段式，消除“外碎片”問題，沒有外碎片，每個內(nèi)碎片不超過頁大小。段頁式：結(jié)合二者優(yōu)點。每個進程包含若干段，每個段包含若干頁1 基本原理基本原理：是先將用戶程序分成若干個段，再把每個段分成若干個頁，并為每一個段賦予一個段名。再把每個

33、段分成若干個頁（頁式）。其地址結(jié)構(gòu)由段號、段內(nèi)頁號、及頁內(nèi)位移三部分所組成。下圖是作業(yè)地址空間和地址結(jié)構(gòu)。該圖顯示一個作業(yè)有三個段。頁面大小是4kB.分別是主程序段、子程序段、數(shù)據(jù)段。04K8K12K15K16K主程序段04K8K子程序段04K8K12K10K數(shù)據(jù)段作業(yè)地址空間：地址結(jié)構(gòu)：頁內(nèi)地址(W)段內(nèi)頁號(P)段號(S)2 地址變換過程2.1 地址變換過程在段頁式系統(tǒng)中，為了實現(xiàn)地址變換，增加一個段表寄存器，用來存放段表始址和段長。進行地址變換時，首先利用段號S和段長TL比較。若S<TL，表示沒越界。于是利用段表起始地址和段號求出該段所對應(yīng)的段表項在段表的位置，從中得到該段的頁表地

34、址，并利用邏輯地址中的段內(nèi)頁號P來獲得對應(yīng)頁的頁表項位置，從中讀出該頁所在的物理塊號b，再利用塊號b和頁內(nèi)地址來構(gòu)成物理地址。如下圖所示。注意：在段頁式系統(tǒng)中，為了獲得一條指令或數(shù)據(jù)，需要訪問三次內(nèi)存：第一次：訪問內(nèi)存中的段表，取得頁表始址第二次：訪問內(nèi)存中的頁表，取得該頁所在的物理塊號，將塊號與頁內(nèi)地址形成物理地址第三次：訪問第二次所得的地址，取出指令或數(shù)據(jù)解決方法：增設(shè)高速緩沖寄存器-快表第五節(jié) 虛擬存儲器虛擬存儲器，對換，覆蓋都是從邏輯上擴充內(nèi)存容量1 引入1.1 常規(guī)內(nèi)存管理方式的特征常規(guī)存儲管理的特征：§ 一次性（指全部裝入）。也就是要求作業(yè)在運行前一次性的全部裝入內(nèi)存。但

35、是許多作業(yè)在運行時，并不是全部程序和數(shù)據(jù)都要用到，如果一次性全部裝入，其實就是對內(nèi)存空間的浪費。§ 駐留性（指駐留在內(nèi)存不換出）。是指作業(yè)裝入內(nèi)存后，一直駐留在內(nèi)存，直到作業(yè)運行結(jié)束。一直占用內(nèi)存資源。1.2 局部性原理概念：指程序在執(zhí)行時呈現(xiàn)出局部性規(guī)律，即在一較短時間內(nèi)，程序的執(zhí)行僅限于某個部分，相應(yīng)地，它所訪問的存儲空間也局限于某個區(qū)域。§ 時間局部性：如循環(huán)執(zhí)行。§ 空間局部性：如順序執(zhí)行。1.3 虛擬存儲器的概念u 基于局部性原理，程序在運行之前，沒有必要全部裝入內(nèi)存，僅須將當前要運行的頁（段）裝入內(nèi)存即可。u 運行時，如訪問的頁（段）在內(nèi)存中，則繼續(xù)執(zhí)

36、行，如訪問的頁未在內(nèi)存中（缺頁或缺段），則利用OS的請求調(diào)頁（段）功能，將該頁（段）調(diào)入內(nèi)存。 u 如內(nèi)存已滿，則利用OS的頁（段）置換功能，按某種置換算法將內(nèi)存中的某頁（段）調(diào)至外存，從而調(diào)入需訪問的頁。 虛擬存儲器是指僅把作業(yè)的一部分裝入內(nèi)存便可運行作業(yè)的存儲管理系統(tǒng)，它具有請求頁調(diào)入功能和頁置換功能，能從邏輯上對內(nèi)存容量進行擴充，其邏輯容量由外存容量和內(nèi)存容量之和決定，其運行速度接近于內(nèi)存，成本接近于外存。2 虛擬存儲器的實現(xiàn)方法虛擬存儲器的實現(xiàn)，都建立在離散分配的存儲管理方式基礎(chǔ)上。2,1 分頁請求系統(tǒng) 在分頁系統(tǒng)的基礎(chǔ)上，增加了請求調(diào)頁功能、頁面置換功能所形成的頁式虛擬存儲器系統(tǒng)。

37、它允許只裝入若干頁的用戶程序和數(shù)據(jù)，便可啟動運行，以后再硬件支持下通過調(diào)頁功能和置換頁功能，陸續(xù)將要運行的頁面調(diào)入內(nèi)存，同時把暫不運行的頁面換到外存上，置換時以頁面為單位。 系統(tǒng)須設(shè)置相應(yīng)的硬件支持和軟件：（1）硬件支持：請求分頁的頁表機制、缺頁中斷機構(gòu)和地址變換機構(gòu)。（2）軟件：請求調(diào)頁功能和頁置換功能的軟件。2.2 分段請求系統(tǒng) 在分段系統(tǒng)的基礎(chǔ)上，增加了請求調(diào)段功能及分段置換功能，所形成的段式虛擬存儲器系統(tǒng)。 它允許只裝入若干段的用戶程序和數(shù)據(jù)，便可啟動運行，以后再硬件支持下通過請求調(diào)段功能和分段置換功能，陸續(xù)將要運行的段調(diào)入內(nèi)存，同時把暫不運行的段換到外存上，置換時以段為單位。系統(tǒng)須設(shè)

38、置相應(yīng)的硬件支持和軟件：（1）硬件支持：請求分段的段表機制、缺段中斷機構(gòu)和地址變換機構(gòu)（2）軟件：請求調(diào)段功能和段置換功能的軟件3 虛擬存儲器特征u 離散性：在分配內(nèi)存時采用離散分配方式u 多次性：一個作業(yè)被分成多次調(diào)入內(nèi)存運行u 對換性：允許在作業(yè)的運行過程中進行換進、換出。u 虛擬性：能夠從邏輯上擴充內(nèi)存容量，使用戶所看到的內(nèi)存容量遠大于實際內(nèi)存容量。注意：虛擬性以多次性和對換性為基礎(chǔ)；多次性和對換性又必須建立在離散分配的基礎(chǔ)上。第六節(jié) 請求分頁存儲管理方式1 基本概述請求分頁管理是建立在基本分頁基礎(chǔ)上的，為了能支持虛擬存儲器而增加了請求調(diào)頁功能和頁面置換功能?；驹恚旱刂房臻g的劃分同頁

39、式；裝入頁時，可裝入作業(yè)的一部分(運行所需)頁即可運行。2 請求分頁的硬件支持為實現(xiàn)請求分頁，需要一定的硬件支持，包括：頁表機制、缺頁中斷機構(gòu)、地址變換機構(gòu)。2.1 頁表機制作用：將用戶地址空間的邏輯地址轉(zhuǎn)換為內(nèi)存空間的物理地址。因為請求分頁的特殊性，即程序的一部分調(diào)入內(nèi)存，一部分仍在外存，因此頁表結(jié)構(gòu)有所不同。如圖：頁號塊號狀態(tài)位訪問字段修改位外存地址說明：（1）狀態(tài)位P：指示該頁是否已調(diào)入內(nèi)存。（2）訪問字段A：記錄本頁在一段時間內(nèi)被訪問的次數(shù)或最近未被訪問的時間。（3）修改位M：表示該頁在調(diào)入內(nèi)存后是否被修改過。若修改過，則換出時需重寫至外存。（4）外存地址：指出該頁在外存上的地址。2.

40、2 缺頁中斷機構(gòu)在請求分頁系統(tǒng)中，每當所要訪問的頁面不在內(nèi)存時，便產(chǎn)生缺頁中斷，請求OS將所缺的頁調(diào)入內(nèi)存。缺頁中斷與一般中斷的區(qū)別：（1）在指令執(zhí)行期間產(chǎn)生和處理中斷信號（2）一條指令在執(zhí)行期間，可能產(chǎn)生多次缺頁中斷2.3 地址變換機構(gòu)請求分頁系統(tǒng)的地址變換機構(gòu)。是在分頁系統(tǒng)地址變換機構(gòu)的基礎(chǔ)上，又增加了一些功能。例：某虛擬存儲器的用戶空間共有32個頁面，每頁1KB，主存16KB。假定某時刻系統(tǒng)為用戶的第0、1、2、3頁分別分配的物理塊號為5、10、4、7，試將虛擬地址0A5C和093C變換為物理地址。解：虛擬地址為：頁號（25=32）5位 頁內(nèi)位移（1K =210=1024）10位 物理地

41、址為 物理塊號（24=16）4位 因為頁內(nèi)是10 位， 塊內(nèi)位移（1K =210=1024）10位虛擬地址OA5C對應(yīng)的二進制為： 00010 1001011100 即虛擬地址OA5C的頁號為2，頁內(nèi)位移為1001011100，由題意知對應(yīng)的物理地址為：0100 1001011100即125C同理求093C。略3 內(nèi)存分配策略和分配算法在請求分頁系統(tǒng)中，為進程分配內(nèi)存時，將涉及以下三個問題：最小物理塊數(shù)的確定；物理塊的分配策略；物理塊的分配算法。3.1 最小物理塊數(shù)的確定概念：最小物理塊數(shù)：是指能保證進程正常運行所需的最小物理塊數(shù)。確定方法：與計算機的硬件結(jié)構(gòu)有關(guān)，取決于指令的格式、功能和尋址

42、方式。3.2 物理塊的分配策略內(nèi)存分配策略：固定和可變分配策略置換策略：全局置換和局部置換三種合適的策略如下：（1）固定分配局部置換（Fixecd Allocation,Local replacement）：為每個進程分配固定數(shù)目n的物理塊，在整個運行中都不改變。如出現(xiàn)缺頁，則從中置換一頁。（2）可變分配全局置換(VariableAllocatio,Global Repalcement)：分配固定數(shù)目的物理塊，但OS自留一空閑塊隊列，若發(fā)現(xiàn)缺頁，則從空閑塊隊列中分配一空閑塊與該進程，并調(diào)入缺面于其中。當空閑塊隊列用完時，OS才從內(nèi)存中任選擇一頁置換。（3）可變分配局部置換(VariableAl

43、locatio,Local Repalcement)：分配一定數(shù)目的物理塊，若發(fā)現(xiàn)缺頁，則從該進程的頁面中置換一頁，根據(jù)該進程缺頁率高低，則可增加或減少物理塊。3.3 物理塊的分配算法在采用固定分配策略時，將系統(tǒng)中可供分配的所有物理塊分配給各個進程，可采用以下幾種算法：（1）平均分配算法：將系統(tǒng)中所有可供分配的物理塊，平均分配給每個進程。缺點：未考慮各進程本身的大小。（2）按比例分配算法：這是根據(jù)進程的大小按比例分配物理塊的算法。如果系統(tǒng)中共有n個進程，每個進程的頁面數(shù)為Si，則系統(tǒng)中各進程頁面數(shù)的總和為：又假定系統(tǒng)中可用的物理塊總數(shù)為m，則每個進程所能分到的物理塊數(shù)為bi，將有：b應(yīng)該取整，

44、它必須大于最小物理塊數(shù)。 （3）考慮優(yōu)先權(quán)的分配算法：將系統(tǒng)提供的物理塊一部分根據(jù)進程大小先按比例分配給各個進程，另一部分再根據(jù)各進程的優(yōu)先權(quán)適當增加物理塊數(shù)。4 調(diào)頁策略什么時候?qū)⒁粋€頁面由外存調(diào)入內(nèi)存？從何處將頁面調(diào)入內(nèi)存？這就是調(diào)頁策略所要解決的問題。4.1 何時調(diào)入頁面？v 預調(diào)頁策略：將那些預計在不久便被訪問的頁預先調(diào)入內(nèi)存。這種調(diào)入策略提高了調(diào)頁的效率，減少了I/O次數(shù)。但由于這是一種基于局部性原理的預測，若預調(diào)入的頁面在以后很少被訪問，則造成浪費，故這種方式常用于程序的首次調(diào)入。v 請求調(diào)頁策略：當進程運行中訪問的頁出現(xiàn)缺頁時，則發(fā)出缺頁中斷，提出請求調(diào)頁，由OS將所需頁調(diào)入內(nèi)存

45、。這種策略實現(xiàn)簡單，應(yīng)用于目前的虛擬存儲器中，但易產(chǎn)生較多的缺頁中斷，且每次調(diào)一頁，系統(tǒng)開銷較大，容易產(chǎn)生抖動現(xiàn)象。注意：首次：預調(diào)頁；運行時：請求調(diào)頁。4.2從何處調(diào)入頁面？ 在請求分頁系統(tǒng)中，通常將外存分成了文件區(qū)和對換區(qū)，文件區(qū)按離散分配方式存放文件，對換區(qū)按連續(xù)分配方式存放對換頁。 v 系統(tǒng)有足夠的對換區(qū)空間情況：運行前可將與進程相關(guān)的文件從文件區(qū)復制至對換區(qū)，以后缺頁時，全部從對換區(qū)調(diào)頁。只從對換區(qū)調(diào)頁。v 系統(tǒng)沒有足夠的對換區(qū)空間情況：頁面不會被修改：凡是不會被修改的文件，每次都直接從文件區(qū)調(diào)頁，換出時不必換出。只從文件區(qū)調(diào)頁。頁面可能被修改：若對可能會修改的文件第一次調(diào)頁直接從文

46、件區(qū)，換出時換至對換區(qū)，以后從對換區(qū)調(diào)頁。第一次從文件區(qū)調(diào)入以后從對換區(qū)。從文件區(qū)/對換區(qū)調(diào)頁v UNIX方式：凡未運行過的頁面均從文件區(qū)調(diào)頁，運行過的頁面和換出的頁面均從對換區(qū)調(diào)頁。5 頁面調(diào)入過程 了解過程如下：每當程序所要訪問的頁面未在內(nèi)存時，便向CPU發(fā)出一缺頁中斷，中斷處理程序首先保留CPU環(huán)境，分析中斷原因后，轉(zhuǎn)入缺頁中斷處理程序。該程序通過查找頁表，得到該頁在外存上的物理塊后，如果此時內(nèi)存能容納新頁，則啟動磁盤I/O將所缺之頁調(diào)入內(nèi)存，然后修改頁表。如果內(nèi)存已滿，則需按照某種置換算法從內(nèi)存中選出一頁準備換出；如果該頁未被修改過，可不必寫回磁盤；但如果此頁已被修改，則必須將它寫回磁

47、盤，然后把所缺的頁調(diào)入內(nèi)存，并修改頁表中的相應(yīng)表項，置其存在位為“1”，并將此頁表項寫入快表。在缺頁調(diào)入內(nèi)存后，利用修改后的頁表，形成所要訪問的物理地址，再去訪問內(nèi)存數(shù)據(jù)。流程如下：第七節(jié) 頁面置換算法1 引言在進程運行過程中，若其訪問的頁面不在內(nèi)存而需將其調(diào)入，但內(nèi)存已無空閑空間時，需從內(nèi)存中調(diào)出一頁程序或數(shù)據(jù)，送入磁盤的對換區(qū)。但應(yīng)將哪個頁面調(diào)出，需根據(jù)一定的算法來確定。把選擇換出頁面的算法稱為頁面置換算法，其好壞直接影響系統(tǒng)的性能。剛被淘汰出內(nèi)存的頁面，過后不久又要訪問它，需要再次將其調(diào)入，而該頁調(diào)入內(nèi)存后不入又再次被淘汰出內(nèi)存，然后又要訪問它，如此反復，這種現(xiàn)象稱為抖動（又稱顛簸）。

48、一個好的置換算法應(yīng)具有較低的頁面更換頻率。從理論上講，應(yīng)將那些以后不會再訪問的頁面換出，或者把那些在較長時間內(nèi)不會再訪問的頁面換出。2 常用的頁面置換算法2.1 最佳置換算法（The best optimal） 最佳置換算法是由Belady于1966年提出的一種理論上的算法。其所選擇的被淘汰頁面，將是以后永不使用的， 或許是在最長(未來)時間內(nèi)不再被訪問的頁面。采用最佳置換算法，通常可保證獲得最低的缺頁率。 由于人們無法預知一個進程在內(nèi)存的若干個頁面中，哪一個頁面是將來最長時間內(nèi)不再被訪問的頁面，因此該算法無法實現(xiàn)。但該算法可以用來評價其他算法。例：就是課本上的例子假定系統(tǒng)為某進程分配了三個物

49、理塊， 并考慮有以下的頁面號引用串：7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1 2.2 先進先出頁面置換算法(FIFO)該算法淘汰最先進入內(nèi)存的頁面，即選擇在內(nèi)存中駐留時間最久的頁面淘汰。Belady現(xiàn)象：使用FIFO算法時，在未給進程或作業(yè)分配足它所要求的頁面數(shù)時，有時會出現(xiàn)分配的頁面增多，缺頁次數(shù)反而增加的奇怪現(xiàn)象，就是Belady現(xiàn)象。例：和上例一樣例子：1，2，3，4，1，2，5，1，2，3，4，5內(nèi)存3個物理頁面：缺頁9次內(nèi)存4個物理頁面：缺頁10次 異常！ Belady現(xiàn)象2.3最近最久未使用置換算法(Least Recently Used,LR

50、U) 算法描述算法思想：利用“最近的過去”作為“最近的將來”。選擇最近最久未使用的頁面淘汰。該算法對每個頁面設(shè)置一個訪問字段，用于記錄一個頁面自上次被訪問以來所經(jīng)歷的時間t,每次淘汰t值最大的頁面，也就是最近最久未使用的頁面。例：缺頁12次，總訪問次數(shù)20次，缺頁率12/2060 硬件支持兩類硬件支持：寄存器、棧。為每個在內(nèi)存中的頁面配置一個移位寄存器，用來記錄某進程在內(nèi)存中各頁的使用情況。移位寄存器表示為 R=當進程訪問某物理塊時，要將相應(yīng)寄存器的位置成1。此時，定時信號將每隔一定時間將寄存器右移一位。如果把n位寄存器的數(shù)看作一個整數(shù)，那么具有最小數(shù)值的寄存器所對應(yīng)的頁面，就是最近最久未使用

51、的頁面。例：某進程在內(nèi)存中具有8個頁面，為每個頁面配置一個8位寄存器。如下圖：2.3.3 棧利用一個特殊的棧來保存當前使用的各個頁面的頁面號。每當進程訪問某頁面時，便將該頁面的頁面號從棧中移出，將它壓入棧頂。因此，棧頂始終是最新被訪問頁面的編號，而棧底則是最近最久未使用頁面的頁面號。如下圖：R0R1R2R3R4R5R6R7 R 實頁 000101111001111001101011010101011000100001010101100110010100100012345678某進程具有8個頁面時的LRU訪問情況444774700407740711471004701147012247021147

52、0122701266設(shè)一進程訪問頁面的頁面號序列為：4，7，0，7，1，0，1，2，1，2，6隨著進程的訪問，棧中頁面號的變化情況：2.4 CLOCK置換算法是一種最近最久未使用算法的近似算法。 簡單的CLOCK置換算法算法描述：v 每頁設(shè)置一位訪問位，某頁被訪問時，其訪問位被置1。內(nèi)存中的所有頁鏈接成一個循環(huán)隊列；v 循環(huán)檢查各頁面的使用情況，訪問位為“0”，選擇該頁淘汰；訪問位為“1”，復位訪問位為“0”，查詢指針前進一步。v 因為該算法只有一位訪問位，只能用它表示該頁是否使用過，置換時只能將未使用過的頁面置換出去，因此稱為“最近未使用”置換算法（NRU）例子：2.4.2 改進型的CLOC

53、K置換算法1 由訪問位A和修改位M可以組合成下面四種類型的頁面： 1類(A=0, M=0): 表示該頁最近既未被訪問，又未被修改， 是最佳淘汰頁。 2類(A=0, M=1)： 表示該頁最近未被訪問，但已被修改， 并不是很好的淘汰頁。 3類(A=1, M=0)： 最近已被訪問， 但未被修改，該頁有可能再被訪問。 4類(A=1, M=1): 最近已被訪問且被修改，該頁可能再被訪問。 2 執(zhí)行過程訪問位A，修改位M共同表示一個頁面的狀態(tài)：四種狀態(tài)：00 01 10 11。三輪掃描：第一輪：查找00頁面，若找到，則淘汰所找到的第一頁，結(jié)束；若未找到，下一步；第二輪：查找01頁面，若找到，則淘汰所找到的第一頁，結(jié)束；，若未找到，下一步；（第二輪中，所有掃描過的頁面，A位復位為“0”）第三輪：所有頁面A位復位為“0”，重復第一步。2.5 其他置換算法最少使用(LFU： Least Frequently Used)置換算法Ø 選擇到當前時間為止被訪問次數(shù)最少的頁面被置換；Ø 每頁設(shè)置訪問計數(shù)器，每當頁面被訪問時，該頁面的訪問計數(shù)器加1；Ø 發(fā)生