內(nèi)存管理

總的來(lái)說(shuō)，包括內(nèi)存管理和虛擬內(nèi)存管理。
內(nèi)存管理包括程序裝入等概念、交換技術(shù)、連續(xù)分配管理方式和非連續(xù)分配管理方式（分頁(yè)、分段、段頁(yè)式）。
虛擬內(nèi)存管理包括虛擬內(nèi)存概念、請(qǐng)求分頁(yè)管理方式、頁(yè)面置換算法、頁(yè)面分配策略、工作集和抖動(dòng)。

存儲(chǔ)器層次結(jié)構(gòu)

寄存器 -- 高速緩存 -- 主存儲(chǔ)器 -- 磁盤(pán)緩存 -- 固定磁盤(pán) -- 可移動(dòng)存儲(chǔ)介質(zhì)

程序裝入和鏈接

創(chuàng)建進(jìn)程首先要將程序和數(shù)據(jù)裝入內(nèi)存。將用戶源程序變?yōu)榭稍趦?nèi)存中執(zhí)行的程序，通常需要以下幾個(gè)步驟：

• 編譯：由編譯程序?qū)⒂脩粼创a編譯成若干個(gè)目標(biāo)模塊。
• 鏈接：由鏈接程序?qū)⒕幾g后形成的一組目標(biāo)模塊，以及所需庫(kù)函數(shù)鏈接在一起，形成一個(gè)完整的裝入模塊。

• 裝入：由裝入程序?qū)⒀b入模塊裝入內(nèi)存運(yùn)行。

  
  
  對(duì)用戶程序的處理步驟.jpg

程序的鏈接方式：

• 靜態(tài)鏈接：在程序運(yùn)行之前，先將各目標(biāo)模塊及它們所需的庫(kù)函數(shù)鏈接成一個(gè)完整的可執(zhí)行程序，以后不再拆開(kāi)。
• 裝入時(shí)動(dòng)態(tài)鏈接：將用戶源程序編譯后所得到的一組目標(biāo)模塊，在裝入內(nèi)存時(shí)，釆用邊裝入邊鏈接的鏈接方式。
• 運(yùn)行時(shí)動(dòng)態(tài)鏈接：對(duì)某些目標(biāo)模塊的鏈接，是在程序執(zhí)行中需要該目標(biāo)模塊時(shí)，才對(duì)它進(jìn)行的鏈接。其優(yōu)點(diǎn)是便于修改和更新，便于實(shí)現(xiàn)對(duì)目標(biāo)模塊的共享。

程序的裝入方式：

1. 絕對(duì)裝入：在編譯時(shí)，如果知道程序?qū)Ⅰv留在內(nèi)存的某個(gè)位置，編譯程序?qū)a(chǎn)生絕對(duì)地址的目標(biāo)代碼。絕對(duì)裝入程序按照裝入模塊中的地址，將程序和數(shù)據(jù)裝入內(nèi)存。由于程序中的邏輯地址與實(shí)際內(nèi)存地址完全相同，故不需對(duì)程序和數(shù)據(jù)的地址進(jìn)行修改。
2. 可重定位裝入：在多道程序環(huán)境下，多個(gè)目標(biāo)模塊的起始地址通常都是從 0 開(kāi)始，程序中的其他地址都是相對(duì)于起始地址的,此時(shí)應(yīng)釆用可重定位裝入方式。根據(jù)內(nèi)存的當(dāng)前情況，將裝入模塊裝入到內(nèi)存的適當(dāng)位置。裝入時(shí)對(duì)目標(biāo)程序中指令和數(shù)據(jù)的修改過(guò)程稱(chēng)為重定位，地址變換通常是在裝入時(shí)一次完成的，所以又稱(chēng)為靜態(tài)重定位。
   靜態(tài)重定位的特點(diǎn)是在一個(gè)作業(yè)裝入內(nèi)存時(shí)，必須分配其要求的全部?jī)?nèi)存空間，如果沒(méi)有足夠的內(nèi)存，就不能裝入該作業(yè)。此外，作業(yè)一旦進(jìn)入內(nèi)存后，在整個(gè)運(yùn)行期間不能在內(nèi)存中移動(dòng)，也不能再申請(qǐng)內(nèi)存空間。
3. 動(dòng)態(tài)運(yùn)行時(shí)裝入，也稱(chēng)為動(dòng)態(tài)重定位：程序在內(nèi)存中如果發(fā)生移動(dòng)，就需要釆用動(dòng)態(tài)的裝入方式。裝入程序在把裝入模塊裝入內(nèi)存后，并不立即把裝入模塊中的相對(duì)地址轉(zhuǎn)換為絕對(duì)地址，而是把這種地址轉(zhuǎn)換推遲到程序真正要執(zhí)行時(shí)才進(jìn)行。因此，裝入內(nèi)存后的所有地址均為相對(duì)地址。這種方式需要一個(gè)重定位寄存器的支持。
   動(dòng)態(tài)重定位的特點(diǎn)是可以將程序分配到不連續(xù)的存儲(chǔ)區(qū)中；在程序運(yùn)行之前可以只裝入它的部分代碼即可投入運(yùn)行，然后在程序運(yùn)行期間，根據(jù)需要?jiǎng)討B(tài)申請(qǐng)分配內(nèi)存；便于程序段的共享，可以向用戶提供一個(gè)比存儲(chǔ)空間大得多的地址空間。

重定向類(lèi)型.jpg

內(nèi)存保護(hù)

內(nèi)存分配前，需要保護(hù)操作系統(tǒng)不受用戶進(jìn)程的影響，同時(shí)保護(hù)用戶進(jìn)程不受其他用戶進(jìn)程的影響。通過(guò)釆用重定位寄存器和界地址寄存器來(lái)實(shí)現(xiàn)這種保護(hù)。重定位寄存器含最小的物理地址值，界地址寄存器含邏輯地址值。
每個(gè)邏輯地址值必須小于界地址寄存器；內(nèi)存管理機(jī)構(gòu)動(dòng)態(tài)地將邏輯地址與界地址寄存器進(jìn)行比較，如果未發(fā)生地址越界，則加上重定位寄存器的值后映射成物理地址，再送交內(nèi)存單元。
當(dāng)CPU調(diào)度程序選擇進(jìn)程執(zhí)行時(shí)，派遣程序會(huì)初始化重定位寄存器和界地址寄存器。每一個(gè)邏輯地址都需要與這兩個(gè)寄存器進(jìn)行核對(duì)，以保證操作系統(tǒng)和其他用戶程序及數(shù)據(jù)不被該進(jìn)程的運(yùn)行所影響。

內(nèi)存交換

交換（對(duì)換）的基本思想是，把處于等待狀態(tài)（或在 CPU 調(diào)度原則下被剝奪運(yùn)行權(quán)利）的程序從內(nèi)存移到輔存，把內(nèi)存空間騰出來(lái)，這一過(guò)程又叫換出；把準(zhǔn)備好競(jìng)爭(zhēng) CPU 運(yùn)行的程序從輔存移到內(nèi)存，這一過(guò)程又稱(chēng)為換入。中級(jí)調(diào)度就是釆用交換技術(shù)。

注意一下問(wèn)題：

• 交換需要備份存儲(chǔ)，通常是快速磁盤(pán)。它必須足夠大，并且提供對(duì)這些內(nèi)存映像的直接訪問(wèn)。
• 為了有效使用CPU，需要每個(gè)進(jìn)程的執(zhí)行時(shí)間比交換時(shí)間長(zhǎng)，而影響交換時(shí)間的主要是轉(zhuǎn)移時(shí)間。轉(zhuǎn)移時(shí)間與所交換的內(nèi)存空間成正比。
• 如果換出進(jìn)程，必須確保該進(jìn)程是完全處于空閑狀態(tài)。
• 普通的交換使用不多，但交換策略的某些變種在許多系統(tǒng)中（如 UNIX 系統(tǒng)）仍發(fā)揮作用。

內(nèi)存連續(xù)分配管理方式

連續(xù)分配方式，是指為一個(gè)用戶程序分配一個(gè)連續(xù)的內(nèi)存空間。它主要包括單一連續(xù)分配、固定分區(qū)分配和動(dòng)態(tài)分區(qū)分配。

單一連續(xù)分配

內(nèi)存在此方式下分為系統(tǒng)區(qū)和用戶區(qū)，系統(tǒng)區(qū)僅提供給操作系統(tǒng)使用，通常在低地址部分；用戶區(qū)是為用戶提供的、除系統(tǒng)區(qū)之外的內(nèi)存空間。這種方式無(wú)需進(jìn)行內(nèi)存保護(hù)。

固定分區(qū)分配

將用戶內(nèi)存空間劃分為若干個(gè)固定大小的區(qū)域，每個(gè)分區(qū)只裝入一道作業(yè)。當(dāng)有空閑分區(qū)時(shí)，便可以再?gòu)耐獯娴暮髠渥鳂I(yè)隊(duì)列中,選擇適當(dāng)大小的作業(yè)裝入該分區(qū)，如此循環(huán)。

這種分區(qū)方式存在兩個(gè)問(wèn)題：一是程序可能太大而放不進(jìn)任何一個(gè)分區(qū)中，這時(shí)用戶不得不使用覆蓋技術(shù)來(lái)使用內(nèi)存空間；二是主存利用率低，當(dāng)程序小于固定分區(qū)大小時(shí)，也占用了一個(gè)完整的內(nèi)存分區(qū)空間，這樣分區(qū)內(nèi)部有空間浪費(fèi)，這種現(xiàn)象稱(chēng)為內(nèi)部碎片。

動(dòng)態(tài)分區(qū)分配

(與 JVM 垃圾回收進(jìn)行對(duì)比)
動(dòng)態(tài)分區(qū)分配又稱(chēng)為可變分區(qū)分配，是一種動(dòng)態(tài)劃分內(nèi)存的分區(qū)方法。這種分區(qū)方法不預(yù)先將內(nèi)存劃分，而是在進(jìn)程裝入內(nèi)存時(shí)，根據(jù)進(jìn)程的大小動(dòng)態(tài)地建立分區(qū)，并使分區(qū)的大小正好適合進(jìn)程的需要。因此系統(tǒng)中分區(qū)的大小和數(shù)目是可變的。

在進(jìn)程裝入或換入主存時(shí)，如果內(nèi)存中有多個(gè)足夠大的空閑塊，操作系統(tǒng)必須確定分配哪個(gè)內(nèi)存塊給進(jìn)程使用，這就是動(dòng)態(tài)分區(qū)的分配策略，考慮以下幾種算法：

• 首次適應(yīng)(First Fit)算法：空閑分區(qū)以地址遞增的次序鏈接。分配內(nèi)存時(shí)順序查找，找到大小能滿足要求的第一個(gè)空閑分區(qū)。
• 最佳適應(yīng)(Best Fit)算法：空閑分區(qū)按容量遞增形成分區(qū)鏈，找到第一個(gè)能滿足要求的空閑分區(qū)。
• 最壞適應(yīng)(Worst Fit)算法：又稱(chēng)最大適應(yīng)(Largest Fit)算法，空閑分區(qū)以容量遞減的次序鏈接。找到第一個(gè)能滿足要求的空閑分區(qū)，也就是挑選出最大的分區(qū)。
• 鄰近適應(yīng)(Next Fit)算法：又稱(chēng)循環(huán)首次適應(yīng)算法，由首次適應(yīng)算法演變而成。不同之處是分配內(nèi)存時(shí)從上次查找結(jié)束的位置開(kāi)始繼續(xù)查找。

在這幾種方法中，首次適應(yīng)算法不僅是最簡(jiǎn)單的，而且通常也是最好和最快的。

內(nèi)存非連續(xù)分配管理方式

非連續(xù)分配允許一個(gè)程序分散地裝入到不相鄰的內(nèi)存分區(qū)中，根據(jù)分區(qū)的大小是否固定分為分頁(yè)存儲(chǔ)管理方式和分段存儲(chǔ)管理方式。

分頁(yè)存儲(chǔ)管理方式中，又根據(jù)運(yùn)行作業(yè)時(shí)是否要把作業(yè)的所有頁(yè)面都裝入內(nèi)存才能運(yùn)行分為基本分頁(yè)存儲(chǔ)管理方式和請(qǐng)求分頁(yè)存儲(chǔ)管理方式。

基本分頁(yè)存儲(chǔ)管理方式

固定分區(qū)會(huì)產(chǎn)生內(nèi)部碎片，動(dòng)態(tài)分區(qū)會(huì)產(chǎn)生外部碎片，這兩種技術(shù)對(duì)內(nèi)存的利用率都比較低。我們希望內(nèi)存的使用能盡量避免碎片的產(chǎn)生，這就引入了分頁(yè)的思想：把主存空間劃分為大小相等且固定的塊，塊相對(duì)較小，作為主存的基本單位。每個(gè)進(jìn)程也以塊為單位進(jìn)行劃分，進(jìn)程在執(zhí)行時(shí)，以塊為單位逐個(gè)申請(qǐng)主存中的塊空間。

分頁(yè)的方法從形式上看，像分區(qū)相等的固定分區(qū)技術(shù)，分頁(yè)管理不會(huì)產(chǎn)生外部碎片。但它又有本質(zhì)的不同點(diǎn)：塊的大小相對(duì)分區(qū)要小很多，而且進(jìn)程也按照塊進(jìn)行劃分，進(jìn)程運(yùn)行時(shí)按塊申請(qǐng)主存可用空間并執(zhí)行。這樣，進(jìn)程只會(huì)在為最后一個(gè)不完整的塊申請(qǐng)一個(gè)主存塊空間時(shí)，才產(chǎn)生主存碎片，所以盡管會(huì)產(chǎn)生內(nèi)部碎片，但是這種碎片相對(duì)于進(jìn)程來(lái)說(shuō)也是很小的。

分頁(yè)存儲(chǔ)的幾個(gè)概念：

a. 頁(yè)面和頁(yè)面大小。進(jìn)程中的塊稱(chēng)為頁(yè)(Page)，內(nèi)存中的塊稱(chēng)為頁(yè)框（Page Frame，或頁(yè)幀）。外存也以同樣的單位進(jìn)行劃分，直接稱(chēng)為塊(Block)。進(jìn)程在執(zhí)行時(shí)需要申請(qǐng)主存空間，就是要為每個(gè)頁(yè)面分配主存中的可用頁(yè)框，這就產(chǎn)生了頁(yè)和頁(yè)框的一一對(duì)應(yīng)。

為方便地址轉(zhuǎn)換，頁(yè)面大小應(yīng)是 2 的整數(shù)冪。同時(shí)頁(yè)面大小應(yīng)該適中，如果頁(yè)面太小，會(huì)使進(jìn)程的頁(yè)面數(shù)過(guò)多，這樣頁(yè)表就過(guò)長(zhǎng)，占用大量?jī)?nèi)存，而且也會(huì)增加硬件地址轉(zhuǎn)換的開(kāi)銷(xiāo)，降低頁(yè)面換入/換出的效率；頁(yè)面過(guò)大又會(huì)使頁(yè)內(nèi)碎片增大，降低內(nèi)存的利用率。所以頁(yè)面的大小應(yīng)該適中，考慮到耷間效率和時(shí)間效率的權(quán)衡。

b. 地址結(jié)構(gòu)。分頁(yè)存儲(chǔ)管理的邏輯地址結(jié)構(gòu)如圖:

分頁(yè)存儲(chǔ)管理的地址結(jié)構(gòu).jpg

地址結(jié)構(gòu)包含兩部分：前一部分為頁(yè)號(hào) P，后一部分為頁(yè)內(nèi)偏移量W。地址長(zhǎng)度為 32 位，其中 0~11 位為頁(yè)內(nèi)地址，即每頁(yè)大小為 4KB ；12~31 位為頁(yè)號(hào)，地址空間最多允許有 2^20 頁(yè)。

c. 頁(yè)表。為了便于在內(nèi)存中找到進(jìn)程的每個(gè)頁(yè)面所對(duì)應(yīng)的物理塊，系統(tǒng)為每個(gè)進(jìn)程建立一張頁(yè)表，記錄頁(yè)面在內(nèi)存中對(duì)應(yīng)的物理塊號(hào)，頁(yè)表一般存放在內(nèi)存中。在配置了頁(yè)表后，進(jìn)程執(zhí)行時(shí)，通過(guò)查找該表，即可找到每頁(yè)在內(nèi)存中的物理塊號(hào)。可見(jiàn)，頁(yè)表的作用是實(shí)現(xiàn)從頁(yè)號(hào)到物理塊號(hào)的地址映射。

頁(yè)表的作用.jpg

基本地址變換機(jī)構(gòu)

地址變換機(jī)構(gòu)的任務(wù)是將邏輯地址轉(zhuǎn)換為內(nèi)存中物理地址，地址變換是借助于頁(yè)表實(shí)現(xiàn)的。

分頁(yè)存儲(chǔ)管理的地址變換機(jī)構(gòu).jpg

分頁(yè)管理方式存在的兩個(gè)主要問(wèn)題：

• 每次訪存操作都需要進(jìn)行邏輯地址到物理地址的轉(zhuǎn)換，地址轉(zhuǎn)換過(guò)程必須足夠快，否則訪存速度會(huì)降低；
• 每個(gè)進(jìn)程引入了頁(yè)表，用于存儲(chǔ)映射機(jī)制，頁(yè)表不能太大，否則內(nèi)存利用率會(huì)降低。

具有快表的地址變換機(jī)構(gòu)

由上面介紹的地址變換過(guò)程可知，若頁(yè)表全部放在內(nèi)存中，則存取一個(gè)數(shù)據(jù)或一條指令至少要訪問(wèn)兩次內(nèi)存：一次是訪問(wèn)頁(yè)表，確定所存取的數(shù)據(jù)或指令的物理地址，第二次才根據(jù)該地址存取數(shù)據(jù)或指令。顯然，這種方法比通常執(zhí)行指令的速度慢了一半。

為此，在地址變換機(jī)構(gòu)中增設(shè)了一個(gè)具有并行查找能力的高速緩沖存儲(chǔ)器——快表，又稱(chēng)聯(lián)想寄存器(TLB)，用來(lái)存放當(dāng)前訪問(wèn)的若干頁(yè)表項(xiàng)，以加速地址變換的過(guò)程。與此對(duì)應(yīng)，主存中的頁(yè)表也常稱(chēng)為慢表，配有快表的地址變換機(jī)構(gòu)如圖所示。

具有快表的地址變換機(jī)構(gòu).jpg

一般快表的命中率可以達(dá)到90%以上，這樣，分頁(yè)帶來(lái)的速度損失就降低到10%以下。快表的有效性是基于著名的局部性原理。

兩級(jí)頁(yè)表

第二個(gè)問(wèn)題：由于引入了分頁(yè)管理，進(jìn)程在執(zhí)行時(shí)不需要將所有頁(yè)調(diào)入內(nèi)存頁(yè)框中，而只要將保存有映射關(guān)系的頁(yè)表調(diào)入內(nèi)存中即可。但是我們?nèi)匀恍枰紤]頁(yè)表的大小。

將頁(yè)表映射的思想進(jìn)一步延伸，就可以得到二級(jí)分頁(yè)：將頁(yè)表的10頁(yè)空間也進(jìn)行地址映射，建立上一級(jí)頁(yè)表，用于存儲(chǔ)頁(yè)表的映射關(guān)系。這里對(duì)頁(yè)表的10個(gè)頁(yè)面進(jìn)行映射只需要10個(gè)頁(yè)表項(xiàng)，所以上一級(jí)頁(yè)表只需要1頁(yè)就足夠（可以存儲(chǔ) 2^10=1024個(gè)頁(yè)表項(xiàng)）。在進(jìn)程執(zhí)行時(shí)，只需要將這1頁(yè)的上一級(jí)頁(yè)表調(diào)入內(nèi)存即可，進(jìn)程的頁(yè)表和進(jìn)程本身的頁(yè)面，可以在后面的執(zhí)行中再 i 周入內(nèi)存。

如圖所示，這是Intel處理器80x86系列的硬件分頁(yè)的地址轉(zhuǎn)換過(guò)程。在32位系統(tǒng)中，全部32位邏輯地址空間可以分為2^20 (4GB/4KB)個(gè)頁(yè)面。這些頁(yè)面可以再進(jìn)一步建立頂級(jí)頁(yè)表，需要2^10個(gè)頂級(jí)頁(yè)表項(xiàng)進(jìn)行索引，這正好是一頁(yè)的大小，所以建立二級(jí)頁(yè)表即可。

硬件分頁(yè)地址轉(zhuǎn)換.jpg

基本分段存儲(chǔ)管理方式

分頁(yè)管理方式是從計(jì)算機(jī)的角度考慮設(shè)計(jì)的，以提高內(nèi)存的利用率，提升計(jì)算機(jī)的性能, 且分頁(yè)通過(guò)硬件機(jī)制實(shí)現(xiàn)，對(duì)用戶完全透明；而分段管理方式的提出則是考慮了用戶和程序員，以滿足方便編程、信息保護(hù)和共享、動(dòng)態(tài)增長(zhǎng)及動(dòng)態(tài)鏈接等多方面的需要。

分段

段式管理方式按照用戶進(jìn)程中的自然段劃分邏輯空間。例如，用戶進(jìn)程由主程序、兩個(gè)子程序、棧和一段數(shù)據(jù)組成，于是可以把這個(gè)用戶進(jìn)程劃分為5個(gè)段，每段從0 開(kāi)始編址，并分配一段連續(xù)的地址空間（段內(nèi)要求連續(xù)，段間不要求連續(xù)，因此整個(gè)作業(yè)的地址空間是二維的）。其邏輯地址由段號(hào)S與段內(nèi)偏移量W兩部分組成。

在頁(yè)式系統(tǒng)中，邏輯地址的頁(yè)號(hào)和頁(yè)內(nèi)偏移量對(duì)用戶是透明的，但在段式系統(tǒng)中，段號(hào)和段內(nèi)偏移量必須由用戶顯示提供，在髙級(jí)程序設(shè)計(jì)語(yǔ)言中，這個(gè)工作由編譯程序完成。

段表

每個(gè)進(jìn)程都有一張邏輯空間與內(nèi)存空間映射的段表，其中每一個(gè)段表項(xiàng)對(duì)應(yīng)進(jìn)程的一個(gè)段，段表項(xiàng)記錄該段在內(nèi)存中的起始地址和段的長(zhǎng)度。段表的內(nèi)容如圖所示。

段表項(xiàng).jpg

在配置了段表后，執(zhí)行中的進(jìn)程可通過(guò)查找段表，找到每個(gè)段所對(duì)應(yīng)的內(nèi)存區(qū)。

段的共享與保護(hù)

在分段系統(tǒng)中，段的共享是通過(guò)兩個(gè)作業(yè)的段表中相應(yīng)表項(xiàng)指向被共享的段的同一個(gè)物理副本來(lái)實(shí)現(xiàn)的。當(dāng)一個(gè)作業(yè)正從共享段中讀取數(shù)據(jù)時(shí)，必須防止另一個(gè)作業(yè)修改此共享段中的數(shù)據(jù)。不能修改的代碼稱(chēng)為純代碼或可重入代碼（它不屬于臨界資源)，這樣的代碼和不能修改的數(shù)據(jù)是可以共享的，而可修改的代碼和數(shù)據(jù)則不能共享。

與分頁(yè)管理類(lèi)似，分段管理的保護(hù)方法主要有兩種：一種是存取控制保護(hù)，另一種是地址越界保護(hù)。地址越界保護(hù)是利用段表寄存器中的段表長(zhǎng)度與邏輯地址中的段號(hào)比較，若段號(hào)大于段表長(zhǎng)度則產(chǎn)生越界中斷；再利用段表項(xiàng)中的段長(zhǎng)和邏輯地址中的段內(nèi)位移進(jìn)行比較，若段內(nèi)位移大于段長(zhǎng)，也會(huì)產(chǎn)生越界中斷。

段頁(yè)式管理方式

頁(yè)式存儲(chǔ)管理能有效地提高內(nèi)存利用率，而分段存儲(chǔ)管理能反映程序的邏輯結(jié)構(gòu)并有利于段的共享。如果將這兩種存儲(chǔ)管理方法結(jié)合起來(lái)，就形成了段頁(yè)式存儲(chǔ)管理方式。

在段頁(yè)式系統(tǒng)中，作業(yè)的地址空間首先被分成若干個(gè)邏輯段，每段都有自己的段號(hào)，然后再將每一段分成若干個(gè)大小固定的頁(yè)。對(duì)內(nèi)存空間的管理仍然和分頁(yè)存儲(chǔ)管理一樣，將其分成若干個(gè)和頁(yè)面大小相同的存儲(chǔ)塊，對(duì)內(nèi)存的分配以存儲(chǔ)塊為單位，如圖所示。

段頁(yè)式管理方式.jpg

在進(jìn)行地址變換時(shí)，首先通過(guò)段表查到頁(yè)表起始地址，然后通過(guò)頁(yè)表找到頁(yè)幀號(hào)，最后形成物理地址。如圖所示，進(jìn)行一次訪問(wèn)實(shí)際需要三次訪問(wèn)主存，這里同樣可以使用快表以加快查找速度，其關(guān)鍵字由段號(hào)、頁(yè)號(hào)組成，值是對(duì)應(yīng)的頁(yè)幀號(hào)和保護(hù)碼。

段頁(yè)式系統(tǒng)的地址變換機(jī)構(gòu).jpg

虛擬內(nèi)存

剛剛說(shuō)的內(nèi)存管理方式有個(gè)特點(diǎn)：都要求將一個(gè)作業(yè)全部裝入內(nèi)存后才能運(yùn)行。這在作業(yè)很大或是作業(yè)量很大的時(shí)候會(huì)出現(xiàn)問(wèn)題，除了從物理上增加內(nèi)存容量，還可以從邏輯上擴(kuò)充容量，這就是虛擬內(nèi)存。

當(dāng)訪問(wèn)虛擬內(nèi)存時(shí)，會(huì)通過(guò) MMU（內(nèi)存管理單元）去匹配對(duì)應(yīng)的物理地址，而如果虛擬內(nèi)存的頁(yè)并不存在于物理內(nèi)存中，會(huì)產(chǎn)生缺頁(yè)中斷，從磁盤(pán)中取得缺的頁(yè)放入內(nèi)存，如果內(nèi)存已滿，還會(huì)根據(jù)某種算法將磁盤(pán)中的頁(yè)換出。

頁(yè)面置換算法

頁(yè)面置換算法和緩存淘汰策略類(lèi)似。在緩存系統(tǒng)中，緩存的大小有限，當(dāng)有新的緩存到達(dá)時(shí)，需要淘汰一部分已經(jīng)存在的緩存，這樣才有空間存放新的緩存數(shù)據(jù)。

頁(yè)面置換算法的主要目標(biāo)是使頁(yè)面置換頻率最低（也可以說(shuō)缺頁(yè)率最低）。

1. 最佳 Optimal
   所選擇的被換出的頁(yè)面將是最長(zhǎng)時(shí)間內(nèi)不再被訪問(wèn)，通?？梢员ＷC獲得最低的缺頁(yè)率。
   是一種理論上的算法，因?yàn)闊o(wú)法知道一個(gè)頁(yè)面多長(zhǎng)時(shí)間不再被訪問(wèn)。
2. 最近最久未使用 （LRU, Least Recently Used）
   雖然無(wú)法知道將來(lái)要使用的頁(yè)面情況，但是可以知道過(guò)去使用頁(yè)面的情況。LRU 將最近最久未使用的頁(yè)面換出。
   為了實(shí)現(xiàn) LRU，需要在內(nèi)存中維護(hù)一個(gè)所有頁(yè)面的鏈表。當(dāng)一個(gè)頁(yè)面被訪問(wèn)時(shí)，將這個(gè)頁(yè)面移到鏈表表頭。這樣就能保證鏈表表尾的頁(yè)面時(shí)最近最久未訪問(wèn)的。因?yàn)槊看卧L問(wèn)都需要更新鏈表，因此這種方式實(shí)現(xiàn)的 LRU 代價(jià)很高。
3. 最近未使用（NRU, Not Recently Used）
   首先，系統(tǒng)為毎一頁(yè)面設(shè)置了兩個(gè)狀態(tài)位。當(dāng)頁(yè)面被訪問(wèn) (讀或?qū)? 時(shí)設(shè)置 R 位; 當(dāng)頁(yè)面 (即修改頁(yè)面) 被寫(xiě)入時(shí)設(shè)置 M 位。當(dāng)啟動(dòng)一個(gè)進(jìn)程時(shí)，它的所有頁(yè)面的兩個(gè)位都由操作系統(tǒng)設(shè)置成 0，R 位被定期地 (比如在每次時(shí)鐘中斷時(shí)) 清零，以區(qū)別最近沒(méi)有被訪問(wèn)的頁(yè)面和被訪問(wèn)的頁(yè)面。
   當(dāng)發(fā)生缺頁(yè)中斷時(shí)，操作系統(tǒng)檢査所有的頁(yè)面并根據(jù)它們當(dāng)前的 R 位和 M 位的值，把它們分為 4 類(lèi)，NRU 算法隨機(jī)地從類(lèi)編號(hào)最小的非空類(lèi)中挑選一個(gè)頁(yè)面淘汰之。
4. 先進(jìn)先出（FIFO, First In First Out）
   選擇換出的頁(yè)面是最先進(jìn)入的頁(yè)面。
   該算法會(huì)將那些經(jīng)常被訪問(wèn)的頁(yè)面也被換出，從而使缺頁(yè)率升高。
5. 改進(jìn)型FIFO (Second Chance Page Replacement Algorithm)
   這種算法是在FIFO的基礎(chǔ)上，為了避免置換出經(jīng)常使用的頁(yè)，增加一個(gè)標(biāo)志位R，如果最近使用過(guò)將 R 置1，當(dāng)頁(yè)將會(huì)淘汰時(shí)，如果 R 為1，則不淘汰頁(yè)，將 R 置0.而那些 R=0 的頁(yè)將被淘汰時(shí)，直接淘汰。這種算法避免了經(jīng)常被使用的頁(yè)被淘汰。
6. 時(shí)鐘替換 (Clock Page Replacement Algorithm)
   雖然改進(jìn)型 FIFO 算法避免置換出常用的頁(yè)，但由于需要經(jīng)常移動(dòng)頁(yè)，效率并不高。因此在改進(jìn)型 FIFO 算法的基礎(chǔ)上，將隊(duì)列首位相連形成一個(gè)環(huán)路，當(dāng)缺頁(yè)中斷產(chǎn)生時(shí)，從當(dāng)前位置開(kāi)始找R=0的頁(yè)，而所經(jīng)過(guò)的 R=1 的頁(yè)被置 0，并不需要移動(dòng)頁(yè)。