第四章 存 储 器 管 理
第四章 存储器管理
4.1 程序的装入和链接
4.2 连续分配方式
4.3 基本分页存储管理方式
4.4 基本分段存储管理方式
4.5 虚拟存储器的基本概念
4.6 请求分页存储管理方式
4.7 页面置换算法
4.8 请求分段存储管理方式
第四章 存 储 器 管 理
存储器管理是指对存储器资源的管理。存储
器管理的主要对象是 内存 。
存储管理的内容主要包括：
? 存储器资源的组织 （ 如内存的组织方式 ） ；
? 地址变换 （ 逻辑地址与物理地址的对应关系
维护 ） ；
? 虚拟存储的调度算法。
第四章 存 储 器 管 理
4.1 程序的装入和链接
对用户程序的处理步骤
编译
目标模块
库
…
..
链接
程序
装入模块 装入程序
内存
源程序
第四章 存 储 器 管 理
4.1.1 程序的装入
将一个模块装入内存时，可采用三种方式：
? 绝对装入方式
? 可重定位方式
? 动态运行时装入方式
第四章 存 储 器 管 理
1,绝对装入方式
如果事先知道程序将驻留在
内存的什么位置，那么编译
或汇编程序将产生绝对地址
的目标代码，装入程序直接
将目标代码装入相应的内存
空间。
Load 2224
365
2224
1024
? 优点,装入过程简单。
? 缺点,过于依赖于硬件结构，只适用于单道程
序环境，不适于多道程序系统。
第四章 存 储 器 管 理
2,可重定位方式
把用户程序在装入内存时对目标程序中指令和数
据的修改过程称为 重定位 。
当用户程序被装入内存时，一次性实现逻辑地址
到物理地址的转换，以后不再转换,称为 静态重定
位 。
? 优点,无需硬件支持，地址变换由重定位装配程
序完成。
? 缺点,地址变换在装入时一次性完成，装入内存
后不能移动，不利于内存空间的有效利用，难于
实现程序的共享。
第四章 存 储 器 管 理
LOAD 1,2500
365
LOAD 1,12500
365
10000
11000
12500
150005000
2500
1000
0
作业地址空间
内存空间
逻辑地址 物理地址
第四章 存 储 器 管 理
3,动态运行时装入方式
装入模块装入内存后，不立即把相对地址转换
成绝对地址，而是推迟到程序真正要执行时才进
行。
优点,程序占用的内存空间可动态变化，即允许
程序在内存中移动；也不必分配连续的内存空
间，便于程序的共享。
缺点,需要硬件 重定位寄存器 支持,OS实现较复
杂。
第四章 存 储 器 管 理
4.1.2 程序的链接
链接是指多个目标模块在执行时的地址空间分
配和相互引用。
根据链接时间的不同，把链接分为以下三种类
型：
? 静态链接方式
? 装入时动态链接
? 运行时动态链接
第四章 存 储 器 管 理
1,静态链接方式
将所有目标模块和所需的库函数在装入前事先
链接成一个完整的装入模块（可执行文件），以
后不再拆开的链接方式。
在将几个目标模块链接装配成一个装入模块时，
需要解决以下两个问题：
? 对相对地址进行修改；
? 变换外部调用符号。
第四章 存 储 器 管 理
例：
模块 A
CALL B；
Return；
0
L－ 1
模块 B
CALL C；
Return；
0
M－ 1
模块 C
Return；
0
N－ 1
0
模块 A
JSR“L”
Return；L－ 1
模块 B
JSR“L＋ M”
Return；
L
L＋ M－ 1
L＋ M
L＋ M＋ N－ 1
模块 C
Return；
(a) 目标模块 (b) 装入模块
第四章 存 储 器 管 理
2,装入时动态链接
一个程序的多个目标模块在装入内存时，边装
入边链接。
优点,
? 便于修改和更新；
? 便于实现对目标模块的共享。
第四章 存 储 器 管 理
3,运行时动态链接
一个程序的多个目标模块在程序执行时，根据
需要再动态装入和链接。
优点,
本次执行过程中不用的模块可以不装入和链接。
如典型的错误处理模块。
第四章 存 储 器 管 理
连续分配是指为一个用户程序分配一个连续的
内存空间。具体分为四种分配方式：
? 单一连续分配
? 固定分区分配
? 动态分区分配
? 可重定位分区分配
4.2 连续分配方式
第四章 存 储 器 管 理
4.2.1 单一连续分配方式
? 最简单的一种存储管理方式，适用于单用户、
单任务的 OS。
? 把内存分为两个区域：系统区，用户区。应用
程序装入到用户区，可使用用户区全部空间。
? 优点,易于管理。
? 缺点,对要求内存空间少的程序，造成内存浪
费；程序全部装入，很少使用的程序部分也占
用内存。
第四章 存 储 器 管 理
4.2.2 固定分区分配方式
? 最简单的可运行多道程序的存储管理方式。
? 将内存的用户空间划分为若干个固定大小的连
续分区，在每个分区中只装入一道作业。
1,划分分区的方法：
? 分区大小相等：只适合于多个相同程序的并发
执行（处理多个类型相同的对象）。
? 分区大小不等：多个小分区、适量的中等分区、
少量的大分区。根据程序的大小，分配当前空
闲的、适当大小的分区。
第四章 存 储 器 管 理
固定分区 (大小相同 ) 固定分区 (大小不同 )
例：
8 M
8 M
8 M
8 M
8 M
Operating System 8 M
12 M
8 M
8 M
6 M
4 M
2 M
Operating System
第四章 存 储 器 管 理
? 分区使用表,用于记录分区的大小和使用情况，
按分区大小排队。包括每个分区的起始地址、
大小和状态（是否分配）。
? 用户程序需要装入时，内存分配程序检索该表，
找出一个能满足要求尚未分配的分区，分配给
该程序，并将其表项中的状态置为“已分配”。
? 若未找到大小足够的分区，则拒绝为用户程序
分配内存。
2,内存分配
第四章 存 储 器 管 理
例,某系统的内存容量为 256K，操作系统占用低地址
的 20K，其余空间划分成 4个固定大小的分区。
OS
20K
28K
60K
124K
256K-1
作业 A（ 6K）
作业 B（ 20K）
作业 C（ 50K）
1
2
3
4
0K
主存
作业 A
6K
作业 B
20K
作业 C
50K
作业队列
第四章 存 储 器 管 理
分区说明表
分区号 大小 (KB) 始址 (KB) 状态
1 8 20 已分配
2 32 28 已分配
3 64 60 已分配
4 132 124 未分配
第四章 存 储 器 管 理
? 优点,易于实现，开销小。
? 缺点：
?内碎片造成浪费；
?分区总数固定，限制了并发执行的程序数目。
第四章 存 储 器 管 理
4.2.3 动态分区分配方式
? 动态创建分区：在装入程序时按其初始要求分
配，或在其执行过程中通过系统调用进行分配
或改变分区大小。
? 优点,没有内碎片。
? 缺点,有外碎片；如果大小不是任意的，也可
能出现内碎片。
第四章 存 储 器 管 理
进程 A（ 8K） 进程 D（ 124K）进程 B（ 16K） 进程 C（ 64K） …
OS
进程 A
进程 B
进程 C
进程 D
OS
进程 A
进程 B
进程 C
OS
进程 A
进程 B
OS
进程 A
第四章 存 储 器 管 理
1,分区分配中的数据结构
? 空闲分区表,记录每个空闲分区的情况, 包括
分区序号, 分区始址, 分区大小等 。
? 空闲分区链：
?在每个空闲分区的起始部分开辟出一个单元,
存放一个链表指针和该分区的大小, 在尾部则
设置一后向指针 。
?系统中用一个固定单元作为空闲分区链表的链
表头指针, 指向第一块空闲分区首地址, 最后
一块空闲分区的链表指针存放链尾标志 。
?当分区被分配出去以后, 状态位由, 0”改为
,1”,此时前后指针无意义 。
第四章 存 储 器 管 理例,采用 双向链的空闲分区链结构
第四章 存 储 器 管 理
2,分区分配算法
? 首次适应算法
? 循环首次适应算法
? 最佳适应算法
第四章 存 储 器 管 理
首次适应法 FF：
? 要求空闲区按 首址递增 的次序组织空闲区表（队
列）。
? 当进程申请大小为 SIZE的内存时, 系统从空闲区
表的第一个表目开始查询, 直到首次找到等于或
大于 SIZE的空闲区 。 从该区中划出大小为 SIZE的
分区分配给进程, 余下的部分仍作为一个空闲区
留在空闲区表中, 但要修改其首址和大小 。
第四章 存 储 器 管 理
? 优点：
该算法是尽可能地利用低地址空间，从而保
证高地址空间有较大的空闲区。
? 缺点：
低地址部分的不断划分，会留下许多难以利
用的、很小的空闲分区，而每次查找都是从低
地址部分开始，会增加查找可利用分区时的开
销。
第四章 存 储 器 管 理
循环首次适应算法：
? 把存储空间中空白区构成一个循环链，每次为
存储请求查找合适的分区时，总是从上次查找
结束的地方开始，只要找到一个足够大的空白
区，就将它划分后分配出去。
? 优点,能使内存中的空闲分区分布均匀，从而
减少了查找空闲分区时的开销。
? 缺点,使内存中缺乏大的分区。
第四章 存 储 器 管 理
最佳适应算法：
? 要求按空闲区大小 从小到大 的次序组成空闲区
表（队列）。
? 当进程申请一个存储区时，系统从表头开始查
找，当找到第一个满足要求的空闲区时，停止
查找，并且这个空闲区是最佳的空闲区。
? 所谓最佳即选中的空闲区是满足要求的最小空
闲区。
第四章 存 储 器 管 理
? 优点：
?在系统中若存在一个与申请分区大小相等的空
闲区, 必定会被选中, 而首次适应法则不一定 。
?若系统中不存在与申请分区大小相等的空闲区,
则选中的空闲区是满足要求的最小空闲区, 而
不致于毁掉较大的空闲区 。
? 缺点：
空闲区的大小一般与申请分区大小不相等，
因此将其一分为二，留下来的空闲区一般情况
下是很小的，以致无法使用。随着时间的推移，
系统中的小空闲区会越来越多，从而造成存储
区的大量浪费。
第四章 存 储 器 管 理
几点说明：
? 上述三种分配算法各有利弊, 到底哪种最好不
能一概而论, 而应针对具体作业序列来分析 。
? 对于某一作业序列来说, 某种算法能将该作业
序列中所有作业安置完毕, 那么我们说该算法
对这一作业序列是 合适的 。
? 对于某一算法而言，如它不能立即满足某一要
求，而其它算法却可以满足此要求，则这一算
法对该作业序列是 不合适的 。
第四章 存 储 器 管 理
例：
有一作业序列：作业
A要求 18K；作业 B要求
25K，作业 C要求 30K。
分析系统中空闲区按
三种算法组成的空闲区
队列。
（图中灰色部分为空闲
区。）
第四章 存 储 器 管 理
① 首次适应算法的空闲区队列：
② 循环首次适应算法的空闲区队列：
③ 最佳适应算法的空闲区队列：
30K 20K 5K 46K ^
20K 100K 160K 210K链首指针
30K 20K 5K 46K
20K 100K 160K 210K链首指针
2K 20K 30K 46K ^
160K 100K 20K 210K链首指针
第四章 存 储 器 管 理
3,分区的分配
? 在采用分区存储管理的系统中，系统初启后。
除操作系统占用一个分区外，其余存储区为一
个大的空闲区。
? 分区的分配是指 利用某种分配算法，找到所需
的分区，按照大小划分出一块内存空间分配出
去，剩余的部分留在空闲分区链中。
第四章 存 储 器 管 理从头开始查表
检索完否？
m.size＞ u.size?
m.size－ u.size≤size?
从该分区中划出
u.size 大小的分区
将该分区分配给请求者修
改有关数据结构
返回
返回
继续检索下一个表项
将该分区从链中移出
Y
N
N
Y
Y
N
分
配
流
程
图
：
第四章 存 储 器 管 理
说明：
将一个空闲区分成二部分有两种办法：
a) 从空闲区的上部开始划出 U.SIZE大小的空闲
区给用户；
b) 从空闲区的底部开始向上划出 U.SIZE大小的
空闲区给用户 。
一般常用第二种办法, 因为这样划分时, 余下
的部分在空闲区表中的首地址不变, 只需要修
改一下大小就行了 。
第四章 存 储 器 管 理
4.分区的回收
? 当某个进程释放某存储区时, 系统首先检查
释放区是否与系统中的空闲区相邻, 若相邻
则把释放区合并到相邻的空闲区中去, 否则
把释放区作为一个空闲区插入到空闲区表的
适当位置 。
? 分区回收时会有四种情况：
第四章 存 储 器 管 理
第四章 存 储 器 管 理
4.2.4 可重定位分区分配
? 不能被利用的小分区称为,零头,或,碎片,。
? 通过移动，把多个分散的小分区拼接成大分区
的方法被称为,拼接,或,紧凑,。
? 每次“紧凑”后必须对移动了的程序或数据进
行重新定位。
1,动态重定位的引入
第四章 存 储 器 管 理
操作系统
作业 1
作业 2
作业 3
空闲区
作业 4
操作系统
作业 1
空闲区
作业 2
空闲区
作业 3
空闲区
操作系统
作业 1
作业 2
作业 3
空闲区
紧凑前 紧凑后
第四章 存 储 器 管 理
2,动态重定位的实现
? 需要硬件地址变换机构的支持，即重定位寄存
器。
? 内存地址＝相对地址＋重定位寄存器中的地址。
? 地址变换过程是在程序执行期间，随着对每条
指令或数据的访问而自动进行的。
第四章 存 储 器 管 理
LOAD1,2500
365
0
100
2500
5000
2500
相对地址
10000
重定位寄存器
＋
LOAD1,2500
365
10000
10100
12500
15000
作业 J
处理机一侧 存储器一侧 主存
动态重定位示意图
第四章 存 储 器 管 理
3,动态重定位分区分配算法
流程图,请求分配u.size分区
检索空闲分区链 (表 )
找到大于 u.size
的可用区?
按动态分区方式
进行分配
修改有关的
数据结构
返回分区号
及首址
空闲分区
总和 ≥ u.size?
进行紧凑形
成连续空闲区
修改有关的
数据结构
否
是
无法分配
返回
否
是
第四章 存 储 器 管 理
4.2.5 对换
1,对换的引入
? 对换 是指把内存中暂时不能运行的进程或者暂
时不用的程序和数据，调出到外存上，以便腾
出足够的内存空间，再把已具备运行条件的进
程或者进程所需的程序和数据，调入内存。
? 通过对换，可利用外存来逻辑地扩充主存。
? 如果对换以整个进程为单位，便称,整体对换,
或,进程对换,。如果以“页”或“段”为单
位，则分别称,页面对换,或,分段对换,，
并通称,部分对换,。
第四章 存 储 器 管 理
2,对换空间的管理
在具有对换功能的 OS中，通常把外存分为 文件
区 和 对换区 。
? 文件区存放文件，常采用离散方式，以提高文
件存储空间的利用率；
? 对换区存放从内存换出的进程，常利用连续分
配方式，以提高对换速度。
第四章 存 储 器 管 理
? 进程的换出：选择处于阻塞状态且优先级最
低的进程作为换出进程，换出后收回内存空
间，修改进程的 PCB相关信息。
? 进程的换入：找出“就绪”状态并已经换出
的进程，将其中换出时间最久的进程作为换
入进程，将其换入。直到已无可换入的进程
和无可换出的进程。
3,进程的换出和换入
第四章 存 储 器 管 理
4.3 基本分页存储管理方式
离散分配方式,为了减少因连续分配所产生的碎片，
提高内存的利用率产生了离散分配方式，它可将一
个用户程序离散地分配到内存中的多个不相连接的
区域中。
其方式有：
a.分页存储管理方式－离散的基本单位是, 页, ；
b.分段存储管理方式－离散的基本单位是, 段, ；
c.段页式存储管理方式。
第四章 存 储 器 管 理
基本分页存储管理方式：
在分页存储管理方式中，如果不具备页面对
换功能，就是基本分页存储管理方式，即不支
持虚拟存储器的功能。
第四章 存 储 器 管 理
1,页面
页（页面） －把每个作业 (进程 )逻辑地址空间
划分成若干大小相等的片。
物理块 －把内存空间划分成与页相同的片。
2,分页式存储器的逻辑地址结构
分页地址中的地址结构确定了主存储器的分
页大小,也决定了页面大小。
页 号 P 页内地址 (偏移量 )
31 12 11 0
总页数,220＝ 1M(页 )；每页大小为,212＝ 4KB
第四章 存 储 器 管 理
3,页表
? 系统为每个进程建立一张页面映象表，即 页表 。
? 页表的长度和首地址存放在该进程的进程控制块
（ PCB）中。
? 页表的作用是实现从页号到物理块号的 地址映射。
? 页表由 页号 和 块号 组成，指出逻辑地址中页号与
主存中物理块号的对应关系。
? 页号 ---作业地址空间的页序号。
? 块号 ---内存空间的页面序号。
逻辑上相邻的页，物理上不一定相邻。
页号 块号
0 2
1 3
2 6
第四章 存 储 器 管 理
页表的作用
用户程序
0 页
1 页
2 页
3 页
4 页
5 页
…
n 页
页表
页号 块号
0 2
1 3
2 6
3 8
4 9
5
… …
内存空间
0
1
2
3
4
5
6
7
8
9
10
第四章 存 储 器 管 理
注意,页大小的选择
? 太大：浪费；
? 太小：页表过长；
? 页的大小是 2K, 通常为 512B-5KB。
第四章 存 储 器 管 理
例,如图，作业 1有 2页分别装入内存的第 5,6块；
作业 2有 3页装入内存的第 2,4,7块；作业 3有 1 页
装入内存的第 8块。
第四章 存 储 器 管 理
4.3.2 地址变换机构
? 基本任务：逻辑地址 ?物理地址。
? 由于页面和物理块大小相同，他们的地址是一
一对应的，无需变换。所以地址变换实际上只
是将逻辑地址中的页号，转换为内存中的物理
块号，这一任务是由页表来完成的。
即,页号 ?页表 ?存储块号 b，与 页内地址 w合
成，形成 物理地址 。
第四章 存 储 器 管 理1,基本的地址变换机构
页表长度（ 5）页表始址 页内地址 w页号（ 3）
wbb
0
1
2
3
4
页表寄存器 逻辑地址
页表
物理地址
块号页号
＋
>
越界中断
第四章 存 储 器 管 理
例,在采用页式存储管理的系
统中，某作业 J的逻辑地址
空间为 4页（每页 2048字
节），且已知该作业的页面
映像表（即页表）如右图，
试借助地址变换图（要求画
出地址变换图）求出有效逻
辑地址 4865所对应的物理地
址。
页号 块号
0 2
1 4
2 6
3 8
第四章 存 储 器 管 理
页表长度页表始址 页内地址页号
7696
页表寄存器 逻辑地址
页表
物理地址
＋
页号 块号
0 2
1 4
2 6
3 8
4865=2*2048+769
7692
物理地址,6*2048+769=13057
第四章 存 储 器 管 理
2.具有快表的地址变换机构
? 在前述的页地址变换过程中有一个严重的问题,
那就是每一次对内存的访问都要访问页表, 页
表是放在内存中的, 也就是说每一次访问内存
的指令至少要访问两次内存, 运行速度要下降
一半 。
? 若不解决这一问题是不能令人忍受的 。
第四章 存 储 器 管 理
? 为了提高存取速度, 通常设置一个具有并行查
询能力的特殊 高速缓冲寄存器, 存放当前作业
的 最常用 的页号及对应块号 。 我们把存放在高
速缓冲寄存器中的页表叫 快表, 把存放在内存
中的页表称为 慢表 。
? 快表又叫 联想寄存器 。
? 需要说明的是：快表的地址转换是非常快的,
因为它是将页号与快表中的各行同时比较, 从
而大大减少了地址变换时间, 基本上克服了两
次访问主存的缺点 。
第四章 存 储 器 管 理
页表长度（ 5）页表始址 页内地址 w页号（ 3）
wbb
0
1
2
3
4
页表寄存器 逻辑地址寄存器
页表
块号页号
＋
>
b
输
入
寄
存
器
块号页号
快表
具有快表的地址变换机构
越界中断
第四章 存 储 器 管 理
4.3.3 两级页表和多级页表
? 当页表项很多时, 仅采用一级页表需要大片连
续空间, 可将页表也分页, 并对页表所占的空
间进行索引形成外层页表 。 由此构成 两级页表 。
? 更进一步可形成 多级页表 。
第四章 存 储 器 管 理
1,两级页表
外层页表有 210个页表项；
最多允许有 210个页表分页；
页面大小为,212＝ 4KB。
逻辑地址结构可描述如下：
第四章 存 储 器 管 理
1011
1078
0
1
2
1742n
第 0页页表
1
4
6…
01
2…
1023
第 1页页表
114
115
0
1…
1023外部页表
0
1
2
3
4
5
6
7
…
…
114
115
1468
第 n页页表
14680
1
2…
1023 内存空间
两级页表结构
第四章 存 储 器 管 理
具有两级页表的地址变换机构
外部页号
P1 P2
外部页内地址 页内地址
d逻辑地址
＋外部页表寄存器
外部页表
＋ db
页表
物理地址… …
两级页表地址变换需 三次 访问内存：一次访问页目
录, 一次访问页表页, 一次访问指令或数据, 访问
时间加了两倍 。 可增设快表, 提高访问速度 。
第四章 存 储 器 管 理
4.4 基本分段存储管理方式
分页存储管理方式中用户的程序地址空间是一
维线性的，这对用户特别是程序设计极不方便，
用户看待程序是以自然段为单位的，如：主程序
段、子程序段、数据段等 …… 。因此人们提出了
段式存储管理方式。
第四章 存 储 器 管 理
将程序的地址空间按内容或过程（函数）关系
划分为若干个段，每段有自己的名字。以段为单
位分配内存，然后通过地址重定位机构把段式虚
拟地址转换为实际的内存物理地址。
基本思想：
第四章 存 储 器 管 理
主要是为了满足用户和程序员的下述需要：
? 方便编程
? 分段共享
? 分段保护
? 动态链接
? 动态保护
? 动态增长
4.4.1 分段存储管理方式的引入
第四章 存 储 器 管 理
1,分段
? 每个段定义了一组逻辑信息。如：主程序段、
子程序段、数据段等。
? 用段号代替段名。
? 两维逻辑地址：段号＋段内地址。
? 地址结构,段号 S + 段内地址 W
4.4.2 分段系统的基本原理
段号 S 段内地址 d
31 16 15 0
(一个作业最多 216=64K个段, 每段最大长度 216=64KB)
第四章 存 储 器 管 理
? 每个进程一张表，用以实现地址变换,程序的每
一个段在段表中占用一个表目。
? 包括：段的长度、段的首址 (基址 )信息。
2,段表
段号
0
1
2
段首址段长度
58K20K
100K110K
260K140K
第四章 存 储 器 管 理作业空间
(MAIN)＝ 00
30K (X)＝ 1
0
20K
(D)＝ 20
15K (S)＝ 3
0
10K
30K
20K
15K
10K
40K
80K
120K
150K
段长 基址段号 (MAIN)＝ 0
30K
(X)＝ 1
20K
(D)＝ 2
15K
(S)＝ 3
10K
0
40K
80K
120K
150K
段表
内存空间
0
1
2
3
利用段表实现地址映射
第四章 存 储 器 管 理3,地址变换机构
控制寄存器
段表始址 段表长度 ＞ 2 100
＋
段号 S越界
1 K
段长
600
段号
0
1
2
3
6 K
4 K
500
200
8 K
9200
基址
位移量 W
＋
8292
8K
8292
8692
主存
物理地址
有效地址
地址变换需 两次 访问内存, 访问
时间加了一倍 。 可增设快表, 提
高访问速度 。
第四章 存 储 器 管 理
例,有一段表如
右图所示，试分
别求逻辑地址
（ 2,88）和逻
辑地址（ 4,100）
所对应的物理地
址。
段号 基地址 段长
0 219 600
1 2300 14
2 90 100
3 1327 580
4 1952 96
第四章 存 储 器 管 理
4,分段与分页技术的比较
相似,二者在内存中都不是整体连续的, 都要通过
地址映射机构将逻辑地址映射到物理内存中 。
不同：
?, 页, 是信息的, 物理, 单位, 大小固定 。, 段,
是信息的逻辑单位, 即它是一组有意义的信息,
其长度不定 。
? 页的大小是由系统固定的, 在一个系统中所有页
的大小是一样的, 只能有一种大小；段的长度因
段而异, 取决于用户所编写的程序
? 分页的作业的地址空间是单一的线性地址空间,
分段作业的地址空间是二维的 。
第四章 存 储 器 管 理
4.4.3 信息共享
分段系统的一个突出优点是易于实现段的共享,
即允许若干个进程共享一个或多个分段, 且对共享
段的保护也简单易行 。 分页系统虽然也能实现程序
和数据的共享, 但远不如分段系统方便 。
例,40个用户 共享一文本编辑程序 。 该程序有
160KB的代码和 40KB的数据区 。 其中, 160KB的
代码为 可重入代码 （ 即允许多个进程同时访问的代
码, 但不允许任何进程对它进行修改 。 ）
第四章 存 储 器 管 理
e d 1
e d 2
…
e d 4 0
d a t a 1
…
d a t a 1 0
进程 1
21
22
…
60
61
…
70
页表
e d 1
e d 2
…
e d 4 0
d a t a 1
…
d a t a 1 0
进程 2
21
22
…
60
71
…
80
…
e d 1
e d 2
…
e d 4 0
d a t a 1
…
d a t a 1 0
d a t a 1
…
d a t a 1 0
主存
0
21
22
60
61
70
71
80
页表
分页系统中共享 editor的示意图
（ 设页面大小为 4KB）
第四章 存 储 器 管 理
分段系统中共享 editor的示意图
e d i t o r
进程1
d a t a 1
进程2
e d i t o r
d a t a 2
段表
段长 基址
1 6 0 80
40 2 4 0
1 6 0 80
40 3 8 0
e d i t o r
d a t a 1
?
d a t a 2
80
2 4 0
2 8 0
3 8 0
4 2 0
第四章 存 储 器 管 理
4.4.4 段页式存储管理方式
引入：
分页和分段管理方式各有其优缺点，分页系统
能有效提高内存的利用率，而分段则能更好地满
足用户的需要，因此可以将两者结合成一种新的
存储管理方式系统称为,段页式系统,。
第四章 存 储 器 管 理
1,基本原理
? 一个程序首先被分成若干程序段，每一段赋予
不同的分段标识符，然后，对每一分段又分成
若干个固定大小的页面。
? 地址结构：分三部分
（如图所示）
第四章 存 储 器 管 理
作业地址空间和地址结构
0
4K
8K
12K
15K
16K
子程序段0
4K
8K
数据段0
4K
8K
10K
12K
(a)
段号 (S) 段内页号 (P) 页内地址 (W)
(b)
主程序段
第四章 存 储 器 管 理
2,地址映射
? 段表：记录了每一段的页表始址和页表长度。
? 页表：记录了逻辑页号与内存块号的对应关系
（每一段有一个，一个程序可能有多个页表）。
? 内存分配管理：同页式管理。
? 如图所示：
第四章 存 储 器 管 理
利用段表和页表实现地址映射
段号 状态 页表大小 页表始址
0 1
1 1
2 1
3 0
4 1
页号 状态 存储块 #
0 1
1 1
2 1
3 0
4 1
操作系统
主存
页表
段表
段表大小 段表始址
段表寄存器
第四章 存 储 器 管 理3,地址变换过程
段表寄存器
段表始址 段表长度 ＞ 段号 S 页号 P
＋
段超长
段表
0
1
2
3 ＋
页内地址
页表
0
1
2
3 b 块号 b 块内地址
页表始址页表长度
地址变换需 三次 访问内存：一次访问段表, 一次访
问页表, 一次访问指令或数据, 访问时间加了两倍 。
可增设快表, 提高访问速度 。
第四章 存 储 器 管 理
4.5 虚拟存储器的基本概念
基本思想：
通过软硬件结合的方法，利用大容量的外存空
间来逻辑扩充内存，使得产生一种不受实际内存
容量大小限制的逻辑的虚拟存储器。
第四章 存 储 器 管 理
1.常规存储器管理方式的特征
? 一次性
? 驻留性
4.5.1
第四章 存 储 器 管 理
2,局部性原理
指程序在执行过程中的一个较短时期，所执行的
指令地址和指令的操作数地址，分别局限于一定区
域。具体表现在以下几方面：
? 程序在执行时，大部分是顺序执行的指令，少部
分是转移和过程调用指令。
? 过程调用的嵌套深度一般不超过 5，因此执行的
范围不超过这组嵌套的过程。
? 程序中存在相当多的循环结构，它们由少量指令
组成，而被多次执行。
? 程序中存在相当多对一定数据结构的操作，如数
组操作，往往局限在较小范围内。
第四章 存 储 器 管 理
还可以表现为：
? 时间局部性，即一条指令的一次执行和下次执行，
一个数据的一次访问和下次访问都集中在一个较
短时期内；
? 空间局部性，即当前指令和邻近的几条指令，当
前访问的数据和邻近的数据都集中在一个较小区
域内。
基于程序局部性原理, 就 没有必要 把 一个作业一
次性 全部装入内存再开始运行 。 而是可以把程序当前
执行所涉及的信息放入内存中, 其余部分可根据需要
临时调入 。
第四章 存 储 器 管 理
3,虚拟存储器的定义
是指具有请求调入功能和置换功能，能从逻辑
上对内存容量加以扩充的一种存储器系统。
第四章 存 储 器 管 理
4.5.2 虚拟存储器的实现方法
1,分页请求系统
在分页系统的基础上，增加了请求调页功能、
页面置换功能所形成的页式虚拟存储系统。
2,请求分段系统
在分段系统的基础上，增加了请求调段功能、
分段置换功能所形成的段式虚拟存储系统。
第四章 存 储 器 管 理
4.5.3 虚拟存储器的特征
? 多次性（ 虚拟存储器最重要的特征 ）
指一个作业被分成多次调入内存运行。
? 对换性
指允许在作业的运行过程中进行换进、换出。
? 虚拟性（ 实现虚拟存储器的主要目的 ）
指能够从逻辑上扩充内存容量。
三个特征中，虚拟性以多次性、对换性为基础，
而多次性、对换性必须建立在离散分配的基础上。
第四章 存 储 器 管 理
4.6 请求分页存储管理方式
是指在分页系统的基础上, 增加了请求调页
功能, 页面置换功能所形成的页式虚拟存储系统 。
第四章 存 储 器 管 理
页表项,页号、物理块号、状态位、访问位、修
改位、外存地址。
? 状态位：表示该页是在内存还是在外存；
? 访问位：根据访问位来决定淘汰哪页（由不同
的算法决定）；
? 修改位：查看此页是否在内存中被修改过；
? 外存地址：用于指出该页在外存上的地址，通
常是物理块号，供调入该页时参考。
页号 物理块号 状态位 外存地址访问位 修改位
4.6.1 请求分页中的硬件支持
1,页表机制
第四章 存 储 器 管 理
2,缺页中断机构
? 在地址映射过程中，在页表中发现所要访问的页
不在内存，则产生 缺页中断 。操作系统接到此中
断信号后，就调出缺页中断处理程序，根据页表
中给出的外存地址，准备将该页调入内存。
? 此时应将缺页的进程挂起（调页完成后唤醒）。
? 如果内存中有空闲块，则分配一个块，将要调入
的页装入该块，并修改页表中相应页表项目的状
态位及相应的物理块号。
? 若此时内存中没有空闲块，则要淘汰某页（若被
淘汰页在内存期间被修改过，则要将其写回外
存）。
第四章 存 储 器 管 理
缺页中断与一般中断的比较：
相同点：
缺页中断同一般中断都是中断，都需要保护现
场、中断处理、恢复现场。
不同点：
? 一般中断是一条指令完成后中断，缺页中断是
一条指令执行时中断；
? 一条指令执行时可能产生多个缺页中断。
例如一条指令可能访问多个内存地址，这些
地址在不同的页中。
第四章 存 储 器 管 理
将产生 6次缺页中断
例,COPYA TO B 页面
B：
A：
6
5
4
3
2
1
指令
copy A
TO B
第四章 存 储 器 管 理
缺页中断处理
保留 C P U 现场
从外存中找到缺页
内存满否？
选择一页换出
该页被修改否？
将该页写回外存
OS 命令 C P U 从外存读缺页
启动 I / O 硬件
将一页从外存换入内存
修改页表
否
是
是
否
页表项在快表中？
C P U 检索快表
访问页表
否
页在内存？
修改访问位和修改位
形成物理地址
地址变换结束
否
页号＞页表长度?
开始
程序请求访问一页
产生缺页中
断请求调页
修改快表
是
越界中断
是
是
3,地址变换机构
第四章 存 储 器 管 理
两种内存分配策略：
固定分配和可变分配。
两种置换策略：
全局置换和局部置换。
经过组合，得出三种适用的策略：
? 固定分配局部置换
? 可变分配全局置换
? 可变分配局部置换
4.6.2 内存分配策略和分配算法
1,物理块的分配策略
第四章 存 储 器 管 理
2,物理块分配算法
? 平均分配算法
? 按比例分配算法
? 考虑优先权的分配算法
第四章 存 储 器 管 理
? 请求调页 (demand paging)：只调入发生缺页时所
需的页面。
优点,容易实现；
缺点,对外存 I/O次数多，开销较大。
? 预调页 (prepaging)：在发生缺页需要调入某页时，
一次调入该页以及相邻的几个页。
优点,提高调页的 I/O效率；
缺点,基于预测，若调入的页在以后很少被访问，
则效率低。常用于程序装入时的调页。
4.6.3
1,何时调入页面 （有两种常用策略）
第四章 存 储 器 管 理
2,调入页面的来源
? 进程装入时，将其全部页面复制到对换区，以后
总是从对换区调入。执行时调入速度快，要求对
换区空间较大。
? 凡是未被修改的页面，都直接从文件区读入，而
被置换时不需调出；已被修改的页面，被置换时
需调出到对换区，以后从对换区调入。节省对换
区空间，用于缺少足够的对换区的系统。
将外存划分为两部分：文件区, 对换区 。 通常
对外存对换区的 I/O效率比文件区的高 。 关于调入页
面的来源, 这里有两种做法：
第四章 存 储 器 管 理
4.7 页面置换算法
? 把选择换出页面的算法称为 页面置换算法 。
? 应该把那些以后不再会访问的页面换出，或者
把那些停留较长时间而不会再访问的页面调出，
最终的目的是达到一个 较低的页面更换频率 。
第四章 存 储 器 管 理
几种常用置换算法：
? 最佳置换算法 (OPT,Optimal)
? 先进先出置换算法 (FIFO)
? 最近最久未使用置换算法 (LRU,Least Recently
Used)
? Clock置换算法
? 最少使用置换算法 (LFU,Least Frequently
Used)
? 页面缓冲算法 (PBA,Page Buffering Algorithm)
第四章 存 储 器 管 理
? Belady于 1966年提出的一种理论上的算法。
? 选择“未来不再使用的”或“在最长时间内不
再被访问的”页面被置换。
? 通常可以获得最低的缺页率。
? 这是一种理想情况，是实际执行中无法预知的，
因而不能实现。可用作性能评价的依据。
1,最佳 (Optimal)置换算法
4.7.1
第四章 存 储 器 管 理
假定系统为某进程分配了三个物理块,并考虑有
以下的页面号引用串,7,0,1,2,0,3,0,4，
2,3,0,3,2,1,2,0,1,7,0,1 。
7 0
7 7
0
1
7
0
1
2
2
0
1
0 3
2
0
3
0 4
2
4
3
2 3 0 3 2 1
2
0
1
2 0 1 7
7
0
1
0 1
2
0
3
利用最佳页面置换算法时的置换图：
例：
共发生 6次页面置换
▲ ▲ ▲ ▲ ▲ ▲
第四章 存 储 器 管 理
2,先进先出 (FIFO)页面置换算法
? 基本思想：总是先淘汰那些驻留在内存时间最长
的页面，即先进入内存的页面先被置换掉。理由
是：最先进入内存的页面不再被访问的可能性最
大。
? 引入指针将进入内存的页面按时间的先后次序链
成队列，新进入的页面从队尾入队，淘汰总是从
队列头进行。
第四章 存 储 器 管 理
7 0
7 7
0
1
7
0
1
2
2
0
1
0 3
2
3
1
0 4
4
3
0
2 3 0 3 2 1
0
1
3
2 0 1 7
7
0
2
0 1
2
3
0
4
2
0
4
2
3
0
2
3
0
1
2
7
1
2
7
0
1
1
例,（ 同前例 ）
利用 FIFO置换算法时的置换图：
共发生 12次页面置换
▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲
第四章 存 储 器 管 理
Belady现象,
? Belady现象：采用 FIFO算法时，如果对一个进
程未分配它所要求的全部页面，有时就会出现
分配的页面数增多，缺页率反而提高的异常现
象。
? 描述：一个进程 P要访问 M个页,OS分配 N个内
存页面给进程 P；对一个访问序列 S，发生缺页
次数为 PE(S,N)。当 N增大时,PE(S,N)时而增
大，时而减小。
? 原因,FIFO算法的置换特征与进程访问内存的
动态特征是矛盾的，即被置换的页面并不是进
程不会访问的。
第四章 存 储 器 管 理
Belady现象的例子：
进程 P有 5页程序。访问页的顺序为,1,2,3,4,1,2,5,
1,2,3,4,5。
(1) 如果在内存中分配 3个页面，则缺页情况如下：
12次访问中有缺页 9次；
FIFO 1 2 3 4 1 2 5 1 2 3 4 5
页 0 1 2 3 4 1 2 5 5 5 3 4 4
页 1 1 2 3 4 1 2 2 2 5 3 3
页 2 1 2 3 4 1 1 1 2 5 5
缺页 x x x x x x x √ √ x √x
第四章 存 储 器 管 理
(2) 如果在内存中分配 4个页面，则缺页情况如下,12次
访问中有缺页 10次；
FIFO 1 2 3 4 1 2 5 1 2 3 4 5
页 0 1 2 3 4 4 4 5 1 2 3 4 5
页 1 1 2 3 3 3 4 5 1 2 3 4
页 2 1 2 2 2 3 4 5 1 2 3
页 3 1 1 1 2 3 4 5 1 2
缺页 x x x x √ √ x x x x x x
第四章 存 储 器 管 理
? 选择内存中最近一段时间里较久未被访问的页
面予以淘汰。性能接近最佳置换算法。
? 根据程序局部性原理，那些刚被使用过的页面，
可能马上还要被使用，而在较长时间里未被使
用的页面，可能不会马上使用到。
? 由于需要记录页面使用时间的先后关系，硬件
开销太大。
4.7.2 最近最久未使用 (LRU)置换算法
1,LRU置换算法的描述
第四章 存 储 器 管 理
7 0
7 7
0
1
7
0
1
2
2
0
1
0 3
2
0
3
0 4
4
0
3
2 3 0 3 2 1
1
3
2
2 0 1 7
1
0
7
0 1
4
0
2
4
3
2
0
3
2
1
0
2
例,（ 同前例 ）
利用 LRU页面置换算法时的置换图：
共发生 9次页面置换
▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲
第四章 存 储 器 管 理
1)
为了记录某进程在内存中各页的使用情况, 须
为每个在内存中的页面配置一个移位寄存器, 可
表示为,
R = Rn-1Rn-2Rn-3 … R 2R1R0
2,LRU置换算法的硬件支持
当页面被访问时, 对应的寄存器的最左边位置 1；
每隔时间 t,将 r寄存器右移一位；发生缺页中断时,
找最小数值的 r寄存器对应的页面淘汰 。
第四章 存 储 器 管 理
某进程具有 8个页面时的 LRU访问情况
第四章 存 储 器 管 理
2) 栈
用栈保存当前使用页面时栈的变化情况
4
4
7
4
7
0
7
4
0
7
0
4
7
1
7
0
4
1
0
1
7
4
0
1
0
7
4
1
2
1
0
7
4
2
1
2
0
7
4
1
2
1
0
7
4
2
6
2
1
0
7
6
用栈来保存当前使用的各个页面的页面号, 当进
程访问某页面时, 将该页面的页面号从栈中移出, 压
入栈顶 。 因此栈顶始终是最新被访问页面的编号 。
第四章 存 储 器 管 理
? 每页有一个使用访问位, 将内存中的所有页面通
过链接指针链接成一个循环队列 。
? 若该页被访问则置访问位 =1。
4.7.3 Clock置换算法
也称最近未使用算法 (NRU,Not Recently Used)，
是一种最为流行, 低开销的 LRU(最近最久未使用算
法 )近似算法 。
1,简单的 Clock置换算法
第四章 存 储 器 管 理
简单 Clock置换算法的流程和示例
入口
查寻指针前进一步，
指向下一个表目
页面访问
位＝ 0?
选择该页面淘汰
是
返回
置页面访
问位＝ 0
否
替换
指针
块号 页号 访问位 指针
0
1
2 4 0
3
4 2 1
5
6 5 0
7 1 1
第四章 存 储 器 管 理
2,改进型 Clock置换算法
首选置换页面：既是未使用过的页面；又是未修
改的页面 。
由访问位 A和修改位 M可以组合成下面四种类型
的页面：
? 1类 (A=0,M=0)：表示该页最近既未被访问, 又未
被修改, 是最佳淘汰页 。
? 2类 (A=0,M=1)：表示该页最近未被访问, 但已被
修改, 并不是很好的淘汰页 。
? 3类 (A=1,M=0)：最近已被访问, 但未被修改, 该
页有可能再被访问 。
? 4类 (A=1,M=1)：最近已被访问且被修改, 该页可
能再被访问 。
第四章 存 储 器 管 理
(1) 从指针所指示的当前位置开始, 扫描循环队列,
寻找 A=0且 M=0的第一类页面, 将所遇到的第一个
页面作为所选中的淘汰页 。 在第一次扫描期间不改
变访问位 A。
(2) 如果第一步失败, 即查找一周后未遇到第一类页
面, 则开始第二轮扫描, 寻找 A=0且 M=1的第二类
页面, 将所遇到的第一个这类页面作为淘汰页 。 在
第二轮扫描期间, 将所有扫描过的页面的访问位都
置 0。
(3) 如果第二步也失败, 亦即未找到第二类页面, 则
将指针返回到开始的位置, 并将所有的访问位复 0。
然后重复第一步, 如果仍失败, 必要时再重复第二
步, 此时就一定能找到被淘汰的页 。
第四章 存 储 器 管 理
? 选择到当前时间为止被访问次数最少的页面被置
换。
? 为内存中每页设置一个移位寄存器，每次访问某
页时将该移位寄存器最高位置 1，每隔一定时间
右移一次。使用最少的页面即为 ∑ Ri最小的页。
（ 页面访问图同 LRU置换算法）
? 会出现的问题：不能真正反映页面的使用情况。
4.7.4 其它置换算法
1,最少使用 (LFU)置换算法
第四章 存 储 器 管 理
2,页面缓冲算法 (PBA)
? 它是对 FIFO算法的发展，通过被置换页面的缓
冲，有机会找回刚被置换的页面；
? 被置换页面的选择和处理：用 FIFO算法选择被
置换页，把被置换的页面放入两个链表之一：
----如果页面未被修改，就将其归入到空闲页面
链表的末尾；
----否则将其归入到已修改页面链表。
第四章 存 储 器 管 理
? 需要调入新的物理页面时，将新页面内容读入
到空闲页面链表的第一项所指的页面，然后将
第一项删除。
? 空闲页面和已修改页面，仍停留在内存中一段
时间，如果这些页面被再次访问，只需较小开
销，而被访问的页面可以返还作为进程的内存
页。
? 当已修改页面达到一定数目后，再将它们一起
调出到外存，然后将它们归入空闲页面链表，
这样能大大减少 I/O操作的次数。
第四章 存 储 器 管 理
缺页率的计算：
缺页率 =缺页次数 /访问串的访问次数
第四章 存 储 器 管 理
思考题：
某程序在内存中分配 3块内存, 初始为空, 访
问页的走向为 2,3,2,1,5,2,4,5,3,2，
5,2,用 FIFO和 LRU算法分别计算缺页次数和
缺页率 。
第四章 存 储 器 管 理
FIFO 2 3 2 1 5 2 4 5 3 2 5 2
页 1 2 3 3 1 5 2 4 4 3 3 5 2
页 2 2 2 3 1 5 2 2 4 4 3 5
页 3 2 3 1 5 5 2 2 4 3
x x ? x x x x ? x ? x x
共缺页中断 9次，缺页率,9/12=0.75。
解：
第四章 存 储 器 管 理
LRU 2 3 2 1 5 2 4 5 3 2 5 2
页 1 2 3 2 1 5 2 4 5 3 2 5 2
页 2 2 3 2 1 5 2 4 5 3 2 5
页 3 3 2 1 5 2 4 5 3 3
x x ? x x ? x ? x x ? ?
共缺页中断 7次，缺页率,7/12。
第四章 存 储 器 管 理
4.8 请求分段存储管理方式
为了能实现虚拟存储, 段式逻辑地址空间中的
程序段在运行时并不全部装入内存, 而是如同请
求式分页存储管理, 首先调入一个或若干个程序
段运行, 在运行过程中调用到哪段时, 就根据该
段长度在内存分配一个连续的分区给它使用 。 若
内存中没有足够大的空闲分区, 则考虑进行段的
紧凑或将某段或某些段淘汰出去 。 相应于请求式
分页存储管理, 这种存储管理技术称为 请求分段
存储管理方式 。
第四章 存 储 器 管 理
1.
外存
始址
增补
位
存在
位 P
修改
位 M
访问字
段 A
存取
方式
段的
基址段长段号
4.8.1 请求分段中的硬件支持
第四章 存 储 器 管 理
2,缺段中断机构
? 当发现要访问的段尚未调入内存时, 便由缺段
中断机构产生以缺段中断信号, 进入缺段中断
处理程序, 将所需的段调入内存 。
? 由于段是程序的逻辑单位, 因此不会出现一条
指令出现在两个分段中, 或一组相关信息被分
割在两个段中的情况 。
? 但是由于段不是定长的, 因此处理过程比缺页
中断复杂 。
第四章 存 储 器 管 理虚段 S不在内存
阻塞请求进程
内存中有合适
的空闲区吗？
从外存读入段 S
修改段表及内存空区链
唤醒请求进程
返回
空区容量总
和能否满足？
空区拼接, 以形成
一个合适的空区
淘汰一个或几个实段
以形成一个合适空区
否
否
是
是
请求分段系统中的
中断处理过程
第四章 存 储 器 管 理
? 是在分段系统地址变换机构的基础上形成的 。
? 若发现要访问的段不在内存, 首先必须将所缺
的段调入内存, 修改段表, 然后才能利用段表
进行地址变换 。
? 增加了一些功能, 如缺段中断的请求, 及相应
的处理过程等 。
3,地址变换机构
第四章 存 储 器 管 理访问 [s][w]
w≤ 段长?
符合存取方式?
段 S在主存?
修改访问字段,如写
访问,置修改位 ＝ 1
形成访问主存地址
(A)＝ (主存始址 )
＋ (位移量 w)
返回
分段越界
中断处理
分段保护
中断处理
缺段中
断处理
是
是
是
否
否
否
请
求
分
段
系
统
的
地
址
变
换
过
程
第四章 存 储 器 管 理4.8.2 分段的共享与保护
1,共享段表
为了实现分段共享, 在系统中配置一张共享段表,
每个共享段占有一个表项 。 表项中记录了共享段的段
号, 段长, 内存始址, 存在位等信息, 并记录了使用
此共享段的所有进程的情况 。
段名 段长 内存始址 状态 外存始址
共享进程计数 count
状态 进程名 进程号 段号 存取控制
… … … … ……
共享段表
第四章 存 储 器 管 理
2,共享段的分配与回收
1)
? 第一次请求调入时：把共享段调入内存一物理区,
修改请求调入进程的段表的相应项, 还要在共享
段表中增加一表项, 填写相关数据, 把 count置 1。
? 之后, 当又有其它进程需要调用该共享段时：由
于该共享段已被调入内存, 故此时无须再为该段
分配内存, 而只需在调用进程的段表中, 增加一
表项, 填写该共享段的物理地址；在共享段的段
表中, 填上调用进程的进程名, 存取控制等, 再
执行 count∶ =count+1操作, 以表明有两个进程
共享该段 。
第四章 存 储 器 管 理
2) 共享段的回收
? 当进程不需要该段, 应将该段释放, 撤销在段
表中共享段对应的表项, 执行 count,=count-1操
作 。
? 若结果为 0,则系统回收该共享段, 以及取消共
享段表中所对应的表项, 表明此时已没有进程使
用该段 。
? 否则 (减 1结果不为 0),则只是取消调用者进程
在共享段表中的有关记录 。
第四章 存 储 器 管 理
3,分段保护
1) 越界检查
2) 存取控制检查
(1)只读 (2) 只执行 (3) 读 /写
3) 环保护机构
(1)一个程序可以访问驻留在相同环或较低特权
环中的数据。
(2)一个程序可以调用驻留在相同环或较高特权
环中的服务。
第四章 存 储 器 管 理
环保护机构
调用 返回
调用
返回
环 0
环 1
环 2
(a) 程序间的控制传输
数据访问
环 0
环 1
环 2
(b) 数据访问
数据访问
第四章 存储器管理
4.1 程序的装入和链接
4.2 连续分配方式
4.3 基本分页存储管理方式
4.4 基本分段存储管理方式
4.5 虚拟存储器的基本概念
4.6 请求分页存储管理方式
4.7 页面置换算法
4.8 请求分段存储管理方式
第四章 存 储 器 管 理
存储器管理是指对存储器资源的管理。存储
器管理的主要对象是 内存 。
存储管理的内容主要包括：
? 存储器资源的组织 （ 如内存的组织方式 ） ；
? 地址变换 （ 逻辑地址与物理地址的对应关系
维护 ） ；
? 虚拟存储的调度算法。
第四章 存 储 器 管 理
4.1 程序的装入和链接
对用户程序的处理步骤
编译
目标模块
库
…
..
链接
程序
装入模块 装入程序
内存
源程序
第四章 存 储 器 管 理
4.1.1 程序的装入
将一个模块装入内存时，可采用三种方式：
? 绝对装入方式
? 可重定位方式
? 动态运行时装入方式
第四章 存 储 器 管 理
1,绝对装入方式
如果事先知道程序将驻留在
内存的什么位置，那么编译
或汇编程序将产生绝对地址
的目标代码，装入程序直接
将目标代码装入相应的内存
空间。
Load 2224
365
2224
1024
? 优点,装入过程简单。
? 缺点,过于依赖于硬件结构，只适用于单道程
序环境，不适于多道程序系统。
第四章 存 储 器 管 理
2,可重定位方式
把用户程序在装入内存时对目标程序中指令和数
据的修改过程称为 重定位 。
当用户程序被装入内存时，一次性实现逻辑地址
到物理地址的转换，以后不再转换,称为 静态重定
位 。
? 优点,无需硬件支持，地址变换由重定位装配程
序完成。
? 缺点,地址变换在装入时一次性完成，装入内存
后不能移动，不利于内存空间的有效利用，难于
实现程序的共享。
第四章 存 储 器 管 理
LOAD 1,2500
365
LOAD 1,12500
365
10000
11000
12500
150005000
2500
1000
0
作业地址空间
内存空间
逻辑地址 物理地址
第四章 存 储 器 管 理
3,动态运行时装入方式
装入模块装入内存后，不立即把相对地址转换
成绝对地址，而是推迟到程序真正要执行时才进
行。
优点,程序占用的内存空间可动态变化，即允许
程序在内存中移动；也不必分配连续的内存空
间，便于程序的共享。
缺点,需要硬件 重定位寄存器 支持,OS实现较复
杂。
第四章 存 储 器 管 理
4.1.2 程序的链接
链接是指多个目标模块在执行时的地址空间分
配和相互引用。
根据链接时间的不同，把链接分为以下三种类
型：
? 静态链接方式
? 装入时动态链接
? 运行时动态链接
第四章 存 储 器 管 理
1,静态链接方式
将所有目标模块和所需的库函数在装入前事先
链接成一个完整的装入模块（可执行文件），以
后不再拆开的链接方式。
在将几个目标模块链接装配成一个装入模块时，
需要解决以下两个问题：
? 对相对地址进行修改；
? 变换外部调用符号。
第四章 存 储 器 管 理
例：
模块 A
CALL B；
Return；
0
L－ 1
模块 B
CALL C；
Return；
0
M－ 1
模块 C
Return；
0
N－ 1
0
模块 A
JSR“L”
Return；L－ 1
模块 B
JSR“L＋ M”
Return；
L
L＋ M－ 1
L＋ M
L＋ M＋ N－ 1
模块 C
Return；
(a) 目标模块 (b) 装入模块
第四章 存 储 器 管 理
2,装入时动态链接
一个程序的多个目标模块在装入内存时，边装
入边链接。
优点,
? 便于修改和更新；
? 便于实现对目标模块的共享。
第四章 存 储 器 管 理
3,运行时动态链接
一个程序的多个目标模块在程序执行时，根据
需要再动态装入和链接。
优点,
本次执行过程中不用的模块可以不装入和链接。
如典型的错误处理模块。
第四章 存 储 器 管 理
连续分配是指为一个用户程序分配一个连续的
内存空间。具体分为四种分配方式：
? 单一连续分配
? 固定分区分配
? 动态分区分配
? 可重定位分区分配
4.2 连续分配方式
第四章 存 储 器 管 理
4.2.1 单一连续分配方式
? 最简单的一种存储管理方式，适用于单用户、
单任务的 OS。
? 把内存分为两个区域：系统区，用户区。应用
程序装入到用户区，可使用用户区全部空间。
? 优点,易于管理。
? 缺点,对要求内存空间少的程序，造成内存浪
费；程序全部装入，很少使用的程序部分也占
用内存。
第四章 存 储 器 管 理
4.2.2 固定分区分配方式
? 最简单的可运行多道程序的存储管理方式。
? 将内存的用户空间划分为若干个固定大小的连
续分区，在每个分区中只装入一道作业。
1,划分分区的方法：
? 分区大小相等：只适合于多个相同程序的并发
执行（处理多个类型相同的对象）。
? 分区大小不等：多个小分区、适量的中等分区、
少量的大分区。根据程序的大小，分配当前空
闲的、适当大小的分区。
第四章 存 储 器 管 理
固定分区 (大小相同 ) 固定分区 (大小不同 )
例：
8 M
8 M
8 M
8 M
8 M
Operating System 8 M
12 M
8 M
8 M
6 M
4 M
2 M
Operating System
第四章 存 储 器 管 理
? 分区使用表,用于记录分区的大小和使用情况，
按分区大小排队。包括每个分区的起始地址、
大小和状态（是否分配）。
? 用户程序需要装入时，内存分配程序检索该表，
找出一个能满足要求尚未分配的分区，分配给
该程序，并将其表项中的状态置为“已分配”。
? 若未找到大小足够的分区，则拒绝为用户程序
分配内存。
2,内存分配
第四章 存 储 器 管 理
例,某系统的内存容量为 256K，操作系统占用低地址
的 20K，其余空间划分成 4个固定大小的分区。
OS
20K
28K
60K
124K
256K-1
作业 A（ 6K）
作业 B（ 20K）
作业 C（ 50K）
1
2
3
4
0K
主存
作业 A
6K
作业 B
20K
作业 C
50K
作业队列
第四章 存 储 器 管 理
分区说明表
分区号 大小 (KB) 始址 (KB) 状态
1 8 20 已分配
2 32 28 已分配
3 64 60 已分配
4 132 124 未分配
第四章 存 储 器 管 理
? 优点,易于实现，开销小。
? 缺点：
?内碎片造成浪费；
?分区总数固定，限制了并发执行的程序数目。
第四章 存 储 器 管 理
4.2.3 动态分区分配方式
? 动态创建分区：在装入程序时按其初始要求分
配，或在其执行过程中通过系统调用进行分配
或改变分区大小。
? 优点,没有内碎片。
? 缺点,有外碎片；如果大小不是任意的，也可
能出现内碎片。
第四章 存 储 器 管 理
进程 A（ 8K） 进程 D（ 124K）进程 B（ 16K） 进程 C（ 64K） …
OS
进程 A
进程 B
进程 C
进程 D
OS
进程 A
进程 B
进程 C
OS
进程 A
进程 B
OS
进程 A
第四章 存 储 器 管 理
1,分区分配中的数据结构
? 空闲分区表,记录每个空闲分区的情况, 包括
分区序号, 分区始址, 分区大小等 。
? 空闲分区链：
?在每个空闲分区的起始部分开辟出一个单元,
存放一个链表指针和该分区的大小, 在尾部则
设置一后向指针 。
?系统中用一个固定单元作为空闲分区链表的链
表头指针, 指向第一块空闲分区首地址, 最后
一块空闲分区的链表指针存放链尾标志 。
?当分区被分配出去以后, 状态位由, 0”改为
,1”,此时前后指针无意义 。
第四章 存 储 器 管 理例,采用 双向链的空闲分区链结构
第四章 存 储 器 管 理
2,分区分配算法
? 首次适应算法
? 循环首次适应算法
? 最佳适应算法
第四章 存 储 器 管 理
首次适应法 FF：
? 要求空闲区按 首址递增 的次序组织空闲区表（队
列）。
? 当进程申请大小为 SIZE的内存时, 系统从空闲区
表的第一个表目开始查询, 直到首次找到等于或
大于 SIZE的空闲区 。 从该区中划出大小为 SIZE的
分区分配给进程, 余下的部分仍作为一个空闲区
留在空闲区表中, 但要修改其首址和大小 。
第四章 存 储 器 管 理
? 优点：
该算法是尽可能地利用低地址空间，从而保
证高地址空间有较大的空闲区。
? 缺点：
低地址部分的不断划分，会留下许多难以利
用的、很小的空闲分区，而每次查找都是从低
地址部分开始，会增加查找可利用分区时的开
销。
第四章 存 储 器 管 理
循环首次适应算法：
? 把存储空间中空白区构成一个循环链，每次为
存储请求查找合适的分区时，总是从上次查找
结束的地方开始，只要找到一个足够大的空白
区，就将它划分后分配出去。
? 优点,能使内存中的空闲分区分布均匀，从而
减少了查找空闲分区时的开销。
? 缺点,使内存中缺乏大的分区。
第四章 存 储 器 管 理
最佳适应算法：
? 要求按空闲区大小 从小到大 的次序组成空闲区
表（队列）。
? 当进程申请一个存储区时，系统从表头开始查
找，当找到第一个满足要求的空闲区时，停止
查找，并且这个空闲区是最佳的空闲区。
? 所谓最佳即选中的空闲区是满足要求的最小空
闲区。
第四章 存 储 器 管 理
? 优点：
?在系统中若存在一个与申请分区大小相等的空
闲区, 必定会被选中, 而首次适应法则不一定 。
?若系统中不存在与申请分区大小相等的空闲区,
则选中的空闲区是满足要求的最小空闲区, 而
不致于毁掉较大的空闲区 。
? 缺点：
空闲区的大小一般与申请分区大小不相等，
因此将其一分为二，留下来的空闲区一般情况
下是很小的，以致无法使用。随着时间的推移，
系统中的小空闲区会越来越多，从而造成存储
区的大量浪费。
第四章 存 储 器 管 理
几点说明：
? 上述三种分配算法各有利弊, 到底哪种最好不
能一概而论, 而应针对具体作业序列来分析 。
? 对于某一作业序列来说, 某种算法能将该作业
序列中所有作业安置完毕, 那么我们说该算法
对这一作业序列是 合适的 。
? 对于某一算法而言，如它不能立即满足某一要
求，而其它算法却可以满足此要求，则这一算
法对该作业序列是 不合适的 。
第四章 存 储 器 管 理
例：
有一作业序列：作业
A要求 18K；作业 B要求
25K，作业 C要求 30K。
分析系统中空闲区按
三种算法组成的空闲区
队列。
（图中灰色部分为空闲
区。）
第四章 存 储 器 管 理
① 首次适应算法的空闲区队列：
② 循环首次适应算法的空闲区队列：
③ 最佳适应算法的空闲区队列：
30K 20K 5K 46K ^
20K 100K 160K 210K链首指针
30K 20K 5K 46K
20K 100K 160K 210K链首指针
2K 20K 30K 46K ^
160K 100K 20K 210K链首指针
第四章 存 储 器 管 理
3,分区的分配
? 在采用分区存储管理的系统中，系统初启后。
除操作系统占用一个分区外，其余存储区为一
个大的空闲区。
? 分区的分配是指 利用某种分配算法，找到所需
的分区，按照大小划分出一块内存空间分配出
去，剩余的部分留在空闲分区链中。
第四章 存 储 器 管 理从头开始查表
检索完否？
m.size＞ u.size?
m.size－ u.size≤size?
从该分区中划出
u.size 大小的分区
将该分区分配给请求者修
改有关数据结构
返回
返回
继续检索下一个表项
将该分区从链中移出
Y
N
N
Y
Y
N
分
配
流
程
图
：
第四章 存 储 器 管 理
说明：
将一个空闲区分成二部分有两种办法：
a) 从空闲区的上部开始划出 U.SIZE大小的空闲
区给用户；
b) 从空闲区的底部开始向上划出 U.SIZE大小的
空闲区给用户 。
一般常用第二种办法, 因为这样划分时, 余下
的部分在空闲区表中的首地址不变, 只需要修
改一下大小就行了 。
第四章 存 储 器 管 理
4.分区的回收
? 当某个进程释放某存储区时, 系统首先检查
释放区是否与系统中的空闲区相邻, 若相邻
则把释放区合并到相邻的空闲区中去, 否则
把释放区作为一个空闲区插入到空闲区表的
适当位置 。
? 分区回收时会有四种情况：
第四章 存 储 器 管 理
第四章 存 储 器 管 理
4.2.4 可重定位分区分配
? 不能被利用的小分区称为,零头,或,碎片,。
? 通过移动，把多个分散的小分区拼接成大分区
的方法被称为,拼接,或,紧凑,。
? 每次“紧凑”后必须对移动了的程序或数据进
行重新定位。
1,动态重定位的引入
第四章 存 储 器 管 理
操作系统
作业 1
作业 2
作业 3
空闲区
作业 4
操作系统
作业 1
空闲区
作业 2
空闲区
作业 3
空闲区
操作系统
作业 1
作业 2
作业 3
空闲区
紧凑前 紧凑后
第四章 存 储 器 管 理
2,动态重定位的实现
? 需要硬件地址变换机构的支持，即重定位寄存
器。
? 内存地址＝相对地址＋重定位寄存器中的地址。
? 地址变换过程是在程序执行期间，随着对每条
指令或数据的访问而自动进行的。
第四章 存 储 器 管 理
LOAD1,2500
365
0
100
2500
5000
2500
相对地址
10000
重定位寄存器
＋
LOAD1,2500
365
10000
10100
12500
15000
作业 J
处理机一侧 存储器一侧 主存
动态重定位示意图
第四章 存 储 器 管 理
3,动态重定位分区分配算法
流程图,请求分配u.size分区
检索空闲分区链 (表 )
找到大于 u.size
的可用区?
按动态分区方式
进行分配
修改有关的
数据结构
返回分区号
及首址
空闲分区
总和 ≥ u.size?
进行紧凑形
成连续空闲区
修改有关的
数据结构
否
是
无法分配
返回
否
是
第四章 存 储 器 管 理
4.2.5 对换
1,对换的引入
? 对换 是指把内存中暂时不能运行的进程或者暂
时不用的程序和数据，调出到外存上，以便腾
出足够的内存空间，再把已具备运行条件的进
程或者进程所需的程序和数据，调入内存。
? 通过对换，可利用外存来逻辑地扩充主存。
? 如果对换以整个进程为单位，便称,整体对换,
或,进程对换,。如果以“页”或“段”为单
位，则分别称,页面对换,或,分段对换,，
并通称,部分对换,。
第四章 存 储 器 管 理
2,对换空间的管理
在具有对换功能的 OS中，通常把外存分为 文件
区 和 对换区 。
? 文件区存放文件，常采用离散方式，以提高文
件存储空间的利用率；
? 对换区存放从内存换出的进程，常利用连续分
配方式，以提高对换速度。
第四章 存 储 器 管 理
? 进程的换出：选择处于阻塞状态且优先级最
低的进程作为换出进程，换出后收回内存空
间，修改进程的 PCB相关信息。
? 进程的换入：找出“就绪”状态并已经换出
的进程，将其中换出时间最久的进程作为换
入进程，将其换入。直到已无可换入的进程
和无可换出的进程。
3,进程的换出和换入
第四章 存 储 器 管 理
4.3 基本分页存储管理方式
离散分配方式,为了减少因连续分配所产生的碎片，
提高内存的利用率产生了离散分配方式，它可将一
个用户程序离散地分配到内存中的多个不相连接的
区域中。
其方式有：
a.分页存储管理方式－离散的基本单位是, 页, ；
b.分段存储管理方式－离散的基本单位是, 段, ；
c.段页式存储管理方式。
第四章 存 储 器 管 理
基本分页存储管理方式：
在分页存储管理方式中，如果不具备页面对
换功能，就是基本分页存储管理方式，即不支
持虚拟存储器的功能。
第四章 存 储 器 管 理
1,页面
页（页面） －把每个作业 (进程 )逻辑地址空间
划分成若干大小相等的片。
物理块 －把内存空间划分成与页相同的片。
2,分页式存储器的逻辑地址结构
分页地址中的地址结构确定了主存储器的分
页大小,也决定了页面大小。
页 号 P 页内地址 (偏移量 )
31 12 11 0
总页数,220＝ 1M(页 )；每页大小为,212＝ 4KB
第四章 存 储 器 管 理
3,页表
? 系统为每个进程建立一张页面映象表，即 页表 。
? 页表的长度和首地址存放在该进程的进程控制块
（ PCB）中。
? 页表的作用是实现从页号到物理块号的 地址映射。
? 页表由 页号 和 块号 组成，指出逻辑地址中页号与
主存中物理块号的对应关系。
? 页号 ---作业地址空间的页序号。
? 块号 ---内存空间的页面序号。
逻辑上相邻的页，物理上不一定相邻。
页号 块号
0 2
1 3
2 6
第四章 存 储 器 管 理
页表的作用
用户程序
0 页
1 页
2 页
3 页
4 页
5 页
…
n 页
页表
页号 块号
0 2
1 3
2 6
3 8
4 9
5
… …
内存空间
0
1
2
3
4
5
6
7
8
9
10
第四章 存 储 器 管 理
注意,页大小的选择
? 太大：浪费；
? 太小：页表过长；
? 页的大小是 2K, 通常为 512B-5KB。
第四章 存 储 器 管 理
例,如图，作业 1有 2页分别装入内存的第 5,6块；
作业 2有 3页装入内存的第 2,4,7块；作业 3有 1 页
装入内存的第 8块。
第四章 存 储 器 管 理
4.3.2 地址变换机构
? 基本任务：逻辑地址 ?物理地址。
? 由于页面和物理块大小相同，他们的地址是一
一对应的，无需变换。所以地址变换实际上只
是将逻辑地址中的页号，转换为内存中的物理
块号，这一任务是由页表来完成的。
即,页号 ?页表 ?存储块号 b，与 页内地址 w合
成，形成 物理地址 。
第四章 存 储 器 管 理1,基本的地址变换机构
页表长度（ 5）页表始址 页内地址 w页号（ 3）
wbb
0
1
2
3
4
页表寄存器 逻辑地址
页表
物理地址
块号页号
＋
>
越界中断
第四章 存 储 器 管 理
例,在采用页式存储管理的系
统中，某作业 J的逻辑地址
空间为 4页（每页 2048字
节），且已知该作业的页面
映像表（即页表）如右图，
试借助地址变换图（要求画
出地址变换图）求出有效逻
辑地址 4865所对应的物理地
址。
页号 块号
0 2
1 4
2 6
3 8
第四章 存 储 器 管 理
页表长度页表始址 页内地址页号
7696
页表寄存器 逻辑地址
页表
物理地址
＋
页号 块号
0 2
1 4
2 6
3 8
4865=2*2048+769
7692
物理地址,6*2048+769=13057
第四章 存 储 器 管 理
2.具有快表的地址变换机构
? 在前述的页地址变换过程中有一个严重的问题,
那就是每一次对内存的访问都要访问页表, 页
表是放在内存中的, 也就是说每一次访问内存
的指令至少要访问两次内存, 运行速度要下降
一半 。
? 若不解决这一问题是不能令人忍受的 。
第四章 存 储 器 管 理
? 为了提高存取速度, 通常设置一个具有并行查
询能力的特殊 高速缓冲寄存器, 存放当前作业
的 最常用 的页号及对应块号 。 我们把存放在高
速缓冲寄存器中的页表叫 快表, 把存放在内存
中的页表称为 慢表 。
? 快表又叫 联想寄存器 。
? 需要说明的是：快表的地址转换是非常快的,
因为它是将页号与快表中的各行同时比较, 从
而大大减少了地址变换时间, 基本上克服了两
次访问主存的缺点 。
第四章 存 储 器 管 理
页表长度（ 5）页表始址 页内地址 w页号（ 3）
wbb
0
1
2
3
4
页表寄存器 逻辑地址寄存器
页表
块号页号
＋
>
b
输
入
寄
存
器
块号页号
快表
具有快表的地址变换机构
越界中断
第四章 存 储 器 管 理
4.3.3 两级页表和多级页表
? 当页表项很多时, 仅采用一级页表需要大片连
续空间, 可将页表也分页, 并对页表所占的空
间进行索引形成外层页表 。 由此构成 两级页表 。
? 更进一步可形成 多级页表 。
第四章 存 储 器 管 理
1,两级页表
外层页表有 210个页表项；
最多允许有 210个页表分页；
页面大小为,212＝ 4KB。
逻辑地址结构可描述如下：
第四章 存 储 器 管 理
1011
1078
0
1
2
1742n
第 0页页表
1
4
6…
01
2…
1023
第 1页页表
114
115
0
1…
1023外部页表
0
1
2
3
4
5
6
7
…
…
114
115
1468
第 n页页表
14680
1
2…
1023 内存空间
两级页表结构
第四章 存 储 器 管 理
具有两级页表的地址变换机构
外部页号
P1 P2
外部页内地址 页内地址
d逻辑地址
＋外部页表寄存器
外部页表
＋ db
页表
物理地址… …
两级页表地址变换需 三次 访问内存：一次访问页目
录, 一次访问页表页, 一次访问指令或数据, 访问
时间加了两倍 。 可增设快表, 提高访问速度 。
第四章 存 储 器 管 理
4.4 基本分段存储管理方式
分页存储管理方式中用户的程序地址空间是一
维线性的，这对用户特别是程序设计极不方便，
用户看待程序是以自然段为单位的，如：主程序
段、子程序段、数据段等 …… 。因此人们提出了
段式存储管理方式。
第四章 存 储 器 管 理
将程序的地址空间按内容或过程（函数）关系
划分为若干个段，每段有自己的名字。以段为单
位分配内存，然后通过地址重定位机构把段式虚
拟地址转换为实际的内存物理地址。
基本思想：
第四章 存 储 器 管 理
主要是为了满足用户和程序员的下述需要：
? 方便编程
? 分段共享
? 分段保护
? 动态链接
? 动态保护
? 动态增长
4.4.1 分段存储管理方式的引入
第四章 存 储 器 管 理
1,分段
? 每个段定义了一组逻辑信息。如：主程序段、
子程序段、数据段等。
? 用段号代替段名。
? 两维逻辑地址：段号＋段内地址。
? 地址结构,段号 S + 段内地址 W
4.4.2 分段系统的基本原理
段号 S 段内地址 d
31 16 15 0
(一个作业最多 216=64K个段, 每段最大长度 216=64KB)
第四章 存 储 器 管 理
? 每个进程一张表，用以实现地址变换,程序的每
一个段在段表中占用一个表目。
? 包括：段的长度、段的首址 (基址 )信息。
2,段表
段号
0
1
2
段首址段长度
58K20K
100K110K
260K140K
第四章 存 储 器 管 理作业空间
(MAIN)＝ 00
30K (X)＝ 1
0
20K
(D)＝ 20
15K (S)＝ 3
0
10K
30K
20K
15K
10K
40K
80K
120K
150K
段长 基址段号 (MAIN)＝ 0
30K
(X)＝ 1
20K
(D)＝ 2
15K
(S)＝ 3
10K
0
40K
80K
120K
150K
段表
内存空间
0
1
2
3
利用段表实现地址映射
第四章 存 储 器 管 理3,地址变换机构
控制寄存器
段表始址 段表长度 ＞ 2 100
＋
段号 S越界
1 K
段长
600
段号
0
1
2
3
6 K
4 K
500
200
8 K
9200
基址
位移量 W
＋
8292
8K
8292
8692
主存
物理地址
有效地址
地址变换需 两次 访问内存, 访问
时间加了一倍 。 可增设快表, 提
高访问速度 。
第四章 存 储 器 管 理
例,有一段表如
右图所示，试分
别求逻辑地址
（ 2,88）和逻
辑地址（ 4,100）
所对应的物理地
址。
段号 基地址 段长
0 219 600
1 2300 14
2 90 100
3 1327 580
4 1952 96
第四章 存 储 器 管 理
4,分段与分页技术的比较
相似,二者在内存中都不是整体连续的, 都要通过
地址映射机构将逻辑地址映射到物理内存中 。
不同：
?, 页, 是信息的, 物理, 单位, 大小固定 。, 段,
是信息的逻辑单位, 即它是一组有意义的信息,
其长度不定 。
? 页的大小是由系统固定的, 在一个系统中所有页
的大小是一样的, 只能有一种大小；段的长度因
段而异, 取决于用户所编写的程序
? 分页的作业的地址空间是单一的线性地址空间,
分段作业的地址空间是二维的 。
第四章 存 储 器 管 理
4.4.3 信息共享
分段系统的一个突出优点是易于实现段的共享,
即允许若干个进程共享一个或多个分段, 且对共享
段的保护也简单易行 。 分页系统虽然也能实现程序
和数据的共享, 但远不如分段系统方便 。
例,40个用户 共享一文本编辑程序 。 该程序有
160KB的代码和 40KB的数据区 。 其中, 160KB的
代码为 可重入代码 （ 即允许多个进程同时访问的代
码, 但不允许任何进程对它进行修改 。 ）
第四章 存 储 器 管 理
e d 1
e d 2
…
e d 4 0
d a t a 1
…
d a t a 1 0
进程 1
21
22
…
60
61
…
70
页表
e d 1
e d 2
…
e d 4 0
d a t a 1
…
d a t a 1 0
进程 2
21
22
…
60
71
…
80
…
e d 1
e d 2
…
e d 4 0
d a t a 1
…
d a t a 1 0
d a t a 1
…
d a t a 1 0
主存
0
21
22
60
61
70
71
80
页表
分页系统中共享 editor的示意图
（ 设页面大小为 4KB）
第四章 存 储 器 管 理
分段系统中共享 editor的示意图
e d i t o r
进程1
d a t a 1
进程2
e d i t o r
d a t a 2
段表
段长 基址
1 6 0 80
40 2 4 0
1 6 0 80
40 3 8 0
e d i t o r
d a t a 1
?
d a t a 2
80
2 4 0
2 8 0
3 8 0
4 2 0
第四章 存 储 器 管 理
4.4.4 段页式存储管理方式
引入：
分页和分段管理方式各有其优缺点，分页系统
能有效提高内存的利用率，而分段则能更好地满
足用户的需要，因此可以将两者结合成一种新的
存储管理方式系统称为,段页式系统,。
第四章 存 储 器 管 理
1,基本原理
? 一个程序首先被分成若干程序段，每一段赋予
不同的分段标识符，然后，对每一分段又分成
若干个固定大小的页面。
? 地址结构：分三部分
（如图所示）
第四章 存 储 器 管 理
作业地址空间和地址结构
0
4K
8K
12K
15K
16K
子程序段0
4K
8K
数据段0
4K
8K
10K
12K
(a)
段号 (S) 段内页号 (P) 页内地址 (W)
(b)
主程序段
第四章 存 储 器 管 理
2,地址映射
? 段表：记录了每一段的页表始址和页表长度。
? 页表：记录了逻辑页号与内存块号的对应关系
（每一段有一个，一个程序可能有多个页表）。
? 内存分配管理：同页式管理。
? 如图所示：
第四章 存 储 器 管 理
利用段表和页表实现地址映射
段号 状态 页表大小 页表始址
0 1
1 1
2 1
3 0
4 1
页号 状态 存储块 #
0 1
1 1
2 1
3 0
4 1
操作系统
主存
页表
段表
段表大小 段表始址
段表寄存器
第四章 存 储 器 管 理3,地址变换过程
段表寄存器
段表始址 段表长度 ＞ 段号 S 页号 P
＋
段超长
段表
0
1
2
3 ＋
页内地址
页表
0
1
2
3 b 块号 b 块内地址
页表始址页表长度
地址变换需 三次 访问内存：一次访问段表, 一次访
问页表, 一次访问指令或数据, 访问时间加了两倍 。
可增设快表, 提高访问速度 。
第四章 存 储 器 管 理
4.5 虚拟存储器的基本概念
基本思想：
通过软硬件结合的方法，利用大容量的外存空
间来逻辑扩充内存，使得产生一种不受实际内存
容量大小限制的逻辑的虚拟存储器。
第四章 存 储 器 管 理
1.常规存储器管理方式的特征
? 一次性
? 驻留性
4.5.1
第四章 存 储 器 管 理
2,局部性原理
指程序在执行过程中的一个较短时期，所执行的
指令地址和指令的操作数地址，分别局限于一定区
域。具体表现在以下几方面：
? 程序在执行时，大部分是顺序执行的指令，少部
分是转移和过程调用指令。
? 过程调用的嵌套深度一般不超过 5，因此执行的
范围不超过这组嵌套的过程。
? 程序中存在相当多的循环结构，它们由少量指令
组成，而被多次执行。
? 程序中存在相当多对一定数据结构的操作，如数
组操作，往往局限在较小范围内。
第四章 存 储 器 管 理
还可以表现为：
? 时间局部性，即一条指令的一次执行和下次执行，
一个数据的一次访问和下次访问都集中在一个较
短时期内；
? 空间局部性，即当前指令和邻近的几条指令，当
前访问的数据和邻近的数据都集中在一个较小区
域内。
基于程序局部性原理, 就 没有必要 把 一个作业一
次性 全部装入内存再开始运行 。 而是可以把程序当前
执行所涉及的信息放入内存中, 其余部分可根据需要
临时调入 。
第四章 存 储 器 管 理
3,虚拟存储器的定义
是指具有请求调入功能和置换功能，能从逻辑
上对内存容量加以扩充的一种存储器系统。
第四章 存 储 器 管 理
4.5.2 虚拟存储器的实现方法
1,分页请求系统
在分页系统的基础上，增加了请求调页功能、
页面置换功能所形成的页式虚拟存储系统。
2,请求分段系统
在分段系统的基础上，增加了请求调段功能、
分段置换功能所形成的段式虚拟存储系统。
第四章 存 储 器 管 理
4.5.3 虚拟存储器的特征
? 多次性（ 虚拟存储器最重要的特征 ）
指一个作业被分成多次调入内存运行。
? 对换性
指允许在作业的运行过程中进行换进、换出。
? 虚拟性（ 实现虚拟存储器的主要目的 ）
指能够从逻辑上扩充内存容量。
三个特征中，虚拟性以多次性、对换性为基础，
而多次性、对换性必须建立在离散分配的基础上。
第四章 存 储 器 管 理
4.6 请求分页存储管理方式
是指在分页系统的基础上, 增加了请求调页
功能, 页面置换功能所形成的页式虚拟存储系统 。
第四章 存 储 器 管 理
页表项,页号、物理块号、状态位、访问位、修
改位、外存地址。
? 状态位：表示该页是在内存还是在外存；
? 访问位：根据访问位来决定淘汰哪页（由不同
的算法决定）；
? 修改位：查看此页是否在内存中被修改过；
? 外存地址：用于指出该页在外存上的地址，通
常是物理块号，供调入该页时参考。
页号 物理块号 状态位 外存地址访问位 修改位
4.6.1 请求分页中的硬件支持
1,页表机制
第四章 存 储 器 管 理
2,缺页中断机构
? 在地址映射过程中，在页表中发现所要访问的页
不在内存，则产生 缺页中断 。操作系统接到此中
断信号后，就调出缺页中断处理程序，根据页表
中给出的外存地址，准备将该页调入内存。
? 此时应将缺页的进程挂起（调页完成后唤醒）。
? 如果内存中有空闲块，则分配一个块，将要调入
的页装入该块，并修改页表中相应页表项目的状
态位及相应的物理块号。
? 若此时内存中没有空闲块，则要淘汰某页（若被
淘汰页在内存期间被修改过，则要将其写回外
存）。
第四章 存 储 器 管 理
缺页中断与一般中断的比较：
相同点：
缺页中断同一般中断都是中断，都需要保护现
场、中断处理、恢复现场。
不同点：
? 一般中断是一条指令完成后中断，缺页中断是
一条指令执行时中断；
? 一条指令执行时可能产生多个缺页中断。
例如一条指令可能访问多个内存地址，这些
地址在不同的页中。
第四章 存 储 器 管 理
将产生 6次缺页中断
例,COPYA TO B 页面
B：
A：
6
5
4
3
2
1
指令
copy A
TO B
第四章 存 储 器 管 理
缺页中断处理
保留 C P U 现场
从外存中找到缺页
内存满否？
选择一页换出
该页被修改否？
将该页写回外存
OS 命令 C P U 从外存读缺页
启动 I / O 硬件
将一页从外存换入内存
修改页表
否
是
是
否
页表项在快表中？
C P U 检索快表
访问页表
否
页在内存？
修改访问位和修改位
形成物理地址
地址变换结束
否
页号＞页表长度?
开始
程序请求访问一页
产生缺页中
断请求调页
修改快表
是
越界中断
是
是
3,地址变换机构
第四章 存 储 器 管 理
两种内存分配策略：
固定分配和可变分配。
两种置换策略：
全局置换和局部置换。
经过组合，得出三种适用的策略：
? 固定分配局部置换
? 可变分配全局置换
? 可变分配局部置换
4.6.2 内存分配策略和分配算法
1,物理块的分配策略
第四章 存 储 器 管 理
2,物理块分配算法
? 平均分配算法
? 按比例分配算法
? 考虑优先权的分配算法
第四章 存 储 器 管 理
? 请求调页 (demand paging)：只调入发生缺页时所
需的页面。
优点,容易实现；
缺点,对外存 I/O次数多，开销较大。
? 预调页 (prepaging)：在发生缺页需要调入某页时，
一次调入该页以及相邻的几个页。
优点,提高调页的 I/O效率；
缺点,基于预测，若调入的页在以后很少被访问，
则效率低。常用于程序装入时的调页。
4.6.3
1,何时调入页面 （有两种常用策略）
第四章 存 储 器 管 理
2,调入页面的来源
? 进程装入时，将其全部页面复制到对换区，以后
总是从对换区调入。执行时调入速度快，要求对
换区空间较大。
? 凡是未被修改的页面，都直接从文件区读入，而
被置换时不需调出；已被修改的页面，被置换时
需调出到对换区，以后从对换区调入。节省对换
区空间，用于缺少足够的对换区的系统。
将外存划分为两部分：文件区, 对换区 。 通常
对外存对换区的 I/O效率比文件区的高 。 关于调入页
面的来源, 这里有两种做法：
第四章 存 储 器 管 理
4.7 页面置换算法
? 把选择换出页面的算法称为 页面置换算法 。
? 应该把那些以后不再会访问的页面换出，或者
把那些停留较长时间而不会再访问的页面调出，
最终的目的是达到一个 较低的页面更换频率 。
第四章 存 储 器 管 理
几种常用置换算法：
? 最佳置换算法 (OPT,Optimal)
? 先进先出置换算法 (FIFO)
? 最近最久未使用置换算法 (LRU,Least Recently
Used)
? Clock置换算法
? 最少使用置换算法 (LFU,Least Frequently
Used)
? 页面缓冲算法 (PBA,Page Buffering Algorithm)
第四章 存 储 器 管 理
? Belady于 1966年提出的一种理论上的算法。
? 选择“未来不再使用的”或“在最长时间内不
再被访问的”页面被置换。
? 通常可以获得最低的缺页率。
? 这是一种理想情况，是实际执行中无法预知的，
因而不能实现。可用作性能评价的依据。
1,最佳 (Optimal)置换算法
4.7.1
第四章 存 储 器 管 理
假定系统为某进程分配了三个物理块,并考虑有
以下的页面号引用串,7,0,1,2,0,3,0,4，
2,3,0,3,2,1,2,0,1,7,0,1 。
7 0
7 7
0
1
7
0
1
2
2
0
1
0 3
2
0
3
0 4
2
4
3
2 3 0 3 2 1
2
0
1
2 0 1 7
7
0
1
0 1
2
0
3
利用最佳页面置换算法时的置换图：
例：
共发生 6次页面置换
▲ ▲ ▲ ▲ ▲ ▲
第四章 存 储 器 管 理
2,先进先出 (FIFO)页面置换算法
? 基本思想：总是先淘汰那些驻留在内存时间最长
的页面，即先进入内存的页面先被置换掉。理由
是：最先进入内存的页面不再被访问的可能性最
大。
? 引入指针将进入内存的页面按时间的先后次序链
成队列，新进入的页面从队尾入队，淘汰总是从
队列头进行。
第四章 存 储 器 管 理
7 0
7 7
0
1
7
0
1
2
2
0
1
0 3
2
3
1
0 4
4
3
0
2 3 0 3 2 1
0
1
3
2 0 1 7
7
0
2
0 1
2
3
0
4
2
0
4
2
3
0
2
3
0
1
2
7
1
2
7
0
1
1
例,（ 同前例 ）
利用 FIFO置换算法时的置换图：
共发生 12次页面置换
▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲
第四章 存 储 器 管 理
Belady现象,
? Belady现象：采用 FIFO算法时，如果对一个进
程未分配它所要求的全部页面，有时就会出现
分配的页面数增多，缺页率反而提高的异常现
象。
? 描述：一个进程 P要访问 M个页,OS分配 N个内
存页面给进程 P；对一个访问序列 S，发生缺页
次数为 PE(S,N)。当 N增大时,PE(S,N)时而增
大，时而减小。
? 原因,FIFO算法的置换特征与进程访问内存的
动态特征是矛盾的，即被置换的页面并不是进
程不会访问的。
第四章 存 储 器 管 理
Belady现象的例子：
进程 P有 5页程序。访问页的顺序为,1,2,3,4,1,2,5,
1,2,3,4,5。
(1) 如果在内存中分配 3个页面，则缺页情况如下：
12次访问中有缺页 9次；
FIFO 1 2 3 4 1 2 5 1 2 3 4 5
页 0 1 2 3 4 1 2 5 5 5 3 4 4
页 1 1 2 3 4 1 2 2 2 5 3 3
页 2 1 2 3 4 1 1 1 2 5 5
缺页 x x x x x x x √ √ x √x
第四章 存 储 器 管 理
(2) 如果在内存中分配 4个页面，则缺页情况如下,12次
访问中有缺页 10次；
FIFO 1 2 3 4 1 2 5 1 2 3 4 5
页 0 1 2 3 4 4 4 5 1 2 3 4 5
页 1 1 2 3 3 3 4 5 1 2 3 4
页 2 1 2 2 2 3 4 5 1 2 3
页 3 1 1 1 2 3 4 5 1 2
缺页 x x x x √ √ x x x x x x
第四章 存 储 器 管 理
? 选择内存中最近一段时间里较久未被访问的页
面予以淘汰。性能接近最佳置换算法。
? 根据程序局部性原理，那些刚被使用过的页面，
可能马上还要被使用，而在较长时间里未被使
用的页面，可能不会马上使用到。
? 由于需要记录页面使用时间的先后关系，硬件
开销太大。
4.7.2 最近最久未使用 (LRU)置换算法
1,LRU置换算法的描述
第四章 存 储 器 管 理
7 0
7 7
0
1
7
0
1
2
2
0
1
0 3
2
0
3
0 4
4
0
3
2 3 0 3 2 1
1
3
2
2 0 1 7
1
0
7
0 1
4
0
2
4
3
2
0
3
2
1
0
2
例,（ 同前例 ）
利用 LRU页面置换算法时的置换图：
共发生 9次页面置换
▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲
第四章 存 储 器 管 理
1)
为了记录某进程在内存中各页的使用情况, 须
为每个在内存中的页面配置一个移位寄存器, 可
表示为,
R = Rn-1Rn-2Rn-3 … R 2R1R0
2,LRU置换算法的硬件支持
当页面被访问时, 对应的寄存器的最左边位置 1；
每隔时间 t,将 r寄存器右移一位；发生缺页中断时,
找最小数值的 r寄存器对应的页面淘汰 。
第四章 存 储 器 管 理
某进程具有 8个页面时的 LRU访问情况
第四章 存 储 器 管 理
2) 栈
用栈保存当前使用页面时栈的变化情况
4
4
7
4
7
0
7
4
0
7
0
4
7
1
7
0
4
1
0
1
7
4
0
1
0
7
4
1
2
1
0
7
4
2
1
2
0
7
4
1
2
1
0
7
4
2
6
2
1
0
7
6
用栈来保存当前使用的各个页面的页面号, 当进
程访问某页面时, 将该页面的页面号从栈中移出, 压
入栈顶 。 因此栈顶始终是最新被访问页面的编号 。
第四章 存 储 器 管 理
? 每页有一个使用访问位, 将内存中的所有页面通
过链接指针链接成一个循环队列 。
? 若该页被访问则置访问位 =1。
4.7.3 Clock置换算法
也称最近未使用算法 (NRU,Not Recently Used)，
是一种最为流行, 低开销的 LRU(最近最久未使用算
法 )近似算法 。
1,简单的 Clock置换算法
第四章 存 储 器 管 理
简单 Clock置换算法的流程和示例
入口
查寻指针前进一步，
指向下一个表目
页面访问
位＝ 0?
选择该页面淘汰
是
返回
置页面访
问位＝ 0
否
替换
指针
块号 页号 访问位 指针
0
1
2 4 0
3
4 2 1
5
6 5 0
7 1 1
第四章 存 储 器 管 理
2,改进型 Clock置换算法
首选置换页面：既是未使用过的页面；又是未修
改的页面 。
由访问位 A和修改位 M可以组合成下面四种类型
的页面：
? 1类 (A=0,M=0)：表示该页最近既未被访问, 又未
被修改, 是最佳淘汰页 。
? 2类 (A=0,M=1)：表示该页最近未被访问, 但已被
修改, 并不是很好的淘汰页 。
? 3类 (A=1,M=0)：最近已被访问, 但未被修改, 该
页有可能再被访问 。
? 4类 (A=1,M=1)：最近已被访问且被修改, 该页可
能再被访问 。
第四章 存 储 器 管 理
(1) 从指针所指示的当前位置开始, 扫描循环队列,
寻找 A=0且 M=0的第一类页面, 将所遇到的第一个
页面作为所选中的淘汰页 。 在第一次扫描期间不改
变访问位 A。
(2) 如果第一步失败, 即查找一周后未遇到第一类页
面, 则开始第二轮扫描, 寻找 A=0且 M=1的第二类
页面, 将所遇到的第一个这类页面作为淘汰页 。 在
第二轮扫描期间, 将所有扫描过的页面的访问位都
置 0。
(3) 如果第二步也失败, 亦即未找到第二类页面, 则
将指针返回到开始的位置, 并将所有的访问位复 0。
然后重复第一步, 如果仍失败, 必要时再重复第二
步, 此时就一定能找到被淘汰的页 。
第四章 存 储 器 管 理
? 选择到当前时间为止被访问次数最少的页面被置
换。
? 为内存中每页设置一个移位寄存器，每次访问某
页时将该移位寄存器最高位置 1，每隔一定时间
右移一次。使用最少的页面即为 ∑ Ri最小的页。
（ 页面访问图同 LRU置换算法）
? 会出现的问题：不能真正反映页面的使用情况。
4.7.4 其它置换算法
1,最少使用 (LFU)置换算法
第四章 存 储 器 管 理
2,页面缓冲算法 (PBA)
? 它是对 FIFO算法的发展，通过被置换页面的缓
冲，有机会找回刚被置换的页面；
? 被置换页面的选择和处理：用 FIFO算法选择被
置换页，把被置换的页面放入两个链表之一：
----如果页面未被修改，就将其归入到空闲页面
链表的末尾；
----否则将其归入到已修改页面链表。
第四章 存 储 器 管 理
? 需要调入新的物理页面时，将新页面内容读入
到空闲页面链表的第一项所指的页面，然后将
第一项删除。
? 空闲页面和已修改页面，仍停留在内存中一段
时间，如果这些页面被再次访问，只需较小开
销，而被访问的页面可以返还作为进程的内存
页。
? 当已修改页面达到一定数目后，再将它们一起
调出到外存，然后将它们归入空闲页面链表，
这样能大大减少 I/O操作的次数。
第四章 存 储 器 管 理
缺页率的计算：
缺页率 =缺页次数 /访问串的访问次数
第四章 存 储 器 管 理
思考题：
某程序在内存中分配 3块内存, 初始为空, 访
问页的走向为 2,3,2,1,5,2,4,5,3,2，
5,2,用 FIFO和 LRU算法分别计算缺页次数和
缺页率 。
第四章 存 储 器 管 理
FIFO 2 3 2 1 5 2 4 5 3 2 5 2
页 1 2 3 3 1 5 2 4 4 3 3 5 2
页 2 2 2 3 1 5 2 2 4 4 3 5
页 3 2 3 1 5 5 2 2 4 3
x x ? x x x x ? x ? x x
共缺页中断 9次，缺页率,9/12=0.75。
解：
第四章 存 储 器 管 理
LRU 2 3 2 1 5 2 4 5 3 2 5 2
页 1 2 3 2 1 5 2 4 5 3 2 5 2
页 2 2 3 2 1 5 2 4 5 3 2 5
页 3 3 2 1 5 2 4 5 3 3
x x ? x x ? x ? x x ? ?
共缺页中断 7次，缺页率,7/12。
第四章 存 储 器 管 理
4.8 请求分段存储管理方式
为了能实现虚拟存储, 段式逻辑地址空间中的
程序段在运行时并不全部装入内存, 而是如同请
求式分页存储管理, 首先调入一个或若干个程序
段运行, 在运行过程中调用到哪段时, 就根据该
段长度在内存分配一个连续的分区给它使用 。 若
内存中没有足够大的空闲分区, 则考虑进行段的
紧凑或将某段或某些段淘汰出去 。 相应于请求式
分页存储管理, 这种存储管理技术称为 请求分段
存储管理方式 。
第四章 存 储 器 管 理
1.
外存
始址
增补
位
存在
位 P
修改
位 M
访问字
段 A
存取
方式
段的
基址段长段号
4.8.1 请求分段中的硬件支持
第四章 存 储 器 管 理
2,缺段中断机构
? 当发现要访问的段尚未调入内存时, 便由缺段
中断机构产生以缺段中断信号, 进入缺段中断
处理程序, 将所需的段调入内存 。
? 由于段是程序的逻辑单位, 因此不会出现一条
指令出现在两个分段中, 或一组相关信息被分
割在两个段中的情况 。
? 但是由于段不是定长的, 因此处理过程比缺页
中断复杂 。
第四章 存 储 器 管 理虚段 S不在内存
阻塞请求进程
内存中有合适
的空闲区吗？
从外存读入段 S
修改段表及内存空区链
唤醒请求进程
返回
空区容量总
和能否满足？
空区拼接, 以形成
一个合适的空区
淘汰一个或几个实段
以形成一个合适空区
否
否
是
是
请求分段系统中的
中断处理过程
第四章 存 储 器 管 理
? 是在分段系统地址变换机构的基础上形成的 。
? 若发现要访问的段不在内存, 首先必须将所缺
的段调入内存, 修改段表, 然后才能利用段表
进行地址变换 。
? 增加了一些功能, 如缺段中断的请求, 及相应
的处理过程等 。
3,地址变换机构
第四章 存 储 器 管 理访问 [s][w]
w≤ 段长?
符合存取方式?
段 S在主存?
修改访问字段,如写
访问,置修改位 ＝ 1
形成访问主存地址
(A)＝ (主存始址 )
＋ (位移量 w)
返回
分段越界
中断处理
分段保护
中断处理
缺段中
断处理
是
是
是
否
否
否
请
求
分
段
系
统
的
地
址
变
换
过
程
第四章 存 储 器 管 理4.8.2 分段的共享与保护
1,共享段表
为了实现分段共享, 在系统中配置一张共享段表,
每个共享段占有一个表项 。 表项中记录了共享段的段
号, 段长, 内存始址, 存在位等信息, 并记录了使用
此共享段的所有进程的情况 。
段名 段长 内存始址 状态 外存始址
共享进程计数 count
状态 进程名 进程号 段号 存取控制
… … … … ……
共享段表
第四章 存 储 器 管 理
2,共享段的分配与回收
1)
? 第一次请求调入时：把共享段调入内存一物理区,
修改请求调入进程的段表的相应项, 还要在共享
段表中增加一表项, 填写相关数据, 把 count置 1。
? 之后, 当又有其它进程需要调用该共享段时：由
于该共享段已被调入内存, 故此时无须再为该段
分配内存, 而只需在调用进程的段表中, 增加一
表项, 填写该共享段的物理地址；在共享段的段
表中, 填上调用进程的进程名, 存取控制等, 再
执行 count∶ =count+1操作, 以表明有两个进程
共享该段 。
第四章 存 储 器 管 理
2) 共享段的回收
? 当进程不需要该段, 应将该段释放, 撤销在段
表中共享段对应的表项, 执行 count,=count-1操
作 。
? 若结果为 0,则系统回收该共享段, 以及取消共
享段表中所对应的表项, 表明此时已没有进程使
用该段 。
? 否则 (减 1结果不为 0),则只是取消调用者进程
在共享段表中的有关记录 。
第四章 存 储 器 管 理
3,分段保护
1) 越界检查
2) 存取控制检查
(1)只读 (2) 只执行 (3) 读 /写
3) 环保护机构
(1)一个程序可以访问驻留在相同环或较低特权
环中的数据。
(2)一个程序可以调用驻留在相同环或较高特权
环中的服务。
第四章 存 储 器 管 理
环保护机构
调用 返回
调用
返回
环 0
环 1
环 2
(a) 程序间的控制传输
数据访问
环 0
环 1
环 2
(b) 数据访问
数据访问
