存儲(chǔ)器管理95191

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

52、0122701266設(shè)一進(jìn)程訪(fǎng)問(wèn)頁(yè)面的頁(yè)面號(hào)序列為：4，7，0，7，1，0，1，2，1，2，6隨著進(jìn)程的訪(fǎng)問(wèn)，棧中頁(yè)面號(hào)的變化情況：2.4 CLOCK置換算法是一種最近最久未使用算法的近似算法。 簡(jiǎn)單的CLOCK置換算法算法描述：v 每頁(yè)設(shè)置一位訪(fǎng)問(wèn)位，某頁(yè)被訪(fǎng)問(wèn)時(shí)，其訪(fǎng)問(wèn)位被置1。內(nèi)存中的所有頁(yè)鏈接成一個(gè)循環(huán)隊(duì)列；v 循環(huán)檢查各頁(yè)面的使用情況，訪(fǎng)問(wèn)位為“0”，選擇該頁(yè)淘汰；訪(fǎng)問(wèn)位為“1”，復(fù)位訪(fǎng)問(wèn)位為“0”，查詢(xún)指針前進(jìn)一步。v 因?yàn)樵撍惴ㄖ挥幸晃辉L(fǎng)問(wèn)位，只能用它表示該頁(yè)是否使用過(guò)，置換時(shí)只能將未使用過(guò)的頁(yè)面置換出去，因此稱(chēng)為“最近未使用”置換算法（NRU）例子：2.4.2 改進(jìn)型的CLOC

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