c第四章 存儲(chǔ)器管理

第四章存儲(chǔ)器管理4.0存儲(chǔ)器的層次結(jié)構(gòu)4.1程序的裝入和鏈接4.2連續(xù)分配方式4.3基本分頁(yè)存儲(chǔ)管理方式4.4基本分段存儲(chǔ)管理方式4.5虛擬存儲(chǔ)器的基本概念4.6請(qǐng)求分頁(yè)存儲(chǔ)管理方式4.8頁(yè)面置換算法4.9請(qǐng)求分段存儲(chǔ)管理方式內(nèi)存(MainMemory或PrimaryMemory或RealMemory)也稱主存,是指CPU能直接存取指令和數(shù)據(jù)的存儲(chǔ)器。圖

內(nèi)存在計(jì)算機(jī)系統(tǒng)中的地位4.0存儲(chǔ)器的層次結(jié)構(gòu)高速緩存主存儲(chǔ)器（簡(jiǎn)稱內(nèi)存或主存）外存儲(chǔ)器（軟盤、硬盤、光盤）磁盤內(nèi)存儲(chǔ)器：存儲(chǔ)管理外存儲(chǔ)器：設(shè)備管理寄存器

磁盤緩存可移動(dòng)存儲(chǔ)介質(zhì)4.0存儲(chǔ)器的層次結(jié)構(gòu)功能：儲(chǔ)存以二進(jìn)位形式表示的程序和數(shù)據(jù)分類：內(nèi)存儲(chǔ)器/外存儲(chǔ)器內(nèi)存儲(chǔ)器外存儲(chǔ)器(簡(jiǎn)稱外存或輔存)存取速度很快較慢存儲(chǔ)容量較小(因單位成本較高)很大(因單位成本較低)性質(zhì)斷電后信息消失斷電后信息保持用途存放已經(jīng)啟動(dòng)運(yùn)行的程序和需要立即處理的數(shù)據(jù)長(zhǎng)期存放計(jì)算機(jī)系統(tǒng)中幾乎所有的信息與CPU關(guān)系CPU所處理的指令及數(shù)據(jù)直接從內(nèi)存中取出程序及相關(guān)數(shù)據(jù)必須先送入內(nèi)存后才能被CPU使用在多道程序環(huán)境下，程序要運(yùn)行必須為之創(chuàng)建進(jìn)程，而創(chuàng)建進(jìn)程的第一件事，就是要將程序和數(shù)據(jù)裝入內(nèi)存。如何將一個(gè)用戶源程序變?yōu)橐粋€(gè)可在內(nèi)存中執(zhí)行的程序，通常要經(jīng)過以下幾步:（1）編譯：由編譯程序（Compiler）將用戶源代碼編譯成若干個(gè)目標(biāo)模塊（ObjectModule）；（2）鏈接：由鏈接程序（Linker）將編譯后形成的目標(biāo)模塊以及它們所需要的庫(kù)函數(shù)，鏈接在一起，形成一個(gè)裝入模塊（LoadModule）；（3）裝入：由裝入程序（Loader）將裝入模塊裝入內(nèi)存。4.1程序的裝入和鏈接4.1程序的裝入和鏈接圖4-1對(duì)用戶程序的處理步驟1)靜態(tài)鏈接：在裝入內(nèi)存前鏈接成一個(gè)大的裝入模塊module。但需要解決兩個(gè)問題，即：

(1)修改相對(duì)地址。

(2)變換外部調(diào)用符號(hào)。2)裝入時(shí)動(dòng)態(tài)鏈接：邊裝入邊鏈接，即裝入一個(gè)模塊時(shí)，便去找它的調(diào)用模塊，如有便再裝入，同時(shí)修改目標(biāo)模塊中的相對(duì)地址。由于分開裝入：便于模塊更新修改；便于模塊的共享。3)運(yùn)行時(shí)動(dòng)態(tài)鏈接:

將對(duì)某些目標(biāo)模塊的鏈接推遲到執(zhí)行時(shí)才進(jìn)行。凡在執(zhí)行過程中未被用到的目標(biāo)模塊，都不會(huì)被調(diào)入內(nèi)存或被鏈接到裝入模塊上，這樣不僅可加快程序的裝入過程，而且可節(jié)省大量的內(nèi)存空間。4.1.2程序的鏈接圖4-3程序鏈接示意圖4.1.1程序的裝入絕對(duì)裝入方式可重定位裝入方式（靜態(tài)重定位）動(dòng)態(tài)運(yùn)行時(shí)裝入方式（動(dòng)態(tài)重定位）重要的術(shù)語(yǔ)：

邏輯地址，是目標(biāo)程序中的地址。這種地址一般以0為基地址，順序編址。一個(gè)作業(yè)或進(jìn)程的目標(biāo)程序（準(zhǔn)確地說應(yīng)是裝入模塊）的邏輯地址的集合稱為該作業(yè)或進(jìn)程的邏輯地址空間，或稱地址空間或虛擬空間。邏輯地址也稱相對(duì)地址或虛擬地址。

物理地址，是物理存貯器的單元地址。物理地址的集合稱為物理地址空間，或稱存儲(chǔ)空間或?qū)嵉刂房臻g。物理地址也稱絕對(duì)地址或?qū)嵉刂贰?/p>

重定位：把裝入模塊中指令的邏輯地址以及數(shù)據(jù)的邏輯地址變換成內(nèi)存中物理地址的過程稱為重定位。1.絕對(duì)裝入：只能將目標(biāo)模塊裝入指定的內(nèi)存位置缺點(diǎn)：（1）在程序中必須由程序員給出絕對(duì)地址。或者說此時(shí)的相對(duì)地址和絕對(duì)地址一樣；（2）要求程序員對(duì)內(nèi)存使用情況非常熟悉。事先知道自己的程序?qū)⒁b在什么地方；（3）只適合于單道程序環(huán)境。例如：某個(gè)程序員想在內(nèi)存200處編一個(gè)程序：Movax,[204]35h200204Movax,[204]35h裝入程序邏輯地址相對(duì)地址內(nèi)存中進(jìn)程絕對(duì)地址物理地址….20020402.可重定位的裝入：裝入時(shí)將邏輯地址轉(zhuǎn)換為物理地址(重定位)，邏輯地址從0開始。適合于多道程序環(huán)境。地址變換在裝入時(shí)一次性完成，以后不變，可看作是靜態(tài)重定位。Movax,[2500]3650100025005000例如:準(zhǔn)備將程序裝入內(nèi)存10000處1000015000Movax,[2500]3651100012500Movax,[12500]365注意：這種裝入后程序不便在內(nèi)存中移動(dòng)。Why?3.動(dòng)態(tài)運(yùn)行時(shí)裝入：模塊裝入內(nèi)存后沒有立即重定位，仍然是相對(duì)地址；只有當(dāng)CPU執(zhí)行到具有相對(duì)地址的代碼時(shí)才去重定位，因此是動(dòng)態(tài)重定位。Movax,[2500]365010002500500010000150001100012500Movax,[2500]3652500相對(duì)地址10000重定位寄存器＋12500這種裝入后程序可以內(nèi)存中移動(dòng)，但需要重定位寄存器的硬件支持。內(nèi)存的分配提綱內(nèi)存分配的總的介紹：連續(xù)分配方式--〉離散分配方式連續(xù)1.單一連續(xù)分配2.固定分區(qū)分配3.動(dòng)態(tài)分區(qū)分配4.動(dòng)態(tài)重定位分區(qū)分配離散1.基本分頁(yè)存儲(chǔ)管理2.基本分段存儲(chǔ)管理3.段頁(yè)式存儲(chǔ)管理對(duì)換技術(shù)1.請(qǐng)求分頁(yè)存儲(chǔ)管理2.請(qǐng)求分段存儲(chǔ)管理虛擬存儲(chǔ)器4.2連續(xù)分配方式4.2.1單一連續(xù)分配最簡(jiǎn)單的一種存儲(chǔ)管理方式將內(nèi)存分為系統(tǒng)區(qū)和用戶區(qū)兩部分，系統(tǒng)區(qū)僅提供給OS使用，通常是放在內(nèi)存的低址部分；用戶區(qū)是指除系統(tǒng)區(qū)以外的全部?jī)?nèi)存空間，提供給用戶使用只能用于單用戶、單任務(wù)的操作系統(tǒng)例如：一個(gè)容量為256k的內(nèi)存，OS占用32K。操作系統(tǒng)作業(yè)用戶區(qū)0KB32KB96KB256KB-14.2.2固定分區(qū)分配最簡(jiǎn)單的多道程序的存儲(chǔ)管理方式主要思想：在單一連續(xù)分配的基礎(chǔ)上，將用戶區(qū)劃分成若干個(gè)固定大小的區(qū)，每個(gè)區(qū)可以放一個(gè)作業(yè)進(jìn)程，多個(gè)進(jìn)程并發(fā)。系統(tǒng)一啟動(dòng)后就已經(jīng)分好了分區(qū)；4.2.2固定分區(qū)分配分區(qū)大小劃分方法：（a）分區(qū)大小相等：缺乏靈活性，當(dāng)程序太小時(shí)，內(nèi)存空間浪費(fèi)；當(dāng)程序太大時(shí)，一個(gè)分區(qū)又不足以裝入該程序。通常適合于控制多個(gè)相同對(duì)象的場(chǎng)合。（b）分區(qū)大小不等：將內(nèi)存劃分成含多個(gè)較小的分區(qū)、適量的中等分區(qū)及少量的大分區(qū)。操作系統(tǒng)用戶區(qū)分區(qū)1分區(qū)2分區(qū)3…操作系統(tǒng)用戶區(qū)分區(qū)5分區(qū)4分區(qū)1分區(qū)2分區(qū)34.2.2固定分區(qū)分配如何分配

（a）分區(qū)使用表：表中包含每個(gè)分區(qū)的起始地址、大小、狀態(tài)。

（b）分配方法：在分區(qū)使用表中找出一個(gè)能滿足要求的、尚未分配的分區(qū)。將該分區(qū)分給程序、并修改分區(qū)使用表點(diǎn)擊鼠標(biāo)：對(duì)1k、9k、33k、121k作業(yè)分配內(nèi)存，并修改分區(qū)狀態(tài)浪費(fèi)（陰影部分）：7k23k87k211k總浪費(fèi)：328k操作系統(tǒng)0K20K28K60K180K512k-1分區(qū)1分區(qū)2分區(qū)3分區(qū)4內(nèi)存分區(qū)情況分區(qū)號(hào)起始地址大小狀態(tài)1未分配2未分配3未分配4未分配180k20k8k例題：某系統(tǒng)采用固定分區(qū)管理方式，內(nèi)存分區(qū)如圖。現(xiàn)有大小為1k、9k、33k、121k要求進(jìn)入內(nèi)存，畫出他們進(jìn)入內(nèi)存的空間分配情況，說明主存浪費(fèi)多大。28k60k32k120k332k分區(qū)使用表1k9k33k121k已分配已分配已分配已分配4.2.3動(dòng)態(tài)分區(qū)分配含義：根據(jù)作業(yè)進(jìn)程的需要，動(dòng)態(tài)的分配內(nèi)存。系統(tǒng)剛啟動(dòng)時(shí)并不分區(qū)。數(shù)據(jù)結(jié)構(gòu)：用來描述空閑分區(qū)和已分配分區(qū)的情況。常用的數(shù)據(jù)結(jié)構(gòu)有以下兩種形式：空閑分區(qū)鏈：以鏈表形式記錄每個(gè)空閑分區(qū)的情況?？臻e分區(qū)表：以表結(jié)構(gòu)形式記錄每個(gè)空閑分區(qū)的情況。例如：操作系統(tǒng)0K20K28K60K180K1k9k33k121k21K37K93K301K空閑分區(qū)表分區(qū)號(hào)起始地址大小狀態(tài)1234301k21k7k37k93k23k87k211k空閑空閑空閑空閑4.2.3動(dòng)態(tài)分區(qū)分配分配算法：（1）首次適應(yīng)算法：從空閑分區(qū)表或分區(qū)鏈（按照地址遞增次序排列）頭上開始查找，找到第一個(gè)滿足要求的分區(qū)為止，分配內(nèi)存，余下的部分然仍留在空閑分區(qū)表中。優(yōu)點(diǎn)：傾向于優(yōu)先利用內(nèi)存低地址部分的空閑分區(qū)；保留了高地址部分的空閑分區(qū)。缺點(diǎn)：低地址部分不斷被劃分，留下很多碎片.

例題：例題：已知主存有256k容量，其中os占地端內(nèi)存20k，有下列作業(yè)序列：分析內(nèi)存分配情況和空閑分區(qū)表情況作業(yè)1要求80k；作業(yè)2要求16k；作業(yè)3要求140k

作業(yè)1完成；作業(yè)3完成；作業(yè)4要求60k；作業(yè)5要求120k操作系統(tǒng)0k20k256k-1空閑分區(qū)表分區(qū)號(hào)起始地址大小120k236k作業(yè)1來到操作系統(tǒng)0k20k256k-1空閑分區(qū)表分區(qū)號(hào)起始地址大小1100k156k作業(yè)1100k剛開始時(shí)作業(yè)216k作業(yè)3140k分別來到后空閑分區(qū)表分區(qū)號(hào)起始地址大小1100k156k操作系統(tǒng)0k20k256k-1作業(yè)1100k作業(yè)2作業(yè)3116k1116k140k0作業(yè)1完成作業(yè)3完成操作系統(tǒng)0k20k256k-1作業(yè)1100k作業(yè)2作業(yè)3116k空閑分區(qū)表分區(qū)號(hào)起始地址大小120k80k2116k140k作業(yè)460k作業(yè)5120k（12k?)分別來到180k20k作業(yè)4作業(yè)51236k20kback4.2.3動(dòng)態(tài)分區(qū)分配分配算法：（2）最佳適應(yīng)算法：每次為作業(yè)分配內(nèi)存時(shí)，總是找一個(gè)既能滿足要求、又是最小的空閑分區(qū)分配給作業(yè)。特點(diǎn)：為提高程序中查找速度，常常將分配表按照分區(qū)容量按照從小到大排列，查找時(shí)只需要從表首按順序查找最合適的。缺點(diǎn)：都在找最合適的分割，常會(huì)剩下一些小碎片

例題：例題：已知內(nèi)存分配情況如下圖。要求填寫空閑分區(qū)表，并分配如下作業(yè)序列作業(yè)4大小2k，作業(yè)5大小6k，作業(yè)6大小2k操作系統(tǒng)作業(yè)10k20k256k-110k25k作業(yè)23k35k45k作業(yè)3156k48k100k分區(qū)號(hào)起始地址大小空閑分區(qū)表125k10k245k3k3100k156k作業(yè)4247k1k作業(yè)5131k4k作業(yè)6133k2k改進(jìn)：空閑分區(qū)表（按大小排列，便于程序）分區(qū)號(hào)起始地址大小225k10k3100k156k145k3k4.2.3動(dòng)態(tài)分區(qū)分配分配算法：（3）最壞適應(yīng)算法每次分配總是挑選出分配表（鏈）中最大的分區(qū)進(jìn)行分配（4）循環(huán)首次適應(yīng)算法由首次適應(yīng)算法演變而來（5）快速適應(yīng)算法又稱為分類搜索算法，將空閑分區(qū)根據(jù)其容量大小進(jìn)行分類，對(duì)于每一類具有相同容量的所有空閑分區(qū)，單獨(dú)設(shè)立一個(gè)空閑分區(qū)鏈表。

看書自行理解4.2.3動(dòng)態(tài)分區(qū)分配分配內(nèi)存：在系統(tǒng)利用上述的某種分配算法，從空閑分區(qū)表（鏈）中找到所需大小的空閑分區(qū)之后，應(yīng)進(jìn)行內(nèi)存的分配操作，即：

1.計(jì)算當(dāng)前空閑分區(qū)的大小m.size和實(shí)際請(qǐng)求的分區(qū)大小u.size之差

2.若m.size-u.size<=size（size是實(shí)現(xiàn)規(guī)定的不在分割的剩余分區(qū)的大小），則將整個(gè)空閑分區(qū)分配給請(qǐng)求者。

3.若m.size-u.size>size，則從該空閑分區(qū)中按請(qǐng)求的大小劃分出一塊內(nèi)存空間分配給請(qǐng)求者，并將剩余的部分仍留在空閑分區(qū)表（鏈）中。

4.將分配區(qū)的首地址返回給調(diào)用者。實(shí)際地，內(nèi)存分配的操作流程亦可描述為：4.2.3動(dòng)態(tài)分區(qū)分配回收內(nèi)存：當(dāng)進(jìn)程運(yùn)行完畢釋放內(nèi)存時(shí)，系統(tǒng)根據(jù)回收區(qū)的首地址，從空閑分區(qū)表（鏈）中找到相應(yīng)的插入點(diǎn)，將回收區(qū)插入到空閑分區(qū)表（鏈）中的適當(dāng)位置。此時(shí)，可能出現(xiàn)以下四種情況之一：

1.回收區(qū)前連空閑區(qū)

2.回收區(qū)后連空閑區(qū)

3.回收區(qū)前、后連空閑區(qū)

4.回收區(qū)前、后都不連空閑區(qū)例題：操作系統(tǒng)作業(yè)10k20k256k-110k25k作業(yè)23k35k45k作業(yè)3156k48k100k作業(yè)5作業(yè)6作業(yè)458k68k70k分區(qū)號(hào)起始地址大小125k10k245k3k3100k156k空閑分區(qū)表作業(yè)3完成、作業(yè)1完成、作業(yè)2完成、作業(yè)5完成作業(yè)3完成10k245k13k作業(yè)1完成5k120k15k作業(yè)2完成10k120k38k作業(yè)5完成2k268k2k4.2.4動(dòng)態(tài)重定位分區(qū)分配1.動(dòng)態(tài)重定位的引入思想：在動(dòng)態(tài)分區(qū)分配的基礎(chǔ)上引入“緊湊”技術(shù)（整理功能）操作系統(tǒng)作業(yè)10k20k256k-110k25k作業(yè)23k35k45k作業(yè)3156k48k100k操作系統(tǒng)作業(yè)10k20k256k-110k25k作業(yè)23k作業(yè)3156k2.動(dòng)態(tài)重定位的實(shí)現(xiàn)動(dòng)態(tài)重定位分區(qū)分配算法需與在裝入時(shí)，采用“動(dòng)態(tài)運(yùn)行時(shí)裝入”方式，才能保證程序中相對(duì)地址的正確性4.2.4動(dòng)態(tài)重定位分區(qū)分配3.動(dòng)態(tài)重定位分區(qū)分配算法4.2.4動(dòng)態(tài)重定位分區(qū)分配動(dòng)態(tài)重定位分區(qū)分配算法與動(dòng)態(tài)分區(qū)分配算法基本相同，差別僅在于：在找不到足夠大的空閑分區(qū)來滿足用戶需求時(shí)應(yīng)進(jìn)行“緊湊”。其流程可描述為：優(yōu)點(diǎn):可以消除碎片,能夠分配更多的分區(qū),有助于多道程序設(shè)計(jì),提高內(nèi)存的利用率。缺點(diǎn):緊湊花費(fèi)了大量CPU時(shí)間;4.2.5對(duì)換(Swapping)1.對(duì)換的引入（新教材P129）所謂“對(duì)換”，是指把內(nèi)存中暫時(shí)不能運(yùn)行的進(jìn)程或者暫時(shí)不用的程序和數(shù)據(jù)，調(diào)出到外存上，以便騰出足夠的內(nèi)存空間，再把已具備運(yùn)行條件的進(jìn)程或進(jìn)程所需要的程序和數(shù)據(jù)，調(diào)入內(nèi)存。對(duì)換是提高內(nèi)存利用率的有效措施。對(duì)換又分為：（1）整體對(duì)換即對(duì)換是以整個(gè)進(jìn)程為單位的，又稱進(jìn)程對(duì)換。

（2）部分對(duì)換

頁(yè)面對(duì)換：對(duì)換是以“頁(yè)”為單位進(jìn)行的。

分段對(duì)換：對(duì)換是以“段”為單位進(jìn)行的。圖

對(duì)換兩個(gè)進(jìn)程4.2.5對(duì)換(Swapping)2.對(duì)換空間的管理

為了能對(duì)對(duì)換區(qū)中的空閑盤塊進(jìn)行管理，在系統(tǒng)中應(yīng)配置相應(yīng)的數(shù)據(jù)結(jié)構(gòu)，以記錄外存的使用情況。其形式與內(nèi)存在動(dòng)態(tài)分區(qū)分配方式中所用數(shù)據(jù)結(jié)構(gòu)相似，即同樣可以用空閑分區(qū)表或空閑分區(qū)鏈。在空閑分區(qū)表中的每個(gè)表目中應(yīng)包含兩項(xiàng)，即對(duì)換區(qū)的首址及其大小，它們的單位是盤塊號(hào)和盤塊數(shù)。3.進(jìn)程的換出與換入

(1)進(jìn)程的換出。每當(dāng)一進(jìn)程由于創(chuàng)建子進(jìn)程而需要更多的內(nèi)存空間，但又無(wú)足夠的內(nèi)存空間等情況發(fā)生時(shí)，系統(tǒng)應(yīng)將某進(jìn)程換出。其過程是：系統(tǒng)首先選擇處于阻塞狀態(tài)且優(yōu)先級(jí)最低的進(jìn)程作為換出進(jìn)程，然后啟動(dòng)磁盤，將該進(jìn)程的程序和數(shù)據(jù)傳送到磁盤的對(duì)換區(qū)上。若傳送過程未出現(xiàn)錯(cuò)誤，便可回收該進(jìn)程所占用的內(nèi)存空間，并對(duì)該進(jìn)程的進(jìn)程控制塊做相應(yīng)的修改。4.2.5對(duì)換(Swapping)

(2)進(jìn)程的換入。系統(tǒng)應(yīng)定時(shí)地查看所有進(jìn)程的狀態(tài)，從中找出“就緒”狀態(tài)但已換出的進(jìn)程，將其中換出時(shí)間(換出到磁盤上)最久的進(jìn)程作為換入進(jìn)程，將之換入，直至已無(wú)可換入的進(jìn)程或無(wú)可換出的進(jìn)程為止。4.3基本分頁(yè)存儲(chǔ)管理方式為什么會(huì)引入離散分配管理？連續(xù)分配管理（單一連續(xù)、固定分區(qū)、可變分區(qū)、可重定位分區(qū)）中的每個(gè)進(jìn)程都是連續(xù)的放在內(nèi)存中、要能運(yùn)行一定要一段連續(xù)的空間。要求嚴(yán)格、浪費(fèi)空間、產(chǎn)生很多碎片。雖然有“緊湊”、但開銷大。如果允許將一個(gè)進(jìn)程直接分散地裝入到許多不相鄰的分區(qū)中，則無(wú)需再進(jìn)行“緊湊”?；谶@一思想而產(chǎn)生了離散分配管理方式，包括：

1.分頁(yè)存儲(chǔ)管理方式，此時(shí)離散分配的基本單位是頁(yè)。在分頁(yè)存儲(chǔ)管理方式中，又根據(jù)是否具備頁(yè)面對(duì)換功能，將分頁(yè)存儲(chǔ)管理方式分為：（1）基本的分頁(yè)存儲(chǔ)管理方式：要求每個(gè)作業(yè)全部裝入內(nèi)存后方能運(yùn)行。

（2）請(qǐng)求分頁(yè)存儲(chǔ)管理方式

2.分段存儲(chǔ)管理方式，此時(shí)離散分配的基本單位是段。在分段存儲(chǔ)管理方式中，又根據(jù)是否具備分段對(duì)換功能，將分段存儲(chǔ)管理方式分為：（1）基本的分段存儲(chǔ)管理方式

（2）請(qǐng)求分段存儲(chǔ)管理方式4.3基本分頁(yè)存儲(chǔ)管理方式分頁(yè)的思想：把邏輯地址空間（程序）分成若干個(gè)大小相等的片－－頁(yè)面或頁(yè)，并加以編號(hào)0頁(yè)、1頁(yè)、2頁(yè)…….把內(nèi)存也分成和頁(yè)面大小相等的若干個(gè)物理存儲(chǔ)塊－－物理塊，并加以編號(hào)0塊、1塊、2塊……為進(jìn)程分配內(nèi)存時(shí)，將進(jìn)程的若干個(gè)頁(yè)裝入多個(gè)不相鄰的塊中。當(dāng)一個(gè)用戶程序裝入內(nèi)存時(shí),以頁(yè)面為單位進(jìn)行分配。頁(yè)面的大小是為2n,通常為1KB,2KB,nKB等。由于進(jìn)程的最后一頁(yè)經(jīng)常裝不滿一頁(yè)，因而形成不可以利用的碎片，稱為“頁(yè)內(nèi)碎片”。要注意什么問題？4.3基本分頁(yè)存儲(chǔ)管理方式4.3.1頁(yè)面與頁(yè)表

1.頁(yè)面

1)頁(yè)面和物理塊分頁(yè)存儲(chǔ)管理，是將一個(gè)進(jìn)程的邏輯地址空間分成若干個(gè)大小相等的片，稱為頁(yè)面或頁(yè)，并為各頁(yè)加以編號(hào)，從0開始，如第0頁(yè)、第1頁(yè)等。相應(yīng)地，也把內(nèi)存空間分成與頁(yè)面相同大小的若干個(gè)存儲(chǔ)塊，稱為(物理)塊或頁(yè)框(frame)，也同樣為它們加以編號(hào)，如0＃塊、1＃塊等等。在為進(jìn)程分配內(nèi)存時(shí)，以塊為單位將進(jìn)程中的若干個(gè)頁(yè)分別裝入到多個(gè)可以不相鄰接的物理塊中。由于進(jìn)程的最后一頁(yè)經(jīng)常裝不滿一塊而形成了不可利用的碎片，稱之為“頁(yè)內(nèi)碎片”。

2)頁(yè)面大小在分頁(yè)系統(tǒng)中的頁(yè)面其大小應(yīng)適中。頁(yè)面若太小，一方面雖然可使內(nèi)存碎片減小，從而減少了內(nèi)存碎片的總空間，有利于提高內(nèi)存利用率，但另一方面也會(huì)使每個(gè)進(jìn)程占用較多的頁(yè)面，從而導(dǎo)致進(jìn)程的頁(yè)表過長(zhǎng)，占用大量?jī)?nèi)存；此外，還會(huì)降低頁(yè)面換進(jìn)換出的效率。然而，如果選擇的頁(yè)面較大，雖然可以減少頁(yè)表的長(zhǎng)度，提高頁(yè)面換進(jìn)換出的速度，但卻又會(huì)使頁(yè)內(nèi)碎片增大。因此，頁(yè)面的大小應(yīng)選擇得適中，且頁(yè)面大小應(yīng)是2的冪，通常為512B~8KB。4.3.1頁(yè)面與頁(yè)表2.地址結(jié)構(gòu)分頁(yè)地址中的地址結(jié)構(gòu)如下：頁(yè)號(hào)P位移量（或頁(yè)內(nèi)地址）d31121104.3.1頁(yè)面與頁(yè)表（a）若頁(yè)內(nèi)偏移d占12位，表示頁(yè)面大小為4kB（b）若頁(yè)號(hào)P占20位、表示頁(yè)面的數(shù)目為1M頁(yè)2.地址結(jié)構(gòu)4.3.1頁(yè)面與頁(yè)表例:某系統(tǒng)頁(yè)面大小為1k，已知地址為A=2170Byte（十進(jìn)制）、問頁(yè)號(hào)p是多少？頁(yè)內(nèi)地址d是多少？A=2170=第0頁(yè)（1024）＋第1頁(yè)(1024）+第2頁(yè)(頁(yè)內(nèi)122)頁(yè)號(hào)：P=2頁(yè)內(nèi)地址:d=122對(duì)某特定機(jī)器，其地址結(jié)構(gòu)是一定的。若給定一個(gè)邏輯地址空間中的地址為A，頁(yè)面的大小為L(zhǎng)，則頁(yè)號(hào)P和頁(yè)內(nèi)地址d可按下式求得：2170除以1024＝2….122 例:某系統(tǒng)頁(yè)面大小為1k，已知地址為A=4EA5h（16進(jìn)制），問頁(yè)號(hào)p是多少？頁(yè)內(nèi)地址d是多少？方法一：將A=4EA5h轉(zhuǎn)化為十進(jìn)制，利用上例中的方法求解：

A=4EA5h=2013320133/1024=19…….677方法二：由于地址系統(tǒng)是：

本題中頁(yè)面大小為1k=1024是需要10位頁(yè)內(nèi)偏移位數(shù)0頁(yè)號(hào)位數(shù)P910位將A=4EA5h轉(zhuǎn)變?yōu)槎M(jìn)制是:0100111010100101頁(yè)號(hào)：P=010011=19頁(yè)內(nèi)偏移地址：d=1010100101=6773.頁(yè)表頁(yè)表的作用是實(shí)現(xiàn)從頁(yè)號(hào)到物理塊號(hào)的地址映射。4.3.1頁(yè)面與頁(yè)表用戶程序0頁(yè)1頁(yè)2頁(yè)4k4k4k0塊1塊2塊….3塊19塊20塊….物理內(nèi)存3頁(yè)4k頁(yè)表頁(yè)號(hào)塊號(hào)0113219304.3.2地址變換機(jī)構(gòu)00頁(yè)1頁(yè)…Movax,3…102047204820492170前面的例子：某系統(tǒng)頁(yè)面大小為1k，共有3頁(yè)、分別放于內(nèi)存的1、19、3物理塊中。已知邏輯地址為A=2170Byte，問物理塊中的地址是多少？1220塊1塊2塊….3塊19塊20塊….Movax,33x1k+122=3194實(shí)際的物理地址變換機(jī)構(gòu)，見下一頁(yè)4.3.2地址變換機(jī)構(gòu)頁(yè)號(hào)塊號(hào)0111923a頁(yè)表始址頁(yè)表長(zhǎng)度頁(yè)表寄存器頁(yè)號(hào)頁(yè)內(nèi)偏址邏輯地址A=21702122a3>+越界Na+23122物理地址＝31941.基本的地址變換機(jī)構(gòu)例：在一個(gè)分頁(yè)存儲(chǔ)管理系統(tǒng)中、某個(gè)作業(yè)的頁(yè)表如下。已知頁(yè)面大小為1024字節(jié)。試將邏輯地址1011、2148、3000、4000、5012轉(zhuǎn)化為相應(yīng)的物理地址頁(yè)號(hào)塊號(hào)02132136答：1011－>30592148－>11243000－>19764000－>70725012－>越界非法2.具有快表的地址變換機(jī)構(gòu)4.3.2地址變換機(jī)構(gòu)在基本的地址變換機(jī)構(gòu)中，頁(yè)表是放在內(nèi)存中的。此時(shí)，CPU存取一個(gè)數(shù)據(jù)，需要訪問內(nèi)存2次。

第1次，訪問內(nèi)存中的頁(yè)表，找出邏輯地址對(duì)應(yīng)的物理地址；第2次，訪問內(nèi)存物理地址處的數(shù)據(jù)。為了提高地址變換速度，可在地址變換機(jī)構(gòu)中增設(shè)一個(gè)具有并行查詢能力的特殊高速緩沖寄存器，又稱“快表”，用以存放當(dāng)前訪問的那些頁(yè)表項(xiàng)。此時(shí)的變換過程可描述為：頁(yè)號(hào)塊號(hào)0111923a頁(yè)表始址頁(yè)表長(zhǎng)度頁(yè)表寄存器頁(yè)號(hào)頁(yè)內(nèi)偏址邏輯地址A=21702122a3>+越界Na+23122物理地址＝3194頁(yè)號(hào)塊號(hào)頁(yè)表快表2.具有快表的地址變換機(jī)構(gòu)4.3.2地址變換機(jī)構(gòu)2.具有快表的地址變換機(jī)構(gòu)4.3.2地址變換機(jī)構(gòu)例：某頁(yè)式系統(tǒng)，頁(yè)表存在內(nèi)存中（1）如果對(duì)主存一次存取要1.5微秒、存取一個(gè)數(shù)據(jù)需要多少時(shí)間（2）如果系統(tǒng)有快表，平均命中率為85%，對(duì)快表的查找時(shí)間忽略為0，問此時(shí)存取一個(gè)數(shù)據(jù)要多少時(shí)間？答（1）2次訪問內(nèi)存2x1.5=3微秒（2）85%命中，只要訪問一次內(nèi)存，直接取得數(shù)據(jù)0.85x1.515％不能命中，要先訪問內(nèi)存快表得物理地址、在訪問內(nèi)存數(shù)據(jù)，共訪問2次3微秒。0.15x3

需要時(shí)間：0.85x1.5+0.15x3=1.725微秒4.3.3兩級(jí)和多級(jí)頁(yè)表現(xiàn)代的大多數(shù)計(jì)算機(jī)系統(tǒng)，都支持非常大的邏輯地址空間(232~264)。在這樣的環(huán)境下，頁(yè)表就變得非常大，要占用相當(dāng)大的內(nèi)存空間。在某些情況下，是不現(xiàn)實(shí)的?？梢圆捎眠@樣兩個(gè)方法來解決這一問題：①采用離散分配方式來解決難以找到一塊連續(xù)的大內(nèi)存空間的問題；②只將當(dāng)前需要的部分頁(yè)表項(xiàng)調(diào)入內(nèi)存，其余的頁(yè)表項(xiàng)仍駐留在磁盤上，需要時(shí)再調(diào)入。1.兩級(jí)頁(yè)表(Two-LevelPageTable)邏輯地址結(jié)構(gòu)可描述如下：圖4-14兩級(jí)頁(yè)表結(jié)構(gòu)圖4-15具有兩級(jí)頁(yè)表的地址變換機(jī)構(gòu)

2.多級(jí)頁(yè)表對(duì)于32位的機(jī)器，采用兩級(jí)頁(yè)表結(jié)構(gòu)是合適的；但對(duì)于64位的機(jī)器，如果頁(yè)面大小仍采用4KB即212B，那么還剩下52位，假定仍按物理塊的大小(212位)來劃分頁(yè)表，則將余下的42位用于外層頁(yè)號(hào)。此時(shí)在外層頁(yè)表中可能有4096G個(gè)頁(yè)表項(xiàng)，要占用16384GB的連續(xù)內(nèi)存空間。必須采用多級(jí)頁(yè)表，將外層頁(yè)表再進(jìn)行分頁(yè)，也是將各分頁(yè)離散地裝入到不相鄰接的物理塊中，再利用第2級(jí)的外層頁(yè)表來映射它們之間的關(guān)系。對(duì)于64位的計(jì)算機(jī)，如果要求它能支持2６４(=1844744TB)規(guī)模的物理存儲(chǔ)空間，則即使是采用三級(jí)頁(yè)表結(jié)構(gòu)也是難以辦到的；而在當(dāng)前的實(shí)際應(yīng)用中也無(wú)此必要。4.4基本分段存儲(chǔ)管理方式4.4.1分段存儲(chǔ)管理方式的引入引入分段存儲(chǔ)管理方式，主要是為了滿足用戶和程序員的下述一系列需要（新教材P135）：

1)方便編程

2)信息共享

3)信息保護(hù)

4)動(dòng)態(tài)增長(zhǎng)

5)動(dòng)態(tài)鏈接4.4.2分段系統(tǒng)的基本原理1.分段分段地址中的地址具有如下結(jié)構(gòu)：段號(hào)段內(nèi)地址3116150圖4-16利用段表實(shí)現(xiàn)地址映射2.段表圖4-17分段系統(tǒng)的地址變換過程3.地址變換機(jī)構(gòu)4.分頁(yè)和分段的主要區(qū)別

(1)頁(yè)是信息的物理單位，分頁(yè)是為實(shí)現(xiàn)離散分配方式，以消減內(nèi)存的外零頭，提高內(nèi)存的利用率?；蛘哒f，分頁(yè)僅僅是由于系統(tǒng)管理的需要而不是用戶的需要。段則是信息的邏輯單位，它含有一組其意義相對(duì)完整的信息。分段的目的是為了能更好地滿足用戶的需要。

(2)頁(yè)的大小固定且由系統(tǒng)決定，由系統(tǒng)把邏輯地址劃分為頁(yè)號(hào)和頁(yè)內(nèi)地址兩部分，是由機(jī)器硬件實(shí)現(xiàn)的，因而在系統(tǒng)中只能有一種大小的頁(yè)面；而段的長(zhǎng)度卻不固定，決定于用戶所編寫的程序，通常由編譯程序在對(duì)源程序進(jìn)行編譯時(shí)，根據(jù)信息的性質(zhì)來劃分。

(3)分頁(yè)的作業(yè)地址空間是一維的，即單一的線性地址空間，程序員只需利用一個(gè)記憶符，即可表示一個(gè)地址；而分段的作業(yè)地址空間則是二維的，程序員在標(biāo)識(shí)一個(gè)地址時(shí)，既需給出段名，又需給出段內(nèi)地址。4.4.3信息共享(新教材P139)圖4-18分頁(yè)系統(tǒng)中共享editor的示意圖圖4-19分段系統(tǒng)中共享editor的示意圖4.4.4段頁(yè)式存儲(chǔ)管理方式1.基本原理圖4-20作業(yè)地址空間和地址結(jié)構(gòu)圖4-21利用段表和頁(yè)表實(shí)現(xiàn)地址映射2.地址變換過程圖4-22段頁(yè)式系統(tǒng)中的地址變換機(jī)構(gòu)4.5虛擬存儲(chǔ)器的基本概念4.5.1虛擬存儲(chǔ)器的引入1.常規(guī)存儲(chǔ)器管理方式的特征（新教材P142）一次性，即作業(yè)在運(yùn)行前需一次性全部裝入內(nèi)存。(2)駐留性，即作業(yè)裝入內(nèi)存后，便一直駐留在內(nèi)存中，直至作業(yè)運(yùn)行結(jié)束。思考這樣兩種情形：(1)有的作業(yè)很大甚至超過了內(nèi)存總?cè)萘浚?2)有大量的作業(yè)要求運(yùn)行，但內(nèi)存容量不足以容納所有這些作業(yè)。2.局部性原理早在1968年，

Denning.P就曾指出：

(1)程序執(zhí)行時(shí)，除了少部分的轉(zhuǎn)移和過程調(diào)用指令外，在大多數(shù)情況下仍是順序執(zhí)行的。

(2)過程調(diào)用將會(huì)使程序的執(zhí)行軌跡由一部分區(qū)域轉(zhuǎn)至另一部分區(qū)域，但經(jīng)研究看出，過程調(diào)用的深度在大多數(shù)情況下都不超過5。

(3)程序中存在許多循環(huán)結(jié)構(gòu)，這些雖然只由少數(shù)指令構(gòu)成，但是它們將多次執(zhí)行。

(4)程序中還包括許多對(duì)數(shù)據(jù)結(jié)構(gòu)的處理，如對(duì)數(shù)組進(jìn)行操作，它們往往都局限于很小的范圍內(nèi)。局限性又表現(xiàn)在下述兩個(gè)方面：

(1)時(shí)間局限性。如果程序中的某條指令一旦執(zhí)行，則不久以后該指令可能再次執(zhí)行；如果某數(shù)據(jù)被訪問過，則不久以后該數(shù)據(jù)可能再次被訪問。產(chǎn)生時(shí)間局限性的典型原因，是由于在程序中存在著大量的循環(huán)操作。

(2)空間局限性。一旦程序訪問了某個(gè)存儲(chǔ)單元，在不久之后，其附近的存儲(chǔ)單元也將被訪問，即程序在一段時(shí)間內(nèi)所訪問的地址，可能集中在一定的范圍之內(nèi)，其典型情況便是程序的順序執(zhí)行。3.虛擬存儲(chǔ)器定義正是由于程序在執(zhí)行時(shí)具有局部性規(guī)律，因此應(yīng)用程序在執(zhí)行之前，沒有必要全部一次性裝入內(nèi)存，僅須將那些當(dāng)前要運(yùn)行的少數(shù)頁(yè)面或段先裝入內(nèi)存便可運(yùn)行，其余部分留在磁盤上。程序在運(yùn)行時(shí)，如果它所要訪問的頁(yè)(段)已調(diào)入內(nèi)存，便可繼續(xù)執(zhí)行下去；如果尚未調(diào)入內(nèi)存(缺頁(yè)或缺段)，此時(shí)程序應(yīng)利用OS提供的請(qǐng)求調(diào)頁(yè)(段)功能，將它們調(diào)入內(nèi)存，以使程序能繼續(xù)執(zhí)行下去；如果此時(shí)內(nèi)存已滿，無(wú)法再裝入新的頁(yè)(段)，則還需利用頁(yè)(段)的置換功能，將內(nèi)存中暫時(shí)不用的頁(yè)(段)調(diào)至磁盤上，騰出足夠的內(nèi)存空間后，再將要訪問的頁(yè)(段)調(diào)入內(nèi)存，使程序繼續(xù)執(zhí)行下去。3.虛擬存儲(chǔ)器定義所謂虛擬存儲(chǔ)器，是指具有請(qǐng)求調(diào)入功能和置換功能，能從邏輯上對(duì)內(nèi)存容量加以擴(kuò)充的一種存儲(chǔ)器系統(tǒng)。其邏輯容量由內(nèi)存容量和外存容量之和所決定，其運(yùn)行速度接近于內(nèi)存速度，而每位的成本卻又接近于外存。可見，虛擬存儲(chǔ)技術(shù)是一種性能非常優(yōu)越的存儲(chǔ)器管理技術(shù)，故被廣泛地應(yīng)用于大、中、小型機(jī)器和微型機(jī)中。

4.5.2虛擬存儲(chǔ)器的實(shí)現(xiàn)方法1.分頁(yè)請(qǐng)求系統(tǒng)硬件支持。①請(qǐng)求分頁(yè)的頁(yè)表機(jī)制，它是在純分頁(yè)的頁(yè)表機(jī)制上增加若干項(xiàng)而形成的，作為請(qǐng)求分頁(yè)的數(shù)據(jù)結(jié)構(gòu)；②缺頁(yè)中斷機(jī)構(gòu)，即每當(dāng)用戶程序要訪問的頁(yè)面尚未調(diào)入內(nèi)存時(shí)便產(chǎn)生一缺頁(yè)中斷，以請(qǐng)求OS將所缺的頁(yè)調(diào)入內(nèi)存；③地址變換機(jī)構(gòu)，它同樣是在純分頁(yè)地址變換機(jī)構(gòu)的基礎(chǔ)上發(fā)展形成的。(2)實(shí)現(xiàn)請(qǐng)求分頁(yè)的軟件。包括用于實(shí)現(xiàn)請(qǐng)求調(diào)頁(yè)的軟件和實(shí)現(xiàn)頁(yè)面置換的軟件。4.5.2虛擬存儲(chǔ)器的實(shí)現(xiàn)方法2.分段請(qǐng)求系統(tǒng)硬件支持。①請(qǐng)求分段的段表機(jī)制；②缺段中斷機(jī)構(gòu)；③地址變換機(jī)構(gòu)。(2)實(shí)現(xiàn)請(qǐng)求分段的軟件。4.5.3虛擬存儲(chǔ)器管理方式的特征(新教材P144)多次性即一個(gè)作業(yè)被分成多次調(diào)入內(nèi)存運(yùn)行。對(duì)換性即允許在作業(yè)的運(yùn)行過程中進(jìn)行換進(jìn)換出。虛擬性即能夠從邏輯上擴(kuò)充內(nèi)存容量，使用戶所看到的內(nèi)存容量遠(yuǎn)大于實(shí)際內(nèi)存容量。這是虛擬存儲(chǔ)器所表現(xiàn)出來的最重要的特征，也是實(shí)現(xiàn)虛擬存儲(chǔ)器的最重要的目標(biāo)。4.6請(qǐng)求分頁(yè)存儲(chǔ)管理方式4.6.1請(qǐng)求分頁(yè)中的硬件支持1.頁(yè)表機(jī)制頁(yè)號(hào)物理塊號(hào)狀態(tài)位P訪問字段A修改位M外存地址用于指示該頁(yè)是否已經(jīng)調(diào)入內(nèi)存用于記錄該頁(yè)在一段時(shí)間內(nèi)被訪問的次數(shù)，或者記錄該頁(yè)最近已有多長(zhǎng)時(shí)間未被訪問表示該頁(yè)在調(diào)入內(nèi)存后是否被修改過，若已被修改，則在置換該頁(yè)是，必須將該頁(yè)重寫到外存上。用于指出該頁(yè)在外存上的地址2.缺頁(yè)中斷機(jī)構(gòu)圖4-23涉及6次缺頁(yè)中斷的指令與一般中斷相比，缺頁(yè)中斷有著明顯的不同，主要表現(xiàn)在以下兩個(gè)方面：(1)通常，CPU是在一條指令執(zhí)行完后，才檢查是否有中斷請(qǐng)求到達(dá)。若有，便去響應(yīng)；否則，繼續(xù)執(zhí)行下一條指令。然而，缺頁(yè)中斷則是在指令執(zhí)行期間，發(fā)現(xiàn)所要訪問的指令或數(shù)據(jù)不在內(nèi)存時(shí)所產(chǎn)生和處理的。(2)一條指令在執(zhí)行期間，可能產(chǎn)生多次缺頁(yè)中斷。如右圖所示。3.地址變換機(jī)構(gòu)圖4-24請(qǐng)求分頁(yè)中的地址變換過程4.6.2內(nèi)存分配策略和分配算法在為進(jìn)程分配內(nèi)存時(shí)，將涉及到三個(gè)問題：最小物理塊數(shù)問題物理塊的分配策略物理塊分配算法4.6.2內(nèi)存分配策略和分配算法1.最小物理塊數(shù)的確定這里所說的最小物理塊數(shù)，是指能保證進(jìn)程正常運(yùn)行所需的最小物理塊數(shù)。當(dāng)系統(tǒng)為進(jìn)程分配的物理塊數(shù)少于此值時(shí)，進(jìn)程將無(wú)法運(yùn)行。進(jìn)程應(yīng)獲得的最少物理塊數(shù)與計(jì)算機(jī)的硬件結(jié)構(gòu)有關(guān)，取決于指令的格式、功能和尋址方式。2.物理塊的分配策略在請(qǐng)求分頁(yè)系統(tǒng)中，可采取兩種內(nèi)存分配策略，即固定和可變分配策略。在進(jìn)行置換時(shí)，也可采取兩種策略，即全局置換和局部置換。于是可組合出以下三種適用的策略。

先為每個(gè)進(jìn)程分配一定數(shù)目的物理塊，而OS自身也保持一個(gè)空閑物理塊隊(duì)列。當(dāng)某進(jìn)程發(fā)現(xiàn)缺頁(yè)時(shí)，由系統(tǒng)從物理空閑塊中取出一個(gè)物理塊分配給該進(jìn)程，并將欲調(diào)入的頁(yè)裝入其中。僅當(dāng)空閑物理塊隊(duì)列中的物理塊用完時(shí)，OS才從內(nèi)存中選擇一頁(yè)調(diào)出，該頁(yè)可能是系統(tǒng)中任意進(jìn)程的某一頁(yè)。為每個(gè)進(jìn)程分配一定數(shù)目的物理塊，且在整個(gè)運(yùn)行期間都不再改變。若進(jìn)程在運(yùn)行中發(fā)現(xiàn)缺頁(yè)，則只能從該進(jìn)程在內(nèi)存中的n個(gè)頁(yè)面中選出一頁(yè)換出，然后再調(diào)入一頁(yè)，從而保證該進(jìn)程在所占內(nèi)存空間不變。為每個(gè)進(jìn)程分配一定數(shù)目的物理塊，但當(dāng)發(fā)現(xiàn)某進(jìn)程缺頁(yè)時(shí)，只允許從該進(jìn)程在內(nèi)存的n個(gè)頁(yè)面中選出一頁(yè)換出。但如果該進(jìn)程在運(yùn)行中頻繁地發(fā)生缺頁(yè)中斷，則系統(tǒng)須再為該進(jìn)程分配若干附加的物理塊，直至該進(jìn)程的缺頁(yè)率減少到適當(dāng)程度為止；反之，若某進(jìn)程在運(yùn)行過程中的缺頁(yè)率特別低，則可適當(dāng)就減少分配給它的物理塊數(shù)。1)固定分配局部置換：2)可變分配全局置換：3)可變分配局部置換：3.物理塊分配算法在采用固定分配策略時(shí)，如何將系統(tǒng)中可供分配的所有物理塊分配給各個(gè)進(jìn)程，可采用以下幾種算法：

1)平均分配算法這是將系統(tǒng)中所有可供分配的物理塊，平均分配給各個(gè)進(jìn)程。例如，當(dāng)系統(tǒng)中有100個(gè)物理塊，有5個(gè)進(jìn)程在運(yùn)行時(shí)，每個(gè)進(jìn)程可分得20個(gè)物理塊。這種方式貌似公平，但實(shí)際上是不公平的，因?yàn)樗纯紤]到各進(jìn)程本身的大小。如有一個(gè)進(jìn)程其大小為200頁(yè)，只分配給它20個(gè)塊，這樣，它必然會(huì)有很高的缺頁(yè)率；而另一個(gè)進(jìn)程只有10頁(yè)，卻有10個(gè)物理塊閑置未用。

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，將有：bi應(yīng)該取整，它必須大于最小物理塊數(shù)。

3)考慮優(yōu)先權(quán)的分配算法在實(shí)際應(yīng)用中，為了照顧到重要的、緊迫的作業(yè)能盡快地完成，應(yīng)為它分配較多的內(nèi)存空間。通常采取的方法是把內(nèi)存中可供分配的所有物理塊分成兩部分：一部分按比例地分配給各進(jìn)程；另一部分則根據(jù)各進(jìn)程的優(yōu)先權(quán)，適當(dāng)?shù)卦黾悠湎鄳?yīng)份額后，分配給各進(jìn)程。在有的系統(tǒng)中，如重要的實(shí)時(shí)控制系統(tǒng)，則可能是完全按優(yōu)先權(quán)來為各進(jìn)程分配其物理塊的。頁(yè)面調(diào)入策略涉及到三個(gè)問題：調(diào)入頁(yè)面的時(shí)機(jī)從何處調(diào)入頁(yè)面頁(yè)面調(diào)入的過程4.6.3調(diào)頁(yè)策略4.6.3調(diào)頁(yè)策略1.何時(shí)調(diào)入頁(yè)面預(yù)調(diào)頁(yè)策略即將那些預(yù)計(jì)在不久之后便會(huì)訪問的頁(yè)面預(yù)先調(diào)入內(nèi)存。但遺憾的是，目前預(yù)調(diào)頁(yè)的成功率較低，僅約50%。2)請(qǐng)求調(diào)頁(yè)策略根據(jù)請(qǐng)求調(diào)入頁(yè)面，此時(shí)調(diào)入的頁(yè)面肯定是會(huì)被訪問的，但這種策略每次僅調(diào)入一頁(yè)，故系統(tǒng)開銷相對(duì)較大。2.從何處調(diào)入頁(yè)面在請(qǐng)求分頁(yè)系統(tǒng)中的外存分為兩部分：用于存放文件的文件區(qū)和用于存放對(duì)換頁(yè)面的對(duì)換區(qū)。通常，由于對(duì)換區(qū)是采用連續(xù)分配方式，而文件是采用離散分配方式，故對(duì)換區(qū)的磁盤I/O速度比文件區(qū)的高。這樣，每當(dāng)發(fā)生缺頁(yè)請(qǐng)求時(shí)，系統(tǒng)應(yīng)從何處將缺頁(yè)調(diào)入內(nèi)存，可分成如下三種情況：(1)若系統(tǒng)擁有足夠的對(duì)換區(qū)空間，能使得在進(jìn)程運(yùn)行前，保證與該進(jìn)程有關(guān)的文件，都已從文件區(qū)拷貝到對(duì)換區(qū)。這時(shí)，若發(fā)生缺頁(yè)中斷，則可全部從對(duì)換區(qū)調(diào)入所需頁(yè)面。(2)系統(tǒng)缺少足夠的對(duì)換區(qū)空間，即運(yùn)行中的進(jìn)程僅是部分頁(yè)面拷貝到了對(duì)換區(qū)。這時(shí)，若發(fā)生缺頁(yè)中斷，則分以下兩種情形：凡是不會(huì)被修改的頁(yè)面，都直接從文件區(qū)調(diào)入；而當(dāng)換出這些頁(yè)面時(shí)，由于它們未被修改而不必再將它們換出（直接覆蓋就行），以后再調(diào)入時(shí)，仍從文件區(qū)直接調(diào)入。對(duì)于那些可能被修改的頁(yè)面，若已經(jīng)拷貝到對(duì)換區(qū)，則從對(duì)換區(qū)調(diào)入，否則從文件區(qū)調(diào)入。但在將它們換出時(shí)，便須調(diào)出到對(duì)換區(qū)，以后需要時(shí)，再?gòu)膶?duì)換區(qū)調(diào)入。(3)UNIX方式。此時(shí)，與進(jìn)程有關(guān)的頁(yè)面都放在文件區(qū)，故凡是未運(yùn)行過的頁(yè)面，都應(yīng)從文件區(qū)調(diào)入。而對(duì)于曾經(jīng)運(yùn)行過但又被換出的頁(yè)面，由于是被放在對(duì)換區(qū)，因此在下次調(diào)入時(shí)，應(yīng)從對(duì)換區(qū)調(diào)入。3.頁(yè)面調(diào)入過程每當(dāng)程序所要訪問的頁(yè)面未在內(nèi)存時(shí)，便向CPU發(fā)出一缺頁(yè)中斷：(1)中斷處理程序首先保留CPU環(huán)境，分析中斷原因后，轉(zhuǎn)入缺頁(yè)中斷處理程序。(2)該程序通過查找頁(yè)表，得到該頁(yè)在外存的物理塊后，

(a)如果此時(shí)內(nèi)存能容納新頁(yè)，則啟動(dòng)磁盤I/O將所缺之頁(yè)調(diào)入內(nèi)存，然后修改頁(yè)表。

(b)如果內(nèi)存已滿，則須先按照某種置換算法從內(nèi)存中選出一頁(yè)準(zhǔn)備換出。如果該頁(yè)未被修改過，可不必將該頁(yè)寫回磁盤；如果此頁(yè)已被修改，則必須將它寫回磁盤，然后再把所缺的頁(yè)調(diào)入內(nèi)存，并修改頁(yè)表中的相應(yīng)表項(xiàng)，置其存在位為“1”，并將此頁(yè)表項(xiàng)寫入快表中。(3)在缺頁(yè)調(diào)入內(nèi)存后，利用修改后的頁(yè)表，去形成所要訪問數(shù)據(jù)的物理地址，再去訪問內(nèi)存數(shù)據(jù)。4.8頁(yè)面置換算法4.8.1最佳置換算法和先進(jìn)先出置換算法

1.最佳(Optimal)置換算法最佳置換算法是由Belady于1966年提出的一種理論上的算法。其所選擇的被淘汰頁(yè)面，將是以后永不使用的，或許是在最長(zhǎng)(未來)時(shí)間內(nèi)不再被訪問的頁(yè)面。采用最佳置換算法，通常可保證獲得最低的缺頁(yè)率。假定系統(tǒng)為某進(jìn)程分配了三個(gè)物理塊，并考慮有以下的頁(yè)面號(hào)引用順序：7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1

進(jìn)程運(yùn)行時(shí)，先將7，0，1三個(gè)頁(yè)面裝入內(nèi)存。以后，當(dāng)進(jìn)程要訪問頁(yè)面2時(shí)，將會(huì)產(chǎn)生缺頁(yè)中斷。此時(shí)OS根據(jù)最佳置換算法，將選擇頁(yè)面7予以淘汰。圖4-25利用最佳頁(yè)面置換算法時(shí)的置換圖引用順序70770170122010320304243230321201201770101頁(yè)框(物理塊）2032.先進(jìn)先出(FIFO)頁(yè)面置換算法圖4-26利用FIFO置換算法時(shí)的置換圖引用順序70770170122010323104430230321013201770201頁(yè)框23042042302301271270114.8.2最近最久未使用(LRU)置換算法1.LRU(LeastRecentlyUsed)置換算法的描述圖4-27LRU頁(yè)面置換算法引用順序70770170122010320304403230321132201710701頁(yè)框4024320321022.LRU置換算法的硬件支持

LRU置換算法雖然是一種比較好的算法，但要求系統(tǒng)有較多的支持硬件。為了了解一個(gè)進(jìn)程在內(nèi)存中各個(gè)頁(yè)面各有多少時(shí)間未被進(jìn)程訪問，以及如何快速地知道哪一頁(yè)是最近最久未使用的頁(yè)面，須有兩類硬件之一的支持：寄存器或棧。2.LRU置換算法的硬件支持

1)寄存器為了記錄某進(jìn)程在內(nèi)存中各頁(yè)的使用情況，須為每個(gè)在內(nèi)存中的頁(yè)面配置一個(gè)移位寄存器，可表示為R=Rn-1Rn-2Rn-3…R2R1R0

當(dāng)某頁(yè)面首次進(jìn)入內(nèi)存時(shí)，相應(yīng)寄存器的各位置為1。此時(shí)，定時(shí)信號(hào)將每隔一定時(shí)間將寄存器右移一位。注意，當(dāng)進(jìn)程訪問該頁(yè)面時(shí)，則將相應(yīng)寄存器的Rn-1位置為1。那么具有最小數(shù)值的寄存器所對(duì)應(yīng)的頁(yè)面，就是最近最久未使用的頁(yè)面。圖4-28某進(jìn)程具有8個(gè)頁(yè)面時(shí)的LRU訪問情況2)棧也可利用一個(gè)特殊的棧來保存當(dāng)前使用的各個(gè)頁(yè)面的頁(yè)面號(hào)。每當(dāng)進(jìn)程訪問某頁(yè)面時(shí)，便將該頁(yè)面的頁(yè)面號(hào)從棧中移出，將它壓入棧頂。因此，棧頂始終是最新被訪問頁(yè)面的頁(yè)面號(hào)，而棧底則是最近最久未是頁(yè)面的頁(yè)面號(hào)。圖4-29用棧保存當(dāng)前使用頁(yè)面時(shí)棧的變化情況44747074070471704101740107