动态存储管理：伙伴系统与边界标识法

"本文介绍了伙伴系统在动态存储管理中的应用，特别是如何使用数据结构来有效地管理内存。" 在计算机科学中，动态存储管理是操作系统的重要组成部分，它负责在程序运行过程中根据需要分配和回收内存。本章主要关注的是动态存储管理中的伙伴系统数据结构及其在内存分配和回收中的作用。 伙伴系统是一种用于管理内存的机制，尤其适用于连续内存分配。在这个系统中，内存被划分为一系列的块，每个块的大小都是2的幂，例如1, 2, 4, 8, 16...等等。这种划分方式使得内存块可以相互配对成为“伙伴”，便于管理和合并。 数据结构的核心是`struct BLK`，定义了一个包含以下元素的结构体： 1. `kval`：通常用于表示块的大小或者其他的属性，比如标记（tag）。 2. `prev` 和 `next`：这两个指针用于实现双向循环链表，使得在内存块之间可以方便地进行前向和后向移动。 `struct BLK *av[M]` 是一个数组，代表了多个空闲链表，每个链表管理不同大小的内存块。M表示不同大小类别的数量，通常是2^n，其中n是内存块大小的最小位数。 动态存储管理的几个关键概念包括： 1. 可利用空间表：这是通过链表维护的空闲内存块列表，可以按照不同策略进行分配，如首次拟合法、最佳拟合法和最坏拟合法。 - 首次拟合法：找到第一个大于等于请求大小的块并分配。 - 最佳拟合法：分配与请求大小最接近的块，以减少碎片。 - 最坏拟合法：分配最大的块，以期望未来分配时能有更大的连续空间。 2. 内存分配与回收： - 分配：根据申请的大小，选择合适的分配策略。如果分配的块大小接近请求大小，就全部分配；否则，将其分割，一部分分配给用户，剩余部分保留。 - 回收：当内存块不再需要时，检查其相邻块是否为空闲，如果为空闲则合并成更大的空闲块，并更新可利用空间表。 边界标识法是另一种内存管理方法，它在每个内存块的头部和尾部存储额外的信息，如标签和大小，用于快速识别块的状态和边界。这种方法可以高效地处理内存分配和回收，因为它可以立即确定哪些块是可用的，以及它们的精确大小。 动态存储管理是通过精心设计的数据结构和算法来实现的，目的是优化内存的利用率和效率，确保程序能够高效运行。伙伴系统和边界标识法都是为了实现这个目标的有效工具。