转载

深入理解计算机系统第 18 课 Dynamic Memory Allocation - Basic Concept

前面了解了虚拟内存的相关知识，这节课我们来看看动态内存分配的基本概念，相信这之后就知道诸如 malloc 和 new 这类方法是怎么做的了。

基础概念

程序员通过动态内存分配（例如 malloc ）来让程序在运行时得到虚拟内存。动态内存分配器会管理一个虚拟内存区域，称为堆(heap)，如下图所示：

分配器以 block 为单位来维护 heap，可以进行 allocate 或 free。有两种类型的分配器：

显式分配器：应用分配并且回收空间（C 语言中的 malloc 和 free ）
隐式分配器：应用只负责分配，但是不负责回收（Java 中的垃圾收集）

malloc

我们来看看 malloc 函数：

深入理解计算机系统第 18 课 Dynamic Memory Allocation - Basic Concept

一个简单的例子：

#include <stdio.h>
#include <stdlib.h>

void foo(int n) {
    int i, *p;
    
    /* Allocate a block of n ints */
    p = (int *) malloc(n * sizeof(int));
    if (p == NULL) {
        perror("malloc");
        exit(0);
    }
    
    /* Initialize allocated block */
    for (i=0; i<n; i++)
        p[i] = i;

    /* Return allocated block to the heap */
    free(p);
}

这节课中，为了讲述方便，我们做如下假设：

Memory is word addressed
Words are int-sized

深入理解计算机系统第 18 课 Dynamic Memory Allocation - Basic Concept

具体的例子：

深入理解计算机系统第 18 课 Dynamic Memory Allocation - Basic Concept

程序可以用任意的顺序发送 malloc 和 free 请求， free 请求必须作用与已被分配的 block。

分配器有如下的限制：

不能控制已分配 block 的数量和大小
必须立即响应 malloc 请求（不能缓存或者给请求重新排序）
必须在未分配的内存中分配
不同的 block 需要对齐（32 位中 8 byte，64 位中 16 byte）
只能操作和修改未分配的内存
不能移动已分配的 block

性能指标

现在我们可以来看看如何去评测具体的分配算法了。假设给定一个 malloc 和 free 的请求的序列：

$$R_0, R_1, ..., R_k, ..., R_{n-1}$$

目标是尽可能提高吞吐量以及内存利用率（注意，这两个目标常常是冲突的）

吞吐量是在单位时间内完成的请求数量。假设在 10 秒中之内进行了 5000 次 malloc 和 5000 次 free 调用，那么吞吐量是 1000 operations/second

另外一个目标是 Peak Memory Utilization，就是最大的内存利用率，具体如下：

深入理解计算机系统第 18 课 Dynamic Memory Allocation - Basic Concept

影响内存利用率的主要因素就是『内存碎片』，有两种类型：

internal fragmentation
external fragmentation0

内部碎片

对于给定的 block，internal fragmentation 主要是因为 payload 小于 block size 造成的，如下图所示：

深入理解计算机系统第 18 课 Dynamic Memory Allocation - Basic Concept

主要是由以下原因导致；

Overhead of maintaining heap data structures
Padding for alignment purposes
Explicit policy decisions

只依赖于上一个请求的具体模式，所以比较容易测量。

外部碎片

指的是内存中没有足够的连续空间，如下图所示：

深入理解计算机系统第 18 课 Dynamic Memory Allocation - Basic Concept

依赖于未来的请求模式，所以比较难测量。

实现细节

在具体实现之前，需要考虑以下问题：

给定一个指针，我们如何知道需要释放多少内存？
如何记录未分配的 block ？
实际需要的空间比未分配的空间要小的时候，剩下的空间怎么办？
如果有多个区域满足条件，如何选择？
释放空间之后如何进行记录？

一个标准的方式是在指针的前一个 word 中保存 block 的大小，通常称之为 header field 或 header，这种方式需要额外的一个 word，具体如下：

深入理解计算机系统第 18 课 Dynamic Memory Allocation - Basic Concept

这里我们先给出常用的四种方式，这节课主要介绍第一种，下节课会介绍后面的方法：

深入理解计算机系统第 18 课 Dynamic Memory Allocation - Basic Concept

隐式 free 列表

对于每个 block 来说，我们需要知道大小和具体的状态（已分配/未分配），可以用两个 word 来存储，但是这样太浪费了。

如果一个 block 已经对其，低位地址一定是 0，所以我们可以用来当做 allocated/free 标志，当读入 word 大小的时候，需要标记出这个值。

深入理解计算机系统第 18 课 Dynamic Memory Allocation - Basic Concept

寻找未分配的空间的方式如下，主要有三种：

深入理解计算机系统第 18 课 Dynamic Memory Allocation - Basic Concept

确定空间之后，具体进行分配如下：

深入理解计算机系统第 18 课 Dynamic Memory Allocation - Basic Concept

void addblock(ptr p, int len) {
    int newsize = ((len + 1) >> 1) << 1;  // round up to even
    int oldsize = *p & -2;                // mask out low bit
    *p = newsize | 1;                     // set new length
    if (newsize < oldsize)
        *(p+newsize) = oldsize - newsize; // set length in remaining
                                          // part of block
}