拆分引用计数如何在无锁堆栈中工作？
How does the split reference counting work in a lock free stack?
我正在阅读 C++ 并发实战 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;
}
}
}
};
简短说明
拆分引用计数减少争用。将 external_count-2 添加到 internal_count 在此实现中将引用计数分为两个阶段：在第一阶段引用计数被拆分，在第二阶段引用计数仅在 internal_count 中。
请阅读下面的详细说明。
引用计数
让我们从书中的无锁堆栈案例开始，为什么我们需要引用计数。如果此节点已被删除，我们需要阻止访问 head 指向的节点的 next 字段。当 head 指向的节点不再使用时，我们想删除它。为此，我们使用引用计数延迟删除此节点。
重要的是节点只能被头（当节点在列表中的第一个时）或前一个节点的下一个指针（当节点在列表的中间或末尾时）引用，但不能同时被两者引用同时 - 因为没有头指向列表中间或末尾的节点的情况。这就是为什么我们不需要从多个计数的节点指针（如 shared_ptr 中）指向一个单独的控制块。所以，我们可以直接把counter放到head指针中。
虽然我们只需要保护对 head.ptr 指向的节点字段的访问（实际上只对字段 next ），但将计数器放入头指针是不够的。我们还必须将 counter 放入 next 指针 - 继续保护节点不被删除，即使节点在它之前被推送和弹出。如果我们将节点 B 推到被其他线程 Tb 弹出的节点 A 之前，然后在线程 Tb 之前弹出节点 B，我们将头指针计数器保存并恢复为下一个指针。
增加计数器和加载当前指针应该是单个原子操作，以确保取消引用的指针增加其计数器。
为什么要拆分引用计数？
我们将计数器分为内部计数器和外部计数器，原因有二：
我们不需要在递减计数器时对计数器和指针进行原子操作。以原子方式更改计数器就足够了。如果我们只有一个计数器，我们将不得不像在 increase_head_count.
中那样在循环中递减指针
使用两个原子计数器可减少争用，但会增加代码复杂度、内存使用量并需要添加两个计数器进行检查。
为了保护节点不被删除，我们递增 external_count。 internal_count 在计数指针指向的节点内。
返回非拆分引用计数
在弹出操作期间，一旦头部指针移动到compare_exchange操作中的下一个节点，任何线程都不能增加指针计数器，因为读取前一个头部的线程将失败compare_exchange操作，并且还没有读取 head 的线程永远不会读取这个 head，因为 head 已经移动到下一个节点。这就是不再需要外部 count/pointer 配对的原因。它的值被添加到 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，书中的文字是“内部计数增加外部计数的值减一”。我认为这是文本中的一个错误（可能，作者最初计划在添加 external_count-1 的同时将 internal_count 减 1）。
我正在阅读 C++ 并发实战 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;
}
}
}
};
简短说明
拆分引用计数减少争用。将 external_count-2 添加到 internal_count 在此实现中将引用计数分为两个阶段：在第一阶段引用计数被拆分，在第二阶段引用计数仅在 internal_count 中。
请阅读下面的详细说明。
引用计数
让我们从书中的无锁堆栈案例开始，为什么我们需要引用计数。如果此节点已被删除，我们需要阻止访问 head 指向的节点的 next 字段。当 head 指向的节点不再使用时，我们想删除它。为此，我们使用引用计数延迟删除此节点。
重要的是节点只能被头（当节点在列表中的第一个时）或前一个节点的下一个指针（当节点在列表的中间或末尾时）引用，但不能同时被两者引用同时 - 因为没有头指向列表中间或末尾的节点的情况。这就是为什么我们不需要从多个计数的节点指针（如 shared_ptr 中）指向一个单独的控制块。所以，我们可以直接把counter放到head指针中。
虽然我们只需要保护对 head.ptr 指向的节点字段的访问（实际上只对字段 next ），但将计数器放入头指针是不够的。我们还必须将 counter 放入 next 指针 - 继续保护节点不被删除，即使节点在它之前被推送和弹出。如果我们将节点 B 推到被其他线程 Tb 弹出的节点 A 之前，然后在线程 Tb 之前弹出节点 B，我们将头指针计数器保存并恢复为下一个指针。
增加计数器和加载当前指针应该是单个原子操作，以确保取消引用的指针增加其计数器。
为什么要拆分引用计数？
我们将计数器分为内部计数器和外部计数器，原因有二：
我们不需要在递减计数器时对计数器和指针进行原子操作。以原子方式更改计数器就足够了。如果我们只有一个计数器，我们将不得不像在 increase_head_count.
中那样在循环中递减指针使用两个原子计数器可减少争用，但会增加代码复杂度、内存使用量并需要添加两个计数器进行检查。
为了保护节点不被删除，我们递增 external_count。 internal_count 在计数指针指向的节点内。
返回非拆分引用计数
在弹出操作期间，一旦头部指针移动到compare_exchange操作中的下一个节点，任何线程都不能增加指针计数器，因为读取前一个头部的线程将失败compare_exchange操作，并且还没有读取 head 的线程永远不会读取这个 head，因为 head 已经移动到下一个节点。这就是不再需要外部 count/pointer 配对的原因。它的值被添加到 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，书中的文字是“内部计数增加外部计数的值减一”。我认为这是文本中的一个错误（可能，作者最初计划在添加 external_count-1 的同时将 internal_count 减 1）。