操作系統(tǒng)-第4章存儲(chǔ)器管理

第四章存儲(chǔ)器管理4.1存儲(chǔ)器的層次結(jié)構(gòu)4.2程序的裝入和鏈接4.3連續(xù)分配存儲(chǔ)管理方式4.4對(duì)換4.5分頁(yè)存儲(chǔ)管理方式4.6分段存儲(chǔ)管理方式4.1程序的裝入和鏈接圖4-1對(duì)用戶程序的處理步驟絕對(duì)地址（邏輯地址）和物理地址4.1.1程序的裝入1.絕對(duì)裝入方式(AbsoluteLoadingMode)

程序中所使用的絕對(duì)地址，既可在編譯或匯編時(shí)給出，也可由程序員直接賦予。但在由程序員直接給出絕對(duì)地址時(shí)，不僅要求程序員熟悉內(nèi)存的使用情況，而且一旦程序或數(shù)據(jù)被修改后，可能要改變程序中的所有地址。因此，通常是寧可在程序中采用符號(hào)地址，然后在編譯或匯編時(shí)，再將這些符號(hào)地址轉(zhuǎn)換為絕對(duì)地址。2.可重定位裝入方式(RelocationLoadingMode)圖4-2作業(yè)裝入內(nèi)存時(shí)的情況3.動(dòng)態(tài)運(yùn)行時(shí)裝入方式(DenamleRun-timeLoading)

動(dòng)態(tài)運(yùn)行時(shí)的裝入程序，在把裝入模塊裝入內(nèi)存后，并不立即把裝入模塊中的相對(duì)地址轉(zhuǎn)換為絕對(duì)地址，而是把這種地址轉(zhuǎn)換推遲到程序真正要執(zhí)行時(shí)才進(jìn)行。因此，裝入內(nèi)存后的所有地址都仍是相對(duì)地址。4.1.2程序的鏈接1.靜態(tài)鏈接方式(StaticLinking)

在將這幾個(gè)目標(biāo)模塊裝配成一個(gè)裝入模塊時(shí)，須解決以下兩個(gè)問(wèn)題：

(1)對(duì)相對(duì)地址進(jìn)行修改。

(2)變換外部調(diào)用符號(hào)。圖4-3程序鏈接示意圖目標(biāo)模塊裝入模塊圖4-3程序鏈接示意圖2.裝入時(shí)動(dòng)態(tài)鏈接(LoadtimeDynamicLinking)裝入時(shí)動(dòng)態(tài)鏈接方式有以下優(yōu)點(diǎn)：便于修改和更新。(2)便于實(shí)現(xiàn)對(duì)目標(biāo)模塊的共享。3.運(yùn)行時(shí)動(dòng)態(tài)鏈接(Run-timeDynamicLinking)

近幾年流行起來(lái)的運(yùn)行時(shí)動(dòng)態(tài)鏈接方式，是對(duì)上述在裝入時(shí)鏈接方式的一種改進(jìn)。這種鏈接方式是將對(duì)某些模塊的鏈接推遲到執(zhí)行時(shí)才執(zhí)行，亦即，在執(zhí)行過(guò)程中，當(dāng)發(fā)現(xiàn)一個(gè)被調(diào)用模塊尚未裝入內(nèi)存時(shí)，立即由OS去找到該模塊并將之裝入內(nèi)存，把它鏈接到調(diào)用者模塊上。凡在執(zhí)行過(guò)程中未被用到的目標(biāo)模塊，都不會(huì)被調(diào)入內(nèi)存和被鏈接到裝入模塊上，這樣不僅可加快程序的裝入過(guò)程，而且可節(jié)省大量的內(nèi)存空間。4.2連續(xù)分配方式4.2.1單一連續(xù)分配

這是最簡(jiǎn)單的一種存儲(chǔ)管理方式，但只能用于單用戶、單任務(wù)的操作系統(tǒng)中。采用這種存儲(chǔ)管理方式時(shí)，可把內(nèi)存分為系統(tǒng)區(qū)和用戶區(qū)兩部分，系統(tǒng)區(qū)僅提供給OS使用，通常是放在內(nèi)存的低址部分；用戶區(qū)是指除系統(tǒng)區(qū)以外的全部?jī)?nèi)存空間，提供給用戶使用。4.2.2固定分區(qū)分配1.劃分分區(qū)的方法分區(qū)大小相等，即使所有的內(nèi)存分區(qū)大小相等。(2)分區(qū)大小不等。2.內(nèi)存分配圖4-4固定分區(qū)使用表1.分區(qū)分配中的數(shù)據(jù)結(jié)構(gòu)空閑分區(qū)表。

(2)空閑分區(qū)鏈。圖4-5空閑鏈結(jié)構(gòu)4.2.3動(dòng)態(tài)分區(qū)分配2.分區(qū)分配算法首次適應(yīng)算法FF。(2)循環(huán)首次適應(yīng)算法，該算法是由首次適應(yīng)算法演變而成的。(3)最佳適應(yīng)算法。3.分區(qū)分配操作1)分配內(nèi)存圖4-6內(nèi)存分配流程2)回收內(nèi)存圖4-7內(nèi)存回收時(shí)的情況8k16k64k124k221、首次適應(yīng)算法首次適應(yīng)算法的表是按空閑區(qū)首址升序的（即空閑區(qū)表是按空閑區(qū)首址從小到大）方法組織的。

4.3.4基于順序搜索的動(dòng)態(tài)分區(qū)分配算法23一、首次適應(yīng)算法分配時(shí)從表首開(kāi)始，以請(qǐng)求內(nèi)存區(qū)的大小逐個(gè)與空閑區(qū)進(jìn)行比較，找到第一個(gè)滿足要求的空閑后，若空閑區(qū)大小與請(qǐng)求區(qū)的大小相等，則將該空閑區(qū)分配給請(qǐng)求者，并撤消該空閑區(qū)所在表目；若大于請(qǐng)求區(qū)，就將該空閑區(qū)的一部分分配給請(qǐng)求者，然后，修改空閑區(qū)的大小和首址。24一、首次適應(yīng)算法

切割空閑區(qū)有兩種方法：

·

從空閑區(qū)頭開(kāi)始

·

從空閑區(qū)尾開(kāi)始空閑區(qū)大小50KB，首址156KB，申請(qǐng)34KB。25一、首次適應(yīng)算法

這種算法的實(shí)質(zhì)是盡可能地利用低地址部分的空閑區(qū)，而盡量地保證高地址部分的大空閑區(qū)，使其不被切削成小的區(qū)，其目的是保證在以有有大的作業(yè)的到來(lái)有足夠大的空閑區(qū)來(lái)滿足請(qǐng)求者。回收時(shí)，首先考察釋放區(qū)是否與系統(tǒng)中的某個(gè)空閑區(qū)相鄰，若相鄰則合并成一個(gè)空閑區(qū)，否則，將釋放區(qū)作為一個(gè)空閑區(qū)按首址升序的規(guī)則插入到空閑區(qū)表適當(dāng)?shù)奈恢谩?6最佳適應(yīng)算法是將申請(qǐng)者放入與其大小最接近的空閑區(qū)中。切割后的空閑區(qū)最小，若系統(tǒng)中有與申請(qǐng)區(qū)大小相等的空閑區(qū)，這種算法肯定能將這種空閑區(qū)分配給申請(qǐng)者。（首次適應(yīng)法則不一定）。二、最佳適應(yīng)算法27二、最佳適應(yīng)算法最佳適應(yīng)算法的空閑區(qū)表按空閑區(qū)大小升序方法組織。分配時(shí)，按申請(qǐng)的大小逐個(gè)與空閑區(qū)大小進(jìn)行比較，找到一個(gè)滿足要求的空閑區(qū)，就說(shuō)明它是最適合的（即最佳的）。這種算法最大的缺點(diǎn)是分割后的空閑區(qū)將會(huì)很小，直至無(wú)法使用，而造成浪費(fèi)。28三、最壞適應(yīng)算法為了克服最佳適應(yīng)算法把空閑區(qū)切割得大小的缺點(diǎn)，人們提出了一種最壞適應(yīng)算法，即每次分配時(shí)，總是將最大的空閑區(qū)切去一部分分配給請(qǐng)求者，其依據(jù)是當(dāng)一個(gè)很大的空閑區(qū)被切割了一部分后可能仍是一個(gè)較大的空閑區(qū)。避免了空閑區(qū)越分越小的問(wèn)題。29三、最壞適應(yīng)算法最壞適應(yīng)算法的空閑區(qū)表是按空閑區(qū)大小降序的方法組織的（從大到小的順序）。分配時(shí)總是取表中的第一個(gè)表目，若不能滿足申請(qǐng)者的要求，則表示系統(tǒng)中無(wú)滿足要求的空閑區(qū)，分配失敗；否則，將從該空閑區(qū)中分配給申請(qǐng)者，然后修改空閑區(qū)的大小，并將它插入到空閑區(qū)表的適當(dāng)位置。30

這三種放置算法的優(yōu)劣很難區(qū)分，要具體情況具體分析。例如：某時(shí)刻系統(tǒng)中有三個(gè)空閑區(qū)其大小和首址為：(35KB，100KB)、(12KB，156KB)、(28KB，200KB)有一作業(yè)系列：(JOB1，12KB)、(JOB2，30KB)、(JOB3，28KB)314.3.6可重定位分區(qū)分配1.動(dòng)態(tài)重定位的引入圖4-8緊湊的示意2.動(dòng)態(tài)重定位的實(shí)現(xiàn)圖4-9動(dòng)態(tài)重定位示意圖3.動(dòng)態(tài)重定位分區(qū)分配算法圖4-10動(dòng)態(tài)分區(qū)分配算法流程圖4.4對(duì)換(Swapping)1.對(duì)換的引入

所謂“對(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)存利用率的有效措施。2.對(duì)換空間的管理

為了能對(duì)對(duì)換區(qū)中的空閑盤(pán)塊進(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ū)的首址及其大小，它們的單位是盤(pán)塊號(hào)和盤(pán)塊數(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)程換出。其過(guò)程是：系統(tǒng)首先選擇處于阻塞狀態(tài)且優(yōu)先級(jí)最低的進(jìn)程作為換出進(jìn)程，然后啟動(dòng)盤(pán)塊，將該進(jìn)程的程序和數(shù)據(jù)傳送到磁盤(pán)的對(duì)換區(qū)上。若傳送過(guò)程未出現(xiàn)錯(cuò)誤，便可回收該進(jìn)程所占用的內(nèi)存空間，并對(duì)該進(jìn)程的進(jìn)程控制塊做相應(yīng)的修改。(2)進(jìn)程的換入。系統(tǒng)應(yīng)定時(shí)地查看所有進(jìn)程的狀態(tài)，從中找出“就緒”狀態(tài)但已換出的進(jìn)程，將其中換出時(shí)間(換出到磁盤(pán)上)最久的進(jìn)程作為換入進(jìn)程，將之換入，直至已無(wú)可換入的進(jìn)程或無(wú)可換出的進(jìn)程為止。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開(kāi)始，如第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è)表過(guò)長(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。2.地址結(jié)構(gòu)分頁(yè)地址中的地址結(jié)構(gòu)如下：頁(yè)號(hào)P位移量W3112110

對(duì)某特定機(jī)器，其地址結(jié)構(gòu)是一定的。若給定一個(gè)邏輯地址空間中的地址為A，頁(yè)面的大小為L(zhǎng)，則頁(yè)號(hào)P和頁(yè)內(nèi)地址d可按下式求得：3.頁(yè)表圖4-11頁(yè)表的作用4.3.2地址變換機(jī)構(gòu)1.基本的地址變換機(jī)構(gòu)圖4-12分頁(yè)系統(tǒng)的地址變換機(jī)構(gòu)2.具有快表的地址變換機(jī)構(gòu)圖4-13具有快表的地址變換機(jī)構(gòu)4.3.3兩級(jí)和多級(jí)頁(yè)表

現(xiàn)代的大多數(shù)計(jì)算機(jī)系統(tǒng)，都支持非常大的邏輯地址空間(232~264)。在這樣的環(huán)境下，頁(yè)表就變得非常大，要占用相當(dāng)大的內(nèi)存空間。例如，對(duì)于一個(gè)具有32位邏輯地址空間的分頁(yè)系統(tǒng)，規(guī)定頁(yè)面大小為4KB即212B，則在每個(gè)進(jìn)程頁(yè)表中的頁(yè)表項(xiàng)可達(dá)1兆個(gè)之多。又因?yàn)槊總€(gè)頁(yè)表項(xiàng)占用一個(gè)字節(jié)，故每個(gè)進(jìn)程僅僅其頁(yè)表就要占用4KB的內(nèi)存空間，而且還要求是連續(xù)的?？梢圆捎眠@樣兩個(gè)方法來(lái)解決這一問(wèn)題：①采用離散分配方式來(lái)解決難以找到一塊連續(xù)的大內(nèi)存空間的問(wèn)題：②只將當(dāng)前需要的部分頁(yè)表項(xiàng)調(diào)入內(nèi)存，其余的頁(yè)表項(xiàng)仍駐留在磁盤(pán)上，需要時(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位)來(lái)劃分頁(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è)表來(lái)映射它們之間的關(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ǔ)管理方式，主要是為了滿足用戶和程序員的下述一系列需要：

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)地址31161502.段表圖4-16利用段表實(shí)現(xiàn)地址映射圖4-17分段系統(tǒng)的地址變換過(guò)程3.地址變換機(jī)構(gòu)4.分頁(yè)和分段的主要區(qū)別(1)頁(yè)是信息的物理單位，分頁(yè)是為實(shí)現(xiàn)離散分配方式，以消減內(nèi)存的外零頭，提高內(nèi)存的利用率?；蛘哒f(shuō)，分頁(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)度卻不固定，決定于用戶所編寫(xiě)的程序，通常由編譯程序在對(duì)源程序進(jìn)行編譯時(shí)，根據(jù)信息的性質(zhì)來(lái)劃分。

(3)分頁(yè)的作業(yè)地址空間是一維的，即單一的線性地址空間，程序員只需利用一個(gè)記憶符，即可表示一個(gè)地址；而分段的作業(yè)地址空間則是二維的，程序員在標(biāo)識(shí)一個(gè)地址時(shí)，既需給出段名，又需給出段內(nèi)地址。4.4.3信息共享圖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.地址變換過(guò)程圖4-22段頁(yè)式系統(tǒng)中的地址變換機(jī)構(gòu)4.6請(qǐng)求分頁(yè)存儲(chǔ)管理方式4.6.1請(qǐng)求分頁(yè)中的硬件支持1.頁(yè)表機(jī)制頁(yè)號(hào)物理塊號(hào)狀態(tài)位P訪問(wèn)字段A修改位M外存地址2.缺頁(yè)中斷機(jī)構(gòu)圖4-23涉及6次缺頁(yè)中斷的指令3.地址變換機(jī)構(gòu)圖4-24請(qǐng)求分頁(yè)中的地址變換過(guò)程4.6.2內(nèi)存分配策略和分配算法1.最小物理塊數(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)，取決于指令的格式、功能和尋址方式。對(duì)于某些簡(jiǎn)單的機(jī)器，若是單地址指令且采用直接尋址方式，則所需的最少物理塊數(shù)為2。其中，一塊是用于存放指令的頁(yè)面，另一塊則是用于存放數(shù)據(jù)的頁(yè)面。如果該機(jī)器允許間接尋址時(shí)，則至少要求有三個(gè)物理塊。對(duì)于某些功能較強(qiáng)的機(jī)器，其指令長(zhǎng)度可能是兩個(gè)或多于兩個(gè)字節(jié)，因而其指令本身有可能跨兩個(gè)頁(yè)面，且源地址和目標(biāo)地址所涉及的區(qū)域也都可能跨兩個(gè)頁(yè)面。2.物理塊的分配策略

在請(qǐng)求分頁(yè)系統(tǒng)中，可采取兩種內(nèi)存分配策略，即固定和可變分配策略。在進(jìn)行置換時(shí)，也可采取兩種策略，即全局置換和局部置換。于是可組合出以下三種適用的策略。

1)固定分配局部置換(FixedAllocation,LocalReplacement)2)可變分配全局置換(VariableAllocation,GlobalReplacement)3)可變分配局部置換(VariableAllocation,LocalReplacemen3.物理塊分配算法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，將有：b應(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)來(lái)為各進(jìn)程分配其物理塊的。4.6.3調(diào)頁(yè)策略1.何時(shí)調(diào)入頁(yè)面預(yù)調(diào)頁(yè)策略2)請(qǐng)求調(diào)頁(yè)策略2.從何處調(diào)入頁(yè)面

在請(qǐng)求分頁(yè)系統(tǒng)中的外存分為兩部分：用于存放文件的文件區(qū)和用于存放對(duì)換頁(yè)面的對(duì)換區(qū)。通常，由于對(duì)換區(qū)是采用連續(xù)分配方式，而事件是采用離散分配方式，故對(duì)換區(qū)的磁盤(pán)I/O速度比文件區(qū)的高。這樣，每當(dāng)發(fā)生缺頁(yè)請(qǐng)求時(shí)，系統(tǒng)應(yīng)從何處將缺頁(yè)調(diào)入內(nèi)存，可分成如下三種情況：

(1)系統(tǒng)擁有足夠的對(duì)換區(qū)空間，這時(shí)可以全部從對(duì)換區(qū)調(diào)入所需頁(yè)面，以提高調(diào)頁(yè)速度。為此，在進(jìn)程運(yùn)行前，便須將與該進(jìn)程有關(guān)的文件，從文件區(qū)拷貝到對(duì)換區(qū)。(2)系統(tǒng)缺少足夠的對(duì)換區(qū)空間，這時(shí)凡是不會(huì)被修改的文件，都直接從文件區(qū)調(diào)入；而當(dāng)換出這些頁(yè)面時(shí)，由于它們未被修改而不必再將它們換出，以后再調(diào)入時(shí)，仍從文件區(qū)直接調(diào)入。但對(duì)于那些可能被修改的部分，在將它們換出時(shí)，便須調(diào)到對(duì)換區(qū)，以后需要時(shí)，再?gòu)膶?duì)換區(qū)調(diào)入。

(3)UNIX方式。由于與進(jìn)程有關(guān)的文件都放在文件區(qū)，故凡是未運(yùn)行過(guò)的頁(yè)面，都應(yīng)從文件區(qū)調(diào)入。而對(duì)于曾經(jīng)運(yùn)行過(guò)但又被換出的頁(yè)面，由于是被放在對(duì)換區(qū)，因此在下次調(diào)入時(shí)，應(yīng)從對(duì)換區(qū)調(diào)入。由于UNIX系統(tǒng)允許頁(yè)面共享，因此，某進(jìn)程所請(qǐng)求的頁(yè)面有可能已被其它進(jìn)程調(diào)入內(nèi)存，此時(shí)也就無(wú)須再?gòu)膶?duì)換區(qū)調(diào)入。

3.頁(yè)面調(diào)入過(guò)程每當(dā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)存已滿，則須先按照某種置換算法從內(nèi)存中選出一頁(yè)準(zhǔn)備換出；如果該頁(yè)未被修改過(guò)，可不必將該頁(yè)寫(xiě)回磁盤(pán)；但如果此頁(yè)已被修改，則必須將它寫(xiě)回磁盤(pán)，然后再把所缺的頁(yè)調(diào)入內(nèi)存，并修改頁(yè)表中的相應(yīng)表項(xiàng)，置其存在位為“1”，并將此頁(yè)表項(xiàng)寫(xiě)入快表中。在缺頁(yè)調(diào)入內(nèi)存后，利用修改后的頁(yè)表，去形成所要訪問(wèn)數(shù)據(jù)的物理地址，再去訪問(wèn)內(nèi)存數(shù)據(jù)。4.7頁(yè)面置換算法4.7.1最佳置換算法和先進(jìn)先出置換算法1.最佳(Optimal)置換算法最佳置換算法是由Belady于1966年提出的一種理論上的算法。其所選擇的被淘汰頁(yè)面，將是以后永不使用的，或許是在最長(zhǎng)(未來(lái))時(shí)間內(nèi)不再被訪問(wèn)的頁(yè)面。采用最佳置換算法，通?？杀ＷC獲得最低的缺頁(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)程要訪問(wèn)頁(yè)面2時(shí)，將會(huì)產(chǎn)生缺頁(yè)中斷。此時(shí)OS根據(jù)最佳置換算法，將選擇頁(yè)面7予以淘汰。圖4-25利用最佳頁(yè)面置換算法時(shí)的置換圖2.先進(jìn)先出(FIFO)頁(yè)面置換算法圖4-26利用FIFO置換算法時(shí)的置換圖4.7.2最近最久未使用(LRU)置換算法1.LRU(LeastRecentlyUsed)置換算法的描述圖4-27LRU頁(yè)面置換算法2.LRU置換算法的硬件支持1)寄存器為了記錄某進(jìn)程在內(nèi)存中各頁(yè)的使用情況，須為每個(gè)在內(nèi)存中的頁(yè)面配置一個(gè)移位寄存器，可表示為R=Rn-1Rn-2Rn-3…R2R1R0

圖4-28某進(jìn)程具有8個(gè)頁(yè)面時(shí)的LRU訪問(wèn)情況2)棧圖4-29用棧保存當(dāng)前使用頁(yè)面時(shí)棧的變化情況4.7.3Clock置換算法1.簡(jiǎn)單的Clock置換算法圖4-30簡(jiǎn)單Clock置換算法的流程和示例2.改進(jìn)型Clock置換算法

由訪問(wèn)位A和修改位M可以組合成下面四種類型的頁(yè)面：

1類(A=0,M=0):

表示該頁(yè)最近既未被訪問(wèn)，又未被修改，是最佳淘汰頁(yè)。

2類(A=0,M=1)：表示該頁(yè)最近未被訪問(wèn)，但已被修改，并不是很好的淘汰頁(yè)。

3類(A=1,M=0)：最近已被訪問(wèn)，但未被修改，該頁(yè)有可能再被訪問(wèn)。

4類(A=1,M=1):

最近已被訪問(wèn)且被修改，該頁(yè)可能再被訪問(wèn)。

其執(zhí)行過(guò)程可分成以下三步：

(1)從指針?biāo)甘镜漠?dāng)前位置開(kāi)始，掃描循環(huán)隊(duì)列，尋找A=0且M=0的第一類頁(yè)面，將所遇到的第一個(gè)頁(yè)面作為所選中的淘汰頁(yè)。在第一次掃描期間不改變?cè)L問(wèn)位A。

(2)如果第一步失敗，即查找一周后未遇到第一類頁(yè)面，則開(kāi)始第二輪掃描，尋找A=0且M=1的第二類頁(yè)面，將所遇到的第一個(gè)這類頁(yè)面作為淘汰頁(yè)。在第二輪掃描期間，將所有掃描過(guò)的頁(yè)面的訪問(wèn)位都置0。

(3)如果第二步也失敗，亦即未找到第二類頁(yè)面，則將指針?lè)祷氐介_(kāi)始的位置，并將所有的訪問(wèn)位復(fù)0。然后重復(fù)第一步，如果仍失敗，必要時(shí)再重復(fù)第二步，此時(shí)就一定能找到被淘汰的頁(yè)。