c++ - 拆分引用计数如何在无锁堆栈中工作？

Question

我正在阅读 C++ concurrency in action 2。
它为无锁堆栈引入了拆分引用计数。

One possible technique involves the use of not one but two reference counts for each node: an internal count and an external count. The sum of these values is the total number of references to the node. The external count is kept alongside the pointer to the node and is increased every time the pointer is read. When the reader is finished with the node, it decreases the internal count. A simple operation that reads the pointer will leave the external count increased by one and the internal count decreased by one when it’s finished.

上面的短语解释了拆分引用计数的简要概念。听起来外部计数总是增加而内部计数总是减少。

When the external count/pointer pairing is no longer required (the node is no longer accessible from a location accessible to multiple threads), the internal count is increased by the value of the external count minus one and the external counter is discarded. Once the internal count is equal to zero, there are no outstanding references to the node and it can be safely deleted. It’s still important to use atomic operations for updates of shared data. Let’s now look at an implementation of a lock-free stack that uses this technique to ensure that the nodes are reclaimed only when it’s safe to do so.

但是在上面的短语中，当节点不再可访问时，内部计数应该增加外部计数的值减一。我对这个解释感到非常困惑。
(1) 使用内部和外部计数的确切目的是什么？
(2) 为什么它需要两个引用计数而不是一个？
编辑:
我在下面添加了书中的示例代码。

template <typename T>
class lock_free_stack {
 private:
  struct node;
  struct counted_node_ptr {
    int external_count;
    node* ptr;
  };
  struct node {
    std::shared_ptr<T> data;
    std::atomic<int> internal_count;
    counted_node_ptr next;
    node(T const& data_)
        : data(std::make_shared<T>(data_)), internal_count(0) {}
  };
  std::atomic<counted_node_ptr> head;

  void increase_head_count(counted_node_ptr& old_counter) {
    counted_node_ptr new_counter;
    do {
      new_counter = old_counter;
      ++new_counter.external_count;
    } while (!head.compare_exchange_strong(old_counter, new_counter,
                                           std::memory_order_acquire,
                                           std::memory_order_relaxed));
    old_counter.external_count = new_counter.external_count;
  }

 public:
  ~lock_free_stack() {
    while (pop())
      ;
  }

  void push(T const& data) {
    counted_node_ptr new_node;
    new_node.ptr = new node(data);
    new_node.external_count = 1;
    new_node.ptr->next = head.load();
    while (!head.atomic_compare_exchange_weak(new_node.ptr->next, new_node,
                                              std::memory_order_release,
                                              std::memory_order_relaxed))
      ;
  }

  std::shared_ptr<T> pop() {
    counted_node_ptr old_head = head.load(std::memory_order_relaxed);
    for (;;) {
      increase_head_count(old_head);
      node* const ptr = old_head.ptr;

      if (!ptr) {
        return std::shared_ptr<T>();
      }

      if (head.compare_exchange_strong(old_head, ptr->next,
                                       std::memory_order_relaxed)) {
        std::shared_ptr<T> res;
        res.swap(ptr->data);
        int const count_increase = old_head.external_count - 2;
        if (ptr->internal_count.fetch_add(
                count_increase, std::memory_order_release) == -count_increase) {
          delete ptr;
        }
        return res;
      } else if (ptr->internal_count.fetch_add(-1, std::memory_order_relaxed) ==
                 1) {
        ptr->internal_count.load(std::memory_order_acquire);
        delete ptr;
      }
    }
  }
};

Answer 1

简短说明
拆分引用计数减少了争用。添加 external_count-2至 internal_count在这个实现中将引用计数的两个阶段分开:在第一个阶段引用计数被拆分，在第二个阶段引用计数在 internal_count 中。只要。
请阅读以下详细说明。
引用计数
让我们从为什么在本书中的无锁堆栈的情况下需要引用计数开始。我们需要阻止访问 next head指向的节点字段, 如果该节点已被删除。我们要删除 head 指向的节点当它不再使用时。为了实现这一点，我们使用引用计数延迟删除此节点。
重要的是，节点只能被头(当节点在列表中的第一个)或前一个节点的下一个指针(当节点在列表的中间或末尾时)引用，但不能同时被两者引用 -因为没有头部指向链表中间或尾部的节点的情况。这就是为什么我们不需要从多个计数节点指针指向一个单独的控制块(如 shared_ptr )。因此，我们可以将计数器直接放入头指针中。
虽然我们需要保护对 head.ptr 指向的节点字段的访问仅(实际上仅用于字段 next)，将计数器放入头指针是不够的。我们还必须将计数器放入 next指针 - 继续保护节点不被删除，即使节点在它之前被推送和弹出。如果我们在其他线程 Tb 正在弹出的节点 A 之前推送节点 B，然后在线程 Tb 之前弹出节点 B，我们将头指针计数器保存并恢复为下一个指针。
递增计数器和加载当前指针应该是单个原子操作，以确保被取消引用的指针的计数器增加。
为什么要拆分引用计数？
我们将计数器分为内部和外部两个原因:

递减计数器时，我们不需要对计数器和指针进行原子操作。原子地改变计数器就足够了。如果我们只有一个计数器，我们将不得不像在增加_head_count 中那样在循环中递减指针。

使用两个原子计数器减少了争用，但它增加了代码复杂性、内存使用量并且需要添加两个计数器进行检查。

为了保护节点不被删除，我们增加了 external_count。 internal_count 在计数指针指向的节点内。
回到非拆分引用计数
在pop操作的compare_exchange操作中，一旦header指针移动到下一个节点，没有线程可以增加指针计数器，因为读过前一个head的线程将失败compare_exchange操作，还没有读head的线程永远不会读这个head ，因为头部已经移动到下一个节点。这就是不再需要外部计数/指针配对的原因。它的值被添加到 internal_count。在此之后，计数器不再拆分:我们现在使用单个计数器 internal_count，它将所有计数器的增加和减少汇总到一个变量中。
我们可以将其视为两个阶段:在第一个阶段，我们的计数器被拆分(分为 external_count 和 internal_count)，在第二个阶段，我们的计数器合并为一个变量 - internal_count。在第一阶段，我们需要将 external_count 添加到 internal_count 以获得真实的计数器值。在第二阶段，我们只需要使用 internal_count，因为 external_count 有一些现在没有任何意义的旧值(正如书中所说，现在“外部计数器被丢弃”)。
为什么要从 external_count 中减去 2？
将 external_count 添加到 internal_count 时，external_count 值减 2。 为简单起见，此操作可以分为三个:

将 external_count 添加到 internal_count 移动到第二阶段(现在我们不再使用 external_count)。

将 internal_count 减 1，因为 head 不再指向此节点(请记住，我们将每个新节点的 external_count 设置为 1，因为 head 指向此节点)。

将 internal_count 减 1 以表示当前线程中不再需要此指针保护(请记住，我们在 increase_head_count 中将 external_count 增加 1 以保护指针)

internal_count.fetch_add(external_count - 2)的比较结果至 2 - external_count只是将结果 internal_count 与零进行比较的原子方式。
在代码中external_count在加到internal_count之前先减2，在书本中“内部计数增加了外部计数的值减1”。我认为这是文本中的一个错误(可能，作者最初计划将 internal_count 与添加 external_count-1 分开，另外减少 1 )。