第八章动态存储管理

1、第八章第八章 动态存储管理动态存储管理 动态存储管理概述动态存储管理概述p存储原理n计算机内存在刚开始工作时，空闲部分是一个整块的计算机内存在刚开始工作时，空闲部分是一个整块的连续区域；连续区域；n随着用户进入系统，多次申请和释放内存以后，空闲随着用户进入系统，多次申请和释放内存以后，空闲部分不再是连续的了，而成了多个空闲区。常用链表部分不再是连续的了，而成了多个空闲区。常用链表管理，即可利用空间表管理，即可利用空间表n动态存储管理动态存储管理p指系统随机地根据用户程序申请空间的大小，进行分配空间和回收不用空间所进行的内存管理。 内存的初始状态u1u2u3u4 系统运行初期u2u4 系统运行若

2、干时后可利用空间表及分配方法可利用空间表及分配方法p可利用空间表n将所有内存空闲块用链表连接而成；将所有内存空闲块用链表连接而成；n空闲块的大小可以是全相同的，也可以是分成若干固空闲块的大小可以是全相同的，也可以是分成若干固定大小的，还可以是随机大小的。定大小的，还可以是随机大小的。tag size linkspacetag=0：空闲tag=1：使用av 0 2000 3000 150.分配方法分配方法p首次拟合法n分配找到的第一个不小于分配找到的第一个不小于n的空闲块的一部分。的空闲块的一部分。n操作方便，查找快捷；操作方便，查找快捷；p最佳拟合法n分配不小于分配不小于n且最接近且最接近n的

3、空闲块的一部分。的空闲块的一部分。n尽可能将大的空闲块留给大程序使用；尽可能将大的空闲块留给大程序使用；p最坏拟合法n分配不小于分配不小于n且是最大的空闲块的一部分。且是最大的空闲块的一部分。n尽可能减少分配后无用碎片；尽可能减少分配后无用碎片；内存的分配与回收内存的分配与回收p分配n根据申请内存大小利用相应的分配策略分配给用户所根据申请内存大小利用相应的分配策略分配给用户所需的空间；需的空间；n若分配块大小与申请大小相差不多，则将此块全部分若分配块大小与申请大小相差不多，则将此块全部分给用户；给用户；n否则，就需将分配块分为两部分，一部分给用户使用，否则，就需将分配块分为两部分，一部分给用户

4、使用，另一部分继续留在可利用空间表中。另一部分继续留在可利用空间表中。p回收n测试回收块前后相邻内存块是否空闲；测试回收块前后相邻内存块是否空闲；n若是则需将回收块与相邻空闲块合并成较大的空闲块，若是则需将回收块与相邻空闲块合并成较大的空闲块，再链入可利用空间表中。再链入可利用空间表中。8.3 边界标识法边界标识法p用以进行动态分区分配的一种管理方法p可利用空间表的结点结构llink tag size rlinkuplink tagheadfoot边界标识法的数据结构边界标识法的数据结构struct blk struct blk *llink;#define ulink llink /ulin

5、k直接利用llink域 int tag;int size; /* 不包括头和脚占用的空间,必须是sizeof(struct blk)的倍数 */struct blk *rlink;#define footloc(p) (struct blk *)(char *)p + sizeof(struct blk) + p-size) 分配算法分配算法p将所有的空闲块链接在一个双重循环链表结构的可利用空间表中；p分配可按首次拟合法或最佳拟合法进行；p为避免过多碎片，设一常量epsilonnm-n epsilon将大小为将大小为m的块全部分出的块全部分出n epsilon分出分出n大小，剩余留下大小，剩余

6、留下分配算法描述分配算法描述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 tag = footloc(p)-tag = 1; return p+1; else p-size -= nbytes + 2 * sizeof(struct blk

7、); 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根据回收缓冲区地址，找到当前内存块的管理信息 p = (struct blk *)buf 1;p与此内存块紧邻的，处于高地址端的内存块的管理信息 h = (struct blk *)(char *)(p+2) + p-size);p与此内存块紧邻的，处于低地址端的内存块的管理信息 l = (p-1)-upli

8、nk;p判l-tag和h-tag，知低端/高端内存块是否空闲，决定是否和低端/高端空闲块合并回收算法描述回收算法描述void mem_free(void *buf) p = (struct blk *)buf 1; p-tag = footloc(p)-tag = 0; h = (struct blk *)(char *)(p+2) + p-size); if (h-tag = 0) h脱离空闲块链表； footloc(h)-uplink = p; p-size += h-size + 2 * sizeof(struct blk); l = (p-1)-uplink; if (l-tag) 将

9、p加入到空闲块链表； else l-size += p-size + 2 * sizeof(struct blk); footloc(p)-uplink = l; (上述算法未考虑p为可分配空间第一块和最后一块的特殊情况)边界表示法的问题边界表示法的问题p查找适合需要的块，需要较多的时间p查找适合需要的块的策略（最先/最佳/最坏），每种都有缺陷p碎片问题8.4 伙伴系统伙伴系统p伙伴系统的空闲块大小以2k (k=n, n+1,n+2,m)标定。按k值不同组织成多个空闲块链表av。设n=5,最小分配32字节，用一张位图维护内存中每个32字节块的使用情况(1:已分配,0:空闲)p系统开始时只有一个

10、空闲块，大小为2m p分配(访问链表avk)n将满足用户需求的将满足用户需求的2 2k k大小的空闲块分配给用户大小的空闲块分配给用户navkavk链表空，就找链表空，就找2 2k+1k+1的空闲块，将其分为两半的空闲块，将其分为两半( (互称伙互称伙伴伴) )，一半给用户，另一半加入，一半给用户，另一半加入avkavk链表中链表中p回收:n只有伙伴才合并，并将合并后的新空闲块加入上一级大只有伙伴才合并，并将合并后的新空闲块加入上一级大小的空闲块链表中。小的空闲块链表中。伙伴系统（续）伙伴系统（续）例：大小128字节，首地址为0 xe580的内存块，其伙伴为0 xe500例：大小128字节，首

11、地址为0 xf600的内存块，其伙伴为0 xf680buddy(k,z)=z+2k 当 z mod 2k+1 = 0z - 2k 当 z mod 2k+1 = 2kp首地址为z，大小为2k的内存块，其伙伴为分配和回收算法分配和回收算法 p分配算法当用户申请大小为当用户申请大小为n n的内存请求的内存请求, ,在可利用空间表上寻找在可利用空间表上寻找结点大小与结点大小与n n相匹配的表相匹配的表p表非空，分配表中第一个内存块p表空，从更大的非空表中查找，直到找到一个空闲块，切割出所需要大小的块p未分配部分，插入到相应的空闲表中p回收算法判断伙伴是否为空闲块判断伙伴是否为空闲块( (回收算法需了解

12、释放的块大小回收算法需了解释放的块大小) )p否，将释放的空闲块插入到相应表中；p是，找到伙伴，伙伴出队，合并p合并后，判断合并后的块的伙伴是否是空闲块，如果是，继续合并成更大的块。依次重复，直到归并后的块的伙伴不空闲。再插入到相应的空闲块表中。举例举例:阶段阶段1 分配256,128,64之后,分别是b,c,d举例：阶段举例：阶段2申请128（块f),释放128(块c）举例：阶段举例：阶段3 释放64(块d）伙伴系统的数据结构伙伴系统的数据结构struct blk int kval; struct blk *prev, *next;struct blk *avm; / 多个空闲链表应当使用双

13、向循环链表结构buddy算法分析算法分析n可以立即找到空闲块可以立即找到空闲块n避免了碎片问题避免了碎片问题n申请内存总是以申请内存总是以2n字节满足要求，块内浪费字节满足要求，块内浪费 例如：申请例如：申请130130字节，会分得字节，会分得256256字节字节; ;申请申请15141514字节，会分得字节，会分得20482048字节字节n申请申请/释放可能会导致连锁切块释放可能会导致连锁切块/合并，影响系统效率合并，影响系统效率 例如：当前只有一块空闲，块大小例如：当前只有一块空闲，块大小1m, 1m, 申请申请4040字节，会导致字节，会导致1212次次切块，用完立即归还，导致切块，用完

14、立即归还，导致1212次合并。如果程序循环式申请次合并。如果程序循环式申请4040字字节，然后归还内存，会导致系统频繁忙碌。节，然后归还内存，会导致系统频繁忙碌。其它算法其它算法nlazy-buddy 解决申请解决申请/ /释放可能会导致连锁切块释放可能会导致连锁切块/ /合并。该合并时，通过一定合并。该合并时，通过一定“lazy”lazy”策略策略, ,暂时不合并，在合适的时机合并暂时不合并，在合适的时机合并nslab 最早出现最早出现在在solaris, 在在linux中采用中采用 避免了碎片问题，并且与内存的分页系统很好配合工作，分配归避免了碎片问题，并且与内存的分页系统很好配合工作，分配归还的效率很高。还的效率很高。 基本思路：每次申请一个内存页面（基本思路：每次申请一个内存页面（4096字节）或者多个，切割字节）或者多个，切割成所需要的固定大小。不同大小的内存申请，使用不同的空闲队成所需要的固定大小。不同大小的内存申请，使用不同的空闲队列。列。作业作业1.边界标识