Как работает разделенный подсчет ссылок в стеке без блокировок? ⇐ C++

[Anonymous]

Я читаю о параллелизме C++ в действии 2.
Он вводит разделение счетчиков ссылок для стека без блокировок.

Один из возможных методов предполагает использование не одного, а двух счетчиков ссылок для каждого узла: внутреннего счетчика и внешнего счетчика. Сумма этих значений представляет собой общее количество ссылок на узел. Внешний счетчик хранится рядом с указателем на узел и увеличивается каждый раз при чтении указателя. Когда считыватель завершает работу с узлом, он уменьшает внутренний счетчик. Простая операция чтения указателя приведет к тому, что внешний счетчик увеличится на единицу, а внутренний счетчик уменьшится на единицу после завершения.

Приведенная выше фраза объясняет краткую концепцию разделенного счетчика ссылок. Похоже, что внешний счетчик всегда увеличивается, а внутренний счетчик всегда уменьшается.

Когда соединение внешнего счетчика и указателя больше не требуется (узел больше не доступен из местоположения, доступного для нескольких потоков), внутренний счетчик увеличивается на значение внешнего счетчика минус один, а внешний счетчик отбрасывается. Как только внутренний счетчик станет равным нулю, на узел не останется невыполненных ссылок, и его можно будет безопасно удалить. По-прежнему важно использовать атомарные операции для обновления общих данных. Давайте теперь посмотрим на реализацию стека без блокировок, который использует эту технику, чтобы гарантировать, что узлы будут освобождены только тогда, когда это безопасно.

Но в приведенной выше фразе внутренний счетчик должен быть увеличен на значение внешнего счетчика минус единица, когда узел больше не доступен. Меня очень смущает это объяснение.
(1) Какова точная цель использования внутреннего и внешнего счетчика?
(2) Почему требуется два счетчика ссылок вместо одного?
Изменить:
Я добавил пример кода ниже из книги.
template
class lock_free_stack {
private:
struct node;
struct counted_node_ptr {
int external_count;
node* ptr;
};
struct node {
std::shared_ptr data;
std::atomic internal_count;
counted_node_ptr next;
node(T const& data_)
: data(std::make_shared(data_)), internal_count(0) {}
};
std::atomic 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 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();
}

if (head.compare_exchange_strong(old_head, ptr->next,
std::memory_order_relaxed)) {
std::shared_ptr 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;
}
}
}
};


Подробнее здесь: https://stackoverflow.com/questions/673 ... free-stack