第八章 实存储器管理技术
第 8章 实存储器管理技术
? 8.1 引言
? 8.2 固定分区
? 8.3 可变分区多道管理技术
? 8.4 多重分区管理技术
? 8.5 简单分页
? 8.6 简单分段
? 8.7 内核主存管理
第八章 实存储器管理技术
8.1 引言
? 存储器包括内存（主存）和外存（磁盘）
? 存储器的功能是保存数据，存储器的发展方
向是高速、大容量和小体积。
? 内存在访问速度方面的发展,DRAM,SDRAM、
SRAM等；
? 硬盘技术在大容量方面的发展：接口标准、存储
密度等；
? 主存储器管理技术分为两大类
? 实存储器管理
? 虚拟存储器管理
第八章 实存储器管理技术
8.1 引言
? 存储器的物理组织、多级存储器
? 存储组织是指在存储技术和 CPU寻址技术许
可的范围内组织合理的存储结构。
? 其依据是访问速度匹配关系、容量要求和价格。
?, 寄存器 -内存 -外存, 结构
?, 寄存器 -缓存 -内存 -外存, 结构；
? 微机中的存储层次组织,
? 访问速度越慢，容量越大，价格越便宜；
? 最佳状态应是各层次的存储器都处于均衡的繁忙
状态（如：缓存命中率正好使主存读写保持繁
忙）；
第八章 实存储器管理技术
8.1 引言
? 快速缓存,
? Data Cache
? TLB(Translation Lookaside Buffer)
? 内存,DRAM,SDRAM等；
? 外存：软盘、硬盘、光盘、磁带等；
外存(sec onda ry s tora ge)
DOS核 心
命令处理程序
内存(pri mary sto rage )
快速缓存(cac he)
寄存器(r egis ter)
第八章 实存储器管理技术
8.1 引言
? 主存储器管理功能
? 存储分配和回收：分配和回收算法及相应的数据结
构。
? 地址变换和重定位,
? 可执行文件生成中的链接技术
? 程序加载 (装入 )时的重定位技术
? 进程运行时硬件和软件的地址变换技术和机构
? 存储共享和保护,
? 代码和数据共享
? 地址空间访问权限（读、写、执行）
? 存储器扩充：存储器的逻辑组织和物理组织；
? 由应用程序控制：覆盖；
? 由 OS控制：交换（整个进程空间），虚拟存储的请求调入
和预调入（部分进程空间）
第八章 实存储器管理技术
8.2 固定分区
? 单道作业（单一固定分区）
? 内存分为两个区域：系统区，用户区。应用程序装
入到用户区，可使用用户区全部空间
? 使用界地址寄存器保护系统信息
? 最简单，适用于单用户、单任务的 OS
? 优点：易于管理
? 缺点：对要求内存空间少的程序，造成内存浪费；
程序全部装入，很少使用的程序部分也占用内存
第八章 实存储器管理技术
用户程序
位于 RAM 中的
操作系统
0 xFFF,..
0
位于 RAM 中的
操作系统
用户程序
0
R OM 中的
设备驱动程序
用户程序
位于 RAM 中的
操作系统
0
单一连续区存储管理
第八章 实存储器管理技术
8.2 固定分区
? 多道作业
? 主存分为固定大小的若干块，主存分区的数
量不变，每个分区的大小也不变
? 分区的信息由存储分块表（ MBT）管理
? 大小：以字节为单位
? 位置：分区的起始地址
? 状态：分区是否被使用
? 使用界地址寄存器
? 采用静态重定位
第八章 实存储器管理技术
8 M
8 M
8 M
8 M
8 M
Op er ati ng S ys tem
O p e r ati n g S ys te m
8 M
12 M
8 M
8 M
6 M
4 M
2 M
固定分区 (大小相同 ) 固定分区 (多种大小 )
第八章 实存储器管理技术
8.3 可变分区多道管理技术
（动态分区）
? 主存事先并不划分分区，而是在作业级
如主存时，按作业大小建立分区，分给
作业使用
? 优点：没有分区内部碎片
? 缺点：有外碎片；如果大小不是任意的，
也可能出现内碎片。
第八章 实存储器管理技术
O perati ng
Sy st em
128 K
896 K
O perati ng
Sy st em
Process 1
320 K
576 K
O perati ng
Sy st em
Process 1
320 K
Process 2 224 K
352 K
第八章 实存储器管理技术
O per at i ng
Syst em
Pr oce ss 1
320 K
Pr oce ss 2
Pr oce ss 3
224 K
288 K
64 K
O per at i ng
Syst em
Pr oce ss 1
320 K
Pr oce ss 3
224 K
288 K
64 K
O per at i ng
Syst em
Pr oce ss 1
320 K
Pr oce ss 3 288 K
64 K
Pr oce ss 4
128 K
96 K
第八章 实存储器管理技术
Op e r a ti n g
S ys te m
32 0 K
P ro ce s s 3 28 8 K
6 4 K
P r oc e s s 4
12 8 K
9 6 K
Op e r a ti n g
S ys te m
P ro ce s s 3 28 8 K
6 4 K
P r oc e s s 4
12 8 K
9 6 K
P ro ce s s 2 22 4 k
9 6 K
第八章 实存储器管理技术
8.3 可变分区多道管理技术
（动态分区）
? 需要解决三个问题：分配管理的数据结构
（ MBT）、存储分配算法、分区的分配和
回收
? MBT组织方法
? 存储分块表
? 分开设置两个存储管理表
? 空闲存储块链
第八章 实存储器管理技术
8.3 可变分区多道管理技术
（动态分区）
? MBT组织方法：存储分块表
? 缺点
? 分区个数不固定，所以需要的分块表的表长度不
能确定，可能造成预留空间不足或浪费的情况
? 分区增多时，查找空闲分区的时间长
第八章 实存储器管理技术
8.3 可变分区多道管理技术
（动态分区）
? MBT组织方法：两个存储分块表
? 设置空闲分区表（ FBT），提高查找速度
序号 分区大小 (K) 分区始址 (K) 状态
1 32 256 可用
2 16 512 可用
…… …… …… ……
第八章 实存储器管理技术
8.3 可变分区多道管理技术
（动态分区）
? 存储分配算法
? 最先匹配法 (first-fit)：按分区的先后次序，
从头查找，找到符合要求的第一个分区
? 该算法的分配和释放的时间性能较好，较大的空
闲分区可以被保留在内存高端。
? 但随着低端分区不断划分而产生较多小分区，每
次分配时查找时间开销会增大。
? 下次匹配法 (next-fit)：按分区的先后次序，
从上次分配的分区起查找（到最后分区时再
回到开头），找到符合要求的第一个分区
? 该算法的分配和释放的时间性能较好，使空闲分
区分布得更均匀，但较大的空闲分区不易保留。
第八章 实存储器管理技术
8.3 可变分区多道管理技术
（动态分区）
? 存储分配算法
? 最佳匹配法 (best-fit)：找到其大小与要求相
差最小的空闲分区
? 从个别来看，外碎片较小，但从整体来看，会形
成较多外碎片。较大的空闲分区可以被保留。
? 最坏匹配法 (worst-fit)：找到最大的空闲分区
? 基本不留下小空闲分区，但较大的空闲分区不被
保留。
第八章 实存储器管理技术
Last
al l oc ate d
blo c k (1 4K )
Be for e
Afte r
8 K 8 K
12 K 12 K
22 K
18 K
6 K 6 K
8 K
8 K
14 K 14 K
6 K
2 K
36 K
20 K
Ne xt F i t
F r e e bl oc k
All oc ate d blo c k
Be st F i t
F i r st F i t
请求分配 16K
第八章 实存储器管理技术
8.3 可变分区多道管理技术
（动态分区）
? 存储分块分
配和回收
? 分配
从头开始查找
检索完否？ 返回
m.size>u.size 查找下一个
m.size-u.size>size
划出 u.size分区 整块分配
修改有关数据
N
Y
N
Y N
m.size— 空闲分区大小
u.size— 请求分区大小
size— 不可再分割大小
按分区分
配算法
第八章 实存储器管理技术
8.3 可变分区多道管理技术
（动态分区）
? 存储分块分配和回收
? 回收：当一个进程运行结束，要释放内存，
操作回收内存，并把它插入到空闲区链表中。
? 根据回收区的位置，有四种情况需要处理,
空闲区
回收区 回收区
空闲区
空闲区
回收区
空闲区
回收区
情况 1 情况 2 情况 3 情况 4
第八章 实存储器管理技术
8.3 可变分区多道管理技术
（动态分区）
? 存储器紧缩和程序浮动
? 因为存储块的动态分配和
回收，会产生大量的碎片，
这些碎片的总量很大，但
每一个碎片都不足以容纳
一个程序
? 处理碎片的方法：存储器
紧缩，就是把已经使用的
空间移动到存储器的一端，
而使碎片移动到另一端连
接起来
8K
12K
6K
18K
44K
紧缩
第八章 实存储器管理技术 8.3 可变分区多道管理技术
（动态分区）
? 存储器紧缩和程序浮动
? 处理器紧缩的关键是内存中的程序要移动，
把这称为程序浮动
1000
Load 2500 1100
365 3500
移动后
0
Load 2500 100
365 2500
移动前
第八章 实存储器管理技术 8.3 可变分区多道管理技术
（动态分区）
? 存储器紧缩和程序浮动
? 解决程序移动产生的访问地址错误 —— 动
态重定位
0
Load 2500 100
365 2500
2500
相对地址 0
重定位寄存器 0
Load 2500 100
365 2500 +
处理机 存储器 移动前
第八章 实存储器管理技术 8.3 可变分区多道管理技术
（动态分区）
? 存储器紧缩和程序浮动
? 解决程序移动产生的访问地址错误 —— 动
态重定位
0
Load 2500 100
365 2500
2500
相对地址 10000
重定位寄存器 10000
Load 2500 10100
365 12500 +
处理机 存储器 移动后
第八章 实存储器管理技术
8.3 可变分区多道管理技术
（动态分区）
? 动态重定位分配算法
? 在一个分区释放后立即移动
? 当请求得不到满足时再移动
请求分配
u.size分区
检索空闲分区链
找到
m.size≥u.size
按动态分区分配
方式进行分配
空闲分区
总和 ≥u.size
进行“紧凑” 返回分区号 及首址
无法分配
返回
y
N
Y
N
第八章 实存储器管理技术
8.4 多重分区
? 即一个程序可以占据主存中不连续的多
个分区 —— 可以解决碎片问题
? 需要硬件支持（多对界地址寄存器）
? 管理复杂
? 多重分区的思想和实现类似于虚拟段式
存储
第八章 实存储器管理技术
8.5 简单分页
? 把主存分成许多同样大小的存储块，并
把这种存储块作为存储分配的最小单位
第八章 实存储器管理技术
8.5 简单分页
? 实现方法,
? 把内存空间划分成若干大小相同的物理块，
这些物理块叫, 页架, (frame)，并依次编
以连续的页架号 0,1,2…,,
? 把用户程序的地址空间划分成与页架大小相
同的部分 (fixed size chunk)，把它们叫, 页,
（不同系统的页大小不同）
? 用户的逻辑地址表示为一个数对（ p,d），
其中 p是页号,d是页内相对地址
第八章 实存储器管理技术
8.5 简单分页
? 实现方法,
? 给定虚地址（逻辑地址） A，页面大小 L，则
p=INT[A/L],d=[A] mod L，其中 INT是向
下取整,mod是取余。
? 例如 L=2KB,A=2506B，则 p=1,d=506，
表示为 (1,506)
第八章 实存储器管理技术
8.5 简单分页
? 主存分配
? 把用户程序的任一页分配到内存中的任一帧，
从而实现非连续的内存分配。
? 问题
? 如何管理、如何进行地址变换。
第八章 实存储器管理技术
8.5 简单分页
进程 A页表
0 0
页号 块号
1 1
2 4
3 5
4 8
5 9
…… ……
0
1
2
3
4
5
6
7
8
内存
9
程序 A
0页
1页
2页
3页
4页
5页
n页
程序 B
0页
1页
2页
3页
4页
5页
m页
进程 B页表
0 2
页号 块号
1 3
2 6
3 7
…… ……
页表：实现页号到物理块号的映射。
第八章 实存储器管理技术
8.5 简单分页
? 地址组成：页号 P+(页内地址 )位移量 d
例如,32位地址,0~11为偏移量,12~31为
页号，最大可以有 1M页，每页 4KB 。
地址结构,
页号 P 位移量 d
12 11 0 31
第八章 实存储器管理技术
8.5 简单分页
? 页面大小的确定
? 分页系统中，页面的大小是由硬件的地址结构
所决定的。机器确定、页面大小就确定。
? 通常页面大小采用 2的幂次（为什么？）
? 影响因素,
? 页面 ↓→ 内部碎块 ↓,内存的利用率 ↑
? 页面 ↓→ 页表 ↑,占用内存 ↑
? 页面 ↓→ 页面的换出换入效率 ↓ 。
第八章 实存储器管理技术
8.5 简单分页
计算机类型 页面大小 (B)
IBM AS/400
VAX
Intel 80386
Motorola 68030
512
512
4096
4096
常见机型页面
第八章 实存储器管理技术
8.5 简单分页
? 地址转换
? 分页存储系统中，地址变换机构的任务是把逻辑地
址中的页号转换为内存中物理块的块号。
? 注意：页面大小与页框大小一致，无须进行页内地
址转换。
? 实现转换：借助于页表。
? 页表的实现,
? 寄存器：变换速度快、成本高，适应小型系统。
? 页表驻留在内存：速度较低、成本低，适应大系统。
第八章 实存储器管理技术
8.5 简单分页
? 地址转换实现
? 将逻辑地址的页号取出
? 以页号为索引查找该进程的页表，找出和该
页号对应的页架号
? 用页架号和逻辑地址的页内相对地址拼接，
得到的就是物理地址
第八章 实存储器管理技术
8.6 简单分段
? 分段管理思想的引入
? 在分页管理中，只按页面大小划分程序，没
有考虑程序的逻辑功能结构
? 一个程序包含多个逻辑上相对独立的功能模
块，也可能包含多个子程序，这些模块或者
子程序完成相对独立的功能
? 在分页系统中，一个逻辑段可能被分到不同
的页内，不利于执行
第八章 实存储器管理技术
8.6 简单分段
? 分段的实现
? 把作业的地址空间按逻辑功能划分若干段，
每一段定义一组逻辑信息：段名、段的长度
? 段名：用段号来替代。
? 段的长度：不确定，由相应的逻辑信息组的长度
决定。
? 逻辑地址,Segment Number Offset
31 16 15 0
64K个段 64KB长度
第八章 实存储器管理技术
8.6 简单分段
? 主存分配
? 以段为单位，每一段分配一个连续的主存分
区，一个程序的各段所分到的主存分区不要
求是连续的
? 请考虑：程序的段是在什么时候由谁划分出
来的？
第八章 实存储器管理技术
8.6 简单分段
? 段表：记录逻辑段与内存物理位置的对应映射
关系。
段号 段长 基址
0 30K 40K
1 20K 80K
2 15K 120K
段表
(MAIN)=0
(x)=1
(D)=2
内存空间
作业空间
0 (MAIN)=0
0 (X)=1
0 (D)=2
40K
80K
120K
第八章 实存储器管理技术
8.6 简单分段
? 段的地址转换
段表始址 段表长度
段表寄存器
2
段号 段内偏移量
100
+
6K 1K 0
4K 600 1
8K 500 2
9200 200 3
基址 段长 段号
段表
+
越界中断
+
8292
物理地址
0
1
2
内存空间
8K
第八章 实存储器管理技术
? 分页与分段的区别
分块方式 使用 碎片 长度 目的
分页存储
管理
物理分块，
系统决
定
对程序员
是不可
见，使
用简单
每个进程
只有一
个内部
碎片，
大小不
超过 1
页
固定 提高内存
的利用
率
分段存储
管理
逻辑分块，
大小与
信息块
有关，
由编译
系统划
分
对程序员
可见，
使用方
便，但
难度大
每个进程
会产生
多个外
部碎片
不确定 便于信息
保护与
共享，
方便用
户
第八章 实存储器管理技术
? 实存储管理技术的特点：程序要整体装
入，一个程序在没有全部装入主存之前
不能运行。
? 请同学们课后分析一下这种技术的优缺
点
第八章 实存储器管理技术
8.7 内核主存管理
? 即对操作系统内核程序占用的主存区的
管理
? 现代操作系统的内核程序大都驻留在 ROM里
? 但是一些系统内核程序在运行时，需要一些
存储空间（属于内核存储区）存放临时信息
? 预留一定大小的空间
? 动态管理 —— 内核主存分配器
第八章 实存储器管理技术
8.7 内核主存管理
? 二次幂空闲表分配器
? 伙伴系统
? SVR3延迟伙伴算法
第八章 实存储器管理技术
8.7 内核主存管理
（二次幂空闲表分配器）
? 把内核存储区分成一些固定大小的空线块，如
1KB,2KB等，每个空闲块有一个字长的头结构
（不属于可用空间）用来存放链指针
? 使用一组空闲表，每个表存放某一特定尺寸的
空闲块
? 内核程序需要存储区时，根据它需要的大小给
它分配一个合适的空闲块
? 见 Page162 图 8.14
第八章 实存储器管理技术
8.7 内核主存管理
（二次幂空闲表分配器）
? 优点
? 快速分配和式访主存
? 缺点
? 因为要存放头结构，浪费空间
? 存储块不能合并，不能满足对大主存块的要
求
第八章 实存储器管理技术
8.7 内核主存管理 （伙伴系统）
? 思想
? 通过不断的对分大主存块来获得小主存块，
并尽可能合并空闲块，但必须在伙伴的关系
上才能合并
? 伙伴：当一个主存块被对分后，每一部分称
为另一部分的伙伴
第八章 实存储器管理技术
8.7 内核主存管理 （伙伴系统）
? 概念
? 伙伴系统是通过对分大空闲块来获得小空闲块，对
分生成的两个空闲块互称伙伴，合并必须在伙伴之
间进行
? 系统中规定最小分配单位，通常为 32byte或 64byte
? 系统使用位图位互主存中每一个最小单位的使用情
况,1表示正在使用,0表示空闲
? 系统为每一种可能大小的空闲块维护一个空闲链表
? 缺点
? 会有频繁的对分和合并
第八章 实存储器管理技术
8.7 内核主存管理 （伙伴系统）
? 概念
? 系统启动时，只有一个大的 2次幂大小的空
闲块。
? 将请求的大小取整，然后寻找对应的空闲链
表，如果有空闲块，则分配，否则将一个大
空闲块对分，直到与请求大小相符合
? 确定伙伴的方法是根据空闲块的基地址和大
小
第八章 实存储器管理技术
1MB
A：请求 100K 128K
B：请求 240K 256K 128K
C：请求 64K 256K 128K 64K
D：请求 256K 256K 128K 64K 256K
释放 A 256K 128K 64K 256K
释放 D 256K 128K 64K
E：请求 75K 256K 128K 64K
释放 C 256K 128K
第八章 实存储器管理技术
8.7 内核主存管理
（ SVR4延迟伙伴算法）
? 为了解决伙伴算法的频繁对分和合并问
题 —— 必要时再合并
第八章 实存储器管理技术
8.7 内核主存管理
（ SVR4延迟伙伴算法）
? 合并算法
? 使用几个参数
? Ni：尺寸为 2的 i次幂的主存块数量
? Ai：尺寸为 2的 i次幂的以分配主存块数量
? Li：尺寸为 2的 i次幂的局部空闲块数量
? Gi：尺寸为 2的 i次幂的全局空闲块数量
? 局部空闲块：暂时不能合并的空闲块
? 全局空闲块：可以合并的空闲块
第八章 实存储器管理技术
8.7 内核主存管理
（ SVR4延迟伙伴算法）
? 合并算法
? 当 2i级空闲块过多时，说明下一级空闲块过
少，进行合并，合并标准,Li<=Ai
? Slack=Ai-Li=Ni-2Li-Gi
? 每个主存块类有 3种状态
? 平稳状态,Slack>=2，不需合并
? 回收状态,Slack=1，需要合并
? 加速状态,Slack=0，需要加速合并
第八章 实存储器管理技术
8.7 内核主存管理
（ SVR4延迟伙伴算法）
? 合并算法
? 当有块被释放时，将其放入空闲链表，检查
该主存块类的状态
? 平稳状态：不操作
? 回收状态：合并
? 加速状态：合并两个主存块
? 局部空闲块优先被分配使用，减少修改位图
的开销
第八章 实存储器管理技术
课后作业
? Page 147上交时间：下周
? 8.9
? 8.17
? 思考题
? 8.5
第 8章 实存储器管理技术
? 8.1 引言
? 8.2 固定分区
? 8.3 可变分区多道管理技术
? 8.4 多重分区管理技术
? 8.5 简单分页
? 8.6 简单分段
? 8.7 内核主存管理
第八章 实存储器管理技术
8.1 引言
? 存储器包括内存（主存）和外存（磁盘）
? 存储器的功能是保存数据，存储器的发展方
向是高速、大容量和小体积。
? 内存在访问速度方面的发展,DRAM,SDRAM、
SRAM等；
? 硬盘技术在大容量方面的发展：接口标准、存储
密度等；
? 主存储器管理技术分为两大类
? 实存储器管理
? 虚拟存储器管理
第八章 实存储器管理技术
8.1 引言
? 存储器的物理组织、多级存储器
? 存储组织是指在存储技术和 CPU寻址技术许
可的范围内组织合理的存储结构。
? 其依据是访问速度匹配关系、容量要求和价格。
?, 寄存器 -内存 -外存, 结构
?, 寄存器 -缓存 -内存 -外存, 结构；
? 微机中的存储层次组织,
? 访问速度越慢，容量越大，价格越便宜；
? 最佳状态应是各层次的存储器都处于均衡的繁忙
状态（如：缓存命中率正好使主存读写保持繁
忙）；
第八章 实存储器管理技术
8.1 引言
? 快速缓存,
? Data Cache
? TLB(Translation Lookaside Buffer)
? 内存,DRAM,SDRAM等；
? 外存：软盘、硬盘、光盘、磁带等；
外存(sec onda ry s tora ge)
DOS核 心
命令处理程序
内存(pri mary sto rage )
快速缓存(cac he)
寄存器(r egis ter)
第八章 实存储器管理技术
8.1 引言
? 主存储器管理功能
? 存储分配和回收：分配和回收算法及相应的数据结
构。
? 地址变换和重定位,
? 可执行文件生成中的链接技术
? 程序加载 (装入 )时的重定位技术
? 进程运行时硬件和软件的地址变换技术和机构
? 存储共享和保护,
? 代码和数据共享
? 地址空间访问权限（读、写、执行）
? 存储器扩充：存储器的逻辑组织和物理组织；
? 由应用程序控制：覆盖；
? 由 OS控制：交换（整个进程空间），虚拟存储的请求调入
和预调入（部分进程空间）
第八章 实存储器管理技术
8.2 固定分区
? 单道作业（单一固定分区）
? 内存分为两个区域：系统区，用户区。应用程序装
入到用户区，可使用用户区全部空间
? 使用界地址寄存器保护系统信息
? 最简单，适用于单用户、单任务的 OS
? 优点：易于管理
? 缺点：对要求内存空间少的程序，造成内存浪费；
程序全部装入，很少使用的程序部分也占用内存
第八章 实存储器管理技术
用户程序
位于 RAM 中的
操作系统
0 xFFF,..
0
位于 RAM 中的
操作系统
用户程序
0
R OM 中的
设备驱动程序
用户程序
位于 RAM 中的
操作系统
0
单一连续区存储管理
第八章 实存储器管理技术
8.2 固定分区
? 多道作业
? 主存分为固定大小的若干块，主存分区的数
量不变，每个分区的大小也不变
? 分区的信息由存储分块表（ MBT）管理
? 大小：以字节为单位
? 位置：分区的起始地址
? 状态：分区是否被使用
? 使用界地址寄存器
? 采用静态重定位
第八章 实存储器管理技术
8 M
8 M
8 M
8 M
8 M
Op er ati ng S ys tem
O p e r ati n g S ys te m
8 M
12 M
8 M
8 M
6 M
4 M
2 M
固定分区 (大小相同 ) 固定分区 (多种大小 )
第八章 实存储器管理技术
8.3 可变分区多道管理技术
（动态分区）
? 主存事先并不划分分区，而是在作业级
如主存时，按作业大小建立分区，分给
作业使用
? 优点：没有分区内部碎片
? 缺点：有外碎片；如果大小不是任意的，
也可能出现内碎片。
第八章 实存储器管理技术
O perati ng
Sy st em
128 K
896 K
O perati ng
Sy st em
Process 1
320 K
576 K
O perati ng
Sy st em
Process 1
320 K
Process 2 224 K
352 K
第八章 实存储器管理技术
O per at i ng
Syst em
Pr oce ss 1
320 K
Pr oce ss 2
Pr oce ss 3
224 K
288 K
64 K
O per at i ng
Syst em
Pr oce ss 1
320 K
Pr oce ss 3
224 K
288 K
64 K
O per at i ng
Syst em
Pr oce ss 1
320 K
Pr oce ss 3 288 K
64 K
Pr oce ss 4
128 K
96 K
第八章 实存储器管理技术
Op e r a ti n g
S ys te m
32 0 K
P ro ce s s 3 28 8 K
6 4 K
P r oc e s s 4
12 8 K
9 6 K
Op e r a ti n g
S ys te m
P ro ce s s 3 28 8 K
6 4 K
P r oc e s s 4
12 8 K
9 6 K
P ro ce s s 2 22 4 k
9 6 K
第八章 实存储器管理技术
8.3 可变分区多道管理技术
（动态分区）
? 需要解决三个问题：分配管理的数据结构
（ MBT）、存储分配算法、分区的分配和
回收
? MBT组织方法
? 存储分块表
? 分开设置两个存储管理表
? 空闲存储块链
第八章 实存储器管理技术
8.3 可变分区多道管理技术
（动态分区）
? MBT组织方法：存储分块表
? 缺点
? 分区个数不固定，所以需要的分块表的表长度不
能确定，可能造成预留空间不足或浪费的情况
? 分区增多时，查找空闲分区的时间长
第八章 实存储器管理技术
8.3 可变分区多道管理技术
（动态分区）
? MBT组织方法：两个存储分块表
? 设置空闲分区表（ FBT），提高查找速度
序号 分区大小 (K) 分区始址 (K) 状态
1 32 256 可用
2 16 512 可用
…… …… …… ……
第八章 实存储器管理技术
8.3 可变分区多道管理技术
（动态分区）
? 存储分配算法
? 最先匹配法 (first-fit)：按分区的先后次序，
从头查找，找到符合要求的第一个分区
? 该算法的分配和释放的时间性能较好，较大的空
闲分区可以被保留在内存高端。
? 但随着低端分区不断划分而产生较多小分区，每
次分配时查找时间开销会增大。
? 下次匹配法 (next-fit)：按分区的先后次序，
从上次分配的分区起查找（到最后分区时再
回到开头），找到符合要求的第一个分区
? 该算法的分配和释放的时间性能较好，使空闲分
区分布得更均匀，但较大的空闲分区不易保留。
第八章 实存储器管理技术
8.3 可变分区多道管理技术
（动态分区）
? 存储分配算法
? 最佳匹配法 (best-fit)：找到其大小与要求相
差最小的空闲分区
? 从个别来看，外碎片较小，但从整体来看，会形
成较多外碎片。较大的空闲分区可以被保留。
? 最坏匹配法 (worst-fit)：找到最大的空闲分区
? 基本不留下小空闲分区，但较大的空闲分区不被
保留。
第八章 实存储器管理技术
Last
al l oc ate d
blo c k (1 4K )
Be for e
Afte r
8 K 8 K
12 K 12 K
22 K
18 K
6 K 6 K
8 K
8 K
14 K 14 K
6 K
2 K
36 K
20 K
Ne xt F i t
F r e e bl oc k
All oc ate d blo c k
Be st F i t
F i r st F i t
请求分配 16K
第八章 实存储器管理技术
8.3 可变分区多道管理技术
（动态分区）
? 存储分块分
配和回收
? 分配
从头开始查找
检索完否？ 返回
m.size>u.size 查找下一个
m.size-u.size>size
划出 u.size分区 整块分配
修改有关数据
N
Y
N
Y N
m.size— 空闲分区大小
u.size— 请求分区大小
size— 不可再分割大小
按分区分
配算法
第八章 实存储器管理技术
8.3 可变分区多道管理技术
（动态分区）
? 存储分块分配和回收
? 回收：当一个进程运行结束，要释放内存，
操作回收内存，并把它插入到空闲区链表中。
? 根据回收区的位置，有四种情况需要处理,
空闲区
回收区 回收区
空闲区
空闲区
回收区
空闲区
回收区
情况 1 情况 2 情况 3 情况 4
第八章 实存储器管理技术
8.3 可变分区多道管理技术
（动态分区）
? 存储器紧缩和程序浮动
? 因为存储块的动态分配和
回收，会产生大量的碎片，
这些碎片的总量很大，但
每一个碎片都不足以容纳
一个程序
? 处理碎片的方法：存储器
紧缩，就是把已经使用的
空间移动到存储器的一端，
而使碎片移动到另一端连
接起来
8K
12K
6K
18K
44K
紧缩
第八章 实存储器管理技术 8.3 可变分区多道管理技术
（动态分区）
? 存储器紧缩和程序浮动
? 处理器紧缩的关键是内存中的程序要移动，
把这称为程序浮动
1000
Load 2500 1100
365 3500
移动后
0
Load 2500 100
365 2500
移动前
第八章 实存储器管理技术 8.3 可变分区多道管理技术
（动态分区）
? 存储器紧缩和程序浮动
? 解决程序移动产生的访问地址错误 —— 动
态重定位
0
Load 2500 100
365 2500
2500
相对地址 0
重定位寄存器 0
Load 2500 100
365 2500 +
处理机 存储器 移动前
第八章 实存储器管理技术 8.3 可变分区多道管理技术
（动态分区）
? 存储器紧缩和程序浮动
? 解决程序移动产生的访问地址错误 —— 动
态重定位
0
Load 2500 100
365 2500
2500
相对地址 10000
重定位寄存器 10000
Load 2500 10100
365 12500 +
处理机 存储器 移动后
第八章 实存储器管理技术
8.3 可变分区多道管理技术
（动态分区）
? 动态重定位分配算法
? 在一个分区释放后立即移动
? 当请求得不到满足时再移动
请求分配
u.size分区
检索空闲分区链
找到
m.size≥u.size
按动态分区分配
方式进行分配
空闲分区
总和 ≥u.size
进行“紧凑” 返回分区号 及首址
无法分配
返回
y
N
Y
N
第八章 实存储器管理技术
8.4 多重分区
? 即一个程序可以占据主存中不连续的多
个分区 —— 可以解决碎片问题
? 需要硬件支持（多对界地址寄存器）
? 管理复杂
? 多重分区的思想和实现类似于虚拟段式
存储
第八章 实存储器管理技术
8.5 简单分页
? 把主存分成许多同样大小的存储块，并
把这种存储块作为存储分配的最小单位
第八章 实存储器管理技术
8.5 简单分页
? 实现方法,
? 把内存空间划分成若干大小相同的物理块，
这些物理块叫, 页架, (frame)，并依次编
以连续的页架号 0,1,2…,,
? 把用户程序的地址空间划分成与页架大小相
同的部分 (fixed size chunk)，把它们叫, 页,
（不同系统的页大小不同）
? 用户的逻辑地址表示为一个数对（ p,d），
其中 p是页号,d是页内相对地址
第八章 实存储器管理技术
8.5 简单分页
? 实现方法,
? 给定虚地址（逻辑地址） A，页面大小 L，则
p=INT[A/L],d=[A] mod L，其中 INT是向
下取整,mod是取余。
? 例如 L=2KB,A=2506B，则 p=1,d=506，
表示为 (1,506)
第八章 实存储器管理技术
8.5 简单分页
? 主存分配
? 把用户程序的任一页分配到内存中的任一帧，
从而实现非连续的内存分配。
? 问题
? 如何管理、如何进行地址变换。
第八章 实存储器管理技术
8.5 简单分页
进程 A页表
0 0
页号 块号
1 1
2 4
3 5
4 8
5 9
…… ……
0
1
2
3
4
5
6
7
8
内存
9
程序 A
0页
1页
2页
3页
4页
5页
n页
程序 B
0页
1页
2页
3页
4页
5页
m页
进程 B页表
0 2
页号 块号
1 3
2 6
3 7
…… ……
页表：实现页号到物理块号的映射。
第八章 实存储器管理技术
8.5 简单分页
? 地址组成：页号 P+(页内地址 )位移量 d
例如,32位地址,0~11为偏移量,12~31为
页号，最大可以有 1M页，每页 4KB 。
地址结构,
页号 P 位移量 d
12 11 0 31
第八章 实存储器管理技术
8.5 简单分页
? 页面大小的确定
? 分页系统中，页面的大小是由硬件的地址结构
所决定的。机器确定、页面大小就确定。
? 通常页面大小采用 2的幂次（为什么？）
? 影响因素,
? 页面 ↓→ 内部碎块 ↓,内存的利用率 ↑
? 页面 ↓→ 页表 ↑,占用内存 ↑
? 页面 ↓→ 页面的换出换入效率 ↓ 。
第八章 实存储器管理技术
8.5 简单分页
计算机类型 页面大小 (B)
IBM AS/400
VAX
Intel 80386
Motorola 68030
512
512
4096
4096
常见机型页面
第八章 实存储器管理技术
8.5 简单分页
? 地址转换
? 分页存储系统中，地址变换机构的任务是把逻辑地
址中的页号转换为内存中物理块的块号。
? 注意：页面大小与页框大小一致，无须进行页内地
址转换。
? 实现转换：借助于页表。
? 页表的实现,
? 寄存器：变换速度快、成本高，适应小型系统。
? 页表驻留在内存：速度较低、成本低，适应大系统。
第八章 实存储器管理技术
8.5 简单分页
? 地址转换实现
? 将逻辑地址的页号取出
? 以页号为索引查找该进程的页表，找出和该
页号对应的页架号
? 用页架号和逻辑地址的页内相对地址拼接，
得到的就是物理地址
第八章 实存储器管理技术
8.6 简单分段
? 分段管理思想的引入
? 在分页管理中，只按页面大小划分程序，没
有考虑程序的逻辑功能结构
? 一个程序包含多个逻辑上相对独立的功能模
块，也可能包含多个子程序，这些模块或者
子程序完成相对独立的功能
? 在分页系统中，一个逻辑段可能被分到不同
的页内，不利于执行
第八章 实存储器管理技术
8.6 简单分段
? 分段的实现
? 把作业的地址空间按逻辑功能划分若干段，
每一段定义一组逻辑信息：段名、段的长度
? 段名：用段号来替代。
? 段的长度：不确定，由相应的逻辑信息组的长度
决定。
? 逻辑地址,Segment Number Offset
31 16 15 0
64K个段 64KB长度
第八章 实存储器管理技术
8.6 简单分段
? 主存分配
? 以段为单位，每一段分配一个连续的主存分
区，一个程序的各段所分到的主存分区不要
求是连续的
? 请考虑：程序的段是在什么时候由谁划分出
来的？
第八章 实存储器管理技术
8.6 简单分段
? 段表：记录逻辑段与内存物理位置的对应映射
关系。
段号 段长 基址
0 30K 40K
1 20K 80K
2 15K 120K
段表
(MAIN)=0
(x)=1
(D)=2
内存空间
作业空间
0 (MAIN)=0
0 (X)=1
0 (D)=2
40K
80K
120K
第八章 实存储器管理技术
8.6 简单分段
? 段的地址转换
段表始址 段表长度
段表寄存器
2
段号 段内偏移量
100
+
6K 1K 0
4K 600 1
8K 500 2
9200 200 3
基址 段长 段号
段表
+
越界中断
+
8292
物理地址
0
1
2
内存空间
8K
第八章 实存储器管理技术
? 分页与分段的区别
分块方式 使用 碎片 长度 目的
分页存储
管理
物理分块，
系统决
定
对程序员
是不可
见，使
用简单
每个进程
只有一
个内部
碎片，
大小不
超过 1
页
固定 提高内存
的利用
率
分段存储
管理
逻辑分块，
大小与
信息块
有关，
由编译
系统划
分
对程序员
可见，
使用方
便，但
难度大
每个进程
会产生
多个外
部碎片
不确定 便于信息
保护与
共享，
方便用
户
第八章 实存储器管理技术
? 实存储管理技术的特点：程序要整体装
入，一个程序在没有全部装入主存之前
不能运行。
? 请同学们课后分析一下这种技术的优缺
点
第八章 实存储器管理技术
8.7 内核主存管理
? 即对操作系统内核程序占用的主存区的
管理
? 现代操作系统的内核程序大都驻留在 ROM里
? 但是一些系统内核程序在运行时，需要一些
存储空间（属于内核存储区）存放临时信息
? 预留一定大小的空间
? 动态管理 —— 内核主存分配器
第八章 实存储器管理技术
8.7 内核主存管理
? 二次幂空闲表分配器
? 伙伴系统
? SVR3延迟伙伴算法
第八章 实存储器管理技术
8.7 内核主存管理
（二次幂空闲表分配器）
? 把内核存储区分成一些固定大小的空线块，如
1KB,2KB等，每个空闲块有一个字长的头结构
（不属于可用空间）用来存放链指针
? 使用一组空闲表，每个表存放某一特定尺寸的
空闲块
? 内核程序需要存储区时，根据它需要的大小给
它分配一个合适的空闲块
? 见 Page162 图 8.14
第八章 实存储器管理技术
8.7 内核主存管理
（二次幂空闲表分配器）
? 优点
? 快速分配和式访主存
? 缺点
? 因为要存放头结构，浪费空间
? 存储块不能合并，不能满足对大主存块的要
求
第八章 实存储器管理技术
8.7 内核主存管理 （伙伴系统）
? 思想
? 通过不断的对分大主存块来获得小主存块，
并尽可能合并空闲块，但必须在伙伴的关系
上才能合并
? 伙伴：当一个主存块被对分后，每一部分称
为另一部分的伙伴
第八章 实存储器管理技术
8.7 内核主存管理 （伙伴系统）
? 概念
? 伙伴系统是通过对分大空闲块来获得小空闲块，对
分生成的两个空闲块互称伙伴，合并必须在伙伴之
间进行
? 系统中规定最小分配单位，通常为 32byte或 64byte
? 系统使用位图位互主存中每一个最小单位的使用情
况,1表示正在使用,0表示空闲
? 系统为每一种可能大小的空闲块维护一个空闲链表
? 缺点
? 会有频繁的对分和合并
第八章 实存储器管理技术
8.7 内核主存管理 （伙伴系统）
? 概念
? 系统启动时，只有一个大的 2次幂大小的空
闲块。
? 将请求的大小取整，然后寻找对应的空闲链
表，如果有空闲块，则分配，否则将一个大
空闲块对分，直到与请求大小相符合
? 确定伙伴的方法是根据空闲块的基地址和大
小
第八章 实存储器管理技术
1MB
A：请求 100K 128K
B：请求 240K 256K 128K
C：请求 64K 256K 128K 64K
D：请求 256K 256K 128K 64K 256K
释放 A 256K 128K 64K 256K
释放 D 256K 128K 64K
E：请求 75K 256K 128K 64K
释放 C 256K 128K
第八章 实存储器管理技术
8.7 内核主存管理
（ SVR4延迟伙伴算法）
? 为了解决伙伴算法的频繁对分和合并问
题 —— 必要时再合并
第八章 实存储器管理技术
8.7 内核主存管理
（ SVR4延迟伙伴算法）
? 合并算法
? 使用几个参数
? Ni：尺寸为 2的 i次幂的主存块数量
? Ai：尺寸为 2的 i次幂的以分配主存块数量
? Li：尺寸为 2的 i次幂的局部空闲块数量
? Gi：尺寸为 2的 i次幂的全局空闲块数量
? 局部空闲块：暂时不能合并的空闲块
? 全局空闲块：可以合并的空闲块
第八章 实存储器管理技术
8.7 内核主存管理
（ SVR4延迟伙伴算法）
? 合并算法
? 当 2i级空闲块过多时，说明下一级空闲块过
少，进行合并，合并标准,Li<=Ai
? Slack=Ai-Li=Ni-2Li-Gi
? 每个主存块类有 3种状态
? 平稳状态,Slack>=2，不需合并
? 回收状态,Slack=1，需要合并
? 加速状态,Slack=0，需要加速合并
第八章 实存储器管理技术
8.7 内核主存管理
（ SVR4延迟伙伴算法）
? 合并算法
? 当有块被释放时，将其放入空闲链表，检查
该主存块类的状态
? 平稳状态：不操作
? 回收状态：合并
? 加速状态：合并两个主存块
? 局部空闲块优先被分配使用，减少修改位图
的开销
第八章 实存储器管理技术
课后作业
? Page 147上交时间：下周
? 8.9
? 8.17
? 思考题
? 8.5
