这是本学期创新实践课程uCore OS实验2的挑战部分,代码实现可见:buddy.cbuddy.hslub.cslub.h

Buddy System分配算法

初始化

在Buddy System中,空间块之间的关系形成一颗完全二叉树,对于一颗有着n叶子的完全二叉树来说,所有节点的总数为。也就是说,如果Buddy System的可分配空间为n页的话,那么就需要额外保存2n-1个节点信息。

初始化空闲链表

Buddy System并不需要链表,但是为了在调式的时候方便访问所有空闲空间,还是将所有的空闲空间加入链表中。

确定分配空间大小

假设我们得到了大小为n的空间,我们需要在此基础上建立Buddy System,经过初始化后,Buddy System管理的页数为,那么大小为n的实际空间可能分为两个或者三个部分。

节点信息区:节点信息区可以用来保存每个节点对应子树中可用空间的信息,用于在分配内存的时候便于检查子树中是否有足够的空间来满足请求大小。在32位操作系统中,最大页数不会超过4GB/4KB=1M,所有使用一个32位整数即可表示每个节点的信息。所以节点信息区的大小为字节,每页大小为4KB,内存占用按照页面大小对齐,所以占用页。

虚拟分配区:占用页。

实际分配区:显然实际可以得到的内存大小不大可能刚好等于节点信息区大小+分配空间区大小。如果节点信息区大小+分配空间区大小<=内存大小,那么实际可以分配的区域就等于页。如果节点信息区大小+分配空间区大小>内存大小,那么实际可以分配的区域就等于页。

作为操作系统,自然希望实际使用的区域越大越好,不妨分类讨论。

当内存小于等于512页:此时无论如何节点信息都会占用一页,所以提高内存利率的方法就是将实际内存大小减一后向上取整(文中整数意为2的幂)。

当内存大于512页:不难证明,对于内存大小来说,最佳虚拟分配区大小往往是n向下取整或者向上取整的数值,所以候选项也就是只有两个,所以可以先考虑向下取整。对于中的数,向下取整可以得到:

  • 时,显然已经是最佳值;
  • 时,扩大虚拟分配区导致节点信息区增加却没有使得实际分配区增加,所以当期m还是最佳值;
  • 时,可以扩大实际分配区。
初始化节点信息

虚拟分配区可能会大于实际分配区,所以一开始需要将虚拟分配区中没有实际分配区对应的空间标记为已经分配进行屏蔽。另当前区块的虚拟空间大小为,实际空间大小为,屏蔽的过程如下:

  • 如果,将空间初始化为一个空闲空间,屏蔽过程结束;
  • 如果,将空间初始化为一个已分配空间,屏蔽过程结束;
  • 如果,将右半空间初始化为已分配空间,更新后继续对左半空间进行操作;
  • 如果,将左半空间初始化为空闲空间,更新后继续对左半空间进行操作。

以虚拟分配区16页、实际分配区14页为例,初始化后如下:

[0,16)
[0,16)
[0,8)
[0,8)
[8,16)
[8,16)
[8,12)
[8,12)
[12,16)
[12,16)
[12,14)
[12,14)
[14,16)
[14,16)
8
8
4
4
2
2
2
[Not supported by viewer]

分配过程

Buddy System要求分配空间为2的幂,所以首先将请求的页数向上对齐到2的幂。

接下来从二叉树的根节点(1号节点)开始查找满足要求的节点。对于每次检查的节点:

  • 如果子树的最大可用空间小于请求空间,那么分配失败;

  • 如果子树的最大可用空间大于等于请求空间,并且总空间大小等于请求空间,说明这个节点对应的空间没有被分割和分配,并且满足请求空间大小,那么分配这个空间;

  • 如果子树的最大可用空间大于等于请求空间,并且总空间大小大于请求空间,那么在这个节点的子树中查找:

    • 如果这个节点对应的空间没有被分割过(最大可用空间等于总空间大小),那么分割空间,在左子树(左半部分)继续查找;
    • 如果左子树包含大小等于请求空间的可用空间,那么在左子树中继续查找;
    • 如果右子树包含大小等于请求空间的可用空间,那么在右子树中继续查找;
  • 如果左子树的最大可用空间大于等于请求空间,那么在左子树中继续查找;

    • 如果右子树的最大可用空间大于等于请求空间,那么在右子树中继续查找。

算法中加粗的部分主要为了减少碎片而增加的额外优化。

当一个空间被分配之后,这个空间对应节点的所有父节点的可用空间表都会受到影响,需要自地向上重新更新可用空间信息。

释放过程

Buddy System要求分配空间为2的幂,所以同样首先将请求的页数向上对齐到2的幂。

在进行释放之前,需要确定要释放的空间对应的节点,然后将空间标记为可用。接下来进行自底向上的操作:

  • 如果某节点的两个子节点对应的空间都未分割和分配,那么合并这两个空间,形成一个更大的空间;
  • 否则,根据子节点的可用空间信息更新父节点的可用空间信息。

Slub分配算法

实际上Slub分配算法是非常复杂的,需要考虑缓存对齐、NUMA等非常多的问题,作为实验性质的操作系统就不考虑这些复杂因素了。简化的Slub算法结合了Slab算法和Slub算法的部分特征,使用了一些比较右技巧性的实现方法。具体的简化为:

  • Slab大小为一页,不允许创建大对象仓库
  • 复用Page数据结构,将Slab元数据保存在Page结构体中

数据结构

在操作系统中经常会用到大量相同的数据对象,例如互斥锁、条件变量等等,同种数据对象的初始化方法、销毁方法、占用内存大小都是一样的,如果操作系统能够将所有的数据对象进行统一管理,可以提高内存利用率,同时也避免了反复初始化对象的开销。

仓库

每种对象由仓库(感觉cache在这里翻译为仓库更好)进行统一管理:

struct kmem_cache_t {
    list_entry_t slabs_full;	// 全满Slab链表
    list_entry_t slabs_partial;	// 部分空闲Slab链表
    list_entry_t slabs_free;	// 全空闲Slab链表
    uint16_t objsize;		// 对象大小
    uint16_t num;			// 每个Slab保存的对象数目
    void (*ctor)(void*, struct kmem_cache_t *, size_t);	// 构造函数
    void (*dtor)(void*, struct kmem_cache_t *, size_t);	// 析构函数
    char name[CACHE_NAMELEN];	// 仓库名称
    list_entry_t cache_link;	// 仓库链表
};

由于限制Slab大小为一页,所以数据对象和每页对象数据不会超过,所以使用16位整数保存足够。然后所有的仓库链接成一个链表,方便进行遍历。

Slab

在上面的Buddy System中,一个物理页被分配之后,Page结构中除了ref之外的成员都没有其他用处了,可以把Slab的元数据保存在这些内存中:

struct slab_t {
    int ref;				// 页的引用次数(保留)
    struct kmem_cache_t *cachep;	// 仓库对象指针
    uint16_t inuse;			// 已经分配对象数目
    int16_t free;			// 下一个空闲对象偏移量
    list_entry_t slab_link;		// Slab链表
};

为了方便空闲区域的管理,Slab对应的内存页分为两部分:保存空闲信息的bufcnt以及可用内存区域buf。

bufctl
[Not supported by viewer]
buf
[Not supported by viewer]
1
1
2
2
3
3
-1
-1
object 0
object 0
object 1
[Not supported by viewer]
...
...
object 2
[Not supported by viewer]
object n-1
[Not supported by viewer]
...
...
0
0
1
1
2
2
n-1
n-1

对象数据不会超过2048,所以bufctl中每个条目为16位整数。bufctl中每个“格子”都对应着一个对象内存区域,不难发现,bufctl保存的是一个隐式链表,格子中保存的内容就是下一个空闲区域的偏移,-1表示不存在更多空闲区,slab_t中的free就是链表头部。

内置仓库

除了可以自行管理仓库之外,操作系统往往也提供了一些常见大小的仓库,本文实现中内置了8个仓库,仓库对象大小为:8B、16B、32B、64B、128B、256B、512B、1024B。

操作函数

私有函数
  • void *kmem_cache_grow(struct kmem_cache_t *cachep);

申请一页内存,初始化空闲链表bufctl,构造buf中的对象,更新Slab元数据,最后将新的Slab加入到仓库的空闲Slab表中。

  • void kmem_slab_destroy(struct kmem_cache_t *cachep, struct slab_t *slab);

析构buf中的对象后将内存页归还。

公共函数
  • void kmem_int();

初始化kmem_cache_t仓库:由于kmem_cache_t也是由Slab算法分配的,所以需要预先手动初始化一个kmem_cache_t仓库;

初始化内置仓库:初始化8个固定大小的内置仓库。

  • kmem_cache_create(const char *name, size_t size, void (*ctor)(void*, struct kmem_cache_t *, size_t),void (*dtor)(void*, struct kmem_cache_t *, size_t));

从kmem_cache_t仓库中获得一个对象,初始化成员,最后将对象加入仓库链表。其中需要注意的就是计算Slab中对象的数目,由于空闲表每一项占用2字节,所以每个Slab的对象数目就是:4096字节/(2字节+对象大小)。

  • void kmem_cache_destroy(struct kmem_cache_t *cachep);

释放仓库中所有的Slab,释放kmem_cache_t。

  • void *kmem_cache_alloc(struct kmem_cache_t *cachep);

先查找slabs_partial,如果没找到空闲区域则查找slabs_free,还是没找到就申请一个新的slab。从slab分配一个对象后,如果slab变满,那么将slab加入slabs_full。

  • void *kmem_cache_zalloc(struct kmem_cache_t *cachep);

使用kmem_cache_alloc分配一个对象之后将对象内存区域初始化为零。

  • void kmem_cache_free(struct kmem_cache_t *cachep, void *objp);

将对象从Slab中释放,也就是将对象空间加入空闲链表,更新Slab元信息。如果Slab变空,那么将Slab加入slabs_partial链表。

  • size_t kmem_cache_size(struct kmem_cache_t *cachep);

获得仓库中对象的大小。

  • const char *kmem_cache_name(struct kmem_cache_t *cachep);

获得仓库的名称。

  • int kmem_cache_shrink(struct kmem_cache_t *cachep);

将仓库中slabs_free中所有Slab释放。

  • int kmem_cache_reap();

遍历仓库链表,对每一个仓库进行kmem_cache_shrink操作。

  • void *kmalloc(size_t size);

找到大小最合适的内置仓库,申请一个对象。

  • void kfree(const void *objp);

释放内置仓库对象。

  • size_t ksize(const void *objp);

获得内置仓库对象大小。

参考资料