* 它没有实现很多其他的内存函数，比如 realloc()。
    * 由于 sbrk() 可能会交回比我们请求的更多的内存，所以在堆（heap）的末端会遗漏一些内存。
    * 虽然 is_available 标记只包含一位信息，但它要使用完整的 4-字节 的字。
    * 分配程序不是线程安全的。
    * 分配程序不能将空闲空间拼合为更大的内存块。
    * 分配程序的过于简单的匹配算法会导致产生很多潜在的内存碎片。
    * 我确信还有很多其他问题。这就是为什么它只是一个例子!

其他 malloc 实现
malloc() 的实现有很多，这些实现各有优点与缺点。在设计一个分配程序时，要面临许多需要折衷的选择，其中包括：

    * 分配的速度。
    * 回收的速度。
    * 有线程的环境的行为。
    * 内存将要被用光时的行为。
    * 局部缓存。
    * 簿记（Bookkeeping）内存开销。
    * 虚拟内存环境中的行为。
    * 小的或者大的对象。
    * 实时保证。

每一个实现都有其自身的优缺点集合。在我们的简单的分配程序中，分配非常慢，而回收非常快。另外，由于它在使用虚拟内存系统方面较差，所以它最适于处理大的对象。

还有其他许多分配程序可以使用。其中包括：

    * Doug Lea Malloc：Doug Lea Malloc 实际上是完整的一组分配程序，其中包括 Doug Lea 的原始分配程序，GNU libc 分配程序和 ptmalloc。 Doug Lea 的分配程序有着与我们的版本非常类似的基本结构，但是它加入了索引，这使得搜索速度更快，并且可以将多个没有被使用的块组合为一个大的块。它还支持缓存，以便更快地再次使用最近释放的内存。ptmalloc 是 Doug Lea Malloc 的一个扩展版本，支持多线程。在本文后面的参考资料部分中，有一篇描述 Doug Lea 的 Malloc 实现的文章。
    * BSD Malloc：BSD Malloc 是随 4.2 BSD 发行的实现，包含在 FreeBSD 之中，这个分配程序可以从预先确实大小的对象构成的池中分配对象。它有一些用于对象大小的 size 类，这些对象的大小为 2 的若干次幂减去某一常数。所以，如果您请求给定大小的一个对象，它就简单地分配一个与之匹配的 size 类。这样就提供了一个快速的实现，但是可能会浪费内存。在参考资料部分中，有一篇描述该实现的文章。
    * Hoard：编写 Hoard 的目标是使内存分配在多线程环境中进行得非常快。因此，它的构造以锁的使用为中心，从而使所有进程不必等待分配内存。它可以显著地加快那些进行很多分配和回收的多线程进程的速度。在参考资料部分中，有一篇描述该实现的文章。

众多可用的分配程序中最有名的就是上述这些分配程序。如果您的程序有特别的分配需求，那么您可能更愿意编写一个定制的能匹配您的程序内存分配方式的分配程序。不过，如果不熟悉分配程序的设计，那么定制分配程序通常会带来比它们解决的问题更多的问题。要获得关于该主题的适当的介绍，请参阅 Donald Knuth 撰写的 The Art of Computer Programming Volume 1: Fundamental Algorithms 中的第 2.5 节"Dynamic Storage Allocation"（请参阅参考资料中的链接）。它有点过时，因为它没有考虑虚拟内存环境，不过大部分算法都是基于前面给出的函数。

在 C++ 中，通过重载 operator new()，您可以以每个类或者每个模板为单位实现自己的分配程序。在 Andrei Alexandrescu 撰写的 Modern C++ Design 的第 4 章（"Small Object Allocation"）中，描述了一个小对象分配程序（请参阅参考资料中的链接）。

基于 malloc() 的内存管理的缺点
不只是我们的内存管理器有缺点，基于 malloc() 的内存管理器仍然也有很多缺点，不管您使用的是哪个分配程序。对于那些需要保持长期存储的程序使用 malloc() 来管理内存可能会非常令人失望。如果您有大量的不固定的内存引用，经常难以知道它们何时被释放。生存期局限于当前函数的内存非常容易管理，但是对于生存期超出该范围的内存来说，管理内存则困难得多。而且，关于内存管理是由进行调用的程序还是由被调用的函数来负责这一问题，很多 API 都不是很明确。


因为管理内存的问题，很多程序倾向于使用它们自己的内存管理规则。C++ 的异常处理使得这项任务更成问题。有时好像致力于管理内存分配和清理的代码比实际完成计算任务的代码还要多！因此，我们将研究内存管理的其他选择。

半自动内存管理策略

引用计数
引用计数是一种半自动（semi-automated）的内存管理技术，这表示它需要一些编程支持，但是它不需要您确切知道某一对象何时不再被使用。引用计数机制为您完成内存管理任务。

在引用计数中，所有共享的数据结构都有一个域来包含当前活动"引用"结构的次数。当向一个程序传递一个指向某个数据结构指针时，该程序会将引用计数增加 1。实质上，您是在告诉数据结构，它正在被存储在多少个位置上。然后，当您的进程完成对它的使用后，该程序就会将引用计数减少 1。结束这个动作之后，它还会检查计数是否已经减到零。如果是，那么它将释放内存。

这样做的好处是，您不必追踪程序中某个给定的数据结构可能会遵循的每一条路径。每次对其局部的引用，都将导致计数的适当增加或减少。这样可以防止在使用数据结构时释放该结构。不过，当您使用某个采用引用计数的数据结构时，您必须记得运行引用计数函数。另外，内置函数和第三方的库不会知道或者可以使用您的引用计数机制。引用计数也难以处理发生循环引用的数据结构。

要实现引用计数，您只需要两个函数 —— 一个增加引用计数，一个减少引用计数并当计数减少到零时释放内存。

一个示例引用计数函数集可能看起来如下所示：
清单 9. 基本的引用计数函数


/* Structure Definitions*/

/* Base structure that holds a refcount */

struct refcountedstruct

{

int refcount;

}

/* All refcounted structures must mirror struct
 * refcountedstruct for their first variables
 */

/* Refcount maintenance functions */

/* Increase reference count */

void REF(void *data)

{

struct refcountedstruct *rstruct;

rstruct = (struct refcountedstruct *) data;

rstruct->refcount++;

}

/* Decrease reference count */

void UNREF(void *data)

{

struct refcountedstruct *rstruct;

rstruct = (struct refcountedstruct *) data;

rstruct->refcount--;

/* Free the structure if there are no more users */

if(rstruct->refcount == 0)

{

free(rstruct);

}

}

REF 和 UNREF 可能会更复杂，这取决于您想要做的事情。例如，您可能想要为多线程程序增加锁，那么您可能想扩展 refcountedstruct，使它同样包含一个指向某个在释放内存之前要调用的函数的指针（类似于面向对象语言中的析构函数 —— 如果您的结构中包含这些指针，那么这是必需的）。

当使用 REF 和 UNREF 时，您需要遵守这些指针的分配规则：

    * UNREF 分配前左端指针（left-hand-side pointer）指向的值。
    * REF 分配后左端指针（left-hand-side pointer）指向的值。

在传递使用引用计数的结构的函数中，函数需要遵循以下这些规则：

    * 在函数的起始处 REF 每一个指针。
    * 在函数的结束处 UNREF 第一个指针。

以下是一个使用引用计数的生动的代码示例：
清单 10. 使用引用计数的示例


/* EXAMPLES OF USAGE */


/* Data type to be refcounted */

struct mydata

{

int refcount; /* same as refcountedstruct */

int datafield1; /* Fields specific to this struct */

int datafield2;

/* other declarations would go here as appropriate */

};


/* Use the functions in code */

void dosomething(struct mydata *data)

{

REF(data);



/* Process data */

/* when we are through */

UNREF(data);

}


struct mydata *globalvar1;

/* Note that in this one, we don't decrease the
 * refcount since we are maintaining the reference
 * past the end of the function call through the
 * global variable
 */

void storesomething(struct mydata *data)

{

REF(data); /* passed as a parameter */

globalvar1 = data;

REF(data); /* ref because of Assignment */

UNREF(data); /* Function finished */

}

由于引用计数是如此简单，大部分程序员都自已去实现它，而不是使用库。不过，它们依赖于 malloc 和 free 等低层的分配程序来实际地分配和释放它们的内存。

在 Perl 等高级语言中，进行内存管理时使用引用计数非常广泛。在这些语言中，引用计数由语言自动地处理，所以您根本不必担心它，除非要编写扩展模块。由于所有内容都必须进行引用计数，所以这会对速度产生一些影响，但它极大地提高了编程的安全性和方便性。以下是引用计数的益处：

    * 实现简单。
    * 易于使用。
    * 由于引用是数据结构的一部分，所以它有一个好的缓存位置。

不过，它也有其不足之处：

    * 要求您永远不要忘记调用引用计数函数。
    * 无法释放作为循环数据结构的一部分的结构。
    * 减缓几乎每一个指针的分配。
    * 尽管所使用的对象采用了引用计数，但是当使用异常处理（比如 try 或 setjmp()/longjmp()）时，您必须采取其他方法。
    * 需要额外的内存来处理引用。
    * 引用计数占用了结构中的第一个位置，在大部分机器中最快可以访问到的就是这个位置。
    * 在多线程环境中更慢也更难以使用。

C++ 可以通过使用智能指针（smart pointers）来容忍程序员所犯的一些错误，智能指针可以为您处理引用计数等指针处理细节。不过，如果不得不使用任何先前的不能处理智能指针的代码（比如对 C 库的联接），实际上，使用它们的后果通实比不使用它们更为困难和复杂。因此，它通常只是有益于纯 C++ 项目。如果您想使用智能指针，那么您实在应该去阅读 Alexandrescu 撰写的 Modern C++ Design 一书中的"Smart Pointers"那一章。

内存池
内存池是另一种半自动内存管理方法。内存池帮助某些程序进行自动内存管理，这些程序会经历一些特定的阶段，而且每个阶段中都有分配给进程的特定阶段的内存。例如，很多网络服务器进程都会分配很多针对每个连接的内存 —— 内存的最大生存期限为当前连接的存在期。Apache 使用了池式内存（pooled memory），将其连接拆分为各个阶段，每个阶段都有自己的内存池。在结束每个阶段时，会一次释放所有内存。

在池式内存管理中，每次内存分配都会指定内存池，从中分配内存。每个内存池都有不同的生存期限。在 Apache 中，有一个持续时间为服务器存在期的内存池，还有一个持续时间为连接的存在期的内存池，以及一个持续时间为请求的存在期的池，另外还有其他一些内存池。因此，如果我的一系列函数不会生成比连接持续时间更长的数据，那么我就可以完全从连接池中分配内存，并知道在连接结束时，这些内存会被自动释放。另外，有一些实现允许注册清除函数（cleanup functions），在清除内存池之前，恰好可以调用它，来完成在内存被清理前需要完成的其他所有任务（类似于面向对象中的析构函数）。

要在自己的程序中使用池，您既可以使用 GNU libc 的 obstack 实现，也可以使用 Apache 的 Apache Portable Runtime。GNU obstack 的好处在于，基于 GNU 的 Linux 发行版本中默认会包括它们。Apache Portable Runtime 的好处在于它有很多其他工具，可以处理编写多平台服务器软件所有方面的事情。要深入了解 GNU obstack 和 Apache 的池式内存实现，请参阅参考资料部分中指向这些实现的文档的链接。


下面的假想代码列表展示了如何使用 obstack：
清单 11. obstack 的示例代码


#include <obstack.h>

#include <stdlib.h>

/* Example code listing for using obstacks */

/* Used for obstack macros (xmalloc is
   a malloc function that exits if memory
   is exhausted */

#define obstack_chunk_alloc xmalloc

#define obstack_chunk_free free

/* Pools */

/* Only permanent allocations should go in this pool */

struct obstack *global_pool;

/* This pool is for per-connection data */

struct obstack *connection_pool;

/* This pool is for per-request data */

struct obstack *request_pool;

void allocation_failed()

{

exit(1);

}

int main()

{

/* Initialize Pools */

global_pool = (struct obstack *)

xmalloc (sizeof (struct obstack));

obstack_init(global_pool);

connection_pool = (struct obstack *)

xmalloc (sizeof (struct obstack));

obstack_init(connection_pool);

request_pool = (struct obstack *)

xmalloc (sizeof (struct obstack));

obstack_init(request_pool);

/* Set the error handling function */

obstack_alloc_failed_handler = &allocation_failed;

/* Server main loop */

while(1)

{

wait_for_connection();

/* We are in a connection */

while(more_requests_available())

{

/* Handle request */

handle_request();

/* Free all of the memory allocated

 * in the request pool

 */

obstack_free(request_pool, NULL);

}

/* We're finished with the connection, time

 * to free that pool

 */

obstack_free(connection_pool, NULL);

}

}

int handle_request()

{

/* Be sure that all object allocations are allocated
 * from the request pool
 */

int bytes_i_need = 400;

void *data1 = obstack_alloc(request_pool, bytes_i_need);

/* Do stuff to process the request */

/* return */

return 0;

}

基本上，在操作的每一个主要阶段结束之后，这个阶段的 obstack 会被释放。不过，要注意的是，如果一个过程需要分配持续时间比当前阶段更长的内存，那么它也可以使用更长期限的 obstack，比如连接或者全局内存。传递给 obstack_free() 的 NULL 指出它应该释放 obstack 的全部内容。可以用其他的值，但是它们通常不怎么实用。

使用池式内存分配的益处如下所示：

    * 应用程序可以简单地管理内存。
    * 内存分配和回收更快，因为每次都是在一个池中完成的。分配可以在 O(1) 时间内完成，释放内存池所需时间也差不多（实际上是 O(n) 时间，不过在大部分情况下会除以一个大的因数，使其变成 O(1)）。
    * 可以预先分配错误处理池（Error-handling pools），以便程序在常规内存被耗尽时仍可以恢复。
    * 有非常易于使用的标准实现。

池式内存的缺点是：

    * 内存池只适用于操作可以分阶段的程序。
    * 内存池通常不能与第三方库很好地合作。
    * 如果程序的结构发生变化，则不得不修改内存池，这可能会导致内存管理系统的重新设计。
    * 您必须记住需要从哪个池进行分配。另外，如果在这里出错，就很难捕获该内存池。

垃圾收集
垃圾收集（Garbage collection）是全自动地检测并移除不再使用的数据对象。垃圾收集器通常会在当可用内存减少到少于一个具体的阈值时运行。通常，它们以程序所知的可用的一组"基本"数据 —— 栈数据、全局变量、寄存器 —— 作为出发点。然后它们尝试去追踪通过这些数据连接到每一块数据。收集器找到的都是有用的数据；它没有找到的就是垃圾，可以被销毁并重新使用这些无用的数据。为了有效地管理内存，很多类型的垃圾收集器都需要知道数据结构内部指针的规划，所以，为了正确运行垃圾收集器，它们必须是语言本身的一部分。


收集器的类型

    * 复制（copying）： 这些收集器将内存存储器分为两部分，只允许数据驻留在其中一部分上。它们定时地从"基本"的元素开始将数据从一部分复制到另一部分。内存新近被占用的部分现在成为活动的，另一部分上的所有内容都认为是垃圾。另外，当进行这项复制操作时，所有指针都必须被更新为指向每个内存条目的新位置。因此，为使用这种垃圾收集方法，垃圾收集器必须与编程语言集成在一起。
    * 标记并清理（Mark and sweep）：每一块数据都被加上一个标签。不定期的，所有标签都被设置为 0，收集器从"基本"的元素开始遍历数据。当它遇到内存时，就将标签标记为 1。最后没有被标记为 1 的所有内容都认为是垃圾，以后分配内存时会重新使用它们。
    * 增量的（Incremental）：增量垃圾收集器不需要遍历全部数据对象。因为在收集期间的突然等待，也因为与访问所有当前数据相关的缓存问题（所有内容都不得不被页入（page-in）），遍历所有内存会引发问题。增量收集器避免了这些问题。
    * 保守的（Conservative）：保守的垃圾收集器在管理内存时不需要知道与数据结构相关的任何信息。它们只查看所有数据类型，并假定它们可以全部都是指针。所以，如果一个字节序列可以是一个指向一块被分配的内存的指针，那么收集器就将其标记为正在被引用。有时没有被引用的内存会被收集，这样会引发问题，例如，如果一个整数域中包含一个值，该值是已分配内存的地址。不过，这种情况极少发生，而且它只会浪费少量内存。保守的收集器的优势是，它们可以与任何编程语言相集成。

Hans Boehm 的保守垃圾收集器是可用的最流行的垃圾收集器之一，因为它是免费的，而且既是保守的又是增量的，可以使用 --enable-redirect-malloc 选项来构建它，并且可以将它用作系统分配程序的简易替代者（drop-in replacement）（用 malloc/free 代替它自己的 API）。实际上，如果这样做，您就可以使用与我们在示例分配程序中所使用的相同的 LD_PRELOAD 技巧，在系统上的几乎任何程序中启用垃圾收集。如果您怀疑某个程序正在泄漏内存，那么您可以使用这个垃圾收集器来控制进程。在早期，当 Mozilla 严重地泄漏内存时，很多人在其中使用了这项技术。这种垃圾收集器既可以在 Windows® 下运行，也可以在 UNIX 下运行。

垃圾收集的一些优点：

    * 您永远不必担心内存的双重释放或者对象的生命周期。
    * 使用某些收集器，您可以使用与常规分配相同的 API。

其缺点包括：

    * 使用大部分收集器时，您都无法干涉何时释放内存。
    * 在多数情况下，垃圾收集比其他形式的内存管理更慢。
    * 垃圾收集错误引发的缺陷难于调试。
    * 如果您忘记将不再使用的指针设置为 null，那么仍然会有内存泄漏。

结束语
一切都需要折衷：性能、易用、易于实现、支持线程的能力等，这里只列出了其中的一些。为了满足项目的要求，有很多内存管理模式可以供您使用。每种模式都有大量的实现，各有其优缺点。对很多项目来说，使用编程环境默认的技术就足够了，不过，当您的项目有特殊的需要时，了解可用的选择将会有帮助。下表对比了本文中涉及的内存管理策略。

表 1. 内存分配策略的对比
策略 分配速度 回收速度 局部缓存 易用性 通用性 实时可用 SMP 线程友好
定制分配程序  取决于实现  取决于实现  取决于实现  很难  无  取决于实现  取决于实现
简单分配程序 内存使用少时较快 很快 差  容易  高  否  否
GNU malloc 中  快  中  容易  高  否  中
Hoard  中  中  中  容易  高  否  是
引用计数  N/A  N/A  非常好  中  中  是（取决于 malloc 实现）  取决于实现
池  中  非常快  极好  中  中  是（取决于 malloc 实现）  取决于实现
垃圾收集  中（进行收集时慢）  中  差  中  中  否  几乎不


Web 上的通用参考资料

    * 内存管理参考 中有很多关于内存管理参考资料和技术文章的链接。

    * 关于内存管理和内存层级的 OOPS Group Papers 是非常好的一组关于此主题的技术文章。

    * C++ 中的内存管理讨论的是为 C++ 编写定制的分配程序。

    * Programming Alternatives: Memory Management 讨论了程序员进行内存管理时的一些选择。

    * 垃圾收集 FAQ 讨论了关于垃圾收集您需要了解的所有内容。

    * Richard Jones 的 Garbage Collection Bibliography 有指向任何您想要的关于垃圾收集的文章的链接。

    * 用于动态存储分配和内存管理的调试工具 很好地列出了用于在程序中寻找内存问题的 malloc 实现。

书籍

    * Michael Daconta 撰写的 C++ Pointers and Dynamic Memory Management 介绍了关于内存管理的很多技术。

    * Frantisek Franek 撰写的 Memory as a Programming Concept in C and C++ 讨论了有效使用内存的技术与工具，并给出了在计算机编程中应当引起注意的内存相关错误的角色。

    * Richard Jones 和 Rafael Lins 合著的 Garbage Collection: Algorithms for Automatic Dynamic Memory Management 描述了当前使用的最常见的垃圾收集算法。

    * 在 Donald Knuth 撰写的 The Art of Computer Programming 第 1 卷 Fundamental Algorithms 的第 2.5 节"Dynamic Storage Allocation"中，描述了实现基本的分配程序的一些技术。

    * 在 Donald Knuth 撰写的 The Art of Computer Programming 第 1 卷 Fundamental Algorithms 的第 2.3.5 节"Lists and Garbage Collection"中，讨论了用于列表的垃圾收集算法。

    * Andrei Alexandrescu 撰写的 Modern C++ Design 第 4 章"Small Object Allocation"描述了一个比 C++ 标准分配程序效率高得多的一个高速小对象分配程序。

    * Andrei Alexandrescu 撰写的 Modern C++ Design 第 7 章"Smart Pointers"描述了在 C++ 中智能指针的实现。

    * Jonathan 撰写的 Programming from the Ground Up 第 8 章"Intermediate Memory Topics"中有本文使用的简单分配程序的一个汇编语言版本。

来自 developerWorks

    * 自我管理数据缓冲区内存 （developerWorks，2004 年 1 月）略述了一个用于管理内存的自管理的抽象数据缓存器的伪 C （pseudo-C）实现。

    * A framework for the user defined malloc replacement feature （developerWorks，2002 年 2 月）展示了如何利用 AIX 中的一个工具，使用自己设计的内存子系统取代原有的内存子系统。

    * 掌握 Linux 调试技术 （developerWorks，2002 年 8 月）描述了可以使用调试方法的 4 种不同情形：段错误、内存溢出、内存泄漏和挂起。

    * 在 处理 Java 程序中的内存漏洞 （developerWorks，2001 年 2 月）中，了解导致 Java 内存泄漏的原因，以及何时需要考虑它们。

    * 在 developerWorks Linux 专区中，可以找到更多为 Linux 开发人员准备的参考资料。

    * 从 developerWorks 的 Speed-start your Linux app 专区中，可以下载运行于 Linux 之上的 IBM 中间件产品的免费测试版本，其中包括 WebSphere® Studio Application Developer、WebSphere Application Server、DB2® Universal Database、Tivoli® Access Manager 和 Tivoli Directory Server，查找 how-to 文章和技术支持。

    * 通过参与 developerWorks blogs 加入到 developerWorks 社区。

    * 可以在 Developer Bookstore Linux 专栏中定购 打折出售的 Linux 书籍。

关于作者
Jonathan Bartlett 是 Programming from the Ground Up 一书的作者，这本书介绍的是 Linux 汇编语言编程。Jonathan Bartlett 是 New Media Worx 的总开发师，负责为客户开发 Web、视频、kiosk 和桌面应用程序。您可以通过 johnnyb@eskimo.com 与 Jonathan 联系。

refer:http://210.77.146.90/blog/article_81038.522452.html