第四章 存储器管理课件

夕第四章存储器管理

MemoryManagement

□为多道程序的运行提供良好的环境

□提高存储器的利用率

□从逻辑上扩充存储器

本章主要内容

一♦一・—U■■■■A—/f・♦—―•・・・■

4.1存储体条

4.2程序的链接和装入

4.3连续分配方式

4.4基本分页存储管理方式

4.5基本分段存储管理方式

4.6虚拟存储器的基本概念

4.7请求分页存储管理方式

4.8页面置换算法

4.9请求分段存储管理方式

二章寤跚管

§4.1存储体系

在现代计算机系统中，存储器是信息外理的来源与归

宿，占据重要位置。但是，在现有技术条件下，任何

一种存储装置，都无法同时从速度与容量两方面，满

足用户的需求。实际上它们组成了一个速度由快到慢,

容量由小到大的存储装置层次。

§4.1存储体系

存储层次结构

使主存储器在成本、速度和规模之间获得较好的权衡。

§4.2程序的链接和装入

ProgramLinkingandLoading

ca一、用户程序的主要处理阶段

ca二、程序的装入

ca三、程序的链接

朱1

一、用户程序的主要处理阶段

将一个用户程序变为一个可在内存中执行的程序，通常

要经过以下几步：

。(1)编译Compiling)

9Sourcecode™>ObjectModule

O(2)链接(Linking)

9ObjectModules+Libraryfunction…>LoadModule

O(3)装入(Loading)

<LoadModule■■-internalMemory；构造PCB,形成

进程(使用物理地址)

编译器只能在一个模块内部完成符号名到地址的转换,

1同模块间的符号解析由链接器来完成的。

主

库

汇编

编译

k

『V'内存

第一步第二步第三步

图4・1对用户程序的处理步骤

符号地址、相对地址、绝对地址

源程序逻辑地址空间物理地址空间

0

BA=1000

LoadAdatal100

LoadA1200

编译地址映射

连接

12003456

datal3456200o

二章褊辘百

基本概念(BasicConcept)

。地址映射（重定位）：把逻辑地址空间中使用的逻辑地址变换成

内存空间中的物理地址的过程。

。物理地址：内存是一块存储区域，存储单位是字节（字），每个

字节都有地址。这种地址称为物理地址（绝对地址）。所有的物

理地址集合构成物理地址空间。

。逻辑地址：源程序经过编译连接形成可执行文件中的地址，通常

从o开始，程序中其余指令中的地址都相对于首地址而编址，这

种地址称为逻辑地址（相对地址、虚地址）。所有逻辑地址的集

合构成逻辑地址空间。

。符号地址：源程序中用字母和数字组成的符号代表存储器的地址。

二、程序的装入

ProgramLoading

4•IQ■■■■令•—♦・、间・•・——

一个程序运行装入到内存时，可有三种装入方式：

割(1)绝对装入方式(AbsoluteLoadingMode)

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

-fl⑶动态运行时装入方式(dynamicRun-TimeLoading)

1绝对装入方式(AbsoluteLoadingMode)

由装入程序根据装入模块中的地址，将程序和数据装

入内存。装入模块的地址是编译时由编译程序产生的，是绝

对地址。装入程序按装入模块装入内存时，不需修改地址。

。绝对地址可由程序员直接给出，或在编译或汇编时给出。

。这种方式要求事先已知程序将装入内存的位置。一般只在

单道程序的环境才有可能实现。

9优点：装入过程简单。

小缺点：过于依赖硬件结构，不适于多道程序系统。

例如:

逻辑地址空间内存

printfprintf

Ujj^JIOVOlFFI^JMOV01FFF,5

CALL01011SggaCALLOIOU

■M麴1

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

由装入程序根据内存当时的实际使用情况，将装入模块装

入到内存的适当地方。目标模块中为相对地址（逻辑地址）。

O装入模块中的逻辑地址与实际装入内存的物理地址不同。

装入内存时，要进行fii虐例

o可重定装入方式采用的静态重定位。

o其地址变换方式为：|物理地址=相对地址+内存起始地址

。优点：不需硬件支持，可以装入有限多道程序。

。缺点：一个程序通常需要占用连续的内存空间，程序装

入内存后不能移动。

1章褊辘毓

例如:

内存空间

逻辑空间0

3、动态运行时装入方式（dynamicRun-TimeLoading）

装入模块为相对地址，在装入内存时，并不立即变为物理

地址（绝对地址），即装入后仍为相对地址。只有在程序真正

执行到某一步时才对它进行地址转换（动态重定位）。

♦:♦优点：OS可以将一个程序分散存放于不连续的内存空间，

可以移动程序，有利用实现共享。

❖缺点：该方式需要一定特殊硬件的支持，OS实现较复杂。

是实现虚拟存储的基础。

例：如：

o*s曾定位寄彳军器

作业10

01000

111000

100

Load1,500■500・1100

Load1,500

相对地址\

500

123451500

12345

N1000+N

处理机存令斤器内存

一侧一磔

几个重要概念

Severalimportantconcepts

O绝对地址(AbsoluteAddress)>物理地址(PhysicalAddress)

O相对地址(RelativeAddress)>逻辑地址(LogicalAddress)

。符号地址(SymbolAddress)

O地址空间(AddressSpace)>逻辑地址空间

。存储空间(storagespace)、主存空间、物理地址空间

。重定位(Relocation):在把程序的目标程序装入到内存时的地址修

改过程，即LA”>PA.

O静态重定位(StaticRelocation)

。动态重定位(DynamicRelocation)

重定位

o概念：程序和数据装入内存时，需要对目标程序中的地

址进行修改，这种把逻辑地址转换为内存物理地址的过

程叫做重定位。

o类型：根据重定位时间和技术的不同，分为：

9静态重定位：程序执行前，一次性将该作业中程序的

指令地址和数据地址全部转换成绝对地址，装入内存,

且以后不能移动。

9动态重定位：在程序执行过程中动态地进行地址转换,

由地址变换机构（硬件）自动执行。

H二□章褥雌曾！

三、程序的链接

ProgramLinking

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

源程序经过编译后，可得到一组目标模块，利用链

接程序将这组目标模块链接，形成装入模块。链接阶段

产生的可执行目标程序在不运行时，通常作为一个二进

制可执行文件驻留在硬盘上。

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

(1)静态链接Staticlinking

(2)装入时动态链接Load-timedynamiclinking

(3)运行时动态链接Run-timedynamiclinking

需口章裾

1.静态链接

在装入内存之前进行，链接后形成一固定的装入模块（也

称为可执行程序），不再拆开。

目标模块1装入模块图

4

0

04—

printf(MOK");程

call1200H序

静

态

库模块1300H链

接

。voidprintf(…){示

)意

此方式需要解决：1）修改相对地址。

2）变换外部调用符号。

2.装入时动态链接

目标模块在装入内存时边装入边链接。

密入

衣20000H

call21200H

库模块21200H

0voidprintf(...)

)

1s

.U早m腐葩阂

优点:

❖1)便于修改和更新：由于各目标模块分开存放，只需对要修

改的模块修改后编译即可，保证所有的软件同步升级。

❖2)便于实现目标模块的共享：通常被链接的共享代码称为动

态链接库(DLL,Dynamic-LinkLibrary)或共享库(sharedlibrary)o

实现多个模块共享一个DLL而不要每个程序都含有该模块的拷贝。

3)便于运行环境适应：调用不同的DLL,就可适应多种使用环

境和提供不同功能。如：不同的显卡只需厂商为其提供特定DLL,

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

缺点：

每次都要链接装入所有的模块，不论是否用到。

例如：IFv条件〉THENS1ELSES2;

3.运行时动态链接

I一开始只链接装入部分模块，在运行过程中，若发现被调用模块

■不在内存，则发出请求，由OS查找、装入并链接到调用模块。

0

装入

printf(uOK");call33600H

执行

主模块

voidprintf(...)33600H

内存

库模块

通常链接和装入是一体的，其发展过程可分为三个阶段:

1.静态链接、静态装入2.静态链接、动态装入

3.动态链接、动态装入

§4.3连续分配方式

ContiguousMemoryAllocation

连续分配指为用户程序分配一个连续的内存空间。

Q-、单一连续分配

ca二、分区式分配

一、单一连续分配

SingleContinuousAllocation

物

。内存分为两个区域：系统区，用户区。

。单一连续分配：内存中仅驻留一道程序，整个用户区为一个

用户独占。

内存的保护

为了防止os受到用户程序有意或无意的破坏，可以设置

保护机构：如基址（重定位）寄存器和界限寄存器。

二、分区式分配

PartitionAllocation

为了支持多道程序运行，提出了分区式分配存储管理

方式。该方式中，内存用户区共多个用户程序使用，划分

成若干分区，每个分区容纳一个作业。按照分区的划分和

分配方式，常见的分区式分配有如下几种：

。固定分区分配

O动态分区分配

O可重定位分区分配

。伙伴系统

A

1、固定分区分酉己(FixedPartitionAllocation)

\7

1）基本原理：将内存空间分为若干个固定大小的区域，每

个分区装入一道作业。划分通常是在系统初使化时执行。

2）划分分区的方法

口分区大小相同：主要用于控制多个相同对象的场合。即各

处理对象的大小基本相同。

口分区大小不同：一般可划分多个小分区，适量中等分区，

少量大分区。可适应多种类型的作业。

3）内存分配

□数据结构：将分区按大小顺序排列；建立一张分区使用表,

包含分区起始地址、大小、状态等。

□分配过程：有内容要装入时，在分区使用表中查找大小能

满足且未分配出去的分区，若找到，则实施分配且修改分

区表中的状态。否则，拒绝分配。

例如：主存分配表

分区号起始地址长度占用标志

0S(8K)

18K16K0

用户分区1(16K)

224K16K0

用户分区2(16K)

340K32KJdbl

__________________________________________________________________________

内存中已分配给作业但未被利用的区域称

为“内零头”(internalfragment)

固定分区分配会有内零头产生。

固定分区分配方法小结

。优点：简单。

。缺点：

9实际系统运行时，往往无法预知分区大小（太大，等同

于“单用户分区模式”）；

9主存空间利用率仍然较低；

6分区数目预先确定，限制了多道运行程序的数量。

如今，几乎没有哪一种操作系统支持这种模式。

A

2、动态分区分配(DynamicPartitionAllocation)

\)

1）基本原理：内存不预先划分好，当进程装入时，根据进

程的需求和内存空间的使用情况来决定是否分配。

口若空间足够，则按需要动态为之分配连续的内存空间；

□否则，令其等待主存空间例如：

。在实现动态分区分配存储管理方式时，必须解决下述

三个问题：

❖动态分区分配中的数据结构；

分区分配算法；

分区的分配和回收。

2）动态分区分配中的数据结构

系统必须记录内存的使用情况，为分配提供依据。

❖1）空闲分区表：用表记

录内存中的所有空闲分区。每

一分区占一表目。可包括序号、

大小、始址等。

❖2）空闲分区链：用链方

式记录每一空闲分区。链上每

一分区中存储有指向前后分区

的指针及本分区的大小、状态

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

空闲分区链结点示意图

0

操作系统空闲分区表

400K

区号起始地址长度

1900K100K

900K

21700K300K

1000K

32300K260K

1700K空闲分区链

2000K0

900K1700K2300K

2300K100K300K260K

000NULL

2560K

3)动态分区分配算法

将作业装入内存时，选择哪个的内存分区进行分配。

常用的算法有如下几种：

O首次适应算法(First-FitAlgorithm)

O循环首次适应算法Next-fitAlgorithm)

O最佳适应算法(Best-fitAlgorithm)

O最坏适应算法(Worst-fitAlgorithm)

O快速适应算法(Quick・fitAlgorithm)(作业)

■II.首次适应算法(First-FitAlgorithm)

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

•要求：空闲分区以地址递增的次序链接。

•分配：从链首顺序查找，直至找到一个能满足大小的空闲

分区为止。按需要对其进行划分，分配、保留。例：

・倾向：利用低址分区。

♦:♦优点：分区组织简单；高址部分可容纳大作业。

。缺点：低址处外零头(externalfragment)多，查找

越来越困难。

例如:

系统中的空闲分区表如下，现有三个作业分配申请内存空间

100K、30K及7K。给出按首次适应算法的内存分配情况及分配后

空闲分区表。

区号大小起址

空

12k50k闲

2分

1k59k区

320k160k表

4331k180k

解：按首次适应算法,

申请作业100k,分配3号分区，剩下分区为20k,起始地址160K；

申请作业30k,分配1号分区，剩下分区为2k,起始地址50K；

申请作业7k,分配2号分区，剩下分区为:1k,起始地址59K；

01。

A外零头

1

2

3

在低地址部分会

积累大量外零头

"III.循环首次适应算法(Next-fitAlgorithm)

■一一.*

0要求：空闲分区以地址递增的次序链接；且做成环形。设

置一个起始查寻指针。

0分配：从上次找到的空闲分区的下一个分区开始查找，直

至找到一个能满足大小要求的空闲分区。划分。例i_

O倾向：平衡利用内存。

优点：空闲分区组织简单；查找简单。

❖缺点：无大的空闲分区，难满足大作业的要求。

例如：

系统中的空闲分区表如下，现有三个作业分配申请内存空间

100K、30K及7K。给出按循环首次适应算法的内存分配情况及分

配后空闲分区表。

区号大小起址

起始查询指针

125k27k

28k52k

320k160k

4301k210k

解：按循环首次适应算法，

申请作业100k,分配3号分区,剩下分区为20k,起始地址160K；

申请作业30k,分配4号分区,剩下分区为301k,起始地址210K；

申请作业7k,分配1号分区,剩下分区为25k,起始地址27K；

Ill,最佳适应算法(Best-fitAlgorithm)

。要求：空闲分区按大小从小到大进行链接。

9分配：从链表头进行顺序查找，直至第一个大小能满足的

分区。则为能满足且最接近需要大小的分区。划分。

例如：

优点：避免“大材小用”。

缺点：外零头严重；分区组织、回收复杂。

©©0

例如：

系统中的空闲分区表如下，现有三个作业分配申请内存空间

100K、30K及7K。给出按最佳适应算法的内存分配情况及分配后空

闲分区表。

区号大小起址

11k59k

22k50k

320k160k

4331k180k

解：按最佳适应算法,

申请作业100k,分配3号分区,剩下分区为20k,起始地址160K；

申请作业30k,分配3号分区，剩下分区为2k,起始地址50K；

申请作业7k,分配2号分区，剩下分区为:Lk,起始地址59K；

IV.最坏适应算法(Worst-fitAlgorithm)

o要求：空闲分区按从大到小链接。

o分配：从头顺序查找，找到大小能满足的。则为能满足且

划分后剩余空间最大的分区。划分。例如：

优点：外零头较少。

缺点：难满足大作业的要求；分区组织、空闲分区回

收复杂。

囱

例如:

系统中的空闲分区表如下，现有三个作业分配申请内存空间

100K、30K及7K。给出按最坏适应算法的内存分配情况及分配后

空闲分区表。

区号大小起址

空

1194k317k闲

2120k60k分

区

332k20k表

48k52k

解：按最坏适应算法，

申请作业100k,分配1号分区,剩下分区为231k,起始地址280K；

申请作业30k,分配1号分区，剩下分区为201k,起始地址310K；

申请作业7k,分配1号分区，剩下分区为194k,起始地址317K；

FF\BF\WF三种算法比较

分区分配算法的性能看其时间、空间复杂性而定。就算

法本身来说，它们的复杂性由排序（地址大小、空闲区大小）

和查找（查找所需自由区）两项决定。

・搜索速度：FF最佳。BF或WF要求按空间大小进行排序，

因此速度较慢。

0回收过程：FF最佳，因为FF算法回收时不用改变空闲区位

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

9空闲区：BF最佳。但某些情况下会降低内存利用率。

0碎片：WF基于不留碎片空间为出发点。

FF\BF\WF三种算法比较（续）

上述三种分配算法各有利弊，好坏不能一概而论，应针

对具体作业序列来分析。

・对某作业序列来说，若某算法能将该作业中所有作业安置

完毕，则称该算法对这一作业序列是合适的。

•对某一算法而言，若不能立即满足作业序列的某一要求，

则该算法对该作业序列是不合适的。

FF算法以其简单、快速特性，在实际的操作系统中用得较

多；其次是最佳适应算法。

4)动态分区的分配和回收

动态分区管理方式中，主要操作是内存分配和回收。

I.分配内存MemoryAllocation)

□①按某种算法根据请求的大小，在表或链中进行查找合适

空闲区；

□②找不到则结束；找到则划分。为减少外零头，可设一下

限。若划分后零头小于该下限，则不划分直接分配。

口③修改相应的数据结构。

u.size:请求的分区大小；

m.size:表中每个空闲分区的大小；

size:事先规定的不再切割的剩余分区的大小。

存在内零头

将分区分配给用户，从空闲分区表（链）中移出

II.回收内存(ReturnMemory)

当内存运行完毕释放内存时，系统根据回收区的首址

在相应的数据结构中查找插入点。

此时可能出现四种情况之一：

①回收区上邻接一个空闲分区：合并、改大小。

②回收区下邻接一个空闲分区相邻：合并、改始址、大小。

③回收区上下邻接区相邻：合并、共用上空闲分区首址、改

大小、取消下空闲分区。

④回收区不邻接空闲分区：单独建一表项。

回收内存举例

Pl运行结束

P1所占分区的上下都不空闲，在空闲

分区链中添加一项

P3运行结束

P3所占分区下边的分区F1空闲，应进行合并。

在空闲分区链中找到F1节点，修改其起始地

址和长度

P2运行结束

P2所占分区上边的分区Fl空闲，应进行

合并。在空闲链表中找到F1节点，修改

其长度

P1运行结束

P1所占分区上下边的分区F1和F2都空闲，

应进行合并。在空闲链表中找到F1节点，修

改其长度为Fl、F2和P2所占分区的长度和。

删除F2节点

动态分区分配举例:

某计算机有2560K内存，采用可变分区模式管理内

存，操作系统占用低地址的400K空间，剩余2160K的空

间为用户区。分区分配采用首次适应算法。

最初整个用户区为空闲，即只有一个分区。随着用

户程序的创建和撤销，分区的个数和大小位置开始变化。

分配回收过程如下所示：

内存的初始状态P1来，600K

0

P2来，1000K

400K

P3来，300K

900K

1000K

P2结束］

P4来，700K

1700K

Pl结束;

2000K

P5来，500K

2300K

P4结束

2559K

3、可重定位分区分配

Relocatablepartitionallocation

\7

1）引入

动态分区分配中，经多次划分后，常会出现大量的太小

而无法利用的区域（外零头）。为了充分利用内存空间，可

采用紧凑（compaction）技术。

紧凑：将内存中的作业进行移动，使它们相邻接，将分

散的小分区拼接成一个大分区，从而利于作业的装入。

（以时间换空间）

紧凑后的作业在内存中位置发生了变化，则应对其中程序、

数据等的地址做相应的修改，即重定位。

(a)

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

二章褊辘百

2）动态重定位的实现

TheimplementationofdynamicRelocation

。为支持作业在内存中的移动，应采用动态运行时装入方式。

。因此，允许作业在运行过程中在内存中移动的技术，必须获

得硬件地址变换机构的支持。

■在系统中设置一个重定位寄存器。用于存放作业在内存

中的起始地址。

■运行时，相对地址执行：

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

得到它在内存中的实际地址。如图所示.

紧凑时，只需修改重定位寄存器值，使之存放新起始地址。

G二

匚二

不“

3）可重定位分区分配算法

DynamicRelocationPartitionAllocationAlgorithm

动

态

分

区

分

配

算

法

流

程

修改有关的修改有关的"返回分区号

数据结构数据结构\及首址

可重定位分区分配小结

。优点：

9消除内存碎片，提高内存利用率。

。缺点：

提高硬件成本。

紧凑时花费CPU时间，开销大。

紧凑的时机

☆进程结束，释放分区时，如不与空闲区相邻，则紧凑,

保持空闲区连续，花费多。

☆分配进程分区时，若不满足，则紧凑。空闲区管理复

杂。

r

4.伙伴系统(BuddySystem)

固定分区和动态分区方式都有不足之处。伙伴系统方式是

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

。伙伴系统规定：

❖1）内存分区大小均为2的k次塞，k为整数（I0陋m）,其中：21

表示分配的最小分区的大小，2m表示最大分区的大小，通常为系

统开始运行时可分配内存的大小。

❖2）该方法通过不断划分大的空闲区来获得小的空闲区，直到

获得所需内存块。空闲块的分配和合并均使用2的幕次方算法。

。3）当一个空闲块被对分后，其中一部分称为另一部分的伙伴。

日。伙伴系统空闲块的组织

空闲分区根据分区的大小进行分类，对于每•类具仃相同

大小的所有空闲分区，单独设立一个空闲分区双向链表。这样,

不同大小的空闲分区形成了k（O0联m）个空闲分区链表。

”与=4

?□G

亍三—三

O伙伴系统内存的分配和回收

1Mblock

Request100K

Request240K

Request64KA=128KB=256K512K

FrF

Request256KA=128K64KB=256KD=256K256K

RelesetBA=128K64K256KD=256K256K

RelesetA64K256KD=256K256K

F

Request75KE=128K64K256KD=256K256K

1M

。伙伴系统内存的分配和回收（续）

伙伴系统小结

。Easytopartition

。Easytocombine

0Internalfragmentationexisting,No

externalfragmentation

。ThebuddysystemisusedforLinuxkernel

memoryallocation.

在内存分区分配中考虑两个问题:

割1、若进程在运行过程中长度发生变化。

则如果邻接内存区域为空白，可再分配。若邻接为

一进程，则需要移动、等待、交换或撤销。

割2、作业调度时内存空间是否满足。

因此，作业调度算法应同分区内存管理相结合。即

在考虑调度顺利时，还要考虑到内存空间是否能满足。

ra例如：

―主存总容量为257K,OS占40K。系统采用FCFS作业调度,

进程调度采用时间片(5§)轮转。

作业到来次序所需存储量运行时间

160KB10s

2100KB5s

330KB20s

470KB8s

550KB15s

03940256

三、对换(Swapping)

1.

对换是提高内存的利用率的有效措施。

■•原理：暂停执行内存中的进程，修要换出的进程的地

址空间保存到外存的对换区中（换出），而将外存中由阻塞变

为就绪的进程的地址空间读入内存，并将该进程送到就绪队列

（换入）。

•实现：可在系统中设一对换进程，以执行换进内存、

换出至外存操作。对换是系统行为

•分类：

'O1)“整体对换”或“进程对换”。对换以整个进程为单位,

用于分时系统，以解决内存紧张，提高内存利用率。

02)“页面对换”或“分段对换”。对换以“页”或“段”

为单位进行“部分对换”。支持虚存系统。

•系统提供的功能：为实现对换，系统需要三方面的功能：

。对换空间的管理(ManagementofSwappingSpace)

O进程的换入(SwapinofProcess)

O进程的换出(SwapoutofProcess)

2.对换空间的管理

(ManagementofSwappingSpace)

\____________________________________________________________________________

引入对换后，外存被分为两部分：文件区和对换区。

文件区：用于存放文件，其管理目标为提高存储空间的利

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

*口即一个文件可根据当前外存的使用情况，被分成多块,]

较夕分别存到不邻接的多个内存存储区域中。熨

度。因此采用连续分配方式。

涛脚换卤蹄摊蝇踊帮随动慈绣位画僧爵岷8

3.进程的换入与换出

(SwapinandSwapoutofProcess)

\7

进程的换入和换出由对换进程完成。

♦:*(1)进程的换出

A实质：把活动阻塞、就绪状态的进程转挂起状态。

A步骤：换出过程分以下两步：

stepl.选择被换出的进程

《处于阻塞状态的、优先级最低的进程。

力无阻塞：选择优先级低的就绪进程。

力考虑优先级低产生“换进、再换出”，兼顾内存驻留时

间。

力非共享的程序和数据段。若为共享，只能引用数为零后

才能被换出。

step2.换出过程

9①申请对换空间，成功则执行②，否则，重新选择;

9②将程序和数据写入对换区，检查写入的正确性；

小③无误，则调用释放内存过程，释放原内存；

9④修改PCB、内存分配表等；

小⑤若内存仍不足或仍有可换出进程，则回到①

(2)进程的换入

＞实质：把挂起状态■＞活动就绪或阻塞。

＞步骤：换入过程分以下两步：

stepl.选择换入进程

9有足够的内存空间；

9“就绪挂起”优先于“阻塞挂起”；

9同一队列中，优先级高、挂起时间长的优先换入。

step2.换入过程

9①从PCB集合中查找“就绪且换出”的进程，有多个，

则选择换出时间最长的。

《②根据进程大小申请内存，成功则读入，否则要先执行换

出，再换入。

小③若还有可换入进程，则转向①。直至无“就绪且换出”

进程或无法获得足够内存空间为止。

离散内存分配方式

<y

把用户的程序空间划分成若干部分（化整为零），它们可

以离散分配到内存中非连续的存储区域中，充分利用内存。即

离散分配方式。

根据程序划分时的基本单位不同，可分为三种：

O基本分页存储管理方式

O基本分段存储管理方式

O段页式存储管理方式

§44基本分页存储管理方式

lasicPagedMemoryManagement

ca一、基本分页存储管理原理

ca二、基本概念

三、内存分配和回收

caI、地址变换

ca五、两级和多级页表朱

■一、基本分页存储管理原理

□将程序的逻辑地址空间划分为固定大小的页(页面)

(pageorpageframe)；

□将物理内存划分为与页面大小相等的物理块(block)；

□程序加载时，按页分配其所需的块，连续页面所分得物

理块不必连续。

□需要CPU的硬件支持。

基本分页存储管理示意图

0

页1

表2

页号块号

3

04

4

16

225

386

4号块

7

45（块长2K）

518

6109

6页内碎片

11

口。"3内存需二章魏

二、基本概念(BasicConcept)

/X

1.页面和物理块(pageandblock)

\7

把用户程序的逻辑地址空间划分成若干大小相等的

“页”，各页从。开始依次编页号0,L2,....

页内地址相对于0编址。因此，分页系统中，每个逻辑地

址都可用二元组(页号，页内地址)表示。

把内存空间划分成若干和“页”大小相同的块，称为

物理块(Block)或页框(frame)。同样为它们编号0,1……。

物理地址同样用二元组(块号，块内地址)表示。

2.页面大小(PageSize)

。分页系统中页面大小由机器地址结构决定，因此，机器的

页面大小固定。用户程序页面划分由系统自动完成，一般

为2的整数次赛。例如，旧MAS/400的页面大小为512B。

。小页面

♦:♦优点：减少碎片，提高内存利用率。

♦:♦缺点：页表过长，占用较多内存空间。且以页为单位进

行换进、换出时效率低。

。大页面

♦:♦优点：页表小，换进换出时效率高。

♦:♦缺点：页内碎片相应较大。

O页面的大小通常在512B~4KB之间。

3.逻辑地址形式(LogicAddress)

\7

。在分页存储管理方式中，程序经过页面划分后，任一个

逻辑地址都可转变（页号，页内位移量）。

。如：一个32位的逻辑地址，可转化为如下方式:

编号0〜1048575相对地址0T095

■。逻辑地址转换过程：

逻辑地址A,在分页存储管理方式中，需要被转换成（页

号，页内偏移）二元组地址形式。

若页面大小为L,则转换过程为：

页号P=INT[A/L]；页内位移量W=AMODL

变换通常由系统中的某些硬件完成（MMU,内存管理单元）

例如：有逻辑地址为：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■>

设有一页式存储管理系统，向用户提供的逻辑地址空

间最大为16页，每页2048字节，内存总共有8个存储块，

试问逻辑地址至少应为多少位？内存空间有多大？

山

三、内存的分配与回收

MemoryAllocationandReturn

1.数据结构(DataStructer)

1)进程页表/页表(PageTable)

□作用：描述进程页面存放在内存中所对应的物理块。

口内容：页表中主要包括页号、物理块号。还可有存取控

制字段，实现对存储块中内容的保护。如二

口注意：每个进程一个页表。全部页表集中存放在内存的

系统专用区中，只有系统有权访问页表，保证安全。例」

近2）虚空间表（作业表）：记录进程空间的情况。一个进程

一个表项。记录进程页表在内存的存放情况。全系统仅1张。

3）空闲块表：记录内存当前空闲块，全系统1张。

O31

O空

块

1管

理

——

…

…

位

示

7图

章

需

二

一

问?

1、进程页表放在哪儿？内存I

2、进程页表的首地址和长度放在哪儿？

进程PCB

需口章筋

2.内存分配过程(MemoryAllocation)

J

3.内存回收过程(MemoryReturn)

y

♦：♦根据进程页表的内容，把空闲块表中对应的物理页改为

空闲；

*撤销该进程的进程页表。

四、地址变换

AddressTransformMechanism

•一—_Q

物

用

理

户MOVA,8279

内

程

存

序

空

间

页号到物理块号的转换，借助页表。

1.基本地址变换机构

(BasicAddressTransformMechanism)

越界中断

页表寄存器PTR逻辑地址

分

页

页表始址页表长度>=287系

统

的

地

页号块号址

变

01换