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

Question

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

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 узел подвержен проблеме ABA. Даже если значение head остается прежним, узел, на который он изначально указывает, возможно, был удален. Новый head выделен узел, который имеет то же значение адреса, что и предыдущий.

Answer 1

По умолчанию 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(), но тот факт, что вам нужно более строгое ограничение доступа, чтобы последний проверенный элемент действительно был удален из стека.