算法与数据结构：第八章 动态存储管理

1、第八章 动态存储管理8.1 概述8.2 边界标识法8.3 伙伴系统8.4 无用单元收集8.5 存储紧缩习题1数据结构-第八章 动态存储管理8.1 概述动态存储管理 指系统随机地根据用户程序申请空间的大小，进行分配空间和回收不用空间所进行的内存管理。动态存储管理的一种方法 建立可利用空间表(自由空间表/存储池)，将所有可利用的空闲内存块链接起来。内存空间的初始状态系统运行一段时间后内存的状态2数据结构-第八章 动态存储管理三种基本分配策略首次拟合法：分配找到的第一个不小于n的空闲块 的一部分。操作方便，查找快捷最佳拟合法：分配不小于n且最接近n的空闲块的一部分。尽可能将大的空闲块留给大程序使用最

2、差拟合法：分配不小于n且是最大的空闲块的一部分。尽可能减少分配后无用碎片3数据结构-第八章 动态存储管理8.2 边界标识法双向循环链表的应用8.2.1 可利用空间表的结点结构 llink tag size rlink space uplink taghead(块头)foot(块尾)size标志位： tag= 1 占用块 0 空闲块块尾的作用：简化回收算法size以“字”为单位，head和foot各占一个字空间。4数据结构-第八章 动态存储管理8.2.2 分配算法 (申请容量为n的存储空间)假设采用首次分配法，为避免过多碎片，设一常量e m-n e 将大小为m的块全部分出 e 分出n大小，剩余留

3、下为使分配后剩余的小块均匀分布在链表中，可利用空间链表的头指针pav在每次分配之后，指向被分配块的后继块pav5数据结构-第八章 动态存储管理算法思想 从p=pav开始查找一块容量n的空闲块，结果有三种情况1) p-size n且p-size -ne ：分配p整块置tag=1从可利用空间表中删除此块pav指向被分配块的后继块2) p-size n且p-size -ne ：分配p块高地址部分大小为n的块修改剩余块的头部设置剩余块的尾部设置占用块的头部修改占用块的尾部pav指向被分配块的后继块3) 未找到，无法分配pn6数据结构-第八章 动态存储管理8.2.3 回收算法 设释放块的首地址指针为p，

4、大小为n，分四种情况：1) (p-1)-tag=1 且 (p+n)-tag=1 释放块的左右邻块均为占用块 将释放块插入到pav所指的结点之后或之前；2) (p-1)-tag=0 且 (p+n)-tag=1 释放块的左邻块为空闲块，右邻块为占用块 将释放块合并到左邻块的底部，并修改相应的信息；3) (p-1)-tag=1 且 (p+n)-tag=0 释放块的左邻块为占用块，右邻块为空闲块 将释放块合并到右邻块的顶部，并修改相应的信息4) (p-1)-tag=0 且 (p+n)-tag=0 释放块的左右邻块均为空闲块 从链表上删除右邻块，将释放块和右邻块一起合并到左邻块的底部pn7数据结构-第八

5、章 动态存储管理比较边界标志法分别采用最佳适配和首次适配策略时，在数据结构、分配算法和回收算法上有何不同。 最佳适配 首次适配 数据结构 分配算法 回收算法 空闲块应由小到大顺序链接，头指针应始终指向最小的空闲块。采用单链表即可。无本质区别。必须保持表的有序性要使大小不同的块在分配时被随机选择，应采用循环链表，并使头指针经常移动。进行合并或在头指针处插入即可边界标示法的问题 查找适合需要的块，需要较多的时间 查找适合需要的块的策略（最先/最佳/最坏），每种都有缺陷 碎片问题8数据结构-第八章 动态存储管理8.3 伙伴系统索引+双循环链表伙伴系统原理伙伴系统的空闲块大小以2k（k=0,1,2,m

6、） 标定。按k值不同组织成多个双循环链表。系统起始时只有一个空闲块， 大小为 2m 。用户申请内存时，就将刚好满足用户需求的 2k大小的空闲块分配给用户；若不存在 2k 大小的空闲块，就找到k值更大的空闲块，将其分为两半（互称伙伴），按此直至分出2k大小给用户，被分出的其它空闲块加入对应的循环链表中。回收时，只有伙伴才合并，并将合并后的新空闲块加入上一级大小的空闲块链表中。9数据结构-第八章 动态存储管理“伙伴”的概念 当把一个存储块分为大小相等的两半时，则它们互为伙伴。大小为2k的伙伴的首地址之间的关系起始地址为p，大小为2k的内存块，其伙伴的起始地址为：buddy(p, k)= p+2k

7、=xx.x100.0 当 p mod 2k+1 =0 p-2k = xx.x000.0 当 p mod 2k+1 =2k(0)0000(8)10000000010010001100232322222222212100000010k个010数据结构-第八章 动态存储管理8.3.1 可利用空间表的结点结构 llink tag kval rlink space存储管理方式按k值索引，相同k值的块构成子表(双链表)header(块头)标志位： tag= 1 占用块 0 空闲块202k2m0km 0 k 0 knodesize first11数据结构-第八章 动态存储管理8.3.2 分配算法 (申请容量

8、为n的存储空间)算法思想1)计算k值：k=log2n2)从子表k开始找可用的块 2.1)k子表有，取出分配，结束； 2.2)否则，若从k向下找到i (ik)子表有可用块 (起始地址为p)，则取出2k分配，剩余的块 大小 2i-1 2i-2 . . 2k 起始地址 p+2i-1 p+ 2i-2 . . p+2k 插入相应的子表。p2i分配2k2i-1 2i-212数据结构-第八章 动态存储管理8.3.3 回收算法算法思想 考虑合并 设归还块的起始地址为p，大小为2k1)计算p的伙伴块的地址q：q=buddy(p,k)2)若q空闲，合并出起始地址为p=minp，q， 大小为2k+1的块； 将q从k

9、子表中删除； 修改k：k=k+1，转1)3)若q被占用，则将起始地址为p，大小为2k的块插 入k子表中。ppqq2k 2k 2k2k13数据结构-第八章 动态存储管理8.3.4 Buddy算法分析多个空闲队列，可以立即找到空闲块避免了碎片问题申请内存总是以2n字节满足要求，块内浪费 例如：申请130字节，会分得256字节;申请1514字节，会分得2048字节申请/释放可能会导致连锁切块/合并，影响系统效率 例如：当前只有一块空闲，块大小1M, 申请40字节，会导致12次切块，用完立即归还，导致12次合并。如果程序循环式申请40字节，然后归还内存，会导致系统频繁忙碌。14数据结构-第八章 动态存储管理Lazy-Buddy 解决申请/释放可能会导致连锁切块/合并。该合并时，通过一定“lazy”策略,暂时不合并，在合适的时机合并Slab 最早出现在Solaris, 在Linux中采用 避免了碎片问题，并且与内存的分页系统很好配合工作，分配归还的效率很高。 基本思路：每次申请一个内存页面（4096字节）或者多个，切割成所需要的固定大小。不同大小的内存申请，使用不同的空闲队列。其它算法15数据结构-第八章 动态存储管理习题 假设利用边界标识法首次匹配策略分配，已知在某个时刻的可利用空间表如下： （1）请画出当系统回收一个起始地址为559、大小为4