内存管理算法

笔者以前曾经写过一个RTOS内核，内核中有多种内存管理算法，有：

1.类SLOB算法，分配及释放最坏时间复杂度为O(n)，该算法被笔者大量使用，应该没什么问题

2.内存池算法，有多个版本，时间复杂度包括O(1)、O(N)，具有静态、动态多种分配

3.连接链表-红黑树算法，结合first-fit与best-fit策略及染色策略，O(logN)复杂度，比第一种类SLOB算法快很多

4.radix树-索引算法，O(K)复杂度，用位运算进行映射分配的想法来自tlsf算法，查找内存块时间近似于常数，与tlsf算法相比，可以通过调整树高实现空间-时间置换策略，且具有更强大的动态特性。

1.相较于tlsf算法，虽然二者执行时间都是固定的，但前者具有动态优势。

2.相对于连接链表-红黑树算法，时间复杂度远远胜出一个量级，缺点是比较耗费内存。

应该还要写一个tlsf算法的，不过笔者太懒了，而且笔者认为tlsf算法与radix树的思想其实已经非常接近了，而且其实类SLOB算法已经完全够用了，还是以后有时间再写吧。

注意

radix树-索引算法有bug，至于为什么有bug笔者仍然选择上传，是因为笔者认为算法思路没问题，但是根本找不到bug。虽然无法使用，但是作为一种笔者设计的O(K)（其中的K取决于树高，用户可自调整）时间复杂度的算法，其动态特性和查找时间对另外几种内存管理算法都是降维打击，记录该算法的思路是非常有必要的，其中的bug只能等以后再修复了。

测试程序

测试了类SLOB算法与连接链表-红黑树算法，分配规模为43MB内存，分配内存为16Byte到1kb：

表现：

1.类SLOB算法，这种算法在FreeRTOS，RTT-Thread都被使用，多次测试，总耗时约为900ms

2.连接链表-红黑树算法，总耗时约35ms

两种算法的差距随分配规模的增长越发明显，如果将分配规模增加一倍（修改最大分配块大小为1024，总分配规模变成80MB），前者总耗时翻倍，达到了2000ms，而后者却只增长几ms，仅仅达到42ms。

O(logN)对O(n)已经是非常惊人的了，难以想象radix树的O(K)时间复杂度算法会到达怎样一个程度，可惜程序有bug，根本通不过测试。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#include <stdio.h>
#include <stdint.h>
#include "memalloc.h"
#include <stddef.h>
#include <stdlib.h>
#include <time.h>

#define INITIAL_ALLOCATIONS 5000  // 初始化阶段分配的块数
#define TEST_ITERATIONS 100000     // 测试阶段的分配与释放操作次数
#define MAX_ALLOC_SIZE 1024       // 最大分配块大小
#define MIN_ALLOC_SIZE 16         // 最小分配块大小

void *heap_malloc(size_t WantSize);
void heap_free(void *xReturn);

void shuffle(void **array, int n) {
    for (int i = n - 1; i > 0; i--) {
        int j = rand() % (i + 1);
        void *temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
}

void memory_test() {
    void *allocations[INITIAL_ALLOCATIONS + TEST_ITERATIONS];
    size_t sizes[INITIAL_ALLOCATIONS + TEST_ITERATIONS];
    uint32_t failed_allocs = 0;
    size_t total_memory_used = 0;
    size_t actual_memory_used = 0;
    size_t fragmented_memory = 0;
    clock_t start_test, end_test;

    // **初始化阶段**
    for (int i = 0; i < INITIAL_ALLOCATIONS; i++) {
        sizes[i] = (rand() % (MAX_ALLOC_SIZE - MIN_ALLOC_SIZE + 1)) + MIN_ALLOC_SIZE;
        allocations[i] = heap_malloc(sizes[i]);

        if (allocations[i]) {
            total_memory_used += sizes[i];
            actual_memory_used += sizes[i];
        } else {
            failed_allocs++;
        }
    }

    // **随机释放部分内存形成碎片**
    shuffle(allocations, INITIAL_ALLOCATIONS);
    for (int i = 0; i < INITIAL_ALLOCATIONS / 2; i++) {
        if (allocations[i]) {
            heap_free(allocations[i]);
            actual_memory_used -= sizes[i];
            allocations[i] = NULL;
        }
    }

    // **测试阶段**
    start_test = clock();
    for (int i = INITIAL_ALLOCATIONS; i < INITIAL_ALLOCATIONS + TEST_ITERATIONS; i++) {
        sizes[i] = (rand() % (MAX_ALLOC_SIZE - MIN_ALLOC_SIZE + 1)) + MIN_ALLOC_SIZE;
        allocations[i] = heap_malloc(sizes[i]);

        if (allocations[i]) {
            total_memory_used += sizes[i];
            actual_memory_used += sizes[i];
        } else {
            failed_allocs++;
            fragmented_memory += sizes[i];
        }

        int random_index = rand() % (i + 1);
        if (allocations[random_index]) {
            heap_free(allocations[random_index]);
            actual_memory_used -= sizes[random_index];
            allocations[random_index] = NULL;
        }
    }
    end_test = clock();


    // **输出碎片化统计**
    double total_test_time_ms = (double)(end_test - start_test) * 1000 / CLOCKS_PER_SEC;
    double fragmentation_rate = (double)fragmented_memory / total_memory_used * 100;

    printf("\n--- Test Results ---\n");
    printf("Total memory used: %zu MB\n", total_memory_used / (1024 * 1024));
    printf("Actual memory used: %zu MB\n", actual_memory_used / (1024 * 1024));
    printf("Failed allocations: %u\n", failed_allocs);
    printf("Total test time: %.2f ms\n", total_test_time_ms);
    printf("Fragmented memory: %zu KB\n", fragmented_memory / 1024);
    printf("Fragmentation rate: %.2f%%\n", fragmentation_rate);
}

int main() {
    srand((unsigned int)time(NULL));
    memory_test();
    return 0;
}

类SLOB算法

理论

SLOB算法是linux内核的一种分配器，特点是实现了极简、极低开销的内存分配机制，它是一种基于链表的分配器，其设计灵感来自早期 UNIX 的 K&R 分配器。它直接在页框中维护一个空闲块链表，每个块记录大小和下一个空闲块的位置。

分配策略：默认使用首次适应（first-fit），即从头开始找第一个能放下请求大小的空闲块。 释放策略：释放时尝试与相邻空闲块合并，减少碎片。 页管理：每个页头部维护一个空闲块链表，页来自伙伴系统

实现

在嵌入式场景中，内存以page划分是不可能的，一个page就是4KB。要知道很多单片机就几十KB物理内存。

所以，如何管理这些小内存呢？

小内存管理算法，通常也称为内存分配器，用于在内存资源有限的嵌入式系统中高效地管理内存。这些算法的目标是减少内存碎片，提高内存利用率，并确保分配和释放内存的操作尽可能快速、稳定。

它采用不断分割的方法对内存进行动态分配，分为初始化，分割，释放三个步骤，为了简洁起见，笔者直接放图：

初始化与申请

1
2
3
4
graph LR
A(头部)-->B(初始大内存块)-->C(尾部)

 
1
2
graph LR
A(头部)-->B(内存块)-->C(内存块)-->D(内存块)-->E(内存块)-->T(尾部)

这是整体思想，通过对初始内存块的不断切割，最终形成了各个不同的内存块。

初始化

1
2
graph LR
A(头部)-->B(内存块)-->C(尾部)

在初始化后，空闲内存块已经形成了一条链表，这条链表被称为空闲内存块链表，内存块被使用就被踢出这条链表，被释放就加入这条链表，如果内存块大于要申请的大小，就把多余的部分切割，然后加入这条内存链表。

malloc会找到合适的内存块，并且返回它的地址。

申请malloc

1
2
3
4
graph LR
A(头部)--从头开始找_直到找到符合大小的内存块-->B(内存块)-->C(内存块)-->D(内存块)-->E(内存块)-->T(尾部)


1
2
3
graph LR
G(链表起始)--把初始化的内存链表模型作为空闲内存块建立的链表-->F(结束)
A(prev)--在这条链表上找到符合条件的内存块-->B(use)-->C(new)

这条链表上就是空闲内存块链表，内存块被使用就被踢出这条链表，被释放就加入这条链表，如果内存块大于要申请的大小，就把多余的部分切割，然后加入这条内存链表。

最终读者会看到，空闲内存块会越来越小，而且也越来越不连续。

虽然通过指针，通常情况下我们可以把不连续的空间当成连续的空间使用，这些不连续的空间被称为碎片。但是，

当不连续的空间越来越小时，我们很可能找不到一个足够大的空间碎片满足存储请求，尽管总的空闲空间可能仍然满足。

这样下去，系统绝对是会崩溃的。

为了避免碎片问题，也有一些方法被广泛采用。

分配时的策略

为了减少碎片，通常有两种策略：best-fit和first-fit。

best-fit算法：这个策略趋向于将大的碎片保留下来满足后续的请求。我们根据空闲空间块的大小，将它们分在若干个容器中，在容器中，存储块按照他们的大小进行排列，这使得寻找best-fit块变得更加容易。

first-fit算法 ：在这个策略中，对象被放置在地址最低的、能够容纳对象的碎片中。这种策略的优点是速度快，但是内存分配性能比较差。

free释放

释放内存块，就是将内存块加入空闲内存块表。同时会有一些方法减少碎片。

合并内存块

同时，如果我们检测到free释放的内存块的地址与其他空闲内存块是连续的，我们会合并它们：

合并内存块

1
2
3
4
5
graph LR
A(开始)-->B(prev)-->C(next)-->D(结束);
E(Insert)-->G(?)


1
2
3
4
graph LR
A(start)-->B-->C(Insert)-->D-->E-->G(end);


内存块后相邻：

1
2
3
graph LR
A(start)--后相邻-->B-->C(Insert)-->E-->F(end);
D-->E;

合并后等价于：

1
2
3
graph LR
A(start)--后相邻-->B-->C(Insert + D)-->E-->F(end);

内存块前相邻：

1
2
3
4
graph LR

A(start)--前相邻-->B-->D-->E-->F(end);
C(Insert)-->D;

合并后等价于：

1
2
3
4
graph LR

A(start)--前相邻-->B(B+Insert)-->D-->E-->F(end);

前后都相邻：

1
2
graph LR
A(start)--可以只考虑最终结果-->B--Insert + D-->E-->F(end);

合并后等价于：

1
2
3
4
graph LR

A(start)--可以只考虑最终结果-->B(B + Insert +D)-->E-->F(end);

共有三种情况：前相邻、后相邻、前后都相邻。

如果前后相邻是相互独立的，那么互不影响，如果不独立，通过后，前的顺序可以得到前后都相邻的结果，因此该顺序正确。

所以程序中，我们先进行后相邻合并判断，再进行前相邻合并判断。