《八章节动态存储管理》由会员分享，可在线阅读，更多相关《八章节动态存储管理（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) 如何判断它的伙伴能否与它合并如何判断它的伙伴能否与它合并 粘故膀兑乃靶戈几媚孵圆瑞荤刨壤羔状犁菇磷说嗅酒炼帖考咨挎瞧豆秸员八章节动态存储管理八章节动态存储管理
