大海啊，你全是水。

     骏马啊，你四条腿。

                                  --------------题记

MM1.0 中可能会存在哪些问题呢？

如果系统中请求的块具有相同的大小，那么MM1.0 完全可以满足用户的需求。但是在实际的应用中，这中情况是极少的，一般会混杂大小不同的内存请求。这就会产生两个问题：

1.      在链表中查找满足请求大小的空闲块可能花费大量的时间。

2.      当前程序只有分割，没有合并。如果程序运行时间较长，容易产生内存碎片。这时即使内存中有足够大的连续空闲内存，但是系统中记录的是零碎的空闲内存块，从而无法满足请求。

针对以上问题，我们应该如何加以改进呢？

1.      如何能够快速检索出具有特定大小的空闲内存块呢？

极端的方案是针对每一个块大小都建立一个空闲链表。如果要查找相应大小的空闲块，只要到相应的空闲链表中查找就好了。如果该大小的空闲链表为空，则到更大块对应的空闲链表中查找，直到满足条件未知。

2.      如何能够合并相邻的空闲内存块呢？

为了能够合并相邻内存块，有两个问题需要解决:

1. 如何能够检索到相邻内存块？ 2. 如何知道相邻内存块是否空闲？

由于Chunk是连续分布的，并且Chunk描述符总是位于内存块之前，因此只要知道了前面内存块的大小即可知道前面块的Chunk描述符的地址了。--à 问题1解决。

每一个Chunk可以增加一个Flag来记录当前Chunk是否为空闲块。--à 问题2解决。

改进后的伪代码如下所示：

//----------------------------------------

struct Chuck

{

    Chunk * next;

    size_t size;

    size_t preSize;

    int flag;

};

Chunk * bin[*****]; // 针对每种大小都要建立一个空闲链表

void * malloc(size_t size)

{

    for ( size_t start = size; ; start++)

    {

        Chunk * victim = bin[start];

        if (victim)

        {

            erase(victim); //将当前空闲内存块从空闲链表中删除

            return victim + 1;

        }

     }

}

void free(void * add)

{

    Chunk * idle = ((Chunk *)add) - 1;

    Chunk * pre = (Chunk * )((((char *)idle) + idle->preSize)) - 1;

    Chunk * next = (Chunk * )((((char *)idle) + idle->size)) + 1;

    if ( pre->flag & CHUNK_IDLE)

    {

        erase(pre);

        idle = merge(pre, idle);

    }

    if ( next & CHUNK_IDLE)

    {

        erase(next);

        idle = merge(idle, next);

    }

    insert(idle);   //根据idle的大小将其插入到合适的空闲链表中

}

//----------------------------------------

哈哈，如此一来，我们的MM2.0 也已经OK了。

相对于MM1.0 它的功能更加强大:

1. 更快地检索空闲块。

2. 在一定程度上避免了内存碎片。

但是MM2.0 中也存在一定的问题，例如建立了太多的空闲链表等等。

这些问题我们又应该如何解决呢？