一条小河上有一座独木桥，现河东
河西都有人要过桥，同一方向的可
连续过桥；某方向有人过桥时另一
方向的人须等待。如果把每个过桥
者看作一个进程，为保证安全，用
信号量协调他们之间的关系。
全局变量
enumber,河东过桥者人数，初值为 0
wnumber,河西过桥者人数，初值为 0
信号量
mutex1,访问变量 enumber的互斥信号量
mutex2,访问变量 wnumber的互斥信号量
bridge,是否允许过桥
初值为 1
河东过桥者进程
wait ( mutex1 ) ;
enumber,= enumber + 1;
if enumber = 1 then wait ( bridge ) ;
signal ( mutex1 ) ;
过桥
wait ( mutex1 ) ;
enumber = enumber – 1 ;
if enumber = 0 then signal ( bridge ) ;
signal ( mutex1 ) ;
河西过桥者进程
wait ( mutex2 ) ;
wnumber,= wnumber + 1;
if wnumber = 1 then wait ( bridge ) ;
signal ( mutex2 ) ;
过桥
wait ( mutex2 ) ;
wnumber = wnumber – 1 ;
if wnumber = 0 then signal ( bridge ) ;
signal ( mutex2 ) ;
第八章 实存储器管理技术
1、引言
2、固定分区
3、可变分区的多道管理技术
4、多重分区管理
5、简单分页
6、简单分段
7、内核主存管理
8.1 引言
一,存储体系
存储器的层次结构,
Cache
主存
磁盘
二、主存管理
1、主存分配
系统区：用于存放操作系统
用户区：用于装入并存放用户程序
和数据
2,存储管理目的
充分利用内存，为并发执行提供存储基础
自动装入用户程序
解决程序空间比实际内存空间大的问题
3、存储管理的任务
?内存空间的管理、分配与回收
?存储共享
?存储保护与安全
?内存“扩充”
?地址映射（地址重定位，地址变换）
8.2 固定分区
一、基本概念
预先把可分配的主存空间分割成若干个连续
区域（称为分区）。每个分区的大小可以相
同也可以不同，但分区大小固定不变，每个
分区装一个且只能装一个作业
分区 4
分区 3
分区 2
分区 1
操作系统
二、内存管理
设置存储分块表 MBT,用于描述内存
各分区使用情况的数据结构。
分区号 大小 位置 状态
1 8K 512K 使用
2 32K 520K 使用
3 32K 552K 未用
4 128K 584K 未用
5 512K 712K 使用
三、存储分配
要求 XK大小分区
取存储分块表第一项
表结束？
该分区未使用？
分区大小 ?XK？
状态位置置“使用”
向用户返回分区号
Y
N
Y
N
N
Y
无法分配
取下一项
四、存储回收
给出分区号：把状态为由使用 ?未用
五、存储保护和重定位
? 存储保护,
使用上下界保护
使用存储键保护 ——分区号即为存储键
? 重定位：静态地址重定位
六、优缺点
? 优点：软件算法和硬件要求都比较简单
? 缺点：主存利用率不高
内部碎片：一个需要 M个字的作业可能包含在
N个字的存储空间（ N?M）,则 N-
M为内部碎片
外部碎片：当某个存储空间空闲时，但对于等
待的作业又太小，该空闲块为外部碎
片。
8.3 可变分区的多道管理技术
? 可变分区存储管理的概念
? 数据基
? 可变分区的分配与释放
? 存储分配算法（最佳、最先、最坏适应法）
? 存储器的紧缩与程序的浮动
? 动态重定位的可变分区多道管理
一、可变分区存储管理的概念
在系统运行过程中建立分区，并且分区的大
小和作业相符。
特点,
? 分区个数可变，分区大小可变
? 主存中分布着个数和大小都是变化的自由
分区或碎片
二、数据库
记录空闲区起始地址和长度
? 存储分块表
? 分开设置两个存储管理表：已分分区表
和自由分区表
? 自由存储块链
两个存储管理表
区号 大小 位置 状态 区号 大小 位置 状态
1 8K 312K 已分 1 32K 352K 空闲
2 32K 320K 已分 2 空
3 空 3 520K 504K 空闲
4 120K 384K 已分
UBT FBT
自由存储块链
在每个已分配的分区和未分配的空白区中
附上表格，然后用地址指针把所有空白区
链接起来。
在每个分区中，前末两个字用来存入下列
有关信息,
? 状态信息,1 已分配 0 空白区
? 大小
? 指针：只有空白区有
1 N+2
1 N+2
容纳 N个字的作业
0 N+2
0 N+2
N个字可用
前向指针
后向指针
已分分区 自由分区
三、分配和 回收 算法
内存分配, 动态分配
内存回收：当某一块归还后，前后空间合并，修改内
存空闲块表
分配步骤,
?从未分配表中找到一个足以容纳该作业的可用空白
区（未分配区）
?如果这个空白区比所要求的大，则将它分成两部分：
一部部分成为已经分配的分区，剩余部分仍为空白
区
?修改两个存储表的有关信息，并回送一个所分配分
区的序号或该分区的始址
回收步骤,
?检查回收的分区是否与空白区相邻接，如有
则加以合并，使之成为一个连续的空白区
?修改两张存储表
F1 空白
R 回收 F1
F2 F1 空白 R 回收 F1
F2 空白
R 回收
F1 空白
四、存储分配算法
? 最先适应法
? 最佳适应法
? 最坏适应法
1、最先适应法
分配原则：最先适应法要求按空闲区首址
递增的次序组织空闲区表或队
列。当接到内存申请时，查空
闲块表，找到第一个不小于请
求的空闲块，将其分割并分配。
优点,释放某一存储区，若与空闲区
相邻，则合并后，无须改变该
区在队列的位置。尽可能利用
低地址，高地址处留有较大的
空间。
2、最佳适应法
分配原则：按空闲区大小递增的次序组织空
闲区表或队列。 接到内存申请时,
在空闲块表中找到一个不小于请
求的最小空块进行分配
优点,若系统中存在一个和申请区大小
相同的空闲区，则必定被选中。
若不存在这样的空闲区，选中的
是满足要求的最小空闲区。 用最
小空间满足要求
缺点,容易产生碎片。
3、最坏适应法
分配原则：最坏适应法要求空闲区按大小
递减的次序组织空闲区表或队
列。 接到内存申请时，在空闲
块表中找到一个不小于请求的
最大空块进行分配
优点,当程序装入内存中最大的空闲
区剩下的空闲区较大，还能装
较大的程序。 当分割后空闲块
仍为较大空块
例
有一作业序列，要求用最先，最佳，最坏
适应法分析哪种算法最合适。
a
b
c
d
e
f
g
h
16k
14k
5k
30k
作业 A要求 13K
作业 B要求 15K
作业 C要求 30K
内存分布情况
最先适应法
始址 大小 始址 大小 始址 大小
a 16K a+13k 3k a+13k 3k
c 14K c 14K c 14K
e 5K e 5K e 5K
g 30k g 30k g+15K 15K
A B C
无
法
分
配
最佳适应法
始址 大小 始址 大小 始址 大小
e 5k c+13k 1k c+13k 1k
c 14k e 5k a+15k 1k
a 16k a 16k e 5K
g 30k g 30k g 30k
A B
始址 大小
c+13k 1k
a+15k 1k
e 5K
C
最坏适应法
始址 大小 始址 大小 始址 大小
g 30k g+13k 17k a 16k
a 16k a 16k c 14k
c 14k c 14k e 5k
a 5k a 5k g+28K 2k
A B
C
无
法
分
配
五、存储器的紧缩和程序的浮动
? 碎片问题和存储器的紧缩
? 程序的浮动
六、动态重定位的可变分区多道管理
? 动态重定位
? 动态重定位的硬件支持和软件算法
硬件支持：定位寄存器、加法器,
界地址寄存器
软件算法,1.在某个分区被释放后立
即紧缩。
2.找不到足够大的空闲区
再进行紧缩。
? 优点,
– 主存的使用更加灵活、更加有效
– 便于实现动态链接
– 提高了主存的利用率
? 缺点,
– 需要附加的硬件支持
– 实现存储管理的软件算法比较复杂
8.4 多重分区（多对界地址）管理
目前采用的多重分区分配，一般允许给一个
作业分配二个分区，分别称为 0界区和 1界区,
且各自由一对上、下界寄存器加以限定，采
用动态重定位技术，利用下界寄存器作为重
定位寄存器，而其上界可供检查地址越界用。
8.5 简单分页
? 基本概念
? 地址转换过程
一、分页存储管理的基本概念
? 等分主存：页架、页架号
? 用户逻辑地址空间的分页：页、页号
? 逻辑地址的表示：（页号 p,页内地址 d）
? 分配原则：以页架为基本分配单位
? 页表：页号、页架号
? 分页系统中的地址结构,
– 页号 ?最大页数
– 页内地址 ?页架的大小
? 页面尺寸应是 2的幂
二、分页系统中的地址转换
? 分页系统中的地址转换是动态地址重定位。
? 转换过程,1,将逻辑地址分离出页号，页内地址。
2,以页架号为索引查页表，得该页在
内存的页架号
3,把页架号，页内地址（二进制形式）
拼接成物理地址。
分页系统中的地址转换举例
一分页系统，页架的大小为 1KB,逻辑地
址为 4101（十进制数）页表如下。
要求把逻辑地址转换成物理地址
页表
0 15
1 17
2 20
3 39
4 18
5 22
?4101=0001000000000101B 得 P=4,d=5
?由 P=4查 P?=18
?物理地址拼接 000100100000000101B=4805H
P d
P? d
简单分页的优缺点
? 优点：解决碎片（仅存最后一页页内零头）
较好利用内存空间。
? 缺点：页面的划分对用户是透明的。
最后一页页内零头。
8.6 简单分段
? 基本概念
? 地址转换过程
一、分段存储管理的基本概念
? 进程的逻辑地址空间：按自然逻辑关系分
段。
? 程序的地址结构：（段号 s,段内地址 w）
? 主存分配：以段为单位分配，一个段占连
续主存空间，各段可不连续。
? 段表：段号、段的长度、段在主存中的起
始地址
,,,
0
S
工作区段 [B]
主程序段 [M]
.,,
,
.,
0
E
P
子程序段 [X]
0
K
.,,
CALL [X] [E]
.,,
.,,
.,,
CALL [Y] [F]
CALL [A] 116
.,,
,
.,
0
F
L
子程序段 [Y]
0
116
N
数组 [A]
12345
.,,
操作系统
,
,
,
,
,
B 0 S
A 0 N
Y 0 L
X 0 P
M 0 K
逻辑段号
0
1
2
3
4
作业 1的地址空间
1000
3200
5000
6000
8000
P
K
S
L
N
主存
K 3200
P 1500
L 6000
N 8000
S 5000
长度 段地址
0
1
2
3
4
操作系统
逻辑地址
内存划分
内存空间被动态的划分为若干个长度
不相同的区域，这些区域被称为物
理段，每个物理段由起始地址和长
度确定
段号 段内地址
二、分段系统中的地址转换
? 把逻辑地址中段号取出来。
? 按段号查找段表：取段长，段首地址。
? 判断段内地址 ?段长？
不是，产生越界中断
是，访问合法
? 把段内地址加上段首址形成实地址
二、分段系统中的地址转换
段号 段内地址
段表
S′ l
S w
s
+
实地址
虚地址
举例
段长 段起始地址
0 200 500
1 400 1000
2 100 1400
3 900 2000
虚地址：（ 0,100），（ 1,500）完成实地址转换
段表
1,600
2,越界
8.7 内核主存管理
? 内核主存管理概述
? 2次幂空闲表分配器
? 伙伴系统
? SVR4的延迟伙伴系统
一、内核主存管理概述
? 内核主存管理由内核主存分配器实现
? 内核主存分配器功能：为不同的内核子系
统提供各种尺寸的主存块。
? 常用的内核主存分配器,
（ 1） 2次幂空闲表分配器
（ 2）伙伴系统
（ 3） SVR4的延迟伙伴系统
二,2次幂空闲表分配器
本方法使用一组空闲块链表，每个链表存
放某一特定尺寸的空闲块，空闲块的大小
均为 2的整数幂。
优点：简单，分配和释放都是快速的。
缺点：内存的利用率低。
三、伙伴系统
? 伙伴系统是将空闲块合并技术与 2次幂算法相结合的分
配方法
? 伙伴系统的实现：对分大主存块以获得小主存块，并尽
可能合并空闲块，但合并空闲块必须在伙伴的关系。
? 优点,
（ 1）主存的分配和回收都很快，特别适用于合并。
（ 2） 主存可以以不同的尺寸再利用，具有很好的灵活性。
（ 3）与分页系统互借页面比较方便。
? 缺点：经常要进行合并分开。
四,SVR4的延迟伙伴算法
该算法对伙伴系统的改进，即延迟合并操
作直到必要时才合并。
算法,slack=Ai-Li=Ni-2Li-Gi(Ni=Ai+Li+Gi)
其中,Ni尺寸为 2 的主存块当前总数
Ai尺寸为 2 的 已分配的主存块当前总数
Li尺寸为 2 局部空闲块当前总数
Gi尺寸为 2 全局空闲块当前总数
slack?2 平稳状态，不需要合并
slack=1 回收 状态，需要合并
slack=0 加速 状态，加快合并
i
i
i
i
i
河西都有人要过桥，同一方向的可
连续过桥；某方向有人过桥时另一
方向的人须等待。如果把每个过桥
者看作一个进程，为保证安全，用
信号量协调他们之间的关系。
全局变量
enumber,河东过桥者人数，初值为 0
wnumber,河西过桥者人数，初值为 0
信号量
mutex1,访问变量 enumber的互斥信号量
mutex2,访问变量 wnumber的互斥信号量
bridge,是否允许过桥
初值为 1
河东过桥者进程
wait ( mutex1 ) ;
enumber,= enumber + 1;
if enumber = 1 then wait ( bridge ) ;
signal ( mutex1 ) ;
过桥
wait ( mutex1 ) ;
enumber = enumber – 1 ;
if enumber = 0 then signal ( bridge ) ;
signal ( mutex1 ) ;
河西过桥者进程
wait ( mutex2 ) ;
wnumber,= wnumber + 1;
if wnumber = 1 then wait ( bridge ) ;
signal ( mutex2 ) ;
过桥
wait ( mutex2 ) ;
wnumber = wnumber – 1 ;
if wnumber = 0 then signal ( bridge ) ;
signal ( mutex2 ) ;
第八章 实存储器管理技术
1、引言
2、固定分区
3、可变分区的多道管理技术
4、多重分区管理
5、简单分页
6、简单分段
7、内核主存管理
8.1 引言
一,存储体系
存储器的层次结构,
Cache
主存
磁盘
二、主存管理
1、主存分配
系统区：用于存放操作系统
用户区：用于装入并存放用户程序
和数据
2,存储管理目的
充分利用内存，为并发执行提供存储基础
自动装入用户程序
解决程序空间比实际内存空间大的问题
3、存储管理的任务
?内存空间的管理、分配与回收
?存储共享
?存储保护与安全
?内存“扩充”
?地址映射（地址重定位，地址变换）
8.2 固定分区
一、基本概念
预先把可分配的主存空间分割成若干个连续
区域（称为分区）。每个分区的大小可以相
同也可以不同，但分区大小固定不变，每个
分区装一个且只能装一个作业
分区 4
分区 3
分区 2
分区 1
操作系统
二、内存管理
设置存储分块表 MBT,用于描述内存
各分区使用情况的数据结构。
分区号 大小 位置 状态
1 8K 512K 使用
2 32K 520K 使用
3 32K 552K 未用
4 128K 584K 未用
5 512K 712K 使用
三、存储分配
要求 XK大小分区
取存储分块表第一项
表结束？
该分区未使用？
分区大小 ?XK？
状态位置置“使用”
向用户返回分区号
Y
N
Y
N
N
Y
无法分配
取下一项
四、存储回收
给出分区号：把状态为由使用 ?未用
五、存储保护和重定位
? 存储保护,
使用上下界保护
使用存储键保护 ——分区号即为存储键
? 重定位：静态地址重定位
六、优缺点
? 优点：软件算法和硬件要求都比较简单
? 缺点：主存利用率不高
内部碎片：一个需要 M个字的作业可能包含在
N个字的存储空间（ N?M）,则 N-
M为内部碎片
外部碎片：当某个存储空间空闲时，但对于等
待的作业又太小，该空闲块为外部碎
片。
8.3 可变分区的多道管理技术
? 可变分区存储管理的概念
? 数据基
? 可变分区的分配与释放
? 存储分配算法（最佳、最先、最坏适应法）
? 存储器的紧缩与程序的浮动
? 动态重定位的可变分区多道管理
一、可变分区存储管理的概念
在系统运行过程中建立分区，并且分区的大
小和作业相符。
特点,
? 分区个数可变，分区大小可变
? 主存中分布着个数和大小都是变化的自由
分区或碎片
二、数据库
记录空闲区起始地址和长度
? 存储分块表
? 分开设置两个存储管理表：已分分区表
和自由分区表
? 自由存储块链
两个存储管理表
区号 大小 位置 状态 区号 大小 位置 状态
1 8K 312K 已分 1 32K 352K 空闲
2 32K 320K 已分 2 空
3 空 3 520K 504K 空闲
4 120K 384K 已分
UBT FBT
自由存储块链
在每个已分配的分区和未分配的空白区中
附上表格，然后用地址指针把所有空白区
链接起来。
在每个分区中，前末两个字用来存入下列
有关信息,
? 状态信息,1 已分配 0 空白区
? 大小
? 指针：只有空白区有
1 N+2
1 N+2
容纳 N个字的作业
0 N+2
0 N+2
N个字可用
前向指针
后向指针
已分分区 自由分区
三、分配和 回收 算法
内存分配, 动态分配
内存回收：当某一块归还后，前后空间合并，修改内
存空闲块表
分配步骤,
?从未分配表中找到一个足以容纳该作业的可用空白
区（未分配区）
?如果这个空白区比所要求的大，则将它分成两部分：
一部部分成为已经分配的分区，剩余部分仍为空白
区
?修改两个存储表的有关信息，并回送一个所分配分
区的序号或该分区的始址
回收步骤,
?检查回收的分区是否与空白区相邻接，如有
则加以合并，使之成为一个连续的空白区
?修改两张存储表
F1 空白
R 回收 F1
F2 F1 空白 R 回收 F1
F2 空白
R 回收
F1 空白
四、存储分配算法
? 最先适应法
? 最佳适应法
? 最坏适应法
1、最先适应法
分配原则：最先适应法要求按空闲区首址
递增的次序组织空闲区表或队
列。当接到内存申请时，查空
闲块表，找到第一个不小于请
求的空闲块，将其分割并分配。
优点,释放某一存储区，若与空闲区
相邻，则合并后，无须改变该
区在队列的位置。尽可能利用
低地址，高地址处留有较大的
空间。
2、最佳适应法
分配原则：按空闲区大小递增的次序组织空
闲区表或队列。 接到内存申请时,
在空闲块表中找到一个不小于请
求的最小空块进行分配
优点,若系统中存在一个和申请区大小
相同的空闲区，则必定被选中。
若不存在这样的空闲区，选中的
是满足要求的最小空闲区。 用最
小空间满足要求
缺点,容易产生碎片。
3、最坏适应法
分配原则：最坏适应法要求空闲区按大小
递减的次序组织空闲区表或队
列。 接到内存申请时，在空闲
块表中找到一个不小于请求的
最大空块进行分配
优点,当程序装入内存中最大的空闲
区剩下的空闲区较大，还能装
较大的程序。 当分割后空闲块
仍为较大空块
例
有一作业序列，要求用最先，最佳，最坏
适应法分析哪种算法最合适。
a
b
c
d
e
f
g
h
16k
14k
5k
30k
作业 A要求 13K
作业 B要求 15K
作业 C要求 30K
内存分布情况
最先适应法
始址 大小 始址 大小 始址 大小
a 16K a+13k 3k a+13k 3k
c 14K c 14K c 14K
e 5K e 5K e 5K
g 30k g 30k g+15K 15K
A B C
无
法
分
配
最佳适应法
始址 大小 始址 大小 始址 大小
e 5k c+13k 1k c+13k 1k
c 14k e 5k a+15k 1k
a 16k a 16k e 5K
g 30k g 30k g 30k
A B
始址 大小
c+13k 1k
a+15k 1k
e 5K
C
最坏适应法
始址 大小 始址 大小 始址 大小
g 30k g+13k 17k a 16k
a 16k a 16k c 14k
c 14k c 14k e 5k
a 5k a 5k g+28K 2k
A B
C
无
法
分
配
五、存储器的紧缩和程序的浮动
? 碎片问题和存储器的紧缩
? 程序的浮动
六、动态重定位的可变分区多道管理
? 动态重定位
? 动态重定位的硬件支持和软件算法
硬件支持：定位寄存器、加法器,
界地址寄存器
软件算法,1.在某个分区被释放后立
即紧缩。
2.找不到足够大的空闲区
再进行紧缩。
? 优点,
– 主存的使用更加灵活、更加有效
– 便于实现动态链接
– 提高了主存的利用率
? 缺点,
– 需要附加的硬件支持
– 实现存储管理的软件算法比较复杂
8.4 多重分区（多对界地址）管理
目前采用的多重分区分配，一般允许给一个
作业分配二个分区，分别称为 0界区和 1界区,
且各自由一对上、下界寄存器加以限定，采
用动态重定位技术，利用下界寄存器作为重
定位寄存器，而其上界可供检查地址越界用。
8.5 简单分页
? 基本概念
? 地址转换过程
一、分页存储管理的基本概念
? 等分主存：页架、页架号
? 用户逻辑地址空间的分页：页、页号
? 逻辑地址的表示：（页号 p,页内地址 d）
? 分配原则：以页架为基本分配单位
? 页表：页号、页架号
? 分页系统中的地址结构,
– 页号 ?最大页数
– 页内地址 ?页架的大小
? 页面尺寸应是 2的幂
二、分页系统中的地址转换
? 分页系统中的地址转换是动态地址重定位。
? 转换过程,1,将逻辑地址分离出页号，页内地址。
2,以页架号为索引查页表，得该页在
内存的页架号
3,把页架号，页内地址（二进制形式）
拼接成物理地址。
分页系统中的地址转换举例
一分页系统，页架的大小为 1KB,逻辑地
址为 4101（十进制数）页表如下。
要求把逻辑地址转换成物理地址
页表
0 15
1 17
2 20
3 39
4 18
5 22
?4101=0001000000000101B 得 P=4,d=5
?由 P=4查 P?=18
?物理地址拼接 000100100000000101B=4805H
P d
P? d
简单分页的优缺点
? 优点：解决碎片（仅存最后一页页内零头）
较好利用内存空间。
? 缺点：页面的划分对用户是透明的。
最后一页页内零头。
8.6 简单分段
? 基本概念
? 地址转换过程
一、分段存储管理的基本概念
? 进程的逻辑地址空间：按自然逻辑关系分
段。
? 程序的地址结构：（段号 s,段内地址 w）
? 主存分配：以段为单位分配，一个段占连
续主存空间，各段可不连续。
? 段表：段号、段的长度、段在主存中的起
始地址
,,,
0
S
工作区段 [B]
主程序段 [M]
.,,
,
.,
0
E
P
子程序段 [X]
0
K
.,,
CALL [X] [E]
.,,
.,,
.,,
CALL [Y] [F]
CALL [A] 116
.,,
,
.,
0
F
L
子程序段 [Y]
0
116
N
数组 [A]
12345
.,,
操作系统
,
,
,
,
,
B 0 S
A 0 N
Y 0 L
X 0 P
M 0 K
逻辑段号
0
1
2
3
4
作业 1的地址空间
1000
3200
5000
6000
8000
P
K
S
L
N
主存
K 3200
P 1500
L 6000
N 8000
S 5000
长度 段地址
0
1
2
3
4
操作系统
逻辑地址
内存划分
内存空间被动态的划分为若干个长度
不相同的区域，这些区域被称为物
理段，每个物理段由起始地址和长
度确定
段号 段内地址
二、分段系统中的地址转换
? 把逻辑地址中段号取出来。
? 按段号查找段表：取段长，段首地址。
? 判断段内地址 ?段长？
不是，产生越界中断
是，访问合法
? 把段内地址加上段首址形成实地址
二、分段系统中的地址转换
段号 段内地址
段表
S′ l
S w
s
+
实地址
虚地址
举例
段长 段起始地址
0 200 500
1 400 1000
2 100 1400
3 900 2000
虚地址：（ 0,100），（ 1,500）完成实地址转换
段表
1,600
2,越界
8.7 内核主存管理
? 内核主存管理概述
? 2次幂空闲表分配器
? 伙伴系统
? SVR4的延迟伙伴系统
一、内核主存管理概述
? 内核主存管理由内核主存分配器实现
? 内核主存分配器功能：为不同的内核子系
统提供各种尺寸的主存块。
? 常用的内核主存分配器,
（ 1） 2次幂空闲表分配器
（ 2）伙伴系统
（ 3） SVR4的延迟伙伴系统
二,2次幂空闲表分配器
本方法使用一组空闲块链表，每个链表存
放某一特定尺寸的空闲块，空闲块的大小
均为 2的整数幂。
优点：简单，分配和释放都是快速的。
缺点：内存的利用率低。
三、伙伴系统
? 伙伴系统是将空闲块合并技术与 2次幂算法相结合的分
配方法
? 伙伴系统的实现：对分大主存块以获得小主存块，并尽
可能合并空闲块，但合并空闲块必须在伙伴的关系。
? 优点,
（ 1）主存的分配和回收都很快，特别适用于合并。
（ 2） 主存可以以不同的尺寸再利用，具有很好的灵活性。
（ 3）与分页系统互借页面比较方便。
? 缺点：经常要进行合并分开。
四,SVR4的延迟伙伴算法
该算法对伙伴系统的改进，即延迟合并操
作直到必要时才合并。
算法,slack=Ai-Li=Ni-2Li-Gi(Ni=Ai+Li+Gi)
其中,Ni尺寸为 2 的主存块当前总数
Ai尺寸为 2 的 已分配的主存块当前总数
Li尺寸为 2 局部空闲块当前总数
Gi尺寸为 2 全局空闲块当前总数
slack?2 平稳状态，不需要合并
slack=1 回收 状态，需要合并
slack=0 加速 状态，加快合并
i
i
i
i
i
