寫在前面：本文參考王道論壇的 操作系統(tǒng)考研復(fù)習(xí)指導(dǎo)單科書(shū)

下面的流程圖很重要。
加入快表的基本分頁(yè)

加入快表的二級(jí)頁(yè)表！！

虛擬存儲(chǔ)器：請(qǐng)求分頁(yè)的流程圖。

文章目錄

• 第三章 內(nèi)存管理
• • 3.1 內(nèi)存管理概念
  • • 3.1.1 內(nèi)存管理的基本原理和要求
    • • 1 程序裝入和鏈接
      • 2 邏輯地址空間與物理地址空間
      • 3 內(nèi)存保護(hù)
    • 3.1.2 覆蓋與交換
    • • 1 覆蓋
      • 2 交換
    • 3.1.3 連續(xù)分配管理方式
    • • 1 單一連續(xù)分配
      • 2 固定分區(qū)分配
      • 3 動(dòng)態(tài)分區(qū)分配
    • 3.1.4 非連續(xù)分配管理方式
    • • 1 基本分頁(yè)存儲(chǔ)管理方式
      • • （1）分頁(yè)存儲(chǔ)的幾個(gè)基本概念
        • （2） 基本地址變換機(jī)構(gòu)
        • （3）具有快表的地址變換機(jī)構(gòu)
        • （4）兩級(jí)頁(yè)表
      • 2 基本分段存儲(chǔ)管理方式
      • 3 段頁(yè)式管理方式
  • 王道習(xí)題（二級(jí)頁(yè)表）
  • 3.2虛擬內(nèi)存管理
  • • 3.2.1 虛擬內(nèi)存的基本概念
    • 3.2.2 請(qǐng)求分頁(yè)管理方式
    • 3.2.3 頁(yè)面置換算法
    • • 1. 最佳（OPT）置換算法
      • 2. 先進(jìn)先出（FIFO）置換算法
      • 3.最近最久未使用（LRU）置換算法
      • 4. 時(shí)鐘（CLOCK）置換算法
    • 3.2.4 頁(yè)面分配策略
    • 3.2.5 抖動(dòng)
    • 3.2.6 工作集
    • 王道習(xí)題

第三章 內(nèi)存管理

3.1 內(nèi)存管理概念

3.1.1 內(nèi)存管理的基本原理和要求

內(nèi)存管理是操作系統(tǒng)設(shè)計(jì)中最重要和最復(fù)雜的內(nèi)容之一。雖然計(jì)算機(jī)硬件技術(shù)一直在發(fā)展，內(nèi)存容量也在不斷增大，但是仍然不可能將所有的用戶進(jìn)程和系統(tǒng)所需要的全部程序與數(shù)據(jù)放入內(nèi)存，因此操作系統(tǒng)必須對(duì)內(nèi)存空間進(jìn)行合理的劃分和有效的動(dòng)態(tài)分配。 操作系統(tǒng)對(duì)內(nèi)存的劃分和動(dòng)態(tài)分配，就是內(nèi)存管理的概念。

1 程序裝入和鏈接

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

• 編譯。由編譯程序?qū)⒂脩粼创a編譯成若干目標(biāo)代碼。就是.o文件，每個(gè)模塊的編址相互獨(dú)立，都從0開(kāi)始。
• 鏈接。由鏈接程序?qū)⒕幾g后形成的一組目標(biāo)模塊及所需的庫(kù)函數(shù)鏈接在一起，形成一個(gè)完整的裝入模塊。就是.exe文件。
• 裝入。由裝入程序?qū)⒀b入模塊裝入內(nèi)存中運(yùn)行。

程序的鏈接有以下三種方式

1）靜態(tài)鏈接。在程序運(yùn)行之前，先將各目標(biāo)模塊及它們所需要的庫(kù)函數(shù)鏈接成一個(gè)可執(zhí)行程序，以后不再拆開(kāi)。

2）裝入時(shí)動(dòng)態(tài)鏈接。將用戶源程序編譯后所得到的一組目標(biāo)模塊，在裝入內(nèi)存時(shí)，采用邊裝入邊鏈接的方式。

3）運(yùn)行時(shí)動(dòng)態(tài)鏈接。對(duì)某些目標(biāo)模塊的鏈接，是在程序執(zhí)行中需要該目標(biāo)模塊時(shí)才進(jìn)行的。優(yōu)點(diǎn)是便于修改和更新，便于實(shí)現(xiàn)對(duì)目標(biāo)模塊的共享。

內(nèi)存的裝入模塊在裝入內(nèi)存時(shí)，同樣有三種方式。

1）絕對(duì)裝入。 在編譯時(shí)，若知道程序?qū)Ⅰv留在內(nèi)存中的某個(gè)位置，則編譯程序?qū)a(chǎn)生絕地地址的目標(biāo)代碼。 絕對(duì)裝入程序按照裝入模塊中的地址，將程序和數(shù)據(jù)裝入內(nèi)存。 由于程序中的邏輯地址與實(shí)際內(nèi)存地址完全相同，因此不需要對(duì)程序和數(shù)據(jù)的地址進(jìn)行修改。

絕對(duì)裝入方式只適用于單道程序設(shè)計(jì)。另外，程序中所用的絕對(duì)地址，可在編譯或匯編時(shí)給出，也可以由程序員直接賦予。而通常情況下在程序中采用的是符號(hào)地址，編譯或匯編時(shí)再轉(zhuǎn)換為絕對(duì)地址。

2）可重定位裝入。在多道程序設(shè)計(jì)下，多個(gè)目標(biāo)模塊的起始地址（簡(jiǎn)稱始址）通常都是從0開(kāi)始，程序中的其他地址都是相對(duì)于始址的，此時(shí)應(yīng)采用可重定位裝入方式。 根據(jù)內(nèi)存的當(dāng)前情況，將裝入模塊裝入內(nèi)存的適當(dāng)位置。裝入時(shí)對(duì)目標(biāo)程序中指令和數(shù)據(jù)的修改過(guò)程稱為重定位。地址變換通常是在裝入時(shí)一次完成的，所以又稱靜態(tài)重定位。

靜態(tài)重定位的特點(diǎn)是，一個(gè)作業(yè)裝入內(nèi)存中，必須給它分配要求的全部?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í)裝入，也稱動(dòng)態(tài)重定位。 程序在內(nèi)存中若發(fā)生移動(dòng)，則需要采用動(dòng)態(tài)的裝入方式。裝入程序把裝入模塊裝入內(nèi)存后，并不立即把裝入模塊中的相對(duì)地址轉(zhuǎn)換為絕對(duì)地址，而是把這種地址轉(zhuǎn)換過(guò)程推遲到程序真正需要執(zhí)行時(shí)進(jìn)行。因此，裝入內(nèi)存后的所有地址均為相對(duì)地址。這種方式需要一個(gè)重定位寄存器。

重定位寄存器存放裝入模塊的起始內(nèi)存地址。

動(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ǔ)空間大得多的地址空間。

2 邏輯地址空間與物理地址空間

編譯后，每個(gè)目標(biāo)模塊都從0號(hào)單元開(kāi)始編址，這稱為該目標(biāo)模塊的相對(duì)地址（或邏輯地址）。當(dāng)鏈接程序?qū)⒏鱾€(gè)模塊鏈接成一個(gè)完整的可執(zhí)行目標(biāo)程序時(shí)，鏈接程序順序依次按照各個(gè)模塊的相對(duì)地址構(gòu)成統(tǒng)一的從0號(hào)單元地址開(kāi)始的邏輯地址空間，用戶程序和程序員只需要知道邏輯地址，而內(nèi)存管理的具體機(jī)制則是完全透明的，只有系統(tǒng)編程人員才會(huì)涉及內(nèi)存管理的具體機(jī)制。 不同進(jìn)程可以擁有相同的邏輯地址， 因?yàn)檫@些相同的邏輯地址可以映射到主存的不同位置。

物理地址空間是指內(nèi)存中物理單元的集合，它是地址轉(zhuǎn)換的最終地址，進(jìn)程在運(yùn)行時(shí)執(zhí)行指令和訪問(wèn)數(shù)據(jù)，最后都要通過(guò)物理地址從主存中存取。 當(dāng)裝入程序?qū)⒖蓤?zhí)行代碼裝入內(nèi)存時(shí)，必須通過(guò)地址轉(zhuǎn)換將邏輯地址轉(zhuǎn)換為物理地址， 這個(gè)過(guò)程稱為地址重定位。

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

內(nèi)存分配前，需要保護(hù)操作系統(tǒng)不受用戶進(jìn)程的影響，同時(shí)保護(hù)用戶進(jìn)程不受其他用戶進(jìn)程的影響。內(nèi)存保護(hù)可以采取兩種方法：

1） 在CPU中設(shè)置一對(duì)上下限寄存器，存放用戶作業(yè)在主存中的下限和上限地址，每當(dāng)CPU要訪問(wèn)一個(gè)地址時(shí)，分別和兩個(gè)寄存器相比，判斷有無(wú)越界。

2） 采用重定位寄存器（或稱為基址寄存器） 和界地址寄存器（又稱限長(zhǎng)寄存器）來(lái)實(shí)現(xiàn)這種保護(hù)。 重定位寄存器含最小的物理地址值，界地址寄存器含邏輯地址的最大值。 每個(gè)邏輯地址值必須小于界地址寄存器；

內(nèi)存管理機(jī)構(gòu)動(dòng)態(tài)地將邏輯地址與界地址寄存器比較，若未發(fā)生地址越界，則加上重定位寄存器的值后映射成物理地址，再送交到內(nèi)存單元。

3.1.2 覆蓋與交換

覆蓋與交換技術(shù)是在多道程序環(huán)境中用來(lái)擴(kuò)充內(nèi)存的兩種方法。

1 覆蓋

早期的計(jì)算機(jī)系統(tǒng)中，主存容量很小，雖然主存中僅僅存放一道用戶程序，但存儲(chǔ)空間放不下用戶進(jìn)程的現(xiàn)象也時(shí)有發(fā)生，這一矛盾可以使用覆蓋技術(shù)來(lái)解決。

覆蓋的基本思想：將程序分為多個(gè)段，常用的段常駐內(nèi)存，不常用的段在需要時(shí)調(diào)入內(nèi)存。

把用戶空間分為一個(gè)固定區(qū)和若干覆蓋區(qū)。

2 交換

交換的基本思想：把處于等待狀態(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ò)程稱為換入。

交換技術(shù)主要用在不同進(jìn)程（或者作業(yè)）之間，而覆蓋則用于同一程序或進(jìn)程中。由于覆蓋技術(shù)要求給出程序段之間的覆蓋結(jié)構(gòu)，使得其對(duì)用戶和程序員不透明，所以對(duì)于主存無(wú)法存放用戶程序的矛盾， 現(xiàn)代操作系統(tǒng)是通過(guò)虛擬內(nèi)存技術(shù)來(lái)解決的，覆蓋技術(shù)則已經(jīng)成為歷史。

3.1.3 連續(xù)分配管理方式

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

1 單一連續(xù)分配

內(nèi)存在該種方式下分為系統(tǒng)區(qū)和用戶區(qū)。系統(tǒng)區(qū)僅供操作系統(tǒng)使用，通常在低地址部分；用戶區(qū)是為用戶提供的、除系統(tǒng)區(qū)外的內(nèi)存空間。

這種方式無(wú)需進(jìn)行內(nèi)存保護(hù)。因?yàn)閮?nèi)存中永遠(yuǎn)只有一道程序，因此肯定不會(huì)因?yàn)樵L問(wèn)越界而干擾其他程序。

這種方式的優(yōu)點(diǎn)：簡(jiǎn)單、無(wú)外部碎片，可以采用覆蓋技術(shù)，不需要額外的技術(shù)支持。

缺點(diǎn)：只能用于單用戶、單任務(wù)的操作系統(tǒng)，有內(nèi)部碎片，存儲(chǔ)器的利用率極低。

2 固定分區(qū)分配

固定分區(qū)分配是最簡(jiǎn)單的一種多道程序存儲(chǔ)管理方式，它將用戶內(nèi)存空間劃分為若干固定大小的區(qū)域，每個(gè)分區(qū)只裝入一道作業(yè)。當(dāng)有空閑分區(qū)時(shí)，便可再?gòu)耐獯娴暮髠渥鳂I(yè)隊(duì)列中選擇適當(dāng)大小的作業(yè)裝入該分區(qū)，如此循環(huán)。

固定分區(qū)分配在劃分分區(qū)時(shí)有兩種不同的方法。

• 分區(qū)大小相等。用于利用一臺(tái)計(jì)算機(jī)去控制多個(gè)相同對(duì)象的場(chǎng)合，缺乏靈活性。
• 分區(qū)大小不等。 劃分為多個(gè)較小的分區(qū)、適量的中等分區(qū)和少量大分區(qū)。

為了便于內(nèi)存分配，通常將分區(qū)按照大小排隊(duì)，并為之建立一張分區(qū)說(shuō)明表，其中各表項(xiàng)包括每個(gè)分區(qū)的始址、大小及狀態(tài)（是否已分配）。當(dāng)有用戶程序要裝入時(shí)，便檢索該表，以找到合適的分區(qū)給予分配并將其狀態(tài)置為“已分配”； 未找到合適分區(qū)時(shí)，則拒絕為該用戶程序分配內(nèi)存。

這種分區(qū)方式存在兩個(gè)問(wèn)題：

1）程序可能太大而放不進(jìn)任何一個(gè)分區(qū)中，這時(shí)用戶不得不使用覆蓋技術(shù)（常用的段常駐內(nèi)存，不常用的段在需要時(shí)調(diào)入內(nèi)存）來(lái)使用內(nèi)存空間。

2）主存利用率低，當(dāng)程序小于固定分區(qū)大小時(shí)，也占用一個(gè)完整的內(nèi)存分區(qū)空間，這樣分區(qū)內(nèi)部就存在空間浪費(fèi)，這種現(xiàn)象稱為內(nèi)部碎片。

固定分區(qū)是可用于多道程序設(shè)計(jì)的最簡(jiǎn)單的存儲(chǔ)分配，無(wú)外部碎片，但不能實(shí)現(xiàn)多進(jìn)程共享一個(gè)主存區(qū)，所以存儲(chǔ)空間利用率低。 固定分區(qū)分配很少用于現(xiàn)在通用的操作系統(tǒng)中，但在某些用于控制多個(gè)相同對(duì)象的控制系統(tǒng)中仍發(fā)揮著一定的作用。

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

動(dòng)態(tài)分區(qū)分配又稱可變分區(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ù)目是可變的。

動(dòng)態(tài)分區(qū)在開(kāi)始分配時(shí)是很好的，但之后會(huì)導(dǎo)致內(nèi)存中出現(xiàn)許多小的內(nèi)存塊。 隨著時(shí)間的推移，內(nèi)存中會(huì)產(chǎn)生越來(lái)越多的碎片，內(nèi)存的利用率隨之下降。這些小的內(nèi)存塊稱為外部碎片，指在所有分區(qū)外的存儲(chǔ)空間會(huì)變成越來(lái)越多的碎片，這些與固定分區(qū)中的內(nèi)部碎片正好相對(duì)。

克服外部碎片可以通過(guò)緊湊（compaction）技術(shù)來(lái)解決，即操作系統(tǒng)不時(shí)地對(duì)進(jìn)程進(jìn)行移動(dòng)和整理。但這需要?jiǎng)討B(tài)重定位寄存器的支持，且相對(duì)費(fèi)時(shí)。 緊湊的過(guò)程類似于Windows系統(tǒng)中的磁盤整理程序，只不過(guò)后者是對(duì)外存空間的緊湊。

3.1.4 非連續(xù)分配管理方式

非連續(xù)分配允許一個(gè)程序分散地裝入不相鄰的內(nèi)存分區(qū)。在連續(xù)分配管理方式中，我們發(fā)現(xiàn)，即使內(nèi)存中有超過(guò)1GB的空閑空間，但若沒(méi)有連續(xù)的1GB空間，則需要1GB空間的作業(yè)仍然無(wú)法運(yùn)行。 但若采用非連續(xù)分配管理方式，則作業(yè)所要求的1GB內(nèi)存空間可以分散地分配在內(nèi)存的各個(gè)區(qū)域，當(dāng)然，這也需要額外的空間去存儲(chǔ)它們(分散區(qū)域)的索引， 使得非連續(xù)分配方式的存儲(chǔ)密度低于連續(xù)存儲(chǔ)方式的。

非連續(xù)存儲(chǔ)方式根據(jù)分區(qū)的大小是否固定，分為分頁(yè)存儲(chǔ)管理方式和分段存儲(chǔ)管理方式。

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

1 基本分頁(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ì)的區(qū)別： 塊的大小相對(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ō)也是很小的，每個(gè)進(jìn)程平均產(chǎn)生半個(gè)塊大小的內(nèi)部碎片（也稱業(yè)內(nèi)碎片）。

（1）分頁(yè)存儲(chǔ)的幾個(gè)基本概念

1）頁(yè)面和頁(yè)面大小。

將內(nèi)存空間分為一個(gè)個(gè)大小相等的分區(qū)（比如每個(gè)分區(qū)4KB），每個(gè)分區(qū)就是一個(gè)“頁(yè)框”。每個(gè)頁(yè)框有一個(gè)編號(hào)，即頁(yè)框號(hào)，頁(yè)框號(hào)從0開(kāi)始。

注：$頁(yè)框=頁(yè)幀=內(nèi)存塊=物理塊=物理頁(yè)面$
頁(yè)框號(hào)=頁(yè)幀號(hào)=內(nèi)存塊號(hào)=物理塊號(hào)=物理頁(yè)號(hào)

將進(jìn)程的邏輯地址空間也分為與頁(yè)框大小相等的一個(gè)個(gè)部分，每個(gè)部分稱為一個(gè)“頁(yè)”或者“頁(yè)面”。每個(gè)頁(yè)面也有一個(gè)編號(hào)，叫做頁(yè)號(hào)，頁(yè)號(hào)也是從0開(kāi)始編號(hào)。

2）邏輯地址結(jié)構(gòu)
\color{red}{}
$邏輯地址結(jié)構(gòu)=頁(yè)號(hào)P+頁(yè)內(nèi)偏移量W$

注意，地址結(jié)構(gòu)決定了虛擬內(nèi)存的尋址空間有多大。在實(shí)際問(wèn)題中，頁(yè)號(hào)、頁(yè)內(nèi)偏移、邏輯地址大都是用十進(jìn)制給出的。

3）頁(yè)表

為了便于在內(nèi)存中找到進(jìn)程的每個(gè)頁(yè)面所對(duì)應(yīng)的物理塊，系統(tǒng)為每個(gè)進(jìn)程建立一張頁(yè)表，頁(yè)表記錄頁(yè)面在內(nèi)存中對(duì)應(yīng)的物理塊號(hào)，頁(yè)表一般存放在內(nèi)存中。

頁(yè)表是由頁(yè)表項(xiàng)組成的.

$頁(yè)表項(xiàng)=頁(yè)號(hào)+內(nèi)存塊號(hào)$

頁(yè)表的作用：實(shí)現(xiàn)頁(yè)號(hào)到物理塊號(hào)的地址映射。

操作系統(tǒng)以頁(yè)框?yàn)閱挝?/strong>為各個(gè)進(jìn)程分配內(nèi)存空間，進(jìn)程的每個(gè)頁(yè)面分別放入一個(gè)頁(yè)框中。也就是說(shuō)，進(jìn)程的頁(yè)面和內(nèi)存的頁(yè)框有一一對(duì)應(yīng)的關(guān)系。

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

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

設(shè)頁(yè)面大小為L(zhǎng),邏輯地址A到物理地址E的變換過(guò)程如下圖（邏輯地址、頁(yè)號(hào)、每頁(yè)的長(zhǎng)度都是十進(jìn)制給出的）

地址變換機(jī)構(gòu)的地址變換過(guò)程：

根據(jù)邏輯地址算出頁(yè)號(hào)和頁(yè)內(nèi)偏移量

檢查頁(yè)號(hào)是否越界

查詢頁(yè)表（根據(jù)頁(yè)表始址+頁(yè)號(hào)），找到相應(yīng)的頁(yè)表項(xiàng)，確定頁(yè)面存放的內(nèi)存塊號(hào)

用內(nèi)存塊號(hào)和頁(yè)內(nèi)偏移量計(jì)算出物理地址

在系統(tǒng)中通常設(shè)置一個(gè)頁(yè)表寄存器（PTR），存放頁(yè)表在內(nèi)存的起始地址F和頁(yè)表長(zhǎng)度M。 進(jìn)程未執(zhí)行時(shí)，頁(yè)表的始址和長(zhǎng)度存放在進(jìn)程控制塊PCB（在系統(tǒng)區(qū)中）中，當(dāng)進(jìn)程執(zhí)行時(shí)，才將頁(yè)表始址和長(zhǎng)度存入頁(yè)表寄存器。

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

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

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

在有快表的分頁(yè)機(jī)制中，地址轉(zhuǎn)換的過(guò)程如下所示：

CPU給出邏輯地址后，由硬件進(jìn)行地址轉(zhuǎn)換，將頁(yè)號(hào)送入cache，并將此頁(yè)號(hào)與快表中的所有頁(yè)號(hào)進(jìn)行比較。

若找到匹配的頁(yè)號(hào)，說(shuō)明所要訪問(wèn)的頁(yè)表項(xiàng)在快表中，則直接從中取出該頁(yè)對(duì)應(yīng)的頁(yè)框號(hào)（內(nèi)存塊號(hào)），與頁(yè)內(nèi)偏移量拼接形成物理地址。 這樣，存取數(shù)據(jù)僅一次訪存便可以實(shí)現(xiàn)。

若未找到匹配的頁(yè)號(hào)，則需要訪問(wèn)主存中的頁(yè)表，在讀出頁(yè)表項(xiàng)后，應(yīng)同時(shí)將其存入快表，以便后面可能的再次訪問(wèn)。但若快表已滿，需要按照一定的算法對(duì)舊的頁(yè)表項(xiàng)進(jìn)行替換。

注意：有些處理機(jī)設(shè)計(jì)為快表和慢表同時(shí)查找，若在快表中查找成功則終止慢表的查找。

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

（4）兩級(jí)頁(yè)表

單級(jí)頁(yè)表存在的問(wèn)題
問(wèn)題一：頁(yè)表必須連續(xù)存放，因此當(dāng)頁(yè)表很大時(shí)，需要占用很多個(gè)連續(xù)的物理內(nèi)存塊（頁(yè)框）。

問(wèn)題二：沒(méi)有必要讓整個(gè)頁(yè)表常駐內(nèi)存，因?yàn)檫M(jìn)程在一段時(shí)間內(nèi)可能只訪問(wèn)幾個(gè)特定的頁(yè)面。

二級(jí)頁(yè)表就是在原有頁(yè)表結(jié)構(gòu)上再加上一層頁(yè)表。

如何實(shí)現(xiàn)地址轉(zhuǎn)換？

1按照地址結(jié)構(gòu)將邏輯地址拆分為3部分

2從PCB中讀出頁(yè)目錄表始址，根據(jù)一級(jí)頁(yè)號(hào)查頁(yè)目錄表，找到下一級(jí)頁(yè)表在內(nèi)存中的位置

3根據(jù)二級(jí)頁(yè)號(hào)查表，找到最終想訪問(wèn)的內(nèi)存號(hào)

4結(jié)合頁(yè)內(nèi)偏移量得到物理地址

需要注意的幾個(gè)細(xì)節(jié)：

1 采用多級(jí)頁(yè)表機(jī)制，則各級(jí)頁(yè)表的大小不能超過(guò)一個(gè)頁(yè)面。

2 兩級(jí)頁(yè)表的訪存次數(shù)分析（假設(shè)沒(méi)有快表機(jī)構(gòu)）

第一次訪存：訪問(wèn)內(nèi)存中的頁(yè)目錄表；
第二次訪存：訪問(wèn)內(nèi)存中的二級(jí)頁(yè)表；
第三次訪存：訪問(wèn)目標(biāo)內(nèi)存單元；

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

分頁(yè)管理方式是從計(jì)算機(jī)的角度設(shè)計(jì)的，目的是提高內(nèi)存的利用率，提高計(jì)算機(jī)的性能。分頁(yè)通過(guò)硬件機(jī)制實(shí)現(xiàn)，對(duì)用戶完全透明。

分段管理方式是從用戶和程序員的角度出發(fā)的，以滿足方便編程、信息保護(hù)和共享、動(dòng)態(tài)增長(zhǎng)及動(dòng)態(tài)鏈接等多方面的需要。

1）分段。 段式管理方式按照用戶進(jìn)程中的自然段劃分邏輯空間。

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

段號(hào)的位數(shù)：決定了每個(gè)進(jìn)程最多可分為多少段。

段內(nèi)地址的位數(shù)：決定了每個(gè)段的最大長(zhǎng)度是多少。

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

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

配置段表后，執(zhí)行中的進(jìn)程可通過(guò)查找段表，找到每段對(duì)應(yīng)的內(nèi)存區(qū)。 可見(jiàn)，段表用于實(shí)現(xiàn)從邏輯段到物理內(nèi)存區(qū)的映射。

3）地址變換機(jī)構(gòu)。

為了實(shí)現(xiàn)進(jìn)程從邏輯地址到物理地址的變換功能，在系統(tǒng)中設(shè)置了段表寄存器，用于存放段表始址F和段表長(zhǎng)度M。

從邏輯地址A到實(shí)際物理地址E的地址轉(zhuǎn)換如下：

1.根據(jù)邏輯地址得到段號(hào)S和段內(nèi)地址W（即段內(nèi)偏移量）
2.判斷段號(hào)是否越界。如果S≥M，則產(chǎn)生越界中斷，否則繼續(xù)執(zhí)行。
3.查詢段表，找到對(duì)應(yīng)的段表項(xiàng)，段表項(xiàng)的存放地址為F+S?段表項(xiàng)長(zhǎng)度。
4.檢查段內(nèi)地址是否超過(guò)段長(zhǎng)（和頁(yè)式管理不同）。如果W≥C（段內(nèi)地址≥段長(zhǎng)），則產(chǎn)生越界中斷，否則繼續(xù)執(zhí)行。
5段基址b+段內(nèi)地址W=實(shí)際物理地址。
6.訪問(wèn)目標(biāo)內(nèi)存單元。

4）段的共享與保護(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ù)。不能修改的代碼稱為純代碼或可重入代碼（它不屬于臨界資源），這樣不能修改的代碼或數(shù)據(jù)可以共享，而可修改的代碼或數(shù)據(jù)不能共享。

分段管理方式的保護(hù)主要有兩種：一種是存儲(chǔ)控制保護(hù)，另一種是地址越界保護(hù)。

分段管理的地址空間是二維的，因?yàn)槎翁?hào)和段內(nèi)地址（即段內(nèi)偏移量）必須要顯式給出（段號(hào)，段內(nèi)偏移）。

3 段頁(yè)式管理方式

優(yōu)點(diǎn)缺點(diǎn)

分頁(yè)管理	內(nèi)存空間利用率高，不會(huì)產(chǎn)生外部碎片，只會(huì)有少量?jī)?nèi)部碎片	不方便按照邏輯模塊實(shí)現(xiàn)信息的共享和保護(hù)
分段管理	很方便按照邏輯模塊實(shí)現(xiàn)信息的共享和保護(hù)	如果段長(zhǎng)過(guò)大，為其分配很大的連續(xù)的內(nèi)存空間不方便。另外，段式會(huì)產(chǎn)生外部碎片。

盡管段式管理的外部碎片可以通過(guò)緊縮技術(shù)來(lái)處理，但是需要付出較大的時(shí)間代價(jià)。

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

在段頁(yè)式系統(tǒng)中，作業(yè)的邏輯地址分為三部分：段號(hào)、頁(yè)號(hào)和業(yè)內(nèi)偏移量。

為了實(shí)現(xiàn)地址轉(zhuǎn)換，系統(tǒng)為每個(gè)進(jìn)程建立一張段表，每個(gè)分段有一張頁(yè)表。段表表項(xiàng)中至少包含段號(hào)、頁(yè)表長(zhǎng)度和頁(yè)表始址，頁(yè)表表項(xiàng)中至少包括頁(yè)號(hào)和塊號(hào)。此外，系統(tǒng)還應(yīng)有一個(gè)段表寄存器，指出作業(yè)的段表長(zhǎng)度和段表始址。

注意：在一個(gè)進(jìn)程中，段表只有一個(gè)，而頁(yè)表可能有多個(gè)。

在進(jìn)行地址轉(zhuǎn)換時(shí)，首先通過(guò)段表查到頁(yè)表始址，然后通過(guò)頁(yè)表找到頁(yè)框號(hào)，最后形成物理地址。

由邏輯地址得到段號(hào)、頁(yè)號(hào)、頁(yè)內(nèi)偏移量
2.段號(hào)和段表寄存器的段長(zhǎng)比較，檢查是否越界
3.由段表始址和段號(hào)找到對(duì)應(yīng)的段表項(xiàng)
4.根據(jù)段表中頁(yè)表長(zhǎng)度，檢查頁(yè)號(hào)是否越界
5.根據(jù)段表項(xiàng)中記錄的頁(yè)表始址和頁(yè)號(hào)查詢頁(yè)表，得到相應(yīng)的頁(yè)表項(xiàng)
6.由頁(yè)表項(xiàng)記錄的塊號(hào)和頁(yè)內(nèi)偏移量得到物理地址
7.訪問(wèn)目標(biāo)單元

段頁(yè)式進(jìn)行查找一次邏輯地址需要三次訪存（分別是查段表，查頁(yè)表，訪問(wèn)實(shí)際內(nèi)存）。這里同樣可以使用快表進(jìn)行加速。

程序員需要顯示地給出（段號(hào)，段內(nèi)地址），而各段進(jìn)行“分頁(yè)”對(duì)程序員是不可見(jiàn)的。 系統(tǒng)會(huì)根據(jù)段內(nèi)地址自動(dòng)劃分為頁(yè)號(hào)和頁(yè)內(nèi)偏移量。所以段頁(yè)式管理的地址空間是二維的。

王道習(xí)題（二級(jí)頁(yè)表）

答案：B 128
分析 ：在二級(jí)頁(yè)表中，一頁(yè)可以存放的頁(yè)表項(xiàng)個(gè)數(shù)=$2^{10}/2=2^9個(gè)頁(yè)表項(xiàng)$，邏輯地址空間需要$2^{16}$個(gè)頁(yè)表項(xiàng)，則總共需要$2^{16}/2^9=2^7=128$個(gè)頁(yè)面，二級(jí)頁(yè)表供128個(gè)頁(yè)面，則一級(jí)頁(yè)表(又稱頁(yè)目錄表)有128個(gè)表項(xiàng)。

本題選A
只需要將虛擬地址寫成二進(jìn)制形式，并且分塊即可。

3.2虛擬內(nèi)存管理

3.2.1 虛擬內(nèi)存的基本概念

傳統(tǒng)存儲(chǔ)管理方式的特征

前面討論的各種內(nèi)存管理策略是為了同時(shí)將多個(gè)進(jìn)程保存在內(nèi)存中，以便允許多道程序設(shè)計(jì)。 它們都具有以下兩個(gè)共同的特征：

1）一次性。作業(yè)必須一次性全部裝入內(nèi)存，才能開(kāi)始運(yùn)行。

2）駐留性。作業(yè)被裝入內(nèi)存后，就一直駐留在內(nèi)存中，其任何部分都不會(huì)被換出，直到作業(yè)運(yùn)行結(jié)束。運(yùn)行中的進(jìn)程會(huì)因等待I/O而被阻塞，可能處于長(zhǎng)期等待狀態(tài)。

2 局部性原理

局部性原理表現(xiàn)在以下兩個(gè)方面：
1）時(shí)間局部性。 程序中的某條指令一旦執(zhí)行，不久后該指令可能再次執(zhí)行；某數(shù)據(jù)被訪問(wèn)過(guò)，不久后該數(shù)據(jù)可能再次被訪問(wèn)。 產(chǎn)生時(shí)間局部性的典型原因是程序中存在著大量的循環(huán)操作。

2）空間局部性。 一旦程序訪問(wèn)了某個(gè)存儲(chǔ)單元，在不久后，其附近的存儲(chǔ)單元也將被訪問(wèn)，即程序在一段時(shí)間內(nèi)所訪問(wèn)的地址，可能集中在一定的范圍內(nèi)，因?yàn)?strong>指令通常是順序存放、順序執(zhí)行的，數(shù)據(jù)也一般是以向量、數(shù)組、表等形式簇聚存儲(chǔ)的。

時(shí)間局部性通過(guò)將近來(lái)使用的指令和數(shù)據(jù)保存到高速緩存中，并使用高速緩存的層次結(jié)構(gòu)實(shí)現(xiàn)。

空間局部性通常使用較大的高速緩存， 并將預(yù)取機(jī)制集成到高速緩存控制邏輯中實(shí)現(xiàn)。

虛擬內(nèi)存技術(shù)實(shí)際上建立了“內(nèi)存-外存”的兩級(jí)存儲(chǔ)器結(jié)構(gòu)， 利用局部性原理實(shí)現(xiàn)高速緩存。

3 虛擬存儲(chǔ)器的定義和特征

基于局部性原理，在程序裝入時(shí)，將程序的一部分裝入內(nèi)存，而將其余部分留在外存，就可啟動(dòng)程序執(zhí)行。 在程序執(zhí)行過(guò)程中，當(dāng)所訪問(wèn)的信息不在內(nèi)存時(shí)，由操作系統(tǒng)將所需要的部分調(diào)入內(nèi)存，然后繼續(xù)執(zhí)行程序。另一方面，操作系統(tǒng)將內(nèi)存中暫時(shí)不使用的內(nèi)容換出到外存上，從而騰出空間存放將要調(diào)入內(nèi)存的信息。 這樣，操作系統(tǒng)好像為用戶提供了一個(gè)比實(shí)際內(nèi)存大得多的存儲(chǔ)器，稱為虛擬存儲(chǔ)器。

之所以將其稱為虛擬存儲(chǔ)器，是因?yàn)檫@種存儲(chǔ)器實(shí)際上并不存在，只是由于系統(tǒng)提供了部分裝入、請(qǐng)求調(diào)入和置換功能后（對(duì)用戶完全透明），給用戶的感覺(jué)是好像存在一個(gè)比實(shí)際物理內(nèi)存大得多的存儲(chǔ)器。 虛擬存儲(chǔ)器的大小由計(jì)算機(jī)的地址結(jié)構(gòu)決定， 并不是內(nèi)存和外存的簡(jiǎn)單相加。

虛擬存儲(chǔ)器具有以下三個(gè)主要特征：

1）多次性。 多次性是指無(wú)需在作業(yè)運(yùn)行時(shí)一次性地全部裝入內(nèi)存，而允許被分成多次調(diào)入內(nèi)存運(yùn)行。

2）對(duì)換性。 對(duì)換性是指無(wú)需在作業(yè)運(yùn)行時(shí)一直常駐內(nèi)存，而允許在作業(yè)的運(yùn)行過(guò)程中，進(jìn)行換出和換入。

3）虛擬性。 虛擬性是指從邏輯上擴(kuò)充內(nèi)存的容量， 使用戶看到的內(nèi)存容量遠(yuǎn)大于實(shí)際的內(nèi)存容量。

4 虛擬內(nèi)存技術(shù)的實(shí)現(xiàn)

虛擬內(nèi)存技術(shù)允許將一個(gè)作業(yè)分多次調(diào)入內(nèi)存。采用連續(xù)分配方式時(shí)，會(huì)使相當(dāng)一部分內(nèi)存空間都處于暫時(shí)或“永久”空閑狀態(tài)，造成內(nèi)存資源的嚴(yán)重浪費(fèi)，而且也無(wú)法從邏輯上擴(kuò)大內(nèi)存容量。因此，虛擬內(nèi)存的實(shí)現(xiàn)需要建立在離散分配的內(nèi)存管理方式的基礎(chǔ)上。

虛擬內(nèi)存的實(shí)現(xiàn)有以下三種方式：

• 請(qǐng)求分頁(yè)存儲(chǔ)管理
• 請(qǐng)求分段存儲(chǔ)管理
• 請(qǐng)求段頁(yè)式存儲(chǔ)管理

不管哪一種實(shí)現(xiàn)方式，都需要一定的硬件支持。 一般需要的支持有以下幾個(gè)方面：

1一定容量的內(nèi)存和外存。
2頁(yè)表機(jī)制（或段表機(jī)制)，作為主要的數(shù)據(jù)結(jié)構(gòu)。

3 中斷機(jī)構(gòu)，當(dāng)用戶程序要訪問(wèn)的部分尚未調(diào)入內(nèi)存時(shí)，則產(chǎn)生中斷。
4地址變換機(jī)構(gòu)，邏輯地址到物理地址的變換。

3.2.2 請(qǐng)求分頁(yè)管理方式

請(qǐng)求分頁(yè)系統(tǒng)建立在基本分頁(yè)系統(tǒng)基礎(chǔ)之上，為了支持虛擬存儲(chǔ)器功能而增加了請(qǐng)求調(diào)頁(yè)功能和頁(yè)面置換功能。請(qǐng)求分頁(yè)使目前最常用的一種實(shí)現(xiàn)虛擬存儲(chǔ)器的方法。

再請(qǐng)求分頁(yè)系統(tǒng)中，只要求將當(dāng)前需要的一部分頁(yè)面裝入內(nèi)存，便可以啟動(dòng)作業(yè)。 在作業(yè)執(zhí)行過(guò)程中，當(dāng)所訪問(wèn)的頁(yè)面不在內(nèi)存中時(shí)，再通過(guò)調(diào)頁(yè)功能將其調(diào)入，同時(shí)還可以通過(guò)置換功能將暫時(shí)不用的頁(yè)面換出到外存上，以便騰出內(nèi)存空間。

1 頁(yè)表機(jī)制

請(qǐng)求分頁(yè)系統(tǒng)的頁(yè)表機(jī)制不同于基本分頁(yè)系統(tǒng)，請(qǐng)求分頁(yè)系統(tǒng)在一個(gè)作業(yè)運(yùn)行之前不要求全部一次性調(diào)入內(nèi)存，因此在作業(yè)運(yùn)行過(guò)程中，必然會(huì)存在要訪問(wèn)的頁(yè)面不在內(nèi)存中的情況，如何發(fā)現(xiàn)和處理這種情況是請(qǐng)求分頁(yè)系統(tǒng)必須解決的兩個(gè)基本問(wèn)題。 為此，在請(qǐng)求頁(yè)表項(xiàng)中增加了4個(gè)字段。

增加的4個(gè)字段說(shuō)明如下：

狀態(tài)位P。用于指示該頁(yè)是否已經(jīng)調(diào)入內(nèi)存。供程序訪問(wèn)時(shí)參考。

訪問(wèn)字段A。 用于記錄本頁(yè)在一段時(shí)間內(nèi)被訪問(wèn)的次數(shù)，或記錄本頁(yè)最近已有多長(zhǎng)時(shí)間未被訪問(wèn)，共置換算法換出頁(yè)面時(shí)參考。

修改位M。 標(biāo)識(shí)該頁(yè)在調(diào)入內(nèi)存后是否被修改過(guò)。

外存地址。 用于指出該頁(yè)在外存上的地址，通常是物理塊號(hào)，供調(diào)入該頁(yè)時(shí)參考。

2 缺頁(yè)中斷機(jī)構(gòu)

在請(qǐng)求分頁(yè)系統(tǒng)中，每當(dāng)所要訪問(wèn)的頁(yè)面不在內(nèi)存時(shí)，便產(chǎn)生一個(gè)缺頁(yè)中斷，請(qǐng)求操作系統(tǒng)將所缺的頁(yè)調(diào)入內(nèi)存。此時(shí)應(yīng)將缺頁(yè)的進(jìn)程阻塞（調(diào)頁(yè)完成喚醒），若內(nèi)存中有空閑塊，則分配一個(gè)塊，將要調(diào)入的頁(yè)裝入該塊，并修改頁(yè)表中的相應(yīng)頁(yè)表項(xiàng)，若此時(shí)內(nèi)存中沒(méi)有空閑塊，則要淘汰某頁(yè)（若被淘汰頁(yè)在內(nèi)存期間被修改過(guò)，則要將其寫回外存）。

缺頁(yè)中斷作為中斷，同樣要經(jīng)歷諸如保護(hù)CPU環(huán)境、分析中斷原因、轉(zhuǎn)入缺頁(yè)中斷處理程序、恢復(fù)CPU環(huán)境等幾個(gè)步驟。 但是和一般的中斷相比，有兩個(gè)明顯的區(qū)別：

• 1.在指令執(zhí)行期間而非一條指令執(zhí)行完后產(chǎn)生和處理中斷信號(hào)，屬于內(nèi)部中斷。
• 2.一條指令在執(zhí)行期間，可能產(chǎn)生多次中斷。

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

在地址變換時(shí)，先檢索快表：
如果找到要訪問(wèn)的頁(yè)，則修改頁(yè)表項(xiàng)中的訪問(wèn)位（寫指令還需要重置修改位），然后利用頁(yè)表項(xiàng)中給出的物理塊號(hào)和頁(yè)內(nèi)地址形成物理地址。

如果沒(méi)有找到該頁(yè)的頁(yè)表項(xiàng)，則應(yīng)到內(nèi)存中去查找頁(yè)表，再對(duì)比頁(yè)表項(xiàng)中的狀態(tài)位P，看是否已經(jīng)調(diào)入內(nèi)存，未調(diào)入則產(chǎn)生缺頁(yè)中斷，請(qǐng)求從外存把該頁(yè)調(diào)入內(nèi)存。

3.2.3 頁(yè)面置換算法

1. 最佳（OPT）置換算法

最佳(OPT,optimal)置換算法選擇的被淘汰頁(yè)面是以后永不使用的頁(yè)面，或是在最長(zhǎng)時(shí)間內(nèi)不再被訪問(wèn)的頁(yè)面，以便保證獲得最低的缺頁(yè)率。

然而，由于人們目前無(wú)法預(yù)知進(jìn)程在內(nèi)存下的若干頁(yè)面中哪個(gè)是未來(lái)最長(zhǎng)時(shí)間內(nèi)不再被訪問(wèn)的，因而該算法無(wú)法被實(shí)現(xiàn)。

最佳置換算法可以用來(lái)評(píng)價(jià)其他算法。

2. 先進(jìn)先出（FIFO）置換算法

優(yōu)先淘汰最早進(jìn)入內(nèi)存的頁(yè)面，即在內(nèi)存中駐留時(shí)間最久的頁(yè)面。 該算法實(shí)現(xiàn)簡(jiǎn)單，只需要把調(diào)入內(nèi)存的頁(yè)面根據(jù)先后次序鏈接成隊(duì)列，設(shè)置一個(gè)指針總指向最早的頁(yè)面。 但該算法與進(jìn)程實(shí)際運(yùn)行時(shí)的規(guī)律不適應(yīng)加粗樣式，因?yàn)樵谶M(jìn)程中，有的頁(yè)面經(jīng)常被訪問(wèn)。

FIFO算法會(huì)產(chǎn)生所分配的物理塊數(shù)增大而頁(yè)故障數(shù)不減反增的異常現(xiàn)象，稱為Belady異常。只有FIFO算法可能出現(xiàn)Belady異常，LRU和OPT算法永遠(yuǎn)不會(huì)出現(xiàn)Belady異常。

3.最近最久未使用（LRU）置換算法

最近最久未使用（LRU，Leat Recently Used）置換算法選擇最近最長(zhǎng)時(shí)間未訪問(wèn)過(guò)的頁(yè)面予以淘汰，它認(rèn)為過(guò)去一段時(shí)間內(nèi)未訪問(wèn)過(guò)的頁(yè)面，在最近的將來(lái)可能亦不會(huì)被訪問(wèn)。 該算法為每個(gè)頁(yè)面設(shè)置一個(gè)訪問(wèn)字段，來(lái)記錄頁(yè)面自上次被訪問(wèn)以來(lái)所經(jīng)歷的時(shí)間，淘汰頁(yè)面時(shí)選擇現(xiàn)有頁(yè)面中值最大的予以淘汰。

LRU算法的性能較好，但需要寄存器和棧的硬件支持。LRU是堆棧類算法。理論上可以證明，堆棧類算法不可能出現(xiàn)Belady異常。

4. 時(shí)鐘（CLOCK）置換算法

LRU算法的性能接近于最佳置換算法，但是實(shí)現(xiàn)起來(lái)比較困難，且開(kāi)銷大；FIFO算法實(shí)現(xiàn)起來(lái)簡(jiǎn)單，但性能差。 因此，操作系統(tǒng)的設(shè)計(jì)者嘗試了很多算法，試圖用比較小的開(kāi)銷接近LRU算法的性能，這類算法都是CLOCK算法的變體。因?yàn)?strong>算法要循環(huán)掃描緩沖區(qū)，像時(shí)鐘的指針一樣轉(zhuǎn)動(dòng)，所以稱為CLOCK算法，又稱為最近未用（Not Recently Used，NRU）算法。

簡(jiǎn)單的CLOCK算法給每幀關(guān)聯(lián)一個(gè)附加位，稱為使用位。但某頁(yè)首次裝入內(nèi)存時(shí)，將該幀的使用位設(shè)置為1；當(dāng)該頁(yè)最后再被訪問(wèn)到時(shí)，其使用位也被置為1.對(duì)于頁(yè)替換算法，用于替換的候選幀集合可視為一個(gè)循環(huán)緩沖區(qū)，并有一個(gè)指針與之相關(guān)聯(lián)。 當(dāng)某一頁(yè)被替換時(shí)，該指針被設(shè)置為指向緩沖區(qū)的下一幀。 當(dāng)需要替換一頁(yè)時(shí)，操作系統(tǒng)掃描緩沖區(qū)，以查找使用位被置為0的一幀。 每當(dāng)遇到一個(gè)使用位為1的幀時(shí)，操作系統(tǒng)就將該位重新置為0. 若在這個(gè)過(guò)程開(kāi)始時(shí)，緩沖區(qū)中所有幀的使用位均為0，則選擇遇到的第一個(gè)幀替換，并停留在最初的位置上，替換該幀中的頁(yè)。

改進(jìn)型CLOCK置換算法

在使用位u的基礎(chǔ)上再增加一個(gè)修改位m，則得到改進(jìn)型CLOCK置換算法。

這樣每幀都處于以下四種情況之一

• 最近未被訪問(wèn)，也未被修改（0，0）
• 最近被訪問(wèn)，但未被修改（1，0）
• 最近未被訪問(wèn)，但被修改（0，1）
• 最近被訪問(wèn)，被修改（1，1）

算法執(zhí)行過(guò)程如下

1）從指針的當(dāng)前位置開(kāi)始，掃描幀緩沖區(qū)。在這次掃描過(guò)程中，對(duì)使用位不做任何修改，選擇遇到的第一個(gè)幀（0，0）進(jìn)行替換。

2） 若第一步失敗，則重新掃描，查找（0，1）的幀。選擇遇到的第一個(gè)這樣的幀用于替換。在這個(gè)掃描過(guò)程中，對(duì)每個(gè)跳過(guò)的幀，把它的使用位設(shè)置為0.
3）若第二步失敗， 則指針將回到它的最初位置，且集合中所有幀的使用位均為0.重復(fù)第一步，查找（0，0）幀，并且對(duì)使用位不做任何修改。

4）若第四步失敗，則重復(fù)第二步。查找（0，1）的幀。這個(gè)過(guò)程中需要對(duì)遇到的幀就行使用位設(shè)置0.

改進(jìn)型CLOCK優(yōu)于簡(jiǎn)單CLOCK算法的地方在于替換時(shí)首選沒(méi)有變化的頁(yè)。由于修改過(guò)的頁(yè)在替換之前必須寫回，因而這樣做會(huì)節(jié)省時(shí)間。

操作系統(tǒng)中任何優(yōu)化而有效的頁(yè)面置換算法都有一個(gè)原則，即盡可能保留曾經(jīng)使用過(guò)的頁(yè)面，而淘汰未使用過(guò)的頁(yè)面，認(rèn)為這樣可以在總體上減少換頁(yè)次數(shù)。CLOCK算法只考慮到是否被訪問(wèn)過(guò)，因此被訪問(wèn)過(guò)的當(dāng)然盡可能留下來(lái)，未使用過(guò)的就淘汰。 而改進(jìn)型CLOCK置換算法對(duì)任何使用過(guò)的頁(yè)面又做了細(xì)分，分為使用過(guò)但未修改過(guò)和使用過(guò)且修改過(guò)。因此，若有未使用過(guò)的頁(yè)面，實(shí)現(xiàn)把它換出，若全部頁(yè)面都使用過(guò)，優(yōu)先把未修改過(guò)的頁(yè)面換出。

3.2.4 頁(yè)面分配策略

頁(yè)面分配策略
駐留集 指請(qǐng)求分頁(yè)存儲(chǔ)管理中給一個(gè)進(jìn)程分配的內(nèi)存塊的集合。

固定分配vs 可變分配：區(qū)別在于進(jìn)程運(yùn)行期間駐留集大小是否可變
局部置換vs全局置換：區(qū)別在于發(fā)生缺頁(yè)時(shí)是否只能從進(jìn)程自己的頁(yè)面中選擇一個(gè)換出

固定分配局部置換：進(jìn)程運(yùn)行前就分配一定數(shù)量物理塊，缺頁(yè)時(shí)只能換出進(jìn)程自己的某一頁(yè)

可變分配全局置換:只要缺頁(yè)就分配新的物理塊，可能來(lái)自空閑物理塊，也可能換出別的進(jìn)程的頁(yè)

可變分配局部置換:頻繁缺頁(yè)的進(jìn)程，多分配一些物理塊；缺頁(yè)率很低的進(jìn)程，回收一些物理塊；直到缺頁(yè)率合適

何時(shí)調(diào)入頁(yè)面？

• 預(yù)調(diào)頁(yè)策略：一般用于進(jìn)程運(yùn)行前
• 請(qǐng)求調(diào)頁(yè)策略：程序運(yùn)行時(shí)，發(fā)生缺頁(yè)再調(diào)頁(yè)

從何處調(diào)頁(yè)？
對(duì)換區(qū)：采用連續(xù)存儲(chǔ)方式，速度快；
文件區(qū)：采用離散存儲(chǔ)方式，速度慢

• 對(duì)換區(qū)足夠大：運(yùn)行前將數(shù)據(jù)從文件區(qū)復(fù)制到對(duì)換區(qū)，之后所有的頁(yè)面調(diào)入調(diào)出都是內(nèi)存和對(duì)換區(qū)之間進(jìn)行
• 對(duì)換區(qū)不夠大：不會(huì)修改的數(shù)據(jù)每次都從文件區(qū)調(diào)入；會(huì)修改的數(shù)據(jù)調(diào)入對(duì)換區(qū)，需要時(shí)再?gòu)膶?duì)換區(qū)調(diào)入
• UNIX方式：第一次使用的頁(yè)面都從文件區(qū)調(diào)入；調(diào)出的頁(yè)面都寫回到對(duì)換區(qū)，再次使用時(shí)從對(duì)換區(qū)調(diào)入。

3.2.5 抖動(dòng)

抖動(dòng)指頁(yè)面頻繁換入換出的現(xiàn)象。主要原因是分配給進(jìn)程的物理塊不夠。

3.2.6 工作集

工作集指 在某段時(shí)間間隔內(nèi)，進(jìn)程實(shí)際訪問(wèn)頁(yè)面的集合。
駐留集大小一般不能小于工作集。

王道習(xí)題

訪問(wèn)時(shí)間的計(jì)算

在沒(méi)有快表的請(qǐng)求分頁(yè)存儲(chǔ)管理：如果缺頁(yè)，需要訪存三次（分別是：查頁(yè)表1次（第一次），缺頁(yè)之后調(diào)頁(yè)（I/O）然后再查頁(yè)表（第二次），之后訪問(wèn)目標(biāo)單元（第三次））

在有快表的請(qǐng)求分頁(yè)系統(tǒng)中：

分為三種線路；
1 ) 快表命中 ，訪存1次
2 ）快表未命中，訪問(wèn)慢表，慢表命中，訪存2次。

3）快表未命中，訪問(wèn)慢表，慢表缺頁(yè)，需要調(diào)頁(yè)I/O（很慢），然后查快表（肯定命中），訪存2次。

本題正確答案如下

$0.8?1us+0.2?0.9?2us+0.2?0.1?(20ms+2us)=401.2us$

2021考研王道教材答案錯(cuò)誤，錯(cuò)誤答案給的是401.22us。

《新程序員》：云原生和全面數(shù)字化實(shí)踐50位技術(shù)專家共同創(chuàng)作，文字、視頻、音頻交互閱讀

總結(jié)

以上是生活随笔為你收集整理的操作系统第三章-内存管理的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。