数据结构(C语言版)第8章_动态存储管理.ppt.pptx

第8章 动态存储管理; 对于允许进行动态存储分配的程序设计语言，操作系统在内存中划出一块地址连续的大区域(称为堆) ，由设计者在程序中利用语言提供的内存动态分配函数(如C的malloc() ，calloc()，free()函数，C++的new，delete函数等)来实现对堆的使用。 1 两个基本概念 ◆ 占用块：已分配给用户使用的一块地址连续的内存区域； ◆ 空闲块：未曾分配的地址连续的内存区域； 2 用户请求分配内存，系统的处理方式 当有用户程序进入系统请求分配内存时，系统有两种处理方式：;⑴ 系统从高地址空闲块中进行分配，直到分配无法进行时，才回收所有用户不再使用的空闲块，重新组织一个大的空闲块来再分配； ⑵ 用户程序一旦运行结束，便将它所占内存区释放成为空闲块，同时，每当新用户请求分配内存时，系统需要巡视整个内存区中所有空闲块，并从中找出一个“合适”的空闲块分配之。 对于⑵的情况，系统需建立一张“可利用空间表” 。 程序运行过程中，不断地对堆中的部分区域进行分配和释放，堆中会出现占用块和空闲块交错的状态，如图8-1所示。;3 动态存储分配的基本问题 ⑴ 当某一时刻用户程序请求分配400个字节的存储空间，如何分配? ◆ 将块A分配给用户程序? ◆ 从大块C中划出一部分分配给用户程序? ⑵ 当某一时刻分配B块的用户程序运行结束，B块要进行回收，如何回收? ◆ B块直接回收并成为一个独立的空闲块? ◆ B块回收并和前、后的空闲块A、C合并后形成一个更大的空闲块?;8.2 可利用空间表及分配方法;8.2.1 可利用空间表的组织;(a) 堆的状态;8.2.2 结点结构方式与分配策略;◆ 分配时：根据请求的大小，将最接近该大小的某个链表的首结点分配给用户。若剩余部分正好差不多是另一种规格大小，则将剩余部分插入到另一种规格的链表中，然后删除该结点； ◆ 回收时：只要将所释放的空闲块插入到相应大小的表头。 存在的问题： 当请求分配的块空间大小比最大规格的结点还大时，分配不能进行。而实际上内存空间却可能存在比所需大小还要大的的连续空间，应该能够分配。;3 请求分配的块大小不确定 系统开始时，整个堆空间是一个空闲块，链表中只有一个大小为整个堆的结点，随着分配和回收的进行，链表中的结点大小和个数动态变化。 由于链表中结点大小不同，结点中除标志域和链域之外，尚需有一个结点大小域(size)，以保存空闲块的大小，如图8-2(b)。 问题：若用户请求分配大小为n(kB)的内存，而链表中有若干大小不小于n的空闲块时，如何分配?有3种分配策略。;⑴ 首次拟合法(First fit) ◆ 分配时：从表头指针开始查找可利用空间表，将找到的第一个不小于n的空闲块的部分(所需要大小)分配给用户，剩下部分仍然是一个空闲块结点； ◆ 回收时：将释放的空闲块插入在链表的表头。 特点：分配时随机的；回收时仅需插入到表头。 ⑵ 最佳拟合法(Best fit) ◆ 分配时：扫描整个可利用空间链表，找到一个大小满足要求且最接近n空闲块，将其中的一部分(所需要大小)分配给用户，剩下部分仍然是一个空闲块结点；;◆ 回收时：只要将释放的空闲块插入到链表的合适位置。 为了使分配时不需要扫描整个可利用空间链表，链表组织(块回收时)成按从小到大排序(升序) 。 优点：适用于请求分配的内存块大小范围较广的系统； 缺点：系统容易产生无法分配的内存碎片；无论分配与回收，都需要查找表，最费时； ⑶ 最差拟合法(Worst fit) ◆ 分配时：扫描整个可利用空间链表，找到一个大小最大的空闲块，将其中的一部分(所需要大小)分配给用户，剩下部分仍然是一个空闲块结点；;◆ 回收时：只要将释放的空闲块插入到链表的合适位置。 为了使分配时不需要扫描整个可利用空间链表，链表组织(块回收时)成按从大到小排序(降序) 。 特点：适用于请求分配的内存块的大小范围较窄的系统；分配无需查找，回收需要查找适当的位置。 4 选择分配策略需考虑的因素 用户的逻辑要求、请求分配量的大小分布、分配和释放的频率以及效率对系统的重要性。;8.3 边界标识法;8.3.1 可利用空闲表结点结构;8.3.2 分配算法;② 空闲块链表中的结点数可能很多，为了提高查找空闲块的速度和防止小容量结点密集，每次查找时从不同的结点开始——上次刚分配结点的后继结点开始。 Space AllocBoundTag( Space *pav, int n ) { p = pav ; for ( ; p p-sizen p -rlink!=pav; p=p-rlink ) if