操作系统第4章存储管理

第四章存储管理

（内存管理）

进程管理

进程管理涉及到如下内容:

进程的表示

--PCB

进程的创建

-可合并，也可分开

程序的加载

进程的运行——调度

进程管理

进程的同步-锁、信号量等

进程的通信

厂内存

进程的终止文件

进程的资源I/O设备

存储管理的任务

在单道程序环境中，同一个时间内，系

统中只存在一个进程，它独占系统的所有资

源，当然资源也归它管理，操作系统可以不

提供专门的管理服务。

在多道程序环境中，系统中同时存在多

个进程，所有的进程共享系统资源，包括内

存和外存。因此必须将存储的管理权收回，

由操作系统统一管理系统的存储。

存储管理的任务

进程对存储的需求:

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

2、永久性存储输入/输出数据」

3、存放程序执行代码

内存

4、存放临时性数据

存储管理的任务

进程对内存管理的需求：

1、大的内存，需要多少就有多少。

2、保护，不受其它进程的干扰。

3、共享，能与指定的进程共享部分内

存。

存储管理的任务

操作系统内核对内存管理的需求：

1、满足进程的需求，为进程提供内存服务。

2、高的内存利用率，减少对内存的浪费，

充分发挥内存的作用。

3、高的内存管理效率，提供快速的分配和

回收内存资源的手段。

存储管理的任务是：

1、存储资源的分配与回收。

2、存储保护与安全。

3、存储共享。允许两个或多个进程共用内

存中相同区域。

4、内存“扩充”。使用户基本不受实际内

存容量的限制。

5、程序重定位。

6、地址转换。

4.1引言

一、存储器的层次

外存（辅存）：指磁盘、磁带、光盘

等存储器。

外存容量大、价格低，其上的数据不

容易丢失。因而通常用外存存放程序或数据

文件。外存的最小访问单位是块，因而又称

为块设备。

处理器不能直接访问外存上的数据。

必须先通过控制器将其读入内存而后再访问。

4.1引言

内存（主存）：指CPU能直接访问的存储器。

为了管理的方便，把内存抽象成一个字节

数组，其中的每个字节都有自己的地址。CPU可

以通过地址随机地访问内存的任何一个字节。

与外存相比，内存容量小、价格高，而且

掉电后其中的数据会丢失。

所以通常把内存作为程序执行和数据加工

的场所。

4.1引言

内存虽比外存快，但与CPU相比，其速度

仍然很低。为了提高处理器的运算速度，还需

要提供与其速度匹配的存储器，这就是高速缓

存。

高速缓存(Cache)是内存的缓存，它速

度高、价格也高，因而容量小。

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

4.1引言

外

存

magnetictapes

4.1引言

在这种存储层次结构中，内存是外存的

缓存，而Cache又是内存的缓存。这是成本

与速度折中的结果。

在这种结构中，一个数据会同时出现在

几个地方。

操作系统只关心内存和外存，本章只关

心内存。

4.1引言

二、程序的编译、连接和装入

1）用高级或汇编语言开发源程序，一般情况

下，源程序由多个模块组成。

2）将源程序模块编译或汇编成目标代码。

3）连接程序将各个目标文件连接在一起，并

解析其中的符号引用，形成可执行文件。

4）进程执行程序。但在执行之前需要先将可

执行文件中的程序装入内存形成进程映像。

4.1引言

如下图:Memory

4.1引言

Loader的任务：将连接到一起的可执行

模块加载到内存。

主要问题：将可执行模块加载到内存的

什么位置？

程序中可以使用实际的物理地址、符号

地址（标号、变量名、函数名等）或相对地

址等来表示它引用的内存位置，但处理器只

认实际的物理地址，因此在执行程序之前，

必须将其中的符号地址、相对地址等转换成

实际的物理地址。

4.1引言

1、程序员完成地址的转换

程序员在开发程序时采用的就是实际的物

理地址，当然在可执行模块中采用的也是实际

的物理地址。

只能将采用实际物理地址的程序装入到内

存的固定位置（即程序员确定的位置），而且

每次都必须将其装入到同一个内存位置，否则

它将无法运行。

这种装入方式叫做绝对装入。

4.1引言

2、编译（汇编）程序完成地址转换

程序员直接使用实际的物理地址编程会产

生如下问题：

（1）需要程序员了解物理内存的使用情况,

并预先确定程序在物理内存中的位置。

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

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

最好的办法是在程序中使用符号来标识地

址，让编译（汇编）程序将其转换成实际的物

理地址。如下图：

4.1引言

1024

ProgramProgram

jmpLl—jmp1424

Ll1424

movax,var-—movax,2224

DataData

var2224

符号地址绝对地址

4.1引言

3、装入程序完成地址转换

在多道程序的环境中，内存中存在多个

程序，编译或汇编程序实际上无法确定程序

在内存的物理位置。因此，最好将决定程序

位置的工作向后推迟，交给Loader。

要让装入程序决定位置，需要可执行模

块是可重定位(Relocatable)的，即可以将

其装入到内存的任何位置。

4.1引言

具体的做法是：

(1)仍然让编译或汇编程序转换符号地

址，但转换的结果不再是绝对的物理地址，

而是一种相对地址(RelativeAddress),

即相对于某个位置的偏移量，如相对于程序

开始位置或当前位置的偏移量。

4.1引言

(2)装入程序在加载该程序时，为其

选择一个内存位置，如x,而后将程序中所

有对内存的引用地址都加上x,为程序定

位。一次性定位，又称静态重定位。

这种装入方式称为静态可重定位装入。

4.1引言理

50妙,

一Program

0

ProgramProgramjmp5400

jmpLI—jmp4005400

movax,6200

L1400

movax,var-—movax,1200

Data

DataData620012345

var120012345

/

一

/

/

符号地址相对地址x\

4.1引言

4、在执行时完成地址转换

采用静态可重定位装入方式可以将程序装

入到内存的任何位置，但一旦装入，其地址就

转换成了绝对的物理地址，程序的位置也就固

定了。

在多道程序环境中，为了提高处理器和内

存的利用率，经常需要将某个进程的程序换出

内存，当再次需要时再将其换入内存。

静态可重定位装入问题：限定了程序只能

被换入到同一个位置。

4.1引言

解决的办法是：

(1)将地址的转换推迟到实际执行程序

时。

(2)编译(汇编)或连接程序生成可重

定位的目标模块，其中的地址都是相对的。

(3)装入程序直接将可重定位模块加载

到内存，不做相对地址到物理地址的转换。

4.1引言

(4)处理器在执行程序的过程中，逐步

完成相对地址到物理地址的转换。动态重定

位，需要硬件支持。

这种装入方式称为动态可重定位装入。

4.1引言

4.1引言

连接程序的任务是将编译（汇编）后的目标

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

成一个可执行模块，用于程序的加载（装入）。

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引言

完成连接的时机有以下几种：

1、在程序设计时。所有的程序都放在一

个文件中。

2、在编译（汇编）时。编译（汇编）程

序找到所有子程序的源代码，并将它们编译

（汇编）在一起。

4.1引言

3、在装入前。各模块分别编译（汇编）

并生成可重定位的目标模块。由连接程序

将各目标模块整合成一个完整的可重定位

目标模块。

4、在装入时。装入程序先将主模块读

入内存，而后再根据其中的符号引用逐个

读入子模块，修改各子模块的相对地址，

并解析各符号引用。

4.1引言

5、在执行时。在程序装入时也不作连

接工作，Loader只装入程序的主模块，而且

不解析其中的符号引用。当程序执行到某符

号引用时（如子程序调用），它会发现该符

号对应的程序模块不在内存，此时，操作系

统再找到相应的目标文件，并将其装入内存。

4.1引言

在主模块中调用的不能仅仅是一个符

号，否则处理器会产生错误。为此，编译

（汇编）或连接程序会用一个Stub代替子

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

找到驻留在内存中的子程序，或将其装入

内存。这种连接方法称为动态连接。

利用动态连接可以实现共享库（动态

连接库）。

4.1引言

动态连接与动态可重定位装入结合起来，

可以实现很灵活的进程加载机制。

“动态可重定位装入”允许将程序加载到

物理内存的任何位置，而且允许多次换入/换

出，每次换入的位置都可以不同。这给内存管

理提供了很大的发挥空间。

4.1引言

“动态连接”允许只加载部分程序

（主程序），其它程序的加载被推迟到

了真正需要时。这既节约了内存、加快

的程序加载的速度，又提供了共享库函

数的可能。

“动态连接”还使程序的动态升级

成为可能。只要升级函数库，不需要重

新编译、连接，就可以使程序得到升级。

4.1引言

三、地址空间

名字空间：用户源程序中由符号指令、

数据说明等符号名字构成的空间。

地址空间：由程序中相对地址组成的

空间，也称逻辑地址空间。（以0为基址顺

序排列下来）

4.1引言

存储空间：内存中一系列存储信息的物理

单元的集合，也称为物理空间或绝对空间。

外存内存

4.1引言

由CPU生成的地址称为逻辑地址，如果程

序按照动态重定位方式装入，其逻辑（虚拟）

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

地址转换机构：内存管理单元（MMU-

Memorymanagementunit）硬件设备

数据结构：映射表如段描述符表（LDT）

或页表。

4.1引言

如果程序按照动态重定位方式装入，那么

在用户程序中看到的、使用的全部都是逻辑

（虚拟）地址，所以它不再受物理内存大小的

限制，只受地址位数的影响。

通过映射表，操作系统可以将各个进程的

逻辑（虚拟）地址空间完全隔开（实现保护），

也可以让它们有部分重叠（实现共享）。

4.1引言

四、覆盖（Overlay）

在程序加载时要考虑内存的大小。

问题：如何在有限的物理内存中加载、运

行大应用程序？

方法：覆盖（Overlay）。

4.1引言

基本思想：

按照程序的执行顺序，将程序分成几

部分；

装入程序先装入它的第一部分，运行

完后再装入第二部分；

第二部分程序覆盖第一部分程序，从

而节省空间。

4.1引言

如编译程序通常分成两阶段：第一阶段

生成符号表和中间代码，第二阶段生成目标

代码。

因此可以把整个编译器程序分成两部分:

第一部分：第一阶段程序+公共代码+符号表

第二部分：第二阶段程序+公共代码+符号表

4.1引言

假定：

第一阶段程序70KB

第二阶段程序80KB

公共代码30KB

符号表20KB

如不米用覆盖技术，程序运行需要200KB内

存。

如采用上述覆盖技术，最多只需要130KB内

存。

4.1引言

覆盖的问题：需要程序员对程序代码

有透彻的了解，而且需要能够生成覆盖程

序的特殊编译、连接程序。

覆盖技术不需要操作系统提供支持。

覆盖技术可以压缩单个进程的物理地

址空间，但不能增加系统中可用物理内存

的数量。

4.1引言

五、交换（Swapping）

增加可用物理内存的方法是：将某些暂不运行的

进程的映像写回磁盘（换出），回收它的物理内存；

当进程再次运行时，再将其读入内存（换入）。

在早期的分时系统中，内存中只保留一个进程，

其余进程全部放在外存。

进程调度、切换时，需要将当前进程换出，将下

一个进程换入，其代价很高。

KT4.1引言

operating

system

(V)swapout

(T)swapin

user

space

backingstore

mainmemory

4.1引言

交换要耗费很多时间。

例如，设用户程序是20K字节，外存平

均存取时间是8111s，传输速度是250000字节

/S,则传送20K字节的程序需用时间为

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

交换的核心问题：使交换的信息量减到

最小。

一种做法是下面的洋葱皮算法：

4.1引言

(1)存储分配过程

123456

4.1引言

(2)时刻J4各进程使用内存情况

20K进程1

空闲区

进程3

进程2

在内存

进程4在外存

4.2基于分区的存储管理

物理内存的表示:

通常以内存块为单位管理内存。内存块由字

节数组中的一系列连续的字节组成。

在进程的运行过程中，也会不断地提出对内

存的需求，如创建数据结构、缓冲区、堆栈等，

这些内存也是连续的内存块。

进程对内存的最大需求来源于程序的加载。

4.2基于分区的存储管理

随着系统的运行，内存会被逐渐地分割开，因此

需要一个数据结构（如链表、数组）来记录各内存块

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

空闲块

I

已用

开始位置大小使用情况

04MB已用

4M3MB未用

I

■

4.2基于分区的存储管理

操作系统如何管理内存？

一种简单的管理办法是：将内存划分成

区，给每个进程分配一个区，进程自己管理

区内内存的使用，但不许跨区使用内存。

——内存的分区管理。

问题是如何分区？

4.2基于分区的存储管理

一、固定分区法

由操作系统或系统管理员预先将内存划分

为若干分区，每个分区容纳一个进程。在系统

运行的过程中，分区的边界不能再改变。

当要把一个进程装入内存时，操作系统为

其找一个满足下列条件的分区：

■空闲。

■尺寸大于或等于进程的大小。

4.2基于分区的存储管理

分区尺寸的确定：根据以往的统计信息和

系统的特殊需求预先确定的。

大致有两种确定分区尺寸的方法：

1、等尺寸分区一一各分区具有相同的尺寸

OS

8MB

8MB

8MB

8MB

8MB

4.2基于分区的存储管理

等尺寸分区法的问题：

(1)增加了程序设计的限制。当程序过

大时，不得不采用覆盖(Overlay)技术。

这增加了程序设计的难度。

(2)内存的利用率低。如一个1MB的程

序也会占用8MB的分区，造成7MB的浪费。

分区内部的内存浪费称为内部碎片。

4.2基于分区的存储管理

2、不等尺寸分区一一各分区可以具有不同的尺寸

os

2MB

4MB

6MB

8MB

8MB

12MB

16MB

4.2基于分区的存储管理

不等尺寸分区的分配方法以下几种：

(1)固定分配。只给进程分配能满足其需

要的最小尺寸的分区。如分区已被分配，则进

程必须等待。

好处：使内部碎片最小化。

问题：可能出现不公平的等待，如虽有大

尺寸的空闲分区，小进程却无法运行。

4.2基于分区的存储管理

(2)最佳适应分配。给进程分配能满足其

需要的最小尺寸的可用分区。只有当所有

分区都已被分配时，进程才需要等待(或

换出别的进程)。

好处：比较灵活

问题：会产生较大的内部碎片。

4.2基于分区的存储管理

固定分区法比较简单，但却存在如下问题:

(1)分区的个数限定了同时驻留内存的进

程个数。

(2)分区的大小和数量是在系统生成时确

定的，在运行过程中不能调整，会导致较低的

内存利用率，和大量的内部碎片。

(3)进程不能跨区使用内存。

4.2基于分区的存储管理

解决办法：抛弃“固定”的概念，不

预先确定分区的大小和数量；将划分区域

的工作推迟到实际分配内存（如加载程序）

时进行。

一可变分区法

4.2基于分区的存储管理

二、可变分区法

基本思想：

初始情况下，把所有的空闲内存看成一大

块，或一个大的分区。

当进程要装入程序时，按照它的要求，临

时从空闲内存中为其划出一块，构成新的分区。

新分区的尺寸等于程序的大小。剩余的空闲内

存构成另一个新的分区。

4.2基于分区的存储管理

OS128KOS128KOS128KOS128K

进程工320K进程工320K进程1320K

896K进程2224K进程2224K

576K

352K进程3288K

64K

初始状态加载进程1加载进程2加载进程3

4.2基于分区的存储管理

随着系统的运行，进程不断地被创建、换

出、换入，产生的内存碎片越来越多。如下图

128K

224K

96K

128K

96K

288K

64K

进程2进程4进程1进程2

被换出被加载被换出被换入

4.2基于分区的存储管理

在分区外部的小“碎片”称为外部碎

片。

固定分区法会产生内部碎片，而可变

分区法会产生外部碎片。外部碎片会使内

存变得越来越零碎，直至无法使用。

4.2基于分区的存储管理

解决外部碎片问题的一种方法是：紧

缩(Compaction)o即移动内存中的进程,

将碎片集中起来，重新构成大的空闲内存

块。

如上图，紧缩以后可以生成256KB的空

闲内存块。

4.2基于分区的存储管理

紧缩的代价：

1）对地址敏感的项必须作适当修改，

如基址寄存器、访问内存的指令，参数表

和使用地址指针的数据结构等。

2）需要动态重定位的支持。

3）紧缩是很费时的操作。

4.2基于分区的存储管理

紧缩时机：

1）当进程结束，释放了所占用的分区,

如果它不与空闲区邻接，就立即进行紧缩。

2）在分配进程的分区时，如果不能满

足需求则进行紧缩。

紧缩的次数就比1）少得多，但空闲

区的管理较前要复杂。

4.2基于分区的存储管理

在可变分区法中，为了减少外部碎片的产生，需

要仔细选择内存分配算法，或可变分区算法。

内存分配：从空闲内存块中选择一个合适的块，

将其分割开，一部分分配给进程，一部分作为碎片保

留。

内存回收：把进程的内存作为空闲块收回，合并。

数据结构：空闲块链表，或空闲块数组。记录每

个空闲块的位置、大小等信息。

4.2基于分区的存储管理

常用的分配算法有三个：

1、最先适应算法（Firstfit）

2、最佳适应算法（Bestfit）

遍历所有空闲块，将满足需要的最小空闲块

分配给进程。

3、下一个适应算法（Nextfit）

从上次分配的位置开始向后搜索，将第一个

满足要求的空闲块分配给进程。

4.2基于分区的存储管理

8K申请16K

12K12K

22KFirstfit

6K

18KBestfit

次

上2K

配

分

置

位8K8K

6K6K

14K14K

Nextfit

36K

20K

4.2基于分区的存储管理

1、最先适应算法：

快；从头分配，分区相对集中在内存的

前部，大空闲块存留到后面；

便于内存释放后合并。

2、最佳适应算法：

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

需要更频繁地紧缩。

4.2基于分区的存储管理

3、下一个适应算法：

对内存的使用较平均，不容易留下大

的空闲块。

上述三个算法哪个最好？

最先适应算法是最优的，下一个适应

算法次之，最佳适应算法是最差的。

统计表明，大致有1/3的内存因为碎

片而浪费。

4.2基于分区的存储管理

与固定分区法相比，可变分区法比较灵活,

而且避免了内部碎片，但却出现了外部碎片。

原因：可变分区法没有对分区的尺寸和分

割的方法作任何限制，所以容易将内存切割得

太无规则、太零碎。

4.2基于分区的存储管理

解决方法：将分区的大小限定为2k,

并且按照平分的方式分割内存，则各个分

区就会变得较有规则，分割与合并就会更

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

——伙伴算法

4.2基于分区的存储管理

三、伙伴算法（Buddy）

在伙伴算法中，内存块的尺寸为2£

L<K<U；

2L是允许分配的最小内存块的尺寸；

2U是允许分配的最大内存块的尺寸，即

全部可用物理内存的大小。

4.2基于分区的存储管理

分配方法如下：

■1、将全部可用的物理内存看成一块，大小为2L

■2、如果请求的大小为s(2u-1<s<2u),则将全

部内存分配给它。

■3、否则，将内存分割成两个相等的伙伴，大小

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

则将一个伙伴分配给它。

・4、重复分割伙伴，直到其尺寸刚好满足请求。

4.2基于分区的存储管理

释放方法如下：

■1、如果物理页块的伙伴不在空闲队列，则将

被释放的物理页块直接插入空闲队列。（只有

伙伴才可以合并）

■2、如果物理页块的伙伴在空闲队列中，则将

它的伙伴从队列中摘下，将它们合并成一个更

大的物理页块，重新插入另一空闲队列（递

归）。

4.2基于分区的存储管理

数据结构：一组链表，链表i中排列的是大小

为2i的空闲内存块。

大小为2i+l的空闲内存块被分割后，它将被从

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

（大小为2D。

如果大小为2i的两个伙伴都已空闲，可以将它

们从链表i中删除，组合成一个大小为2i+i的新空闲

块，并加入到链表i+1中。

4.2基于分区的存储管理

1MB内存1M

申请100K128K128K256K512K

申请240K128K128K256K512K

申请64K128K6464256K512K

申请256K128K6464256K256K256

释放240K128K6464256K256K256

释放100K128K6464256K256K256

申请75K128K6464256K256K256

释放64K128K128K256K256K256

释放75K512K256K256

释放256K1M

4.2基于分区的存储管理

伙伴算法的特点：

♦:♦是固定分区和可变分区法的一个折中，比

固定分区法灵活，不受分区尺寸及个数的

限制；它比可变分区法规范，不会出现外

部碎片。

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

。会产生内部碎片，但内部碎片的浪费不会

有固定分区那么多。

4.2基于分区的存储管理

在Unix和Linux系统中，采用伙伴算法

管理物理内存，但在具体实现上有一些变

化。

如在Linux中，伙伴的最小单位是页

(212Byte)而不是字节。

4.3基于分段的存储管理

在目前考虑的所有分配方法中，都把进程看成一

个整体，只能同时被加载、释放、换入、换出。

特点：实现简单，只需要记录进程的开始地址和

界线，利用动态重定位技术即可实现地址的转换。

问题：需要为进程准备大块的、连续的内存，增

加了分配的难度，也增加了进程加载、换入、换出的

时间。

4.3基于分段的存储管理

从用户的角度看，进程并不是一块连续的内存块,

而是一组具有不同意义、不同大小的内存段。

logicaladdressspace

4.3基于分段的存储管理

从用户的角度看，进程是由几部分组成的。

可以将其分开加载到内存的不同区域。

减轻对大块连续内存的需求压力，也可减少

I/O操作。

每个进程都需要一个段表来描述进程各个分

区的开始位置和界线，增加了实现的难度。

4.3基于分段的存储管理

,_____甘

代码

♦臾建段名序号基地址大小

代码0200600

.甘阳

数据12300100

建

♦界EB我

堆栈28000200

■甘M+iL

XLEIJUL

堆栈

.)臾建

4.3基于分段的存储管理

在分段技术中，每个逻辑地址由两部分组成：

段号：在进程段表中的序号，用来确定分区的

开始位置和界线。如Intel中的段选择符。

偏移量：即相对地址，是相对于分区开始位置

的偏移量，用来定位内存单元。

地址的转换需要硬件的支持，即需要硬件机制

动态地完成逻辑地址到物理地址的转换。

当不能转换时产生缺段中断。

4.3基于分段的存储管理

地址转换过程:

CPU

4.3基于分段的存储管理

分段技术要点：

♦：♦一个进程可以占用多个小分区。

♦:♦各个小分区可以不连续。

♦:♦各个小分区的尺寸可以不一样（可变分区）。

♦:♦不存在内部碎片。外部碎片也变少。

♦:♦需要为每个进程提供一个段表。

♦:♦需要硬件机制动态地完成逻辑地址到物理地址的转

换。

4.3基于分段的存储管理

在Intel处理器中，逻辑地址到线性地址的转换:

15o31Q

Logical

Address

4.3基于分段的存储管理

利用分段技术可以实现内存保护。

段表中的每一项是一个段描述符，其中

可以包含一些保护信息，如段的大小（界线）

和访问方式（只读、读写、执行等）。

在每一次地址转换前，都要作合法性检

查，如地址是否越界、访问是否合法等。这

种检查是由硬件完成的，且不可屏蔽。

4.3基于分段的存储管理

利用分段技术可以实现内存共享

(Sharing)。

如果一个段描述符出现在两个进程的

段表中，那么在两个进程中都可以访问到

该段的内容，从而可以实现内存的共享。

4.3基于分段的存储管理

进程1的段表

进程2的段表

4.3基于分段的存储管理

段式管理的优点：

1、有利于用户对程序地址空间的了解，便于对各

程序段的共享和保护。

2、允许用户地址空间大于实际的物理内存空间，

为多道程序运行提供了支持。

3、便于动态连接，从而避免静态连接造成的某些

时间和空间的浪费。

段式管理的缺点：

1、复杂，增加硬件成本，增加软件运行开销。

2、分段的大小受内存容量的限制。

4.4基于分页的存储管理

分段技术的特点：

1、可以减少外部碎片，却不能消除；

2、需要用户的参与，不利于操作系统透明

地管理。

固定分区技术特点：

1、不会产生外部碎片，却可能产生内部碎

片。

2、限定一个进程只能使用一个分区。

4.4基于分页的存储管理

对固定分区技术作如下修改：

1、取消一个进程只使用一个分区的

限制，允许进程使用多个分区；

2、压缩分区的尺寸，使各分区足够

小。

4.4基于分页的存储管理

结果：

1、给一个进程分配多个小的固定分区。

2、属于一个进程的小分区可以不连续。

3、消除了外部碎片，减少了内部碎片。

4、以分区为单位实现进程的换入/换出。

当分区足够小时，换入/换出的代价很小，而且

允许进程部分地驻留内存。

分页(Paging)技术

4.4基于分页的存储管理

一、分页管理

问题1:采用等尺寸分区还是不等尺寸分区?

不等尺寸分区需要记录各分区的大小和开

始位置，实现较复杂。

等尺寸分区只需要记录各分区的开始位置，

实现相对简单。

使用等尺寸分区，即各分区的大小相等，

称为帧(Frame)。

4.4基于分页的存储管理

问题2：帧的尺寸应取多大？

如果帧过大，足够容纳下一个进程，那么

分页技术就蜕变成了固定分区技术。

如果帧过小，如大小为一个字节，则分页

技术就变成了可变分区技术。

4.4基于分页的存储管理

内部碎片的平均大小是半个帧，为减少碎片,

帧应小。

研究表明，帧的大小应在512到8192字节之

间。

为了管理的方便，帧的大小应是2的指数。

在Intel处理器上，帧的大小为4096字节。

4.4基于分页的存储管理

问题3：如何分割进程的地址空间（程序和

数据）？

将进程的逻辑（虚拟）地址空间分割成小

块，大小与帧相同，称为页（Page）o由操作

系统自动完成。

当要加载（换入）一个进程时，将进程的

一个页加载进内存的一个帧。

进程在内存中占用的帧可以不连续。

4.4基于分页的存储管理

0

1K

0

2K

1K

2K3K

3K4K

4K5K

6K

页7K

表

8K

4.4基于分页的存储管理

问题4：如何完成地址转换？

假定页X被加载到了帧Y中，那么在页X中偏移量为

d的逻辑地址所对应的物理地址应该是：

帧Y的基地址+偏移量d

逻辑地址

物理地址

4.4基于分页的存储管理

假如页的大小为4KB。

X是位于第2页的一个逻辑地址，它相对于

该页开始位置的偏移量为d（d<4096）o那么该

地址相对于程序开始位置的偏移量为：2X4096

+do

（页号）2（偏移量）d

4.4基于分页的存储管理

如第2页被加载到了物理内存的第3帧,

则X对应的物理地址为：3X4096+do

（帧号）3（偏移量）d

逻辑地址2义4096+d对应的物理地址

为3X4096+d。

4.4基于分页的存储管理

一个逻辑地址由两部分组成:

页号P偏移量d

以P为索引查页表，如得到的帧号为f,则该逻辑

地址对应的物理地址为：

帧号f偏移量d

进程的程序必须是可动态重定位的。

地址转换需要硬件的支持。

4.4基于分页的存储管理

m+1

页表

4.4基于分页的存储管理

每个进程都需要一个页表。

问题：页表放在哪里？

1、如果页表较小，可以用寄存器存放当前

进程的页表。如PDP-11计算机采用16位地址，

页的大小为8KB,每个页表最多有8个页表项。

处理器提供了8个寄存器，用于存放页表。进程

切换时，同时切换这8个寄存器。

4.4基于分页的存储管理

2、进程的页表较大，则需要放在内存中，

并将页表的基地址(Pagetablebase)记录

在进程的PCB中。

如目前的Intel处理器采用32位地址，页

的大小为4KB,单个页表最多可有1024X1024

个页表项。无法用寄存器存放。

页表要用连续的物理内存，采用物理地址。

4.4基于分页的存储管理

处理器提供一个专用寄存器(PTBR)用于

记录当前进程的页表基地址。当进程切换时，

PTBR的内容也要切换。

当需要转换地址时，首先通过PTBR找到当

前进程的页表，而后查页表找到逻辑页对应的

物理帧，从而算出物理地址。

4.4基于分页的存储管理

问题：每次地址转换都需要多次访问内

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

解决方法：由处理器提供快速查找缓存

TLB(TranslationLookaside

Buffer),在其中缓存最近使用的页表项。

TLB的命中率在80%以上。

4.4基于分页的存储管理

带TLB的地址转换:

pagetable

4.4基于分页的存储管理

问题5：谁来完成地址转换？

在支持分页机制的系统中，处理器产生的逻辑地

址并不直接送到地址总线上，而要经过内存管理单元

(MMU)的处理。MMU负责完成地址的转换。

总线

4.4基于分页的存储管理

问题6：如何组织页表？

目前的计算机都支持大的逻辑地址空间，

因而需要大的页表。

如：在具有32位逻辑地址空间的系统中，

如果页的大小为4KB,则页表中应有1M的页表项。

如果一个页表项占用4个字节，则每个页表都需

要4MB的内存。

没有必要为每个进程都分配4MB的连续物理

内存用于存储其页表。

4.4基于分页的存储管理

解决办法：将页表分片，变单级页表为多级页表。

二级页表物理内存

4.4基于分页的存储管理

分级以后，进程的一级页表必须存在（保

存在进程的PCB中）。

二级页表可以不连续，可以不存在，甚至

可以被换出/换入。通常情况下，动态地创建

二级页表，从而大大减少其数量。

4.4基于分页的存储管理

分级以后，进程的逻辑地址也被分成多个部分:

4.4基于分页的存储管理

Intel处理器的地址转换:

LinearAddress

31222112110

r32bitsalignedontoa4-KByteboundary

4.4基于分页的存储管理

32位的SPARC采用三级页表。

32位的Motorola68030采用四级页表。

64位的UltraSPARC采用七级页表。

另有一些体系结构（PowerPC）采用反向页

表。

4.4基于分页的存储管理

问题7：页表项中应包含什么信息?

帧号和保护信息。如Intel的页表项格式如下:

4.4基于分页的存储管理

第0位是一个存在标志，表示逻辑页是否

已被加载进内存。

当逻辑页在内存时，P位为1,页表项中记

录的是物理帧的基地址，即逻辑页在内存中的

位置，处理器利用该地址可以将逻辑地址转换

为物理地址。

4.4基于分页的存储管理

当逻辑页不在内存时，P位为0,处理器无

法利用它转换地址，因而产生异常。

操作系统处理异常时，可以将逻辑页加载

进内存，并修改页表项，将P位置1。

当P位为0时，可以利用页表项记录逻辑页

在外存中的位置。

页表可以不在内存，此时页目录项中的P

位为0。

4.4基于分页的存储管理

U/S位和R/W位用来实现页的保护。

U/S=l,表示普通用户页，特权级为3。

R/W=O,表示页只能读，不能写。

在进程的页表中，0—3GB部分都是普通用户

页（U/S=l）,3GB—4GB是超级用户页（U/S

=0）O

4.4基于分页的存储管理

当进程的逻辑页第一次被加载到内存时，

其页表项才真正建立。以后，随着进程逻辑页

的换出/换入，其页表项会被反复修改。进程终

止时，其页目录和页表都会被释放。

在页被加载时，根据页的实际情况设置其

R/W位o

4.4基于分页的存储管理

D位表示页的内容是否被修改过。当页的

内容被修改时，该页的D位被置1。

操作系统根据该位就可以知道是否需要

保存页的内容。

A位表示页的内容是否被访问过。操作系

统通过检查该位可以统计页被访问的频率，知

道页是否最近被使用过。

4.4基于分页的存储管理

页表是由操作系统管理的。

页表将进程的虚拟地址空间和物理地址

空间完全隔开了，从而给操作系统创造了自由

发挥的空间和条件。

分页机制是现代操作系统的基础。

4.4基于分页的存储管理

问题8：如何管理帧的分配和释放？

数据结构：

1、描述系统中所有的帧（物理页）

Linux用一个page结构描述一个帧。

在系统初始化时，操作系统从BIOS中获得机

器物理内存的大小，算出总的帧数，而后创建

一个page结构的数组mem_niap口，描述系统中所

有的帧（物理页）。

每个物理页对应一个page结构。

4.4基于分页的存储管理

2、描述系统中所有的空闲帧。

Linux用一个free_area[]数组描述所有空闲帧。

4.4基于分页的存储管理

free_area□数组中有多个队列，其中：

free_area[O]上排列的是大小为1页的空闲块。

free_area[l]上排列的是大小为2页的空闲块。

free_area[2]上排列的是大小为4页的空闲块。

free_area[n]上排列的是大小为2rl页的空闲块。

用第一个物理页的page结构代表一个空闲页块。

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

每次分配出去的物理内存必须是2n个物理页（OWn）

4.4基于分页的存储管理

位图map中记录两个伙伴的使用信息：

1）如两个伙伴都已分配出去，它们的位为0；

2）如有一个伙伴空闲，它们的位为1；

3）如两伙伴都空闲，它们应在上一级队列

中。

4.4基于分页的存储管理

大小为2i、编号为m的物理页块的伙伴

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

这两个伙伴在位图freearea[i]->map中共

用的标志位是：m»(1+i)

如：页块8—H(代表是8)的伙伴是12-

T5(代表是12),它们在位图

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

4.4基于分页的存储管理

物理页（帧）的分配算法（申请2。逐改页）：

1、如果需要回收物理内存，则唤醒内核

交换守护进程kswapd,或强行回收（自己调用

回收函数）。

2、如果不需要回收内存或已回收到了足

够的内存,则查free_area数组的第order列：

1）如果其中有满足要求的页块，则摘下一块,

调整参数、位图，返回物理页块的首地址。

1m

1q//4.4基于分页的存储管理

2）否则（队列为空），向上搜索&ee_area数

组：

■如果上面的队列全空，则此次分配失败，返

回0。

■否则，将找到的大物理页块从其队列中摘下、

分割成伙伴，将一个大小适中的伙伴分配给

用户，其余伙伴加入相应队列，同时调整参

数、修改位图。

4.4基于分页的存储管理

物理页的释放算法：

1、根据物理页块的首地址算出它在

mem_map中的索引map_nr,找到物理页块的

page结构。

2、如果物理页块不是保留的，则释放它:

1）清除page结构中的PGjeferenced标

/8O

4.4基于分页的存储管理

2）将物理页块加入到数组free_area中：

■如果物理页块的伙伴不在队列free_area[order]

中，则将其直接插入队列，并修改位图。

■如果物理页块的伙伴在队列中，则将它的伙伴从

队列中摘下、修改位图，将它们合并成一个更大

的物理页块，重新插入数组freearea中（递归）。

4.4基于分页的存储管理

7

6

5

4

3