,数据结构,
第八章 动态存储管理第八章 动态存储管理第 2页
可利用空间表及分配方法
边界标识法
伙伴系统
无用单元收集
存储紧缩内容和要求可利用空间表、边界标识法、伙伴系统和无用单元收集。
要求掌握可利用空间表及分配办法。
重点可利用空间表及分配。
内容和要求第八章 动态存储管理第 3页动态存储管理的基本问题及方法存储管理是一个既复杂而又重要的问题。在后续课程 —— 操作系统 和 编译技术 （或方法、原理）中，将对其作较深入的研究。在数据库技术中，也涉及大量有关存储管理的问题。 本章仅就动态存储管理方面一些基本技术进行讨论。
在以往的算法描述中，有关存储分配请求、存储回收等项工作往往一带而过，好比是存储,自动满足,又
,自动回收,。偶尔亦考虑某一数据结构下判断是否溢出或者是否释放内存空间等问题。这是必要的，主要是为了把当时的重点和核心放在研究数据的逻辑特性、物理表示、算法描述与分析上，而对有关存储管理的问题作了一定的简化。
第八章 动态存储管理第 4页动态存储管理的基本问题
(1) 如何按用户提出的“请示”分配内存？
(2) 如何回收那些用户不再使用而“释放”的内存，以备新的“请示”产生时重新进行分配？
(1) 由用户来解决；
(2) 由系统来解决；
(3) 由系统和用户共同解决。
存储管理问题的解决途径动态存储管理的基本问题及方法第八章 动态存储管理第 5页在计算机系统中，存储管理的分级
(1) 操作系统为进程分配所需要的存储空间，以便能在机器上运行。一旦运行结束从系统撤离时，操作系统就回收进程所使用的空间。此类存储管理问题将在,操作系统,课程中讨论 。
动态存储管理的基本问题及方法
(2) 进程对数据结构分配及回收存储空间，例如编译进程为变量、数组以及各种表格分配、回收空间 。 此类存储管理问题将在,编译方法,课程中讨论 。
(3) 数据结构中，对某结构中的元素或子结构分配、回收存储空间。此类存储管理问题将是,数据结构,课程研究的范畴
。
下面仅限于在数据结构一级上研究存储管理的方法。但其基本思想和方法亦完全适用于其他两个级别。
第八章 动态存储管理第 6页一些有关存储管理的重要问题
(1) 由谁来负责存储空间的分配与回收？是 用户自身,还是由系统的一个专门子系统 为用户分配并发现不再使用的空间而加以回收？
(2) 分配和释放存储空间的单位是 相同还是有大有小？
(3) 系统 何时回收 空闲的空间？是 及时回收 还是 定期回收 或 当存储空间用完时 才去回收？
(4) 是否考虑存储 碎片的紧凑 问题？
(5) 当请示存储空间时，满足该请示的最好 分配策略 是什么？
是寻找容量大致相当的存储块给予，还是不加选择地依次给一块至少能满足的空间？
(6) 怎样 安排空闲存储块的次序？随机排列或按地址排列或按容量大小排列？
动态存储管理的基本问题及方法第八章 动态存储管理第 7页
u1 u2 u3 u4 u5 u6 u7 u8
u1 u3 u4 u6 u8
(b)系统运行若干时间之后
(a) 系统运行初期；
图 8.1 动态存储分配过程中的内存状态示例 1 系统运行期间，动态存储分配过程的初期及系统运行一段时间后的状态示意如下两个术语
占用块 称已分配给用户使用的 地址连续的内存区 为占用块。在不同的动态存储管理系统中，请求分配的内存量大小不同，可能小到几个字节，多至若干 k字节。 但系统每次分配给用户的都是一个地址连续的内存区。
空闲块 称未曾分配的、地址连续的内存区为空闲块或 可利用空间块 。不管怎么样的动态存储管理系统，在刚开始工作时，整个内存区是一个空闲块（ 在编译系统中称之为堆，即堆区域 ）。
动态存储管理的基本问题及方法空闲块占用块此时用户再次请求分配内存，系统将怎样分配
？
第八章 动态存储管理第 8页两种分配策略：
(1) 系统继续从高地址的空闲块中进行分配，而不理会已分配给用户的内存区是否已空闲，直到分配无法进行，才回收所有空闲块，并重新组织内存，将所有空闲的内存区联接成一个大的空闲块；
10,000 15,000 空 闲
31,000 8,000 空 闲
59,000 41,000 空 闲起始地址 内存块大小 使用情况目录表 (b)
动态存储管理的基本问题及方法
(2) 用户一旦运行结束，便将它所占内存区释放成为空闲块，每当新用户请求分配内存时，系统巡视整个内存区中所有空闲块，从中找出一个合适者分配之。
此时，系统需建立一张记录所有空闲块的可利用空间表（ 目录表或链表 ）。
10,000
25,000
31,000
39,000
59,000 99,999
内存状态 (a)
示例 1 可利用空间表的图示形式链 表 (c) 15,0000 8,0000 41,000 ∧0
31,000 59,00010,000av
图 8.2 动态存储管理过程中的内存状态和可利用空间表第八章 动态存储管理第 9页可利用空间表及分配方法可利用空间表中包含所有可分配的空闲块，每一块是链表中的一个结点。 当用户请示分配时，系统从可利用空间表中删除一个结点分配之；当用户释放其所占内存时，系统即回收该内存区并将它插入到可利用空间表中。
可利用空间 表 的结构形式结构形式一,结点均含 大小相同 的空闲块。
可利用空间表可以有下列三和不同的结构形式：
若系统运行期间所有用户请求分配的存储量大小相同，则系统开始运行时，将归它使用的内存区按所需大小分割成若干大小相同的块，并用指针链接成一个可利用空间表。 分配时取表头结点，回收时按插表头形式 。这种情况下的可利用空间表实际是 一个链栈
。是一种最简单的动态存储管理的方式。
第八章 动态存储管理第 10页示例 2 有三种大小结点（设结点大小分别为 2,4,8个字）的可利用空间表的结点结构及其可利用空间表。
结构形式二,建立若干个可利用空间表，同一链表中的结点大小相同。不同链表中的结点大小，一般成倍数关系。
可利用空间表及分配方法
tag type link
space
0 空闲块
1 占用块
0 结点大小的 2个字
1 结点大小的 4个字
2 结点大小的 8个字
tag=
type=
(a)结点结构；
图 8.3 有三种大小结点的可利用空间表
0 0 0 0 0 0∧
0 1 0 1 0 1∧
0 2 0 2 0 2∧
av2
av4
av8
(b)可利用空间表分配过程？
第八章 动态存储管理第 11页结构形式二,建立若干个可利用空间表，同一链表中的结点大小相同。不同链表中的结点大小，一般成倍数关系。
可利用空间表及分配方法分配过程？
根据用户请求空间的大小，到相应的空闲表中取结点。若该空闲表为空，则到较大结点的链表中取一结点，把它一分为二，一部分分配给用户，另部分插入到结点较小的空闲表中。
产生什么结果？ 结点较大链表中的结点，不断一分为二，很容易用完，所以回收时，必须有“紧缩聚合”的过程。
第八章 动态存储管理第 12页如何分配？
结构形式三,结点所包含空闲块的大小可随请求而变。
通常，操作系统中的可利用空间表属于这种类型。
其中
tag,标志位,tag=0表示空闲块,tag=1表示占用块
size：空闲块的存储容量
link,链接下一个结点的指针域、
spack,一片地址连续的内存区域可利用空间表及分配方法
tag size link
space
结点结构的一般形式图 8.4 空闲块的大小随意的结点结构若用户需求量为 n，链表中仅有一块其容量 m≥n，则分割出大小为 n的部分分配给用户，剩余大小为 m-n的部分作为一个结点留在链表中 （只要把 size改小就行 ）。
问题,若空闲块链表中有若干个大小不小于 n的结点，该分配哪一个？分配策略？
三种分配策略：首次拟合法；最佳拟合法；最差拟合法。
第八章 动态存储管理第 13页分配策略一：首次拟合法从空闲块链表的表头指针开始查找，找出 首先能满足 请求容量的存储块，将其中一部分分配给用户。可利用空间表本身既不按结点的初始地址有序，也不按结点的大小有序。在回收时，只要将释放的空闲块插入在链表的表头即可。
分配给用户的占用块 7,000118,000
这种方法需对空闲块链表的结点检测的平均次数从 1— n不等。
所以,首次拟合法为了满足一次请示其平均检测次数小于 n/2。
示例 3 就示例 1的可利用空间表（链表），设有用户 U9进入系统并申请 7千字内存，则按首次拟合法，有
15,0000 8,0000 41,000∧0
31,000 59,00010,000av
图 8.5 结点大小随意的可利用空间表
(a)按首次拟合原则进行分配从高位开始分
8,000
第八章 动态存储管理第 14页分配策略二：最佳拟合法从空闲块链表中找出能满足用户请求容 量的 最小空闲块 。显然这是一种较好的方法，但为了满足某个请示分配，需要对空闲块链表从头至尾扫描，时间开销大。
分配给用户的占用块 7,0001
32,000 图 8.5 结点大小随意的可利用空间表
(b)按最佳拟合原则进行分配
15,0000 8,0000 41,000∧0
31,000 59,00010,000av
示例 5 上例，若采用最佳拟合法，则可得 最佳空闲块从高位开始分
1,000
优点,尽可能保证较大的空闲块不被细分。以满足较大的空间请求。
缺点,有可能使剩余的空闲块容 量变得 太小,以至于不能满足任何请求。
第八章 动态存储管理第 15页为了避免每次分配都要扫视整个链表，可以改造空闲块链表的结点排列顺序,即以结点的容量由小到大排列 。 这样为了满足某个请求分配，则平均检测结点的数目只是链表结点个数一半即可。然而在这种情况下，将任一空闲块插入至空闲块链表的一半位置也需要平均检测链表的一半结点。而不按块容量大小排列的空闲块链表，回收算法中不需要做检测工作。
分配策略二：最佳拟合法第八章 动态存储管理第 16页分配策略三 ——最差拟合法其指导思想是 每次都用空闲块链表中最大的空闲块去满足请求分配,所以若链表中诸结点不是按容量大小排列的话，则每次分配都扫描整个链表，即检测 n次。但是，如果将链表结点按空闲块容量的不增次序排列，则满足一次请求分配仅需检测一次即可。而回收一个空闲块将其插入空闲块链表时，同样需平均检测 n/2次。
分 配 空 闲 块 回收空闲块配 给 方 法首次拟合法 最佳拟合法 最差拟合法 三种方法无序空闲块链表 < n / 2 n n 0
有序空闲块链表
（按容量不增排列）
1 n / 2 1 n / 2
若按结点容量自大至小有序链接诸空闲块，则分配时仅需删除第一个结点，并将其中一部分分配给用户，剩余部分作为一个新的结点插入到链表适当位置。
三种方法分配、回收平均检测次数列列表如下第八章 动态存储管理第 17页边 界 标 识 法边界标识法 (Boundary Tag Method)是操作系统中用以在运行期间对用户所请求的随意内存块大小进行动态分区分配的一种存储管理方法。
空闲块链表是个双向循环链表结构。 分配策略或采用首次拟合法，或采用最佳拟合法。
系统特点：
在每个内存区的 头部 和 底部 两个 边界 上分别设有 标志域,
以标识该内存区域为占用块或空闲块。 在回收时，对物理上相邻的空闲块进行全并，组合成一个尽可能大的、地址连续的空闲块。
第八章 动态存储管理第 18页可利用空间表的结构边界标识法中的结点结构其中
head,结点的头部地址
foot,结点的底部地址
space,一组地址连续的待分配存储单元
tag,标志域,tag=0表示空闲块,tag=1表示占用块
size,整个结点的大小，包括头部 header和底部 footer所占空间（设各占 1个字），但在分配时忽略不计
llink,指向双向循环链表中本结点的 前趋结点 的指针
rlink,指向双向循环链表中本结点的 后继结点 的指针
uplink,指向本结点的指针，其值即为该内存块的首地址边 界 标 识 法
space
llink tag size rlink
uplink tag
head：
foot：
第八章 动态存储管理第 19页
typedef struct WORD{
union {
WORD *llink,//头部域，指向前驱
WORD *uplink; //底部域，指向本结点头部
}
int tag; //块标志
int size; //块大小
WORD *rlink; //后继结点
OtherType other; //其它部分
} WORD,head,foot,*Space;
#define FootLoc(p) (p+p->size-1)
在此双向循环链表中 不设表头结点,表头指针 pav
可以指向 任一个 结点。
0
0 100000
pav
示例 6 一个占有 100k内存空间的系统在运行开始时的可利用空间表的初始状态如下所示边界标识法 – 数据结构第八章 动态存储管理第 20页边界标识法分配算法设采用首次拟合法进行分配，并约定
(1) 选定一个适当的常量 e，当 m－ n≤e（用户请求分配容量为 n的空闲块，而找到的待分配空闲块的容量 m≥n）时，就将容量为 m的空闲块整块地分配给用户；否则，若有 m－ n>e，则仅分配其中 n个字的内存块； 以免产生“空闲碎屑”
(2) 在每次分配之后，令指针指向刚进行过分配的结点的后继结点；
(3) 将 Space型的变量视作其值为存储块的 头部地址 的简单变量，
允许作加、减运算，即假定可按地址来作加、减运算以求得新地址来表示所指向的时针。故有
p,存储块首地址
p->size,地址为 p的存储块头部中的结点大小域，其值约等于同一存储块中 spack空间的容量
p->tag,该存储块头部的标志域
(p+p->size-1)->tag,同一存储块底部的标志域第八章 动态存储管理第 21页
Space AllocBoundTag ( Space &pav,int n )
{/*n为请求分配的存储量，若系统中尚有足够大的空间可分配，则返回 p值指示分配给用户的存储块的地址，否则返回 NULL,若进行分配后的可利用空间表不空，则 pav指向表中刚进行过分配的结点的后继结点 */
for( p = pav; p && p->size < n && p->rlink != pav )
p = p->rlink; //查找空闲块
if( !p || p->size < n ) return NULL; //没有足够大的空间
else{
f = FootLoc(p); pav = p->rlink; //pav指向 p的后继
if( p->size – n ≤ e ) //分配整结点
{ if( pav == p ) pav=NULL;
else
{ pav->llink = p->llink;
p->llink->rlink = pav;
}; //删除已分配的结点
p->tag = f->tag = 1; //修改分配结点的标志
}
else{
f->tag = 1; p->size -= n; f = FootLoc(p);
f->tag = 0; f->uplink = p;
p = f + 1;
p->tag = 1; p->size = n;
}
return p;
}
边界标识法分配算法描述第八章 动态存储管理第 22页边界标识法分配算法描述示例 7 某系统的可利用空间表从初始状态到运行若干时间后的状态以及进行再分配 （ 7000字） 后的状态，可用图示形式表示如下
0
0 100000
pav
(a) 初始状态第八章 动态存储管理第 23页
0
0 15,000
pav
0
0 8,000
0
0 41,000
10,000 31,000 59,000
(b) 运行若干时间后的状态图 8.6 某系统的可利用空间表
1
1 7,000
p(c) 进行再分配后的状态分配：
0
0 8,000
pav
0
0 8,000
0
0 41,000
10,000 31,000 59,000
第八章 动态存储管理第 24页回收算法一旦用户释放占用块，系统应立即回收以备新的请求产生时进行再分配。为了使物理地址相紧邻的空间闲块能结合成一个 尽可能大 的结点,需检查刚释放的占用块的左、右紧邻是否空闲块，若是则合并。
算法思想,设 p指向用户释放的内存区的头部,则与其低地址紧邻的内存区的底部地址为 p-1，与其高地址紧邻的内存区的头部地址为 p+p->size。
分四种情况：
(1) 释放块的左、右邻区均为占用块，
即有 (p-1)->tag == 1 && (p+p->size)->tag == 1
(2) 释放块的左邻区为空闲块，右邻区为占用块，
即有 (p-1)->tag == 0 && (p+p->size)->tag == 1
(3) 释放块的左邻区为占用块，右邻区为空闲块，
即有 (p-1)->tag == 1 && (p+p->size)->tag == 0
(4) 释放块的左、右邻区均为空闲块，
即有 (p-1)->tag == 0 && (p+p->size)->tag == 0
第八章 动态存储管理第 25页则只需将该内存块简单地插入到 pav所指向的结点之前（或之后）
即可。
0
0
0
0
1
1
q
p
pav
(1) 释放块的左、右邻区均为占用块，
即有 (p-1)->tag == 1 && (p+p->size)->tag == 1
0
0
第八章 动态存储管理第 26页此时应将释放块与其紧邻的左邻区合并，即需要改变左邻空闲块的结点，增加结点的 size域的值且重新设置结点的底部。
n = p->size;
s= (p-1)->uplink; //s为左邻空闲块的头部地址
s->size += n; //设置新的空闲块大小
f=p+n+1; f->uplink = s; f->tag = 0; //设置新的空闲块底部
0 s1
0
1
1
s2
1
p
释放块左邻块 右邻块
p+p->size
s1+s2
P-1
(2) 释放块的左邻区为空闲块，右邻区为占用块，即有 (p-1)->tag == 0 && (p+p->size)->tag == 1
0
第八章 动态存储管理第 27页
1
1
0
0
0 s1p
p+p->size
释放块左邻块 右邻块P-1
t = p + p->size; //t为右邻空闲块的头部地址
p->tag = 0; //p为合并后的结点的头部地址
q = t->llink; //q为 t结点在可用空间链表中的前驱结点的头部地址
p->llink = q; q->rlink = p; //q为 p的前驱
q1 = t->rlink; //q1为 t结点在链表中的后继结点的头部地址
p->rlink = q1; q1->llink = p; //q1为 p的后继
p->size += t->size; //新的空闲块大小
FootLoc(t)->uplink = p; //底部指针指向新结点的头部
(3) 释放块的左邻区为占用块，右邻区为空闲块，即有 (p-1)->tag == 1 && (p+p->size)->tag == 0
由原来的右邻空闲块变成合并后的大空闲块时，结点的底部位置不变，但头部要变，由此，链表中的指针也要变。
t
q
q1
第八章 动态存储管理第 28页为使三个空闲块连接在一起成为一个大结点留在可利用空间表中，
只要增加左邻空闲块的 space容量，同时在链表中删去右邻空闲块结点即可。
n = p->size; //n为释放块大小，设为 s2
s = (p-1)->uplink; t = p + p->size; //s指示左邻块,t指示右邻块
q = t->llink; q1 = t->rlink; //q≠q1
s->size += n + t->size; //设置新结点中 spact空间大小
q->rlink = q1; q1->llink = q; //删去右邻空闲块结点
FootLoc(t)->uplink = s; //使新结点底部指针指向新结点的头部
0 s1
0
0 s3
0
s2
q
p
释放块左邻块 右邻块
s
P-1
t
s1+s2+s3
(4) 释放块的左、右邻区均为空闲块，
即有 (p-1)->tag == 0 && (p+p->size)->tag == 0
q1
第八章 动态存储管理第 29页边界标识法由于在每个结点的头部和底部设立了标识域，使得在回收用户释放的内存块时，很容易判别与它毗邻的内存区是否为空闲块，且不需要查询整个可利用空间表便能找到毗邻的空闲块与其合并之；
边 界 标 识 法再者，由于可利用空间表上结点既不需依结点大小有序，也不需依结点地址有序，则释放块插入时也不需查找链表。
由此，不管是哪一种情况，回收空闲块的时间都是个常量，和可利用空间表的大小无关。唯一的缺点是增加了结点底部所占的存储量。
第八章 动态存储管理第 30页伙伴系统 (Buddy System)是操作系统中用到的另一种动态存储管理方法。 所谓伙伴系统是指存储区中有一定地址关系且容量相等的一对存储块 。 伙伴系统中为避免出现许多明显的链域，使用了隐含的寻址规则，它是伙伴系统可用性的基础。如果知道某存储块的地址和容量，也就能够确定它的伙伴存储块。这就要求并约定存储区中的所有存储块容量都必须是 2的幂。
在伙伴系统中，无论是占用块或空闲块，其大小均为 2的幂次。当用户申请 n个字的存储区，则分配的占用块为 2k个字，这里 k满足 2k-1＜ n≤2k.
伙 伴 系 统第八章 动态存储管理第 31页可利用空间表的结构伙伴系统中的可利用空间表由若干个子表组成，每个子表是一个双向循环链表。对于总内存空间为 2m字的一个系统，可以有
m+1个这样的子表，它们以向量形式连接在一起。
双向循环链表的结点形式
header,结点头部（设仅占 1个字）
llink,rlink,指针域，分别指向同一链表中该结点的前驱、后继结点
tag,标志域,tag=0表示空闲块,tag=1表示占用块
kval,k值域，满足存储块大小为 2k字
space,地址连续的内存空间，其大小为 2k－ 1字
llink tag=0 kval rlink
space
header
图 8.8 伙伴系统中的可利用空间表
(a) 空闲块的结点结构伙 伴 系 统第八章 动态存储管理第 32页示例 1 伙伴系统中可利用空间表（设整个内存区是一个大小为 2m
的空闲块）的结构及初始状态示意如下
20 ∧
21 ∧
··
·
··
·
2k ∧
··
·
··
·
2m
freelist
0
1
k
m
nodesize first
m0
llink tag kval rlink
图 8.8 伙伴系统中的可利用空间表 (b) 表的初始状态伙 伴 系 统第八章 动态存储管理第 33页伙伴系统中可利用空间表的数据结构类型定义如下
#define M 16 //可利用空间总容量
typedef struct WORD{
WORD *llink;
int tag;
int kval;
WORD *rlink;
OtherType other;
}WORD,Head;
typedef struct HeadNode{
int nodesize;
WORD *first;
} FreeList[M+1];
伙 伴 系 统第八章 动态存储管理第 34页分配算法伙伴系统分配算法的基本约定：
(1) 分配存储块时其容量一律按照 2的幂给予满足。如果用户请求分配 n字，则伙伴系统将给予容量为 2k的一块存储空间，它满足关系 2k-1< n ≤2k。而已经分配的 2k－ n这个余数称为 内部碎片 （设 n不是 2的幂），它是个小小的浪费；
伙 伴 系 统
(2) 所有容量为 2k的空闲存储块都链接在一个链表中，因此，对于总容量为 2m的伙伴系统，将所有 m+1个链表；
(3) 假定存储区初始状态是容量为 2m的一个单一空闲块，其内存地址是 0 ~ 2m－ 1。
伙伴系统的分配过程,设用户提出大小为 n的内存请求，则在可利用表上寻找结点大小与 n相匹配的子表,(1)若此子表非空，则将该子表中任意一个结点（可取第一个结点）分配之； (2)若此子表为空，则需从结点更大的非空子表中去查找，直至找到一个空闲块
，将其中一部分分配给用户，而将剩余部分插入至相应的子表中第八章 动态存储管理第 35页示例 2 伙伴系统可利用空间表在进行分配用户请求内存时的状态变化（设分配容量为 2k-1
）。 初始状态如右图所示伙 伴 系 统需要分配大小为 n的内存。
2k-1 ∧
2k
··
·
··
·
2m
k0 k0 k0
…
20
(1)如果 2k-1 < n <= 2k-1 且 k+1个子表不为空，直接在 k+1链表中分配。
2k-1 ∧
2k
··
·
··
·
2m
k0 k0
…
20
第八章 动态存储管理第 36页示例 2 伙伴系统可利用空间表在进行分配用户请求内存时的状态变化（设分配容量为 2k-1
）。 初始状态如右图所示伙 伴 系 统需要分配大小为 n的内存。
2k-1 ∧
2k
··
·
··
·
2m
k0 k0 k0
…
20
(2)如果 2k-2 < n <= 2k-1-1且 k(即 2k-1)
个子表为空，则需要从结点大小为 2k取出一般分配，另一半作为新结点插入到结点大小为 2k-1的子表中。
k
20 ∧
2k-1
··
·
··
·
2k
··
·
··
·
2m
0 K-1
0 k0
第八章 动态存储管理第 37页伙 伴 系 统一般情况：
假如对于用户需求 n，有 2k-i-1<n≤2k-i-1
其中 i为小于 k的一个整数，并且所有结点小于 2k的子表均为空，此时如何进行分配？
同样地，需从结点大小为 2k的子表中取出一块，将其中 2k-i的一小部分分配给用户，剩余部分分割成若干个结点分别插入在结点大小为 2k-i,2k-i+1,2k-1的子表中。 k
20 ∧
2k-1
··
·
··
·
2k
··
·
··
·
2m
0 K-1
0 k0
第八章 动态存储管理第 38页示例 3 对于需要内存容量为 n=7的用户，假定所有容量为
23=8,24=16,25=32的链表均为空,而 26=64的链表为非空，则将该表中的一个结点进行分配与分割，设其起始地址为 p，则占用块（始地 p）：分配给用户 ；
空闲块 1（始地 p+8）：插入至 23=8的子表；
空闲块 2（始地 p+16)：插入至 24=16的子表；
空闲块 3（始地 p+32)：插入至 25=32的子表；
2k=64
P+8
P+16
P+32
占用块空闲块 1
空闲块 2
空闲块 3
p
伙 伴 系 统大小 7，碎片为 1
第八章 动态存储管理第 39页伙伴系统分配算法描述
Space alloc_buddy( FreeList &avail,int n )
{ /*avail[0..m]为可利用空间表； n为用户请求分配的存储量，设系统尚有空间可分配时，返回 pa值指示分配给用户的占用块的初始地址，否则返回 NULL*/
for(k=0;k<=m && (avail[k].nodesize<n+1||!avail[k].first)
,k++); //查找满足分配条件的子表
if( k > m ) return NULL; //没有满足，返回
else{
pa = avail[k].first;
pre = pa->llink; suc = pa->rlink; //指向前驱和后继
if( pa == suc ) avail[k].first = NULL; //分配后为空表
else{ //删除 pa结点
pre->rlink=suc; suc->llink=pre; avail[k].first=suc;}
for( i = 1; avail[k-i].nodesize >= n+1; i++ ){
pi = pa + 2(k-i); pi->rlink = pi; pi->llink = pi;
pi->tag = 0; pi->kval = k – i; avail[k-i].first = pi
} //剩余块插入子表
pa->tag = 1; pa->kval = k – ( i-- );
}
return pa;
} //算法 8.2
伙 伴 系 统第八章 动态存储管理第 40页回收算法回收过程：当用户释放不再使用的空闲块时，系统需将新的空闲块插入到可利用空间表中去。 可能要对地址相邻的空闲块进行合并以构成较大块 。但在伙伴系统中,仅考虑互为伙伴的两个空闲块的合并 。对于起始地址为 p，大小为 2k的内存块，
欲 求其伙伴内存块的起始地址,有
p+2k,若 p MOD 2k+1=0
buddy(p,k)= (*)
p-2k,若 p MOD 2k+1=2k
示例 4 设整个可利用内存区大小为 210=1024（地址从 0到 1023）。
则由下图计算大小为 28，起始地址为 29(=512)的内存块，其伙伴块的起始地址为,而大小为 27，起始地址为 384(=28+27)的内存块，其伙伴块的起始地址为 。
27 28
0 256 384 512 768 1023
伙 伴 系 统
768(29+28)
256(=28)
伙伴块 伙伴块第八章 动态存储管理第 41页伙伴系统方法的算法分析,存储动态分配和回收的伙伴系统方法的效率是很高的，它是存储管理中最快捷的一种分配和回收存储块的方法。 然而这种速度快捷的优点 是以增加存储碎片（内部碎片）为代价的 。 由于请求容量不足 2k时，只能分配
2k这样大的存储块，就产生了多余的存储空间。
伙 伴 系 统
2k
第八章 动态存储管理第 42页无用单元收集无用单元是指那些用户不再使用而系统没有回收的结构和变量。
比如
p = malloc( size ); //C++,p = new( … )
… …
p = NULL;
此时，使得执行 malloc为用户在堆区域分配的结点 p成为无用单元。
悬挂访问,欲对已悬空的指针进行访问，比如
p = malloc( size ); //C++,p = new(,,)
… …
q = p;
free( p ); //delete p;
若所释放的结点被再分配，则再次访问指针 q所指结点将引发错误。
无用单元收集法 即 是将存储区中那些不再使用的内存块收集起来形成可利用空间表的方法,亦称为存储废料收集法。
第八章 动态存储管理第 43页一般 并非随时 地进行回收，只有当空闲存储区 几乎耗尽,或者出现了 很大 的用户请求分配，以至于现有的空闲块不能满足需求时，才开始工作。 经过周密而又费时的检测判断过程，找出所有不再使用的那些存储块，把它们当作,废料,回收，形成一个可重新利用的可利用空间表。
无用单元收集此工作由操作系统负责进行管理。在程序运行的过程中，对所有的空闲块链表结点，不管它是否还有用，都不回收，直到整个可利用空间表为空。 此时系统才暂时中断执行程序，将所有当前不被使用的结点链接在一起,成为一个新的可利用空间表，而后程序再继续执行。
第八章 动态存储管理第 44页收集无用单元的步骤
(1) 对所有占用结点加上标志。 确定哪些结点是占用结点的方法是,对于一个正在运行的程序，只要从所当前正在工作的指针变量出发，顺链遍历，那末，所有链接在这些链上的结点都是占用的。反之，可利用存储空间中的其余结点就都是无用的。假设在无用单元收集之前所有结点的标志域均置为 0，则加上标志就是将结点的标志域置为 1；
无用单元收集
(2) 对整个可利用空间的顺序扫描一遍，将所有标志域为 0的结点链接成一个新的可利用空间表。
因此，无用单元收集法的全过程可分为“打标记”和”回收“两个阶段。
上述第一步是在可利用空间表几乎耗尽的情况下进行的，它们的数目多少直接影响着算法的执行时间，故工作量较大。
第八章 动态存储管理第 45页标志算法若系统中采用含有共享子表的广义表来存放用户程序中的各占用块结点，则加标志的操作实质上是遍历广义表，将广义表中所有结点的标志域均赋值为 1。
有三种常用的标志算法：
无用单元收集
(1) 递归算法若列表为空，则无需遍历；若是一个数据元素，则标志该元素结点；反之，则列表非空，首先标志表结点，然后分别遍历表头和表尾。
此算法实现简单，但是需要一个较大的、用于递归的栈空间，该栈空间不能用于动态分配，且栈的大小不易确定，易引起栈区满的异常现象。
这是目前使用的方法中最简单而又古老的方法。
第八章 动态存储管理第 46页
(2) 非递归算法在程序中附设栈（或队列）以实现广义表的遍历。广义表的存储结构中的元素结点不包含指针域。而表结点则类似于二叉树的二叉链表。列表中的元素结点相当于二叉树中的叶子结点，可以类似于遍历二叉树写出遍历广义表的非递归算法，只是在算法中应尽量减少栈的容量。
对列表进行遍历可采用与图的遍历相类似的深度优先搜索遍历或者广度优先搜索遍历。
无用单元收集
(3) 利用表结点本身的指针域标志遍历路径的算法利用已经标志过的表结点中的 tag,hp,和 tp域来代替栈，
以记录遍历过程中的路径。这样,就避免了使用容量不易确定的栈空间。
第八章 动态存储管理第 47页三种标志算法的比较
(1) 递归算法,所使用的栈空间不由用户程序掌握，易产生堆区域溢出；
(2) 非递归算法,程序中附设栈的容量可由用户程序掌握，且比上法所需容量要小，还要操作简单，但仍需要一个不确定量的附加存储；
(3) 利用表本身的指针域标记遍历路径的算法,在作标志时不需要附加存储，使动态分配的可利用空间得到充分利用。但在算法中，几乎是每个表结点的指针域的值都要作两次改变
，故时间上的开销相当大，而且一旦发生中断，整个系统瘫痪，无法重新启动运行。
无用单元收集法不适合在实时处理的情况下使用。
无用单元收集第八章 动态存储管理第 48页无用单元收集法所需要的执行时间与当前还在使用的存储块的数目成正比。无用单元收集这项工作的效率和最后能收集到的可以重新分配的无用结点数有关。
当调用这个方法的的次数频繁，而每次又没有多少可收回的无用存储块时，效率就十分低下。这是此法的主要缺点。
此外，由于它不是随时地、经常地做回收工作，所以那些可能相邻的空闲块得不到及时融合，一旦又进行存储分配时，往往在存储区产生不必要的碎片现象。
无用单元收集第八章 动态存储管理第 49页存 储 紧 缩前面所述的动态存储管理的几种分配和回收算法，使用了空闲块链表。若按地址顺序排列空闲块链表，则较易于将相邻的空闲块融合在一起，把相邻的较小空闲块变成较大的空闲块
，从而减少存储碎片的现象。
但是，由于 没有一种一般的方法来预测已被分配的存储块不再使用而变成空闲块的次序，因此在多数系统中，总存在存储碎片的现象 。同时，由于融合空闲存储块完全是一种 偶然 的机会，所以不能单纯地依赖这种融合技术来保证存储分配时会得到可用的较大空闲存储块。但利用较大的邻接存储块，不仅从逻辑上，而且在物理上的执行效率来看都是十分必要的。更重要的是一个数据集合的所有数据能存放在一块邻接的可访问区，就会减少那些常规外部设备的某些操作。
第八章 动态存储管理第 50页把空闲存储块紧凑成一片十分必要，但这需要移动正在被使用的存储块，这不是件易事。因为这时占用的存储区的信息，有可能被程序引用而正在和外部设备进行传输，此时该存储块的信息决不能移动，否则会造成信息传输的错误。所以存储紧缩的条件是：
已占用的存储块均可移动而重新定位。当整个存储区由加标志过程将正在使用的存储块都打上占用标记后
，即可开始进行存储紧缩的工作。
存储紧缩的方法是,把被占用的存储块信息，集中在相邻的一片存储块中，使它们处于存储区域的一端（低地址端），而另一端（高地址端）就空出了一整块空闲存储区，或相邻接的若干空闲存储块 。
存 储 紧 缩第八章 动态存储管理第 51页示例 5 堆存储管理存储紧缩方法之一：
一旦有用户释放存储块即进行回收紧缩。 示意如下
0 1 2 3 4 5 6 7 8 9
10
20
30
40
50
60
70
80
90
free free
10
20
30
40
50
60
70
80
90
0 1 2 3 4 5 6 7 8 9
12 0
6 12
10 18
8 28
A
B
C
D
lengthstadr
(b)
(a)
(c)
12 0
6 12
8 18
A
B
D
lengthstadr
(d)
图 8.12 堆存储管理示意图
(a) 堆空间； (b) 串的存储映象；
(c) 紧缩后的堆； (d) 修改后的存储映象第八章 动态存储管理第 52页示例 6 堆存储管理存储紧缩方法之二,在程序执行过程中不回收用户随时释放的存储块，直到可利用空间不够分配或堆指针指向最高地址时才能进行存储紧缩 —— 将堆中所有的空闲块连成一片，即将所有的占用块都集中到可利用空间的低地址区，而剩余的高地址区成为一整个地址连续的空闲块 。示意如下
free free (b)(a)
图 8.13 紧缩前后的堆（存储空间）
(a) 紧缩前； (b) 紧缩后第八章 动态存储管理第 53页第八章 动态存储管理 小结内容提要
动态存储管理的基本问题及方法
利用可利用空间表进行动态存储管理的分配策略
操作系统中用以进行动态存储管理的边界标识法和伙伴系统
无用 单元收集时的标志算法
存储紧缩学习要点
深刻理解有关动态存储管理的各种概念及方法
了解可利用空间表的三种分配策略的差异及优缺点
掌握边界标识法的分配与回收算法
掌握伙伴系统方法的分配与回收算法
了解无用 单元收集中标志算法的作用
第八章 动态存储管理第八章 动态存储管理第 2页
可利用空间表及分配方法
边界标识法
伙伴系统
无用单元收集
存储紧缩内容和要求可利用空间表、边界标识法、伙伴系统和无用单元收集。
要求掌握可利用空间表及分配办法。
重点可利用空间表及分配。
内容和要求第八章 动态存储管理第 3页动态存储管理的基本问题及方法存储管理是一个既复杂而又重要的问题。在后续课程 —— 操作系统 和 编译技术 （或方法、原理）中，将对其作较深入的研究。在数据库技术中，也涉及大量有关存储管理的问题。 本章仅就动态存储管理方面一些基本技术进行讨论。
在以往的算法描述中，有关存储分配请求、存储回收等项工作往往一带而过，好比是存储,自动满足,又
,自动回收,。偶尔亦考虑某一数据结构下判断是否溢出或者是否释放内存空间等问题。这是必要的，主要是为了把当时的重点和核心放在研究数据的逻辑特性、物理表示、算法描述与分析上，而对有关存储管理的问题作了一定的简化。
第八章 动态存储管理第 4页动态存储管理的基本问题
(1) 如何按用户提出的“请示”分配内存？
(2) 如何回收那些用户不再使用而“释放”的内存，以备新的“请示”产生时重新进行分配？
(1) 由用户来解决；
(2) 由系统来解决；
(3) 由系统和用户共同解决。
存储管理问题的解决途径动态存储管理的基本问题及方法第八章 动态存储管理第 5页在计算机系统中，存储管理的分级
(1) 操作系统为进程分配所需要的存储空间，以便能在机器上运行。一旦运行结束从系统撤离时，操作系统就回收进程所使用的空间。此类存储管理问题将在,操作系统,课程中讨论 。
动态存储管理的基本问题及方法
(2) 进程对数据结构分配及回收存储空间，例如编译进程为变量、数组以及各种表格分配、回收空间 。 此类存储管理问题将在,编译方法,课程中讨论 。
(3) 数据结构中，对某结构中的元素或子结构分配、回收存储空间。此类存储管理问题将是,数据结构,课程研究的范畴
。
下面仅限于在数据结构一级上研究存储管理的方法。但其基本思想和方法亦完全适用于其他两个级别。
第八章 动态存储管理第 6页一些有关存储管理的重要问题
(1) 由谁来负责存储空间的分配与回收？是 用户自身,还是由系统的一个专门子系统 为用户分配并发现不再使用的空间而加以回收？
(2) 分配和释放存储空间的单位是 相同还是有大有小？
(3) 系统 何时回收 空闲的空间？是 及时回收 还是 定期回收 或 当存储空间用完时 才去回收？
(4) 是否考虑存储 碎片的紧凑 问题？
(5) 当请示存储空间时，满足该请示的最好 分配策略 是什么？
是寻找容量大致相当的存储块给予，还是不加选择地依次给一块至少能满足的空间？
(6) 怎样 安排空闲存储块的次序？随机排列或按地址排列或按容量大小排列？
动态存储管理的基本问题及方法第八章 动态存储管理第 7页
u1 u2 u3 u4 u5 u6 u7 u8
u1 u3 u4 u6 u8
(b)系统运行若干时间之后
(a) 系统运行初期；
图 8.1 动态存储分配过程中的内存状态示例 1 系统运行期间，动态存储分配过程的初期及系统运行一段时间后的状态示意如下两个术语
占用块 称已分配给用户使用的 地址连续的内存区 为占用块。在不同的动态存储管理系统中，请求分配的内存量大小不同，可能小到几个字节，多至若干 k字节。 但系统每次分配给用户的都是一个地址连续的内存区。
空闲块 称未曾分配的、地址连续的内存区为空闲块或 可利用空间块 。不管怎么样的动态存储管理系统，在刚开始工作时，整个内存区是一个空闲块（ 在编译系统中称之为堆，即堆区域 ）。
动态存储管理的基本问题及方法空闲块占用块此时用户再次请求分配内存，系统将怎样分配
？
第八章 动态存储管理第 8页两种分配策略：
(1) 系统继续从高地址的空闲块中进行分配，而不理会已分配给用户的内存区是否已空闲，直到分配无法进行，才回收所有空闲块，并重新组织内存，将所有空闲的内存区联接成一个大的空闲块；
10,000 15,000 空 闲
31,000 8,000 空 闲
59,000 41,000 空 闲起始地址 内存块大小 使用情况目录表 (b)
动态存储管理的基本问题及方法
(2) 用户一旦运行结束，便将它所占内存区释放成为空闲块，每当新用户请求分配内存时，系统巡视整个内存区中所有空闲块，从中找出一个合适者分配之。
此时，系统需建立一张记录所有空闲块的可利用空间表（ 目录表或链表 ）。
10,000
25,000
31,000
39,000
59,000 99,999
内存状态 (a)
示例 1 可利用空间表的图示形式链 表 (c) 15,0000 8,0000 41,000 ∧0
31,000 59,00010,000av
图 8.2 动态存储管理过程中的内存状态和可利用空间表第八章 动态存储管理第 9页可利用空间表及分配方法可利用空间表中包含所有可分配的空闲块，每一块是链表中的一个结点。 当用户请示分配时，系统从可利用空间表中删除一个结点分配之；当用户释放其所占内存时，系统即回收该内存区并将它插入到可利用空间表中。
可利用空间 表 的结构形式结构形式一,结点均含 大小相同 的空闲块。
可利用空间表可以有下列三和不同的结构形式：
若系统运行期间所有用户请求分配的存储量大小相同，则系统开始运行时，将归它使用的内存区按所需大小分割成若干大小相同的块，并用指针链接成一个可利用空间表。 分配时取表头结点，回收时按插表头形式 。这种情况下的可利用空间表实际是 一个链栈
。是一种最简单的动态存储管理的方式。
第八章 动态存储管理第 10页示例 2 有三种大小结点（设结点大小分别为 2,4,8个字）的可利用空间表的结点结构及其可利用空间表。
结构形式二,建立若干个可利用空间表，同一链表中的结点大小相同。不同链表中的结点大小，一般成倍数关系。
可利用空间表及分配方法
tag type link
space
0 空闲块
1 占用块
0 结点大小的 2个字
1 结点大小的 4个字
2 结点大小的 8个字
tag=
type=
(a)结点结构；
图 8.3 有三种大小结点的可利用空间表
0 0 0 0 0 0∧
0 1 0 1 0 1∧
0 2 0 2 0 2∧
av2
av4
av8
(b)可利用空间表分配过程？
第八章 动态存储管理第 11页结构形式二,建立若干个可利用空间表，同一链表中的结点大小相同。不同链表中的结点大小，一般成倍数关系。
可利用空间表及分配方法分配过程？
根据用户请求空间的大小，到相应的空闲表中取结点。若该空闲表为空，则到较大结点的链表中取一结点，把它一分为二，一部分分配给用户，另部分插入到结点较小的空闲表中。
产生什么结果？ 结点较大链表中的结点，不断一分为二，很容易用完，所以回收时，必须有“紧缩聚合”的过程。
第八章 动态存储管理第 12页如何分配？
结构形式三,结点所包含空闲块的大小可随请求而变。
通常，操作系统中的可利用空间表属于这种类型。
其中
tag,标志位,tag=0表示空闲块,tag=1表示占用块
size：空闲块的存储容量
link,链接下一个结点的指针域、
spack,一片地址连续的内存区域可利用空间表及分配方法
tag size link
space
结点结构的一般形式图 8.4 空闲块的大小随意的结点结构若用户需求量为 n，链表中仅有一块其容量 m≥n，则分割出大小为 n的部分分配给用户，剩余大小为 m-n的部分作为一个结点留在链表中 （只要把 size改小就行 ）。
问题,若空闲块链表中有若干个大小不小于 n的结点，该分配哪一个？分配策略？
三种分配策略：首次拟合法；最佳拟合法；最差拟合法。
第八章 动态存储管理第 13页分配策略一：首次拟合法从空闲块链表的表头指针开始查找，找出 首先能满足 请求容量的存储块，将其中一部分分配给用户。可利用空间表本身既不按结点的初始地址有序，也不按结点的大小有序。在回收时，只要将释放的空闲块插入在链表的表头即可。
分配给用户的占用块 7,000118,000
这种方法需对空闲块链表的结点检测的平均次数从 1— n不等。
所以,首次拟合法为了满足一次请示其平均检测次数小于 n/2。
示例 3 就示例 1的可利用空间表（链表），设有用户 U9进入系统并申请 7千字内存，则按首次拟合法，有
15,0000 8,0000 41,000∧0
31,000 59,00010,000av
图 8.5 结点大小随意的可利用空间表
(a)按首次拟合原则进行分配从高位开始分
8,000
第八章 动态存储管理第 14页分配策略二：最佳拟合法从空闲块链表中找出能满足用户请求容 量的 最小空闲块 。显然这是一种较好的方法，但为了满足某个请示分配，需要对空闲块链表从头至尾扫描，时间开销大。
分配给用户的占用块 7,0001
32,000 图 8.5 结点大小随意的可利用空间表
(b)按最佳拟合原则进行分配
15,0000 8,0000 41,000∧0
31,000 59,00010,000av
示例 5 上例，若采用最佳拟合法，则可得 最佳空闲块从高位开始分
1,000
优点,尽可能保证较大的空闲块不被细分。以满足较大的空间请求。
缺点,有可能使剩余的空闲块容 量变得 太小,以至于不能满足任何请求。
第八章 动态存储管理第 15页为了避免每次分配都要扫视整个链表，可以改造空闲块链表的结点排列顺序,即以结点的容量由小到大排列 。 这样为了满足某个请求分配，则平均检测结点的数目只是链表结点个数一半即可。然而在这种情况下，将任一空闲块插入至空闲块链表的一半位置也需要平均检测链表的一半结点。而不按块容量大小排列的空闲块链表，回收算法中不需要做检测工作。
分配策略二：最佳拟合法第八章 动态存储管理第 16页分配策略三 ——最差拟合法其指导思想是 每次都用空闲块链表中最大的空闲块去满足请求分配,所以若链表中诸结点不是按容量大小排列的话，则每次分配都扫描整个链表，即检测 n次。但是，如果将链表结点按空闲块容量的不增次序排列，则满足一次请求分配仅需检测一次即可。而回收一个空闲块将其插入空闲块链表时，同样需平均检测 n/2次。
分 配 空 闲 块 回收空闲块配 给 方 法首次拟合法 最佳拟合法 最差拟合法 三种方法无序空闲块链表 < n / 2 n n 0
有序空闲块链表
（按容量不增排列）
1 n / 2 1 n / 2
若按结点容量自大至小有序链接诸空闲块，则分配时仅需删除第一个结点，并将其中一部分分配给用户，剩余部分作为一个新的结点插入到链表适当位置。
三种方法分配、回收平均检测次数列列表如下第八章 动态存储管理第 17页边 界 标 识 法边界标识法 (Boundary Tag Method)是操作系统中用以在运行期间对用户所请求的随意内存块大小进行动态分区分配的一种存储管理方法。
空闲块链表是个双向循环链表结构。 分配策略或采用首次拟合法，或采用最佳拟合法。
系统特点：
在每个内存区的 头部 和 底部 两个 边界 上分别设有 标志域,
以标识该内存区域为占用块或空闲块。 在回收时，对物理上相邻的空闲块进行全并，组合成一个尽可能大的、地址连续的空闲块。
第八章 动态存储管理第 18页可利用空间表的结构边界标识法中的结点结构其中
head,结点的头部地址
foot,结点的底部地址
space,一组地址连续的待分配存储单元
tag,标志域,tag=0表示空闲块,tag=1表示占用块
size,整个结点的大小，包括头部 header和底部 footer所占空间（设各占 1个字），但在分配时忽略不计
llink,指向双向循环链表中本结点的 前趋结点 的指针
rlink,指向双向循环链表中本结点的 后继结点 的指针
uplink,指向本结点的指针，其值即为该内存块的首地址边 界 标 识 法
space
llink tag size rlink
uplink tag
head：
foot：
第八章 动态存储管理第 19页
typedef struct WORD{
union {
WORD *llink,//头部域，指向前驱
WORD *uplink; //底部域，指向本结点头部
}
int tag; //块标志
int size; //块大小
WORD *rlink; //后继结点
OtherType other; //其它部分
} WORD,head,foot,*Space;
#define FootLoc(p) (p+p->size-1)
在此双向循环链表中 不设表头结点,表头指针 pav
可以指向 任一个 结点。
0
0 100000
pav
示例 6 一个占有 100k内存空间的系统在运行开始时的可利用空间表的初始状态如下所示边界标识法 – 数据结构第八章 动态存储管理第 20页边界标识法分配算法设采用首次拟合法进行分配，并约定
(1) 选定一个适当的常量 e，当 m－ n≤e（用户请求分配容量为 n的空闲块，而找到的待分配空闲块的容量 m≥n）时，就将容量为 m的空闲块整块地分配给用户；否则，若有 m－ n>e，则仅分配其中 n个字的内存块； 以免产生“空闲碎屑”
(2) 在每次分配之后，令指针指向刚进行过分配的结点的后继结点；
(3) 将 Space型的变量视作其值为存储块的 头部地址 的简单变量，
允许作加、减运算，即假定可按地址来作加、减运算以求得新地址来表示所指向的时针。故有
p,存储块首地址
p->size,地址为 p的存储块头部中的结点大小域，其值约等于同一存储块中 spack空间的容量
p->tag,该存储块头部的标志域
(p+p->size-1)->tag,同一存储块底部的标志域第八章 动态存储管理第 21页
Space AllocBoundTag ( Space &pav,int n )
{/*n为请求分配的存储量，若系统中尚有足够大的空间可分配，则返回 p值指示分配给用户的存储块的地址，否则返回 NULL,若进行分配后的可利用空间表不空，则 pav指向表中刚进行过分配的结点的后继结点 */
for( p = pav; p && p->size < n && p->rlink != pav )
p = p->rlink; //查找空闲块
if( !p || p->size < n ) return NULL; //没有足够大的空间
else{
f = FootLoc(p); pav = p->rlink; //pav指向 p的后继
if( p->size – n ≤ e ) //分配整结点
{ if( pav == p ) pav=NULL;
else
{ pav->llink = p->llink;
p->llink->rlink = pav;
}; //删除已分配的结点
p->tag = f->tag = 1; //修改分配结点的标志
}
else{
f->tag = 1; p->size -= n; f = FootLoc(p);
f->tag = 0; f->uplink = p;
p = f + 1;
p->tag = 1; p->size = n;
}
return p;
}
边界标识法分配算法描述第八章 动态存储管理第 22页边界标识法分配算法描述示例 7 某系统的可利用空间表从初始状态到运行若干时间后的状态以及进行再分配 （ 7000字） 后的状态，可用图示形式表示如下
0
0 100000
pav
(a) 初始状态第八章 动态存储管理第 23页
0
0 15,000
pav
0
0 8,000
0
0 41,000
10,000 31,000 59,000
(b) 运行若干时间后的状态图 8.6 某系统的可利用空间表
1
1 7,000
p(c) 进行再分配后的状态分配：
0
0 8,000
pav
0
0 8,000
0
0 41,000
10,000 31,000 59,000
第八章 动态存储管理第 24页回收算法一旦用户释放占用块，系统应立即回收以备新的请求产生时进行再分配。为了使物理地址相紧邻的空间闲块能结合成一个 尽可能大 的结点,需检查刚释放的占用块的左、右紧邻是否空闲块，若是则合并。
算法思想,设 p指向用户释放的内存区的头部,则与其低地址紧邻的内存区的底部地址为 p-1，与其高地址紧邻的内存区的头部地址为 p+p->size。
分四种情况：
(1) 释放块的左、右邻区均为占用块，
即有 (p-1)->tag == 1 && (p+p->size)->tag == 1
(2) 释放块的左邻区为空闲块，右邻区为占用块，
即有 (p-1)->tag == 0 && (p+p->size)->tag == 1
(3) 释放块的左邻区为占用块，右邻区为空闲块，
即有 (p-1)->tag == 1 && (p+p->size)->tag == 0
(4) 释放块的左、右邻区均为空闲块，
即有 (p-1)->tag == 0 && (p+p->size)->tag == 0
第八章 动态存储管理第 25页则只需将该内存块简单地插入到 pav所指向的结点之前（或之后）
即可。
0
0
0
0
1
1
q
p
pav
(1) 释放块的左、右邻区均为占用块，
即有 (p-1)->tag == 1 && (p+p->size)->tag == 1
0
0
第八章 动态存储管理第 26页此时应将释放块与其紧邻的左邻区合并，即需要改变左邻空闲块的结点，增加结点的 size域的值且重新设置结点的底部。
n = p->size;
s= (p-1)->uplink; //s为左邻空闲块的头部地址
s->size += n; //设置新的空闲块大小
f=p+n+1; f->uplink = s; f->tag = 0; //设置新的空闲块底部
0 s1
0
1
1
s2
1
p
释放块左邻块 右邻块
p+p->size
s1+s2
P-1
(2) 释放块的左邻区为空闲块，右邻区为占用块，即有 (p-1)->tag == 0 && (p+p->size)->tag == 1
0
第八章 动态存储管理第 27页
1
1
0
0
0 s1p
p+p->size
释放块左邻块 右邻块P-1
t = p + p->size; //t为右邻空闲块的头部地址
p->tag = 0; //p为合并后的结点的头部地址
q = t->llink; //q为 t结点在可用空间链表中的前驱结点的头部地址
p->llink = q; q->rlink = p; //q为 p的前驱
q1 = t->rlink; //q1为 t结点在链表中的后继结点的头部地址
p->rlink = q1; q1->llink = p; //q1为 p的后继
p->size += t->size; //新的空闲块大小
FootLoc(t)->uplink = p; //底部指针指向新结点的头部
(3) 释放块的左邻区为占用块，右邻区为空闲块，即有 (p-1)->tag == 1 && (p+p->size)->tag == 0
由原来的右邻空闲块变成合并后的大空闲块时，结点的底部位置不变，但头部要变，由此，链表中的指针也要变。
t
q
q1
第八章 动态存储管理第 28页为使三个空闲块连接在一起成为一个大结点留在可利用空间表中，
只要增加左邻空闲块的 space容量，同时在链表中删去右邻空闲块结点即可。
n = p->size; //n为释放块大小，设为 s2
s = (p-1)->uplink; t = p + p->size; //s指示左邻块,t指示右邻块
q = t->llink; q1 = t->rlink; //q≠q1
s->size += n + t->size; //设置新结点中 spact空间大小
q->rlink = q1; q1->llink = q; //删去右邻空闲块结点
FootLoc(t)->uplink = s; //使新结点底部指针指向新结点的头部
0 s1
0
0 s3
0
s2
q
p
释放块左邻块 右邻块
s
P-1
t
s1+s2+s3
(4) 释放块的左、右邻区均为空闲块，
即有 (p-1)->tag == 0 && (p+p->size)->tag == 0
q1
第八章 动态存储管理第 29页边界标识法由于在每个结点的头部和底部设立了标识域，使得在回收用户释放的内存块时，很容易判别与它毗邻的内存区是否为空闲块，且不需要查询整个可利用空间表便能找到毗邻的空闲块与其合并之；
边 界 标 识 法再者，由于可利用空间表上结点既不需依结点大小有序，也不需依结点地址有序，则释放块插入时也不需查找链表。
由此，不管是哪一种情况，回收空闲块的时间都是个常量，和可利用空间表的大小无关。唯一的缺点是增加了结点底部所占的存储量。
第八章 动态存储管理第 30页伙伴系统 (Buddy System)是操作系统中用到的另一种动态存储管理方法。 所谓伙伴系统是指存储区中有一定地址关系且容量相等的一对存储块 。 伙伴系统中为避免出现许多明显的链域，使用了隐含的寻址规则，它是伙伴系统可用性的基础。如果知道某存储块的地址和容量，也就能够确定它的伙伴存储块。这就要求并约定存储区中的所有存储块容量都必须是 2的幂。
在伙伴系统中，无论是占用块或空闲块，其大小均为 2的幂次。当用户申请 n个字的存储区，则分配的占用块为 2k个字，这里 k满足 2k-1＜ n≤2k.
伙 伴 系 统第八章 动态存储管理第 31页可利用空间表的结构伙伴系统中的可利用空间表由若干个子表组成，每个子表是一个双向循环链表。对于总内存空间为 2m字的一个系统，可以有
m+1个这样的子表，它们以向量形式连接在一起。
双向循环链表的结点形式
header,结点头部（设仅占 1个字）
llink,rlink,指针域，分别指向同一链表中该结点的前驱、后继结点
tag,标志域,tag=0表示空闲块,tag=1表示占用块
kval,k值域，满足存储块大小为 2k字
space,地址连续的内存空间，其大小为 2k－ 1字
llink tag=0 kval rlink
space
header
图 8.8 伙伴系统中的可利用空间表
(a) 空闲块的结点结构伙 伴 系 统第八章 动态存储管理第 32页示例 1 伙伴系统中可利用空间表（设整个内存区是一个大小为 2m
的空闲块）的结构及初始状态示意如下
20 ∧
21 ∧
··
·
··
·
2k ∧
··
·
··
·
2m
freelist
0
1
k
m
nodesize first
m0
llink tag kval rlink
图 8.8 伙伴系统中的可利用空间表 (b) 表的初始状态伙 伴 系 统第八章 动态存储管理第 33页伙伴系统中可利用空间表的数据结构类型定义如下
#define M 16 //可利用空间总容量
typedef struct WORD{
WORD *llink;
int tag;
int kval;
WORD *rlink;
OtherType other;
}WORD,Head;
typedef struct HeadNode{
int nodesize;
WORD *first;
} FreeList[M+1];
伙 伴 系 统第八章 动态存储管理第 34页分配算法伙伴系统分配算法的基本约定：
(1) 分配存储块时其容量一律按照 2的幂给予满足。如果用户请求分配 n字，则伙伴系统将给予容量为 2k的一块存储空间，它满足关系 2k-1< n ≤2k。而已经分配的 2k－ n这个余数称为 内部碎片 （设 n不是 2的幂），它是个小小的浪费；
伙 伴 系 统
(2) 所有容量为 2k的空闲存储块都链接在一个链表中，因此，对于总容量为 2m的伙伴系统，将所有 m+1个链表；
(3) 假定存储区初始状态是容量为 2m的一个单一空闲块，其内存地址是 0 ~ 2m－ 1。
伙伴系统的分配过程,设用户提出大小为 n的内存请求，则在可利用表上寻找结点大小与 n相匹配的子表,(1)若此子表非空，则将该子表中任意一个结点（可取第一个结点）分配之； (2)若此子表为空，则需从结点更大的非空子表中去查找，直至找到一个空闲块
，将其中一部分分配给用户，而将剩余部分插入至相应的子表中第八章 动态存储管理第 35页示例 2 伙伴系统可利用空间表在进行分配用户请求内存时的状态变化（设分配容量为 2k-1
）。 初始状态如右图所示伙 伴 系 统需要分配大小为 n的内存。
2k-1 ∧
2k
··
·
··
·
2m
k0 k0 k0
…
20
(1)如果 2k-1 < n <= 2k-1 且 k+1个子表不为空，直接在 k+1链表中分配。
2k-1 ∧
2k
··
·
··
·
2m
k0 k0
…
20
第八章 动态存储管理第 36页示例 2 伙伴系统可利用空间表在进行分配用户请求内存时的状态变化（设分配容量为 2k-1
）。 初始状态如右图所示伙 伴 系 统需要分配大小为 n的内存。
2k-1 ∧
2k
··
·
··
·
2m
k0 k0 k0
…
20
(2)如果 2k-2 < n <= 2k-1-1且 k(即 2k-1)
个子表为空，则需要从结点大小为 2k取出一般分配，另一半作为新结点插入到结点大小为 2k-1的子表中。
k
20 ∧
2k-1
··
·
··
·
2k
··
·
··
·
2m
0 K-1
0 k0
第八章 动态存储管理第 37页伙 伴 系 统一般情况：
假如对于用户需求 n，有 2k-i-1<n≤2k-i-1
其中 i为小于 k的一个整数，并且所有结点小于 2k的子表均为空，此时如何进行分配？
同样地，需从结点大小为 2k的子表中取出一块，将其中 2k-i的一小部分分配给用户，剩余部分分割成若干个结点分别插入在结点大小为 2k-i,2k-i+1,2k-1的子表中。 k
20 ∧
2k-1
··
·
··
·
2k
··
·
··
·
2m
0 K-1
0 k0
第八章 动态存储管理第 38页示例 3 对于需要内存容量为 n=7的用户，假定所有容量为
23=8,24=16,25=32的链表均为空,而 26=64的链表为非空，则将该表中的一个结点进行分配与分割，设其起始地址为 p，则占用块（始地 p）：分配给用户 ；
空闲块 1（始地 p+8）：插入至 23=8的子表；
空闲块 2（始地 p+16)：插入至 24=16的子表；
空闲块 3（始地 p+32)：插入至 25=32的子表；
2k=64
P+8
P+16
P+32
占用块空闲块 1
空闲块 2
空闲块 3
p
伙 伴 系 统大小 7，碎片为 1
第八章 动态存储管理第 39页伙伴系统分配算法描述
Space alloc_buddy( FreeList &avail,int n )
{ /*avail[0..m]为可利用空间表； n为用户请求分配的存储量，设系统尚有空间可分配时，返回 pa值指示分配给用户的占用块的初始地址，否则返回 NULL*/
for(k=0;k<=m && (avail[k].nodesize<n+1||!avail[k].first)
,k++); //查找满足分配条件的子表
if( k > m ) return NULL; //没有满足，返回
else{
pa = avail[k].first;
pre = pa->llink; suc = pa->rlink; //指向前驱和后继
if( pa == suc ) avail[k].first = NULL; //分配后为空表
else{ //删除 pa结点
pre->rlink=suc; suc->llink=pre; avail[k].first=suc;}
for( i = 1; avail[k-i].nodesize >= n+1; i++ ){
pi = pa + 2(k-i); pi->rlink = pi; pi->llink = pi;
pi->tag = 0; pi->kval = k – i; avail[k-i].first = pi
} //剩余块插入子表
pa->tag = 1; pa->kval = k – ( i-- );
}
return pa;
} //算法 8.2
伙 伴 系 统第八章 动态存储管理第 40页回收算法回收过程：当用户释放不再使用的空闲块时，系统需将新的空闲块插入到可利用空间表中去。 可能要对地址相邻的空闲块进行合并以构成较大块 。但在伙伴系统中,仅考虑互为伙伴的两个空闲块的合并 。对于起始地址为 p，大小为 2k的内存块，
欲 求其伙伴内存块的起始地址,有
p+2k,若 p MOD 2k+1=0
buddy(p,k)= (*)
p-2k,若 p MOD 2k+1=2k
示例 4 设整个可利用内存区大小为 210=1024（地址从 0到 1023）。
则由下图计算大小为 28，起始地址为 29(=512)的内存块，其伙伴块的起始地址为,而大小为 27，起始地址为 384(=28+27)的内存块，其伙伴块的起始地址为 。
27 28
0 256 384 512 768 1023
伙 伴 系 统
768(29+28)
256(=28)
伙伴块 伙伴块第八章 动态存储管理第 41页伙伴系统方法的算法分析,存储动态分配和回收的伙伴系统方法的效率是很高的，它是存储管理中最快捷的一种分配和回收存储块的方法。 然而这种速度快捷的优点 是以增加存储碎片（内部碎片）为代价的 。 由于请求容量不足 2k时，只能分配
2k这样大的存储块，就产生了多余的存储空间。
伙 伴 系 统
2k
第八章 动态存储管理第 42页无用单元收集无用单元是指那些用户不再使用而系统没有回收的结构和变量。
比如
p = malloc( size ); //C++,p = new( … )
… …
p = NULL;
此时，使得执行 malloc为用户在堆区域分配的结点 p成为无用单元。
悬挂访问,欲对已悬空的指针进行访问，比如
p = malloc( size ); //C++,p = new(,,)
… …
q = p;
free( p ); //delete p;
若所释放的结点被再分配，则再次访问指针 q所指结点将引发错误。
无用单元收集法 即 是将存储区中那些不再使用的内存块收集起来形成可利用空间表的方法,亦称为存储废料收集法。
第八章 动态存储管理第 43页一般 并非随时 地进行回收，只有当空闲存储区 几乎耗尽,或者出现了 很大 的用户请求分配，以至于现有的空闲块不能满足需求时，才开始工作。 经过周密而又费时的检测判断过程，找出所有不再使用的那些存储块，把它们当作,废料,回收，形成一个可重新利用的可利用空间表。
无用单元收集此工作由操作系统负责进行管理。在程序运行的过程中，对所有的空闲块链表结点，不管它是否还有用，都不回收，直到整个可利用空间表为空。 此时系统才暂时中断执行程序，将所有当前不被使用的结点链接在一起,成为一个新的可利用空间表，而后程序再继续执行。
第八章 动态存储管理第 44页收集无用单元的步骤
(1) 对所有占用结点加上标志。 确定哪些结点是占用结点的方法是,对于一个正在运行的程序，只要从所当前正在工作的指针变量出发，顺链遍历，那末，所有链接在这些链上的结点都是占用的。反之，可利用存储空间中的其余结点就都是无用的。假设在无用单元收集之前所有结点的标志域均置为 0，则加上标志就是将结点的标志域置为 1；
无用单元收集
(2) 对整个可利用空间的顺序扫描一遍，将所有标志域为 0的结点链接成一个新的可利用空间表。
因此，无用单元收集法的全过程可分为“打标记”和”回收“两个阶段。
上述第一步是在可利用空间表几乎耗尽的情况下进行的，它们的数目多少直接影响着算法的执行时间，故工作量较大。
第八章 动态存储管理第 45页标志算法若系统中采用含有共享子表的广义表来存放用户程序中的各占用块结点，则加标志的操作实质上是遍历广义表，将广义表中所有结点的标志域均赋值为 1。
有三种常用的标志算法：
无用单元收集
(1) 递归算法若列表为空，则无需遍历；若是一个数据元素，则标志该元素结点；反之，则列表非空，首先标志表结点，然后分别遍历表头和表尾。
此算法实现简单，但是需要一个较大的、用于递归的栈空间，该栈空间不能用于动态分配，且栈的大小不易确定，易引起栈区满的异常现象。
这是目前使用的方法中最简单而又古老的方法。
第八章 动态存储管理第 46页
(2) 非递归算法在程序中附设栈（或队列）以实现广义表的遍历。广义表的存储结构中的元素结点不包含指针域。而表结点则类似于二叉树的二叉链表。列表中的元素结点相当于二叉树中的叶子结点，可以类似于遍历二叉树写出遍历广义表的非递归算法，只是在算法中应尽量减少栈的容量。
对列表进行遍历可采用与图的遍历相类似的深度优先搜索遍历或者广度优先搜索遍历。
无用单元收集
(3) 利用表结点本身的指针域标志遍历路径的算法利用已经标志过的表结点中的 tag,hp,和 tp域来代替栈，
以记录遍历过程中的路径。这样,就避免了使用容量不易确定的栈空间。
第八章 动态存储管理第 47页三种标志算法的比较
(1) 递归算法,所使用的栈空间不由用户程序掌握，易产生堆区域溢出；
(2) 非递归算法,程序中附设栈的容量可由用户程序掌握，且比上法所需容量要小，还要操作简单，但仍需要一个不确定量的附加存储；
(3) 利用表本身的指针域标记遍历路径的算法,在作标志时不需要附加存储，使动态分配的可利用空间得到充分利用。但在算法中，几乎是每个表结点的指针域的值都要作两次改变
，故时间上的开销相当大，而且一旦发生中断，整个系统瘫痪，无法重新启动运行。
无用单元收集法不适合在实时处理的情况下使用。
无用单元收集第八章 动态存储管理第 48页无用单元收集法所需要的执行时间与当前还在使用的存储块的数目成正比。无用单元收集这项工作的效率和最后能收集到的可以重新分配的无用结点数有关。
当调用这个方法的的次数频繁，而每次又没有多少可收回的无用存储块时，效率就十分低下。这是此法的主要缺点。
此外，由于它不是随时地、经常地做回收工作，所以那些可能相邻的空闲块得不到及时融合，一旦又进行存储分配时，往往在存储区产生不必要的碎片现象。
无用单元收集第八章 动态存储管理第 49页存 储 紧 缩前面所述的动态存储管理的几种分配和回收算法，使用了空闲块链表。若按地址顺序排列空闲块链表，则较易于将相邻的空闲块融合在一起，把相邻的较小空闲块变成较大的空闲块
，从而减少存储碎片的现象。
但是，由于 没有一种一般的方法来预测已被分配的存储块不再使用而变成空闲块的次序，因此在多数系统中，总存在存储碎片的现象 。同时，由于融合空闲存储块完全是一种 偶然 的机会，所以不能单纯地依赖这种融合技术来保证存储分配时会得到可用的较大空闲存储块。但利用较大的邻接存储块，不仅从逻辑上，而且在物理上的执行效率来看都是十分必要的。更重要的是一个数据集合的所有数据能存放在一块邻接的可访问区，就会减少那些常规外部设备的某些操作。
第八章 动态存储管理第 50页把空闲存储块紧凑成一片十分必要，但这需要移动正在被使用的存储块，这不是件易事。因为这时占用的存储区的信息，有可能被程序引用而正在和外部设备进行传输，此时该存储块的信息决不能移动，否则会造成信息传输的错误。所以存储紧缩的条件是：
已占用的存储块均可移动而重新定位。当整个存储区由加标志过程将正在使用的存储块都打上占用标记后
，即可开始进行存储紧缩的工作。
存储紧缩的方法是,把被占用的存储块信息，集中在相邻的一片存储块中，使它们处于存储区域的一端（低地址端），而另一端（高地址端）就空出了一整块空闲存储区，或相邻接的若干空闲存储块 。
存 储 紧 缩第八章 动态存储管理第 51页示例 5 堆存储管理存储紧缩方法之一：
一旦有用户释放存储块即进行回收紧缩。 示意如下
0 1 2 3 4 5 6 7 8 9
10
20
30
40
50
60
70
80
90
free free
10
20
30
40
50
60
70
80
90
0 1 2 3 4 5 6 7 8 9
12 0
6 12
10 18
8 28
A
B
C
D
lengthstadr
(b)
(a)
(c)
12 0
6 12
8 18
A
B
D
lengthstadr
(d)
图 8.12 堆存储管理示意图
(a) 堆空间； (b) 串的存储映象；
(c) 紧缩后的堆； (d) 修改后的存储映象第八章 动态存储管理第 52页示例 6 堆存储管理存储紧缩方法之二,在程序执行过程中不回收用户随时释放的存储块，直到可利用空间不够分配或堆指针指向最高地址时才能进行存储紧缩 —— 将堆中所有的空闲块连成一片，即将所有的占用块都集中到可利用空间的低地址区，而剩余的高地址区成为一整个地址连续的空闲块 。示意如下
free free (b)(a)
图 8.13 紧缩前后的堆（存储空间）
(a) 紧缩前； (b) 紧缩后第八章 动态存储管理第 53页第八章 动态存储管理 小结内容提要
动态存储管理的基本问题及方法
利用可利用空间表进行动态存储管理的分配策略
操作系统中用以进行动态存储管理的边界标识法和伙伴系统
无用 单元收集时的标志算法
存储紧缩学习要点
深刻理解有关动态存储管理的各种概念及方法
了解可利用空间表的三种分配策略的差异及优缺点
掌握边界标识法的分配与回收算法
掌握伙伴系统方法的分配与回收算法
了解无用 单元收集中标志算法的作用
