(C语言详细版)第八章 动态存储管理

重点：内存空间的分配与回收算法，以及可利用空间表的结构。难点：无用单元收集算法的理解与掌握。第八章动态存储管理1/33第八章动态存储管理8.1概述8.2可利用空间表及分配方法8.3边界标识法8.4伙伴系统8.5无用单元收集8.6存储紧缩2/338.1概述(1)程序中的变量如何存储管理？早期，由程序员自己完成：

在执行程序之前，先需将用机器语言或汇编语言编写的程序输送到内存的某个固定区域上，并预先给变量和数据分配好对应的内存地址(绝对或相对地址)有了高级语言后，程序员不需直接和内存地址打交道：

变量对应的内存地址都是由编译程序在编译或执行时进行分配操作系统单用户操作系统：内存空间被划分为系统区(供系统程序使用)和用户区(供单一的用户程序所使用)多道程序设计：多个用户程序共享一个内存区域，每个用户程序使用的内存就由操作系统来进行分配。存储管理是操作系统和编译程序的一个复杂且重要的问题！3/338.1概述(2)动态存储管理的基本问题系统如何用用户提出的“请求”分配内存？如何回收那些用户不再使用而“释放”的内存，以备新的“请求”产生时重新进行分配？用户提出的“请求”：可能是进入系统的一个作业也可能是程序执行过程中的一个动态变量系统每次分配给用户都是一个地址连续的内存区。称已分配给用户使用的地址连续的内存区为“占用块”，称未曾分配的地址连续的内存区为“可利用空间块”或“空闲块”。4/338.1概述(3)U1U2U3U4U5U6U7U8系统运行初期U1U3U4U6U8系统运行若干时间之后占用块空闲块动态存储管理系统刚开工时5/338.1概述(4)当有新的用户进入系统请求分配内存，系统将如何做呢？策略一：从高地址的空闲块中进行分配，当分配无法进行时，系统回收所有用户不再使用的空闲块，并重新组织内存，将所有空闲的内存区连接在一起成为一个大的空闲块。策略二：从所有空闲块中找出一个“合适”的空闲块分配之。

系统需要建立一张记录所有空闲块的“可利用空间表”，它可以是“目录表”，也可以是“链表”。U1U3U4U6U86/338.1概述(5)U60100002500031000390005900099999(a)内存状态(b)目录表015,000av(c)链表08,000041,000^7/338.2可利用空间表及分配方法讨论利用可利用空间表进行动态存储分配的方法.目录表简单，将在操作系统课程中介绍这里仅就链表的情况进行讨论8/338.2可利用空间表及分配方法(1)可利用空间表的表示——链表一个空闲块一个结点用户请求分配时，系统从表中删除一个结点分配之用户释放所占内存时，系统即回收并将它插入到表中根据系统运行的不同情况，可利用空间表有不同的结构形式系统运行期间所有用户请求分配的存储量大小相同由于表中结点大小相同，则分配时无需查找可以用链栈实现——操作系统中的固定分区管理9/338.2可利用空间表及分配方法(2)系统运行期间用户请求分配的存储量有若干种大小的规格建立若干个可利用空间表，同一链表中的结点大小相同每个结点的第一个字设有链域(link)：指向同一链表中下一结点的指针标志域(tag)：0-空闲块、1-占用块结点类型域(type)：区分大小不同的结点tagtypelinkvalue00av20000^01av40101^02av80202^10/338.2可利用空间表及分配方法(3)系统运行期间用户请求分配的存储量有若干种大小的规格分配从结点大小和请求分配的量相同的链表中查找结点并分配之若没有，则从结点较大的链表中查找结点，将其中一部分分配给用户，剩余的插入到相应大小的链表中若各链表都没有合适的结点，则要执行“存储紧缩”将小块合并回收将释放的空闲块插入到相应大小的链表的表头11/338.2可利用空间表及分配方法(4)系统运行期间分配给用户的内存块的大小不固定开始时，整个内存空间是一个空闲块随着分配和回收的进行，可利用空间表中的结点大小和个数也随之而变结点的结构链域(link)：指向同一链表中下一结点的指针标志域(tag)：0-空闲块、1-占用块大小域(size)：指示该空闲块的存储量space：地址连续的内存空间——操作系统中的可变分区管理tagsizelinkspace12/338.2可利用空间表及分配方法(5)可利用空间表中的结点大小不同时的分配方法假设用户需大小为n的内存若链表中仅有一块大小为m≥n的空闲块：将其中大小为n的一部分分配给用户，剩余大小为m-n的作为一个结点留在链表中若链表中有若干个不小于n的空闲块：有三种分配策略首次拟合法：取第一个不小于n的空闲块最佳拟合法：取表中一个不小于n且最接近n的空闲块

表按空闲块大小自小到大有序，适于大小范围较广的系统最差拟合法：取表中不小于n且是表中最大的空闲块

表按空闲块大小自大至小有序，适于大小范围较窄的系统13/338.3边界标识法(1)边界标识法(Boundarytagmethod)可利用空间表：双重循环链表分配：首次拟合或最佳拟合特点每个内存区的头部和底部两个边界上分别设有标识，以标识该区域为占用块或空闲块，使得在回收时易于判别在物理位置上与其相邻的内存区域是否为空闲块，以便将所有地址连续的空闲存储区组合成一个尽可能大的空闲块。14/338.3边界标识法(2)可利用空间表的结构llinktagsizerlinkspaceuplinktagheadfoottypedefstructWORD{//内存字类型union{WORD*llink;

//指向前驱结点WORD*uplink;//指向本结点头部};inttag;//0-空闲;1-占用intsize;//块大小WORD*rlink;//指向后继结点OtherTypeother;//字的其它部分}WORD,head,foot,*Space;//指向p所指结点的底部#defineFootLoc(p)p+p->size-115/338.3边界标识法(3)分配算法(算法8.1P200)假设用首次拟合法进行分配，请求分配的存储量为n。为使整个系统更有效地运行，在边界标识法中作如下约定假设找到的待分配空闲块的容量为m个字(包括头部)，选定一个适当的常量e，当m-n≤e时，就将容量为m的空闲块整块分配给用户；否则只分配其中n个字的内存块。

为避免修改指针，约定将该结点中的高地址部分分配给用户。

每次分配从不同的结点(如刚进行分配的结点的后继)开始进行查找，使分配后剩余的小块均匀地分布在链表中。——避免小块集中在头指针所指结点附近，从而增加查询较大空闲块的时间16/338.3边界标识法(4)回收算法(P201~203)假设用户释放的内存区的头部地址为p要检查刚释放的占用块M的左、右紧邻是否为空闲块与M低地址紧邻的内存区的底部地址为p-1与M高地址紧邻的内存区的头部地址为p+p->sizeM的左、右邻区均为占用块：简单插入M的左邻区为空闲块，右邻区为占用块：合并左邻区和M，增加左邻空闲块结点的size域的值，重新设置结点的底部M的右邻区为空闲块，左邻区为占用块：合并M和右邻区，结点的底部位置不变，头部要变，链表的指针也要变M的左、右邻区均为空闲块：合并左邻区、M和右邻区，增加左邻空闲块的size值，在链表中删除右邻空闲块结点，修改底部17/338.4伙伴系统(1)伙伴系统(buddysystem)与边界标识法类似不同点是：在伙伴系统中，无论是占用块或空闲块，其大小均为2的k次幂(k为某个正整数)可利用空间表若可利用内存容量为2m个字，则空闲块的大小只能是20、21、…、2m所有大小相同的空闲块建于一张子表中，每个子表是一个双重循环链表，可能有m+1个子表将m+1个表头指针用向量结构组织成一个表18/338.4伙伴系统(2)可利用空间表的结构llinktagkvalrlinkspacehead#definem16typedefstructWORD{//内存字类型WORD*llink;

//指向前驱结点inttag;//0-空闲;1-占用intkval;//块大小,值为2的幂次kWORD*rlink;//指向后继结点OtherTypeother;//字的其它部分}WORD,head;

typedefstructHeadNode{intnodesize;//该链表的空闲块的大小WORD*first;//该链表的表头指针}FreeList[m+1];//表头向量类型20…2k-12k…2m…19/338.4伙伴系统(3)分配算法(算法8.2P205)假设用请求分配的存储量为n。若2k-1<n≤2k-1，即第k+1个子表不空，则只删除此链表中第一个结点并分配给用户即可若2k-2<n≤2k-1-1，结点大小为2k-1的子表为空，则从结点大小为2k的子表中取出一块，将其中一半分配给用户，剩余的一半作为一个新结点插入在结点大小为2k-1的子表中若2k-i-1<n≤2k-i-1(i为小于k的整数)，并且所有结点小于2k的子表均为空，则同样需从结点大小为2k的子表中取出一块，将其中2k-i分配给用户，剩余部分分割成若干个结点分别插入在结点大小为2k-i、2k-i+1、…、2k-1的子表中。20/338.4伙伴系统(4)回收算法(P205，206)假设用户释放的内存区的起始地址为p，块的大小为2k伙伴系统仅考虑互为“伙伴”的两个空闲块的归并伙伴：两个由同一大块分裂出来的小块就称为“互为伙伴”。假设p为大小为2k的空闲块的初始地址，且pMOD2k+1=0，则初始地址为p和p+2k的两个空闲块互为伙伴。21/338.4伙伴系统(5)判别其伙伴是否为空闲块若是，则在相应子表中找到其伙伴并删除之，然后再判别合并后的空闲块的伙伴是否是空闲块若否，则只要将释放的空闲块简单插入在相应子表中即可伙伴块的起始地址对伙伴系统的评价优点：算法简单、速度快缺点：由于只归并伙伴而容易产生碎片22/338.5无用单元收集(1)8.2~8.4节讨论的存储管理系统中，用户必须明确给出“请求”和“释放”的信息

因为用户的疏漏或结构本身的原因致使系统在不恰当的时候或没有进行回收而产生“无用单元”或“悬挂访问”的问题。无用单元：那些用户不再使用而系统没有回收的结构和变量。

例：p=malloc(size);….p=NULL;悬挂访问：访问已经被释放的结点

例：p=malloc(size);….q=p;free(p);a=*q;因结构本身的特性，也会产生上述问题

例如广义表的结构:共享子表(图8.9P207)23/338.5无用单元收集(2)如何解决广义表结构中的“无用单元”或“悬挂访问”问题？使用访问计数器：在所有子表或广义表上增加一个表头结点，并设立一个“计数域”，它的值为指向该子表或广义表的指针数目。当该计数域的值为0时,此子表或广义表中的结点才被释放。收集无用单元：在程序运行中，所有的链表结点不管是否还有用，都不被回收，直到整个可利用空间表为空。此时中断执行程序，收集无用单元，分两步进行:

1)对所有占用结点加上标志(0-未用，1-占用)

2)对整个可利用存储空间顺序扫描一遍，将标志为0的结点链成一个新的可利用空间表。困难24/338.5无用单元收集(3)标志算法

加标志的操作实质上是遍历广义表，将广义表中所有结点的标志域赋值为“1”。递归算法：

基本项：1）表为空，则无须遍历；

2）若是一个数据元素，则标志元素结点

归纳项：首先标志表结点，再分别遍历表头和表尾

评价：需要一个较大的实现递归用的栈的辅助内存，该内存不

能用于动态分配。由于表的层次不定，使得栈的容量不

易确定可能会栈溢出25/338.5无用单元收集(4)标志算法非递归算法：程序中附设栈或队列实现广义表的遍历。

类似于图的深度优先遍历或广度优先遍历

评价：栈或队列的空间同样是不确定的利用表结点本身的指针域标记遍历路径的算法：

算法思想：假设p指向某个表结点时，t指向p的母表结点，q指向p的表头或表尾。

当q指向p的表头结点时，

1）设p的表头只是一个元素结点，则遍历表头仅需对该表头

结点打上标志后即令q指向p的表尾；

2）设p的表头为空表或是已加上标志的子表，则无需遍历表

头只要令q指向p的表尾；26/338.5无用单元收集(5)标志算法利用表结点本身的指针域标记遍历路径的算法：

算法思想：假设p指向某个表结点时，t指向p的母表结点，q指向p的表头或表尾。

当q指向p的表头结点时，

3）设p的表头为未加标志的子表，则需先遍历表头子表，即

p应赋q的值，t相应往下移动改赋p的值；

为了记下t指针移动的路径，以便在p退回原结点时同时找

到p的母表结点，则在修改这个指针的值之前，应先记下t

移动的路径，即令p所指结点的hp域的值为t，且tag域的

值为“0”。27/338.5无用单元收集(6)标志算法利用表结点本身的指针域标记遍历路径的算法：

算法思想：假设p指向某个表结点时，t指向p的母表结点，q指向p的表头或表尾。

当q指向p的表尾时，

1）p的表尾为未加标志的子表，则需遍历表尾子表，同样p、

t指针要作相应的移动。

为了记下t指针移动的路径，以便在p退回原结点时同时找

到p的母表结点，则在修改这个指针的值之前，应先记下t

移动的路径，即令p所指结点的tp域的值为t。28/338.5无用单元收集(7)标志算法利用表结点本身的指针域标记遍历路径的算法：

算法思想：假设p指向某个表结点时，t指向p的母表结点，q指向p的表头或表尾。

当q指向p的表尾时，

2）p的表尾为“