动态内存分配

长期以来，我们一直使用malloc（）和free（）库函数来进行动态内存分配。

#include <stdlib.h> void* malloc(size_t size)；// void free（void* ptr）错误时返回NULL；

当我们使用malloc（）函数时，C标准库在堆上分配所需大小的内存块，并返回指向该内存块的指针。在这些笔记中，我们将深入了解动态内存分配方案需要做些什么才能成功地复制malloc（）的行为。

下面的插图，以及我们将在这些注释中看到的示例代码，都来自Bryant和O'Hallaron编写的《计算机系统：程序员的视角》第三版。

Linux上进程的内存架构

下图说明了典型Linux进程中的内存是如何组织的。堆出现在图的底部，并随着堆的扩展而向上增长。操作系统维护一个全局指针brk，它指向堆的顶端。程序可以通过调用sbrk（）系统调用来扩展堆：

#include <unistd.h> void* sbrk(intptr_t incr)；

sbrk（）函数尝试按请求的字节数向上扩展堆。如果请求成功，则brk指针将向上移动请求的字节数，并且sbrk（）将返回brk指针的前一个值。实际上，这个函数的作用就像malloc（）一样，因为它是在堆上分配一块内存，然后返回指向该内存块的指针的一种方法。

动态内存分配

大多数C程序使用malloc（）和free（）在堆上分配和释放内存。

#include <stdlib.h> void* malloc(size_t size)；//错误返回NULL void* calloc(size_t num,size_t size)；//初始化为0 void* realloc(void* ptr,size_t size)；Void free(Void * ptr)；

calloc（）函数既分配了一块内存，又将其内容初始化为全0。realloc（）函数用于调整先前分配的内存块的大小。例如，如果您以前使用malloc（）为数组分配空间，那么您可以通过调用realloc（）来调整数组的大小。您将指向数组的指针以及以字节为单位的数组新大小传递给realloc（）。然后，该函数将尝试为具有请求大小的新数组分配空间，将旧数组的内容复制到新数组，然后返回指向新数组的指针。

设计一个内存分配器

C标准库中的内存分配器是一个非常好的通用内存分配系统，可以很好地满足大多数程序的需要。

在某些特殊情况下，我们可以用我们自己的自定义内存分配系统替换标准库的内存分配系统。这些笔记的其余部分将描述如何设计我们自己的自定义内存分配系统，以及如何在某些特殊情况下调整其行为以潜在地优于标准库的系统。

在设置我们自己的自定义内存分配系统时，我们将使用的第一个想法是，首先使用sbrk（）系统调用在堆上划出一个初始的大块内存。当我们的程序需要分配一些内存时，我们的内存分配器就会根据需要分配大块的内存。我们的内存分配系统将通过将初始大块分解为子块来工作，每个子块将具有如下结构：

在每个块的开始和结束，我们将有一个页眉和一个页脚。报头将是一个32位的序列，前29位存储块的大小，最后3位保留标志。最后一个位将作为一个标志，表明给定的块当前是已分配的还是空闲的。页脚将是页眉的精确副本。

块大小信息将使我们能够建立一个隐式块列表。通过检查第一个块的头中的块大小值，我们将能够计算序列中下一个块的开始位置。在块序列的末尾，我们将放置一个特殊的块，其大小值为0，作为结束标记。

下一张图说明了一个典型的分配请求会做什么。假设我们要求分配一个8字节的块。分配器将沿着块列表遍历，直到遇到一个大到足以容纳请求的未分配块。在上图中，序列中的第三个块是一个大小为32字节的未分配块。然后，我们可以将未分配的块拆分为两个大小为16的块：一个新分配的块包含请求的8字节以及4字节的头和4字节的脚，以及一个大小为16的新未分配块。

当分配系统的客户端向我们发送请求以释放我们之前分配的内存块时，它们将首先给我们一个指向已分配块中有效负载区域的指针。如果我们从该点返回4个字节，我们将有一个指向已分配块开始处的头的指针。一旦我们有了指向头文件的指针，我们就可以找出这个块之前的块在哪里结束，以及这个块之后的块在哪里开始。通过检查相邻的两个块，我们可以将一些自由块合并在一起，形成一个更大的自由块。

下面的图片说明了各种场景，在这些场景中，在释放块之后可能执行合并，也可能不执行合并。

我在这些注释的顶部链接到的存档中的代码基于我上面讨论的思想实现了一个自定义内存分配器。

显式空闲列表

一旦我们实现了一个基本的内存分配系统，我们就可以着手改进它的性能。我们可以实现很多想法来提高系统的总体性能和/或优化它以处理某些特殊情况。

这里有一个这样的想法。上面描述的系统的一个明显问题是，当一个分配请求进来时，我们必须在隐式块列表中从一个块跳转到另一个块，以找到一个未分配的块，这个块也足够大，可以满足我们的请求。这种搜索的浪费部分涉及跳过已分配的块，直到我们到达未分配的块。优化这种搜索的一种方法是实现一种方案，将未分配的块组织在它们自己的单独列表中，称为显式空闲列表。我们可以利用这样一个事实，即未分配的块具有大量当前未使用的可用自由空间。我们可以利用这些未使用的空间来存储有用的信息，比如将未分配的块链接到一个双链表中的一对指针。我们只需要给系统添加一个全局指针，它指向系统中第一个未分配的块。

当分配内存的请求到来时，我们可以直接跳到第一个未分配的块，然后沿着未分配的块列表向下走，直到找到一个足够大的块来满足请求。然后，我们可以进行少量的指针更新，将新分配的块从显式空闲列表中解挂钩。

备选策略包括隔离空闲列表、隔离存储和伙伴列表。

家庭作业

通过单击这些注释顶部的按钮下载项目文件夹。在该项目文件夹中，您将找到上面描述的内存分配系统的代码。这个版本的内存分配器在mm.c文件中的find_fit（）函数中搜索赢博体育块，以查找空闲块。在本练习中，您将修改内存分配器，以使用上面部分中描述的显式空闲列表策略。为此，您将修改mm.c中的find_fit（）函数和其他一些函数。

一旦您更新了内存管理器，您还需要编写一个测试程序，该程序使用内存管理器分配和释放一堆不同大小的块。

mmap函数

#include < unstd .h> #include <sys/mman.h> void* mmap(void* start,size_t length,int prot,int flags,int fd,off_t offset)；//成功返回指针，错误返回-1 int munmap(void* start,size_t length)；

Prot可以是任意的组合

价值	解释
PROT_EXEC	页面包含可执行代码
PROT_READ	可以读取页面
PROT_WRITE分别	可以写几页
PROT_NONE	页面可能无法访问

标志可以是

价值	解释
MAP_ANON	后台存储是匿名文件，页面是零需求的
MAP_PRIVATE	Private，在写对象上复制
MAP_SHARED	共享对象