Chinaunix首页 | 论坛 | 博客
  • 博客访问: 855961
  • 博文数量: 133
  • 博客积分: 7117
  • 博客等级: 少将
  • 技术积分: 1846
  • 用 户 组: 普通用户
  • 注册时间: 2008-08-16 21:30
文章分类

全部博文(133)

文章存档

2012年(1)

2011年(4)

2010年(2)

2009年(57)

2008年(69)

分类: C/C++

2009-04-29 09:10:17

引用计数

引用计数是一种 半自动(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 #include /* 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,那么仍然会有内存泄漏。
 

 
结束语

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

策略  分配速度  回收速度  局部缓存  易用性  通用性  实时可用  SMP 线程友好 
定制分配程序  取决于实现  取决于实现  取决于实现  很难  无  取决于实现  取决于实现 
简单分配程序 内存使用少时较快 很快 差  容易  高  否  否 
GNU malloc  中  快  中  容易  高  否 
Hoard  中  中  中  容易  高  否  是 
引用计数  N/A  N/A  非常好  中  中  是(取决于 malloc 实现)  取决于实现 
池  中  非常快  极好  中  中  是(取决于 malloc 实现)  取决于实现 
垃圾收集  中(进行收集时慢)  中  差  中  中  否  几乎不 
增量垃圾收集  中  中  中  中  中  否  几乎不 
增量保守垃圾收集  中  中  中  容易  高  否  几乎不
阅读(1240) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~