考研数据结构

数据结构---第八章动态存储管理1第八章动态存储管理8.1概述8.2边界标识法8.3伙伴系统8.4例题解析数据结构---第八章动态存储管理28.1概述[动态存储管理]

指系统随机地根据用户程序申请空间的大小，进行分配空间和回收不用空间所进行的内存管理。[动态存储管理的一种方法]

建立可利用空间表(自由空间表/存储池)，将所有可利用的空闲内存块链接起来。内存空间的初始状态系统运行一段时间后内存的状态数据结构---第八章动态存储管理3[三种基本分配策略]首次拟合法：分配找到的第一个不小于n的空闲块的一部分。操作方便，查找快捷最佳拟合法：分配不小于n且最接近n的空闲块的一部分。尽可能将大的空闲块留给大程序使用最差拟合法：分配不小于n且是最大的空闲块的一部分。尽可能减少分配后无用碎片数据结构---第八章动态存储管理48.2边界标识法—双向循环链表的应用8.2.1可利用空间表的结点结构

llinktagsizerlink

spaceuplinktagheader(块头)footer(块尾)size标志位：

tag=1占用块

0空闲块块尾的作用：简化回收算法数据结构---第八章动态存储管理5TYPEblkptr=^blk;blk=RECORDheader:RECORDllink,rlink:blkptr;tag:0..1;size:integerEND;space:ARRAY[1..size-2]OFdatatype;footer:RECORDuplink:blkptr;tag:0..1ENDEND;数据结构---第八章动态存储管理68.2.2分配算法(申请容量为n的存储空间)假设采用首次分配法，为避免过多碎片，设一常量em-ne将大小为m的块全部分出

>e分出n大小，剩余留下为使分配后剩余的小块均匀分布在链表中，可利用空间链表的头指针pav在每次分配之后，指向被分配块的后继块假设header和footer各占一个字的空间[算法思想]

从p=pav开始查找一块容量n的空闲块，结果有三种情况1)p^.sizen且p^.size-ne：分配p整块置tag=1从可利用空间表中删除此块pav指向被分配块的后继块数据结构---第八章动态存储管理72)p^.sizen且p^.size-n>e：分配p块高地址部分大小为n的块修改剩余块的头部设置剩余块的尾部设置占用块的头部修改占用块的尾部pav指向被分配块的后继块3)未找到，无法分配pnpav数据结构---第八章动态存储管理88.2.3回收算法

设释放块的首地址指针为p，大小为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

释放块的左右邻块均为空闲块从链表上删除右邻块，将释放块和右邻块一起合并到左邻块的底部pn数据结构---第八章动态存储管理9比较边界标志法分别采用最佳适配和首次适配策略时，在数据结构、分配算法和回收算法上有何不同。最佳适配首次适配数据结构

分配算法回收算法空闲块应由小到大顺序链接，头指针应始终指向最小的空闲块。采用单链表即可。无本质区别。必须保持表的有序性要使大小不同的块在分配时被随机选择，应采用循环链表，并使头指针经常移动。进行合并或在头指针处插入即可数据结构---第八章动态存储管理108.3伙伴系统—索引+双循环链表[伙伴系统原理]伙伴系统的空闲块大小以2k（k=0,1,2,…,m）标定。按k值不同组织成多个双循环链表。系统起始时只有一个空闲块，大小为2m

。用户申请内存时，就将刚好满足用户需求的2k大小的空闲块分配给用户；若不存在2k大小的空闲块，就找到k值更大的空闲块，将其分为两半（互称伙伴），按此直至分出2k大小给用户，被分出的其它空闲块加入对应的循环链表中。回收时，只有伙伴才合并，并将合并后的新空闲块加入上一级大小的空闲块链表中。数据结构---第八章动态存储管理11[“伙伴”的概念]

当把一个存储块分为大小相等的两半时，则它们互为伙伴。[大小为2k的伙伴的首地址之间的关系]起始地址为p，大小为2k的内存块，其伙伴的起始地址为：buddy(p,k)=p+2k=xx..x100...0

当pmod2k+1=0

p-2k=xx..x000...0当pmod2k+1=2k(0)0000(8)10000000010010001100232322222222212100000010k个0数据结构---第八章动态存储管理128.3.1可利用空间表的结点结构llinktagkvalrlink

space[存储管理方式]按k值索引，相同k值的块构成子表(双链表)header(块头)标志位：

tag=1占用块

0空闲块202k2m0km0k0knodesizefirst数据结构---第八章动态存储管理13TYPEfreeptr=^freenodefreenode=RECORDheader:RECORDllink,rlink:freeptr;tag:0..1;kval:integerEND;space:ARRAY[1..nodesize-1]OFdatatype;END;headnode=RECORDnodesize:integer;first:freeptr;END;

freelist=ARRAY[0..m]OFheadnode;数据结构---第八章动态存储管理148.3.2分配算法

(申请容量为n的存储空间)[算法思想]1)计算k值：k=log2n2)从子表k开始找可用的块

2.1)k子表有，取出分配，结束；

2.2)否则，若从k向下找到i(i>k)子表有可用块

(起始地址为p)，则取出2k分配，剩余的块

大小2i-12i-2......2k

起始地址p+2i-1p+2i-2......p+2k

插入相应的子表。p2i分配2k2i-12i-2数据结构---第八章动态存储管理158.3.3回收算法[算法思想]

考虑合并设归还块的起始地址为p，大小为2k1)计算p的伙伴块的地址q：q=buddy(p,k)2)若q空闲，合并出起始地址为p=min{p，q}，大小为2k+1的块；将q从k子表中删除；修改k：k=k+1，转1)3)若q被占用，则将起始地址为p，大小为2k的块插入k子表中。ppqq2k2k2k2k数据结构---第八章动态存储管理168.4例题解析1.二进制地址为，作为大小为16的块时，其伙伴的二进制地址是什么？（）mod24+1=24其伙伴地址为：-24=-10000=数据结构---第八章动态存储管理172.假设利用边界标识法首次匹配策略分配，已知在某个时刻的可利用空间表如下：（1）请画出当系统回收一个起始地址为559、大小为45的空闲块之后的链表状态；（2）请画出系统在之后接受大小为100的请求后又回收地址为515、大小为44的空闲块后的链表状态。注：存储块头部