如何实现不溢出的原子引用计数器？

Question

我正在考虑基于不会溢出的原子整数的引用计数。怎么做？

请不要关注这种溢出是否是一个现实问题。任务本身引起了我的兴趣，即使实际上并不重要。

例子

引用计数的示例实现如 Boost.Atomic 中的示例所示。基于该示例，我们可以提取以下示例代码：

struct T
{
    boost::atomic<boost::uintmax_t> counter;
};

void add_reference(T* ptr)
{
    ptr->counter.fetch_add(1, boost::memory_order_relaxed);
}

void release_reference(T* ptr)
{
    if (ptr->counter.fetch_sub(1, boost::memory_order_release) == 1) {
        boost::atomic_thread_fence(boost::memory_order_acquire);
        delete ptr;
    }
}

另外给出以下解释

Increasing the reference counter can always be done with memory_order_relaxed: New references to an object can only be formed from an existing reference, and passing an existing reference from one thread to another must already provide any required synchronization.

It is important to enforce any possible access to the object in one thread (through an existing reference) to happen before deleting the object in a different thread. This is achieved by a "release" operation after dropping a reference (any access to the object through this reference must obviously happened before), and an "acquire" operation before deleting the object.

It would be possible to use memory_order_acq_rel for the fetch_sub operation, but this results in unneeded "acquire" operations when the reference counter does not yet reach zero and may impose a performance penalty.

编辑 >>>

Boost.Atomic 文档似乎在这里有误。毕竟可能需要 acq_rel。

至少在使用 std::atomic 时 boost::shared_ptr 的实现是这样的（还有其他实现）。请参阅文件 boost/smart_ptr/detail/sp_counted_base_std_atomic.hpp.

Herb Sutter 在他的演讲中也提到了它 C++ and Beyond 2012: Herb Sutter - atomic<> Weapons, 2 of 2（引用计数部分从 1:19:51 开始）。此外，他似乎不鼓励在这次谈话中使用栅栏。

感谢 user 2501 在下面的评论中指出这一点。

<<< 结束编辑

初始尝试

现在的问题是 add_reference 所写的可能（在某些时候）溢出。而且它会默默地这样做。这显然会在调用 matched release_reference 时导致问题，这会过早地破坏对象。（前提是add_reference会被再次调用到达1。）

我在考虑如何让 add_reference 检测溢出并在不冒任何风险的情况下优雅地失败。

与 0 相比，一旦我们离开 fetch_add 将不会执行，因为在这两个线程之间，其他线程可以再次调用 add_reference（到达 1）然后 release_reference（错误地破坏了有效的对象）。

先检查（load）也无济于事。这样一些其他线程可以在我们对 load 和 fetch_add.

的调用之间添加自己的引用

这是解决方案吗？

然后我想也许我们可以从 load 开始，但前提是我们这样做 compare_exchange。

因此，首先我们执行 load 并获取本地值。如果是 std::numeric_limits<boost::uintmax_t>::max() 那么我们就失败了。 add_reference 无法添加其他参考，因为所有可能的参考都已被采用。

否则我们创建另一个局部值，即先前的局部引用计数加上1。

现在我们 compare_exchange 提供原始本地引用计数作为预期值（这确保没有其他线程同时修改引用计数）和增加的本地引用计数作为期望值。

由于 compare_exchange 可能会失败，我们必须在循环中执行此操作（包括 load）。直到成功或检测到最大值。

一些问题

这样的解对吗？
需要什么样的内存顺序才能使其有效？
应该使用哪个compare_exchange？ _weak 或 _strong?
会影响release_reference功能吗？
实践中使用了吗？

Answer 1

解决方案是正确的，也许可以通过一件事来改进。目前，如果该值在本地 CPU 中达到最大值，可以再减少一个 CPU，但当前 CPU 仍会缓存旧值。值得用相同的 expected 和 newValue 做虚拟 compare_exchange 以确认最大值仍然存在，然后才抛出异常（或任何你想要的）。

其余的：

无论你使用 _weak 还是 _strong 都没有关系，因为无论如何它都会运行循环，因此下一个 load 将非常可靠地获得最新的值。

对于 add_reference 和 release_reference - 那么谁来检查它是否真的被添加了？它会抛出异常吗？如果是，它可能会起作用。但一般来说，最好不要让这么低级别的东西失败，而是使用 uintptr_t 作为参考计数器，这样它就不会溢出，因为它足够大，可以覆盖地址 space，因此可以覆盖任意数量的对象同时存在

不，由于上述原因，它没有在实践中使用。

Answer 2

速算：假设 uint 是 32 位，那么最大 uint 是 4G（大约 40 亿）。每个 reference/pointer 至少有 4 个字节（如果您使用的是 64 位系统，则为 8 个字节）因此要溢出，您需要 16GB 的内存专门用于存储指向同一对象的引用，这应该表明存在严重的设计缺陷。

我想说这在今天不是问题，在可预见的未来也不是。

Answer 3

这个问题没有实际意义。即使假设原子增量需要 1 CPU 个周期（它不会！），在 4GHz CPU 上也需要半年时间来环绕 64 位整数，前提是 CPU 除了保持递增之外什么都不做.

考虑到实际程序的实际情况，我很难相信这是一个可以困扰您的真实问题。

如何实现不溢出的原子引用计数器？

How to implement atomic reference counter that does not overflow?

c++

multithreading

atomic

reference-counting

integer-overflow