C++复习转载部分

分析高效内存池的实现方式

2018-06-06  本文已影响34人  凉拌姨妈好吃

1. 内存池的目的

为什么会产生内存碎片？
1.内部碎片是采用固定大小的内存分区，当一个进程不能完全使用分配给它的固定内存分区时，就会产生内存碎片。
2.外部碎片是由于可分配的连续内存太小，不能满足任何进程的需求，从而不能被进程使用。

再扯一个概念：段页式内存分配方式
将进程的内存区域分成不同的段，段由多个固定大小的页组成。那么通过页表机制，段内的页就不需要存储在同一块内存区域。

段页式内存分配方式

默认内存管理
当我们调用new在堆上分配一些内存的时候，系统收到了分配内存的请求，就会根据一定的算法在空闲内存块里寻找适合该内存大小的内存块。如果内存块过大，就会将内存块分割成适合的内存块。释放内存块后，内存块就会重新被放入空闲内存块中。默认内存管理里还用到了多线程的应用，每次分配和释放内存的时候都需要加锁，这样就损耗了性能。

可见，如果应用程序频繁地在堆上分配和释放内存，则会导致性能的损失，并且会使系统中出现大量的内存碎片，降低内存的利用率

2. 内存池的定义和分类

2.1 定义

顾名思义，我们在系统申请一块适合的内存作为内存池，应用程序对内存的分配和释放都在这个内存池里实现，只有当内存池不够大需要动态扩增的时候才会调用系统的分配内存函数，其他时间对内存的一切操作都是用应用程序控制的。

2.2 分类

从线程安全角度看，有多线程内存池和单线程内存池。
从内存池可分配大小来看，有固定大小内存池(在这里的固定指的是每一次和系统申请的内存的大小都是固定的，而不是这个内存池大小只能那么大)和可变内存池

3. 固定内存池

3.1 固定内存池的简要理解

固定内存池由一系列固定大小的内存块组成，每一个内存块里又包含了固定数量和大小的内存单元。其实在内存池初次生成的时候，我们只是向系统申请了一块内存块，返回一个指针作为整个内存池的头指针。后面随着内存池的不断扩大，我们通过指针将内存池连接在一起。

因为每一次系统都是分配固定大小的内存，所以系统的分配效率高。

固定内存池

固定内存池就像一个链表一样，将内存块一个一个联系到一起。
当我们要需要一个内存单元的时候，就会随着链表去查看每一个内存块的头信息，如果内存块里有空闲的内存单元，将该地址返回，并且将头信息里的空闲单元改成下一个空闲单元。
当应用程序释放某内存单元，就会到对应的内存块的头信息里修改该内存单元为空闲单元。

3.2 固定内存池的优点（性能优化方面）
  1. 内存池中的内存块大小相等，所以在分配的时候不需要太复杂的算法和多线程的保护，也减少了维护系统空闲内存表的开销。
  2. 单个内存池块是连续的内存空间，提升了程序性能。
  3. 申请的内存块大小相等，有利于控制页边界对齐和内存对齐。
3.3 固定内存池的实现
3.3.1 MemoryPool和MemoryBlock声明
class MemoryPool
{
private:
    MemoryBlock*   pBlock;
    USHORT          nUnitSize;
    USHORT          nInitSize;
    USHORT          nGrowSize;

public:
                     MemoryPool( USHORT nUnitSize,
                                  USHORT nInitSize = 1024,
                                  USHORT nGrowSize = 256 );
                    ~MemoryPool();

    void*           Alloc();
    void            Free( void* p );
};

struct MemoryBlock
{
    USHORT          nSize;
    USHORT          nFree;
    USHORT          nFirst;
    USHORT          nDummyAlign1;
    MemoryBlock*  pNext;
    char            aData[1];

    static void* operator new(size_t, USHORT nTypes, USHORT nUnitSize)
    {
        return ::operator new(sizeof(MemoryBlock) + nTypes * nUnitSize);
    }
    static void  operator delete(void *p, size_t)
    {
        ::operator delete (p);
    }

    MemoryBlock (USHORT nTypes = 1, USHORT nUnitSize = 0);
    ~MemoryBlock() {}
};
3.3.2 该内存池总体机制的理解

  1. 有一个MemoryPool类作为内存池，它拥有一个指向第一个MemoryBlock的头指针。当我们有许多内存块的时候，一个内存块由pNext指针指向下一个内存块。

  2. 内存块由内存块结构体与内存单元构成，这些内存单元的大小固定（在这里用nSize表示），MemoryBlock结构体不维护那些已经分配的内存单元的信息，它的nFree成员记录未分配内存单元的数量，nFirst记录第一个未分配的内存单元的编号，每个内存单元编号的前两个字节记录了紧跟它的下一个内存单元的编号，这样内存单元就一个个被链接起来。

  3. 当有新的内存请求时，内存池会使用pBlock去遍历内存块，查找内存块中nFree大于0的内存块，找到了对应的内存块后，我们再根据nFirst找到第一个空闲的内存单元，在返回这个内存单元的地址之前，将nFirst的值改为取到的内存单元的前两个字节的值（也就是它的下一个内存单元），再将nFree减1，最后才将刚才定位到的内存地址返回给调用者。

  4. 如果现有内存块找不到空闲内存单元，MemoryPool就会从堆上申请分配一个内存块，立即进行初始化（nSize为所有内存单元的大小，nFree为n-1，因为立马要分配一个空闲单元，所以就先减1，nFirst为1，因为为0的马上就要分配出去了），MemoryBlock的构造函数主要的作用是将编号为0之后的内存单元链接在一起。因为每个内存单元大小固定（为MemoryPool的nUnitSize），所以要定位到内存单元就通过它的头两位与内存单元大小的乘积作为偏移值进行定位。那么定位要从哪个地方开始呢？思考一下我们的aData[1]的作用，它是MemoryBlock结构体的最后一个字节。所以实质上，MemoryBlock结构体的最后一个字节也用做被分配出去的分配单元的一部分。因为整个内存块由MemoryBlock结构体和整数个分配单元组成，这意味着内存块的最后一个字节会被浪费。所以我们可以从aData[1]的位置开始，每个nUnitSize大小取其头两字节，记录它后面自由单元的序号。因为刚开始所有分配单元都是自由的，所以这个编号就是自身编号加1，即位置上紧跟其后的单元的编号。

  5. 当内存被释放的时候，内存重新回到内存池。MemoryPool根据内存单元的地址遍历所有内存块，判断该内存单元是否在内存块的范围内。注意重新加回去的时候，MemoryBlock的nFree+1，nFirst可能会改变。如果这个内存块内都是空闲的，那么就会将它返回给堆。因为这个内存单元被放入内存块，那么证明这个内存块一定有空闲空间，所以我们将头指针指向该内存块，方便下一次查找。

3.3.3 细节剖析
MemoryPool的构造函数

每个分配单元在自由状态时，其头两个字节用来存放"其下一个自由分配单元的编号"。即每个分配单元"最少"有"两个字节"，这就是⑤处赋值的原因。④处是将大于4个字节的大小_nUnitSize往上"取整到"大于nUnitSize的最小的MEMPOOL ALIGNMENT的倍数（前提是MEMPOOL_ALIGNMENT为2的倍数）。如_nUnitSize为11时，MEMPOOL_ALIGNMENT为8，nUnitSize为16；MEMPOOL_ALIGNMENT为4，nUnitSize为12；

当向MemoryPool提出内存请求时：

void* MemoryPool::Alloc()
{
    if ( !pBlock )           //1
    {
            ……                          
    }

    MemoryBlock* pMyBlock = pBlock;
    while (pMyBlock && !pMyBlock->nFree )//2
        pMyBlock = pMyBlock->pNext;

    if ( pMyBlock )         //3
    {
        char* pFree = pMyBlock->aData+(pMyBlock->nFirst*nUnitSize);         
        pMyBlock->nFirst = *((USHORT*)pFree);
                            
        pMyBlock->nFree--;  
        return (void*)pFree;
    }
    else                    //4
    {
        if ( !nGrowSize )
            return NULL;

        pMyBlock = new(nGrowSize, nUnitSize) FixedMemBlock(nGrowSize, nUnitSize);
        if ( !pMyBlock )
            return NULL;

        pMyBlock->pNext = pBlock;
        pBlock = pMyBlock;

        return (void*)(pMyBlock->aData);
    }

}

MemoryPool回收内存时：

void MemoryPool::Free( void* pFree )
{
    ……

    MemoryBlock* pMyBlock = pBlock;

    while ( ((ULONG)pMyBlock->aData > (ULONG)pFree) ||
         ((ULONG)pFree >= ((ULONG)pMyBlock->aData + pMyBlock->nSize)) )//1
    {
         ……
    }

    pMyBlock->nFree++;                    //2
    *((USHORT*)pFree) = pMyBlock->nFirst;  //3
    pMyBlock->nFirst = (USHORT)(((ULONG)pFree-(ULONG)(pBlock->aData)) / nUnitSize);//4

    if (pMyBlock->nFree*nUnitSize == pMyBlock->nSize )//5
    {
        ……
    }
    else
    {
        ……
    }
}

一个分配单元的内存地址无论是在分配后，还是处于自由状态时，一直都不会变化。变化的只是其状态（已分配/自由），以及当其处于自由状态时在自由分配单元链表中的位置。

参考：
内存池技术介绍（图文并茂，非常清楚）
C++ 实现高性能内存池
极高效内存池实现 (cpu-cache)
固定大小块的内存池设计

上一篇下一篇

猜你喜欢

热点阅读