文档介绍：动态存储管理
1
概述
可利用空间表及分配方法
边界标识法
伙伴系统
2
一、内容提要 
1．动态存储管理指的是在用户需要时给分配内存，而在用户结束使用时，系统要收回用户所占空间。
2．可利用空间表的三种结构形式：结点固定大小；分几种规格；任意大小。
3．可利用空间表的两种组织形式：目录表，链表。
4．可利用空间表的分配方式：首次拟合法，最佳拟合法，最差拟合法。
5．可利用空间表的分配和回收的两种基本实现方法：边界标识法，伙伴系统。
3
二、学****重点
1、概念：可利用空间表及分配方式，紧缩存储，伙伴系统等。
2、边界表示法的分配及回收算法。
3、伙伴系统的分配及回收算法。
4
概述
动态存储管理的基本问题是系统如何响应用户提出的“请求”
分配内存？又如何回收那些用户不再使用而“释放”的内存，以
备新的“请求”产生时重新进行分配？
占用块：已分配给用户使用的地址连续的内存区。
空闲块或可利用空间块：未曾分配的地址连续的内存区。
在系统运行的初期，整个内存区基本上分隔成两大部分：
低地址区包含若干占用块；高地址区（即分配后的剩余部分）
是一个“空闲块”。经过一段时间以后，有的用户运行结束,它
占用的内存区变成空闲块，这就使整个内存区呈现出占用块和空闲块犬牙交错的状态。(b)所示
U1 U2 U3 U4 U5 U6 U7 U8
(b) 系统运行若干时间之后
动态存储分配过程中的内存状态
(a) 系统运行初期
U1 U2 U3 U4 U5 U6 U7 U8
5
此时，若又有新的用户进入系统请求分配内存，那系统将：

策略一：系统继续从高地址的空闲块中进行分配，而不理会
已分配给用户的内存区是否已空闲，直到分配无法进行（即剩余
的空闲块不能满足分配的请求）时，系统才去回收所有用户不再
使用的空闲块，并且重新组织内存，将所有空闲的内存区连接在
一起成为一个大的空闲块。
策略二：用户一旦运行结束，便将它所占内存区释放成为空
闲块，同时，每当新的用户请求分配内存时，系统需要巡视整个
内存区中所有空闲块，并从中找出一个“合适”的空闲块分配之。
在此策略下，系统需建立一张记录所有空闲块的“可利用空间表”，
此表的结构可以是“目录表”，也可以是“链表”。。
25 000 39 000
0 10 000 31 000 59 000 99 999
(a) 内存状态
6
(b) 目录表（初始地址，空闲块大小，使用情况）
起始地址内存块大小使用情况
10 000 15 000 空闲
31 000 8 000 空闲
59 000 41 000 空闲
(c) 链表（分配和回收即删除或插入一个结点）
动态存储管理过程中的内存状态可利用空间表
av
10 000 31 000 59 000
0 15 000 0 8 000 0 41 000 ^
7
可利用空间表及分配方法
可利用空间表亦称作“存储池”。根据系统运行的不同情况，可利用空间表有下列3种不同的结构形式：
（1）系统运行期间所有用户请求分配的存储量大小相同。
对此类系统，在系统开始运行时将归它使用的内存区按所需大小分割成若干大小相同的块，然后用指针链接成一个可利用空间表。这种情况下的可利用空间表实质上是一个链栈:
内存分配：将可利用空间表中的第一个结点分配给用户。
内存回收:将用户释放的空闲块插入可利用空间表的表头。
（2）系统运行期间所有用户请求分配的存储量有若干种大小的规格。
对此类系统，一般情况下是建立若干个可利用空间表，同一链表中的结点大小相同。
8
例如，某动态存储管理系统中的用户请求分配2个字、4个字或8个字的内存块，则系统建立3个结点大小分别为3个字、5个字或9个字的链表，它们的表头指针分别为av2、av4和av8。。
tag type link
value
0 结点大小为2个字
ty