第四章落儲(chǔ)器管理

第四章存儲(chǔ)器管理

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

4.2程序的裝入和鏈接

43連續(xù)分配方式

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

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

4.6虛擬存儲(chǔ)器的基本概念

4.7請(qǐng)求分頁存儲(chǔ)管理方式

4.8頁面置換算法

4.9請(qǐng)求分段存儲(chǔ)管理方式

k士章商借器管理一q

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

4.1.1多級(jí)存儲(chǔ)器結(jié)構(gòu)

?1.存儲(chǔ)器功能

?合理、安全、有效地保存數(shù)據(jù)

?2.存儲(chǔ)器發(fā)展方向

?接口更新

-以硬盤為例：ESDI;IDE/EIDE;ATA;SATA/SATA2;SCSI;

IEEE1394;USB...

＞高速性

-以USB為例：USB1.1是12Mbps,USB2.0是480Mbps,USB3.0

理論上是5Gbps...

?存儲(chǔ)密度越來越高，體積越來越小

-1.7Mb/平方英寸；20Mb/平方英寸；1.43Gb/平方英寸；

135Gb/平方英寸；620Gb/平方英寸；1Tb/平方英寸…的不

第四章落儲(chǔ)器管理

--■

容量有望翻倍希捷達(dá)到存儲(chǔ)密度新紀(jì)錄

2012年03月21日00：00來源:/作者：ChrisR編輯:秋龍?jiān)u論：一條

[IT168資訊】希捷今日正式宣布，該公司成為第一家在存儲(chǔ)密度上達(dá)到1Tbit/平方英寸（1

terabit=ltrillionbit=l萬億bit）這一里程碑的哽盤廠商，新技術(shù)的應(yīng)用使得每平方英寸所記

錄的bit數(shù)量甚至超過了銀河系中的天體數(shù)量（約20007000億之間）?

希捷所采用的技術(shù)名為HAMR,即HeaLAssistedMagneticRecording（熱輔助磁記錄）。作

為目前耍盤采用的P股（PerpendicularMagneticRecording,垂直磁記錄技術(shù)的繼任者）,

HAMR的理論存儲(chǔ)密度為570Tbit/平方英寸。相比之下，目前的3.5英寸硬盤存儲(chǔ)密度為

620Gbit/平方英寸，2.5硬盤的存儲(chǔ)密度為500Gbit/平方英寸。

HAMR技術(shù)可輕松達(dá)到PMR技術(shù)的存儲(chǔ)密度極限一一1Tbit/平方英寸這一里程碑，比目前硬盤產(chǎn)

品的存儲(chǔ)密度高出55%左右。一旦HAMR得到實(shí)際應(yīng)用，目前3.5英寸硬盤產(chǎn)品的容量可輕松翻倍達(dá)

到6TB左右，2.5英寸硬盤的容量更是能提升至2TB。未來HAMR技術(shù)成熟后3.5英寸/2.5英寸硬盤的

容量更是可以達(dá)到目前服務(wù)器水平的30-60TB/10-20ITB。

3

第四章落儲(chǔ)器管理

A容量越來越大，價(jià)格越來越低

-以下是近年來關(guān)于硬盤價(jià)格的趣味數(shù)字

□1995年200MB?400MB大于4000元/GB

□1996年1.2GB?2.1GB1500元?2000/GB

□1998年1.2GB?2.1GB200元?250元/GB

□2000年4.3GB--6.4GB40元/GB

□2002年10GB-20GB20元/GB

□2004年40GB-80GB6.97U/GB

□2005年80GB-J60GB4.57U/GB

□2006年80GB-250GB3.8元/GB

□2008年160GB--1TB1.6元/GB

□2009年500GB--2TB0.8元/GB

□2010年500GB入-2TB0.6元/GB

第四章落儲(chǔ)器管理

■■單

位

容

速

量

成

度

本

圖4-1計(jì)算機(jī)系統(tǒng)存儲(chǔ)層次示意

第四章落儲(chǔ)器管理

?4.存儲(chǔ)管理功能

A存儲(chǔ)分配與回收

-本章主要內(nèi)容，討論其算法和數(shù)據(jù)結(jié)構(gòu)

A地址變換

-可執(zhí)行文件生成中的鏈接技術(shù)；程序裝入時(shí)的重定

位技術(shù)；進(jìn)程運(yùn)行時(shí)的地址變換技術(shù)和機(jī)構(gòu)（軟件、

硬件）

A存儲(chǔ)共享和保護(hù)

-代碼和數(shù)據(jù)共享；對(duì)地址空間的訪問權(quán)限（讀、寫、

執(zhí)行）

A存儲(chǔ)器擴(kuò)充

-由用戶應(yīng)用程序控制：覆蓋Overlay

-由OS控制：交換Swapping；請(qǐng)求調(diào)入和預(yù)調(diào)入On

Demand&OnPrefetch么-

w

第四章存儲(chǔ)器管理

4.1.2主存儲(chǔ)器與寄存器

?1.主存儲(chǔ)器

?主存儲(chǔ)器（簡(jiǎn)稱內(nèi)存或主存）是計(jì)算機(jī)系統(tǒng)中一

個(gè)主要部件，用于保存進(jìn)程運(yùn)行時(shí)的程序和數(shù)

據(jù)，也稱可執(zhí)行存儲(chǔ)器，材質(zhì)以DRAM為主。

由于主存儲(chǔ)器的訪問速度遠(yuǎn)低于CPU執(zhí)行指令

的速度，為緩和這一矛盾，在計(jì)算機(jī)系統(tǒng)中引

入了寄存器和高速緩存。

W

第四章落儲(chǔ)器管理

?2.寄存器

A寄存器訪問速度最快，完全能與CPU協(xié)調(diào)工作,

但價(jià)格卻十分昂貴，因此容量不可能做得很大。

寄存器的長(zhǎng)度一般以字(word)為單位。寄存器

的數(shù)目，對(duì)于當(dāng)前的微機(jī)系統(tǒng)和大中型機(jī)，可

能有幾十個(gè)甚至上百個(gè)；而嵌入式計(jì)算機(jī)系統(tǒng)

一般僅有幾個(gè)到幾十個(gè)。

A寄存器通常用于加速存儲(chǔ)器的訪問速度，如用

寄存器存放操作數(shù)，或用作地址寄存器加快地

址轉(zhuǎn)換速度等。

8

立章啟承器管理

4.1.3高速緩存和磁盤緩存

?1.高速緩存

?高速緩存是現(xiàn)代計(jì)算機(jī)結(jié)構(gòu)中的一個(gè)重要部件,

其容量大于或遠(yuǎn)大于寄存器，而比內(nèi)存約小兩

到三個(gè)數(shù)量級(jí)左右，從幾十KB到幾MB,訪問

速度快于主存儲(chǔ)器。

A根據(jù)程序執(zhí)行的局部性原理（即程序在執(zhí)行時(shí)將

呈現(xiàn)出局部性規(guī)律，在一較短的時(shí)間內(nèi)，程序

的執(zhí)行僅局限于某個(gè)部分），將主存中一些經(jīng)常

訪問的信息存放在高速緩存中，減少訪問主存

儲(chǔ)器的次數(shù)，可大幅度提高程序執(zhí)行速度。

W

上章卷儲(chǔ)器管理:一?

?2.磁盤緩存

?由于目前磁盤的I/O速度遠(yuǎn)低于對(duì)主存的訪問速

度，因此將頻繁使用的一部分磁盤數(shù)據(jù)和信息,

暫時(shí)存放在磁盤緩存中，可減少訪問磁盤的次

數(shù)。

1。

年］上章商儲(chǔ)器管理一?

4.2程序的裝入和鏈接''

?在多道程序環(huán)境下，要使程序運(yùn)行，必須先為之

創(chuàng)建進(jìn)程。而創(chuàng)建進(jìn)程的第一件事，便是將程序

和數(shù)據(jù)裝入內(nèi)存。如何將一個(gè)用戶源程序變?yōu)橐?/p>

個(gè)可在內(nèi)存中執(zhí)行的程序，通常都要經(jīng)過以下幾

個(gè)步驟：首先是要編譯，由編譯程序(Compiler)將

用戶源代碼編譯成若干個(gè)目標(biāo)模塊(Object

Module)；其次是鏈接，由鏈接程序(Linker)將編

譯后形成的一組目標(biāo)模塊，以及它們所需要的庫

函數(shù)鏈接在一起，形成一個(gè)完整的裝入模塊(Load

Module)；最后是裝入，由裝入程序(Loader)將裝

入模塊裝入內(nèi)存。圖4-2示出了這樣的三步過程。

本節(jié)將扼要闡述程序(含數(shù)據(jù))的鏈接和裝入過程。

11F

第四章落儲(chǔ)器管理

庫函數(shù)

Lib

源

程

程

序

員

序

C

裝入

模塊

.EXE

圖4-2對(duì)用戶程序的處理步驟

第回章存儲(chǔ)器管理

4.2.1程序的鏈接

A鏈接：若干目標(biāo)模塊+庫函數(shù)”可裝入模塊

?根據(jù)鏈接時(shí)間的不同，可把鏈接分成如下三種：

-(1)靜態(tài)鏈接。在程序運(yùn)行之前，先將各目標(biāo)模塊及

它們所需的庫函數(shù)，鏈接成一個(gè)完整的裝配模塊，

以后不再拆開。我們把這種事先進(jìn)行鏈接的方式稱

為靜態(tà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í)，才對(duì)它進(jìn)行*

的鏈接。二

13

第四章落儲(chǔ)器管理

?1.靜態(tài)鏈接方式(StaticLinking)

A在生成可裝入模塊時(shí)(也就是在程序裝入運(yùn)行前)

完成的鏈接。見圖4-4

?特點(diǎn)：

-一次鏈接，n次運(yùn)行

-得到完整的可裝入模塊，不可再拆

-不靈活：不管有用與否的模塊都將鏈接到裝入模塊，

同時(shí)導(dǎo)致內(nèi)存利用率較低

-不利于模塊的修改和升級(jí)

14

■第四章存儲(chǔ)器管理

0模塊A0模塊A

CALLB;

JSR"L”一

L-1Return;

L-1Return;

L

0模塊B模塊By

CALLC;JSR"L+M”一

M-lReturn;L+M-lReturn;

L+M模塊C-

0模塊C

L+M+N-lReturn;

N-lReturn;

(a)目標(biāo)模塊(b)裝入模塊

圖4-4程序鏈接示意圖

第四章落儲(chǔ)器管理

?2.裝入時(shí)動(dòng)態(tài)鏈接(Load-timeDynamic

Linking)

A用戶源程序經(jīng)編譯后所得的目標(biāo)模塊，是在裝

入內(nèi)存時(shí)邊裝入邊鏈接的，即在裝入一個(gè)目標(biāo)

模塊時(shí)，若發(fā)生一個(gè)外部模塊調(diào)用事件，將引

起裝入程序去找出相應(yīng)的外部目標(biāo)模塊，并將

它裝入內(nèi)存，還要按照?qǐng)D4-4所示的方式來修改

目標(biāo)模塊中的相對(duì)地址。

16

W

?3.運(yùn)行時(shí)動(dòng)態(tài)鏈接(Run-timeDynamicLinking)

＞裝入時(shí)動(dòng)態(tài)鏈接是將所有可能要運(yùn)行到的模塊都全部

鏈接在一起并裝入內(nèi)存，顯然這是低效的，因?yàn)橥?/p>

會(huì)有些目標(biāo)模塊根本就不運(yùn)行。比較典型的例子是作

為錯(cuò)誤處理用的目標(biāo)模塊，如果程序在整個(gè)運(yùn)行過程

中都不出現(xiàn)錯(cuò)誤，則顯然就不會(huì)用到該模塊。

＞運(yùn)行時(shí)動(dòng)態(tài)鏈接方式是對(duì)裝入時(shí)鏈接方式的一種改進(jìn)。

這種鏈接方式是將對(duì)某些模塊的鏈接推遲到程序執(zhí)行

時(shí)才進(jìn)行鏈接，亦即，在程序執(zhí)行過程中，當(dāng)發(fā)現(xiàn)一

個(gè)被調(diào)用模塊尚未裝入內(nèi)存時(shí)，才立即由OS去找到該

模塊并將之裝入內(nèi)存，把它鏈接到調(diào)用者模塊上。凡

在本次執(zhí)行過程中未被用到的目標(biāo)模塊，都不會(huì)被調(diào)

入內(nèi)存和被鏈接到裝入模塊上，這樣不僅可加快程序

的裝入過程，而且可節(jié)省大量的內(nèi)存空間。

17

W

第四章卷儲(chǔ)器

?4.動(dòng)態(tài)鏈接方式的優(yōu)點(diǎn)

?便于共享

-多個(gè)進(jìn)程可共用一個(gè)DLL模塊，節(jié)省了內(nèi)存。

＞為部分裝入提供了條件（運(yùn)行時(shí)動(dòng)態(tài)鏈接）

-一個(gè)進(jìn)程可由若干DLL模塊構(gòu)成，按需裝入。

?便于模塊的修改和升級(jí)

-只要被修改模塊的接口不變，則該模塊的修改不會(huì)

引發(fā)其它模塊的重新編譯。

?改善了程序的可移植性

-可面向不同的應(yīng)用環(huán)境開發(fā)同一功能模塊的不同版

本，根據(jù)當(dāng)前的環(huán)境載入匹配的模塊版本。.

18"1^01

?5.動(dòng)態(tài)鏈接方式的缺點(diǎn)

A增加了程序執(zhí)行時(shí)的鏈接開銷。（每次運(yùn)行都需

鏈接）

A模塊數(shù)量眾多，增加了模塊的管理開銷。

第四章落儲(chǔ)器管理

4.2.2程序的裝入

?裝入：可裝入模塊（.EXE）”內(nèi)存進(jìn)程

?1.絕對(duì)裝入方式（AbsoluteLoadingMode）

?在編譯后、裝入前已產(chǎn)生了絕對(duì)地址（內(nèi)存地

址），裝入時(shí)不再作地址重定位，即：裝入內(nèi)

存前的虛擬地址==裝入內(nèi)存后的物理地址。

A絕對(duì)地址的產(chǎn)生：（1）由編譯器完成；（2）

由程序員編程完成。

A優(yōu)點(diǎn)：裝入過程簡(jiǎn)單，無需地址映射。

A缺點(diǎn)：不適于多道程序系統(tǒng)；過于依賴硬件結(jié)

構(gòu)；不易修改、不靈潔。

20

W

第四章存儲(chǔ)器管理

?2.可重定位裝入方式(RelocationLoading

Mode)

A可裝入模塊在被裝入到內(nèi)存中時(shí)，由裝入程序

來完成程序虛擬地址》內(nèi)存物理地址的變換

21

第四章落儲(chǔ)器管理

0

10000'「如果不進(jìn)行地址變:

換，那么這條指令

將無法取到正確的

100011000

LOAD1,2500LOAD1,2500U數(shù)值“365”，所以

=>\該指令中的地址應(yīng)

\該重定位為：

250012500

365365\LOAD1,12500>

15000

程序地址空間-

r1

圖4-3裝入內(nèi)存時(shí)的情況物理內(nèi)存空間

靜態(tài)地址重定位：

指令或數(shù)據(jù)的內(nèi)存地址MA

=該指令或數(shù)據(jù)的虛擬地址VA+該程序在內(nèi)存中的首地址BA

?第四章存儲(chǔ)器管理一一y?

A可重定位裝入的優(yōu)缺點(diǎn)：

-優(yōu)點(diǎn)：

口適用于多道程序系統(tǒng)，提高了內(nèi)存利用率；由于地址映射

規(guī)則簡(jiǎn)單，故在地址變換過程中無需硬件變換機(jī)構(gòu)的支持。

-缺點(diǎn)：

口任何進(jìn)程都要求連續(xù)的內(nèi)存空間；必須將全部模塊都裝入

且裝入后不能再移動(dòng)位置（因?yàn)闊o法實(shí)現(xiàn)動(dòng)態(tài)重定位）；不

支持虛擬存儲(chǔ)器技術(shù)；不易實(shí)現(xiàn)共享。

第四章落儲(chǔ)器管理

?3.動(dòng)態(tài)運(yùn)行時(shí)裝入方式(DynamicRun?

timeLoading)

A出于實(shí)際情況，程序在運(yùn)行過程中的內(nèi)存位置

可能經(jīng)常要改變，此時(shí)就應(yīng)采用動(dòng)態(tài)運(yùn)行時(shí)裝

入的方式。

A程序裝入內(nèi)存后并不立即進(jìn)行地址變換，而是

等到真正要執(zhí)行時(shí)才由硬件地址變換機(jī)構(gòu)來完

成地址變換，從而得到內(nèi)存物理地址。

24

W

第四章落儲(chǔ)器管理

“基址寄存器BR

外存程序一側(cè)存儲(chǔ)器一側(cè)主存

動(dòng)態(tài)地址重定位：

指令或數(shù)據(jù)的內(nèi)存地址MA

=該指令或數(shù)據(jù)的虛擬地址VA+重定位基址寄存器BR

25

?第四章存儲(chǔ)器管理一一y?

A動(dòng)態(tài)運(yùn)行時(shí)裝入的優(yōu)缺點(diǎn)：

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

□os可將一個(gè)進(jìn)程的不同部分分散存放在不連續(xù)的內(nèi)存空間;

可移動(dòng)進(jìn)程在內(nèi)存中的位置（由重定位基址寄存器反映移

動(dòng)情況）；提供了實(shí)現(xiàn)虛擬存儲(chǔ)器技術(shù)的基礎(chǔ)（可實(shí)現(xiàn)部分

模塊裝入）；有利于實(shí)現(xiàn)模塊共享。

-缺點(diǎn)

口動(dòng)態(tài)重定位需要硬件變換機(jī)構(gòu)的支持；實(shí)現(xiàn)較復(fù)雜。

第四章落儲(chǔ)器管理

4.3連續(xù)分配方式

連續(xù)分配方式是指一個(gè)進(jìn)程在內(nèi)存中必須占

用連續(xù)的存儲(chǔ)空間。典型的連續(xù)分配方式主要有:

單一連續(xù)分配、固定分區(qū)分配、動(dòng)態(tài)分區(qū)分配、

動(dòng)態(tài)重定位分區(qū)分配等。

4.3.1單一連續(xù)分配

?把內(nèi)存分為系統(tǒng)區(qū)和用戶區(qū)兩部分，系統(tǒng)區(qū)僅提

供給OS使用；用戶區(qū)是指除系統(tǒng)區(qū)以外的全部?jī)?nèi)

存空間，提供給用戶使用。

?優(yōu)點(diǎn)：簡(jiǎn)單，易于管理

?缺點(diǎn)：只能用于單用戶單任務(wù)OS；內(nèi)存利用率低,

毫無共享性可言。早已淘汰。

27

W

引入：分區(qū)存儲(chǔ)管理原理

①將內(nèi)存分為一些大小相等或不等的分區(qū)

(Partition),每個(gè)進(jìn)程可占用一個(gè)分區(qū)。

②適于多道程序系統(tǒng)，支持多個(gè)進(jìn)程并發(fā)執(zhí)行。

③出現(xiàn)了碎片問題

I.內(nèi)碎片：被占用分區(qū)的尾部未被利用的空間。

II.外碎片：在兩個(gè)被占用分區(qū)之間的難以利用的小

空閑分區(qū)。

④分區(qū)管理的數(shù)據(jù)結(jié)構(gòu)：分區(qū)表或分區(qū)鏈表。

⑤內(nèi)存緊湊(Compaction)：將各個(gè)已占用分區(qū)

向內(nèi)存某端移動(dòng)，從而使分散的各個(gè)小空閑分

區(qū)能相鄰，進(jìn)而合并為一個(gè)稍大的空閑分區(qū)。.

28

W

第四章落儲(chǔ)器管理

4.3.2固定分區(qū)分配

?1.把內(nèi)存劃分為若干個(gè)固定大小的分區(qū)，

分區(qū)的總數(shù)以及各個(gè)分區(qū)的大小都是恒定

值。

A各分區(qū)大小相等

-不靈活；對(duì)于小進(jìn)程而言，內(nèi)存利用率低，內(nèi)碎片

嚴(yán)重；對(duì)于大進(jìn)程而言，分區(qū)大小可能無法滿足需

要，導(dǎo)致無法裝入。

A各分區(qū)大小不等

-小分區(qū)、中等分區(qū)、大分區(qū)。適應(yīng)性較強(qiáng)，可以有

效提高內(nèi)存利用率。

29

W

立章啟承器管理

?2.固定分區(qū)的內(nèi)存分配

A為了便于內(nèi)存分配，通常將分區(qū)按大小進(jìn)行排

隊(duì)，并為之建立一張分區(qū)使用表，其中各表項(xiàng)

包括每個(gè)分區(qū)的起始地址、大小及狀態(tài)(是否已

分配)，見圖4-5(a)所示。

A當(dāng)有一用戶程序要裝入時(shí)，由內(nèi)存分配程序檢

索該表，從中找出一個(gè)能滿足要求的、尚未分

配的分區(qū)，將之分配給該程序，然后將該表項(xiàng)

中的狀態(tài)置為“已分配”；若未找到大小足夠

的分區(qū)，則拒絕為該用戶程序分配內(nèi)存。存儲(chǔ)

空間分配情況如圖4-5(b)所示。

第四章落儲(chǔ)器管理

操作系統(tǒng)

分區(qū)號(hào)大小/KB起址/KJB狀態(tài)20KB

進(jìn)程A(8K)

11220已分配32KB

進(jìn)程B(25K)

23232已分配64KJB

36464已分配進(jìn)程C(40K)

128KBJ

4128128未分配

(a)分區(qū)說明表

256KB

(b)存儲(chǔ)空間分配情況

圖4-5固定分區(qū)使用表

第四章落儲(chǔ)器管理

?3.固定分區(qū)分配的優(yōu)缺點(diǎn)

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

-由于各分區(qū)大小固定，故易于實(shí)現(xiàn)，管理開銷小。

?缺點(diǎn)

-內(nèi)碎片的問題不可避免，較大程序不易裝入，故內(nèi)

存利用率較低；分區(qū)數(shù)目固定也限制了進(jìn)程的并發(fā)

度。

第四章落儲(chǔ)器管理

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

?在動(dòng)態(tài)分區(qū)分配方式中，各個(gè)分區(qū)的大小

會(huì)在OS的管理下發(fā)生改變，分區(qū)總數(shù)也會(huì)

相應(yīng)地發(fā)生變化。

?1.分區(qū)分配中的數(shù)據(jù)結(jié)構(gòu)

?(1)空閑分區(qū)表：記錄所有空閑分區(qū)情況的二維

表分區(qū)號(hào)大小/KB起址/KB狀態(tài)

11820未分配

232242未分配

3150502未分配

4128750未分配

33

第四章落儲(chǔ)器管理

?(2)空閑分區(qū)

鏈：將所有

的空閑分區(qū)

鏈接成一個(gè)

雙向鏈，如

圖4-6所示。

「0：未分配

Y

-1：已分配

第四章商儲(chǔ)器管理

?2.分區(qū)分配算法

>1)首次適應(yīng)FF算法(FirstFit)

-空閑分區(qū)鏈以地址遞增的次序鏈接。在每次分配時(shí),

都從鏈?zhǔn)组_始順序查找，直至找到第一個(gè)大小能滿

足要求的空閑分區(qū)為止；然后再按照程序的大小，

從該分區(qū)中劃出一塊內(nèi)存空間分配給請(qǐng)求者，余下

的空閑分區(qū)仍留在空閑鏈中。若從鏈?zhǔn)字敝伶溛捕?/p>

不能找到一個(gè)能滿足要求的分區(qū)，則此次內(nèi)存分配

失敗，返回。

-特點(diǎn)：簡(jiǎn)單；高址內(nèi)存可保留較大的空閑分區(qū)；但

低址內(nèi)存會(huì)產(chǎn)生很多碎片分區(qū)；查找開銷大。

35

■第四章存儲(chǔ)器管理

A2)循環(huán)首次適應(yīng)NF算法(NextFit)

-該算法是由首次適應(yīng)FF算法演變而成的：分配空間

不再是每次都從鏈?zhǔn)组_始查找，而是從上次找到的

空閑分區(qū)的下一個(gè)空閑分區(qū)開始查找，如果達(dá)到鏈

尾則回到鏈?zhǔn)桌^續(xù)。

-特點(diǎn)：查找開銷小；空閑分區(qū)分布更均勻；但較大

分區(qū)難以保留。

>3)最佳適應(yīng)BF算法(BestFit)

-空閑分區(qū)鏈表以容量遞增為序組織，每次分配時(shí)從

鏈?zhǔn)撞檎遥瑢⒌谝粋€(gè)滿足空間要求的分區(qū)分配出去。

-特點(diǎn)：最接近按需分配原則；較大的分區(qū)容易保留;

但會(huì)產(chǎn)生很多難以利用的小碎片分區(qū)。

>4)最壞適應(yīng)WF算法(WorstFit)

-空閑分區(qū)鏈表以容量遞減為序組織，每次分配時(shí)從

鏈?zhǔn)撞檎遥瑢⒌谝粋€(gè)滿足空間要求的分區(qū)分配出去。

-特點(diǎn)：小碎片分區(qū)的問題得到了有效的解決；但大

分區(qū)也不易保留。

A最壞適應(yīng)算法與前面所述的首次適應(yīng)、循環(huán)首

次適應(yīng)、最佳適應(yīng)算法一起，統(tǒng)稱為順序搜索

法。

37

A5)快速適應(yīng)QF算法(QuickFit)

-該算法又稱為分類搜索法，是將空閑分區(qū)根據(jù)其容

量大小進(jìn)行分類，對(duì)于每一類具有相同容量的所有

空閑分區(qū)，單獨(dú)設(shè)立一個(gè)空閑分區(qū)鏈表，這樣，系

統(tǒng)中存在多個(gè)空閑分區(qū)鏈表，同時(shí)在內(nèi)存中設(shè)立一

張管理索引表，該表的每一個(gè)表項(xiàng)對(duì)應(yīng)了一種空閑

分區(qū)類型，并記錄了該類型空閑分區(qū)鏈表表頭的指

針。空閑分區(qū)的分類是根據(jù)進(jìn)程常用的空間大小進(jìn)

行劃分。

-優(yōu)點(diǎn)：查找效率高；不會(huì)對(duì)任何分區(qū)產(chǎn)生分割，所

以能保留大的分區(qū)；也不會(huì)產(chǎn)生內(nèi)存碎片。

-缺點(diǎn)：分區(qū)歸還主存的算法復(fù)雜，系統(tǒng)開銷較大;

多樣化的鏈表造成管理開銷大。

第四章落儲(chǔ)器管理

?3?分區(qū)分配操作

A1）分配內(nèi)存

-系統(tǒng)應(yīng)利用某種分配算法，從空閑分區(qū)鏈（表）中找

到所需大小的分區(qū)。設(shè)請(qǐng)求的分區(qū)大小為u.size,表

中每個(gè)空閑分區(qū)的大小可表示為m.size。若m.size-

u.sizeSsize（size是事先規(guī)定的不再切割的剩余分區(qū)的

大小），說明多余部分太小，可不再切割，將整個(gè)分

區(qū)分配給請(qǐng)求者；否則（即多余部分超過size）,從該

分區(qū)中按請(qǐng)求的大小劃分出一塊內(nèi)存空間分配出去,

余下的部分仍留在空閑分區(qū)鏈（表）中。然后，將分

配區(qū)的首址返回給調(diào)用者。圖4-7示出了分配流程。

39

第四章落儲(chǔ)器管理

圖4-7內(nèi)存分配流程

第四章落儲(chǔ)器管理

>2)回收內(nèi)存

-(1)回收區(qū)與插入點(diǎn)的前一個(gè)空閑分區(qū)F1相鄰接，見圖4-8(a)。

此時(shí)應(yīng)將回收區(qū)與插入點(diǎn)的前一分區(qū)合并，不必為回收分區(qū)分

配新表項(xiàng)，而只需修改其前一分區(qū)F1的大小。

-(2)回收分區(qū)與插入點(diǎn)的后一空閑分區(qū)F2相鄰接，見圖4-8(b)。

此時(shí)也可將兩分區(qū)合并，也不必分配新表項(xiàng)，用回收區(qū)的首址

作為新空閑區(qū)的首址，大小為兩者之和。

-(3)回收區(qū)同時(shí)與插入點(diǎn)的前、后兩個(gè)分區(qū)鄰接，見圖4-8(c)。

此時(shí)將三個(gè)分區(qū)合并，使用Fl的表項(xiàng)，F(xiàn)1的首址不變，F(xiàn)1的

大小為三者之和，刪除F2的表項(xiàng)。

-(4)回收區(qū)既不與F1鄰接，又不與F2鄰接，見圖4-8(d)。這時(shí)應(yīng)

為回收區(qū)單獨(dú)建立一新表項(xiàng)，填寫回收區(qū)的首址和大小，并根

據(jù)其首址插入到空閑鏈中的適當(dāng)位置。

41

w

第四章落儲(chǔ)器管理

(a)(b)(d)

第四章落儲(chǔ)器管理

■例：假設(shè)最佳適應(yīng)法

OS(20K)

進(jìn)程A(8K)

16K空閑區(qū)

進(jìn)程D(50K)

138K空閑區(qū)

進(jìn)程E(16K)

8K空閑區(qū)

如果改為首次適應(yīng)算法?

43

W

■第四章電鰭器管理

4.3.4伙伴系統(tǒng)（自學(xué)內(nèi)容）

?固定分區(qū)和動(dòng)態(tài)分區(qū)方式都有不足之處。固定分

區(qū)方式限制了活動(dòng)進(jìn)程的數(shù)目，當(dāng)進(jìn)程大小與空

閑分區(qū)大小不匹配時(shí)，內(nèi)存空間利用率很低。動(dòng)

態(tài)分區(qū)方式算法復(fù)雜，回收空閑分區(qū)時(shí)需要進(jìn)行

分區(qū)合并等，系統(tǒng)開銷較大。伙伴系統(tǒng)方式是對(duì)

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

?伙伴系統(tǒng)規(guī)定，無論已分配分區(qū)或空閑分區(qū)，其

大小均為2的左次塞，左為整數(shù)，七任加，其中：21

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

分區(qū)的大小，通常2m是整個(gè)可分配內(nèi)存的大小。

44

第四章落儲(chǔ)器管理

?假設(shè)系統(tǒng)的可利用空間容量為2m個(gè)字，則系統(tǒng)開

始運(yùn)行時(shí)，整個(gè)內(nèi)存區(qū)是一個(gè)大小為2m的空閑分

區(qū)。在系統(tǒng)運(yùn)行過程中，由于不斷的劃分，可能

會(huì)形成若干個(gè)不連續(xù)的空閑分區(qū)，將這些空閑分

區(qū)根據(jù)分區(qū)的大小進(jìn)行分類，對(duì)于每一類具有相

同大小的所有空閑分區(qū)，單獨(dú)設(shè)立一個(gè)空閑分區(qū)

雙向鏈表。這樣，不同大小的空閑分區(qū)形成了

左（OS公⑼個(gè)空閑分區(qū)鏈表。

45

當(dāng)需要為進(jìn)程分配一個(gè)長(zhǎng)度為〃的存儲(chǔ)空間時(shí)，首先計(jì)算

一個(gè)，.值，使2*〈脛2］，然后在空閑分區(qū)大小為21的空閑分

區(qū)鏈表中查找。若找到，即把該空閑分區(qū)分配給進(jìn)程。否

則，表明長(zhǎng)度為2,?的空閑分區(qū)已經(jīng)耗盡，則在分區(qū)大小為

2，+1的空閑分區(qū)鏈表中尋找。若存在2汁，的一個(gè)空閑分區(qū)，

則把該空閑分區(qū)分為相等的兩個(gè)分區(qū)，這兩個(gè)分區(qū)稱為一

對(duì)伙伴，其中的一個(gè)分區(qū)用于分配，而把另一個(gè)加入分區(qū)

大小為2,?的空閑分區(qū)鏈表中。若大小為2汁1的空閑分區(qū)也不

存在，則需要查找大小為2計(jì)2的空閑分區(qū)，若找到則對(duì)其

進(jìn)行兩次分割：第一次，將其分割為大小為2計(jì)1的兩個(gè)分

區(qū)，一個(gè)用于分配，一個(gè)加入到大小為2計(jì)1的空閑分區(qū)鏈

表中；第二次，將第一次用于分配的空閑區(qū)分割為2的兩

個(gè)分區(qū)，一個(gè)用于分配，一個(gè)加入到大小為2,?的空閑分區(qū)

鏈表中。若仍然找不到，則繼續(xù)查找大小為2計(jì)3的空閑分

區(qū)，幺此類推。由此可見匕,，在最壞的情況下，可能需要對(duì)

2〃的空訊分區(qū)進(jìn)行上次分割才能得到所需分區(qū)。

46

*

?與一次分配可能要進(jìn)行多次分割一樣，一次日收

也可能要進(jìn)行多次合并，如回收大小為2%的生拓

分區(qū)時(shí)，若事先已存在2%的空閑分區(qū)時(shí)，則應(yīng)將

其與伙伴分區(qū)合并為大小為2計(jì)1的空閑分區(qū)，若事

先已存在2計(jì)1的空閑分區(qū)時(shí)，又應(yīng)繼續(xù)與其伙伴分

區(qū)合并為大小為2汁2的空閑分區(qū)，依此類推。

?在伙伴系統(tǒng)中，其分配和回收的時(shí)間性能取決于

查找空閑分區(qū)的位置和分割、合并空閑分區(qū)所花

費(fèi)的時(shí)間。與前面所述的多種方法相比較，由于

該算法在回收空閑分區(qū)時(shí)，需要對(duì)空閑分區(qū)進(jìn)行

合并，所以其時(shí)間性能比前面所述的分類搜索算

法差，但比順序搜嚎算法好，而其空間性能則遠(yuǎn)

優(yōu)于前面所述的分莢獨(dú)索法，比順序搜索法略差。

*

47

W

立章啟承器管理

4.3.5哈希算法

?哈希算法就是利用哈希快速查找的優(yōu)點(diǎn)，

以及空閑分區(qū)在可利用空間表中的分布規(guī)

律，建立哈希函數(shù)，構(gòu)造一張以空閑分區(qū)

大小為關(guān)鍵字的哈希表，該表的每一個(gè)表

項(xiàng)記錄了一個(gè)對(duì)應(yīng)的空閑分區(qū)鏈表表頭指

針。

?當(dāng)進(jìn)行空閑分區(qū)分配時(shí)，根據(jù)所需空閑分

區(qū)大小，通過哈希函數(shù)計(jì)算，即得到在哈

希表中的位置，從中得到相應(yīng)的空閑分區(qū)

鏈表，實(shí)現(xiàn)最佳分配策略。

48

W

第四章落儲(chǔ)器管理

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

?1.動(dòng)態(tài)重定位的引入

?在連續(xù)分配方式中，必須把一個(gè)系統(tǒng)或用戶程序裝入

一連續(xù)的內(nèi)存空間。如果在系統(tǒng)中只有若干個(gè)小的分

區(qū)，即使它們?nèi)萘康目偤痛笥谝b入的程序，但由于

這些分區(qū)不相鄰接，也無法把該程序裝入內(nèi)存。例如，

圖4-9(a)中示出了在內(nèi)存中現(xiàn)有四個(gè)互不鄰接的小分區(qū),

它們的容量分別為10KB、30KB、14KB和26KB,其

總?cè)萘渴?0KB。但如果現(xiàn)在有一程序到達(dá)，要求獲得

40KB的內(nèi)存空間，由于必須為它分配一連續(xù)空間，故

此程序無法裝入。這種不能被利用的小分區(qū)稱為“零

頭”或“碎片”。

W

第四章落儲(chǔ)器管理

操作系統(tǒng)

用戶程序1

用戶程序3

解決辦法:

用戶程序6

用戶程序9

緊湊：通過移動(dòng)一些

內(nèi)存分區(qū)，將原本離80KB

散的一些內(nèi)存小碎片

變得相鄰，進(jìn)而可以

合并為一個(gè)稍大的空

閑分區(qū)的技術(shù)。

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

現(xiàn)在有4個(gè)空閑分區(qū)，如果有

一個(gè)大小為40KB的程序要求

進(jìn)入內(nèi)存，如何處理？圖4-9緊湊的示意

5。忠3

一

第四章落儲(chǔ)器管理

?2.動(dòng)態(tài)重定位的實(shí)現(xiàn)

A經(jīng)過緊湊后，某些用戶程序在內(nèi)存中的位置發(fā)

生了變化，此時(shí)若不對(duì)程序和數(shù)據(jù)的地址加以

修改（變換），則程序必將無法執(zhí)行。為此，在

每次“緊湊”后，都必須對(duì)移動(dòng)了的程序或數(shù)

據(jù)進(jìn)行地址重定位。

?增設(shè)“重定位寄存器”，每當(dāng)系統(tǒng)對(duì)內(nèi)存進(jìn)行

了“緊湊”而使若干程序從內(nèi)存的某處移至另

一處時(shí)，不需對(duì)程序做任何修改，只要實(shí)時(shí)更

新“重定位寄存器”的值即可。

51*

第四章存儲(chǔ)器管理

基址寄存器BR

（重定位寄存器）

10000

10100

12500

15000

程序

外存程序一側(cè)存儲(chǔ)器一側(cè)主存

圖4-10動(dòng)態(tài)重定位示意圖

動(dòng)態(tài)地址重定位：

指令或數(shù)據(jù)的內(nèi)存地址MA

=該指令或數(shù)據(jù)的虛擬地址VA+重定位基址寄存器BR52

第四章腐儲(chǔ)器管理

?3.動(dòng)態(tài)重定位分區(qū)分配算法

A動(dòng)態(tài)重定位分區(qū)分配算法與動(dòng)態(tài)分區(qū)分配算法

基本上相同，差別僅在于：在這種分配算法中,

增加了緊湊的功能，通常，在找不到足夠大的

空閑分區(qū)來滿足用戶需求時(shí)進(jìn)行緊湊。圖4-11

示出了動(dòng)態(tài)重定位分區(qū)分配算法。

.第？章啟承器管理

請(qǐng)求分配、）

\^u.size^E^x

*

檢索空閑分區(qū)鏈（表）

廠羌法分曉閑分口

^大于

回口>u.size?^ize的個(gè)多

1是

進(jìn)行緊湊形成按動(dòng)態(tài)分區(qū)方式

連續(xù)空閑區(qū)進(jìn)行各配

；「

修改有關(guān)的數(shù)據(jù)結(jié)構(gòu)一（返回分區(qū)號(hào)、

修改有關(guān)的數(shù)據(jù)結(jié)構(gòu)

圖4-11動(dòng)態(tài)分區(qū)分配算法流程圖

54

第四章落儲(chǔ)器管理

4.3.7有關(guān)分區(qū)管理的討論

?1.分區(qū)存儲(chǔ)管理的特點(diǎn)

A優(yōu)點(diǎn)：實(shí)現(xiàn)了多個(gè)進(jìn)程對(duì)內(nèi)存的共享，有助于

多道程序系統(tǒng)；提高了資源利用率；要求的硬

件支持少；管理簡(jiǎn)單，實(shí)現(xiàn)容易。

A缺點(diǎn)：內(nèi)存利用率仍然不高，小碎片多；進(jìn)程

大小受分區(qū)大小的限制；不能部分裝入，難以

實(shí)現(xiàn)各分區(qū)間的信息共享；無法實(shí)現(xiàn)虛存。

55;要?jiǎng)∏?/p>

k上章程儲(chǔ)器管理

?2.關(guān)于虛存的實(shí)現(xiàn)

＞虛存：用戶進(jìn)程所需內(nèi)存容量只受內(nèi)存和外存

容量之和的限制的存儲(chǔ)器技術(shù)。單純的分區(qū)管

理是無法實(shí)現(xiàn)虛存的。

Trw

2）對(duì)換Swapping

■換出Swap_out：將內(nèi)存中阻塞且優(yōu)先級(jí)最低的進(jìn)程

（程序+數(shù)據(jù)）換到外存交換區(qū)，修改其PCB并回收相

應(yīng)內(nèi)存。

■換入Swap_in：將外存交換區(qū)中靜止就緒且被換出時(shí)

間最久的迸程（程序+數(shù)據(jù)）換入內(nèi)存并修改其PCB。

■對(duì)換分類：

?進(jìn)程對(duì)換（整體對(duì)換）

?部分對(duì)換（頁面或分段對(duì)換）——真正意義上實(shí)現(xiàn)虛存

■對(duì)換的三個(gè)關(guān)鍵操作：換出、換入、對(duì)換空間

（pagefile.sys）的管理。

■對(duì)換缺點(diǎn)：換入換出開銷大。

57

W

第四章落儲(chǔ)器管理

③關(guān)于地址變換和內(nèi)存保護(hù)

■地址變換：不實(shí)現(xiàn)緊湊時(shí)可采用“靜態(tài)可重定位

裝入”方式，實(shí)現(xiàn)緊湊時(shí)必須采用“運(yùn)行時(shí)動(dòng)態(tài)

可重定位裝入”方式。

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

?硬件法：為每個(gè)進(jìn)程設(shè)置一對(duì)上、下界寄存器，或利用

分區(qū)的基址寄存器和限長(zhǎng)寄存器。若越界則產(chǎn)生地址保

護(hù)中斷并轉(zhuǎn)錯(cuò)誤處理。

?軟件法（保護(hù)鍵法）：為被保護(hù)分區(qū)設(shè)置保護(hù)鍵開關(guān)字段,

針對(duì)不同的進(jìn)程賦予不同的開關(guān)代碼，通過檢查兩者是

否匹配來實(shí)現(xiàn)讀、寫保護(hù)。

?軟硬結(jié)合法。

第四章存儲(chǔ)器管理

4.4基本（靜態(tài)）分頁存儲(chǔ)管理方式

4.4.1頁式管理的基本原理

A回顧分區(qū)分配法：碎片問題嚴(yán)重，內(nèi)存利用率不高；

由于要求連續(xù)存放，導(dǎo)致進(jìn)程的大小仍受分區(qū)大小和

內(nèi)存可用空間的限制；不利于共享；無法實(shí)現(xiàn)虛存。

A引入頁式管理的目的：為了減少碎片，為了實(shí)現(xiàn)換入/

換出而采用離散存儲(chǔ)，提高內(nèi)存利用率。

A分頁存儲(chǔ)管理：將一個(gè)進(jìn)程的邏輯地址空間分成若干

個(gè)大小相等而片，稱為頁唳頁，并為各國力嗯緘號(hào)，

從0開始，如第0頁、第1頁等。相應(yīng)地，也把內(nèi)存空間

分成與頁面相同大小的若干個(gè)存儲(chǔ)塊，稱為（物理）塊或

頁框（frame）,也同樣為它們加以編號(hào)，如0#塊、1#塊

等等。在為進(jìn)程分配內(nèi)存時(shí)以塊為單位，將進(jìn)程中的

若干人頁分別裝入到多個(gè)可以不相鄰接的物理塊中。

由于進(jìn)程的最后一頁經(jīng)串裝不滿一塊而形成了不可利

用的碎片，稱之為“頁山碎片”。

59Kg

第四章落儲(chǔ)器管理

?1.頁面

A一個(gè)進(jìn)程的虛擬空間被劃分為若干個(gè)長(zhǎng)度相等

的頁面(page),通常幾KB?幾十KB為一頁，故

進(jìn)程的虛地址(邏輯地址)可由頁號(hào)P與頁內(nèi)地址

W所組成。

頁號(hào)P頁內(nèi)地址W

231090

假設(shè)這是某系統(tǒng)的分頁地址結(jié)構(gòu)，則該系

統(tǒng)頁長(zhǎng)為2io=lO24B即1KB/頁，一個(gè)進(jìn)程

最長(zhǎng)允許有214=16384頁即16384KB

60■工

第四章落儲(chǔ)器管理

A與進(jìn)程邏輯空間的分頁結(jié)構(gòu)類似，物理內(nèi)存空

間也被劃分為與頁面相等大小的若干物理塊。

A在為進(jìn)程分配內(nèi)存時(shí)，將進(jìn)程的N個(gè)頁面（必定

連續(xù)）裝入到N個(gè)內(nèi)存物理塊（不一定連續(xù)）。即:

連續(xù)的N個(gè)頁面對(duì)應(yīng)裝入不連續(xù)的N個(gè)物理塊。

式

頁管理特點(diǎn)：無外碎片的概念；且內(nèi)碎片必

小

定于一個(gè)物理塊；實(shí)現(xiàn)了非連續(xù)（離散）方式

儲(chǔ)

存

大

增,為虛存的實(shí)現(xiàn)提供了基礎(chǔ)；但管理開銷

?關(guān)鍵問題：如何將頁面邏輯地址變換為內(nèi)存物

理地址？

-頁表+硬件地址變換機(jī)構(gòu)

W

?2?頁表(PageMappingTable)

A由于在分頁系統(tǒng)中，允許將進(jìn)程的n個(gè)連續(xù)頁離

散地存儲(chǔ)在內(nèi)存不連續(xù)的n個(gè)物理塊中，為此，

系統(tǒng)又為每個(gè)進(jìn)程建立了一張頁面映像表，簡(jiǎn)

稱頁表。在進(jìn)程地址空間內(nèi)的所有頁(0?n),依

次在頁表中有一頁表項(xiàng)，其中記錄了M應(yīng)頁在

內(nèi)存中對(duì)應(yīng)的物理塊號(hào)，見圖4-12的中間部分。

在配置了頁表后，進(jìn)程執(zhí)行時(shí)，通過查找該表，

即可找到每頁在內(nèi)存中的物理塊號(hào)。可見，頁

表的作用是實(shí)現(xiàn)小頁號(hào)到其理塊號(hào)的投址映射。

~物理塊號(hào)

W

細(xì)章啟承器管理

說明:

?頁表負(fù)責(zé)記錄遂聘

頁面與內(nèi)存物理塊

的對(duì)應(yīng)關(guān)系

?每個(gè)進(jìn)程都有自己

的一張頁表

?頁表的長(zhǎng)度由進(jìn)程

大小和頁面大小共

同決定：比如一進(jìn)

程為4765B,若頁

面大小為1KB/頁，

則該進(jìn)程包含5頁

（第0頁?第4頁），即

該戰(zhàn)程的頁表包含

5個(gè)表項(xiàng)

63

W

思考幾個(gè)問題

①頁面大小一般為2n字節(jié)，但具體n有多大？過小怎

樣？過大怎樣？

■過小：則頁表過長(zhǎng)，換入/換出效率低，使用和維護(hù)的開

銷大。

■過長(zhǎng)：頁內(nèi)碎片大。

②已知邏輯地址和頁面大小，如何計(jì)算頁號(hào)及頁內(nèi)

地址？

■頁號(hào)=邏輯地址/頁面大小（整除運(yùn)算）

■頁內(nèi)地址=邏輯地址％頁面大小（求余運(yùn)算）

■例：已知頁面大小為1KB/頁，現(xiàn)有一數(shù)據(jù)的邏輯地址為

2148,問：該數(shù)據(jù)在哪頁的哪個(gè)位置？

?頁號(hào)=2148/1024=2,頁內(nèi)地址=2148%1024=一,

100,即：該數(shù)據(jù)在該進(jìn)程的第2頁的相對(duì)地址100處名人

64

w

3.靜態(tài)頁式管理（基本頁式管理）

＞必須將一個(gè)進(jìn)程的所有頁面全部裝入到內(nèi)存物理塊,

無法實(shí)現(xiàn)虛存。

4.動(dòng)態(tài)頁式管理

＞允/您二個(gè)進(jìn)程的一部分頁面裝入到內(nèi)存物理塊。

＞采用“請(qǐng)求調(diào)頁”或二禪調(diào)頁”技術(shù)實(shí)現(xiàn)了內(nèi)外存存

儲(chǔ)器的統(tǒng)一管理即對(duì)換技術(shù)。

＞內(nèi)存中只存放那些經(jīng)常被執(zhí)行或?qū)⒁粓?zhí)行的頁面，

而不常被執(zhí)行或近期內(nèi)不會(huì)執(zhí)行的頁面則存放在外存,

待需要時(shí)再按請(qǐng)求式調(diào)入。

5.分頁管理的重點(diǎn)

①邏輯地址》物理疝址的地址變換（頁表+硬件地址變

換機(jī)構(gòu)）.

②頁面的動(dòng)態(tài)置換技術(shù)

65；

第四章落儲(chǔ)器管理

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

?1.基本的地址變換機(jī)構(gòu)

?地址映射：連續(xù)的N個(gè)頁面對(duì)應(yīng)于不連續(xù)的N個(gè)物理塊

-邏輯頁號(hào)”物理塊號(hào)：查頁表

-頁內(nèi)地址9塊內(nèi)地址：兩者相等

?從成本和容量上來考慮，采用寄存器來存儲(chǔ)頁表是不

現(xiàn)實(shí)的。因此，頁表大多駐留在內(nèi)存中，而在系統(tǒng)中

只設(shè)置一個(gè)頁表寄存器PTR(TableRegister),在其

中存放該進(jìn)程的頁表在內(nèi)存的始址和頁表的長(zhǎng)度。平

時(shí)，進(jìn)程未執(zhí)行時(shí)，頁表的始址和頁表長(zhǎng)度存放在本

進(jìn)程的PCB中。當(dāng)調(diào)度程序調(diào)度到某進(jìn)程時(shí)，才將這

兩個(gè)數(shù)據(jù)裝入頁表寄存器中。因此，在單處理機(jī)環(huán)境

下，雖然系統(tǒng)中可以運(yùn)行多個(gè)進(jìn)程，但只需一個(gè)頁表

寄存器。

66

W

A地址變換算法

-當(dāng)某進(jìn)程被調(diào)度執(zhí)行時(shí)，將其PCB中記錄的頁表始

址S和頁表長(zhǎng)度L取出來放到“頁表寄存器”中；同

時(shí)，分頁地址變換機(jī)構(gòu)會(huì)自動(dòng)將邏輯地址劃分為頁

號(hào)P和頁內(nèi)地址W,然后用頁號(hào)P與頁表長(zhǎng)度L比較：

若PNL則越界中斷，否則合法，再以頁號(hào)P去檢索頁

表，查得該頁P(yáng)對(duì)應(yīng)的物理塊號(hào)，進(jìn)而算得該塊在內(nèi)

存的起始地址B,最后B與頁內(nèi)地址W（即塊內(nèi)地址）

相加就得到了要訪問的物理地址。這樣便完成了從

邏輯地址到物理地址的變換。圖4-13示出了分頁系

統(tǒng)的地址變換機(jī)構(gòu)。

67

W

第四章落儲(chǔ)器管理

越界中斷

圖4-13分頁系統(tǒng)的地址變換機(jī)構(gòu)

68

第四章存儲(chǔ)器管理

1。

■例：已知頁面長(zhǎng)度為1KB/頁，某進(jìn)程的頁表如圖所

示。現(xiàn)有邏輯地址為100的一條指令LOADR19

[2500]o問：

?試說明該指令的取指過程？

?試說明該指令的取數(shù)過程？

頁號(hào)塊號(hào)

02

13

28

第四章落儲(chǔ)器管理

越界中斷

頁表寄存器邏輯地址100

頁表始址頁表長(zhǎng)度3<頁號(hào)0頁內(nèi)地址100

+

頁號(hào)物理地址

-0A塊號(hào)2塊內(nèi)地址100

1

2

該指令的物理地址為2148

頁表

邏輯地址為100的指令的取指過程：

?頁號(hào)=近科地址/頁長(zhǎng)=100/1024=0

?頁內(nèi)地址=邏輯地址％頁長(zhǎng)=100%1024=100

?物理地址=物理塊號(hào)*塊長(zhǎng)十境內(nèi)地址=2*1024+100=214870

邏輯地址為100的指令的取教過程（該教的邏輯地址為2500）：

?頁號(hào)=近科地址/頁長(zhǎng)