Является ли этот пример указателя опасности ошибочным из-за проблемы ABA?

Question

Является ли этот пример указателя опасности ошибочным из-за проблемы ABA?

В книге C ++ Параллелизм в действии, автор привел пример использования указателя опасности для реализации структуры данных стека без блокировки. Часть кода выглядит следующим образом:

std::shared_ptr<T> pop()
{
std::atomic<void*>& hp=get_hazard_pointer_for_current_thread();
node* old_head=head.load();
node* temp;
do
{
temp=old_head;
hp.store(old_head);
old_head=head.load();
} while(old_head!=temp);
// ...
}

В описании сказано, что

Вы должны сделать это в while цикл, чтобы убедиться, что node не имеет
был удален между чтением старого head указатель и
настройка указателя опасности. Во время этого окна нет другой темы
знает, что вы получаете доступ к этому конкретному узлу. К счастью, если старый
head узел будет удален, head само должно быть изменилось,
так что вы можете проверить это и продолжать цикл, пока вы не знаете, что head
Указатель по-прежнему имеет то же значение, на которое вы установили указатель опасности.

Я думаю, что код неисправен, потому что head узел подвержен АБА проблема. Даже если значение head остается прежним, узел, на который он изначально указывает, возможно, был удален. Новый head выделен узел, который имеет то же значение адреса, что и предыдущий.

6

aba c++c++11 concurrency lock-free

Решение

Другие решения

Других решений пока нет …

Источник

Accepted Answer

По умолчанию memory_order за load() операции это std::memory_order_seq_cst, что обеспечивает последовательную согласованность всех операций (общий глобальный порядок):

каждый memory_order_seq_cst операция B который загружается из атомарной переменной
M, отмечает одно из следующего:

результат последней операции A что модифицировано M, который появляется раньше B в едином общем порядке

ИЛИ, если бы был такой A, B может наблюдать результат некоторой модификации на M это не memory_order_seq_cst и не
случается, перед тем A

ИЛИ, если бы не было такого A, B может наблюдать результат некоторой несвязанной модификации M это не memory_order_seq_cst,

Таким образом, если узел изменен (удален), и это происходит до второго чтения в общем глобальном порядке, вы гарантированно увидите это изменение и, таким образом, цикл продолжит выполняться. Если эта модификация заказана после, то никакого вреда нет, так как указатель опасности уже установлен.

У вас есть эта гарантия, потому что указатель сохранения к опасности также делается с std::memory_order_seq_cst, Этот порядок памяти дает вам приобретать операция для нагрузок и релиз операция для магазинов, предотвращающая переупорядочение в том же потоке. Таким образом, «удачное» чтение (old_head==temp) гарантирует, что правильные данные были сохранены.

Рассматривайте эти две нагрузки как точки синхронизации — так как они выполняют приобретать операции, они синхронизированы с соответствующими релиз операции, которые изменяют эти значения, в результате чего все записи становятся видимыми.

Проблема, которую вы описали, ни в коем случае не испортила пример. pop() Функция предназначена для удаления верхнего элемента, и она это сделает. Если, тем временем, элемент добавляется / удаляется, он его выдает, независимо от того, какой у него адрес (он может быть даже тем же, что был ранее выбран). Это совершенно другая проблема. Рассматривать:

concurrent_stack<int> p;
if (!p.empty() && (p.top() == 5))
{
auto t = p.pop();
assert( t ); // May fail
assert( *t == 5 ); // May fail
}

Оба утверждения могут потерпеть неудачу, и в случае, если многие потоки используют стек очень интенсивно, скорее всего, это будет довольно часто. Но это не из-за неправильной реализации pop(), но тот факт, что вам нужно более строгое ограничение доступа, чтобы последний проверенный элемент действительно был удален из стека.

5