1 / 22
文档名称:

第八章动态存储管理课件.ppt

格式:ppt   大小:1,094KB   页数:22页
下载后只包含 1 个 PPT 格式的文档,没有任何的图纸或源代码,查看文件列表

如果您已付费下载过本站文档,您可以点这里二次下载

分享

预览

第八章动态存储管理课件.ppt

上传人:aluyuw1 9/19/2022 文件大小:1.07 MB

下载得到文件列表

第八章动态存储管理课件.ppt

相关文档

文档介绍

文档介绍:第八章动态存储管理
动态存储管理概述
存储原理
计算机内存在刚开始工作时,空闲部分是一个整块的连续区域;
随着用户进入系统,多次申请和释放内存以后,空闲部分不再是连续的了,而成了多个空闲区。常用链表管理,即可利用空间表
动态存储管理
指系统随机地根据用户程序申请空间的大小,进行分配空间和回收不用空间所进行的内存管理。
内存的初始状态
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且是最大的空闲块的一部分。
尽可能减少分配后无用碎片;

用以进行动态分区分配的一种管理方法
可利用空间表的结点结构
边界标识法的数据结构
structBLK
{
structBLK*llink;
#defineulinkllink//ulink直接利用llink域
inttag;
intsize;/*不包括头和脚占用的空间,必须是sizeof(structBLK)的倍数*/
structBLK*rlink;
};
#defineFootLoc(p)\
(structBLK*)((char*)p+sizeof(structBLK)+p->size)
分配算法描述
void*mem_alloc(intnbytes)
{
#defineusizeof(structBLK);
修正nbytes=(nbytes+u-1)/u*u;/*u为2n有:nbytes=(nbytes+u-1)&~(u-1)*/
从链表中找满足size>=nbytes的块p;
if(p==NULL)returnNULL;
if(p->size–nbytes<=EPSILON){
p脱离空闲链;
p->tag=FootLoc(p)->tag=1;
returnp+1;
}else{
p->size-=nbytes+2*sizeof(structBLK);
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;
returnp+1;
}
}
回收算法
根据回收缓冲区地址,找到当前内存块的管理信息
p=(structBLK*)buf–1;
与此内存块紧邻的,处于高地址端的内存块的管理信息
h=(structBLK*)((char*)(p+2)+p->size);
与此内存块紧邻的,处于低地址端的内存块的管理信息
l=(p-1)->uplink;
判l->tag和h->tag,知低端/高端内存块是否空闲,决定是否和低端/高端空闲块合并
回收算法描述
voidmem_free(void*buf)
{
p=(structBLK*)buf–1;
p->tag=FootLoc(p)->tag=0;
h=(structBLK*)((char*)(p+2)+p->size);
if(h->tag==0){
h脱离空闲块链表;
FootLoc(h)->uplink=p;
p->size+=h->size+2*sizeof(structBLK);
}
l=(p-1)->uplink;
if(l->tag){
将p加入到空闲块链表;
}else{
l->size+=p->size+2*sizeof(structBLK);
FootLoc(p)->uplink=l;
}
}
(上述算法未考虑p为可分配空间第一块和最后一块的特殊情况)
边界表示法的问题
查找适合需要的块,需要较多的时间
查找适合需要的块的策略(最先/最佳/最坏),每种都有缺陷
碎片问题