数据结构课件(C语言版)--第8章 动态存储管理

第8章 动态存储管理8.1 概述程序执行过程中，(数据)结构中的每一个数据元素 都对应一定的存储空间，数据元素的访问都是通过对应 的存储单元来进行的。存储空间的分配与管理是由操作 系统或编译程序负责实现的，是一个复杂而又重要的问 题，现代的存储管理往往采用动态存储管理思想。

动态存储管理：如何根据“存储请求”分配 内存空间？如何回收被释放的(或不再使用的)内 存空间？

对于允许进行动态存储分配的程序设计语言，操作 系统在内存中划出一块地址连续的大区域(称为堆) ,由 设计者在程序中利用语言提供的内存动态分配函数(如 C的malloc() ,calloc(),free()函数，C++的new,delete 函数等)来实现对堆的使用。

1 两个基本概念◆ 占用块：已分配给用户使用的一块地址连续的内 存区域； ◆ 空闲块：未曾分配的地址连续的内存区域；

2 用户请求分配内存，系统的处理方式当有用户程序进入系统请求分配内存时，系统有 两种处理方式：

⑴ 系统从高地址空闲块中进行分配，直到分配无法 进行时，才回收所有用户不再使用的空闲块，重新 组织一个大的空闲块来再分配； ⑵ 用户程序一旦运行结束，便将它所占内存区释放 成为空闲块，同时，每当新用户请求分配内存时， 系统需要巡视整个内存区中所有空闲块，并从中找 出一个“合适”的空闲块分配之。

对于⑵的情况，系统需建立一张“可利用空间 表” 。程序运行过程中，不断地对堆中的部分区域进行 分配和释放，堆中会出现占用块和空闲块交错的状态， 如图8-1所示。

3 动态存储分配的基本问题⑴ 当某一时刻用户程序请求分配400 个字节的存储空间，如何分配?◆ 将块A分配给用户程序? ◆ 从大块C中划出一部分分配给用 户程序?11000H 12004H

12196H 12240H130EFH

A B C

⑵ 当某一时刻分配B块的用户程序运 行结束，B块要进行回收，如何回收?◆ B块直接回收并成为一个独立的 空闲块? ◆ B块回收并和前、后的空闲块A、 C合并后形成一个更大的空闲块?

图8-1 堆的状态

8.2 可利用空间表及分配方法可利用空间表中包含所有可分配的空闲块，当用户 请求分配时，系统从可利用空间表中删除一个结点分配 之；当用户释放其所占内存时，系统即回收并将它插入 到可利用空间表中。因此，可利用空间表亦称做“存储 池”。

8.2.1 可利用空间表的组织可用空间表的组织有两种方式：目录表方式和链表 方式，如图8-2所示 。动态存储管理中需要不断地进行 空闲块的分配和释放，对目录表来说管理复杂，因此， 可利用空间表通常以链表方式组织 。

当可利用空间表以链表方式

组织时，每个空闲块就 是链表中的一个结点。◆ 分配时：从链表中找到一个合适的结点加以分配， 然后将该结点删除之； ◆ 回收时：将空闲块插入到链表中。

实际的动态存储管理实施时，具体的分配和释放的 策略取决于结点(空闲块)的结构。

00000H11000H 12004H 13196H 13740H

起始地址 12004H 13740H 216EFHav

空闲块大小 4498 10671 69632(b) 目录表方式

使用情况 空闲 空闲 空闲

160EFH0 4498 0 10671 0 69632

216EFH

326EFH(a) 堆的状态

(c) 链表方式

图8-2 动态存储管理过程中的内存状态和空闲表结构

8.2.2 结点结构方式与分配策略 1 请求分配的块大小相同将进行动态存储分配的整个内存区域(堆)按所需大 小分割成若干大小相同的块，然后用指针链接成一个可 利用空间表。

◆ 分配时：从表的首结点分配，然后删除该结点；◆ 回收时：将释放的空闲块插入表头。

2 请求分配的块大小只有几种规格根据统计概率事先对动态分配的堆建立若干个可利 用空间链表，同一链表中的结点(块)大小都相同。

◆ 分配时：根据请求的大小，将最接近该大小的某 个链表的首结点分配给用户。若剩余部分正好差不 多是另一种规格大小，则将剩余部分插入到另一种 规格的链表中，然后删除该结点；

◆ 回收时：只要将所释放的空闲块插入到相应大小 的表头。

存在的问题：当请求分配的块空间大小比最大规格的结点还大 时，分配不能进行。而实际上内存空间却可能存在比 所需大小还要大的的连续空间，应该能够分配。

3

请求分配的块大小不确定

系统开始时，整个堆空间是一个空闲块，链表中 只有一个大小为整个堆的结点，随着分配和回收的进 行，链表中的结点大小和个数动态变化。 由于链表中结点大小不同，结点中除标志域和链 域之外，尚需有一个结点大小域(size),以保存空闲块 的大小，如图8-2(b)。

问题：若用户请求分配大小为n(kB)的内存，而链表中有若干大小不小于n的空闲块时，如何分配?有3 种分配策略。

⑴ 首次拟合法(First fit)◆ 分配时：从表头指针开始查找可利用空间表，将 找到的第一个不小于n的空闲块的部分(所需要大小) 分配给用户，剩下部分仍然是一个空闲块结点； ◆ 回收时：将释放的空闲块插入在链表的表头。

特点：分配时随机的；回收时仅需插入到表头。

⑵ 最佳拟合法(Best fit)◆ 分配时：扫描整个可利用空间链表，找到一个大 小满足要求且最接近n空闲块，将其中的一部分(所 需要大小)分配给用户，剩下部分仍然是一个空闲块 结点；

◆ 回收时：只要将释放的空闲块插入到链表的合适 位置。 为了使分配时不需要扫描整个

可利用空间链表，链 表组织(块回收时)成按从小到大排序(升序) 。

优点：适用于请求分配的内存块大小范围较广的系统； 缺点：系统容易产生无法分配的内存碎片；无论分配与回收，都需要查找表，最费时；

⑶ 最差拟合法(Worst fit)◆ 分配时：扫描整个可利用空间链表，找到一个大 小最大的空闲块，将其中的一部分(所需要大小)分 配给用户，剩下部分仍然是一个空闲块结点；

◆ 回收时：只要将释放的空闲块插入到链表的合适 位置。 为了使分配时不需要扫描整个可利用空间链表，链 表组织(块回收时)成按从大到小排序(降序) 。

特点：适用于请求分配的内存块的大小范围较窄的系统；分配无需查找，回收需要查找适当的位置。

4 选择分配策略需考虑的因素用户的逻辑要求、请求分配量的大小分布、分配和 释放的频率以及效率对系统的重要性。

8.3 边界标识法边界标识法(Boundary Tag Method)是操作系统中 一种常用的进行动态分配的存储管理方法。 系统将所有的空闲块链接成一个双重循环链表，分 配可采用几种方法(前述) 。

系统的特点每个内存区域的头部和底部两个边界上分别设置标 识，以标识该区域为占用块或空闲块，在回收块时易于 判别在物理位置上与其相邻的内存区域是否为空闲块， 以便于将所有地址连续的空闲存储区合并成一个尽可能 大的空闲块。

8.3.1 可利用空闲表结点结构typedef struct word head Llink tag size rlink { Union { struct word *llink; space struct word *uplink; foot uplink tag }; int tag; int size; struct word *rlink; OtherType other; }WORD, head, foot, *Space; #define FootLoc(p) p+p->size-1

8.3.2 分配算法分配算法比较简单，可采用前述三种方法中的任 一种进行分配。设采用首次拟合法，为了使系统更有效 地运行，在边界标识法中还做了两条约定：

① 选定适当常量e,设待分配空闲块、请求分配空 间的大小分别为m 、 n 。◆ 当m-n≤e时：将整个空闲块分配给用户； ◆ 当m-n …… 此处隐藏：1818字，全部文档内容请下载后查看。喜欢就下载吧 ……