Проблема, упомянутая в функции push очереди без блокировок в разделе 7.15 «Параллелизм C++ в действии». ⇐ C++

[Anonymous]

Я прочитал в листинге 7.15 «Параллелизм в C++»:

Использование схемы подсчета ссылок позволяет избежать этой конкретной гонки, но это не единственная гонка. в толчке(). Если вы посмотрите на обновленную версию push() в листинге 7.15, вы увидите шаблон, который вы видели в стеке: загрузите атомарный указатель (1) и разыменуйте (2) этот указатель. Тем временем другой поток может обновить указатель (3), что в конечном итоге приведет к освобождению узла (в pop()). Если узел освобождается до того, как вы разыменовываете указатель, у вас неопределенное поведение. Ой! Соблазнительно добавить внешний счетчик в хвост так же, как вы это сделали для головы, но каждый узел уже имеет внешний счетчик в следующем указателе предыдущего узла в очереди. Наличие двух внешних счетчиков для одного и того же узла требует изменения схемы подсчета ссылок, чтобы избежать слишком раннего удаления узла. Вы можете решить эту проблему, также подсчитав количество внешних счетчиков внутри структуры узла и уменьшив это число при уничтожении каждого внешнего счетчика (а также добавив соответствующий внешний счетчик к внутреннему счетчику). Если внутренний счетчик равен нулю и внешние счетчики отсутствуют, вы знаете, что узел можно безопасно удалить. С этой техникой я впервые столкнулся в проекте Джо Сейя Atomic Ptr Plus (http://atomic-ptr-plus.sourceforge.net/). Следующий листинг показывает, как push() выглядит в соответствии с этой схемой.

Листинг 7.15. (Неработающая) первая попытка пересмотра push():
void push(T new_value)
{
std::unique_ptr new_data(new T(new_value));
counted_node_ptr new_next;
new_next.ptr = new node;
new_next.external_count = 1;
for (;;)
{
node* const old_tail = tail.load(); // 1
T* old_data = nullptr;
if (old_tail->data.compare_exchange_strong(
old_data, new_data.get())) // 2
{
old_tail->next = new_next;
tail.store(new_next.ptr); // 3
new_data.release();
break;
}
}
}


Однако я не совсем понимаю эту часть:

Если узел освобождается до того, как вы разыменовывает указатель, у вас неопределенное поведение.

В pop() функция сначала проверяет, указывают ли заголовок и хвост на одно и то же узел-заполнитель. Если да, то он определяет, что очередь пуста, и ничего не делает. В листинге 7.15 функция push() обновляет хвост только на последнем шаге, а это означает, что pop() не будет работать с узлом, поставленным в очередь, пока push() не завершит операцию постановки в очередь. Итак, откуда же берется это состояние гонки?
Поскольку автор не привел в книге пример предположения для этой ситуации (пример основан на предыдущем блокировочном стеке ), я не могу предоставить полный контекст. Ниже приведен код pop() до изменения.
template
class lock_free_queue {
private:
struct node {
std::shared_ptr data;
node *next;
node() : next(nullptr) {}
};

std::atomic head;
std::atomic tail;

node *pop_head() {
node *const old_head = head.load();
if (old_head == tail.load()) {
return nullptr;
}
head.store(old_head->next);
return old_head;
}

public:
lock_free_queue() : head(new node), tail(head.load()) {}

// ...

std::shared_ptr pop() {
node *old_head = pop_head();
if (!old_head) {
return std::shared_ptr();
}
std::shared_ptr const res(old_head->data);
delete old_head;
return res;
}

void push(T new_value) {
std::shared_ptr new_data(std::make_shared(new_value));
node *p = new node;
node *const old_tail = tail.load();
old_tail->data.swap(new_data);
old_tail->next = p;
tail.store(p);
}

};



Подробнее здесь: https://stackoverflow.com/questions/793 ... concurrenc