文档介绍：数据结构与算法Data Structure Algorithms

烟台南山学院信息科技学院
数据结构与算法教学组
动态存储管理概述
存储原理
计算机内存在刚开始工作时,空闲部分是一个整块的连续区域;
随着用户进入系统,多次申请和释放内存以后,空闲部分不再是连续的了,而成了多个空闲区。常用链表管理,即可利用空间表
动态存储管理
指系统随机地根据用户程序申请空间的大小,进行分配空间和回收不用空间所进行的内存管理。
内存的初始状态
U1
U2
U3
U4
系统运行初期
U2
U4
系统运行若干时后
可利用空间表及分配方法
可利用空间表
将所有内存空闲块用链表连接而成;
空闲块的大小可以是全相同的,也可以是分成若干固定大小的,还可以是随机大小的。
tag
size
link
space
tag=0:空闲
tag=1:使用
av
0
200
0
300
0
150
...
分配方法
首次拟合法
分配找到的第一个不小于n的空闲块的一部分。
操作方便,查找快捷;
最佳拟合法
分配不小于n且最接近n的空闲块的一部分。
尽可能将大的空闲块留给大程序使用;
最坏拟合法
分配不小于n且是最大的空闲块的一部分。
尽可能减少分配后无用碎片;
内存的分配与回收
分配
根据申请内存大小利用相应的分配策略分配给用户所需的空间;
若分配块大小与申请大小相差不多,则将此块全部分给用户;
否则,就需将分配块分为两部分,一部分给用户使用,另一部分继续留在可利用空间表中。
回收
测试回收块前后相邻内存块是否空闲;
若是则需将回收块与相邻空闲块合并成较大的空闲块,再链入可利用空间表中。
边界标识法
用以进行动态分区分配的一种管理方法
可利用空间表的结点结构
边界标识法的数据结构
struct BLK
{
struct BLK *llink;
#define ulink llink //ulink直接利用llink域
int tag;
int size; /* 不包括头和脚占用的空间,必须是sizeof(struct BLK)的倍数*/
struct BLK *rlink;
};
#define FootLoc(p) \
(struct BLK *)((char *)p + sizeof(struct BLK) + p->size)
分配算法
将所有的空闲块链接在一个双重循环链表结构的可利用空间表中;
分配可按首次拟合法或最佳拟合法进行;
为避免过多碎片,设一常量EPSILON
m-n  EPSILON将大小为m的块全部分出
> EPSILON分出n大小,剩余留下
分配算法描述
void *mem_alloc(int nbytes)
{
#define u sizeof(struct BLK);
修正nbytes = (nbytes + u -1) / u * u; /*u为2n有:nbytes = (nbytes+u-1)&~(u-1) */
从链表中找满足size>=nbytes的块p;
if (p==NULL) return NULL;
if (p->size – nbytes <= EPSILON) {
p脱离空闲链;
p->tag = FootLoc(p)->tag = 1;
return p+1;
} else {
p->size -= nbytes + 2 * sizeof(struct BLK);
f = FootLoc(p); f->tag = 0; f->uplink = p;
p = f + 1; p->tag = 1; p->size = nbytes;
f = FootLoc(p); f->tag = 1; f->uplink = p;
return p+1;
}
}
回收算法
根据回收缓冲区地址,找到当前内存块的管理信息
p = (struct BLK *)buf – 1;
与此内存块紧邻的,处于高地址端的内存块的管理信息
h = (struct BLK *)((char *)(p+2) + p->size);
与此内存块紧邻的,处于低地址端的内存块的管理信息
l = (p-1)->uplink;
判l->tag和h->tag,知低端/高端内存块是否空闲,决定是否和低端/高端空闲块合并