Arpan Sen, 技术负责人, Synapti Computer Aided Design Pvt Ltd

简介：  代码的性能优化是一项非常重要的工作。经常可以看到，采用 C 或 C++ 编写的、功能正确的软件
在执行时耗费大量的内存、时间、或者在最糟的情况下既耗内存又费时间。作为一名开发人员，可以使用
C/C++ 提供的功能强大的工具来改进处理时间，并且防止内存破坏，这些工具其中之一是控制如何在代码
中分配或者释放内存。通过介绍如何针对特定的情况创建自己的内存管理器，本教程对内存管理的相关
概念进行了揭秘。

开始之前

了解本教程中包含的内容以及如何最好地利用本教程。

关于本教程

本教程采用了一种基本方法为任何应用程序构建内存管理器。本教程解释了为什么需要内存管理器，并提供
了为应用程序编写自定义的内存管理器（以满足特定的需求）的方法。

目标

在本教程中，您将了解在设计内存管理器之前需要考虑的一些注意事项、可用于创建这种内存管理器的一些
特定技术，并在文章的最后了解创建内存管理器的方法。您还将了解各种类型内存管理器设计的优点和不足
之处。

先决条件

本教程面向那些入门级到中级水平的 Linux® 或 UNIX® 程序员。您应该对使用 UNIX 命令行 Shell，
以及 C/C++ 语言的应用知识有基本的了解。此外，还需要了解 malloc、calloc、free、memcpy 和 
memset 等系统调用（即处理内存分配、释放和内容修改的例程）的内部工作方式。

系统要求

要运行本教程中的示例，您需要具备安装了 g++ 编译器工具链的 Linux 或者 UNIX 系统。还需要具有
足够大的 RAM（大约 256 MB）。

为什么要创建自定义的内存管理器呢？

要理解内存分配控制如何帮助提高代码的运行速度，首先需要回忆一下 C/C++ 中内存管理的基础知识。
C 中的标准库函数malloc、free、calloc 和 realloc，以及 C++ 中的 new、new [ ]、delete 和 delete
[ ] 操作符，是这两种语言中内存管理的关键之处。在了解了这一点之后，有几个内容值得注意。

如 malloc 和 new 函数是通用的内存分配器。您的代码可能是单线程的，但它所链接的 malloc 函数同样
可以处理多线程的范例。正是由于这个额外功能，使得这些例程的性能有所降低。

在执行时，malloc 和 new 将向操作系统内核请求内存，而 free 和 delete 则请求释放内存。这意味着，
操作系统必须在每次提出内存请求时在用户空间代码和内核代码之间进行切换。反复调用 malloc 或者
 new 的程序，最终将由于不断地进行上下文切换而导致运行缓慢。

对于在程序中分配的、并且以后不再需要使用的内存，常常会忘记对其进行删除，并且 C/C++ 并没有
提供自动的垃圾收集。这将导致程序的内存空间占用进一步增长。在实际的大型程序中，性能将受到显著
的影响，因为可用内存变得越来越少，并且硬盘访问是非常耗时的。

设计目标

您的内存管理器应该满足下面的设计目标：

• 速度
• 健壮性
• 用户使用便利性
• 可移植性

速度

与编译器提供的分配器相比，内存管理器的速度必须更快一些。重复的分配和释放不应该降低代码的执行
速度。如果可能的话，应该对内存管理器进行优化，以便处理代码中频繁出现的某些分配模式。

健壮性

在程序终止之前，内存管理器必须归还它向系统请求的所有内存。也就是说，不应该存在内存泄漏。它还
应该能够处理错误的情况（例如，请求过大的内存），并且很好地解决这些问题。

用户使用便利性

在将内存管理器集成到他们的代码中时，用户应该只需要更改很少的代码。

可移植性

应该可以很容易地将内存管理器移植到其它的系统，并且不应该使用与平台相关的内存管理特性。

创建内存管理器的实用策略

在创建内存管理器时，下面的这些策略是很实用的：

• 请求较大的内存块。
• 对常见的请求大小进行优化。
• 在容器中收集删除的内存。

请求较大的内存块

最常见的内存管理策略之一是，在程序启动期间请求一些较大的内存块，然后在代码执行期间反复地
使用它们。可以从这些内存块划出部分内存，以满足各种数据结构的内存分配请求。这将极大地减少
系统调用的次数，并提高执行性能。

对常见的请求大小进行优化

在任何程序中，某些特定的请求大小将比其它大小的请求更加常见。如果对您的内存管理器进行优化
以便更好地处理这些请求，那么它将工作得更加出色。

在容器中收集删除的内存

应该将程序执行期间删除的内存收集到容器中。然后，应该使用这些容器来满足进一步的内存请求。
如果某个请求失败，那么应该将内存访问委托给程序启动期间分配的某个较大的内存块。虽然内存
管理最初用于加速程序的执行和防止内存泄漏，但这种技术可能会潜在地导致程序的较低内存空间
占用，这是因为它可以重用删除的内存。这是编写您自己的内存分配器的另一个原因！

分析 C++ new/delete 操作符的执行时间

我们将从一个简单示例开始。假定您的代码使用了一个称为 Complex 的类（该类用于表示复数），
并且它使用了 new 和 delete 操作符所提供的机制，如清单 1 中所示。

外层循环的每次迭代都会导致 1000 次分配和释放。5000 次这样的迭代将导致 10 百万次用户和
内核代码之间的切换。在 Solaris 10 计算机中使用 gcc-3.4.6 进行编译之后，执行这个测试程序
平均需要花费 3.5 秒。这是编译器提供的全局 new 和 delete 操作符实现的基准性能度量。要为 
Complex 类创建自定义的内存管理器以改进编译器的实现，您需要重写 Complex 类特定的 new 和 
delete操作符。

New/Delete：深入研究

在 C++ 中，对内存管理进行组织实际上就是重载 new 或者 delete 操作符。代码中不同的类可能
需要使用不同的内存分配策略，这意味着每个类需要特定的 new。否则，必须重写 new 或者 delete 
全局操作符。可以采用这两种形式中的任何一种来实现操作符重载，如清单 2 中所示。

经过重写的 new 操作符负责分配第一个参数中指定大小的原始内存，而 delete 操作符则负责释放这
个内存。请注意，这些例程只用于分配或者释放内存；它们并不会分别调用构造函数或析构函数。对
于由 new 操作符分配的内存，将调用构造函数，而只有在调用了对象的析构函数后才调用 delete 操
作符。

new 的第二种变体是 placement new 操作符，它接受一个 MemoryManager 参数，该参数基本上是为某
个对象分配原始内存的数据结构,最后将调用这个对象的构造函数。对于本教程，我们建议使用 new 或
者 delete 的第一种变体，因为后一种变体将导致用户代码中 MemoryManager& 参数的大量增加，违反
了用户使用便利性的设计目标。

我们使用 MemoryManager 类，以便将 new 和 delete 操作符例程作为下面的 MemoryManager 例程的包装，
从而进行实际的内存分配或者释放，如清单 3 中所示： MemoryManager gMemoryManager;
// Memory Manager, global variable。

清单 3. 作为包装的 new、new[ ]、delete 和 delete[ ] 操作符

MemoryManager gMemoryManager; // Memory Manager, global variable

void* operator new (size_t size) 

  {

  return gMemoryManager.allocate(size);

  }

void* operator new[ ] (size_t size)

  {

  return  gMemoryManager.allocate(size);

  }

void operator delete (void* pointerToDelete)

  {

  gMemoryManager.free(pointerToDelete);

  }

void operator delete[ ] (void* arrayToDelete)

  {

  gMemoryManager.free(arrayToDelete);

  }      

注意：

• 传递给 new[ ] 操作符的 size 是数组每个元素的大小与数组元素个数相乘后所得的大小。
• 这个指针并不是在任何类特定的 new、delete、new[ ] 或者 delete[ ] 操作符中都可以
  使用。实际上，这四个例程都用作静态方法。您必须在设计过程中始终牢记这一点。
• 除了使用全局变量来声明内存管理器之外，您当然还可以使用一个单例。

根据到目前为止的介绍，清单 4 显示了内存管理器类的基本接口。

清单 4. 内存管理器接口

class IMemoryManager

  {

  public:

    virtual void* allocate(size_t) = 0;

    virtual void   free(void*) = 0;

  };

class MemoryManager : public IMemoryManager

  {

  public: 

    MemoryManager( );

    virtual ~MemoryManager( );

    virtual void* allocate(size_t);

    virtual void   free(void*);

  }; 

我们还倾向于将 allocate 和 free 例程作为内联例程，以便实现更快的分派。

单线程环境中 Complex 类型的第一个内存管理器

我们设计了本教程的第一个内存管理器，并始终牢记到目前为止已经介绍的那些原则。出于
简单的考虑，这个自定义的内存管理器专门用于 Complex 类型的对象，并且只能在单线程
环境中工作。其基本思想是，在可用的内存管理器中保存 Complex 对象池，并通过这个池来
完成以后的分配工作。如果需要创建的 Complex 对象的数目超过了该池中对象的数目，那么
将对该池进行扩展。删除的对象将归还到这个池中。图 1 很好地说明了所发生的事件。

图 1. 创建 Complex 对象的池
 

该池中的每个块具有两个用途：

• 它存储了一个 Complex 对象。
• 它必须能够将其自身连接到池中的下一个块。

没有选择在 Complex 数据结构中存储一个指针，因为这将增加设计的整体内存空间占用。相
比较而言，更好的方法是将 Complex 数据结构的私有变量包装到一个结构中，并将其与 Complex
 指针一起创建一个联合。当用作池中的一部分时，这个指针用于指向该池中的下一个空闲元素。
当用作独立 Complex 对象时，可以利用该结构来保存实数和复数部分。清单 5 显示了经过修改的
数据结构。

清单 5. 经过修改的数据结构，可以在不产生额外开销的情况下存储 Complex*

class Complex                     

  {

  public:

    Complex (double a, double b): r (a), c (b) {}

    private:

    union { 

      struct { 

        double r; // Real Part

        double c; // Complex Part

        };

      Complex* next;

    };

  };

然而，这个策略违反了用户使用便利性的设计目标，因为在集成内存管理器的时候，我们希望在
原始数据结构中进行最小限度的更改。为了对此进行改进，我们设计了一个新的 FreeStore 数据
结构，它是一个包装数据结构，在保存为池中的一部分时用作指针，否则用作 Complex 对象。
清单 6 显示了 FreeStore 对象的数据结构。

清单 6. FreeStore 对象的数据结构

struct FreeStore
{
   FreeStore* next;
};  

然后，该池成为 FreeStore 对象的链表，其中每一个都可以指向该池中的下一个元素，并且可以
用作一个 Complex 对象。MemoryManager 类必须保存一个指针，以指向这个空闲池第一个元素的头。
它应该提供一些用于在需要时扩展池大小的私有方法，以及在程序终止时清空内存的方法。清单 7 
包含了经过修改的 Complex 类的数据结构，从而提供 FreeStore 功能。

清单 7. 经过修改的 Complex 类数据结构，其中提供了 FreeStore 功能

#include <sys/types.h> 

class MemoryManager: public IMemoryManager 
  { 
  struct FreeStore
    {
     FreeStore *next;
    }; 
  void expandPoolSize ();
  void cleanUp ();
  FreeStore* freeStoreHead;
  public:
    MemoryManager () { 
      freeStoreHead = 0;
      expandPoolSize ();
      }
    virtual ~MemoryManager () { 
      cleanUp ();
      }
    virtual void* allocate(size_t);
    virtual void   free(void*);
  };

MemoryManager gMemoryManager;

class Complex 
  {
  public:
    Complex (double a, double b): r (a), c (b) {}
    inline void* operator new(size_t);
    inline void   operator delete(void*);
  private:
    double r; // Real Part
    double c; // Complex Part
  };    

下面是用于内存分配的伪代码：

1. 如果还没有创建空闲存储，那么创建空闲存储，然后跳转到步骤 3。
2. 如果空闲存储已经耗尽，则创建一个新的空闲存储。
3. 返回空闲存储的第一个元素，并且将空闲存储的下一个元素标记为空闲存储的头。

下面是用于内存删除的伪代码：

1. 让删除指针中的 next 域指向当前空闲存储的头。
2. 将删除指针标记为空闲存储的头。

清单 8 包含了 Complex 类的 new 和 delete 操作符的源代码。清单 9 显示了空闲存储的扩展和清理方法。
问题仍然存在。您能发现具体的问题吗？

清单 8. 用于 Complex 类的自定义内存分配或者释放

inline void* MemoryManager::allocate(size_t size)

  {

  if (0 == freeStoreHead)

    expandPoolSize ();

  FreeStore* head = freeStoreHead;

  freeStoreHead = head->next;

  return head;

  }

inline void MemoryManager::free(void* deleted)

  {

  FreeStore* head = static_cast <FreeStore*> (deleted);

  head->next = freeStoreHead;

  freeStoreHead = head;

  }

void* Complex::operator new (size_t size) 

  {

  return gMemoryManager.allocate(size);

  }

void Complex::operator delete (void* pointerToDelete)

  {

  gMemoryManager.free(pointerToDelete);

  }      

空闲存储的创建并不是那么简单。关键在于理解相同的 FreeStore* 指针还可以用来表示 Complex 对象。
因此，单个 FreeStore指针所需的大小必须是 FreeStore* 或者 Complex 中较大的一个，如清单 9 中所示。

清单 9. 扩展或者清空空闲存储的代码

#define POOLSIZE 32

void MemoryManager::expandPoolSize ()

  {

  size_t size = (sizeof(Complex) > sizeof(FreeStore*)) ?

    sizeof(Complex) : sizeof(FreeStore*);

  FreeStore* head = reinterpret_cast <FreeStore*> (new char[size]);

  freeStoreHead = head;

  for (int i = 0; i < POOLSIZE; i++) {

    head->next = reinterpret_cast <FreeStore*> (new char [size]);

    head = head->next;

    }

  head->next = 0;

  }

void MemoryManager::cleanUp()

  {

  FreeStore* nextPtr = freeStoreHead;

  for (; nextPtr; nextPtr = freeStoreHead) {

    freeStoreHead = freeStoreHead->next;

    delete [] nextPtr; // remember this was a char array

    }

  }      

大功告成！您已经为 Complex 类创建了自定义的内存管理器。记得基准测试花费了 3.5 秒。编译并
运行相同测试（不需要在主例程中对客户端代码进行任何更改），现在显示执行该程序只需要花费
0.67 秒！为什么存在这样显著的性能改进呢？主要有两个原因：

• 在用户和内核代码之间的切换数目明显减少，因为它通过将删除的内存收集回空闲存储来重用这些内存。
• 这个内存管理器是一个适合单线程执行的分配器。我们并不打算在多线程环境中运行这些代码。

之前，我们曾问您是否发现了设计中的问题。这个问题就是，如果没有删除使用 new 创建的 Complex 对象，
那么在这种设计中就没有办法回收丢失的内存。如果开发人员使用编译器提供的 new 和 delete 全局操作符，
那么情况也是相同的。然而，内存管理器不仅仅涉及性能改进，它还应该能够在设计中避免内存泄漏。对于
使用 new 创建的 Complex 对象进行显式删除的情况，cleanUp 例程仅仅将内存返回给操作系统。这个问题只
能通过从操作系统中请求更大的内存块（在程序初始化期间）、并对它们进行存储来加以解决。使用 Complex 
的 new 操作符从这些块中划出部分内存来响应内存的请求。cleanUp 例程在释放这些块时应该将其作为一个整
体，而不是从这些内存块中创建的单个对象。

有趣的说明

仍然使用全局 new 和 delete 操作符创建空闲存储的元素。然而，您也可以使用 malloc 和 free 的组合。在这
两种情况下，执行的平均时间基本相同。

 

位图内存管理器

可以在最初的固定大小内存分配方案基础上进行有趣的改进，即位图内存管理器。在这个方案中，向操作系统较
大的块进行内存请求，并且通过从这些块划出部分内存来实现内存的分配。通过将整个块作为一个整体来完成释
放操作，因而避免了任何潜在的泄漏。这种方法的另一个优点是，它可以支持 new 和 delete 操作的数组版本。

在这种方法中，内存管理器将请求较大的内存块。然后进一步将这个块划分为较小的、且大小固定的内存块。在
这种情况下，每个内存块的大小都与 Complex 对象的大小相等。根据这些块中内存块的数目，单独地维护一个位
图，以显示每个块的状态（空闲、或者已分配），并且位的数目与内存块的数目相等。当程序请求一个新的
 Complex 对象时，内存管理器将根据位图来获得一个空闲块。对于所有的空闲块，将其对应的位设置为 1。对于
已使用的块，则将它们对应的位设置为 0。要提供 new[ ] 和 delete[ ] 操作符，您需要维护一个辅助的数据结构，
以便在创建或者销毁 Complex 数组对象时帮助跟踪位图中有多少位需要设置为 1 或者 0。

创建一个位图内存管理器

内存管理器从操作系统中请求足够大的内存块。从这个块中划分出部分内存以进行稍后的内存分配。如果请求失败，
那么内存管理器将解决这个问题，并将合适的消息传递给用户，表示它已经退出。在这个阶段中，位图中的所有条
目都设置为 1。

如果内存管理器耗尽了空闲的内存块，那么它将向操作系统进一步请求较大的内存块。MemoryManager 数据结构中的
每个位图都可以用于增大对应的内存块。然而，在调用删除操作之后，用户可以使用对应的块。因此，非连续的删除
调用将导致所谓的分段的内存，并且可以从这个内存中提供适当大小的块。

清单 10 中给出了 MemoryManager 类的基本结构。它包含 MemoryPoolList，后者保存了从操作系统中请求的内存块的
起始地址。对于每个块，在 BitMapEntryList 中都存在一个相应的条目。FreeMapEntries 是一种数据结构，可以用来
为 new 调用的非数组版本提高下一个可用空闲块的搜索速度。

class MemoryManager : public IMemoryManager 
  {
    std::vector<void*> MemoryPoolList;
    std::vector<BitMapEntry> BitMapEntryList;
    //the above two lists will maintain one-to-one correspondence and hence 
    //should be of same  size.
    std::set<BitMapEntry*> FreeMapEntries;
    std::map<void*, ArrayMemoryInfo> ArrayMemoryList;

  private:
    void* AllocateArrayMemory(size_t size);
    void* AllocateChunkAndInitBitMap();
    void SetBlockBit(void* object, bool flag);
    void SetMultipleBlockBits(ArrayMemoryInfo* info, bool flag);
  public: 
    MemoryManager( ) {}
    ~MemoryManager( ) {}
    void* allocate(size_t);
    void   free(void*);
    std::vector<void*> GetMemoryPoolList(); 
  };      

ArrayMemoryList 保存了为 Complex 对象数组所分配的内存的相关信息。实际上，它是数组的起始地址到结构的映射，
以便维护MemPoolListIndex、位图中数组的 StartPosition 和数组的大小，如清单 11 中所示。

清单 12. BitMapEntry 类定义 
typedef struct BitMapEntry
  {
  int      Index;
  int      BlocksAvailable;
  int      BitMap[BIT_MAP_SIZE];
  public:
    BitMapEntry():BlocksAvailable(BIT_MAP_SIZE)
      {
      memset(BitMap,0xff,BIT_MAP_SIZE / sizeof(char)); 
      // initially all blocks are free and bit value 1 in the map denotes 
      // available block
      }
    void SetBit(int position, bool flag);
    void SetMultipleBits(int position, bool flag, int count);
    void SetRangeOfInt(int* element, int msb, int lsb, bool flag);
    Complex* FirstFreeBlock(size_t size);
    Complex* ComplexObjectAddress(int pos);
    void* Head();
  }
BitMapEntry;  

清单 14 中给出了为单个块设置或重置位的代码。

清单 14. MemoryManager::SetBlockBit 定义

void MemoryManager::SetBlockBit(void* object, bool flag)
  {
  int i = BitMapEntryList.size() - 1;
  for (; i >= 0 ; i--)
    {
    BitMapEntry* bitMap = &BitMapEntryList[i];
    if((bitMap->Head <= object )&amp;&amp; 
      (&(static_cast<Complex*>(bitMap->Head))[BIT_MAP_SIZE-1] >= object))
      {
      int position = static_cast<Complex*>(object) - 
      static_cast<Complex*>(bitMap->Head);
      bitMap->SetBit(position, flag);
      flag ? bitMap->BlocksAvailable++ : bitMap->BlocksAvailable--;
      }
    }
  }    

清单 15 中给出了为多个块设置或重置位的代码。

清单 15. MemoryManager::SetMultipleBlockBit 定义

void MemoryManager::SetMultipleBlockBits(ArrayMemoryInfo* info, bool flag)

  {

  BitMapEntry* mapEntry = &BitMapEntryList[info->MemPoolListIndex];

  mapEntry->SetMultipleBits(info->StartPosition, flag, info->Size);

  }

对于数组版本而言，处理方式有一点不同。用于数组的内存块与那些用于单个对象内存分配的
内存块分配自不同的内存块。这减少了在调用两种类型的 new 时搜索下一个空闲可用内存的开销。
内存管理器将查找 ArrayMemoryList 数据结构，以获取为数组提供内存的块的有关信息。当找到
时，它将获得这个块中的适当部分，将其地址提供给用户，并将相应的位设置为 0。如果出于某
种原因而导致操作失败，那么将从操作系统中请求一个新的块，并从中划分出部分内存。两种
new 调用的内存块作为 MemPoolList 的一部分存储在 MemoryManager 类中。

在调用 Complex 类型对象的指针的 delete、或者 free 的非数组版本的过程中，首先确定包含这
个指针的内存块（请参见清单 16）。然后，根据这个块的 BitMapEntry 将对应的位重置为 1，
从而使其成为可用的块。整个操作将花费 O(1) 时间。对于 delete []，从 ArrayMemoryList 中
检索相关信息，并且在已知起始位置和位图大小的情况下，将这些位标记为可用。

清单 16. MemoryManager::free 定义

void MemoryManager::free(void* object)

  {

  if(ArrayMemoryList.find(object) == ArrayMemoryList.end())

    SetBlockBit(object, true);         // simple block deletion 

  else

    {//memory block deletion

    ArrayMemoryInfo *info = &ArrayMemoryList[object];

    SetMultipleBlockBits(info, true);

    }

  }

 继承带来的问题

派生类的大小很可能会与其基类有很大的不同。例如，可以考虑 Complex 类的一个派生变体，
称为 ComplexT，它用于跟踪复数的值随时间变化的情况，其中包含一个附加的 unsigned long 用来存储时间。先前重写的 new 或者 delete 操作符现在将无法工作，除非我们专门针对这个
派生变体再次定义它们。对于这个问题，有三种可能的解决方案：

• 使用 MemoryManager 为这两个不同的类维护两个不同的池。实际上，这意味着分配/释
  放例程的两个变体，以及用来存储这两个池的头的两个指针。这种方式可能奏效，但
  可伸缩性受到限制。

• 根据最大的派生类大小维护一个池。allocate 例程始终返回最大派生类的大小，无论
  是基类、派生类层次中的哪个对象在请求内存。这样可以很好地解决问题，但它并不是
  一个非常有价值的方法，因为程序的内存空间占用将会增加。

• 为可变大小的分配创建通用的内存管理器。

基于空闲列表的内存管理器

在一个典型的程序中，内存块的大多数请求都是特定大小的。这个内存管理器将充分利用这个
特点。要实现这一点，您需要维护一些列表，其中包含这种大小的空闲块的地址。在技术行话
中，我们称这些列表为空闲列表。例如，可以考虑某个程序，它将提出 8、16、24、32、48
和 64 字节的内存请求。出于这个目的，内存管理器中包含六个不同的空闲列表，并请求从对
应的列表提供特定大小的内存。与位图内存管理器类似，在启动时从操作系统中请求内存，并
且内存管理器在内部将从操作系统请求的块划分到各个列表中。在用户为某个对象请求内存时，
比如“m”个字节，那么会将对象的大小转换为最接近的块大小“n”，并且存在一个空闲列表用来
存储大小为“n”的块。

 有关保护字节（guard bytes）的简单介绍

“n”字节的块不仅存储了对象，还存储了一些元数据信息。每个块的末尾附近都包含四个额外的
字节，其中包含在堆内存操作范例中称为保护字节 的内容。通常，memcpy 和 memset 函数可以
访问所分配内存的界限之外的内存字节。这将导致堆内存的破坏。许多编译器都为所分配的 mem
 块添加了一些特殊字符，以充当该块的哨兵（或者保护字节）。对于所分配内存的这些块所进行
的任何访问，都将检查所分配的块附近的特殊字符。如果找不到这些字符，那么将认为在程序执
行期间以非法的方式更改了它们的值，这暗示堆内存不再处于有序的状态，并且因此受到了破坏。
通过这种机制，程序员可以捕获一些所了解的内存错误。在下面的示例中，这四个字节中的其中
两个充当了保护字节，第三个字节用于存储这个对象的大小，最后一个字节存储了一个标志，表
示这个对象是否可用、或者已经被占用。

 创建一个空闲列表内存管理器

如前所述，内存管理器维护了一些指针的列表，这些指针指向可变大小的块。它还对从操作系统
请求而来的内存块进行维护，并作为memoryPool。在 MemoryManager 调用其析构函数时，这个池
可以用于释放整个内存块。清单 17 显示了该数据结构。

清单 17. 基于空闲列表实现的 MemoryManager 类定义

class MemoryManager : public IMemoryManager 

  {

  private:

    VoidPtrList     Byte8PtrList;

    VoidPtrList     Byte16PtrList;

    VoidPtrList     Byte24PtrList;

    VoidPtrList     Byte32PtrList;

    VoidPtrList     Byte40PtrList;

    std::vector<void*>    MemoryPoolList;

    . . . . . . . . . //helper routines may go in here

  public: 

    MemoryManager( ) {}

    ~MemoryManager( ) {}

    void* allocate(size_t);

    void   free(void*);

我们的示例使用了大小为 16、28 和 32 字节的三个类，因而需要大小为 24、32和40
个字节的块来保存它们的保护字节。因此，Byte24PtrList、Byte32PtrList 和
 Byte40PtrList 的使用最为频繁，并且代码也主要是和它们相关的。然而，设计相当
灵活，也可以用于添加您所希望的其他大小的列表。

为这些类重载了操作符 new 和 delete，它们将调用委派给负责内存分配和释放的 
allocate 和 free 例程。下面将详细地介绍这些例程。我们使用了大小为 1024 的
块作为对象的初始计数。另外，将示例中使用的每个类的大小作为预定义的常数进
行了存储，如清单 18 中所示。

清单 18. 这个实现中所使用的预定义常数

const int JOB_SCHEDULER_SIZE = sizeof(JobScheduler);

const int COMPLEX_SIZE = sizeof(Complex);

const int COORDINATE_SIZE = sizeof(Coordinate);

const int POOL_SIZE = 1024; //number of elements in a single pool

//can be chosen based on application requirements 

const int MAX_BLOCK_SIZE = 36; //depending on the application it may change 

//In above case it came as 36

在 allocate 和 free 例程中使用了这些常数。

allocate 例程

对于给定大小的块，allocate 例程将确定使用内存管理器中的哪个列表。它将查找
必需的列表，以查看是否存在可用的块。请注意，这个列表仅存储了指向该块的指
针，而不是块本身（该块是 MemoryPoolList 的一部分）。

如果空闲列表是空的，那么将从操作系统中请求附加的内存块，并由
InitialiseByte24List、InitialiseByte32List 和InitialiseByte40List 
例程将其组织为分区块。

当存在某个空闲块地址可供使用时，将对应的块标记为不可使用，设置其保护字节，
并且返回该块的地址。可以考虑如清单 19 中所示的实现。

清单 19. MemoryManager::allocate 定义

void* MemoryManager::allocate(size_t size)
 {
  void* base = 0;

  switch(size)

    {

    case JOB_SCHEDULER_SIZE :  

      {

      if(Byte32PtrList.empty())

        {

        base = new char [32 * POOL_SIZE];

        MemoryPoolList.push_back(base);

        InitialiseByte32List(base);

        }

      void* blockPtr =  Byte32PtrList.front();

      *((static_cast<char*>(blockPtr)) + 30) = 32; //size of block set

      *((static_cast<char*>(blockPtr)) + 31) = 0; //block is no longer free

      Byte32PtrList.pop_front();

      return blockPtr;

      }         

    case COORDINATE_SIZE :  

      {

      if(Byte40PtrList.empty())

        {

        base = new char [40 * POOL_SIZE];

        MemoryPoolList.push_back(base);

        InitialiseByte40List(base);

        }

      void* blockPtr =  Byte40PtrList.front();

      *((static_cast<char*>(blockPtr)) + 38) = 40; //size of block set

      *((static_cast<char*>(blockPtr)) + 39) = 0; //block is no longer free

      Byte40PtrList.pop_front();

      return blockPtr;

      }         

    case COMPLEX_SIZE : 

      {

      if(Byte24PtrList.empty())

        {

        base = new char [24 * POOL_SIZE];

        MemoryPoolList.push_back(base);

        InitialiseByte24List(base);

        }

      void* blockPtr =  Byte24PtrList.front();

      *((static_cast<char*>(blockPtr)) + 22) = 24; //size of block set

      *((static_cast<char*>(blockPtr)) + 23) = 0; //block is no longer free

      Byte24PtrList.pop_front();

      return blockPtr;

      }

    default : break;

    }

  return 0;

  }

free 例程接收块的地址，并搜索位于块末尾的、包含大小信息的字节（在保护字节中）。它是
块中的倒数第二个字节。在获得这个大小之后，将对象标记为可用（将最后一个字节设置为 1），
并获取对应的列表。然后，将该对象加入空闲 列表中，这也标志着完成了删除操作。可以考虑
清单 20 中的实现。

清单 20. MemoryManager::free 定义
void MemoryManager::free(void* object)

  {

  char* init = static_cast<char*>(object);

   while(1)

    {

    int count = 0;

    while(*init != static_cast<char>(0xde))  

          //this loop shall never iterate more than 

      {                 // MAX_BLOCK_SIZE times and hence is O(1)

      init++;

      if(count > MAX_BLOCK_SIZE)

        {

        printf ("runtime heap memory corruption near %d", object);

        exit(1);

        } 

      count++; 

      }

    if(*(++init) == static_cast<char>(0xad))  // we have hit the guard bytes

      break;  // from the outer while 

    }

  init++;

  int blockSize = static_cast<int>(*init);

  switch(blockSize)

    {

    case 24: Byte24PtrList.push_front(object); break;

    case 32: Byte32PtrList.push_front(object); break;

    case 40: Byte40PtrList.push_front(object); break;

    default: break;

    }

  init++;

  *init = 1; // set free/available byte   

优点和不足之处

这个设计有下面几个优点：

• 可以很好地处理可变大小的内存分配。

• 设计灵活，并且可以通过确定每个软件所需的列表大小来进行扩展。

• 添加保护字节的能力允许为对象存储大量元数据信息。我们已经将它
  用于确定运行时堆内存的破坏情况。

虽然这个设计可以显著地改善性能，但它仍然存在不足之处，即它需要大量的内存。

 多线程内存管理器

到目前为止，我们所创建的内存管理器并没有考虑到并发的环境。在多线程环境中，
可能会有多个线程同时尝试进行内存的分配和释放。这意味着，我们必须确保在内
存管理器中进行的分配和释放操作都是具有原子性的。也就是说，在两个线程同时
尝试这些操作时，我们必须在这两个线程之间提供一种互斥的机制。要确保分配和
释放操作具有原子性，标准的方法是使用一种基于锁的机制。当一个线程调用这两
种方法其中之一时，在它实际获得对内存的访问或者释放内存之前，必须获得一个
独占锁。如果该锁由另一个线程所拥有，那么将阻塞当前线程，直到它拥有这个锁
为止。清单 21 说明了用作锁定机制的函数签名。

清单 21. pthread mutex 方法

#include <pthread.h>

int pthread_mutex_init(pthread_mutex_t *mutex, 

const pthread_mutexattr_t *attr);

int pthread_mutex_destroy(pthread_mutex_t *mutex);

pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;

int pthread_mutex_lock(pthread_mutex_t *mutex);

int pthread_mutex_trylock(pthread_mutex_t *mutex);

int pthread_mutex_unlock(pthread_mutex_t *mutex);   

 就本文而言，我们使用了标准 Header pthread.h 中定义的 pthread mutexes，GNU
 编译器在安装时就提供了这个 Header，以便模拟锁定或者解锁机制。allocation 和 
free 例程中的代码位于 pthread_mutex_lock 和 pthread_mutex_unlock 方法之间。
如果某个线程正在访问内存池时，又有另一个线程调用了这些例程其中之一，那么它
必须等待，直到该锁可用为止。清单 22 是该方法的经过修改的代码片段。

清单 22. 分配和释放方法的并发版本

void* MemoryManager::allocate(size_t size) 

  {

  pthread_mutex_lock (&lock); 

  ... // usual memory allocation code

  pthread_mutex_unlock (&lock);

  }

void* MemoryManager::free(size_t size) 

  {

  pthread_mutex_lock (&lock); 

  ... // usual memory deallocation code

  pthread_mutex_unlock (&lock);

现在，内存管理器类需要包括一个 pthread_mutex_lock 对象。需要修改类构造函数，
以便调用 pthread_mutex_init 初始化锁，并且类析构函数必须调用 pthread_mutex_destroy 
以销毁 mutex 对象。清单 23 是 MemoryManager 类的修改之后的代码。

清单 23. 经过修改的 MemoryManager 类，以处理多线程的分配和释放

class MemoryManager : public IMemoryManager 

  { 

  pthread_mutex_t lock;

  ... // usual MemoryManager code follows

  };

MemoryManager::MemoryManager () 

  {

  pthread_mutex_init (&lock, NULL);

  ... // usual constructor code 

  }

MemoryManager:: ~MemoryManager () 

  {

  ... // usual destructor code 

  pthread_mutex_destroy (&lock);

现在，运行内存管理器的多线程版本。在我们的测试中，与单线程版本相比，它的运行要慢
得多，这说明了为什么需要提供专用的、自定义的内存管理器。

总结

本教程解释了下面的几个概念：

• 在用户代码中使用内存管理器的需求。
• 内存管理器的设计需求。
• 如何创建固定大小的分配器或者内存管理器。
• 如何创建可变大小的分配器。
• 多线程环境中的内存分配。

有关这个主题的更多信息，请参见参考资料部分。

下载

参考资料

学习

• 内存管理参考资料：这个 Ravenbrook Web 站点提供了内存管理方面的介绍。
  
  
• “内存分配器”（Doug Lea）：其中讨论了各种技术和算法。
  
  
• “内存管理内幕”：这篇文章提供了有关内存管理技术的概述，Linux 程序员可以充分地利用这些技术。
  
  
• AIX and UNIX 专区：developerWorks 的“AIX and UNIX 专区”提供了大量与 AIX 系统管理的所有方面相关的信息，
  您可以利用它们来扩展自己的 UNIX 技能。
  
  
• AIX and UNIX 新手入门：访问“AIX and UNIX 新手入门”页面可了解更多关于 AIX 和 UNIX 的内容。
  
  
• Safari 书店：访问这个电子参考资料库，以查找特定的技术参考资料。
  
  
• developerWorks 技术事件和网络广播：了解最新的 developerWorks 技术事件和网络广播。