*** 作系统——可变分区空闲空间管理

*** 作系统——可变分区空闲空间管理

目录

• 一. 关键问题：如何管理空闲空间
• 二. 假设
• 三 . 底层机制
• • 1. 分割
  • 2. 合并
  • 3. 追踪分配内存大小
  • 4. 如何在空闲内存内部建立列表
• 四. 分配算法
• • 1. 最优匹配（best fit）
  • 2. 最差匹配（worst fit）
  • 3. 首次匹配（first fit）
  • 4. 下次匹配
  • 5. 分离空闲列表
  • 6. 伙伴系统

一. 关键问题：如何管理空闲空间

1. 要满足变长的分配请求，应该如何管理空闲空间？
2. 什么策略可以让碎片最小化？
3. 不同方法的时间和空间开销如何？

二. 假设

1. 基本的接口就像 malloc() 和 free() 提供的那样。

函数定义void * malloc(size t size)需要一个参数size，它是应用程序请求的字节数。函数返回一个指针（没有具体的类型，在C语言的术语中是void类型），指向这样大小（或较大一点）的一块空间。void free(void *ptr)函数接受一个指针，释放对应的内存块。请注意该接口的隐含意义，在释放空间时，用户不需告知库这块空间的大小。

2. 在堆上管理空闲空间的数据结构通常称为 空闲列表（free list）。该数据结构不一定真的是列表，只是逻辑上的列表，某种可以追踪空闲空间的数据结构==（应该是链表）==。
3. 主要关心的是 外部碎片（external fragmentation）。
4. 内存一旦被分配给程序，就不可以被重定位到其他位置。因此，不可能进行紧凑（compaction）空闲空间的 *** 作，从而减少碎片。
5. 分配程序所管理的是 连续的一块字节区域。
6. 假设这块区域在整个生命周期内大小固定。

三 . 底层机制 1. 分割

30字节的堆

这个堆对应的空闲列表会有两个元素，一个描述第一个10字节的空闲区域（字节0～9），一个描述另一个空闲区域（字节20～29）：

任何大于10字节的分配请求都会失败（返回NULL），因为没有足够的连续可用空间。而恰好10字节的需求可以由两个空闲块中的任何一个满足。如果申请小于10字节空间，例如申请1字节空间，分配程序会执行所谓的分割（splitting）动作：它找到一块可以满足请求的空闲空间，将其分割，第一块返回给用户，第二块留在空闲列表中。

从上面可以看出，空闲列表基本没有变化，只是第二个空闲区域的起始位置由20变成21，长度由10变为9了。

2. 合并

对于这个堆，如果应用程序调用free(10)，归还堆中间的空间，会发生什么？如果只是简单地将这块空闲空间加入空闲列表，不多想想，可能得到如下的结果：

这时，如果用户请求20字节的空间，简单遍历空闲列表会找不到这样的空闲块，因此返回失败。为了避免这个问题，分配程序会在释放一块内存时合并可用空间。

在归还一块空闲内存时，仔细查看要归还的内存块的地址以及邻近的空闲空间块。如果新归还的空间与一个原有空闲块相邻（或两个，就像这个例子），就将它们合并为一个较大的空闲块。通过合并，最后空闲列表应该像这样：

通过合并，分配程序可以更好地确保大块的空闲空间能提供给应用程序。

3. 追踪分配内存大小

free(void *ptr)接口没有块大小的参数。因此它是假定，对于给定的指针，内存分配库可以很快确定要释放空间的大小，从而将它放回空闲列表。要完成这个任务，大多数分配程序都会在头块（header）中保存一点额外的信息，它在内存中，通常就在返回的内存块之前。

下图例子中，我们检查一个20字节的已分配块，由ptr指着，设想用户调用了malloc()，并将结果保存在ptr中：ptr = malloc(20)。

头块数据结构

typedef struct  header_t { 
    int size;
    int magic;
} header_t;

该头块中至少包含所分配空间的大小（这个例子中是20）。它也可能包含一些额外的指针来加速空间释放，包含一个常数来提供完整性检查，以及其他信息。我们假定，一个简单的头块包含了分配空间的大小和一个常数。

用户调用free(ptr)时，库会通过简单的指针运算得到头块的位置：

void free(void *ptr) {
    header_t *hptr = (void *)ptr - sizeof(header_t);
}

结合上述代码和图片得到下图

获得头块的指针后，库可以很容易地确定幻数是否符合预期的值，作为正常性检查（assert（hptr->magic == 1234567）），并简单计算要释放的空间大小（即头块的大小加区域长度）。请注意前一句话中一个小但重要的细节：实际释放的是头块大小加上分配给用户的空间的大小。因此，如果用户请求N字节的内存，库不是寻找大小为N的空闲块，而是寻找N加上头块大小的空闲块。

4. 如何在空闲内存内部建立列表

假设我们需要管理一个4096字节的内存块（即堆是4KB）。为了将它作为一个空闲空间列表来管理，首先要初始化这个列表。开始，列表中只有一个条目，记录了大小为4096的空间（减去头块的大小）。下面是该列表中一个节点描述：

typedef struct  node_t { 
    int    size;
    struct  node_t *next;
} node_t;

现在来看一些代码，它们初始化堆，并将空闲列表的第一个元素放在该空间中。假设堆构建在某块空闲空间上，这块空间通过系统调用 mmap()获得。这不是构建这种堆的唯一选择，但在这个例子中很合适。下面是代码：

// mmap() returns a pointer to a chunk of free space 
node_t *head = mmap(NULL, 4096, PROT_READ|PROT_WRITE,
                   MAP_ANON|MAP_PRIVATE, -1, 0);
head->size    = 4096 - sizeof(node_t); 
head->next    = NULL;

执行这段代码之后，列表的状态是它只有一个条目，记录大小为4088。head指针指向这块区域的起始地址，假设是16KB（尽管任何虚拟地址都可以）。堆看起来如下图

现在，假设有一个100字节的内存请求。为了满足这个请求，库首先要找到一个足够大小的块。因为只有一个4088字节的块，所以选中这个块。然后，这个块被分割（split）为两块：一块足够满足请求（以及头块，如前所述），一块是剩余的空闲块。假设记录头块为8个字节（一个整数记录大小，一个整数记录幻数），堆中的空间如下图

至此，对于100字节的请求，库从原有的一个空闲块中分配了108字节，返回指向它的一个指针（在上图中用ptr表示），并在其之前连续的8字节中记录头块信息，供未来的free()函数使用。同时将列表中的空闲节点缩小为3980字节（4088−108）。

四. 分配算法 1. 最优匹配（best fit）

基本思想：首先遍历整个空闲列表，找到和请求大小一样或更大的空闲块，然后返回这组候选者中最小的一块。这就是所谓的最优匹配（也可以称为最小匹配）。

数据结构：空闲列表由小到大进行排列。

特点：选择最接近用户请求大小的块，从而尽量避免空间浪费；简单的实现在遍历查找正确的空闲块时，要付出较高的性能代价（遍历列表方式的影响）；该算法保留大的空闲区，但造成许多小的空闲区。

2. 最差匹配（worst fit）

基本思想：与最优匹配相反，它尝试找最大的空闲块，分割并满足用户需求后，将剩余的块（很大）加入空闲列表。最差匹配尝试在空闲列表中保留较大的块，而不是向最优匹配那样可能剩下很多难以利用的小块。

数据结构：空闲列表由大到小排列。

特点：该算法保留小的空闲区，尽量减少小的碎片产生；导致过量的碎片，同时还有很高的开销（ *** 作系统导论）；使链表中的结点大小趋于均匀，适用于请求分配的内存大小范围较窄的系统。

3. 首次匹配（first fit）

基本思想：找到第一个足够大的块，将请求的空间返回给用户。同样，剩余的空闲空间留给后续请求。

数据结构：要求空闲区按地址递增的次序排列。

特点：首次匹配有速度优势（不需要遍历所有空闲块），但有时会让空闲列表开头的部分有很多小块。因此，分配程序如何管理空闲列表的顺序就变得很重要。一种方式是基于地址排序（address-based ordering）。通过保持空闲块按内存地址有序，合并 *** 作会很容易，从而减少了内存碎片。

4. 下次匹配

基本思想：不同于首次匹配每次都从列表的开始查找，下次匹配（next fit）算法多维护一个指针，指向上一次查找结束的位置。

特点：对空闲空间的查找 *** 作扩散到整个列表中去，避免对列表开头频繁的分割。这种策略的性能与首次匹配很接近，同样避免了遍历查找。

5. 分离空闲列表

基本思想：如果某个应用程序经常申请一种（或几种）大小的内存空间，那就用一个独立的列表，只管理这样大小的对象。其他大小的请求都交给更通用的内存分配程序。

特点：通过拿出一部分内存专门满足某种大小的请求，碎片就不再是问题了。而且，由于没有复杂的列表查找过程，这种特定大小的内存分配和释放都很快。为系统引入了新的复杂性。例如，应该拿出多少内存来专门为某种大小的请求服务，而将剩余的用来满足一般请求。

6. 伙伴系统

基本思想：在伙伴系统中，可用内存分区的大小为2K,L≤K≤U，其中：
● 2L表示分配的最小分区的尺寸；
● 2U表示分配的最大分区的尺寸。
最初，视可用于分配的整个内存空间为一个大小为2U的分区。若所需存储分区的大小 s满足2U-1＜s≤2U，则将整个存储空间分配出去；否则，将该分区分成尺寸均为2U-1的伙伴。如果有2U-2＜s≤2U-1，则为该存储请求分配两个伙伴中的任一个；否则，其中的一个伙伴又被分成两半。这样的过程一直继续下去，直到获得大于或等于s的最小分区，并完成分配。
任何时候，伙伴系统维护着不同尺寸的空闲分区列表，第i个列表中的空闲分区尺寸都是2i。一个空闲分区可以从（i+1）列表中移出，并通过对半分裂，在 i 列表中产生两个大小为2i的伙伴。当i列表中的一对伙伴都变为空闲时，就将它们从i列表中移出，合并成（i+1）列表中的一个空闲分区。

特点：优点是快速搜索合并（O(logN)时间复杂度）以及低外部碎片（最佳适配best-fit）；其缺点是内部碎片，因为按2的幂划分块，如果碰上65单位大小，那么必须划分128单位大小的块。实际上存储结点信息也会占用一小部分内存，但该算法总体上来看性能还是比较优越的。

*** 作系统导论
*** 作系统（第四版）
互联网
https://blog.csdn.net/weixin_39928544/article/details/90044757
https://blog.csdn.net/liying_1234/article/details/52053183?depth_1-utm_source=distribute.pc_relevant.none-task&utm_source=distribute.pc_relevant.none-task
https://blog.csdn.net/dingdingdodo/article/details/100624125
https://blog.csdn.net/kelvin_yin/article/details/78997953