4.1 物理内存管理

在虚拟内存管理讲了操作系统是怎么管理虚拟内存的. 现在就是物理内存的管理了. 虚拟内存管理已经解决了程序对内存的使用问题, 物理内存管理解决内存的分配问题.

如何评价物理内存

内存控制器

按理说想要使用物理内存就得给出区号块号什么乱七八糟的东西, 但是有一个好东西可以将地址翻译成内存要的东西. 那就是 内存控制器(Memory Controller) .

它提供了易用的物理内存抽象, 让操作系统的内存管理变得很简单, 一个地址就能读出一字节数据.

内存多通道

一般的内存条是分多通道的, 不同通道的空间可以同时访问, 相同通道的空间不能同时访问(因为它们连着相同的数据总线).

内存条被分成很多的小块, 双通道内存通常是奇数块号的小块属于一个通道, 偶数块号的属于另一个通道. 每一个小块都是 64 字节, 因此使用数组时, 单一元素最好不要超过 128 字节, 超过了就需要跨块访问了, 一定会由两个块是同一个通道. 我们的电脑基本上都是双通道内存的.

物理内存管理的碎片问题

碎片分为两种, 一种是外部碎片, 一种是内部碎片.

外部碎片

空闲的但不连续, 无法被使用

内部碎片

分配大小比实际用的要大

物理内存的评价指标

内存资源利用率

外部碎片和内部碎片

物理内存分配

产生映射需求时, 要找到合适的物理页

分配速度

复杂的算法可以更好地解决碎片问题, 但是代价是内存分配操作的性能降低

基于位图的连续物理页分配

位图可以把它当作是一串二进制数, 第 n 位有两种状态, 一种是 0, 另一种是 1. 在不需要复杂状态下, 用位图可以节约内存.

基于位图的连续物理页分配其实就是把整个物理内存分配 N 个物理页, 大小 4K. 然后准备一个位图, 一位对应一个物理页. 比如第 k 位为 0, 表示第 k 个物理页没有被分配; 第 k 位为 1, 表示第 k 个物理页被分配了.

内存分配器的初始化

bit bitmap[N];

void init_allocator(void) {
    int i;
    for (i = 0; i < N; ++i) {
        bitmap[i] = 0;
    }
}

这是初始化内存分配器的代码. 内存分配器会维护一个位图, 这里当作数组吧.

内存分配器分配 n 个连续的物理页

u64 alloc_pages(u64 n) {
    int i, j, find;
    for(i = 0; i < N; ++i) {
        find = i;
        for(j = i; j < n; ++j) {
            if(bitmap[i+j] != 0) {
                find = 0;
                break;
            }
        }

        if (find) {
            for(j = i; j < i+n; ++j) {
                bitmap[j] = 1;
            }
            return FREE_MEM_START + i * 4K;
        }
    }
    return -1;
}

可以看出来, 基于位图的连续物理页分配的时间复杂度还挺大的. 大概就是遍历整个位图, 先找到第一个没有被分配的物理页, 然后往后判断 n-1 个物理页有没有被分配; 如果这 n 个物理页都没有被分配, 那就把这 n 个物理页标记成被分配了, 然后返回第一个物理页的起始地址.

这个 FREE_MEM_START 是一个基址, 加上偏移量就是分配的连续物理页的基址了.

内存分配器释放 n 个连续的物理页

free_pages(u64 addr, u64 n) {
    int page_idx;
    int i;

    page_idx = (addr - FREE_MEM_START) / 4K;

    for(i = 0; i < n; ++i) {
        bitmap[page_idx+i] = 0;
    }
}

有的同学可能看不习惯, 这里的 C 语言版本是比较老的, 如果在 for 语句里int i = 0;编译器会报错. 不过现代的我们编写代码的时候, 变量都是会提升的, 只是编译器帮我们处理了一下, 让我们不用提升变量.

这里传入一个起始物理页基址和需要释放的数量, 在位图把它们标记成未分配就可以了. 不需要将物理内存的数据都清空, 之后别人用的时候直接写就可以了, 反正页访问不了, 访问的话会引发异常.

伙伴系统

伙伴系统也是以块为单位, 分配连续的物理内存页.

伙伴系统会把比较大的块, 均分成两个相同的块. 这两个块是彼此的兄弟块. 这两个小块还可以继续分裂. 一般最小是 4KB.

分配

当程序需要 15KB 内存时, 32KB 的连续物理页会分成两个 16KB 连续物理页, 把其中一个连续物理页分给这个程序, 另一个空闲.

伙伴系统使用一个链表数组来管理空闲块.

这个数组的每一个元素都是链表. 当需要 7KB 内存时, 会从第二个元素里找(第一个元素放 4KB 的链表, 第二个 8KB, 第三个 16KB, 以此类推), 如果没有的话那就找第三个的, 一直找下去. 找到了如果需要分裂, 那就分裂成合适的大小, 并在相应的链表后面加上空闲块.

这里的话可以在第三个元素里找到 16KB 的连续物理页, 拆成两个 8KB 的, 一个分配出去, 另一个放在第二个元素的链表里.

释放

假如刚刚分配的 8KB 释放了, 现在要把它拿回链表数组了. 现在就需要找它的兄弟了.

兄弟块之间只有 1 位不同, 只需要找到这样的块就说明是它的兄弟.

在一个连续物理页释放后, 会在对应大小的链表里找有没有它的兄弟, 如果有, 那就合并去下一级链表找, 如果有继续合并, 没有的话就挂在链表后面.

由于兄弟块与兄弟块之间只有一位之差, 所以这个寻找非常高效. 块的大小决定了这个一位之差发生在哪.

SLAB 分配器

建立在伙伴系统的分配器

SLAB 分配器家族(Linux)

• SLAB 分配器

• SLUB 分配器

• SLOB 分配器

伙伴系统中, 分配的最小单位是一个物理页(4K), 不过实际上我们可能用不了这么大, 依旧分配 4K 就产生了内部碎片.

目标

毫无疑问, 刚提到了内部碎片那 SLAB 当然是处理内部碎片的问题.

SLAB 的目标是快速分配小内存对象, 后来由于设计过于复杂出现了 SLUB, 再后来针对内存稀缺的场景又提出了 SLOB.

SLUB

基本思想

首先从伙伴系统获取大块内存, 然后自己进一步细分成小块内存进行管理. 也就是再加一层.

块大小通常是$2^n$个字节(一般$3\le n<12$), 不过可以自己额外增加特殊大小如 198 字节来减小内部碎片.

只分配固定大小块

SLUB 分配器维护一些内存资源池, 每一个固定块大小都有自己的内存资源池. SLUB 使用 best fit 来定位资源池.

SLUB 的内存资源池

一个资源池由三个指针来管理. 这里把从伙伴系统获取到的物理内存块称为 slab. slab 内部可以当作是一个链表, 每个节点的大小都是对应内存资源池的大小. 比如 128KB 的内存资源池里的节点就是 128KB.

• Current 仅指向一个 slab

• Partial 指向未满 slab 链表

• Full 指向全满 slab 链表

分配

当需要分配时, 首先从 Current 指向的 slab 找有没有空闲的节点, 如果有的话就分配出去, 然后标记成已分配; 如果没有空闲的节点, 那就只能用 Partial 的了. 先把 Current 指向的 slab 移动到 Full 指向的链表, 然后让 Current 指向 Partial 里的一个 slab, 再分配空间.

释放

把对应的 slab 里对应的空间标记成未分配, 然后如果它在 Full 链表里, 那么移动到 Partial 链表. 如果 Partial 全空那么就还给伙伴系统.

Linux 内存管理结构