操作系统L1实验笔记

分类:Operating System, 发布于:2019-03-31 18:28:15, 更新于:2019-04-19 00:09:40。 评论

数据结构

为了防止在各种坑人的内存测试中挂掉,我采用了Slab内存分配方式,每种内存大小对应一个cache,每个cache有多个slab对象,每个slab对象对应一个4KB(或者更大的)内存块,包含多个内存对象。

整个内存被分为三个区域(对应图中从左往右):

  • 页面区:可分配的内存空间
  • 缓存区:分配slab cache对象
  • 指示器:用bool类型指示对应的内存块是否可用

每个slab cache为kmem_cache类型,包含两个链表,分别对应可用的Slab和已经全部占用(满的)slab。每个slab为kmem_slab类型,也分别保存两个链表,指向可用的内存对象和不可用的内存对象。为了回收方便,我在每个内存对象的前面贴了一个kmem_item类型的数据,指向slab。

分配、回收过程

内存分配时,先计算所需size + kmem_item的大小,找到对应大小的cache。如果对应的cache有空闲的slab,直接使用,否则进行增长操作。如果所需大小小于512B则分配1个页面,否则分配8个对应对象所需要的内存页面数。在空闲的slab中取出一个空闲的内存对象,将指针加上kmem_item对应的偏移量返回给用户。

回收内存时,将指针减去对应的偏移量,得到kmem_item的指针,然后取出kmem_slab的地址,将该内存对象重新标记为可用即可。

接口封装与自旋锁

内存的分配、回收在进入allocfree函数时直接上自旋锁,先计算所需大小,然后调用具体执行的函数kmem_allockmem_free,内部调用返回后再解开自旋锁,返回获得的结果。

存在的问题与解决方案

在某位超级大佬提供的测试代码中我的无懈可击的完美程序挂了,因为大佬的测试代码分配的内存大小随机,而我的代码每种大小都会单独生成cache,很快cache分区就爆了。

解决方案很简单,对于每次内存分配,都找到不小于所需要的大小的2的次幂。这样cache的种类就非常少了(10种即可覆盖1KB以下的所有需求)。而由于对allocfree函数进行了封装,修改起来也非常简单。只需要在进行内部调用前修改所需大小的值,把修改后的值传入调用即可。例如:

void* alloc(size_t size) {
    lock();
    size_t real_size = cal_real_size();
    void *ret = kmem_alloc(real_size);
    unlock();
    return ret;
}

评论