文档介绍：第八章动态存储管理动态存储管理概述存储原理计算机内存在刚开始工作时,空闲部分是一个整块的连续区域;随着用户进入系统,多次申请和释放内存以后,空闲部分不再是连续的了,而成了多个空闲区。常用链表管理,即可利用空间表动态存储管理指系统随机地根据用户程序申请空间的大小,进行分配空间和回收不用空间所进行的内存管理。内存的初始状态U1U2U3U4系统运行初期U2U4系统运行若干时后可利用空间表及分配方法可利用空间表将所有内存空闲块用链表连接而成;空闲块的大小可以是全相同的,也可以是分成若干固定大小的,还可以是随机大小的。tagsizelinkspacetag=0:空闲tag=1:使用av020003000150...分配方法首次拟合法分配找到的第一个不小于n的空闲块的一部分。操作方便,查找快捷;最佳拟合法分配不小于n且最接近n的空闲块的一部分。尽可能将大的空闲块留给大程序使用;最坏拟合法分配不小于n且是最大的空闲块的一部分。尽可能减少分配后无用碎片;内存的分配与回收分配根据申请内存大小利用相应的分配策略分配给用户所需的空间;若分配块大小与申请大小相差不多,则将此块全部分给用户;否则,就需将分配块分为两部分,一部分给用户使用,另一部分继续留在可利用空间表中。回收测试回收块前后相邻内存块是否空闲;若是则需将回收块与相邻空闲块合并成较大的空闲块,再链入可利用空间表中。{structBLK*llink;#defineulinkllink//ulink直接利用llink域inttag; intsize;/*不包括头和脚占用的空间,必须是sizeof(structBLK)的倍数*/ structBLK*rlink;};#defineFootLoc(p)\(structBLK*)((char*)p+sizeof(structBLK)+p->size)分配算法将所有的空闲块链接在一个双重循环链表结构的可利用空间表中;分配可按首次拟合法或最佳拟合法进行;为避免过多碎片,设一常量EPSILONm-nEPSILON将大小为m的块全部分出>EPSILON分出n大小,剩余留下分配算法描述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,知低端/高端内存块是否空闲,决定是否和低端/高端空闲块合并