第四章 存儲器管理課件

夕第四章存儲器管理

MemoryManagement

□為多道程序的運行提供良好的環(huán)境

□提高存儲器的利用率

□從邏輯上擴充存儲器

本章主要內(nèi)容

一?一?—U■■■■A—/f??—―????■

4.1存儲體條

4.2程序的鏈接和裝入

4.3連續(xù)分配方式

4.4基本分頁存儲管理方式

4.5基本分段存儲管理方式

4.6虛擬存儲器的基本概念

4.7請求分頁存儲管理方式

4.8頁面置換算法

4.9請求分段存儲管理方式

二章寤跚管

§4.1存儲體系

在現(xiàn)代計算機系統(tǒng)中，存儲器是信息外理的來源與歸

宿，占據(jù)重要位置。但是，在現(xiàn)有技術(shù)條件下，任何

一種存儲裝置，都無法同時從速度與容量兩方面，滿

足用戶的需求。實際上它們組成了一個速度由快到慢,

容量由小到大的存儲裝置層次。

§4.1存儲體系

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

使主存儲器在成本、速度和規(guī)模之間獲得較好的權(quán)衡。

§4.2程序的鏈接和裝入

ProgramLinkingandLoading

ca一、用戶程序的主要處理階段

ca二、程序的裝入

ca三、程序的鏈接

朱1

一、用戶程序的主要處理階段

將一個用戶程序變?yōu)橐粋€可在內(nèi)存中執(zhí)行的程序，通常

要經(jīng)過以下幾步：

。(1)編譯Compiling)

9Sourcecode?>ObjectModule

O(2)鏈接(Linking)

9ObjectModules+Libraryfunction…>LoadModule

O(3)裝入(Loading)

<LoadModule■■-internalMemory；構(gòu)造PCB,形成

進程(使用物理地址)

編譯器只能在一個模塊內(nèi)部完成符號名到地址的轉(zhuǎn)換,

1同模塊間的符號解析由鏈接器來完成的。

主

庫

匯編

編譯

k

『V'內(nèi)存

第一步第二步第三步

圖4?1對用戶程序的處理步驟

符號地址、相對地址、絕對地址

源程序邏輯地址空間物理地址空間

0

BA=1000

LoadAdatal100

LoadA1200

編譯地址映射

連接

12003456

datal3456200o

二章褊轆百

基本概念(BasicConcept)

。地址映射（重定位）：把邏輯地址空間中使用的邏輯地址變換成

內(nèi)存空間中的物理地址的過程。

。物理地址：內(nèi)存是一塊存儲區(qū)域，存儲單位是字節(jié)（字），每個

字節(jié)都有地址。這種地址稱為物理地址（絕對地址）。所有的物

理地址集合構(gòu)成物理地址空間。

。邏輯地址：源程序經(jīng)過編譯連接形成可執(zhí)行文件中的地址，通常

從o開始，程序中其余指令中的地址都相對于首地址而編址，這

種地址稱為邏輯地址（相對地址、虛地址）。所有邏輯地址的集

合構(gòu)成邏輯地址空間。

。符號地址：源程序中用字母和數(shù)字組成的符號代表存儲器的地址。

二、程序的裝入

ProgramLoading

4?IQ■■■■令?—??、間???——

一個程序運行裝入到內(nèi)存時，可有三種裝入方式：

割(1)絕對裝入方式(AbsoluteLoadingMode)

割(2)可重定位方式(RelocatableLoadingMode)

-fl⑶動態(tài)運行時裝入方式(dynamicRun-TimeLoading)

1絕對裝入方式(AbsoluteLoadingMode)

由裝入程序根據(jù)裝入模塊中的地址，將程序和數(shù)據(jù)裝

入內(nèi)存。裝入模塊的地址是編譯時由編譯程序產(chǎn)生的，是絕

對地址。裝入程序按裝入模塊裝入內(nèi)存時，不需修改地址。

。絕對地址可由程序員直接給出，或在編譯或匯編時給出。

。這種方式要求事先已知程序?qū)⒀b入內(nèi)存的位置。一般只在

單道程序的環(huán)境才有可能實現(xiàn)。

9優(yōu)點：裝入過程簡單。

小缺點：過于依賴硬件結(jié)構(gòu)，不適于多道程序系統(tǒng)。

例如:

邏輯地址空間內(nèi)存

printfprintf

Ujj^JIOVOlFFI^JMOV01FFF,5

CALL01011SggaCALLOIOU

■M麴1

2可重定位裝入方式(RelocatableLoadingMode)

由裝入程序根據(jù)內(nèi)存當時的實際使用情況，將裝入模塊裝

入到內(nèi)存的適當?shù)胤健Ｄ繕四K中為相對地址（邏輯地址）。

O裝入模塊中的邏輯地址與實際裝入內(nèi)存的物理地址不同。

裝入內(nèi)存時，要進行fii虐例

o可重定裝入方式采用的靜態(tài)重定位。

o其地址變換方式為：|物理地址=相對地址+內(nèi)存起始地址

。優(yōu)點：不需硬件支持，可以裝入有限多道程序。

。缺點：一個程序通常需要占用連續(xù)的內(nèi)存空間，程序裝

入內(nèi)存后不能移動。

1章褊轆毓

例如:

內(nèi)存空間

邏輯空間0

3、動態(tài)運行時裝入方式（dynamicRun-TimeLoading）

裝入模塊為相對地址，在裝入內(nèi)存時，并不立即變?yōu)槲锢?/p>

地址（絕對地址），即裝入后仍為相對地址。只有在程序真正

執(zhí)行到某一步時才對它進行地址轉(zhuǎn)換（動態(tài)重定位）。

?:?優(yōu)點：OS可以將一個程序分散存放于不連續(xù)的內(nèi)存空間，

可以移動程序，有利用實現(xiàn)共享。

?缺點：該方式需要一定特殊硬件的支持，OS實現(xiàn)較復雜。

是實現(xiàn)虛擬存儲的基礎。

例：如：

o*s曾定位寄彳軍器

作業(yè)10

01000

111000

100

Load1,500■500?1100

Load1,500

相對地址\

500

123451500

12345

N1000+N

處理機存令斤器內(nèi)存

一側(cè)一磔

幾個重要概念

Severalimportantconcepts

O絕對地址(AbsoluteAddress)>物理地址(PhysicalAddress)

O相對地址(RelativeAddress)>邏輯地址(LogicalAddress)

。符號地址(SymbolAddress)

O地址空間(AddressSpace)>邏輯地址空間

。存儲空間(storagespace)、主存空間、物理地址空間

。重定位(Relocation):在把程序的目標程序裝入到內(nèi)存時的地址修

改過程，即LA”>PA.

O靜態(tài)重定位(StaticRelocation)

。動態(tài)重定位(DynamicRelocation)

重定位

o概念：程序和數(shù)據(jù)裝入內(nèi)存時，需要對目標程序中的地

址進行修改，這種把邏輯地址轉(zhuǎn)換為內(nèi)存物理地址的過

程叫做重定位。

o類型：根據(jù)重定位時間和技術(shù)的不同，分為：

9靜態(tài)重定位：程序執(zhí)行前，一次性將該作業(yè)中程序的

指令地址和數(shù)據(jù)地址全部轉(zhuǎn)換成絕對地址，裝入內(nèi)存,

且以后不能移動。

9動態(tài)重定位：在程序執(zhí)行過程中動態(tài)地進行地址轉(zhuǎn)換,

由地址變換機構(gòu)（硬件）自動執(zhí)行。

H二□章褥雌曾！

三、程序的鏈接

ProgramLinking

Ig-?――/??|,.nIU■?令?—??一■

源程序經(jīng)過編譯后，可得到一組目標模塊，利用鏈

接程序?qū)⑦@組目標模塊鏈接，形成裝入模塊。鏈接階段

產(chǎn)生的可執(zhí)行目標程序在不運行時，通常作為一個二進

制可執(zhí)行文件駐留在硬盤上。

■根據(jù)鏈接時間的不同，可把鏈接分成如下三種:

(1)靜態(tài)鏈接Staticlinking

(2)裝入時動態(tài)鏈接Load-timedynamiclinking

(3)運行時動態(tài)鏈接Run-timedynamiclinking

需口章裾

1.靜態(tài)鏈接

在裝入內(nèi)存之前進行，鏈接后形成一固定的裝入模塊（也

稱為可執(zhí)行程序），不再拆開。

目標模塊1裝入模塊圖

4

0

04—

printf(MOK");程

call1200H序

靜

態(tài)

庫模塊1300H鏈

接

。voidprintf(…){示

)意

此方式需要解決：1）修改相對地址。

2）變換外部調(diào)用符號。

2.裝入時動態(tài)鏈接

目標模塊在裝入內(nèi)存時邊裝入邊鏈接。

密入

衣20000H

call21200H

庫模塊21200H

0voidprintf(...)

)

1s

.U早m腐葩閡

優(yōu)點:

?1)便于修改和更新：由于各目標模塊分開存放，只需對要修

改的模塊修改后編譯即可，保證所有的軟件同步升級。

?2)便于實現(xiàn)目標模塊的共享：通常被鏈接的共享代碼稱為動

態(tài)鏈接庫(DLL,Dynamic-LinkLibrary)或共享庫(sharedlibrary)o

實現(xiàn)多個模塊共享一個DLL而不要每個程序都含有該模塊的拷貝。

3)便于運行環(huán)境適應：調(diào)用不同的DLL,就可適應多種使用環(huán)

境和提供不同功能。如：不同的顯卡只需廠商為其提供特定DLL,

而OS和應用程序不必修改。

缺點：

每次都要鏈接裝入所有的模塊，不論是否用到。

例如：IFv條件〉THENS1ELSES2;

3.運行時動態(tài)鏈接

I一開始只鏈接裝入部分模塊，在運行過程中，若發(fā)現(xiàn)被調(diào)用模塊

■不在內(nèi)存，則發(fā)出請求，由OS查找、裝入并鏈接到調(diào)用模塊。

0

裝入

printf(uOK");call33600H

執(zhí)行

主模塊

voidprintf(...)33600H

內(nèi)存

庫模塊

通常鏈接和裝入是一體的，其發(fā)展過程可分為三個階段:

1.靜態(tài)鏈接、靜態(tài)裝入2.靜態(tài)鏈接、動態(tài)裝入

3.動態(tài)鏈接、動態(tài)裝入

§4.3連續(xù)分配方式

ContiguousMemoryAllocation

連續(xù)分配指為用戶程序分配一個連續(xù)的內(nèi)存空間。

Q-、單一連續(xù)分配

ca二、分區(qū)式分配

一、單一連續(xù)分配

SingleContinuousAllocation

物

。內(nèi)存分為兩個區(qū)域：系統(tǒng)區(qū)，用戶區(qū)。

。單一連續(xù)分配：內(nèi)存中僅駐留一道程序，整個用戶區(qū)為一個

用戶獨占。

內(nèi)存的保護

為了防止os受到用戶程序有意或無意的破壞，可以設置

保護機構(gòu)：如基址（重定位）寄存器和界限寄存器。

二、分區(qū)式分配

PartitionAllocation

為了支持多道程序運行，提出了分區(qū)式分配存儲管理

方式。該方式中，內(nèi)存用戶區(qū)共多個用戶程序使用，劃分

成若干分區(qū)，每個分區(qū)容納一個作業(yè)。按照分區(qū)的劃分和

分配方式，常見的分區(qū)式分配有如下幾種：

。固定分區(qū)分配

O動態(tài)分區(qū)分配

O可重定位分區(qū)分配

?；锇橄到y(tǒng)

A

1、固定分區(qū)分酉己(FixedPartitionAllocation)

\7

1）基本原理：將內(nèi)存空間分為若干個固定大小的區(qū)域，每

個分區(qū)裝入一道作業(yè)。劃分通常是在系統(tǒng)初使化時執(zhí)行。

2）劃分分區(qū)的方法

口分區(qū)大小相同：主要用于控制多個相同對象的場合。即各

處理對象的大小基本相同。

口分區(qū)大小不同：一般可劃分多個小分區(qū)，適量中等分區(qū)，

少量大分區(qū)?？蛇m應多種類型的作業(yè)。

3）內(nèi)存分配

□數(shù)據(jù)結(jié)構(gòu)：將分區(qū)按大小順序排列；建立一張分區(qū)使用表,

包含分區(qū)起始地址、大小、狀態(tài)等。

□分配過程：有內(nèi)容要裝入時，在分區(qū)使用表中查找大小能

滿足且未分配出去的分區(qū)，若找到，則實施分配且修改分

區(qū)表中的狀態(tài)。否則，拒絕分配。

例如：主存分配表

分區(qū)號起始地址長度占用標志

0S(8K)

18K16K0

用戶分區(qū)1(16K)

224K16K0

用戶分區(qū)2(16K)

340K32KJdbl

__________________________________________________________________________

內(nèi)存中已分配給作業(yè)但未被利用的區(qū)域稱

為“內(nèi)零頭”(internalfragment)

固定分區(qū)分配會有內(nèi)零頭產(chǎn)生。

固定分區(qū)分配方法小結(jié)

。優(yōu)點：簡單。

。缺點：

9實際系統(tǒng)運行時，往往無法預知分區(qū)大?。ㄌ?，等同

于“單用戶分區(qū)模式”）；

9主存空間利用率仍然較低；

6分區(qū)數(shù)目預先確定，限制了多道運行程序的數(shù)量。

如今，幾乎沒有哪一種操作系統(tǒng)支持這種模式。

A

2、動態(tài)分區(qū)分配(DynamicPartitionAllocation)

\)

1）基本原理：內(nèi)存不預先劃分好，當進程裝入時，根據(jù)進

程的需求和內(nèi)存空間的使用情況來決定是否分配。

口若空間足夠，則按需要動態(tài)為之分配連續(xù)的內(nèi)存空間；

□否則，令其等待主存空間例如：

。在實現(xiàn)動態(tài)分區(qū)分配存儲管理方式時，必須解決下述

三個問題：

?動態(tài)分區(qū)分配中的數(shù)據(jù)結(jié)構(gòu)；

分區(qū)分配算法；

分區(qū)的分配和回收。

2）動態(tài)分區(qū)分配中的數(shù)據(jù)結(jié)構(gòu)

系統(tǒng)必須記錄內(nèi)存的使用情況，為分配提供依據(jù)。

?1）空閑分區(qū)表：用表記

錄內(nèi)存中的所有空閑分區(qū)。每

一分區(qū)占一表目。可包括序號、

大小、始址等。

?2）空閑分區(qū)鏈：用鏈方

式記錄每一空閑分區(qū)。鏈上每

一分區(qū)中存儲有指向前后分區(qū)

的指針及本分區(qū)的大小、狀態(tài)

（0表示可用，1表示已用）。

空閑分區(qū)鏈結(jié)點示意圖

0

操作系統(tǒng)空閑分區(qū)表

400K

區(qū)號起始地址長度

1900K100K

900K

21700K300K

1000K

32300K260K

1700K空閑分區(qū)鏈

2000K0

900K1700K2300K

2300K100K300K260K

000NULL

2560K

3)動態(tài)分區(qū)分配算法

將作業(yè)裝入內(nèi)存時，選擇哪個的內(nèi)存分區(qū)進行分配。

常用的算法有如下幾種：

O首次適應算法(First-FitAlgorithm)

O循環(huán)首次適應算法Next-fitAlgorithm)

O最佳適應算法(Best-fitAlgorithm)

O最壞適應算法(Worst-fitAlgorithm)

O快速適應算法(Quick?fitAlgorithm)(作業(yè))

■II.首次適應算法(First-FitAlgorithm)

■■■■■■■■■■■■

?要求：空閑分區(qū)以地址遞增的次序鏈接。

?分配：從鏈首順序查找，直至找到一個能滿足大小的空閑

分區(qū)為止。按需要對其進行劃分，分配、保留。例：

?傾向：利用低址分區(qū)。

?:?優(yōu)點：分區(qū)組織簡單；高址部分可容納大作業(yè)。

。缺點：低址處外零頭(externalfragment)多，查找

越來越困難。

例如:

系統(tǒng)中的空閑分區(qū)表如下，現(xiàn)有三個作業(yè)分配申請內(nèi)存空間

100K、30K及7K。給出按首次適應算法的內(nèi)存分配情況及分配后

空閑分區(qū)表。

區(qū)號大小起址

空

12k50k閑

2分

1k59k區(qū)

320k160k表

4331k180k

解：按首次適應算法,

申請作業(yè)100k,分配3號分區(qū)，剩下分區(qū)為20k,起始地址160K；

申請作業(yè)30k,分配1號分區(qū)，剩下分區(qū)為2k,起始地址50K；

申請作業(yè)7k,分配2號分區(qū)，剩下分區(qū)為:1k,起始地址59K；

01。

A外零頭

1

2

3

在低地址部分會

積累大量外零頭

"III.循環(huán)首次適應算法(Next-fitAlgorithm)

■一一.*

0要求：空閑分區(qū)以地址遞增的次序鏈接；且做成環(huán)形。設

置一個起始查尋指針。

0分配：從上次找到的空閑分區(qū)的下一個分區(qū)開始查找，直

至找到一個能滿足大小要求的空閑分區(qū)。劃分。例i_

O傾向：平衡利用內(nèi)存。

優(yōu)點：空閑分區(qū)組織簡單；查找簡單。

?缺點：無大的空閑分區(qū)，難滿足大作業(yè)的要求。

例如：

系統(tǒng)中的空閑分區(qū)表如下，現(xiàn)有三個作業(yè)分配申請內(nèi)存空間

100K、30K及7K。給出按循環(huán)首次適應算法的內(nèi)存分配情況及分

配后空閑分區(qū)表。

區(qū)號大小起址

起始查詢指針

125k27k

28k52k

320k160k

4301k210k

解：按循環(huán)首次適應算法，

申請作業(yè)100k,分配3號分區(qū),剩下分區(qū)為20k,起始地址160K；

申請作業(yè)30k,分配4號分區(qū),剩下分區(qū)為301k,起始地址210K；

申請作業(yè)7k,分配1號分區(qū),剩下分區(qū)為25k,起始地址27K；

Ill,最佳適應算法(Best-fitAlgorithm)

。要求：空閑分區(qū)按大小從小到大進行鏈接。

9分配：從鏈表頭進行順序查找，直至第一個大小能滿足的

分區(qū)。則為能滿足且最接近需要大小的分區(qū)。劃分。

例如：

優(yōu)點：避免“大材小用”。

缺點：外零頭嚴重；分區(qū)組織、回收復雜。

??0

例如：

系統(tǒng)中的空閑分區(qū)表如下，現(xiàn)有三個作業(yè)分配申請內(nèi)存空間

100K、30K及7K。給出按最佳適應算法的內(nèi)存分配情況及分配后空

閑分區(qū)表。

區(qū)號大小起址

11k59k

22k50k

320k160k

4331k180k

解：按最佳適應算法,

申請作業(yè)100k,分配3號分區(qū),剩下分區(qū)為20k,起始地址160K；

申請作業(yè)30k,分配3號分區(qū)，剩下分區(qū)為2k,起始地址50K；

申請作業(yè)7k,分配2號分區(qū)，剩下分區(qū)為:Lk,起始地址59K；

IV.最壞適應算法(Worst-fitAlgorithm)

o要求：空閑分區(qū)按從大到小鏈接。

o分配：從頭順序查找，找到大小能滿足的。則為能滿足且

劃分后剩余空間最大的分區(qū)。劃分。例如：

優(yōu)點：外零頭較少。

缺點：難滿足大作業(yè)的要求；分區(qū)組織、空閑分區(qū)回

收復雜。

囪

例如:

系統(tǒng)中的空閑分區(qū)表如下，現(xiàn)有三個作業(yè)分配申請內(nèi)存空間

100K、30K及7K。給出按最壞適應算法的內(nèi)存分配情況及分配后

空閑分區(qū)表。

區(qū)號大小起址

空

1194k317k閑

2120k60k分

區(qū)

332k20k表

48k52k

解：按最壞適應算法，

申請作業(yè)100k,分配1號分區(qū),剩下分區(qū)為231k,起始地址280K；

申請作業(yè)30k,分配1號分區(qū)，剩下分區(qū)為201k,起始地址310K；

申請作業(yè)7k,分配1號分區(qū)，剩下分區(qū)為194k,起始地址317K；

FF\BF\WF三種算法比較

分區(qū)分配算法的性能看其時間、空間復雜性而定。就算

法本身來說，它們的復雜性由排序（地址大小、空閑區(qū)大?。?/p>

和查找（查找所需自由區(qū)）兩項決定。

?搜索速度：FF最佳。BF或WF要求按空間大小進行排序，

因此速度較慢。

0回收過程：FF最佳，因為FF算法回收時不用改變空閑區(qū)位

置，只需修改大小和起始地址。

9空閑區(qū)：BF最佳。但某些情況下會降低內(nèi)存利用率。

0碎片：WF基于不留碎片空間為出發(fā)點。

FF\BF\WF三種算法比較（續(xù)）

上述三種分配算法各有利弊，好壞不能一概而論，應針

對具體作業(yè)序列來分析。

?對某作業(yè)序列來說，若某算法能將該作業(yè)中所有作業(yè)安置

完畢，則稱該算法對這一作業(yè)序列是合適的。

?對某一算法而言，若不能立即滿足作業(yè)序列的某一要求，

則該算法對該作業(yè)序列是不合適的。

FF算法以其簡單、快速特性，在實際的操作系統(tǒng)中用得較

多；其次是最佳適應算法。

4)動態(tài)分區(qū)的分配和回收

動態(tài)分區(qū)管理方式中，主要操作是內(nèi)存分配和回收。

I.分配內(nèi)存MemoryAllocation)

□①按某種算法根據(jù)請求的大小，在表或鏈中進行查找合適

空閑區(qū)；

□②找不到則結(jié)束；找到則劃分。為減少外零頭，可設一下

限。若劃分后零頭小于該下限，則不劃分直接分配。

口③修改相應的數(shù)據(jù)結(jié)構(gòu)。

u.size:請求的分區(qū)大?。?/p>

m.size:表中每個空閑分區(qū)的大?。?/p>

size:事先規(guī)定的不再切割的剩余分區(qū)的大小。

存在內(nèi)零頭

將分區(qū)分配給用戶，從空閑分區(qū)表（鏈）中移出

II.回收內(nèi)存(ReturnMemory)

當內(nèi)存運行完畢釋放內(nèi)存時，系統(tǒng)根據(jù)回收區(qū)的首址

在相應的數(shù)據(jù)結(jié)構(gòu)中查找插入點。

此時可能出現(xiàn)四種情況之一：

①回收區(qū)上鄰接一個空閑分區(qū)：合并、改大小。

②回收區(qū)下鄰接一個空閑分區(qū)相鄰：合并、改始址、大小。

③回收區(qū)上下鄰接區(qū)相鄰：合并、共用上空閑分區(qū)首址、改

大小、取消下空閑分區(qū)。

④回收區(qū)不鄰接空閑分區(qū)：單獨建一表項。

回收內(nèi)存舉例

Pl運行結(jié)束

P1所占分區(qū)的上下都不空閑，在空閑

分區(qū)鏈中添加一項

P3運行結(jié)束

P3所占分區(qū)下邊的分區(qū)F1空閑，應進行合并。

在空閑分區(qū)鏈中找到F1節(jié)點，修改其起始地

址和長度

P2運行結(jié)束

P2所占分區(qū)上邊的分區(qū)Fl空閑，應進行

合并。在空閑鏈表中找到F1節(jié)點，修改

其長度

P1運行結(jié)束

P1所占分區(qū)上下邊的分區(qū)F1和F2都空閑，

應進行合并。在空閑鏈表中找到F1節(jié)點，修

改其長度為Fl、F2和P2所占分區(qū)的長度和。

刪除F2節(jié)點

動態(tài)分區(qū)分配舉例:

某計算機有2560K內(nèi)存，采用可變分區(qū)模式管理內(nèi)

存，操作系統(tǒng)占用低地址的400K空間，剩余2160K的空

間為用戶區(qū)。分區(qū)分配采用首次適應算法。

最初整個用戶區(qū)為空閑，即只有一個分區(qū)。隨著用

戶程序的創(chuàng)建和撤銷，分區(qū)的個數(shù)和大小位置開始變化。

分配回收過程如下所示：

內(nèi)存的初始狀態(tài)P1來，600K

0

P2來，1000K

400K

P3來，300K

900K

1000K

P2結(jié)束］

P4來，700K

1700K

Pl結(jié)束;

2000K

P5來，500K

2300K

P4結(jié)束

2559K

3、可重定位分區(qū)分配

Relocatablepartitionallocation

\7

1）引入

動態(tài)分區(qū)分配中，經(jīng)多次劃分后，常會出現(xiàn)大量的太小

而無法利用的區(qū)域（外零頭）。為了充分利用內(nèi)存空間，可

采用緊湊（compaction）技術(shù)。

緊湊：將內(nèi)存中的作業(yè)進行移動，使它們相鄰接，將分

散的小分區(qū)拼接成一個大分區(qū)，從而利于作業(yè)的裝入。

（以時間換空間）

緊湊后的作業(yè)在內(nèi)存中位置發(fā)生了變化，則應對其中程序、

數(shù)據(jù)等的地址做相應的修改，即重定位。

(a)

(a)緊湊前;(b)緊湊后

二章褊轆百

2）動態(tài)重定位的實現(xiàn)

TheimplementationofdynamicRelocation

。為支持作業(yè)在內(nèi)存中的移動，應采用動態(tài)運行時裝入方式。

。因此，允許作業(yè)在運行過程中在內(nèi)存中移動的技術(shù)，必須獲

得硬件地址變換機構(gòu)的支持。

■在系統(tǒng)中設置一個重定位寄存器。用于存放作業(yè)在內(nèi)存

中的起始地址。

■運行時，相對地址執(zhí)行：

物理地址=重定位寄存器+相對地址

得到它在內(nèi)存中的實際地址。如圖所示.

緊湊時，只需修改重定位寄存器值，使之存放新起始地址。

G二

匚二

不“

3）可重定位分區(qū)分配算法

DynamicRelocationPartitionAllocationAlgorithm

動

態(tài)

分

區(qū)

分

配

算

法

流

程

修改有關的修改有關的"返回分區(qū)號

數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)\及首址

可重定位分區(qū)分配小結(jié)

。優(yōu)點：

9消除內(nèi)存碎片，提高內(nèi)存利用率。

。缺點：

提高硬件成本。

緊湊時花費CPU時間，開銷大。

緊湊的時機

☆進程結(jié)束，釋放分區(qū)時，如不與空閑區(qū)相鄰，則緊湊,

保持空閑區(qū)連續(xù)，花費多。

☆分配進程分區(qū)時，若不滿足，則緊湊?？臻e區(qū)管理復

雜。

r

4.伙伴系統(tǒng)(BuddySystem)

固定分區(qū)和動態(tài)分區(qū)方式都有不足之處。伙伴系統(tǒng)方式是

對以上兩種內(nèi)存方式的一種折衷方案。

?；锇橄到y(tǒng)規(guī)定：

?1）內(nèi)存分區(qū)大小均為2的k次塞，k為整數(shù)（I0陋m）,其中：21

表示分配的最小分區(qū)的大小，2m表示最大分區(qū)的大小，通常為系

統(tǒng)開始運行時可分配內(nèi)存的大小。

?2）該方法通過不斷劃分大的空閑區(qū)來獲得小的空閑區(qū)，直到

獲得所需內(nèi)存塊?？臻e塊的分配和合并均使用2的幕次方算法。

。3）當一個空閑塊被對分后，其中一部分稱為另一部分的伙伴。

日?；锇橄到y(tǒng)空閑塊的組織

空閑分區(qū)根據(jù)分區(qū)的大小進行分類，對于每?類具仃相同

大小的所有空閑分區(qū)，單獨設立一個空閑分區(qū)雙向鏈表。這樣,

不同大小的空閑分區(qū)形成了k（O0聯(lián)m）個空閑分區(qū)鏈表。

”與=4

?□G

亍三—三

O伙伴系統(tǒng)內(nèi)存的分配和回收

1Mblock

Request100K

Request240K

Request64KA=128KB=256K512K

FrF

Request256KA=128K64KB=256KD=256K256K

RelesetBA=128K64K256KD=256K256K

RelesetA64K256KD=256K256K

F

Request75KE=128K64K256KD=256K256K

1M

?；锇橄到y(tǒng)內(nèi)存的分配和回收（續(xù)）

伙伴系統(tǒng)小結(jié)

。Easytopartition

。Easytocombine

0Internalfragmentationexisting,No

externalfragmentation

。ThebuddysystemisusedforLinuxkernel

memoryallocation.

在內(nèi)存分區(qū)分配中考慮兩個問題:

割1、若進程在運行過程中長度發(fā)生變化。

則如果鄰接內(nèi)存區(qū)域為空白，可再分配。若鄰接為

一進程，則需要移動、等待、交換或撤銷。

割2、作業(yè)調(diào)度時內(nèi)存空間是否滿足。

因此，作業(yè)調(diào)度算法應同分區(qū)內(nèi)存管理相結(jié)合。即

在考慮調(diào)度順利時，還要考慮到內(nèi)存空間是否能滿足。

ra例如：

―主存總?cè)萘繛?57K,OS占40K。系統(tǒng)采用FCFS作業(yè)調(diào)度,

進程調(diào)度采用時間片(5§)輪轉(zhuǎn)。

作業(yè)到來次序所需存儲量運行時間

160KB10s

2100KB5s

330KB20s

470KB8s

550KB15s

03940256

三、對換(Swapping)

1.

對換是提高內(nèi)存的利用率的有效措施。

■?原理：暫停執(zhí)行內(nèi)存中的進程，修要換出的進程的地

址空間保存到外存的對換區(qū)中（換出），而將外存中由阻塞變

為就緒的進程的地址空間讀入內(nèi)存，并將該進程送到就緒隊列

（換入）。

?實現(xiàn)：可在系統(tǒng)中設一對換進程，以執(zhí)行換進內(nèi)存、

換出至外存操作。對換是系統(tǒng)行為

?分類：

'O1)“整體對換”或“進程對換”。對換以整個進程為單位,

用于分時系統(tǒng)，以解決內(nèi)存緊張，提高內(nèi)存利用率。

02)“頁面對換”或“分段對換”。對換以“頁”或“段”

為單位進行“部分對換”。支持虛存系統(tǒng)。

?系統(tǒng)提供的功能：為實現(xiàn)對換，系統(tǒng)需要三方面的功能：

。對換空間的管理(ManagementofSwappingSpace)

O進程的換入(SwapinofProcess)

O進程的換出(SwapoutofProcess)

2.對換空間的管理

(ManagementofSwappingSpace)

\____________________________________________________________________________

引入對換后，外存被分為兩部分：文件區(qū)和對換區(qū)。

文件區(qū)：用于存放文件，其管理目標為提高存儲空間的利

用率。因此采取離散分配方式。

*口即一個文件可根據(jù)當前外存的使用情況，被分成多塊,]

較夕分別存到不鄰接的多個內(nèi)存存儲區(qū)域中。熨

度。因此采用連續(xù)分配方式。

濤腳換鹵蹄攤蠅踴幫隨動慈繡位畫僧爵岷8

3.進程的換入與換出

(SwapinandSwapoutofProcess)

\7

進程的換入和換出由對換進程完成。

?:*(1)進程的換出

A實質(zhì)：把活動阻塞、就緒狀態(tài)的進程轉(zhuǎn)掛起狀態(tài)。

A步驟：換出過程分以下兩步：

stepl.選擇被換出的進程

《處于阻塞狀態(tài)的、優(yōu)先級最低的進程。

力無阻塞：選擇優(yōu)先級低的就緒進程。

力考慮優(yōu)先級低產(chǎn)生“換進、再換出”，兼顧內(nèi)存駐留時

間。

力非共享的程序和數(shù)據(jù)段。若為共享，只能引用數(shù)為零后

才能被換出。

step2.換出過程

9①申請對換空間，成功則執(zhí)行②，否則，重新選擇;

9②將程序和數(shù)據(jù)寫入對換區(qū)，檢查寫入的正確性；

?、蹮o誤，則調(diào)用釋放內(nèi)存過程，釋放原內(nèi)存；

9④修改PCB、內(nèi)存分配表等；

?、萑魞?nèi)存仍不足或仍有可換出進程，則回到①

(2)進程的換入

＞實質(zhì)：把掛起狀態(tài)■＞活動就緒或阻塞。

＞步驟：換入過程分以下兩步：

stepl.選擇換入進程

9有足夠的內(nèi)存空間；

9“就緒掛起”優(yōu)先于“阻塞掛起”；

9同一隊列中，優(yōu)先級高、掛起時間長的優(yōu)先換入。

step2.換入過程

9①從PCB集合中查找“就緒且換出”的進程，有多個，

則選擇換出時間最長的。

《②根據(jù)進程大小申請內(nèi)存，成功則讀入，否則要先執(zhí)行換

出，再換入。

?、廴暨€有可換入進程，則轉(zhuǎn)向①。直至無“就緒且換出”

進程或無法獲得足夠內(nèi)存空間為止。

離散內(nèi)存分配方式

<y

把用戶的程序空間劃分成若干部分（化整為零），它們可

以離散分配到內(nèi)存中非連續(xù)的存儲區(qū)域中，充分利用內(nèi)存。即

離散分配方式。

根據(jù)程序劃分時的基本單位不同，可分為三種：

O基本分頁存儲管理方式

O基本分段存儲管理方式

O段頁式存儲管理方式

§44基本分頁存儲管理方式

lasicPagedMemoryManagement

ca一、基本分頁存儲管理原理

ca二、基本概念

三、內(nèi)存分配和回收

caI、地址變換

ca五、兩級和多級頁表朱

■一、基本分頁存儲管理原理

□將程序的邏輯地址空間劃分為固定大小的頁(頁面)

(pageorpageframe)；

□將物理內(nèi)存劃分為與頁面大小相等的物理塊(block)；

□程序加載時，按頁分配其所需的塊，連續(xù)頁面所分得物

理塊不必連續(xù)。

□需要CPU的硬件支持。

基本分頁存儲管理示意圖

0

頁1

表2

頁號塊號

3

04

4

16

225

386

4號塊

7

45（塊長2K）

518

6109

6頁內(nèi)碎片

11

口。"3內(nèi)存需二章魏

二、基本概念(BasicConcept)

/X

1.頁面和物理塊(pageandblock)

\7

把用戶程序的邏輯地址空間劃分成若干大小相等的

“頁”，各頁從。開始依次編頁號0,L2,....

頁內(nèi)地址相對于0編址。因此，分頁系統(tǒng)中，每個邏輯地

址都可用二元組(頁號，頁內(nèi)地址)表示。

把內(nèi)存空間劃分成若干和“頁”大小相同的塊，稱為

物理塊(Block)或頁框(frame)。同樣為它們編號0,1……。

物理地址同樣用二元組(塊號，塊內(nèi)地址)表示。

2.頁面大小(PageSize)

。分頁系統(tǒng)中頁面大小由機器地址結(jié)構(gòu)決定，因此，機器的

頁面大小固定。用戶程序頁面劃分由系統(tǒng)自動完成，一般

為2的整數(shù)次賽。例如，舊MAS/400的頁面大小為512B。

。小頁面

?:?優(yōu)點：減少碎片，提高內(nèi)存利用率。

?:?缺點：頁表過長，占用較多內(nèi)存空間。且以頁為單位進

行換進、換出時效率低。

。大頁面

?:?優(yōu)點：頁表小，換進換出時效率高。

?:?缺點：頁內(nèi)碎片相應較大。

O頁面的大小通常在512B~4KB之間。

3.邏輯地址形式(LogicAddress)

\7

。在分頁存儲管理方式中，程序經(jīng)過頁面劃分后，任一個

邏輯地址都可轉(zhuǎn)變（頁號，頁內(nèi)位移量）。

。如：一個32位的邏輯地址，可轉(zhuǎn)化為如下方式:

編號0?1048575相對地址0T095

■。邏輯地址轉(zhuǎn)換過程：

邏輯地址A,在分頁存儲管理方式中，需要被轉(zhuǎn)換成（頁

號，頁內(nèi)偏移）二元組地址形式。

若頁面大小為L,則轉(zhuǎn)換過程為：

頁號P=INT[A/L]；頁內(nèi)位移量W=AMODL

變換通常由系統(tǒng)中的某些硬件完成（MMU,內(nèi)存管理單元）

例如：有邏輯地址為：2170,頁面大小為1KB,則

P=INT[2170/1024]=2；W=2170MOD1024=122

地諦若邏輯地址為二進制呢？

問?

I??B494?1■????I?flB??4Bfl?I■??4■??i??B494?IBt????BflB?B4B4B4■■■■1i?fl■>

設有一頁式存儲管理系統(tǒng)，向用戶提供的邏輯地址空

間最大為16頁，每頁2048字節(jié)，內(nèi)存總共有8個存儲塊，

試問邏輯地址至少應為多少位？內(nèi)存空間有多大？

山

三、內(nèi)存的分配與回收

MemoryAllocationandReturn

1.數(shù)據(jù)結(jié)構(gòu)(DataStructer)

1)進程頁表/頁表(PageTable)

□作用：描述進程頁面存放在內(nèi)存中所對應的物理塊。

口內(nèi)容：頁表中主要包括頁號、物理塊號。還可有存取控

制字段，實現(xiàn)對存儲塊中內(nèi)容的保護。如二

口注意：每個進程一個頁表。全部頁表集中存放在內(nèi)存的

系統(tǒng)專用區(qū)中，只有系統(tǒng)有權(quán)訪問頁表，保證安全。例」

近2）虛空間表（作業(yè)表）：記錄進程空間的情況。一個進程

一個表項。記錄進程頁表在內(nèi)存的存放情況。全系統(tǒng)僅1張。

3）空閑塊表：記錄內(nèi)存當前空閑塊，全系統(tǒng)1張。

O31

O空

塊

1管

理

——

…

…

位

示

7圖

章

需

二

一

問?

1、進程頁表放在哪兒？內(nèi)存I

2、進程頁表的首地址和長度放在哪兒？

進程PCB

需口章筋

2.內(nèi)存分配過程(MemoryAllocation)

J

3.內(nèi)存回收過程(MemoryReturn)

y

?：?根據(jù)進程頁表的內(nèi)容，把空閑塊表中對應的物理頁改為

空閑；

*撤銷該進程的進程頁表。

四、地址變換

AddressTransformMechanism

?一—_Q

物

用

理

戶MOVA,8279

內(nèi)

程

存

序

空

間

頁號到物理塊號的轉(zhuǎn)換，借助頁表。

1.基本地址變換機構(gòu)

(BasicAddressTransformMechanism)

越界中斷

頁表寄存器PTR邏輯地址

分

頁

頁表始址頁表長度>=287系

統(tǒng)

的

地

頁號塊號址

變

01換