65.9K
CodeProject 正在变化。 阅读更多。
Home

一种解决 shared_ptrs 问题的新内存管理方法

Achilleas Margaritis
starIconstarIconstarIconstarIcon
emptyStarIcon
starIcon

4.17/5 (4投票s)

2009年2月23日

CPOL

6分钟阅读

viewsIcon

26020

downloadIcon

140

使用新方法解决 shared_ptrs 问题

引言

本文档描述了一种用于自动化内存管理的新想法的设计和实现，该想法可以解决循环引用的问题。

Boost 包含一些不错的内存管理类：shared_ptr、weak_ptr 和 intrusive_ptr。使用这些类进行内存管理非常方便，但引用计数有一个缺点：它无法处理循环引用。

为了使用引用计数处理循环引用，程序员需要使用弱指针来打破循环。这样的任务在时间和空间上可能无法很好地扩展：随着项目变得越来越大和复杂，循环会越来越难发现，特别是当循环是通过子类引入时。

当一个项目在很长一段时间内演进，并且有不同的程序员负责时，问题会变得更糟。在一个人向另一个人交接期间，关于循环的知识可能会丢失。

文件 'main.cpp' 中的代码实现了一种自动化内存管理的解决方案，借鉴了一些真正的垃圾收集器的思想。该解决方案可以处理引用循环，并且在对象不再被程序中的任何地方引用时，可以按良好的顺序删除对象（最终化顺序是垃圾收集器的一个众所周知的问题）。

提出的解决方案并不是一个解决内存管理所有方面的万能药。充其量，它可以被认为是现有方法的补充。

背景

在真正的垃圾收集器中，收集器从根集开始扫描对象图，将每个访问过的对象标记为可达。在收集结束时未被触及的对象被视为不可达，因此被收集。例如，如果我们有三个根引用 R1、R2 和 R3，以及对象 A、B 和 C

R1 ---> A ---> B 
           |  
R2 --------|
R3 ---> C

如果移除了引用 R3，则对象图变为

R1 ---> A ---> B 
           |  
R2 --------|
R3      C

收集算法的执行过程如下：

  1. 从 R1，A 是可达的。
  2. 将 A 标记为可达。
  3. 扫描 A。
  4. 从 A，B 是可达的。
  5. 将 B 标记为可达。
  6. 扫描 B。
  7. 从 R2，B 是可达的。
  8. B 已经被标记，不要再次标记。
  9. A、B 是可达的；C 是不可达的。
  10. 收集 C。

此方法在 C++ 中的问题

为了让这奏效，我们必须知道根集。不幸的是，在 C++ 中，根集是未知的（这需要编译器协助），所以这个算法无法应用。

一个解决方案是将根指针显式或隐式地注册到一个 ptr 集合中，在特殊指针类的构造函数中进行。但这对于 STL 容器不起作用，因为 STL 容器本身必须使用指定的指针类。不幸的是，这并不总是如此。例如

ROOT_PTR_COLLECTION
 |
 |--> R1 ---> A ---> B
 |          |
 R2 --------|
 |
 R3 ---> C

但是，当我们有一个 STL 容器时

ROOT_PTR_COLLECTION
 |
 |--> R1 ---> A ---> B
 |    |          |
 |--> R2 --------|
 |    |
 |--> R3 ---> C
 |     
 |--> R4 ----> STL CONTAINER
                | ~~> D
                | ~~> E

在上图中，箭头 '~~>' 表示一个非垃圾回收的链接（可能是 shared_ptr）。当收集运行时

  1. 从根 ptr 集合，可以到达引用 R4。
  2. 从 R4，可以到达STL 容器。
  3. C 和 D 是不可达的。
  4. 收集 C 和 D。

因此，C 和 D 将被收集，即使有一个 STL 容器引用了这些对象。

解决方案

在传统方法中，收集算法可以用以下一句话来概括：

当一个对象不再能从任何以根集为起点的路径访问时，它就是可收集的。

上面的句子可以反转而不会改变收集算法的本质：

当一个对象不再能从任何以根集为终点的路径访问时，它就是可收集的。

使用这种反向方法，可以创建一组智能指针类，用于检查是否存在任何通往根指针的路径。带有三个引用 R1、R2、R3 和对象 A、B、C 的原始示例变为

R1 <--- A <--- B
           |
R2 <-------|
R3 <--- C

当移除一个引用时，我们可以检查是否存在另一条通往根引用的路径。如果没有根引用指向该对象，则该对象可以安全删除。例如，如果移除了引用 R3，我们的图变为

R1 <--- A <--- B
           |
R2 <-------|
R3      C

现在，对象 C 可以安全地删除。

设计与实现

在文件 'main.cpp' 中，定义了以下类：

该类是一个 boost::intrusive 列表节点（使用 boost::intrusive），出于性能原因，因为一个指针一次只能指向一个对象。

该类还包含一个指向所有者对象的指针，在指针实例构造时设置。此指针用于确定指针何时为根：如果一个指针在没有所有者的情况下实例化，那么它就是根指针。

  1. 类 'object'，作为一个基类，包含一个指向它的指针列表。这对于能够向后遍历对象图到根是必需的。对象类包含一个标志 'm_lock'，用于防止在检查对象是否可收集时出现无限循环。
  2. 类 'ptr_base'，它是一个通用的指针类，封装了获取和释放对象的逻辑。
    1. 'acquire' 操作会将指针添加到被指向对象的指针列表中。
    2. 'release' 操作会从先前被指向对象的指针列表中移除指针。然后，如果对象可收集，它会调用对象自身来处置它。这就是图向后扫描到根的地方。
  3. 类 'ptr<T>'，它是一个简单的派生类，为 'ptr_base' 类添加了类型检查。该类具有正常的指针语义以及 STL 指针语义（函数 'get()' 和 'reset()'）。

析构顺序

当对象被处置时，会检查它是否可收集：对象图会向后遍历到根。如果对象可收集，它将被删除。

删除对象会导致对象的成员指针递归地释放其自己的对象，按自然顺序（即，按 C++ 析构顺序）。

解决循环问题

如果存在循环，则 dispose() 函数确保在对象被删除之前释放所有指向被处置对象的指针，从而解决循环。

使用 STL 容器

STL 容器包含根引用，即没有所有者的 ptr<T> 实例。因此，只要对象被 STL 容器引用，它就不会被收集，因为它将可从 STL 容器的根集中访问。

STL 容器本身可以通过共享指针进行管理。'main.cpp' 中提供的示例包含一个 std::list 的示例。

即时处置 vs. 延迟处置

每次指针更改值时尝试处置对象可能是一个非常慢的操作，如果对象图过于复杂。解决此问题的方法是推迟检查到稍后的日期，即采用延迟处置。

类 'collector' 和 'collector_object' 协同工作，为延迟处置提供功能。

测试

'main.cpp' 文件包含两个测试：

  1. 一个具有树（节点指向父节点、前一个和下一个兄弟节点、第一个和最后一个子节点）的测试，采用即时处置。
  2. 使用延迟处置的相同测试。

在这两种情况下，所有对象都按要求被收集。

该测试已在 Visual Studio 2005 中执行。

结论

这是作者（以及其他作者）过去（而且很糟糕 :-)) 尝试制作收集器的列表。

历史

  • 2009 年 2 月 23 日：初始版本
© . All rights reserved.