MallocLab

本文最后更新于:2021年6月9日 早上

实验说明

在这个实验中,我们将实现C中的malloc,free和remalloc函数。

CSAPP的mallocLab提供了一个基本的框架和10个测试文件。

我们只需完成mm.c文件。

因为在实验过程中,我们可能需要编写几个不同版本的mm.c文件,因此为了保存不同的版本,可能需要重新组织一下文件结构。

下面安利一下我本人采取的文件结构并放上测试流程。(从github上clone下来可直接食用)

cd my_malloc
/* 完成mm.c文件 */
make clean
make
./mdriver

好了,在确保阅读了CSAPP中的第9章以及实验的Writeup,就开始我们的malloc之旅吧。

注:本文章三个版本malloc代码已上传至github(有详细的注释)。

隐式链表+First_fit

衡量一个内存分配器的好坏的两个指标是内存利用率和吞吐率。这两者往往是矛盾的,因此我们要寻找一个平衡点(当然其实内存利用率更重要一点,毕竟内存=money

让我们考虑如何组织一个动态内存分配器,内存分配器本质是在一大块字节数组(称之为堆)中分配一些字节数组(称之为块)提供给用户。因此我们整个设计都是围绕如何组织空闲块和遍历空闲块。

对应的,书上介绍了三种组织空闲块的方式和三种寻找空闲块的方式。

隐式空闲链表、显示空闲链表、分离的空闲链表首次适配,下次适配,最佳适配

笔者尝试了三种组合:

  • 隐式空闲链表+First_fit

  • 隐式空闲链表+Next_fit

  • 分离空闲链表+First_fit

强烈建议先从第一种开始熟悉下整个框架,而且书本基本给出了第一种的完整代码。

堆块的结构和堆整体结构如下图。

我们可以将堆组织为一个连续的已分配块和空闲块的序列(隐式空闲链表)。这样当我们寻找空闲块的时候,只需按照头部和尾部的块大小信息来遍历整个堆。

这种组织方式的优点是简单。但缺点就是malloc操作的时间开销太大,因为我们每次搜索时间的大小都与整个堆大小呈线性关系。

书中采取的是First_fit匹配方式,即找到第一个满足条件的空闲块就停止。

由于书上已经把完整代码给出来了,这里就不放了,然后测试一下书上的代码。

好吧,看来书上的代码成绩并不是很理想,我们发现thru的分数过低,所以接下来让我们换Next_fit试一下。

隐式链表+Next_fit

将First_fit改成Next_fit,即每次搜索空闲块的时候从上一次搜索到空闲块的地方开始,它源于这样一个思想:如果我们上次在某个空闲块里已经发现了一个匹配,那么很可能下一次我们也能在这个剩余块中发现匹配。显然,这样的思想能使我们的搜索效率提升,但代价就是内存利用率会低得多。

static void *next_fit(size_t size){
    for (char* bp = pre_listp; GET_SIZE(HEAD(bp)) > 0; bp = NEXT_BLKP(bp))
    {
        if (!GET_ALLOC(HEAD(bp)) && GET_SIZE(HEAD(bp)) >= size)
        {
            return bp;
        }
    }
    return NULL;
}

提一下用这个方法的时候踩的坑吧,记录上一次结果的pre_listp除了要在mm_init和place中更新外,在coalesce中也要记得更新pre_listp(这个bug调了一年),因为合并块的时候会更改bp的位置,如果之前pre_listp恰好在合并前的bp位置,不更新就会导致之后非空闲块被覆盖。

改完后测试一下。

嗯。时间效率一下提升了不少,而且内存利用率也没有降低的很多,这种方案已经到达及格线了。最后再让我们尝试一下分离空闲链表。

分离空闲链表+First_fit

我们考虑将空闲链表采用显式链表的方式组合,这样能将时间复杂度从搜索整个堆降低为搜索堆中的空闲块。

更进一步,我们将这个显式链表分成若干个链表,分类的依据是链表中每个空闲块的大小。

例如,我们可以根据2的幂来划分:

{1},{2},{3,4},{58},…,{1025 ~2048 },{20494096},{4097 ~ \infty }

这样,分配器维护一个空闲链表数组,当分配器需要一个大小为 n 的块时,它就搜索相应大小的空闲链表。如果不能找到合适的块与之分配,它就搜索下一个空闲链表。

画个图直观的感受一下。

C中真正的malloc实现也是采用了分离空闲链表的思想。

在脑中有了这个组织架构后,我们就开始实现我们的想法吧。

完整代码在此处,因为有详细的注释,就不再讲解了。直接放下最后跑分结果吧。(终于上90了,完结撒花

总结

这次Lab断断续续做了一周左右(其实主要时间花在debug上了),而且还参考了大量前人的博客,可以说是所有Lab中最难且花费时间最多的一个了。之前从来没有尝试过全是指针的编程,但是在做个实验的过程中,不得不感叹,指针真是个有魅力的家伙,用的好挥斥方遒,用不好就各种segfalut了。

本来这个实验看起来这么硬核,当我完成Nextfit取得80分的时候就想放弃了,但是看到书上的最后一种方法以及体验了指针的魅力之后,还是坚持了下去(调指针bug太痛苦了)。相应地,完完整整做完这个实验带给你的感悟绝对不是书上的理论能比拟的,对内存中的每个字节操作,一招不慎,满盘皆输,但不得不说太cool了。

只剩最后一个Lab了,可惜期中检查周来了,要还债了,还有新苗项目的报备,可能最后的一个Lab要咕好久了吧。(逃


本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!