第四章 存 储 器 管 理
第四章 存储器管理
4.1 程序的装入和链接
4.2 连续分配方式
4.3 基本分页存储管理方式
4.4 基本分段存储管理方式
4.5 虚拟存储器的基本概念
4.6 请求分页存储管理方式
4.7 页面置换算法
4.8 请求分段存储管理方式
第四章 存 储 器 管 理
4.1 程序的装入和链接
图 4-1 对用户程序的处理步骤
库
链接
程序
装入模块
装入
程序
编译程序产
生的目标模
块
第一步 第二步 第三步
内存
?
第四章 存 储 器 管 理
4.1.1 程序的装入
1,绝对装入方式 (Absolute Loading Mode)
程序中所使用的绝对地址, 既可在编译或汇编时给出,
也可由程序员直接赋予 。 但在由程序员直接给出绝对地址
时, 不仅要求程序员熟悉内存的使用情况, 而且一旦程序
或数据被修改后, 可能要改变程序中的所有地址 。 因此,
通常是宁可在程序中采用符号地址, 然后在编译或汇编时,
再将这些符号地址转换为绝对地址 。
第四章 存 储 器 管 理
2,可重定位装入方式 (Relocation Loading Mode)
图 4-2 作业装入内存时的情况
L O A D 1,2 5 0 0
3 6 5
L O A D 1,2 5 0 0
3 6 5
1 0 0 0 0
1 1 0 0 0
1 2 5 0 0
1 5 0 0 0
5 0 0 0
2 5 0 0
1 0 0 0
0
作业地址空间
内存空间
第四章 存 储 器 管 理
3,动态运行时装入方式 (Denamle Run-time Loading)
动态运行时的装入程序, 在把装入模块装入内存后,
并不立即把装入模块中的相对地址转换为绝对地址, 而
是把这种地址转换推迟到程序真正要执行时才进行 。 因
此, 装入内存后的所有地址都仍是相对地址 。
第四章 存 储 器 管 理
4.1.2 程序的链接
1,静态链接方式 (Static Linking)
图 4-3 程序链接示意图
模块 A
C A L L B ；
R e t u r n ；
0
L － 1
模块 B
C A L L C ；
R e t u r n ；
0
M － 1
模块 C
R e t u r n ；
0
N － 1
0
模块 A
J S R, L,
R e t u r n ；L － 1
模块 B
J S R, L ＋ M”
R e t u r n ；
L
L ＋ M － 1
L ＋ M
L ＋ M ＋ N － 1
模块 C
R e t u r n ；
( a ) 目标模块 ( b ) 装入模块
第四章 存 储 器 管 理
在将这几个目标模块装配成一个装入模块时, 须解
决以下两个问题：
(1) 对相对地址进行修改 。
(2) 变换外部调用符号。
第四章 存 储 器 管 理
2,装入时动态链接 (Load time Dynamic Linking)
装入时动态链接方式有以下优点：
(1) 便于修改和更新。
(2) 便于实现对目标模块的共享。
第四章 存 储 器 管 理
3,运行时动态链接 (Run-time Dynamic Linking)
近几年流行起来的运行时动态链接方式, 是对上述在
装入时链接方式的一种改进 。 这种链接方式是将对某些模
块的链接推迟到执行时才执行, 亦即, 在执行过程中, 当
发现一个被调用模块尚未装入内存时, 立即由 OS去找到该
模块并将之装入内存, 把它链接到调用者模块上 。 凡在执
行过程中未被用到的目标模块, 都不会被调入内存和被链
接到装入模块上, 这样不仅可加快程序的装入过程, 而且
可节省大量的内存空间 。
第四章 存 储 器 管 理
4.2 连续分配方式
4.2.1 单一连续分配
这是最简单的一种存储管理方式, 但只能用于单用户,
单任务的操作系统中 。 采用这种存储管理方式时, 可把内
存分为系统区和用户区两部分, 系统区仅提供给 OS使用,
通常是放在内存的低址部分；用户区是指除系统区以外的
全部内存空间, 提供给用户使用 。
第四章 存 储 器 管 理
4.2.2 固定分区分配
1,划分分区的方法
(1) 分区大小相等,即使所有的内存分区大小相等。
(2) 分区大小不等。
第四章 存 储 器 管 理
2,内存分配
图 4-4 固定分区使用表
第四章 存 储 器 管 理
4.2.3 动态分区分配
1,分区分配中的数据结构
(1) 空闲分区表。
(2) 空闲分区链。
图 4-5 空闲链结构
前
向
指
针
N
＋
2
0
N 个字节可用
后
向
指
针
N
＋
2
0
第四章 存 储 器 管 理
2,分区分配算法
(1) 首次适应算法 FF。
(2) 循环首次适应算法，该算法是由首次适应算法演变而成的。
(3) 最佳适应算法。
第四章 存 储 器 管 理
3,分区分配操作
1) 分配内存
从头开始查表
检索完否？
m, s i z e ＞ u, s i z e?
m, s i z e － u, s iz e ≤ s i z e?
从该分区中划出
u, s i z e 大小的分区
将该分区分配给请求者修
改有关数据结构
返回
返回
继续检索下一个表项
将该分区从链中移出
Y
N
N
Y
Y
N
图
4-
6
内
存
分
配
流
程
第四章 存 储 器 管 理
2) 回收内存
图 4-7 内存回收时的情况
第四章 存 储 器 管 理
4.2.4
1,
图 4-8 紧凑的示意
操作系统
用户程序 1
用户程序 3
1 0 K B
3 0 K B
用户程序 6
1 4 K B
用户程序 9
2 6 K B
操作系统
用户程序 1
用户程序 3
用户程序 6
用户程序 9
8 0 K B
( a ) 紧凑前 ( b ) 紧凑后
第四章 存 储 器 管 理
2,
图 4-9 动态重定位示意图
L O A D 1,2 5 0 0
3 6 5
0
1 0 0
2 5 0 0
5 0 0 0
2 5 0 0
相对地址
1 0 0 0 0
重定位寄存器
＋
L O A D 1,2 5 0 0
3 6 5
1 0 0 0 0
1 0 1 0 0
1 2 5 0 0
1 5 0 0 0
作业 J
处理机一侧 存储器一侧
主存
第四章 存 储 器 管 理
3,动态重定位分区分配算法
图 4-10 动态分区分配算法流程图
请求分配
u, s i z e 分区
检索空闲分区链( 表)
找到大于 u, s i z e
的可用区否?
按动态分区方式
进行分配
修改有关的
数据结构
返回分区号
及首批
空闲分区
总和≥ u, s i z e?
进行紧凑形
成连续空闲区
修改有关的
数据结构
否
是
无法分配
返回
否
第四章 存 储 器 管 理
4.2.5 对换 (Swapping)
1,对换的引入
所谓, 对换,, 是指把内存中暂时不能运行的进程或
者暂时不用的程序和数据, 调出到外存上, 以便腾出足够
的内存空间, 再把已具备运行条件的进程或进程所需要的
程序和数据, 调入内存 。 对换是提高内存利用率的有效措
施 。
第四章 存 储 器 管 理
2,对换空间的管理
为了能对对换区中的空闲盘块进行管理, 在系统中应
配置相应的数据结构, 以记录外存的使用情况 。 其形式与
内存在动态分区分配方式中所用数据结构相似, 即同样可
以用空闲分区表或空闲分区链 。 在空闲分区表中的每个表
目中应包含两项, 即对换区的首址及其大小, 它们的单位
是盘块号和盘块数 。
第四章 存 储 器 管 理
3,进程的换出与换入
(1) 进程的换出 。
每当一进程由于创建子进程而需要更多的内存空间,
但又无足够的内存空间等情况发生时, 系统应将某进程换
出 。 其过程是：系统首先选择处于阻塞状态且优先级最低
的进程作为换出进程, 然后启动盘块, 将该进程的程序和
数据传送到磁盘的对换区上 。 若传送过程未出现错误, 便
可回收该进程所占用的内存空间, 并对该进程的进程控制
块做相应的修改 。
第四章 存 储 器 管 理
(2) 进程的换入 。
系统应定时地查看所有进程的状态, 从中找出, 就绪,
状态但已换出的进程, 将其中换出时间 (换出到磁盘上 )最
久的进程作为换入进程, 将之换入, 直至已无可换入的进
程或无可换出的进程为止 。
第四章 存 储 器 管 理
4.3 基本分页存储管理方式
4.3.1 页面与页表
1,页面
1)
分页存储管理, 是将一个进程的逻辑地址空间分成若干个
大小相等的片, 称为页面或页, 并为各页加以编号, 从 0开始,
如第 0页, 第 1页等 。 相应地, 也把内存空间分成与页面相同大
小的若干个存储块, 称为 (物理 )块或页框 (frame),也同样为它
们加以编号, 如 0＃ 块, 1＃ 块等等 。 在为进程分配内存时, 以
块为单位将进程中的若干个页分别装入到多个可以不相邻接的
物理块中 。 由于进程的最后一页经常装不满一块而形成了不可
利用的碎片, 称之为, 页内碎片, 。
第四章 存 储 器 管 理
2)
在分页系统中的页面其大小应适中 。 页面若太小, 一方
面虽然可使内存碎片减小, 从而减少了内存碎片的总空间,
有利于提高内存利用率, 但另一方面也会使每个进程占用较
多的页面, 从而导致进程的页表过长, 占用大量内存； 此
外, 还会降低页面换进换出的效率 。 然而, 如果选择的页面
较大, 虽然可以减少页表的长度, 提高页面换进换出的速度,
但却又会使页内碎片增大 。 因此, 页面的大小应选择得适中,
且页面大小应是 2的幂, 通常为 512 B~8 KB。
第四章 存 储 器 管 理
2,地址结构
分页地址中的地址结构如下：
页号 P 位移量 W
31 12 11 0
对某特定机器, 其地址结构是一定的 。 若给定一个逻
辑地址空间中的地址为 A,页面的大小为 L,则页号 P和页
内地址 d可按下式求得：
M O D LAd
L
A
IN TP
][?
??
?
??
?
?
第四章 存 储 器 管 理
3,页表
图 4-11 页表的作用
用户程序
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
第四章 存 储 器 管 理
4.3.2 地址变换机构
1,基本的地址变换机构
图 4-12 分页系统的地址变换机构
页表寄存器
页表始址 页表长度 ＞ 页号 ( 3 ) 页 内地址
＋
逻辑地址L
越界中断
1
块号
b
页表
页号
0
1
2
物理地址
3
第四章 存 储 器 管 理
2,
图 4-13 具有快表的地址变换机构
页表寄存器
页表始址 页表长度 ＞ 页号 页 内地 址
＋
逻辑地址L
越界中断
块号
b
页表
页号 页号
输
入
寄
存
器
块号
b
b
快表
d
物理地址
第四章 存 储 器 管 理
4.3.3 两级和多级页表
现代的大多数计算机系统, 都支持非常大的逻辑地址空
间 (232~264)。 在这样的环境下, 页表就变得非常大, 要占用相
当大的内存空间 。 例如, 对于一个具有 32位逻辑地址空间的
分页系统, 规定页面大小为 4 KB即 212 B,则在每个进程页表
中的页表项可达 1兆个之多 。 又因为每个页表项占用一个字节,
故每个进程仅仅其页表就要占用 4 KB的内存空间, 而且还要
求是连续的 。 可以采用这样两个方法来解决这一问题,① 采
用离散分配方式来解决难以找到一块连续的大内存空间的问
题,② 只将当前需要的部分页表项调入内存, 其余的页表项
仍驻留在磁盘上, 需要时再调入 。
第四章 存 储 器 管 理
1,两级页表 (Two-Level Page Table)
逻辑地址结构可描述如下：
第四章 存 储 器 管 理
图 4-14 两级页表结构
1 0 1 1
1 0 7 8
0
1
2
1 7 4 2n
第 0 页页表
1
4
6
…
0
1
2
…
1 0 2 3
第 1 页页表
1 1 4
1 1 5
0
1
…
1 0 2 3
外部页表
0
1
2
3
4
5
6
7
…
…
1 1 4
1 1 5
1 4 6 8
第 n 页页表
1 4 6 8
0
1
2
…
1 0 2 3
内存空间
第四章 存 储 器 管 理
图 4-15 具有两级页表的地址变换机构
外部页号
P
1
P
2
外部页内地址 页内地址
d逻辑地址
＋外部页表寄存器
外部页表
＋ db
页表页表
物理地址? ?
第四章 存 储 器 管 理
2,多级页表
对于 32位的机器, 采用两级页表结构是合适的；但对于
64位的机器, 如果页面大小仍采用 4 KB即 212 B,那么还剩
下 52位, 假定仍按物理块的大小 (212位 )来划分页表, 则将
余下的 42位用于外层页号 。 此时在外层页表中可能有 4096
G个页表项, 要占用 16384 GB的连续内存空间 。 必须采用
多级页表, 将外层页表再进行分页, 也是将各分页离散地
装入到不相邻接的物理块中, 再利用第 2级的外层页表来映
射它们之间的关系 。
对于 64位的计算机, 如果要求它能支持 2６４ (=1844744
TB)规模的物理存储空间, 则即使是采用三级页表结构也是
难以办到的；而在当前的实际应用中也无此必要 。
第四章 存 储 器 管 理
4.4 基本分段存储管理方式
4.4.1 分段存储管理方式的引入
引入分段存储管理方式, 主要是为了满足用户和程序员
1)
2) 信息共享
3) 信息保护
4)
5) 动态链接
第四章 存 储 器 管 理
4.4.2 分段系统的基本原理
1,分段
分段地址中的地址具有如下结构：
段号 段内地址
31 16 15 0
2,
第四章 存 储 器 管 理
图 4-16 利用段表实现地址映射
作业空间
( M A I N ) ＝ 0
0
3 0 K
( X ) ＝ 1
0
2 0 K
( D ) ＝ 2
0
1 5 K
( S ) ＝ 3
0
1 0 K
3 0 K
2 0 K
1 5 K
1 0 K
4 0 K
8 0 K
1 2 0 K
1 5 0 K
段长 基址段号
( M A I N ) ＝ 0
3 0 K
( X ) ＝ 1
2 0 K
( D ) ＝ 2
1 5 K
( S ) ＝ 3
1 0 K
0
4 0 K
8 0 K
1 2 0 K
1 5 0 K
段表
内存空间
0
1
2
3
第四章 存 储 器 管 理
控制寄存器
段表始址 段表长度 ＞ 2 1 0 0
＋
段号 S
越界
1 K
段长
6 0 0
段号
0
1
2
3
6 K
4 K
5 0 0
2 0 0
8 K
9 2 0 0
基址
位移量 W
＋
8 2 9 2
8K
8 2 9 2
8 6 9 2
主存
物理地址
有效地址
图 4-17 分段系统的地址变换过程
3,地址变换机构
第四章 存 储 器 管 理
4,
(1) 页是信息的物理单位, 分页是为实现离散分配方
式, 以消减内存的外零头, 提高内存的利用率 。 或者说,
分页仅仅是由于系统管理的需要而不是用户的需要 。 段则
是信息的逻辑单位, 它含有一组其意义相对完整的信息 。
分段的目的是为了能更好地满足用户的需要 。
第四章 存 储 器 管 理
(2) 页的大小固定且由系统决定, 由系统把逻辑地址划
分为页号和页内地址两部分, 是由机器硬件实现的, 因而
在系统中只能有一种大小的页面；而段的长度却不固定,
决定于用户所编写的程序, 通常由编译程序在对源程序进
行编译时, 根据信息的性质来划分 。
(3) 分页的作业地址空间是一维的, 即单一的线性地
址空间, 程序员只需利用一个记忆符, 即可表示一个地址；
而分段的作业地址空间则是二维的, 程序员在标识一个地
址时, 既需给出段名, 又需给出段内地址 。
第四章 存 储 器 管 理
4.4.3 信息共享
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
页表
图
4-
18
分
页
系
统
中
共
享edit
or
的
示
意
图
第四章 存 储 器 管 理
图 4-19 分段系统中共享 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,基本原理
图 4-20 作业地址空间和地址结构
0
4K
8K
1 2 K
1 5 K
1 6 K
子程序段
0
4K
8K
数据段
0
4K
8K
1 0 K
1 2 K
( a )
段号 ( S ) 段内页号 ( P ) 段内地址 ( W )
( b )
主程序段
第四章 存 储 器 管 理
图 4-21 利用段表和页表实现地址映射
段号 状态 页表大小 页表始址
0 1
1 1
2 1
3 0
4 1
页号 状态 存储块#
0 1
1 1
2 1
3 0
4 1
操作系统
主存
页表
段表
段表大小 段表始址
段表寄存器
第四章 存 储 器 管 理
2,地址变换过程
图 4-22 段页式系统中的地址变换机构
段表寄存器
段表始址 段表长度 ＞ 段号 S 页号 P
＋
段超长
段表
0
1
2
3
＋
页内地址
页表
0
1
2
3
b 块号 b 块内地址
页表始址页表长度
第四章 存 储 器 管 理
4.5 虚拟存储器的基本概念
4.5.1
1,
(1) 一次性。
(2) 驻留性。
第四章 存 储 器 管 理
2,
早在 1968年, Denning.P就曾指出：
(1) 程序执行时, 除了少部分的转移和过程调用指令
外, 在大多数情况下仍是顺序执行的 。
(2) 过程调用将会使程序的执行轨迹由一部分区域转至
另一部分区域, 但经研究看出, 过程调用的深度在大多数
情况下都不超过 5。
(3) 程序中存在许多循环结构, 这些虽然只由少数指
令构成, 但是它们将多次执行 。
(4) 程序中还包括许多对数据结构的处理, 如对数组
进行操作, 它们往往都局限于很小的范围内 。
第四章 存 储 器 管 理
(1) 时间局限性 。 如果程序中的某条指令一旦执行,
则不久以后该指令可能再次执行；如果某数据被访问过,
则不久以后该数据可能再次被访问 。 产生时间局限性的
典型原因, 是由于在程序中存在着大量的循环操作 。
(2) 空间局限性 。 一旦程序访问了某个存储单元, 在
不久之后, 其附近的存储单元也将被访问, 即程序在一
段时间内所访问的地址, 可能集中在一定的范围之内,
其典型情况便是程序的顺序执行 。
第四章 存 储 器 管 理
3,虚拟存储器定义
所谓虚拟存储器, 是指具有请求调入功能和置换功能,
能从逻辑上对内存容量加以扩充的一种存储器系统 。 其逻
辑容量由内存容量和外存容量之和所决定, 其运行速度接
近于内存速度, 而每位的成本却又接近于外存 。 可见, 虚
拟存储技术是一种性能非常优越的存储器管理技术, 故被
广泛地应用于大, 中, 小型机器和微型机中 。
第四章 存 储 器 管 理
4.5.2 虚拟存储器的实现方法
1,分页请求系统
(1) 硬件支持。
① 请求分页的页表机制, 它是在纯分页的页表机制上增
加若干项而形成的, 作为请求分页的数据结构； ② 缺页中断
机构, 即每当用户程序要访问的页面尚未调入内存时 便产生
一缺页中断, 以请求 OS将所缺的页调入内存； ③ 地址变换
机构, 它同样是在纯分页地址变换机构的基础上发展形成的 。
(2) 实现请求分页的软件。
第四章 存 储 器 管 理
4.5.3 虚拟存储器的特征
1,多次性
2,对换性
3,虚拟性
第四章 存 储 器 管 理
4.6 请求分页存储管理方式
4.6.1 请求分页中的硬件支持
1,页表机制
页号 物理块号 状态位 P 访问字段 A 修改位 M 外存地址
第四章 存 储 器 管 理
2,缺页中断机构
图 4-23 涉及 6次缺页中断的指令
页面
B,
A,
6
5
4
3
2
1
指令
c o p y A
T O B
第四章 存 储 器 管 理
3,地址变换机构
缺页中断处理
保留 C P U 现场
从外存中找到缺页
内存满否？
选择一页换出
该页被修改否？
将该页写回外存
OS 命令 C P U 从外存读缺页
启动 I / O 硬件
将一页从外存换入内存
修改页表
否
是
是
否
页表项在快表中？
C P U 检索快表
访问页表
否
页在内存？
修改访问位和修改位
形成物理地址
地址变换结束
否
页号＞页表长度?
开始
程序请求访问一页
产生缺页中
断请求调页
修改快表
是
越界中断
是
是
图
4-
24
请
求
分
页
中
的
地
址
变
换
过
程
第四章 存 储 器 管 理
4.6.2 内存分配策略和分配算法
1,最小物理块数的确定
是指能保证进程正常运行所需的最小物理块数 。 当系统为
进程分配的物理块数少于此值时, 进程将无法运行 。 进程应获
得的最少物理块数与计算机的硬件结构有关, 取决于指令的格
式, 功能和寻址方式 。 对于某些简单的机器, 若是单地址指令
且采用直接寻址方式, 则所需的最少物理块数为 2。 其中, 一块
是用于存放指令的页面, 另一块则是用于存放数据的页面 。 如
果该机器允许间接寻址时, 则至少要求有三个物理块 。 对于某
些功能较强的机器, 其指令长度可能是两个或多于两个字节,
因而其指令本身有可能跨两个页面, 且源地址和目标地址所涉
及的区域也都可能跨两个页面 。
第四章 存 储 器 管 理
2,物理块的分配策略
在请求分页系统中, 可采取两种内存分配策略, 即固定
和可变分配策略 。 在进行置换时, 也可采取两种策略, 即全
局置换和局部置换 。 于是可组合出以下三种适用的策略 。
1) 固定分配局部置换 (Fixed Allocation,Local
Replacement)
2) 可变分配全局置换 (Variable Allocation,Global
Replacement)
3) 可变分配局部置换 (Variable Allocation,Local
Replacemen
第四章 存 储 器 管 理
3,物理块分配算法
1)
这是将系统中所有可供分配的物理块, 平均分配给各个
进程 。 例如, 当系统中有 100个物理块, 有 5个进程在运行时,
每个进程可分得 20个物理块 。 这种方式貌似公平, 但实际上
是不公平的, 因为它未考虑到各进程本身的大小 。 如有一个
进程其大小为 200页, 只分配给它 20个块, 这样, 它必然会
有很高的缺页率；而另一个进程只有 10页, 却有 10个物理块
闲置未用 。
第四章 存 储 器 管 理
2)
这是根据进程的大小按比例分配物理块的算法 。 如果
系统中共有 n个进程, 每个进程的页面数为 Si,则系统中各
进程页面数的总和为：
又假定系统中可用的物理块总数为 m,则每个进程所能分
到的物理块数为 bi,将有：
b应该取整, 它必须大于最小物理块数 。
?
?
?
n
i
iSS
1
mSSb ii ??
第四章 存 储 器 管 理
3)
在实际应用中, 为了照顾到重要的, 紧迫的作业能尽
快地完成, 应为它分配较多的内存空间 。 通常采取的方法
是把内存中可供分配的所有物理块分成两部分：一部分按
比例地分配给各进程；另一部分则根据各进程的优先权,
适当地增加其相应份额后, 分配给各进程 。 在有的系统中,
如重要的实时控制系统, 则可能是完全按优先权来为各进
程分配其物理块的 。
第四章 存 储 器 管 理
4.6.3
1,何时调入页面
1)
2) 请求调页策略
第四章 存 储 器 管 理
2,从何处调入页面
在请求分页系统中的外存分为两部分：用于存放文件的
文件区和用于存放对换页面的对换区 。 通常, 由于对换区是
采用连续分配方式, 而事件是采用离散分配方式, 故对换区
的磁盘 I/O速度比文件区的高 。 这样, 每当发生缺页请求时,
系统应从何处将缺页调入内存,
(1) 系统拥有足够的对换区空间, 这时可以全部从对换
区调入所需页面, 以提高调页速度 。 为此, 在进程运行前,
便须将与该进程有关的文件, 从文件区拷贝到对换区 。
第四章 存 储 器 管 理
(2) 系统缺少足够的对换区空间, 这时凡是不会被修改
的文件, 都直接从文件区调入；而当换出这些页面时, 由于
它们未被修改而不必再将它们换出, 以后再调入时, 仍从文
件区直接调入 。 但对于那些可能被修改的部分, 在将它们换
出时, 便须调到对换区, 以后需要时, 再从对换区调入 。
(3) UNIX方式 。 由于与进程有关的文件都放在文件区,
故凡是未运行过的页面, 都应从文件区调入 。 而对于曾经运
行过但又被换出的页面, 由于是被放在对换区, 因此在下次
调入时, 应从对换区调入 。 由于 UNIX系统允许页面共享,
因此, 某进程所请求的页面有可能已被其它进程调入内存,
此时也就无须再从对换区调入 。
第四章 存 储 器 管 理
3,页面调入过程
每当程序所要访问的页面未在内存时, 便向 CPU发出一
缺页中断, 中断处理程序首先保留 CPU环境, 分析中断原因
后, 转入缺页中断处理程序 。 该程序通过查找页表, 得到该
页在外存的物理块后, 如果此时内存能容纳新页, 则启动磁
盘 I/O将所缺之页调入内存, 然后修改页表 。 如果内存已满,
则须先按照某种置换算法从内存中选出一页准备换出；如果
该页未被修改过, 可不必将该页写回磁盘；但如果此页已被
修改, 则必须将它写回磁盘, 然后再把所缺的页调入内存,
并修改页表中的相应表项, 置其存在位为, 1”,并将此页表
项写入快表中 。 在缺页调入内存后, 利用修改后的页表, 去
形成所要访问数据的物理地址, 再去访问内存数据 。
第四章 存 储 器 管 理
4.7 页面置换算法
4.7.1
1,最佳 (Optimal)
最佳置换算法是由 Belady于 1966年提出的一种理论上
的算法 。 其所选择的被淘汰页面, 将是以后永不使用的,
或许是在最长 (未来 )时间内不再被访问的页面 。 采用最佳
置换算法, 通常可保证获得最低的缺页率 。
第四章 存 储 器 管 理
假定系统为某进程分配了三个物理块, 并考虑有以下
7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1
进程运行时, 先将 7,0,1三个页面装入内存 。 以后,
当进程要访问页面 2时, 将会产生缺页中断 。 此时 OS根据
最佳置换算法, 将选择页面 7予以淘汰 。
引用率
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
图 4-25 利用最佳页面置换算法时的置换图
第四章 存 储 器 管 理
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
图 4-26 利用 FIFO置换算法时的置换图
第四章 存 储 器 管 理
4.7.2 最近最久未使用 (LRU)置换算法
1,LRU(Least Recently Used)置换算法的描述
图 4-27 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
第四章 存 储 器 管 理
2,LRU置换算法的硬件支持
1)
为了记录某进程在内存中各页的使用情况, 须为每个
在内存中的页面配置一个移位寄存器, 可表示为
R=Rn-1Rn-2Rn-3 … R 2R1R0
第四章 存 储 器 管 理
图 4-28 某进程具有 8个页面时的 LRU访问情况
第四章 存 储 器 管 理
2) 栈
图 4-29 用栈保存当前使用页面时栈的变化情况
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
第四章 存 储 器 管 理
4.7.3 Clock置换算法
1,简单的 Clock置换算法
图 4-30 简单 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。 然后重复第
一步, 如果仍失败, 必要时再重复第二步, 此时就一定能找
到被淘汰的页 。
第四章 存 储 器 管 理
4.7.4 其它置换算法
1,最少使用 (LFU,Least Frequently Used)置换算法
2,页面缓冲算法 (PBA,Page Buffering Algorithm)
第四章 存 储 器 管 理
4.8 请求分段存储管理方式
4.8.1 请求分段中的硬件支持
1,
段名 段长 段的
基址
存取
方式
访问
字段 A
修改
位 M
存在
位 P
增补
位
外存
始址
第四章 存 储 器 管 理
在段表项中, 除了段名 (号 ),段长, 段在内存中的起
始地址外,
(1) 存取方式。
(2) 访问字段 A。
(3) 修改位 M。
(4) 存在位 P。
(5) 增补位。
(6) 外存始址。
第四章 存 储 器 管 理
2,缺段中断机构
虚段 S 不在内存
阻塞请求进程
内存中有合适
的空闲区吗？
从外存读入段 S
修改段表及内存空区链
唤醒请求进程
返回
空区容量总
和能否满足？
空区拼接，以形成
一个合适的空区
淘汰一个或几个实段，
以形成一个合适空区
否
否
是
是
图 4-31 请求分段系统中的中断处理过程
第四章 存 储 器 管 理
3,地址变换机构
访问 [ s ] [ w ]
w≤ 段长?
符合存取方式?
段 S 在主存?
修改访问字段,如写
访问,置修改位 ＝ 1
形成访问主存地址
( A ) ＝ ( 主存始址 )
＋ ( 位移量 w)
返回
分段越界
中断处理
分段保护
中断处理
缺段中
断处理
是
是
是
否
否
否
图
4-
32
请
求
分
段
系
统
的
地
址
变
换
过
程
第四章 存 储 器 管 理
4.8.2 分段的共享与保护
1,共享段表
图 4-33 共享段表项
段名 段长 内存始址 状态 外存始址
共享进程计数 c o u n t
状态 进程名 进程号 段号 存取控制
? ? ? ? ?
?
共享段表
第四章 存 储 器 管 理
2,共享段的分配与回收
1)
在为共享段分配内存时, 对第一个请求使用该共享段的进
程, 由系统为该共享段分配一物理区, 再把共享段调入该区,
同时将该区的始址填入请求进程的段表的相应项中, 还须在共
享段表中增加一表项, 填写有关数据, 把 count置为 1；之后,
当又有其它进程需要调用该共享段时, 由于该共享段已被调入
内存, 故此时无须再为该段分配内存, 而只需在调用进程的段
表中, 增加一表项, 填写该共享段的物理地址；在共享段的段
表中, 填上调用进程的进程名, 存取控制等, 再执行
count∶ =count+1操作, 以表明有两个进程共享该段 。
第四章 存 储 器 管 理
2)
当共享此段的某进程不再需要该段时, 应将该段释放,
包括撤在该进程段表中共享段所对应的表项, 以及执行
count∶ = count-1操作 。 若结果为 0,则须由系统回收该共
享段的物理内存, 以及取消在共享段表中该段所对应的表
项, 表明此时已没有进程使用该段；否则 (减 1结果不为 0)，
则只是取消调用者进程在共享段表中的有关记录 。
第四章 存 储 器 管 理
3,分段保护
1) 越界检查
2) 存取控制检查
(1) 只读
(2) 只执行
(3) 读 /写
3) 环保护机构
(1) 一个程序可以访问驻留在相同环或较低特权环中的数据。
(2) 一个程序可以调用驻留在相同环或较高特权环中的服务。
第四章 存 储 器 管 理
图 4-34 环保护机构
调用 返回
调用
返回
环 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 对用户程序的处理步骤
库
链接
程序
装入模块
装入
程序
编译程序产
生的目标模
块
第一步 第二步 第三步
内存
?
第四章 存 储 器 管 理
4.1.1 程序的装入
1,绝对装入方式 (Absolute Loading Mode)
程序中所使用的绝对地址, 既可在编译或汇编时给出,
也可由程序员直接赋予 。 但在由程序员直接给出绝对地址
时, 不仅要求程序员熟悉内存的使用情况, 而且一旦程序
或数据被修改后, 可能要改变程序中的所有地址 。 因此,
通常是宁可在程序中采用符号地址, 然后在编译或汇编时,
再将这些符号地址转换为绝对地址 。
第四章 存 储 器 管 理
2,可重定位装入方式 (Relocation Loading Mode)
图 4-2 作业装入内存时的情况
L O A D 1,2 5 0 0
3 6 5
L O A D 1,2 5 0 0
3 6 5
1 0 0 0 0
1 1 0 0 0
1 2 5 0 0
1 5 0 0 0
5 0 0 0
2 5 0 0
1 0 0 0
0
作业地址空间
内存空间
第四章 存 储 器 管 理
3,动态运行时装入方式 (Denamle Run-time Loading)
动态运行时的装入程序, 在把装入模块装入内存后,
并不立即把装入模块中的相对地址转换为绝对地址, 而
是把这种地址转换推迟到程序真正要执行时才进行 。 因
此, 装入内存后的所有地址都仍是相对地址 。
第四章 存 储 器 管 理
4.1.2 程序的链接
1,静态链接方式 (Static Linking)
图 4-3 程序链接示意图
模块 A
C A L L B ；
R e t u r n ；
0
L － 1
模块 B
C A L L C ；
R e t u r n ；
0
M － 1
模块 C
R e t u r n ；
0
N － 1
0
模块 A
J S R, L,
R e t u r n ；L － 1
模块 B
J S R, L ＋ M”
R e t u r n ；
L
L ＋ M － 1
L ＋ M
L ＋ M ＋ N － 1
模块 C
R e t u r n ；
( a ) 目标模块 ( b ) 装入模块
第四章 存 储 器 管 理
在将这几个目标模块装配成一个装入模块时, 须解
决以下两个问题：
(1) 对相对地址进行修改 。
(2) 变换外部调用符号。
第四章 存 储 器 管 理
2,装入时动态链接 (Load time Dynamic Linking)
装入时动态链接方式有以下优点：
(1) 便于修改和更新。
(2) 便于实现对目标模块的共享。
第四章 存 储 器 管 理
3,运行时动态链接 (Run-time Dynamic Linking)
近几年流行起来的运行时动态链接方式, 是对上述在
装入时链接方式的一种改进 。 这种链接方式是将对某些模
块的链接推迟到执行时才执行, 亦即, 在执行过程中, 当
发现一个被调用模块尚未装入内存时, 立即由 OS去找到该
模块并将之装入内存, 把它链接到调用者模块上 。 凡在执
行过程中未被用到的目标模块, 都不会被调入内存和被链
接到装入模块上, 这样不仅可加快程序的装入过程, 而且
可节省大量的内存空间 。
第四章 存 储 器 管 理
4.2 连续分配方式
4.2.1 单一连续分配
这是最简单的一种存储管理方式, 但只能用于单用户,
单任务的操作系统中 。 采用这种存储管理方式时, 可把内
存分为系统区和用户区两部分, 系统区仅提供给 OS使用,
通常是放在内存的低址部分；用户区是指除系统区以外的
全部内存空间, 提供给用户使用 。
第四章 存 储 器 管 理
4.2.2 固定分区分配
1,划分分区的方法
(1) 分区大小相等,即使所有的内存分区大小相等。
(2) 分区大小不等。
第四章 存 储 器 管 理
2,内存分配
图 4-4 固定分区使用表
第四章 存 储 器 管 理
4.2.3 动态分区分配
1,分区分配中的数据结构
(1) 空闲分区表。
(2) 空闲分区链。
图 4-5 空闲链结构
前
向
指
针
N
＋
2
0
N 个字节可用
后
向
指
针
N
＋
2
0
第四章 存 储 器 管 理
2,分区分配算法
(1) 首次适应算法 FF。
(2) 循环首次适应算法，该算法是由首次适应算法演变而成的。
(3) 最佳适应算法。
第四章 存 储 器 管 理
3,分区分配操作
1) 分配内存
从头开始查表
检索完否？
m, s i z e ＞ u, s i z e?
m, s i z e － u, s iz e ≤ s i z e?
从该分区中划出
u, s i z e 大小的分区
将该分区分配给请求者修
改有关数据结构
返回
返回
继续检索下一个表项
将该分区从链中移出
Y
N
N
Y
Y
N
图
4-
6
内
存
分
配
流
程
第四章 存 储 器 管 理
2) 回收内存
图 4-7 内存回收时的情况
第四章 存 储 器 管 理
4.2.4
1,
图 4-8 紧凑的示意
操作系统
用户程序 1
用户程序 3
1 0 K B
3 0 K B
用户程序 6
1 4 K B
用户程序 9
2 6 K B
操作系统
用户程序 1
用户程序 3
用户程序 6
用户程序 9
8 0 K B
( a ) 紧凑前 ( b ) 紧凑后
第四章 存 储 器 管 理
2,
图 4-9 动态重定位示意图
L O A D 1,2 5 0 0
3 6 5
0
1 0 0
2 5 0 0
5 0 0 0
2 5 0 0
相对地址
1 0 0 0 0
重定位寄存器
＋
L O A D 1,2 5 0 0
3 6 5
1 0 0 0 0
1 0 1 0 0
1 2 5 0 0
1 5 0 0 0
作业 J
处理机一侧 存储器一侧
主存
第四章 存 储 器 管 理
3,动态重定位分区分配算法
图 4-10 动态分区分配算法流程图
请求分配
u, s i z e 分区
检索空闲分区链( 表)
找到大于 u, s i z e
的可用区否?
按动态分区方式
进行分配
修改有关的
数据结构
返回分区号
及首批
空闲分区
总和≥ u, s i z e?
进行紧凑形
成连续空闲区
修改有关的
数据结构
否
是
无法分配
返回
否
第四章 存 储 器 管 理
4.2.5 对换 (Swapping)
1,对换的引入
所谓, 对换,, 是指把内存中暂时不能运行的进程或
者暂时不用的程序和数据, 调出到外存上, 以便腾出足够
的内存空间, 再把已具备运行条件的进程或进程所需要的
程序和数据, 调入内存 。 对换是提高内存利用率的有效措
施 。
第四章 存 储 器 管 理
2,对换空间的管理
为了能对对换区中的空闲盘块进行管理, 在系统中应
配置相应的数据结构, 以记录外存的使用情况 。 其形式与
内存在动态分区分配方式中所用数据结构相似, 即同样可
以用空闲分区表或空闲分区链 。 在空闲分区表中的每个表
目中应包含两项, 即对换区的首址及其大小, 它们的单位
是盘块号和盘块数 。
第四章 存 储 器 管 理
3,进程的换出与换入
(1) 进程的换出 。
每当一进程由于创建子进程而需要更多的内存空间,
但又无足够的内存空间等情况发生时, 系统应将某进程换
出 。 其过程是：系统首先选择处于阻塞状态且优先级最低
的进程作为换出进程, 然后启动盘块, 将该进程的程序和
数据传送到磁盘的对换区上 。 若传送过程未出现错误, 便
可回收该进程所占用的内存空间, 并对该进程的进程控制
块做相应的修改 。
第四章 存 储 器 管 理
(2) 进程的换入 。
系统应定时地查看所有进程的状态, 从中找出, 就绪,
状态但已换出的进程, 将其中换出时间 (换出到磁盘上 )最
久的进程作为换入进程, 将之换入, 直至已无可换入的进
程或无可换出的进程为止 。
第四章 存 储 器 管 理
4.3 基本分页存储管理方式
4.3.1 页面与页表
1,页面
1)
分页存储管理, 是将一个进程的逻辑地址空间分成若干个
大小相等的片, 称为页面或页, 并为各页加以编号, 从 0开始,
如第 0页, 第 1页等 。 相应地, 也把内存空间分成与页面相同大
小的若干个存储块, 称为 (物理 )块或页框 (frame),也同样为它
们加以编号, 如 0＃ 块, 1＃ 块等等 。 在为进程分配内存时, 以
块为单位将进程中的若干个页分别装入到多个可以不相邻接的
物理块中 。 由于进程的最后一页经常装不满一块而形成了不可
利用的碎片, 称之为, 页内碎片, 。
第四章 存 储 器 管 理
2)
在分页系统中的页面其大小应适中 。 页面若太小, 一方
面虽然可使内存碎片减小, 从而减少了内存碎片的总空间,
有利于提高内存利用率, 但另一方面也会使每个进程占用较
多的页面, 从而导致进程的页表过长, 占用大量内存； 此
外, 还会降低页面换进换出的效率 。 然而, 如果选择的页面
较大, 虽然可以减少页表的长度, 提高页面换进换出的速度,
但却又会使页内碎片增大 。 因此, 页面的大小应选择得适中,
且页面大小应是 2的幂, 通常为 512 B~8 KB。
第四章 存 储 器 管 理
2,地址结构
分页地址中的地址结构如下：
页号 P 位移量 W
31 12 11 0
对某特定机器, 其地址结构是一定的 。 若给定一个逻
辑地址空间中的地址为 A,页面的大小为 L,则页号 P和页
内地址 d可按下式求得：
M O D LAd
L
A
IN TP
][?
??
?
??
?
?
第四章 存 储 器 管 理
3,页表
图 4-11 页表的作用
用户程序
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
第四章 存 储 器 管 理
4.3.2 地址变换机构
1,基本的地址变换机构
图 4-12 分页系统的地址变换机构
页表寄存器
页表始址 页表长度 ＞ 页号 ( 3 ) 页 内地址
＋
逻辑地址L
越界中断
1
块号
b
页表
页号
0
1
2
物理地址
3
第四章 存 储 器 管 理
2,
图 4-13 具有快表的地址变换机构
页表寄存器
页表始址 页表长度 ＞ 页号 页 内地 址
＋
逻辑地址L
越界中断
块号
b
页表
页号 页号
输
入
寄
存
器
块号
b
b
快表
d
物理地址
第四章 存 储 器 管 理
4.3.3 两级和多级页表
现代的大多数计算机系统, 都支持非常大的逻辑地址空
间 (232~264)。 在这样的环境下, 页表就变得非常大, 要占用相
当大的内存空间 。 例如, 对于一个具有 32位逻辑地址空间的
分页系统, 规定页面大小为 4 KB即 212 B,则在每个进程页表
中的页表项可达 1兆个之多 。 又因为每个页表项占用一个字节,
故每个进程仅仅其页表就要占用 4 KB的内存空间, 而且还要
求是连续的 。 可以采用这样两个方法来解决这一问题,① 采
用离散分配方式来解决难以找到一块连续的大内存空间的问
题,② 只将当前需要的部分页表项调入内存, 其余的页表项
仍驻留在磁盘上, 需要时再调入 。
第四章 存 储 器 管 理
1,两级页表 (Two-Level Page Table)
逻辑地址结构可描述如下：
第四章 存 储 器 管 理
图 4-14 两级页表结构
1 0 1 1
1 0 7 8
0
1
2
1 7 4 2n
第 0 页页表
1
4
6
…
0
1
2
…
1 0 2 3
第 1 页页表
1 1 4
1 1 5
0
1
…
1 0 2 3
外部页表
0
1
2
3
4
5
6
7
…
…
1 1 4
1 1 5
1 4 6 8
第 n 页页表
1 4 6 8
0
1
2
…
1 0 2 3
内存空间
第四章 存 储 器 管 理
图 4-15 具有两级页表的地址变换机构
外部页号
P
1
P
2
外部页内地址 页内地址
d逻辑地址
＋外部页表寄存器
外部页表
＋ db
页表页表
物理地址? ?
第四章 存 储 器 管 理
2,多级页表
对于 32位的机器, 采用两级页表结构是合适的；但对于
64位的机器, 如果页面大小仍采用 4 KB即 212 B,那么还剩
下 52位, 假定仍按物理块的大小 (212位 )来划分页表, 则将
余下的 42位用于外层页号 。 此时在外层页表中可能有 4096
G个页表项, 要占用 16384 GB的连续内存空间 。 必须采用
多级页表, 将外层页表再进行分页, 也是将各分页离散地
装入到不相邻接的物理块中, 再利用第 2级的外层页表来映
射它们之间的关系 。
对于 64位的计算机, 如果要求它能支持 2６４ (=1844744
TB)规模的物理存储空间, 则即使是采用三级页表结构也是
难以办到的；而在当前的实际应用中也无此必要 。
第四章 存 储 器 管 理
4.4 基本分段存储管理方式
4.4.1 分段存储管理方式的引入
引入分段存储管理方式, 主要是为了满足用户和程序员
1)
2) 信息共享
3) 信息保护
4)
5) 动态链接
第四章 存 储 器 管 理
4.4.2 分段系统的基本原理
1,分段
分段地址中的地址具有如下结构：
段号 段内地址
31 16 15 0
2,
第四章 存 储 器 管 理
图 4-16 利用段表实现地址映射
作业空间
( M A I N ) ＝ 0
0
3 0 K
( X ) ＝ 1
0
2 0 K
( D ) ＝ 2
0
1 5 K
( S ) ＝ 3
0
1 0 K
3 0 K
2 0 K
1 5 K
1 0 K
4 0 K
8 0 K
1 2 0 K
1 5 0 K
段长 基址段号
( M A I N ) ＝ 0
3 0 K
( X ) ＝ 1
2 0 K
( D ) ＝ 2
1 5 K
( S ) ＝ 3
1 0 K
0
4 0 K
8 0 K
1 2 0 K
1 5 0 K
段表
内存空间
0
1
2
3
第四章 存 储 器 管 理
控制寄存器
段表始址 段表长度 ＞ 2 1 0 0
＋
段号 S
越界
1 K
段长
6 0 0
段号
0
1
2
3
6 K
4 K
5 0 0
2 0 0
8 K
9 2 0 0
基址
位移量 W
＋
8 2 9 2
8K
8 2 9 2
8 6 9 2
主存
物理地址
有效地址
图 4-17 分段系统的地址变换过程
3,地址变换机构
第四章 存 储 器 管 理
4,
(1) 页是信息的物理单位, 分页是为实现离散分配方
式, 以消减内存的外零头, 提高内存的利用率 。 或者说,
分页仅仅是由于系统管理的需要而不是用户的需要 。 段则
是信息的逻辑单位, 它含有一组其意义相对完整的信息 。
分段的目的是为了能更好地满足用户的需要 。
第四章 存 储 器 管 理
(2) 页的大小固定且由系统决定, 由系统把逻辑地址划
分为页号和页内地址两部分, 是由机器硬件实现的, 因而
在系统中只能有一种大小的页面；而段的长度却不固定,
决定于用户所编写的程序, 通常由编译程序在对源程序进
行编译时, 根据信息的性质来划分 。
(3) 分页的作业地址空间是一维的, 即单一的线性地
址空间, 程序员只需利用一个记忆符, 即可表示一个地址；
而分段的作业地址空间则是二维的, 程序员在标识一个地
址时, 既需给出段名, 又需给出段内地址 。
第四章 存 储 器 管 理
4.4.3 信息共享
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
页表
图
4-
18
分
页
系
统
中
共
享edit
or
的
示
意
图
第四章 存 储 器 管 理
图 4-19 分段系统中共享 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,基本原理
图 4-20 作业地址空间和地址结构
0
4K
8K
1 2 K
1 5 K
1 6 K
子程序段
0
4K
8K
数据段
0
4K
8K
1 0 K
1 2 K
( a )
段号 ( S ) 段内页号 ( P ) 段内地址 ( W )
( b )
主程序段
第四章 存 储 器 管 理
图 4-21 利用段表和页表实现地址映射
段号 状态 页表大小 页表始址
0 1
1 1
2 1
3 0
4 1
页号 状态 存储块#
0 1
1 1
2 1
3 0
4 1
操作系统
主存
页表
段表
段表大小 段表始址
段表寄存器
第四章 存 储 器 管 理
2,地址变换过程
图 4-22 段页式系统中的地址变换机构
段表寄存器
段表始址 段表长度 ＞ 段号 S 页号 P
＋
段超长
段表
0
1
2
3
＋
页内地址
页表
0
1
2
3
b 块号 b 块内地址
页表始址页表长度
第四章 存 储 器 管 理
4.5 虚拟存储器的基本概念
4.5.1
1,
(1) 一次性。
(2) 驻留性。
第四章 存 储 器 管 理
2,
早在 1968年, Denning.P就曾指出：
(1) 程序执行时, 除了少部分的转移和过程调用指令
外, 在大多数情况下仍是顺序执行的 。
(2) 过程调用将会使程序的执行轨迹由一部分区域转至
另一部分区域, 但经研究看出, 过程调用的深度在大多数
情况下都不超过 5。
(3) 程序中存在许多循环结构, 这些虽然只由少数指
令构成, 但是它们将多次执行 。
(4) 程序中还包括许多对数据结构的处理, 如对数组
进行操作, 它们往往都局限于很小的范围内 。
第四章 存 储 器 管 理
(1) 时间局限性 。 如果程序中的某条指令一旦执行,
则不久以后该指令可能再次执行；如果某数据被访问过,
则不久以后该数据可能再次被访问 。 产生时间局限性的
典型原因, 是由于在程序中存在着大量的循环操作 。
(2) 空间局限性 。 一旦程序访问了某个存储单元, 在
不久之后, 其附近的存储单元也将被访问, 即程序在一
段时间内所访问的地址, 可能集中在一定的范围之内,
其典型情况便是程序的顺序执行 。
第四章 存 储 器 管 理
3,虚拟存储器定义
所谓虚拟存储器, 是指具有请求调入功能和置换功能,
能从逻辑上对内存容量加以扩充的一种存储器系统 。 其逻
辑容量由内存容量和外存容量之和所决定, 其运行速度接
近于内存速度, 而每位的成本却又接近于外存 。 可见, 虚
拟存储技术是一种性能非常优越的存储器管理技术, 故被
广泛地应用于大, 中, 小型机器和微型机中 。
第四章 存 储 器 管 理
4.5.2 虚拟存储器的实现方法
1,分页请求系统
(1) 硬件支持。
① 请求分页的页表机制, 它是在纯分页的页表机制上增
加若干项而形成的, 作为请求分页的数据结构； ② 缺页中断
机构, 即每当用户程序要访问的页面尚未调入内存时 便产生
一缺页中断, 以请求 OS将所缺的页调入内存； ③ 地址变换
机构, 它同样是在纯分页地址变换机构的基础上发展形成的 。
(2) 实现请求分页的软件。
第四章 存 储 器 管 理
4.5.3 虚拟存储器的特征
1,多次性
2,对换性
3,虚拟性
第四章 存 储 器 管 理
4.6 请求分页存储管理方式
4.6.1 请求分页中的硬件支持
1,页表机制
页号 物理块号 状态位 P 访问字段 A 修改位 M 外存地址
第四章 存 储 器 管 理
2,缺页中断机构
图 4-23 涉及 6次缺页中断的指令
页面
B,
A,
6
5
4
3
2
1
指令
c o p y A
T O B
第四章 存 储 器 管 理
3,地址变换机构
缺页中断处理
保留 C P U 现场
从外存中找到缺页
内存满否？
选择一页换出
该页被修改否？
将该页写回外存
OS 命令 C P U 从外存读缺页
启动 I / O 硬件
将一页从外存换入内存
修改页表
否
是
是
否
页表项在快表中？
C P U 检索快表
访问页表
否
页在内存？
修改访问位和修改位
形成物理地址
地址变换结束
否
页号＞页表长度?
开始
程序请求访问一页
产生缺页中
断请求调页
修改快表
是
越界中断
是
是
图
4-
24
请
求
分
页
中
的
地
址
变
换
过
程
第四章 存 储 器 管 理
4.6.2 内存分配策略和分配算法
1,最小物理块数的确定
是指能保证进程正常运行所需的最小物理块数 。 当系统为
进程分配的物理块数少于此值时, 进程将无法运行 。 进程应获
得的最少物理块数与计算机的硬件结构有关, 取决于指令的格
式, 功能和寻址方式 。 对于某些简单的机器, 若是单地址指令
且采用直接寻址方式, 则所需的最少物理块数为 2。 其中, 一块
是用于存放指令的页面, 另一块则是用于存放数据的页面 。 如
果该机器允许间接寻址时, 则至少要求有三个物理块 。 对于某
些功能较强的机器, 其指令长度可能是两个或多于两个字节,
因而其指令本身有可能跨两个页面, 且源地址和目标地址所涉
及的区域也都可能跨两个页面 。
第四章 存 储 器 管 理
2,物理块的分配策略
在请求分页系统中, 可采取两种内存分配策略, 即固定
和可变分配策略 。 在进行置换时, 也可采取两种策略, 即全
局置换和局部置换 。 于是可组合出以下三种适用的策略 。
1) 固定分配局部置换 (Fixed Allocation,Local
Replacement)
2) 可变分配全局置换 (Variable Allocation,Global
Replacement)
3) 可变分配局部置换 (Variable Allocation,Local
Replacemen
第四章 存 储 器 管 理
3,物理块分配算法
1)
这是将系统中所有可供分配的物理块, 平均分配给各个
进程 。 例如, 当系统中有 100个物理块, 有 5个进程在运行时,
每个进程可分得 20个物理块 。 这种方式貌似公平, 但实际上
是不公平的, 因为它未考虑到各进程本身的大小 。 如有一个
进程其大小为 200页, 只分配给它 20个块, 这样, 它必然会
有很高的缺页率；而另一个进程只有 10页, 却有 10个物理块
闲置未用 。
第四章 存 储 器 管 理
2)
这是根据进程的大小按比例分配物理块的算法 。 如果
系统中共有 n个进程, 每个进程的页面数为 Si,则系统中各
进程页面数的总和为：
又假定系统中可用的物理块总数为 m,则每个进程所能分
到的物理块数为 bi,将有：
b应该取整, 它必须大于最小物理块数 。
?
?
?
n
i
iSS
1
mSSb ii ??
第四章 存 储 器 管 理
3)
在实际应用中, 为了照顾到重要的, 紧迫的作业能尽
快地完成, 应为它分配较多的内存空间 。 通常采取的方法
是把内存中可供分配的所有物理块分成两部分：一部分按
比例地分配给各进程；另一部分则根据各进程的优先权,
适当地增加其相应份额后, 分配给各进程 。 在有的系统中,
如重要的实时控制系统, 则可能是完全按优先权来为各进
程分配其物理块的 。
第四章 存 储 器 管 理
4.6.3
1,何时调入页面
1)
2) 请求调页策略
第四章 存 储 器 管 理
2,从何处调入页面
在请求分页系统中的外存分为两部分：用于存放文件的
文件区和用于存放对换页面的对换区 。 通常, 由于对换区是
采用连续分配方式, 而事件是采用离散分配方式, 故对换区
的磁盘 I/O速度比文件区的高 。 这样, 每当发生缺页请求时,
系统应从何处将缺页调入内存,
(1) 系统拥有足够的对换区空间, 这时可以全部从对换
区调入所需页面, 以提高调页速度 。 为此, 在进程运行前,
便须将与该进程有关的文件, 从文件区拷贝到对换区 。
第四章 存 储 器 管 理
(2) 系统缺少足够的对换区空间, 这时凡是不会被修改
的文件, 都直接从文件区调入；而当换出这些页面时, 由于
它们未被修改而不必再将它们换出, 以后再调入时, 仍从文
件区直接调入 。 但对于那些可能被修改的部分, 在将它们换
出时, 便须调到对换区, 以后需要时, 再从对换区调入 。
(3) UNIX方式 。 由于与进程有关的文件都放在文件区,
故凡是未运行过的页面, 都应从文件区调入 。 而对于曾经运
行过但又被换出的页面, 由于是被放在对换区, 因此在下次
调入时, 应从对换区调入 。 由于 UNIX系统允许页面共享,
因此, 某进程所请求的页面有可能已被其它进程调入内存,
此时也就无须再从对换区调入 。
第四章 存 储 器 管 理
3,页面调入过程
每当程序所要访问的页面未在内存时, 便向 CPU发出一
缺页中断, 中断处理程序首先保留 CPU环境, 分析中断原因
后, 转入缺页中断处理程序 。 该程序通过查找页表, 得到该
页在外存的物理块后, 如果此时内存能容纳新页, 则启动磁
盘 I/O将所缺之页调入内存, 然后修改页表 。 如果内存已满,
则须先按照某种置换算法从内存中选出一页准备换出；如果
该页未被修改过, 可不必将该页写回磁盘；但如果此页已被
修改, 则必须将它写回磁盘, 然后再把所缺的页调入内存,
并修改页表中的相应表项, 置其存在位为, 1”,并将此页表
项写入快表中 。 在缺页调入内存后, 利用修改后的页表, 去
形成所要访问数据的物理地址, 再去访问内存数据 。
第四章 存 储 器 管 理
4.7 页面置换算法
4.7.1
1,最佳 (Optimal)
最佳置换算法是由 Belady于 1966年提出的一种理论上
的算法 。 其所选择的被淘汰页面, 将是以后永不使用的,
或许是在最长 (未来 )时间内不再被访问的页面 。 采用最佳
置换算法, 通常可保证获得最低的缺页率 。
第四章 存 储 器 管 理
假定系统为某进程分配了三个物理块, 并考虑有以下
7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1
进程运行时, 先将 7,0,1三个页面装入内存 。 以后,
当进程要访问页面 2时, 将会产生缺页中断 。 此时 OS根据
最佳置换算法, 将选择页面 7予以淘汰 。
引用率
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
图 4-25 利用最佳页面置换算法时的置换图
第四章 存 储 器 管 理
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
图 4-26 利用 FIFO置换算法时的置换图
第四章 存 储 器 管 理
4.7.2 最近最久未使用 (LRU)置换算法
1,LRU(Least Recently Used)置换算法的描述
图 4-27 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
第四章 存 储 器 管 理
2,LRU置换算法的硬件支持
1)
为了记录某进程在内存中各页的使用情况, 须为每个
在内存中的页面配置一个移位寄存器, 可表示为
R=Rn-1Rn-2Rn-3 … R 2R1R0
第四章 存 储 器 管 理
图 4-28 某进程具有 8个页面时的 LRU访问情况
第四章 存 储 器 管 理
2) 栈
图 4-29 用栈保存当前使用页面时栈的变化情况
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
第四章 存 储 器 管 理
4.7.3 Clock置换算法
1,简单的 Clock置换算法
图 4-30 简单 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。 然后重复第
一步, 如果仍失败, 必要时再重复第二步, 此时就一定能找
到被淘汰的页 。
第四章 存 储 器 管 理
4.7.4 其它置换算法
1,最少使用 (LFU,Least Frequently Used)置换算法
2,页面缓冲算法 (PBA,Page Buffering Algorithm)
第四章 存 储 器 管 理
4.8 请求分段存储管理方式
4.8.1 请求分段中的硬件支持
1,
段名 段长 段的
基址
存取
方式
访问
字段 A
修改
位 M
存在
位 P
增补
位
外存
始址
第四章 存 储 器 管 理
在段表项中, 除了段名 (号 ),段长, 段在内存中的起
始地址外,
(1) 存取方式。
(2) 访问字段 A。
(3) 修改位 M。
(4) 存在位 P。
(5) 增补位。
(6) 外存始址。
第四章 存 储 器 管 理
2,缺段中断机构
虚段 S 不在内存
阻塞请求进程
内存中有合适
的空闲区吗？
从外存读入段 S
修改段表及内存空区链
唤醒请求进程
返回
空区容量总
和能否满足？
空区拼接，以形成
一个合适的空区
淘汰一个或几个实段，
以形成一个合适空区
否
否
是
是
图 4-31 请求分段系统中的中断处理过程
第四章 存 储 器 管 理
3,地址变换机构
访问 [ s ] [ w ]
w≤ 段长?
符合存取方式?
段 S 在主存?
修改访问字段,如写
访问,置修改位 ＝ 1
形成访问主存地址
( A ) ＝ ( 主存始址 )
＋ ( 位移量 w)
返回
分段越界
中断处理
分段保护
中断处理
缺段中
断处理
是
是
是
否
否
否
图
4-
32
请
求
分
段
系
统
的
地
址
变
换
过
程
第四章 存 储 器 管 理
4.8.2 分段的共享与保护
1,共享段表
图 4-33 共享段表项
段名 段长 内存始址 状态 外存始址
共享进程计数 c o u n t
状态 进程名 进程号 段号 存取控制
? ? ? ? ?
?
共享段表
第四章 存 储 器 管 理
2,共享段的分配与回收
1)
在为共享段分配内存时, 对第一个请求使用该共享段的进
程, 由系统为该共享段分配一物理区, 再把共享段调入该区,
同时将该区的始址填入请求进程的段表的相应项中, 还须在共
享段表中增加一表项, 填写有关数据, 把 count置为 1；之后,
当又有其它进程需要调用该共享段时, 由于该共享段已被调入
内存, 故此时无须再为该段分配内存, 而只需在调用进程的段
表中, 增加一表项, 填写该共享段的物理地址；在共享段的段
表中, 填上调用进程的进程名, 存取控制等, 再执行
count∶ =count+1操作, 以表明有两个进程共享该段 。
第四章 存 储 器 管 理
2)
当共享此段的某进程不再需要该段时, 应将该段释放,
包括撤在该进程段表中共享段所对应的表项, 以及执行
count∶ = count-1操作 。 若结果为 0,则须由系统回收该共
享段的物理内存, 以及取消在共享段表中该段所对应的表
项, 表明此时已没有进程使用该段；否则 (减 1结果不为 0)，
则只是取消调用者进程在共享段表中的有关记录 。
第四章 存 储 器 管 理
3,分段保护
1) 越界检查
2) 存取控制检查
(1) 只读
(2) 只执行
(3) 读 /写
3) 环保护机构
(1) 一个程序可以访问驻留在相同环或较低特权环中的数据。
(2) 一个程序可以调用驻留在相同环或较高特权环中的服务。
第四章 存 储 器 管 理
图 4-34 环保护机构
调用 返回
调用
返回
环 0
环 1
环 2
( a ) 程序间的控制传输
数据访问
环 0
环 1
环 2
( b ) 数据访问
数据访问
