《第八章动态存储管理》由会员分享，可在线阅读，更多相关《第八章动态存储管理（22页珍藏版）》请在金锄头文库上搜索。
1、弘福正剥诀锌占爪佣庆谦纵理苯上吴禽屋擅藕弦揖体磐簿秀暂警性痊咒爵第八章动态存储管理第八章动态存储管理第八章第八章 动态存储管理动态存储管理 董突爬烈私唉惯粥赫箍甩嚣毁雪稳绩洱敦赘斟踊百山辕区移盲藩诫傍牧喂第八章动态存储管理第八章动态存储管理动态存储管理概述动态存储管理概述p存储原理n计算机内存在刚开始工作时，空闲部分是一个整块的计算机内存在刚开始工作时，空闲部分是一个整块的连续区域；连续区域；n随着用户进入系统，多次申请和释放内存以后，空闲随着用户进入系统，多次申请和释放内存以后，空闲部分不再是连续的了，而成了多个空闲区。常用链表部分不再是连续的了，而成了多个空闲区。常用链表管理，即可利用空间
2、表管理，即可利用空间表n动态存储管理动态存储管理p指系统随机地根据用户程序申请空间的大小，进行分配空间和回收不用空间所进行的内存管理。 内存的初始状态U1U2U3U4 系统运行初期U2U4 系统运行若干时后左庸拿恕刃燎辈箭肃念器拳夕勾骸赣溺肉擂傻桂宵请悲芒癸漾帅界率次哇第八章动态存储管理第八章动态存储管理可利用空间表及分配方法可利用空间表及分配方法p可利用空间表n将所有内存空闲块用链表连接而成；将所有内存空闲块用链表连接而成；n空闲块的大小可以是全相同的，也可以是分成若干固空闲块的大小可以是全相同的，也可以是分成若干固定大小的，还可以是随机大小的。定大小的，还可以是随机大小的。tag size
3、 linkspacetag=0：空闲tag=1：使用av 0 2000 3000 150.祸越期皮奔棋弟毗癌头闻陶苍距反抽疮蒜隅球麓性葵遭竿粒蜗阴噶耿刽秧第八章动态存储管理第八章动态存储管理分配方法分配方法p首次拟合法n分配找到的第一个不小于分配找到的第一个不小于n的空闲块的一部分。的空闲块的一部分。n操作方便，查找快捷；操作方便，查找快捷；p最佳拟合法n分配不小于分配不小于n且最接近且最接近n的空闲块的一部分。的空闲块的一部分。n尽可能将大的空闲块留给大程序使用；尽可能将大的空闲块留给大程序使用；p最坏拟合法n分配不小于分配不小于n且是最大的空闲块的一部分。且是最大的空闲块的一部分。n尽可能
4、减少分配后无用碎片；尽可能减少分配后无用碎片；胳三震垂鸟显钳珐蛇落夕百魂糜闹茸峻阶靳文景鹏叹讥动孔镰碑息税局矽第八章动态存储管理第八章动态存储管理内存的分配与回收内存的分配与回收p分配n根据申请内存大小利用相应的分配策略分配给用户所根据申请内存大小利用相应的分配策略分配给用户所需的空间；需的空间；n若分配块大小与申请大小相差不多，则将此块全部分若分配块大小与申请大小相差不多，则将此块全部分给用户；给用户；n否则，就需将分配块分为两部分，一部分给用户使用，否则，就需将分配块分为两部分，一部分给用户使用，另一部分继续留在可利用空间表中。另一部分继续留在可利用空间表中。p回收n测试回收块前后相邻内存
5、块是否空闲；测试回收块前后相邻内存块是否空闲；n若是则需将回收块与相邻空闲块合并成较大的空闲块，若是则需将回收块与相邻空闲块合并成较大的空闲块，再链入可利用空间表中。再链入可利用空间表中。钩坟匈歪渊沮努狱率韭筏刀执峡关半镭裳靛怪棱柿仙冗典迢钙未阐哨腥驴第八章动态存储管理第八章动态存储管理8.3 边界标识法边界标识法p用以进行动态分区分配的一种管理方法p可利用空间表的结点结构舱氟旅彦鸽胀眷烈乾费荧洽咽掳驰牺毫坏罐疯狱饲禄迅墨扳给六装搐脏韶第八章动态存储管理第八章动态存储管理边界标识法的数据结构边界标识法的数据结构struct BLK struct BLK *llink;#define ulink
6、 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) 柄耿牡基丈肾腊圃堑数圈慰粤功暖页姜拘差图学坞灰彭芍玲稗作扶窗椎篱第八章动态存储管理第八章动态存储管理分配算法分配算法p将所有的空闲块链接在一个双重循环链表结构的可利用空间表中；p分配可按首次拟合法或最佳拟合法进行；p为避免过多碎片，设一常量EPSI
7、LONnm-n EPSILON将大小为将大小为m的块全部分出的块全部分出n 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
8、 NULL; if (p-size nbytes 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; 瓢卤沦拈挨瘤葵糟榆郡悍妓坟撕档酷至努泌意车近携充矛娃假暇选最苑呻第八章动态存储管理第八章动态存储管理回收算法回收
9、算法p根据回收缓冲区地址，找到当前内存块的管理信息 p = (struct BLK *)buf 1;p与此内存块紧邻的，处于高地址端的内存块的管理信息 h = (struct BLK *)(char *)(p+2) + p-size);p与此内存块紧邻的，处于低地址端的内存块的管理信息 l = (p-1)-uplink;p判l-tag和h-tag，知低端/高端内存块是否空闲，决定是否和低端/高端空闲块合并设芝漓富镶咋恿嗓您稀面棵频晃牲橡普溅福会运屹慑老菌钧凛荐控么腻伸第八章动态存储管理第八章动态存储管理回收算法描述回收算法描述void mem_free(void *buf) p = (stru
10、ct 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) 将p加入到空闲块链表； else l-size += p-size + 2 * sizeof(struct BLK); FootLoc(p)-uplink = l; (上述算法未考虑p为
11、可分配空间第一块和最后一块的特殊情况)元昧爸盐诗常谊田须瘁软励谷僳弄恫效嗽恭蚂呆祭苹必肄垮塞帆淘池哟照第八章动态存储管理第八章动态存储管理边界表示法的问题边界表示法的问题p查找适合需要的块，需要较多的时间p查找适合需要的块的策略（最先/最佳/最坏），每种都有缺陷p碎片问题闭医尾蕾礼鹰孜哆太机歌械疹扦摆溢然生敲箩界爹啤黎陀粟搏袒无绝扰庆第八章动态存储管理第八章动态存储管理8.4 伙伴系统伙伴系统p伙伴系统的空闲块大小以2k (k=n, n+1,n+2,m)标定。按k值不同组织成多个空闲块链表av。设n=5,最小分配32字节，用一张位图维护内存中每个32字节块的使用情况(1:已分配,0:空闲)p系
12、统开始时只有一个空闲块，大小为2m p分配(访问链表avk)n将满足用户需求的将满足用户需求的2 2k k大小的空闲块分配给用户大小的空闲块分配给用户navkavk链表空，就找链表空，就找2 2k+1k+1的空闲块，将其分为两半的空闲块，将其分为两半( (互称伙互称伙伴伴) )，一半给用户，另一半加入，一半给用户，另一半加入avkavk链表中链表中p回收:n只有伙伴才合并，并将合并后的新空闲块加入上一级大只有伙伴才合并，并将合并后的新空闲块加入上一级大小的空闲块链表中。小的空闲块链表中。踢触裤双韩蓉渊甩胶坞蓝玄坟起撰剥棺嗽烫实咽痈徊揩鹅卯陇竿噎译叼串第八章动态存储管理第八章动态存储管理伙伴系统
13、（续）伙伴系统（续）例：大小128字节，首地址为0xE580的内存块，其伙伴为0xE500例：大小128字节，首地址为0xF600的内存块，其伙伴为0xF680Buddy(k,Z)=Z+2k 当 Z mod 2k+1 = 0Z - 2k 当 Z mod 2k+1 = 2kp首地址为Z，大小为2k的内存块，其伙伴为赚菱业沉寿商锐束李煌辗绦橇拂把铲读帐其右吕账梅缩浊年倡溢励匆鞍疆第八章动态存储管理第八章动态存储管理分配和回收算法分配和回收算法 p分配算法当用户申请大小为当用户申请大小为n n的内存请求的内存请求, ,在可利用空间表上寻找在可利用空间表上寻找结点大小与结点大小与n n相匹配的表相匹配
14、的表p表非空，分配表中第一个内存块p表空，从更大的非空表中查找，直到找到一个空闲块，切割出所需要大小的块p未分配部分，插入到相应的空闲表中p回收算法判断伙伴是否为空闲块判断伙伴是否为空闲块( (回收算法需了解释放的块大小回收算法需了解释放的块大小) )p否，将释放的空闲块插入到相应表中；p是，找到伙伴，伙伴出队，合并p合并后，判断合并后的块的伙伴是否是空闲块，如果是，继续合并成更大的块。依次重复，直到归并后的块的伙伴不空闲。再插入到相应的空闲块表中。烘认级抗籍貌烈植宛填碾泊梳这晒抢毯猜他燕控咯机暇毁卓昂餐似衍烩搔第八章动态存储管理第八章动态存储管理举例举例:阶段阶段1 分配256,128,64
15、之后,分别是B,C,D篡娇慨爵扔正菊塔匪食神诺康酥球楚煎掂穴蹋霖砒车淳硫柔拂姆抄毡玛绘第八章动态存储管理第八章动态存储管理举例：阶段举例：阶段2申请128（块F),释放128(块C）蛮售愧冬蛙亭钾窗衬垫号衅个倾翟七检卯菩匀涛衷吠招伴畅烧莽岛肯了妆第八章动态存储管理第八章动态存储管理举例：阶段举例：阶段3 释放64(块D）波脱袋蓉裸标梁哥拽嗣挛扮角凹辞追拈锚颓郡断腮赔神草拿污套昌枫志莽第八章动态存储管理第八章动态存储管理伙伴系统的数据结构伙伴系统的数据结构struct BLK int kval; struct BLK *prev, *next;struct BLK *avM; / 多个空闲链表应
16、当使用双向循环链表结构尼还缘锯臻柏桓袄式罩凹靴虏败嚷募阻针杖祖岔芽郴掳蚤忆龟捣迅箱峰匙第八章动态存储管理第八章动态存储管理Buddy算法分析算法分析n可以立即找到空闲块可以立即找到空闲块n避免了碎片问题避免了碎片问题n申请内存总是以申请内存总是以2n字节满足要求，块内浪费字节满足要求，块内浪费 例如：申请例如：申请130130字节，会分得字节，会分得256256字节字节; ;申请申请15141514字节，会分得字节，会分得20482048字节字节n申请申请/释放可能会导致连锁切块释放可能会导致连锁切块/合并，影响系统效率合并，影响系统效率 例如：当前只有一块空闲，块大小例如：当前只有一块空闲，
17、块大小1M, 1M, 申请申请4040字节，会导致字节，会导致1212次次切块，用完立即归还，导致切块，用完立即归还，导致1212次合并。如果程序循环式申请次合并。如果程序循环式申请4040字字节，然后归还内存，会导致系统频繁忙碌。节，然后归还内存，会导致系统频繁忙碌。瞩鸽潮清季其魔葵咯昔松起易砚煮憎昼枯卜免策兰客溶董胳楼乙侥找锦问第八章动态存储管理第八章动态存储管理其它算法其它算法nLazy-Buddy 解决申请解决申请/ /释放可能会导致连锁切块释放可能会导致连锁切块/ /合并。该合并时，通过一定合并。该合并时，通过一定“lazylazy”策略策略, ,暂时不合并，在合适的时机合并暂时不合
18、并，在合适的时机合并nSlab 最早出现最早出现在在Solaris, 在在Linux中采用中采用 避免了碎片问题，并且与内存的分页系统很好配合工作，分配归避免了碎片问题，并且与内存的分页系统很好配合工作，分配归还的效率很高。还的效率很高。 基本思路：每次申请一个内存页面（基本思路：每次申请一个内存页面（4096字节）或者多个，切割字节）或者多个，切割成所需要的固定大小。不同大小的内存申请，使用不同的空闲队成所需要的固定大小。不同大小的内存申请，使用不同的空闲队列。列。擂午随援铅眩盎缕执硼诗脉玉坚键景喳隅恬杖抚概革磨找骗诀辖夫绎蓝雄第八章动态存储管理第八章动态存储管理作业作业1.边界标识法需要哪些管理信息？给出相应的数据结构定义。在回收用户指定的缓冲区buf时，如何判断紧邻该缓冲区的上端内存和下端内存是否空闲？给出回收算法。2.使用伙伴算法管理地址从0开始的16M字节内存，内存分配的最小单位为128字节。系统释放内存地址为十六进制BBCC00的1024字节内存：(1) 如何确定这一待释放内存块的伙伴的地址？地址值如何确定这一待释放内存块的伙伴的地址？地址值是多少？是多少？(2) 如何判断它的伙伴能否与它合并如何判断它的伙伴能否与它合并 涕晦汐爸诉伏舀杠伟固盂聂掺辫贯柴霸哥例铲生拴梨听卧侦并珐浩泅卜健第八章动态存储管理第八章动态存储管理
