第四章存儲管理

（內(nèi)存管理）

進(jìn)程管理

進(jìn)程管理涉及到如下內(nèi)容:

進(jìn)程的表示

--PCB

進(jìn)程的創(chuàng)建

-可合并，也可分開

程序的加載

進(jìn)程的運(yùn)行——調(diào)度

進(jìn)程管理

進(jìn)程的同步-鎖、信號量等

進(jìn)程的通信

廠內(nèi)存

進(jìn)程的終止文件

進(jìn)程的資源I/O設(shè)備

存儲管理的任務(wù)

在單道程序環(huán)境中，同一個時間內(nèi)，系

統(tǒng)中只存在一個進(jìn)程，它獨(dú)占系統(tǒng)的所有資

源，當(dāng)然資源也歸它管理，操作系統(tǒng)可以不

提供專門的管理服務(wù)。

在多道程序環(huán)境中，系統(tǒng)中同時存在多

個進(jìn)程，所有的進(jìn)程共享系統(tǒng)資源，包括內(nèi)

存和外存。因此必須將存儲的管理權(quán)收回，

由操作系統(tǒng)統(tǒng)一管理系統(tǒng)的存儲。

存儲管理的任務(wù)

進(jìn)程對存儲的需求:

1、永久性存儲程序映像文件］外存

2、永久性存儲輸入/輸出數(shù)據(jù)」

3、存放程序執(zhí)行代碼

內(nèi)存

4、存放臨時性數(shù)據(jù)

存儲管理的任務(wù)

進(jìn)程對內(nèi)存管理的需求：

1、大的內(nèi)存，需要多少就有多少。

2、保護(hù)，不受其它進(jìn)程的干擾。

3、共享，能與指定的進(jìn)程共享部分內(nèi)

存。

存儲管理的任務(wù)

操作系統(tǒng)內(nèi)核對內(nèi)存管理的需求：

1、滿足進(jìn)程的需求，為進(jìn)程提供內(nèi)存服務(wù)。

2、高的內(nèi)存利用率，減少對內(nèi)存的浪費(fèi)，

充分發(fā)揮內(nèi)存的作用。

3、高的內(nèi)存管理效率，提供快速的分配和

回收內(nèi)存資源的手段。

存儲管理的任務(wù)是：

1、存儲資源的分配與回收。

2、存儲保護(hù)與安全。

3、存儲共享。允許兩個或多個進(jìn)程共用內(nèi)

存中相同區(qū)域。

4、內(nèi)存“擴(kuò)充”。使用戶基本不受實(shí)際內(nèi)

存容量的限制。

5、程序重定位。

6、地址轉(zhuǎn)換。

4.1引言

一、存儲器的層次

外存（輔存）：指磁盤、磁帶、光盤

等存儲器。

外存容量大、價(jià)格低，其上的數(shù)據(jù)不

容易丟失。因而通常用外存存放程序或數(shù)據(jù)

文件。外存的最小訪問單位是塊，因而又稱

為塊設(shè)備。

處理器不能直接訪問外存上的數(shù)據(jù)。

必須先通過控制器將其讀入內(nèi)存而后再訪問。

4.1引言

內(nèi)存（主存）：指CPU能直接訪問的存儲器。

為了管理的方便，把內(nèi)存抽象成一個字節(jié)

數(shù)組，其中的每個字節(jié)都有自己的地址。CPU可

以通過地址隨機(jī)地訪問內(nèi)存的任何一個字節(jié)。

與外存相比，內(nèi)存容量小、價(jià)格高，而且

掉電后其中的數(shù)據(jù)會丟失。

所以通常把內(nèi)存作為程序執(zhí)行和數(shù)據(jù)加工

的場所。

4.1引言

內(nèi)存雖比外存快，但與CPU相比，其速度

仍然很低。為了提高處理器的運(yùn)算速度，還需

要提供與其速度匹配的存儲器，這就是高速緩

存。

高速緩存(Cache)是內(nèi)存的緩存，它速

度高、價(jià)格也高，因而容量小。

速度最高的存儲器是寄存器(Register)o

4.1引言

外

存

magnetictapes

4.1引言

在這種存儲層次結(jié)構(gòu)中，內(nèi)存是外存的

緩存，而Cache又是內(nèi)存的緩存。這是成本

與速度折中的結(jié)果。

在這種結(jié)構(gòu)中，一個數(shù)據(jù)會同時出現(xiàn)在

幾個地方。

操作系統(tǒng)只關(guān)心內(nèi)存和外存，本章只關(guān)

心內(nèi)存。

4.1引言

二、程序的編譯、連接和裝入

1）用高級或匯編語言開發(fā)源程序，一般情況

下，源程序由多個模塊組成。

2）將源程序模塊編譯或匯編成目標(biāo)代碼。

3）連接程序?qū)⒏鱾€目標(biāo)文件連接在一起，并

解析其中的符號引用，形成可執(zhí)行文件。

4）進(jìn)程執(zhí)行程序。但在執(zhí)行之前需要先將可

執(zhí)行文件中的程序裝入內(nèi)存形成進(jìn)程映像。

4.1引言

如下圖:Memory

4.1引言

Loader的任務(wù)：將連接到一起的可執(zhí)行

模塊加載到內(nèi)存。

主要問題：將可執(zhí)行模塊加載到內(nèi)存的

什么位置？

程序中可以使用實(shí)際的物理地址、符號

地址（標(biāo)號、變量名、函數(shù)名等）或相對地

址等來表示它引用的內(nèi)存位置，但處理器只

認(rèn)實(shí)際的物理地址，因此在執(zhí)行程序之前，

必須將其中的符號地址、相對地址等轉(zhuǎn)換成

實(shí)際的物理地址。

4.1引言

1、程序員完成地址的轉(zhuǎn)換

程序員在開發(fā)程序時采用的就是實(shí)際的物

理地址，當(dāng)然在可執(zhí)行模塊中采用的也是實(shí)際

的物理地址。

只能將采用實(shí)際物理地址的程序裝入到內(nèi)

存的固定位置（即程序員確定的位置），而且

每次都必須將其裝入到同一個內(nèi)存位置，否則

它將無法運(yùn)行。

這種裝入方式叫做絕對裝入。

4.1引言

2、編譯（匯編）程序完成地址轉(zhuǎn)換

程序員直接使用實(shí)際的物理地址編程會產(chǎn)

生如下問題：

（1）需要程序員了解物理內(nèi)存的使用情況,

并預(yù)先確定程序在物理內(nèi)存中的位置。

（2）如果修改了程序，插入或刪除了指令,

程序中所有的地址都需要重新確定。

最好的辦法是在程序中使用符號來標(biāo)識地

址，讓編譯（匯編）程序?qū)⑵滢D(zhuǎn)換成實(shí)際的物

理地址。如下圖：

4.1引言

1024

ProgramProgram

jmpLl—jmp1424

Ll1424

movax,var-—movax,2224

DataData

var2224

符號地址絕對地址

4.1引言

3、裝入程序完成地址轉(zhuǎn)換

在多道程序的環(huán)境中，內(nèi)存中存在多個

程序，編譯或匯編程序?qū)嶋H上無法確定程序

在內(nèi)存的物理位置。因此，最好將決定程序

位置的工作向后推遲，交給Loader。

要讓裝入程序決定位置，需要可執(zhí)行模

塊是可重定位(Relocatable)的，即可以將

其裝入到內(nèi)存的任何位置。

4.1引言

具體的做法是：

(1)仍然讓編譯或匯編程序轉(zhuǎn)換符號地

址，但轉(zhuǎn)換的結(jié)果不再是絕對的物理地址，

而是一種相對地址(RelativeAddress),

即相對于某個位置的偏移量，如相對于程序

開始位置或當(dāng)前位置的偏移量。

4.1引言

(2)裝入程序在加載該程序時，為其

選擇一個內(nèi)存位置，如x,而后將程序中所

有對內(nèi)存的引用地址都加上x,為程序定

位。一次性定位，又稱靜態(tài)重定位。

這種裝入方式稱為靜態(tài)可重定位裝入。

4.1引言理

50妙,

一Program

0

ProgramProgramjmp5400

jmpLI—jmp4005400

movax,6200

L1400

movax,var-—movax,1200

Data

DataData620012345

var120012345

/

一

/

/

符號地址相對地址x\

4.1引言

4、在執(zhí)行時完成地址轉(zhuǎn)換

采用靜態(tài)可重定位裝入方式可以將程序裝

入到內(nèi)存的任何位置，但一旦裝入，其地址就

轉(zhuǎn)換成了絕對的物理地址，程序的位置也就固

定了。

在多道程序環(huán)境中，為了提高處理器和內(nèi)

存的利用率，經(jīng)常需要將某個進(jìn)程的程序換出

內(nèi)存，當(dāng)再次需要時再將其換入內(nèi)存。

靜態(tài)可重定位裝入問題：限定了程序只能

被換入到同一個位置。

4.1引言

解決的辦法是：

(1)將地址的轉(zhuǎn)換推遲到實(shí)際執(zhí)行程序

時。

(2)編譯(匯編)或連接程序生成可重

定位的目標(biāo)模塊，其中的地址都是相對的。

(3)裝入程序直接將可重定位模塊加載

到內(nèi)存，不做相對地址到物理地址的轉(zhuǎn)換。

4.1引言

(4)處理器在執(zhí)行程序的過程中，逐步

完成相對地址到物理地址的轉(zhuǎn)換。動態(tài)重定

位，需要硬件支持。

這種裝入方式稱為動態(tài)可重定位裝入。

4.1引言

4.1引言

連接程序的任務(wù)是將編譯（匯編）后的目標(biāo)

模塊連接到一起，解析其中的跨模塊地址引用，形

成一個可執(zhí)行模塊，用于程序的加載（裝入）。

ModuleoModuleA

ALLcallL

callB

L-lUL-l

L

0nModuleB

uModuleLinker

CallL+M

B>M

callC

M-lJL+M-l

L+M

ModuleModuleC

CKN

N-l

4.1引言

完成連接的時機(jī)有以下幾種：

1、在程序設(shè)計(jì)時。所有的程序都放在一

個文件中。

2、在編譯（匯編）時。編譯（匯編）程

序找到所有子程序的源代碼，并將它們編譯

（匯編）在一起。

4.1引言

3、在裝入前。各模塊分別編譯（匯編）

并生成可重定位的目標(biāo)模塊。由連接程序

將各目標(biāo)模塊整合成一個完整的可重定位

目標(biāo)模塊。

4、在裝入時。裝入程序先將主模塊讀

入內(nèi)存，而后再根據(jù)其中的符號引用逐個

讀入子模塊，修改各子模塊的相對地址，

并解析各符號引用。

4.1引言

5、在執(zhí)行時。在程序裝入時也不作連

接工作，Loader只裝入程序的主模塊，而且

不解析其中的符號引用。當(dāng)程序執(zhí)行到某符

號引用時（如子程序調(diào)用），它會發(fā)現(xiàn)該符

號對應(yīng)的程序模塊不在內(nèi)存，此時，操作系

統(tǒng)再找到相應(yīng)的目標(biāo)文件，并將其裝入內(nèi)存。

4.1引言

在主模塊中調(diào)用的不能僅僅是一個符

號，否則處理器會產(chǎn)生錯誤。為此，編譯

（匯編）或連接程序會用一個Stub代替子

程序名。stub是一小段代碼，利用它可以

找到駐留在內(nèi)存中的子程序，或?qū)⑵溲b入

內(nèi)存。這種連接方法稱為動態(tài)連接。

利用動態(tài)連接可以實(shí)現(xiàn)共享庫（動態(tài)

連接庫）。

4.1引言

動態(tài)連接與動態(tài)可重定位裝入結(jié)合起來，

可以實(shí)現(xiàn)很靈活的進(jìn)程加載機(jī)制。

“動態(tài)可重定位裝入”允許將程序加載到

物理內(nèi)存的任何位置，而且允許多次換入/換

出，每次換入的位置都可以不同。這給內(nèi)存管

理提供了很大的發(fā)揮空間。

4.1引言

“動態(tài)連接”允許只加載部分程序

（主程序），其它程序的加載被推遲到

了真正需要時。這既節(jié)約了內(nèi)存、加快

的程序加載的速度，又提供了共享庫函

數(shù)的可能。

“動態(tài)連接”還使程序的動態(tài)升級

成為可能。只要升級函數(shù)庫，不需要重

新編譯、連接，就可以使程序得到升級。

4.1引言

三、地址空間

名字空間：用戶源程序中由符號指令、

數(shù)據(jù)說明等符號名字構(gòu)成的空間。

地址空間：由程序中相對地址組成的

空間，也稱邏輯地址空間。（以0為基址順

序排列下來）

4.1引言

存儲空間：內(nèi)存中一系列存儲信息的物理

單元的集合，也稱為物理空間或絕對空間。

外存內(nèi)存

4.1引言

由CPU生成的地址稱為邏輯地址，如果程

序按照動態(tài)重定位方式裝入，其邏輯（虛擬）

地址空間和物理地址空間是不同的。

地址轉(zhuǎn)換機(jī)構(gòu)：內(nèi)存管理單元（MMU-

Memorymanagementunit）硬件設(shè)備

數(shù)據(jù)結(jié)構(gòu)：映射表如段描述符表（LDT）

或頁表。

4.1引言

如果程序按照動態(tài)重定位方式裝入，那么

在用戶程序中看到的、使用的全部都是邏輯

（虛擬）地址，所以它不再受物理內(nèi)存大小的

限制，只受地址位數(shù)的影響。

通過映射表，操作系統(tǒng)可以將各個進(jìn)程的

邏輯（虛擬）地址空間完全隔開（實(shí)現(xiàn)保護(hù)），

也可以讓它們有部分重疊（實(shí)現(xiàn)共享）。

4.1引言

四、覆蓋（Overlay）

在程序加載時要考慮內(nèi)存的大小。

問題：如何在有限的物理內(nèi)存中加載、運(yùn)

行大應(yīng)用程序？

方法：覆蓋（Overlay）。

4.1引言

基本思想：

按照程序的執(zhí)行順序，將程序分成幾

部分；

裝入程序先裝入它的第一部分，運(yùn)行

完后再裝入第二部分；

第二部分程序覆蓋第一部分程序，從

而節(jié)省空間。

4.1引言

如編譯程序通常分成兩階段：第一階段

生成符號表和中間代碼，第二階段生成目標(biāo)

代碼。

因此可以把整個編譯器程序分成兩部分:

第一部分：第一階段程序+公共代碼+符號表

第二部分：第二階段程序+公共代碼+符號表

4.1引言

假定：

第一階段程序70KB

第二階段程序80KB

公共代碼30KB

符號表20KB

如不米用覆蓋技術(shù)，程序運(yùn)行需要200KB內(nèi)

存。

如采用上述覆蓋技術(shù)，最多只需要130KB內(nèi)

存。

4.1引言

覆蓋的問題：需要程序員對程序代碼

有透徹的了解，而且需要能夠生成覆蓋程

序的特殊編譯、連接程序。

覆蓋技術(shù)不需要操作系統(tǒng)提供支持。

覆蓋技術(shù)可以壓縮單個進(jìn)程的物理地

址空間，但不能增加系統(tǒng)中可用物理內(nèi)存

的數(shù)量。

4.1引言

五、交換（Swapping）

增加可用物理內(nèi)存的方法是：將某些暫不運(yùn)行的

進(jìn)程的映像寫回磁盤（換出），回收它的物理內(nèi)存；

當(dāng)進(jìn)程再次運(yùn)行時，再將其讀入內(nèi)存（換入）。

在早期的分時系統(tǒng)中，內(nèi)存中只保留一個進(jìn)程，

其余進(jìn)程全部放在外存。

進(jìn)程調(diào)度、切換時，需要將當(dāng)前進(jìn)程換出，將下

一個進(jìn)程換入，其代價(jià)很高。

KT4.1引言

operating

system

(V)swapout

(T)swapin

user

space

backingstore

mainmemory

4.1引言

交換要耗費(fèi)很多時間。

例如，設(shè)用戶程序是20K字節(jié)，外存平

均存取時間是8111s，傳輸速度是250000字節(jié)

/S,則傳送20K字節(jié)的程序需用時間為

8ms+(20K/250000)=88ms

交換的核心問題：使交換的信息量減到

最小。

一種做法是下面的洋蔥皮算法：

4.1引言

(1)存儲分配過程

123456

4.1引言

(2)時刻J4各進(jìn)程使用內(nèi)存情況

20K進(jìn)程1

空閑區(qū)

進(jìn)程3

進(jìn)程2

在內(nèi)存

進(jìn)程4在外存

4.2基于分區(qū)的存儲管理

物理內(nèi)存的表示:

通常以內(nèi)存塊為單位管理內(nèi)存。內(nèi)存塊由字

節(jié)數(shù)組中的一系列連續(xù)的字節(jié)組成。

在進(jìn)程的運(yùn)行過程中，也會不斷地提出對內(nèi)

存的需求，如創(chuàng)建數(shù)據(jù)結(jié)構(gòu)、緩沖區(qū)、堆棧等，

這些內(nèi)存也是連續(xù)的內(nèi)存塊。

進(jìn)程對內(nèi)存的最大需求來源于程序的加載。

4.2基于分區(qū)的存儲管理

隨著系統(tǒng)的運(yùn)行，內(nèi)存會被逐漸地分割開，因此

需要一個數(shù)據(jù)結(jié)構(gòu)（如鏈表、數(shù)組）來記錄各內(nèi)存塊

的信息，如大小、開始位置、使用情況等。

空閑塊

I

已用

開始位置大小使用情況

04MB已用

4M3MB未用

I

■

4.2基于分區(qū)的存儲管理

操作系統(tǒng)如何管理內(nèi)存？

一種簡單的管理辦法是：將內(nèi)存劃分成

區(qū)，給每個進(jìn)程分配一個區(qū)，進(jìn)程自己管理

區(qū)內(nèi)內(nèi)存的使用，但不許跨區(qū)使用內(nèi)存。

——內(nèi)存的分區(qū)管理。

問題是如何分區(qū)？

4.2基于分區(qū)的存儲管理

一、固定分區(qū)法

由操作系統(tǒng)或系統(tǒng)管理員預(yù)先將內(nèi)存劃分

為若干分區(qū)，每個分區(qū)容納一個進(jìn)程。在系統(tǒng)

運(yùn)行的過程中，分區(qū)的邊界不能再改變。

當(dāng)要把一個進(jìn)程裝入內(nèi)存時，操作系統(tǒng)為

其找一個滿足下列條件的分區(qū)：

■空閑。

■尺寸大于或等于進(jìn)程的大小。

4.2基于分區(qū)的存儲管理

分區(qū)尺寸的確定：根據(jù)以往的統(tǒng)計(jì)信息和

系統(tǒng)的特殊需求預(yù)先確定的。

大致有兩種確定分區(qū)尺寸的方法：

1、等尺寸分區(qū)一一各分區(qū)具有相同的尺寸

OS

8MB

8MB

8MB

8MB

8MB

4.2基于分區(qū)的存儲管理

等尺寸分區(qū)法的問題：

(1)增加了程序設(shè)計(jì)的限制。當(dāng)程序過

大時，不得不采用覆蓋(Overlay)技術(shù)。

這增加了程序設(shè)計(jì)的難度。

(2)內(nèi)存的利用率低。如一個1MB的程

序也會占用8MB的分區(qū)，造成7MB的浪費(fèi)。

分區(qū)內(nèi)部的內(nèi)存浪費(fèi)稱為內(nèi)部碎片。

4.2基于分區(qū)的存儲管理

2、不等尺寸分區(qū)一一各分區(qū)可以具有不同的尺寸

os

2MB

4MB

6MB

8MB

8MB

12MB

16MB

4.2基于分區(qū)的存儲管理

不等尺寸分區(qū)的分配方法以下幾種：

(1)固定分配。只給進(jìn)程分配能滿足其需

要的最小尺寸的分區(qū)。如分區(qū)已被分配，則進(jìn)

程必須等待。

好處：使內(nèi)部碎片最小化。

問題：可能出現(xiàn)不公平的等待，如雖有大

尺寸的空閑分區(qū)，小進(jìn)程卻無法運(yùn)行。

4.2基于分區(qū)的存儲管理

(2)最佳適應(yīng)分配。給進(jìn)程分配能滿足其

需要的最小尺寸的可用分區(qū)。只有當(dāng)所有

分區(qū)都已被分配時，進(jìn)程才需要等待(或

換出別的進(jìn)程)。

好處：比較靈活

問題：會產(chǎn)生較大的內(nèi)部碎片。

4.2基于分區(qū)的存儲管理

固定分區(qū)法比較簡單，但卻存在如下問題:

(1)分區(qū)的個數(shù)限定了同時駐留內(nèi)存的進(jìn)

程個數(shù)。

(2)分區(qū)的大小和數(shù)量是在系統(tǒng)生成時確

定的，在運(yùn)行過程中不能調(diào)整，會導(dǎo)致較低的

內(nèi)存利用率，和大量的內(nèi)部碎片。

(3)進(jìn)程不能跨區(qū)使用內(nèi)存。

4.2基于分區(qū)的存儲管理

解決辦法：拋棄“固定”的概念，不

預(yù)先確定分區(qū)的大小和數(shù)量；將劃分區(qū)域

的工作推遲到實(shí)際分配內(nèi)存（如加載程序）

時進(jìn)行。

一可變分區(qū)法

4.2基于分區(qū)的存儲管理

二、可變分區(qū)法

基本思想：

初始情況下，把所有的空閑內(nèi)存看成一大

塊，或一個大的分區(qū)。

當(dāng)進(jìn)程要裝入程序時，按照它的要求，臨

時從空閑內(nèi)存中為其劃出一塊，構(gòu)成新的分區(qū)。

新分區(qū)的尺寸等于程序的大小。剩余的空閑內(nèi)

存構(gòu)成另一個新的分區(qū)。

4.2基于分區(qū)的存儲管理

OS128KOS128KOS128KOS128K

進(jìn)程工320K進(jìn)程工320K進(jìn)程1320K

896K進(jìn)程2224K進(jìn)程2224K

576K

352K進(jìn)程3288K

64K

初始狀態(tài)加載進(jìn)程1加載進(jìn)程2加載進(jìn)程3

4.2基于分區(qū)的存儲管理

隨著系統(tǒng)的運(yùn)行，進(jìn)程不斷地被創(chuàng)建、換

出、換入，產(chǎn)生的內(nèi)存碎片越來越多。如下圖

128K

224K

96K

128K

96K

288K

64K

進(jìn)程2進(jìn)程4進(jìn)程1進(jìn)程2

被換出被加載被換出被換入

4.2基于分區(qū)的存儲管理

在分區(qū)外部的小“碎片”稱為外部碎

片。

固定分區(qū)法會產(chǎn)生內(nèi)部碎片，而可變

分區(qū)法會產(chǎn)生外部碎片。外部碎片會使內(nèi)

存變得越來越零碎，直至無法使用。

4.2基于分區(qū)的存儲管理

解決外部碎片問題的一種方法是：緊

縮(Compaction)o即移動內(nèi)存中的進(jìn)程,

將碎片集中起來，重新構(gòu)成大的空閑內(nèi)存

塊。

如上圖，緊縮以后可以生成256KB的空

閑內(nèi)存塊。

4.2基于分區(qū)的存儲管理

緊縮的代價(jià)：

1）對地址敏感的項(xiàng)必須作適當(dāng)修改，

如基址寄存器、訪問內(nèi)存的指令，參數(shù)表

和使用地址指針的數(shù)據(jù)結(jié)構(gòu)等。

2）需要動態(tài)重定位的支持。

3）緊縮是很費(fèi)時的操作。

4.2基于分區(qū)的存儲管理

緊縮時機(jī)：

1）當(dāng)進(jìn)程結(jié)束，釋放了所占用的分區(qū),

如果它不與空閑區(qū)鄰接，就立即進(jìn)行緊縮。

2）在分配進(jìn)程的分區(qū)時，如果不能滿

足需求則進(jìn)行緊縮。

緊縮的次數(shù)就比1）少得多，但空閑

區(qū)的管理較前要復(fù)雜。

4.2基于分區(qū)的存儲管理

在可變分區(qū)法中，為了減少外部碎片的產(chǎn)生，需

要仔細(xì)選擇內(nèi)存分配算法，或可變分區(qū)算法。

內(nèi)存分配：從空閑內(nèi)存塊中選擇一個合適的塊，

將其分割開，一部分分配給進(jìn)程，一部分作為碎片保

留。

內(nèi)存回收：把進(jìn)程的內(nèi)存作為空閑塊收回，合并。

數(shù)據(jù)結(jié)構(gòu)：空閑塊鏈表，或空閑塊數(shù)組。記錄每

個空閑塊的位置、大小等信息。

4.2基于分區(qū)的存儲管理

常用的分配算法有三個：

1、最先適應(yīng)算法（Firstfit）

2、最佳適應(yīng)算法（Bestfit）

遍歷所有空閑塊，將滿足需要的最小空閑塊

分配給進(jìn)程。

3、下一個適應(yīng)算法（Nextfit）

從上次分配的位置開始向后搜索，將第一個

滿足要求的空閑塊分配給進(jìn)程。

4.2基于分區(qū)的存儲管理

8K申請16K

12K12K

22KFirstfit

6K

18KBestfit

次

上2K

配

分

置

位8K8K

6K6K

14K14K

Nextfit

36K

20K

4.2基于分區(qū)的存儲管理

1、最先適應(yīng)算法：

快；從頭分配，分區(qū)相對集中在內(nèi)存的

前部，大空閑塊存留到后面；

便于內(nèi)存釋放后合并。

2、最佳適應(yīng)算法：

留下的碎片最小，基本無法再用；

需要更頻繁地緊縮。

4.2基于分區(qū)的存儲管理

3、下一個適應(yīng)算法：

對內(nèi)存的使用較平均，不容易留下大

的空閑塊。

上述三個算法哪個最好？

最先適應(yīng)算法是最優(yōu)的，下一個適應(yīng)

算法次之，最佳適應(yīng)算法是最差的。

統(tǒng)計(jì)表明，大致有1/3的內(nèi)存因?yàn)樗?/p>

片而浪費(fèi)。

4.2基于分區(qū)的存儲管理

與固定分區(qū)法相比，可變分區(qū)法比較靈活,

而且避免了內(nèi)部碎片，但卻出現(xiàn)了外部碎片。

原因：可變分區(qū)法沒有對分區(qū)的尺寸和分

割的方法作任何限制，所以容易將內(nèi)存切割得

太無規(guī)則、太零碎。

4.2基于分區(qū)的存儲管理

解決方法：將分區(qū)的大小限定為2k,

并且按照平分的方式分割內(nèi)存，則各個分

區(qū)就會變得較有規(guī)則，分割與合并就會更

容易，就可以減少一些外部碎片。

——伙伴算法

4.2基于分區(qū)的存儲管理

三、伙伴算法（Buddy）

在伙伴算法中，內(nèi)存塊的尺寸為2￡

L<K<U；

2L是允許分配的最小內(nèi)存塊的尺寸；

2U是允許分配的最大內(nèi)存塊的尺寸，即

全部可用物理內(nèi)存的大小。

4.2基于分區(qū)的存儲管理

分配方法如下：

■1、將全部可用的物理內(nèi)存看成一塊，大小為2L

■2、如果請求的大小為s(2u-1<s<2u),則將全

部內(nèi)存分配給它。

■3、否則，將內(nèi)存分割成兩個相等的伙伴，大小

為251。如果請求的大小為s(2u-2<s<2u-1),

則將一個伙伴分配給它。

?4、重復(fù)分割伙伴，直到其尺寸剛好滿足請求。

4.2基于分區(qū)的存儲管理

釋放方法如下：

■1、如果物理頁塊的伙伴不在空閑隊(duì)列，則將

被釋放的物理頁塊直接插入空閑隊(duì)列。（只有

伙伴才可以合并）

■2、如果物理頁塊的伙伴在空閑隊(duì)列中，則將

它的伙伴從隊(duì)列中摘下，將它們合并成一個更

大的物理頁塊，重新插入另一空閑隊(duì)列（遞

歸）。

4.2基于分區(qū)的存儲管理

數(shù)據(jù)結(jié)構(gòu)：一組鏈表，鏈表i中排列的是大小

為2i的空閑內(nèi)存塊。

大小為2i+l的空閑內(nèi)存塊被分割后，它將被從

鏈表i+1中刪除。分割后的伙伴被加入到了鏈表i中

（大小為2D。

如果大小為2i的兩個伙伴都已空閑，可以將它

們從鏈表i中刪除，組合成一個大小為2i+i的新空閑

塊，并加入到鏈表i+1中。

4.2基于分區(qū)的存儲管理

1MB內(nèi)存1M

申請100K128K128K256K512K

申請240K128K128K256K512K

申請64K128K6464256K512K

申請256K128K6464256K256K256

釋放240K128K6464256K256K256

釋放100K128K6464256K256K256

申請75K128K6464256K256K256

釋放64K128K128K256K256K256

釋放75K512K256K256

釋放256K1M

4.2基于分區(qū)的存儲管理

伙伴算法的特點(diǎn)：

?:?是固定分區(qū)和可變分區(qū)法的一個折中，比

固定分區(qū)法靈活，不受分區(qū)尺寸及個數(shù)的

限制；它比可變分區(qū)法規(guī)范，不會出現(xiàn)外

部碎片。

。容易分配，也容易組合。

。會產(chǎn)生內(nèi)部碎片，但內(nèi)部碎片的浪費(fèi)不會

有固定分區(qū)那么多。

4.2基于分區(qū)的存儲管理

在Unix和Linux系統(tǒng)中，采用伙伴算法

管理物理內(nèi)存，但在具體實(shí)現(xiàn)上有一些變

化。

如在Linux中，伙伴的最小單位是頁

(212Byte)而不是字節(jié)。

4.3基于分段的存儲管理

在目前考慮的所有分配方法中，都把進(jìn)程看成一

個整體，只能同時被加載、釋放、換入、換出。

特點(diǎn)：實(shí)現(xiàn)簡單，只需要記錄進(jìn)程的開始地址和

界線，利用動態(tài)重定位技術(shù)即可實(shí)現(xiàn)地址的轉(zhuǎn)換。

問題：需要為進(jìn)程準(zhǔn)備大塊的、連續(xù)的內(nèi)存，增

加了分配的難度，也增加了進(jìn)程加載、換入、換出的

時間。

4.3基于分段的存儲管理

從用戶的角度看，進(jìn)程并不是一塊連續(xù)的內(nèi)存塊,

而是一組具有不同意義、不同大小的內(nèi)存段。

logicaladdressspace

4.3基于分段的存儲管理

從用戶的角度看，進(jìn)程是由幾部分組成的。

可以將其分開加載到內(nèi)存的不同區(qū)域。

減輕對大塊連續(xù)內(nèi)存的需求壓力，也可減少

I/O操作。

每個進(jìn)程都需要一個段表來描述進(jìn)程各個分

區(qū)的開始位置和界線，增加了實(shí)現(xiàn)的難度。

4.3基于分段的存儲管理

,_____甘

代碼

?臾建段名序號基地址大小

代碼0200600

.甘陽

數(shù)據(jù)12300100

建

?界EB我

堆棧28000200

■甘M+iL

XLEIJUL

堆棧

.)臾建

4.3基于分段的存儲管理

在分段技術(shù)中，每個邏輯地址由兩部分組成：

段號：在進(jìn)程段表中的序號，用來確定分區(qū)的

開始位置和界線。如Intel中的段選擇符。

偏移量：即相對地址，是相對于分區(qū)開始位置

的偏移量，用來定位內(nèi)存單元。

地址的轉(zhuǎn)換需要硬件的支持，即需要硬件機(jī)制

動態(tài)地完成邏輯地址到物理地址的轉(zhuǎn)換。

當(dāng)不能轉(zhuǎn)換時產(chǎn)生缺段中斷。

4.3基于分段的存儲管理

地址轉(zhuǎn)換過程:

CPU

4.3基于分段的存儲管理

分段技術(shù)要點(diǎn)：

?：?一個進(jìn)程可以占用多個小分區(qū)。

?:?各個小分區(qū)可以不連續(xù)。

?:?各個小分區(qū)的尺寸可以不一樣（可變分區(qū)）。

?:?不存在內(nèi)部碎片。外部碎片也變少。

?:?需要為每個進(jìn)程提供一個段表。

?:?需要硬件機(jī)制動態(tài)地完成邏輯地址到物理地址的轉(zhuǎn)

換。

4.3基于分段的存儲管理

在Intel處理器中，邏輯地址到線性地址的轉(zhuǎn)換:

15o31Q

Logical

Address

4.3基于分段的存儲管理

利用分段技術(shù)可以實(shí)現(xiàn)內(nèi)存保護(hù)。

段表中的每一項(xiàng)是一個段描述符，其中

可以包含一些保護(hù)信息，如段的大小（界線）

和訪問方式（只讀、讀寫、執(zhí)行等）。

在每一次地址轉(zhuǎn)換前，都要作合法性檢

查，如地址是否越界、訪問是否合法等。這

種檢查是由硬件完成的，且不可屏蔽。

4.3基于分段的存儲管理

利用分段技術(shù)可以實(shí)現(xiàn)內(nèi)存共享

(Sharing)。

如果一個段描述符出現(xiàn)在兩個進(jìn)程的

段表中，那么在兩個進(jìn)程中都可以訪問到

該段的內(nèi)容，從而可以實(shí)現(xiàn)內(nèi)存的共享。

4.3基于分段的存儲管理

進(jìn)程1的段表

進(jìn)程2的段表

4.3基于分段的存儲管理

段式管理的優(yōu)點(diǎn)：

1、有利于用戶對程序地址空間的了解，便于對各

程序段的共享和保護(hù)。

2、允許用戶地址空間大于實(shí)際的物理內(nèi)存空間，

為多道程序運(yùn)行提供了支持。

3、便于動態(tài)連接，從而避免靜態(tài)連接造成的某些

時間和空間的浪費(fèi)。

段式管理的缺點(diǎn)：

1、復(fù)雜，增加硬件成本，增加軟件運(yùn)行開銷。

2、分段的大小受內(nèi)存容量的限制。

4.4基于分頁的存儲管理

分段技術(shù)的特點(diǎn)：

1、可以減少外部碎片，卻不能消除；

2、需要用戶的參與，不利于操作系統(tǒng)透明

地管理。

固定分區(qū)技術(shù)特點(diǎn)：

1、不會產(chǎn)生外部碎片，卻可能產(chǎn)生內(nèi)部碎

片。

2、限定一個進(jìn)程只能使用一個分區(qū)。

4.4基于分頁的存儲管理

對固定分區(qū)技術(shù)作如下修改：

1、取消一個進(jìn)程只使用一個分區(qū)的

限制，允許進(jìn)程使用多個分區(qū)；

2、壓縮分區(qū)的尺寸，使各分區(qū)足夠

小。

4.4基于分頁的存儲管理

結(jié)果：

1、給一個進(jìn)程分配多個小的固定分區(qū)。

2、屬于一個進(jìn)程的小分區(qū)可以不連續(xù)。

3、消除了外部碎片，減少了內(nèi)部碎片。

4、以分區(qū)為單位實(shí)現(xiàn)進(jìn)程的換入/換出。

當(dāng)分區(qū)足夠小時，換入/換出的代價(jià)很小，而且

允許進(jìn)程部分地駐留內(nèi)存。

分頁(Paging)技術(shù)

4.4基于分頁的存儲管理

一、分頁管理

問題1:采用等尺寸分區(qū)還是不等尺寸分區(qū)?

不等尺寸分區(qū)需要記錄各分區(qū)的大小和開

始位置，實(shí)現(xiàn)較復(fù)雜。

等尺寸分區(qū)只需要記錄各分區(qū)的開始位置，

實(shí)現(xiàn)相對簡單。

使用等尺寸分區(qū)，即各分區(qū)的大小相等，

稱為幀(Frame)。

4.4基于分頁的存儲管理

問題2：幀的尺寸應(yīng)取多大？

如果幀過大，足夠容納下一個進(jìn)程，那么

分頁技術(shù)就蛻變成了固定分區(qū)技術(shù)。

如果幀過小，如大小為一個字節(jié)，則分頁

技術(shù)就變成了可變分區(qū)技術(shù)。

4.4基于分頁的存儲管理

內(nèi)部碎片的平均大小是半個幀，為減少碎片,

幀應(yīng)小。

研究表明，幀的大小應(yīng)在512到8192字節(jié)之

間。

為了管理的方便，幀的大小應(yīng)是2的指數(shù)。

在Intel處理器上，幀的大小為4096字節(jié)。

4.4基于分頁的存儲管理

問題3：如何分割進(jìn)程的地址空間（程序和

數(shù)據(jù)）？

將進(jìn)程的邏輯（虛擬）地址空間分割成小

塊，大小與幀相同，稱為頁（Page）o由操作

系統(tǒng)自動完成。

當(dāng)要加載（換入）一個進(jìn)程時，將進(jìn)程的

一個頁加載進(jìn)內(nèi)存的一個幀。

進(jìn)程在內(nèi)存中占用的幀可以不連續(xù)。

4.4基于分頁的存儲管理

0

1K

0

2K

1K

2K3K

3K4K

4K5K

6K

頁7K

表

8K

4.4基于分頁的存儲管理

問題4：如何完成地址轉(zhuǎn)換？

假定頁X被加載到了幀Y中，那么在頁X中偏移量為

d的邏輯地址所對應(yīng)的物理地址應(yīng)該是：

幀Y的基地址+偏移量d

邏輯地址

物理地址

4.4基于分頁的存儲管理

假如頁的大小為4KB。

X是位于第2頁的一個邏輯地址，它相對于

該頁開始位置的偏移量為d（d<4096）o那么該

地址相對于程序開始位置的偏移量為：2X4096

+do

（頁號）2（偏移量）d

4.4基于分頁的存儲管理

如第2頁被加載到了物理內(nèi)存的第3幀,

則X對應(yīng)的物理地址為：3X4096+do

（幀號）3（偏移量）d

邏輯地址2義4096+d對應(yīng)的物理地址

為3X4096+d。

4.4基于分頁的存儲管理

一個邏輯地址由兩部分組成:

頁號P偏移量d

以P為索引查頁表，如得到的幀號為f,則該邏輯

地址對應(yīng)的物理地址為：

幀號f偏移量d

進(jìn)程的程序必須是可動態(tài)重定位的。

地址轉(zhuǎn)換需要硬件的支持。

4.4基于分頁的存儲管理

m+1

頁表

4.4基于分頁的存儲管理

每個進(jìn)程都需要一個頁表。

問題：頁表放在哪里？

1、如果頁表較小，可以用寄存器存放當(dāng)前

進(jìn)程的頁表。如PDP-11計(jì)算機(jī)采用16位地址，

頁的大小為8KB,每個頁表最多有8個頁表項(xiàng)。

處理器提供了8個寄存器，用于存放頁表。進(jìn)程

切換時，同時切換這8個寄存器。

4.4基于分頁的存儲管理

2、進(jìn)程的頁表較大，則需要放在內(nèi)存中，

并將頁表的基地址(Pagetablebase)記錄

在進(jìn)程的PCB中。

如目前的Intel處理器采用32位地址，頁

的大小為4KB,單個頁表最多可有1024X1024

個頁表項(xiàng)。無法用寄存器存放。

頁表要用連續(xù)的物理內(nèi)存，采用物理地址。

4.4基于分頁的存儲管理

處理器提供一個專用寄存器(PTBR)用于

記錄當(dāng)前進(jìn)程的頁表基地址。當(dāng)進(jìn)程切換時，

PTBR的內(nèi)容也要切換。

當(dāng)需要轉(zhuǎn)換地址時，首先通過PTBR找到當(dāng)

前進(jìn)程的頁表，而后查頁表找到邏輯頁對應(yīng)的

物理幀，從而算出物理地址。

4.4基于分頁的存儲管理

問題：每次地址轉(zhuǎn)換都需要多次訪問內(nèi)

存，大大降低了處理速度。

解決方法：由處理器提供快速查找緩存

TLB(TranslationLookaside

Buffer),在其中緩存最近使用的頁表項(xiàng)。

TLB的命中率在80%以上。

4.4基于分頁的存儲管理

帶TLB的地址轉(zhuǎn)換:

pagetable

4.4基于分頁的存儲管理

問題5：誰來完成地址轉(zhuǎn)換？

在支持分頁機(jī)制的系統(tǒng)中，處理器產(chǎn)生的邏輯地

址并不直接送到地址總線上，而要經(jīng)過內(nèi)存管理單元

(MMU)的處理。MMU負(fù)責(zé)完成地址的轉(zhuǎn)換。

總線

4.4基于分頁的存儲管理

問題6：如何組織頁表？

目前的計(jì)算機(jī)都支持大的邏輯地址空間，

因而需要大的頁表。

如：在具有32位邏輯地址空間的系統(tǒng)中，

如果頁的大小為4KB,則頁表中應(yīng)有1M的頁表項(xiàng)。

如果一個頁表項(xiàng)占用4個字節(jié)，則每個頁表都需

要4MB的內(nèi)存。

沒有必要為每個進(jìn)程都分配4MB的連續(xù)物理

內(nèi)存用于存儲其頁表。

4.4基于分頁的存儲管理

解決辦法：將頁表分片，變單級頁表為多級頁表。

二級頁表物理內(nèi)存

4.4基于分頁的存儲管理

分級以后，進(jìn)程的一級頁表必須存在（保

存在進(jìn)程的PCB中）。

二級頁表可以不連續(xù)，可以不存在，甚至

可以被換出/換入。通常情況下，動態(tài)地創(chuàng)建

二級頁表，從而大大減少其數(shù)量。

4.4基于分頁的存儲管理

分級以后，進(jìn)程的邏輯地址也被分成多個部分:

4.4基于分頁的存儲管理

Intel處理器的地址轉(zhuǎn)換:

LinearAddress

31222112110

r32bitsalignedontoa4-KByteboundary

4.4基于分頁的存儲管理

32位的SPARC采用三級頁表。

32位的Motorola68030采用四級頁表。

64位的UltraSPARC采用七級頁表。

另有一些體系結(jié)構(gòu)（PowerPC）采用反向頁

表。

4.4基于分頁的存儲管理

問題7：頁表項(xiàng)中應(yīng)包含什么信息?

幀號和保護(hù)信息。如Intel的頁表項(xiàng)格式如下:

4.4基于分頁的存儲管理

第0位是一個存在標(biāo)志，表示邏輯頁是否

已被加載進(jìn)內(nèi)存。

當(dāng)邏輯頁在內(nèi)存時，P位為1,頁表項(xiàng)中記

錄的是物理幀的基地址，即邏輯頁在內(nèi)存中的

位置，處理器利用該地址可以將邏輯地址轉(zhuǎn)換

為物理地址。

4.4基于分頁的存儲管理

當(dāng)邏輯頁不在內(nèi)存時，P位為0,處理器無

法利用它轉(zhuǎn)換地址，因而產(chǎn)生異常。

操作系統(tǒng)處理異常時，可以將邏輯頁加載

進(jìn)內(nèi)存，并修改頁表項(xiàng)，將P位置1。

當(dāng)P位為0時，可以利用頁表項(xiàng)記錄邏輯頁

在外存中的位置。

頁表可以不在內(nèi)存，此時頁目錄項(xiàng)中的P

位為0。

4.4基于分頁的存儲管理

U/S位和R/W位用來實(shí)現(xiàn)頁的保護(hù)。

U/S=l,表示普通用戶頁，特權(quán)級為3。

R/W=O,表示頁只能讀，不能寫。

在進(jìn)程的頁表中，0—3GB部分都是普通用戶

頁（U/S=l）,3GB—4GB是超級用戶頁（U/S

=0）O

4.4基于分頁的存儲管理

當(dāng)進(jìn)程的邏輯頁第一次被加載到內(nèi)存時，

其頁表項(xiàng)才真正建立。以后，隨著進(jìn)程邏輯頁

的換出/換入，其頁表項(xiàng)會被反復(fù)修改。進(jìn)程終

止時，其頁目錄和頁表都會被釋放。

在頁被加載時，根據(jù)頁的實(shí)際情況設(shè)置其

R/W位o

4.4基于分頁的存儲管理

D位表示頁的內(nèi)容是否被修改過。當(dāng)頁的

內(nèi)容被修改時，該頁的D位被置1。

操作系統(tǒng)根據(jù)該位就可以知道是否需要

保存頁的內(nèi)容。

A位表示頁的內(nèi)容是否被訪問過。操作系

統(tǒng)通過檢查該位可以統(tǒng)計(jì)頁被訪問的頻率，知

道頁是否最近被使用過。

4.4基于分頁的存儲管理

頁表是由操作系統(tǒng)管理的。

頁表將進(jìn)程的虛擬地址空間和物理地址

空間完全隔開了，從而給操作系統(tǒng)創(chuàng)造了自由

發(fā)揮的空間和條件。

分頁機(jī)制是現(xiàn)代操作系統(tǒng)的基礎(chǔ)。

4.4基于分頁的存儲管理

問題8：如何管理幀的分配和釋放？

數(shù)據(jù)結(jié)構(gòu)：

1、描述系統(tǒng)中所有的幀（物理頁）

Linux用一個page結(jié)構(gòu)描述一個幀。

在系統(tǒng)初始化時，操作系統(tǒng)從BIOS中獲得機(jī)

器物理內(nèi)存的大小，算出總的幀數(shù)，而后創(chuàng)建

一個page結(jié)構(gòu)的數(shù)組mem_niap口，描述系統(tǒng)中所

有的幀（物理頁）。

每個物理頁對應(yīng)一個page結(jié)構(gòu)。

4.4基于分頁的存儲管理

2、描述系統(tǒng)中所有的空閑幀。

Linux用一個free_area[]數(shù)組描述所有空閑幀。

4.4基于分頁的存儲管理

free_area□數(shù)組中有多個隊(duì)列，其中：

free_area[O]上排列的是大小為1頁的空閑塊。

free_area[l]上排列的是大小為2頁的空閑塊。

free_area[2]上排列的是大小為4頁的空閑塊。

free_area[n]上排列的是大小為2rl頁的空閑塊。

用第一個物理頁的page結(jié)構(gòu)代表一個空閑頁塊。

物理頁的分配和回收采用伙伴算法。

每次分配出去的物理內(nèi)存必須是2n個物理頁（OWn）

4.4基于分頁的存儲管理

位圖map中記錄兩個伙伴的使用信息：

1）如兩個伙伴都已分配出去，它們的位為0；

2）如有一個伙伴空閑，它們的位為1；

3）如兩伙伴都空閑，它們應(yīng)在上一級隊(duì)列

中。

4.4基于分頁的存儲管理

大小為2i、編號為m的物理頁塊的伙伴

是：mA(-((M))?i))

這兩個伙伴在位圖freearea[i]->map中共

用的標(biāo)志位是：m?(1+i)

如：頁塊8—H(代表是8)的伙伴是12-

T5(代表是12),它們在位圖

free_area[2]->map中共用第1位。

4.4基于分頁的存儲管理

物理頁（幀）的分配算法（申請2。逐改頁）：

1、如果需要回收物理內(nèi)存，則喚醒內(nèi)核

交換守護(hù)進(jìn)程kswapd,或強(qiáng)行回收（自己調(diào)用

回收函數(shù)）。

2、如果不需要回收內(nèi)存或已回收到了足

夠的內(nèi)存,則查free_area數(shù)組的第order列：

1）如果其中有滿足要求的頁塊，則摘下一塊,

調(diào)整參數(shù)、位圖，返回物理頁塊的首地址。

1m

1q//4.4基于分頁的存儲管理

2）否則（隊(duì)列為空），向上搜索&ee_area數(shù)

組：

■如果上面的隊(duì)列全空，則此次分配失敗，返

回0。

■否則，將找到的大物理頁塊從其隊(duì)列中摘下、

分割成伙伴，將一個大小適中的伙伴分配給

用戶，其余伙伴加入相應(yīng)隊(duì)列，同時調(diào)整參

數(shù)、修改位圖。

4.4基于分頁的存儲管理

物理頁的釋放算法：

1、根據(jù)物理頁塊的首地址算出它在

mem_map中的索引map_nr,找到物理頁塊的

page結(jié)構(gòu)。

2、如果物理頁塊不是保留的，則釋放它:

1）清除page結(jié)構(gòu)中的PGjeferenced標(biāo)

/8O

4.4基于分頁的存儲管理

2）將物理頁塊加入到數(shù)組free_area中：

■如果物理頁塊的伙伴不在隊(duì)列free_area[order]

中，則將其直接插入隊(duì)列，并修改位圖。

■如果物理頁塊的伙伴在隊(duì)列中，則將它的伙伴從

隊(duì)列中摘下、修改位圖，將它們合并成一個更大

的物理頁塊，重新插入數(shù)組freearea中（遞歸）。

4.4基于分頁的存儲管理

7

6

5

4

3