第04章存储器管理

第四章落储器管理

第四章存储器管理

4」存储器的层次结构

4.2程序的装入和链接

43连续分配方式

4.4基本分页存储管理方式

4.5基本分段存储管理方式

4.6虚拟存储器的基本概念

4.7请求分页存储管理方式

4.8页面置换算法

4.9请求分段存储管理方式

k士章商借器管理一q

4.1存储器的层次结构''

4.1.1多级存储器结构

•1.存储器功能

»合理、安全、有效地保存数据

•2.存储器发展方向

»接口更新

-以硬盘为例：ESDI;IDE/EIDE;ATA;SATA/SATA2;SCSI;

IEEE1394;USB...

＞高速性

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

理论上是5Gbps...

»存储密度越来越高，体积越来越小

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

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

第四章落储器管理

--■

容量有望翻倍希捷达到存储密度新纪录

2012年03月21日00：00来源:/作者：ChrisR编辑:秋龙评论：一条

[IT168资讯】希捷今日正式宣布，该公司成为第一家在存储密度上达到1Tbit/平方英寸（1

terabit=ltrillionbit=l万亿bit）这一里程碑的哽盘厂商，新技术的应用使得每平方英寸所记

录的bit数量甚至超过了银河系中的天体数量（约20007000亿之间）♦

希捷所采用的技术名为HAMR,即HeaLAssistedMagneticRecording（热辅助磁记录）。作

为目前耍盘采用的P股（PerpendicularMagneticRecording,垂直磁记录技术的继任者）,

HAMR的理论存储密度为570Tbit/平方英寸。相比之下，目前的3.5英寸硬盘存储密度为

620Gbit/平方英寸，2.5硬盘的存储密度为500Gbit/平方英寸。

HAMR技术可轻松达到PMR技术的存储密度极限一一1Tbit/平方英寸这一里程碑，比目前硬盘产

品的存储密度高出55%左右。一旦HAMR得到实际应用，目前3.5英寸硬盘产品的容量可轻松翻倍达

到6TB左右，2.5英寸硬盘的容量更是能提升至2TB。未来HAMR技术成熟后3.5英寸/2.5英寸硬盘的

容量更是可以达到目前服务器水平的30-60TB/10-20ITB。

3

第四章落储器管理

A容量越来越大，价格越来越低

-以下是近年来关于硬盘价格的趣味数字

□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

第四章落储器管理

■■单

位

容

速

量

成

度

本

图4-1计算机系统存储层次示意

第四章落储器管理

•4.存储管理功能

A存储分配与回收

-本章主要内容，讨论其算法和数据结构

A地址变换

-可执行文件生成中的链接技术；程序装入时的重定

位技术；进程运行时的地址变换技术和机构（软件、

硬件）

A存储共享和保护

-代码和数据共享；对地址空间的访问权限（读、写、

执行）

A存储器扩充

-由用户应用程序控制：覆盖Overlay

-由OS控制：交换Swapping；请求调入和预调入On

Demand&OnPrefetch么-

w

第四章存储器管理

4.1.2主存储器与寄存器

•1.主存储器

»主存储器（简称内存或主存）是计算机系统中一

个主要部件，用于保存进程运行时的程序和数

据，也称可执行存储器，材质以DRAM为主。

由于主存储器的访问速度远低于CPU执行指令

的速度，为缓和这一矛盾，在计算机系统中引

入了寄存器和高速缓存。

W

第四章落储器管理

•2.寄存器

A寄存器访问速度最快，完全能与CPU协调工作,

但价格却十分昂贵，因此容量不可能做得很大。

寄存器的长度一般以字(word)为单位。寄存器

的数目，对于当前的微机系统和大中型机，可

能有几十个甚至上百个；而嵌入式计算机系统

一般仅有几个到几十个。

A寄存器通常用于加速存储器的访问速度，如用

寄存器存放操作数，或用作地址寄存器加快地

址转换速度等。

8

立章启承器管理

4.1.3高速缓存和磁盘缓存

•1.高速缓存

»高速缓存是现代计算机结构中的一个重要部件,

其容量大于或远大于寄存器，而比内存约小两

到三个数量级左右，从几十KB到几MB,访问

速度快于主存储器。

A根据程序执行的局部性原理（即程序在执行时将

呈现出局部性规律，在一较短的时间内，程序

的执行仅局限于某个部分），将主存中一些经常

访问的信息存放在高速缓存中，减少访问主存

储器的次数，可大幅度提高程序执行速度。

W

上章卷储器管理:一©

•2.磁盘缓存

»由于目前磁盘的I/O速度远低于对主存的访问速

度，因此将频繁使用的一部分磁盘数据和信息,

暂时存放在磁盘缓存中，可减少访问磁盘的次

数。

1。

年］上章商储器管理一©

4.2程序的装入和链接''

•在多道程序环境下，要使程序运行，必须先为之

创建进程。而创建进程的第一件事，便是将程序

和数据装入内存。如何将一个用户源程序变为一

个可在内存中执行的程序，通常都要经过以下几

个步骤：首先是要编译，由编译程序(Compiler)将

用户源代码编译成若干个目标模块(Object

Module)；其次是链接，由链接程序(Linker)将编

译后形成的一组目标模块，以及它们所需要的库

函数链接在一起，形成一个完整的装入模块(Load

Module)；最后是装入，由装入程序(Loader)将装

入模块装入内存。图4-2示出了这样的三步过程。

本节将扼要阐述程序(含数据)的链接和装入过程。

11F

第四章落储器管理

库函数

Lib

源

程

程

序

员

序

C

装入

模块

.EXE

图4-2对用户程序的处理步骤

第回章存储器管理

4.2.1程序的链接

A链接：若干目标模块+库函数”可装入模块

»根据链接时间的不同，可把链接分成如下三种：

-(1)静态链接。在程序运行之前，先将各目标模块及

它们所需的库函数，链接成一个完整的装配模块，

以后不再拆开。我们把这种事先进行链接的方式称

为静态链接方式。

-(2)装入时动态链接。这是指将用户源程序编译后所

得到的一组目标模块，在装入内存时，采用边装入

边链接的链接方式。

-(3)运行时动态链接。这是指对某些目标模块的链接,

是在程序执行中需要该(目标)模块时，才对它进行*

的链接。二

13

第四章落储器管理

•1.静态链接方式(StaticLinking)

A在生成可装入模块时(也就是在程序装入运行前)

完成的链接。见图4-4

»特点：

-一次链接，n次运行

-得到完整的可装入模块，不可再拆

-不灵活：不管有用与否的模块都将链接到装入模块，

同时导致内存利用率较低

-不利于模块的修改和升级

14

■第四章存储器管理

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)目标模块(b)装入模块

图4-4程序链接示意图

第四章落储器管理

•2.装入时动态链接(Load-timeDynamic

Linking)

A用户源程序经编译后所得的目标模块，是在装

入内存时边装入边链接的，即在装入一个目标

模块时，若发生一个外部模块调用事件，将引

起装入程序去找出相应的外部目标模块，并将

它装入内存，还要按照图4-4所示的方式来修改

目标模块中的相对地址。

16

W

•3.运行时动态链接(Run-timeDynamicLinking)

＞装入时动态链接是将所有可能要运行到的模块都全部

链接在一起并装入内存，显然这是低效的，因为往往

会有些目标模块根本就不运行。比较典型的例子是作

为错误处理用的目标模块，如果程序在整个运行过程

中都不出现错误，则显然就不会用到该模块。

＞运行时动态链接方式是对装入时链接方式的一种改进。

这种链接方式是将对某些模块的链接推迟到程序执行

时才进行链接，亦即，在程序执行过程中，当发现一

个被调用模块尚未装入内存时，才立即由OS去找到该

模块并将之装入内存，把它链接到调用者模块上。凡

在本次执行过程中未被用到的目标模块，都不会被调

入内存和被链接到装入模块上，这样不仅可加快程序

的装入过程，而且可节省大量的内存空间。

17

W

第四章卷储器

•4.动态链接方式的优点

»便于共享

-多个进程可共用一个DLL模块，节省了内存。

＞为部分装入提供了条件（运行时动态链接）

-一个进程可由若干DLL模块构成，按需装入。

»便于模块的修改和升级

-只要被修改模块的接口不变，则该模块的修改不会

引发其它模块的重新编译。

»改善了程序的可移植性

-可面向不同的应用环境开发同一功能模块的不同版

本，根据当前的环境载入匹配的模块版本。.

18"1^01

•5.动态链接方式的缺点

A增加了程序执行时的链接开销。（每次运行都需

链接）

A模块数量众多，增加了模块的管理开销。

第四章落储器管理

4.2.2程序的装入

•装入：可装入模块（.EXE）”内存进程

•1.绝对装入方式（AbsoluteLoadingMode）

»在编译后、装入前已产生了绝对地址（内存地

址），装入时不再作地址重定位，即：装入内

存前的虚拟地址==装入内存后的物理地址。

A绝对地址的产生：（1）由编译器完成；（2）

由程序员编程完成。

A优点：装入过程简单，无需地址映射。

A缺点：不适于多道程序系统；过于依赖硬件结

构；不易修改、不灵洁。

20

W

第四章存储器管理

•2.可重定位装入方式(RelocationLoading

Mode)

A可装入模块在被装入到内存中时，由装入程序

来完成程序虚拟地址》内存物理地址的变换

21

第四章落储器管理

0

10000'「如果不进行地址变:

换，那么这条指令

将无法取到正确的

100011000

LOAD1,2500LOAD1,2500U数值“365”，所以

=>\该指令中的地址应

\该重定位为：

250012500

365365\LOAD1,12500>

15000

程序地址空间-

r1

图4-3装入内存时的情况物理内存空间

静态地址重定位：

指令或数据的内存地址MA

=该指令或数据的虚拟地址VA+该程序在内存中的首地址BA

・第四章存储器管理一一y»

A可重定位装入的优缺点：

-优点：

口适用于多道程序系统，提高了内存利用率；由于地址映射

规则简单，故在地址变换过程中无需硬件变换机构的支持。

-缺点：

口任何进程都要求连续的内存空间；必须将全部模块都装入

且装入后不能再移动位置（因为无法实现动态重定位）；不

支持虚拟存储器技术；不易实现共享。

第四章落储器管理

•3.动态运行时装入方式(DynamicRun・

timeLoading)

A出于实际情况，程序在运行过程中的内存位置

可能经常要改变，此时就应采用动态运行时装

入的方式。

A程序装入内存后并不立即进行地址变换，而是

等到真正要执行时才由硬件地址变换机构来完

成地址变换，从而得到内存物理地址。

24

W

第四章落储器管理

“基址寄存器BR

外存程序一侧存储器一侧主存

动态地址重定位：

指令或数据的内存地址MA

=该指令或数据的虚拟地址VA+重定位基址寄存器BR

25

・第四章存储器管理一一y»

A动态运行时装入的优缺点：

-优点

□os可将一个进程的不同部分分散存放在不连续的内存空间;

可移动进程在内存中的位置（由重定位基址寄存器反映移

动情况）；提供了实现虚拟存储器技术的基础（可实现部分

模块装入）；有利于实现模块共享。

-缺点

口动态重定位需要硬件变换机构的支持；实现较复杂。

第四章落储器管理

4.3连续分配方式

连续分配方式是指一个进程在内存中必须占

用连续的存储空间。典型的连续分配方式主要有:

单一连续分配、固定分区分配、动态分区分配、

动态重定位分区分配等。

4.3.1单一连续分配

•把内存分为系统区和用户区两部分，系统区仅提

供给OS使用；用户区是指除系统区以外的全部内

存空间，提供给用户使用。

・优点：简单，易于管理

•缺点：只能用于单用户单任务OS；内存利用率低,

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

27

W

引入：分区存储管理原理

①将内存分为一些大小相等或不等的分区

(Partition),每个进程可占用一个分区。

②适于多道程序系统，支持多个进程并发执行。

③出现了碎片问题

I.内碎片：被占用分区的尾部未被利用的空间。

II.外碎片：在两个被占用分区之间的难以利用的小

空闲分区。

④分区管理的数据结构：分区表或分区链表。

⑤内存紧凑(Compaction)：将各个已占用分区

向内存某端移动，从而使分散的各个小空闲分

区能相邻，进而合并为一个稍大的空闲分区。.

28

W

第四章落储器管理

4.3.2固定分区分配

•1.把内存划分为若干个固定大小的分区，

分区的总数以及各个分区的大小都是恒定

值。

A各分区大小相等

-不灵活；对于小进程而言，内存利用率低，内碎片

严重；对于大进程而言，分区大小可能无法满足需

要，导致无法装入。

A各分区大小不等

-小分区、中等分区、大分区。适应性较强，可以有

效提高内存利用率。

29

W

立章启承器管理

•2.固定分区的内存分配

A为了便于内存分配，通常将分区按大小进行排

队，并为之建立一张分区使用表，其中各表项

包括每个分区的起始地址、大小及状态(是否已

分配)，见图4-5(a)所示。

A当有一用户程序要装入时，由内存分配程序检

索该表，从中找出一个能满足要求的、尚未分

配的分区，将之分配给该程序，然后将该表项

中的状态置为“已分配”；若未找到大小足够

的分区，则拒绝为该用户程序分配内存。存储

空间分配情况如图4-5(b)所示。

第四章落储器管理

操作系统

分区号大小/KB起址/KJB状态20KB

进程A(8K)

11220已分配32KB

进程B(25K)

23232已分配64KJB

36464已分配进程C(40K)

128KBJ

4128128未分配

(a)分区说明表

256KB

(b)存储空间分配情况

图4-5固定分区使用表

第四章落储器管理

•3.固定分区分配的优缺点

A优点

-由于各分区大小固定，故易于实现，管理开销小。

»缺点

-内碎片的问题不可避免，较大程序不易装入，故内

存利用率较低；分区数目固定也限制了进程的并发

度。

第四章落储器管理

4.3.3动态分区分配

•在动态分区分配方式中，各个分区的大小

会在OS的管理下发生改变，分区总数也会

相应地发生变化。

•1.分区分配中的数据结构

»(1)空闲分区表：记录所有空闲分区情况的二维

表分区号大小/KB起址/KB状态

11820未分配

232242未分配

3150502未分配

4128750未分配

33

第四章落储器管理

»(2)空闲分区

链：将所有

的空闲分区

链接成一个

双向链，如

图4-6所示。

「0：未分配

Y

-1：已分配

第四章商储器管理

•2.分区分配算法

>1)首次适应FF算法(FirstFit)

-空闲分区链以地址递增的次序链接。在每次分配时,

都从链首开始顺序查找，直至找到第一个大小能满

足要求的空闲分区为止；然后再按照程序的大小，

从该分区中划出一块内存空间分配给请求者，余下

的空闲分区仍留在空闲链中。若从链首直至链尾都

不能找到一个能满足要求的分区，则此次内存分配

失败，返回。

-特点：简单；高址内存可保留较大的空闲分区；但

低址内存会产生很多碎片分区；查找开销大。

35

■第四章存储器管理

A2)循环首次适应NF算法(NextFit)

-该算法是由首次适应FF算法演变而成的：分配空间

不再是每次都从链首开始查找，而是从上次找到的

空闲分区的下一个空闲分区开始查找，如果达到链

尾则回到链首继续。

-特点：查找开销小；空闲分区分布更均匀；但较大

分区难以保留。

>3)最佳适应BF算法(BestFit)

-空闲分区链表以容量递增为序组织，每次分配时从

链首查找，将第一个满足空间要求的分区分配出去。

-特点：最接近按需分配原则；较大的分区容易保留;

但会产生很多难以利用的小碎片分区。

>4)最坏适应WF算法(WorstFit)

-空闲分区链表以容量递减为序组织，每次分配时从

链首查找，将第一个满足空间要求的分区分配出去。

-特点：小碎片分区的问题得到了有效的解决；但大

分区也不易保留。

A最坏适应算法与前面所述的首次适应、循环首

次适应、最佳适应算法一起，统称为顺序搜索

法。

37

A5)快速适应QF算法(QuickFit)

-该算法又称为分类搜索法，是将空闲分区根据其容

量大小进行分类，对于每一类具有相同容量的所有

空闲分区，单独设立一个空闲分区链表，这样，系

统中存在多个空闲分区链表，同时在内存中设立一

张管理索引表，该表的每一个表项对应了一种空闲

分区类型，并记录了该类型空闲分区链表表头的指

针。空闲分区的分类是根据进程常用的空间大小进

行划分。

-优点：查找效率高；不会对任何分区产生分割，所

以能保留大的分区；也不会产生内存碎片。

-缺点：分区归还主存的算法复杂，系统开销较大;

多样化的链表造成管理开销大。

第四章落储器管理

•3・分区分配操作

A1）分配内存

-系统应利用某种分配算法，从空闲分区链（表）中找

到所需大小的分区。设请求的分区大小为u.size,表

中每个空闲分区的大小可表示为m.size。若m.size-

u.sizeSsize（size是事先规定的不再切割的剩余分区的

大小），说明多余部分太小，可不再切割，将整个分

区分配给请求者；否则（即多余部分超过size）,从该

分区中按请求的大小划分出一块内存空间分配出去,

余下的部分仍留在空闲分区链（表）中。然后，将分

配区的首址返回给调用者。图4-7示出了分配流程。

39

第四章落储器管理

图4-7内存分配流程

第四章落储器管理

>2)回收内存

-(1)回收区与插入点的前一个空闲分区F1相邻接，见图4-8(a)。

此时应将回收区与插入点的前一分区合并，不必为回收分区分

配新表项，而只需修改其前一分区F1的大小。

-(2)回收分区与插入点的后一空闲分区F2相邻接，见图4-8(b)。

此时也可将两分区合并，也不必分配新表项，用回收区的首址

作为新空闲区的首址，大小为两者之和。

-(3)回收区同时与插入点的前、后两个分区邻接，见图4-8(c)。

此时将三个分区合并，使用Fl的表项，F1的首址不变，F1的

大小为三者之和，删除F2的表项。

-(4)回收区既不与F1邻接，又不与F2邻接，见图4-8(d)。这时应

为回收区单独建立一新表项，填写回收区的首址和大小，并根

据其首址插入到空闲链中的适当位置。

41

w

第四章落储器管理

(a)(b)(d)

第四章落储器管理

■例：假设最佳适应法

OS(20K)

进程A(8K)

16K空闲区

进程D(50K)

138K空闲区

进程E(16K)

8K空闲区

如果改为首次适应算法?

43

W

■第四章电鳍器管理

4.3.4伙伴系统（自学内容）

•固定分区和动态分区方式都有不足之处。固定分

区方式限制了活动进程的数目，当进程大小与空

闲分区大小不匹配时，内存空间利用率很低。动

态分区方式算法复杂，回收空闲分区时需要进行

分区合并等，系统开销较大。伙伴系统方式是对

以上两种内存方式的一种折衷方案。

•伙伴系统规定，无论已分配分区或空闲分区，其

大小均为2的左次塞，左为整数，七任加，其中：21

表示分配的最小分区的大小，2m表示分配的最大

分区的大小，通常2m是整个可分配内存的大小。

44

第四章落储器管理

•假设系统的可利用空间容量为2m个字，则系统开

始运行时，整个内存区是一个大小为2m的空闲分

区。在系统运行过程中，由于不断的划分，可能

会形成若干个不连续的空闲分区，将这些空闲分

区根据分区的大小进行分类，对于每一类具有相

同大小的所有空闲分区，单独设立一个空闲分区

双向链表。这样，不同大小的空闲分区形成了

左（OS公⑼个空闲分区链表。

45

当需要为进程分配一个长度为〃的存储空间时，首先计算

一个，.值，使2*〈胫2］，然后在空闲分区大小为21的空闲分

区链表中查找。若找到，即把该空闲分区分配给进程。否

则，表明长度为2,•的空闲分区已经耗尽，则在分区大小为

2，+1的空闲分区链表中寻找。若存在2汁，的一个空闲分区，

则把该空闲分区分为相等的两个分区，这两个分区称为一

对伙伴，其中的一个分区用于分配，而把另一个加入分区

大小为2,•的空闲分区链表中。若大小为2汁1的空闲分区也不

存在，则需要查找大小为2计2的空闲分区，若找到则对其

进行两次分割：第一次，将其分割为大小为2计1的两个分

区，一个用于分配，一个加入到大小为2计1的空闲分区链

表中；第二次，将第一次用于分配的空闲区分割为2的两

个分区，一个用于分配，一个加入到大小为2,•的空闲分区

链表中。若仍然找不到，则继续查找大小为2计3的空闲分

区，幺此类推。由此可见匕,，在最坏的情况下，可能需要对

2〃的空讯分区进行上次分割才能得到所需分区。

46

*

•与一次分配可能要进行多次分割一样，一次日收

也可能要进行多次合并，如回收大小为2%的生拓

分区时，若事先已存在2%的空闲分区时，则应将

其与伙伴分区合并为大小为2计1的空闲分区，若事

先已存在2计1的空闲分区时，又应继续与其伙伴分

区合并为大小为2汁2的空闲分区，依此类推。

•在伙伴系统中，其分配和回收的时间性能取决于

查找空闲分区的位置和分割、合并空闲分区所花

费的时间。与前面所述的多种方法相比较，由于

该算法在回收空闲分区时，需要对空闲分区进行

合并，所以其时间性能比前面所述的分类搜索算

法差，但比顺序搜嚎算法好，而其空间性能则远

优于前面所述的分荚独索法，比顺序搜索法略差。

*

47

W

立章启承器管理

4.3.5哈希算法

•哈希算法就是利用哈希快速查找的优点，

以及空闲分区在可利用空间表中的分布规

律，建立哈希函数，构造一张以空闲分区

大小为关键字的哈希表，该表的每一个表

项记录了一个对应的空闲分区链表表头指

针。

•当进行空闲分区分配时，根据所需空闲分

区大小，通过哈希函数计算，即得到在哈

希表中的位置，从中得到相应的空闲分区

链表，实现最佳分配策略。

48

W

第四章落储器管理

4.3.6可重定位分区分配

•1.动态重定位的引入

»在连续分配方式中，必须把一个系统或用户程序装入

一连续的内存空间。如果在系统中只有若干个小的分

区，即使它们容量的总和大于要装入的程序，但由于

这些分区不相邻接，也无法把该程序装入内存。例如，

图4-9(a)中示出了在内存中现有四个互不邻接的小分区,

它们的容量分别为10KB、30KB、14KB和26KB,其

总容量是80KB。但如果现在有一程序到达，要求获得

40KB的内存空间，由于必须为它分配一连续空间，故

此程序无法装入。这种不能被利用的小分区称为“零

头”或“碎片”。

W

第四章落储器管理

操作系统

用户程序1

用户程序3

解决办法:

用户程序6

用户程序9

紧凑：通过移动一些

内存分区，将原本离80KB

散的一些内存小碎片

变得相邻，进而可以

合并为一个稍大的空

闲分区的技术。

(a)紧凑前(b)紧凑后

现在有4个空闲分区，如果有

一个大小为40KB的程序要求

进入内存，如何处理？图4-9紧凑的示意

5。忠3

一

第四章落储器管理

•2.动态重定位的实现

A经过紧凑后，某些用户程序在内存中的位置发

生了变化，此时若不对程序和数据的地址加以

修改（变换），则程序必将无法执行。为此，在

每次“紧凑”后，都必须对移动了的程序或数

据进行地址重定位。

»增设“重定位寄存器”，每当系统对内存进行

了“紧凑”而使若干程序从内存的某处移至另

一处时，不需对程序做任何修改，只要实时更

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

51*

第四章存储器管理

基址寄存器BR

（重定位寄存器）

10000

10100

12500

15000

程序

外存程序一侧存储器一侧主存

图4-10动态重定位示意图

动态地址重定位：

指令或数据的内存地址MA

=该指令或数据的虚拟地址VA+重定位基址寄存器BR52

第四章腐储器管理

•3.动态重定位分区分配算法

A动态重定位分区分配算法与动态分区分配算法

基本上相同，差别仅在于：在这种分配算法中,

增加了紧凑的功能，通常，在找不到足够大的

空闲分区来满足用户需求时进行紧凑。图4-11

示出了动态重定位分区分配算法。

.第？章启承器管理

请求分配、）

\^u.size^E^x

*

检索空闲分区链（表）

厂羌法分晓闲分口

^大于

回口>u.size?^ize的个多

1是

进行紧凑形成按动态分区方式

连续空闲区进行各配

；「

修改有关的数据结构一（返回分区号、

修改有关的数据结构

图4-11动态分区分配算法流程图

54

第四章落储器管理

4.3.7有关分区管理的讨论

・1.分区存储管理的特点

A优点：实现了多个进程对内存的共享，有助于

多道程序系统；提高了资源利用率；要求的硬

件支持少；管理简单，实现容易。

A缺点：内存利用率仍然不高，小碎片多；进程

大小受分区大小的限制；不能部分装入，难以

实现各分区间的信息共享；无法实现虚存。

55;要剧球

k上章程储器管理

•2.关于虚存的实现

＞虚存：用户进程所需内存容量只受内存和外存

容量之和的限制的存储器技术。单纯的分区管

理是无法实现虚存的。

Trw

2）对换Swapping

■换出Swap_out：将内存中阻塞且优先级最低的进程

（程序+数据）换到外存交换区，修改其PCB并回收相

应内存。

■换入Swap_in：将外存交换区中静止就绪且被换出时

间最久的迸程（程序+数据）换入内存并修改其PCB。

■对换分类：

♦进程对换（整体对换）

♦部分对换（页面或分段对换）——真正意义上实现虚存

■对换的三个关键操作：换出、换入、对换空间

（pagefile.sys）的管理。

■对换缺点：换入换出开销大。

57

W

第四章落储器管理

③关于地址变换和内存保护

■地址变换：不实现紧凑时可采用“静态可重定位

装入”方式，实现紧凑时必须采用“运行时动态

可重定位装入”方式。

■内存保护：

♦硬件法：为每个进程设置一对上、下界寄存器，或利用

分区的基址寄存器和限长寄存器。若越界则产生地址保

护中断并转错误处理。

♦软件法（保护键法）：为被保护分区设置保护键开关字段,

针对不同的进程赋予不同的开关代码，通过检查两者是

否匹配来实现读、写保护。

♦软硬结合法。

第四章存储器管理

4.4基本（静态）分页存储管理方式

4.4.1页式管理的基本原理

A回顾分区分配法：碎片问题严重，内存利用率不高；

由于要求连续存放，导致进程的大小仍受分区大小和

内存可用空间的限制；不利于共享；无法实现虚存。

A引入页式管理的目的：为了减少碎片，为了实现换入/

换出而采用离散存储，提高内存利用率。

A分页存储管理：将一个进程的逻辑地址空间分成若干

个大小相等而片，称为页唳页，并为各国力嗯缄号，

从0开始，如第0页、第1页等。相应地，也把内存空间

分成与页面相同大小的若干个存储块，称为（物理）块或

页框（frame）,也同样为它们加以编号，如0#块、1#块

等等。在为进程分配内存时以块为单位，将进程中的

若干人页分别装入到多个可以不相邻接的物理块中。

由于进程的最后一页经串装不满一块而形成了不可利

用的碎片，称之为“页山碎片”。

59Kg

第四章落储器管理

•1.页面

A一个进程的虚拟空间被划分为若干个长度相等

的页面(page),通常几KB〜几十KB为一页，故

进程的虚地址(逻辑地址)可由页号P与页内地址

W所组成。

页号P页内地址W

231090

假设这是某系统的分页地址结构，则该系

统页长为2io=lO24B即1KB/页，一个进程

最长允许有214=16384页即16384KB

60■工

第四章落储器管理

A与进程逻辑空间的分页结构类似，物理内存空

间也被划分为与页面相等大小的若干物理块。

A在为进程分配内存时，将进程的N个页面（必定

连续）装入到N个内存物理块（不一定连续）。即:

连续的N个页面对应装入不连续的N个物理块。

式

页管理特点：无外碎片的概念；且内碎片必

小

定于一个物理块；实现了非连续（离散）方式

储

存

大

增,为虚存的实现提供了基础；但管理开销

»关键问题：如何将页面逻辑地址变换为内存物

理地址？

-页表+硬件地址变换机构

W

•2•页表(PageMappingTable)

A由于在分页系统中，允许将进程的n个连续页离

散地存储在内存不连续的n个物理块中，为此，

系统又为每个进程建立了一张页面映像表，简

称页表。在进程地址空间内的所有页(0〜n),依

次在页表中有一页表项，其中记录了M应页在

内存中对应的物理块号，见图4-12的中间部分。

在配置了页表后，进程执行时，通过查找该表，

即可找到每页在内存中的物理块号。可见，页

表的作用是实现小页号到其理块号的投址映射。

~物理块号

W

细章启承器管理

说明:

•页表负责记录遂聘

页面与内存物理块

的对应关系

•每个进程都有自己

的一张页表

•页表的长度由进程

大小和页面大小共

同决定：比如一进

程为4765B,若页

面大小为1KB/页，

则该进程包含5页

（第0页〜第4页），即

该战程的页表包含

5个表项

63

W

思考几个问题

①页面大小一般为2n字节，但具体n有多大？过小怎

样？过大怎样？

■过小：则页表过长，换入/换出效率低，使用和维护的开

销大。

■过长：页内碎片大。

②已知逻辑地址和页面大小，如何计算页号及页内

地址？

■页号=逻辑地址/页面大小（整除运算）

■页内地址=逻辑地址％页面大小（求余运算）

■例：已知页面大小为1KB/页，现有一数据的逻辑地址为

2148,问：该数据在哪页的哪个位置？

♦页号=2148/1024=2,页内地址=2148%1024=一,

100,即：该数据在该进程的第2页的相对地址100处名人

64

w

3.静态页式管理（基本页式管理）

＞必须将一个进程的所有页面全部装入到内存物理块,

无法实现虚存。

4.动态页式管理

＞允/您二个进程的一部分页面装入到内存物理块。

＞采用“请求调页”或二禅调页”技术实现了内外存存

储器的统一管理即对换技术。

＞内存中只存放那些经常被执行或将要被执行的页面，

而不常被执行或近期内不会执行的页面则存放在外存,

待需要时再按请求式调入。

5.分页管理的重点

①逻辑地址》物理疝址的地址变换（页表+硬件地址变

换机构）.

②页面的动态置换技术

65；

第四章落储器管理

4.4.2地址变换机构

•1.基本的地址变换机构

»地址映射：连续的N个页面对应于不连续的N个物理块

-逻辑页号”物理块号：查页表

-页内地址9块内地址：两者相等

»从成本和容量上来考虑，采用寄存器来存储页表是不

现实的。因此，页表大多驻留在内存中，而在系统中

只设置一个页表寄存器PTR(TableRegister),在其

中存放该进程的页表在内存的始址和页表的长度。平

时，进程未执行时，页表的始址和页表长度存放在本

进程的PCB中。当调度程序调度到某进程时，才将这

两个数据装入页表寄存器中。因此，在单处理机环境

下，虽然系统中可以运行多个进程，但只需一个页表

寄存器。

66

W

A地址变换算法

-当某进程被调度执行时，将其PCB中记录的页表始

址S和页表长度L取出来放到“页表寄存器”中；同

时，分页地址变换机构会自动将逻辑地址划分为页

号P和页内地址W,然后用页号P与页表长度L比较：

若PNL则越界中断，否则合法，再以页号P去检索页

表，查得该页P对应的物理块号，进而算得该块在内

存的起始地址B,最后B与页内地址W（即块内地址）

相加就得到了要访问的物理地址。这样便完成了从

逻辑地址到物理地址的变换。图4-13示出了分页系

统的地址变换机构。

67

W

第四章落储器管理

越界中断

图4-13分页系统的地址变换机构

68

第四章存储器管理

1。

■例：已知页面长度为1KB/页，某进程的页表如图所

示。现有逻辑地址为100的一条指令LOADR19

[2500]o问：

»试说明该指令的取指过程？

»试说明该指令的取数过程？

页号块号

02

13

28

第四章落储器管理

越界中断

页表寄存器逻辑地址100

页表始址页表长度3<页号0页内地址100

+

页号物理地址

-0A块号2块内地址100

1

2

该指令的物理地址为2148

页表

逻辑地址为100的指令的取指过程：

•页号=近科地址/页长=100/1024=0

・页内地址=逻辑地址％页长=100%1024=100

•物理地址=物理块号*块长十境内地址=2*1024+100=214870

逻辑地址为100的指令的取教过程（该教的逻辑地址为2500）：

•页号=近科地址/页长