Можно застрять в l oop Compare_exchange?

Question

Рассмотрим этот код (из «Параллелизм C ++ в действии» [Второе издание]: стр. 212 ):

void LockFreeStack::pop (stack_data& result)
{
    Node* old_head = head.load();
    while(!head.compare_exchange_weak(old_head, old_head->next))
        ;
    result = old_head->data;
}

Я думаю, что возможно выполнение одного потока pop() и после выполнения первой строки (загрузка head) квантование времени произошло со вторым потоком, который выполняет push(T&). Так что теперь значение переменной head atomi c не равно old_head и while -l oop не сломается.
Это верно?

Answer 1

при условии, что head является std::atomic<Node*>, тогда код верен, например, при сбое compare_exchange_weak загружается текущее значение переменной в ее первый параметр после вызова compare_exchange_weak old_head всегда будет содержать текущее значение head.

Код примерно эквивалентен выполнению следующего без атомики:

Node* old_head = head;
while (true)
{
  std::unique_lock lock(mutex);
  if (old_head == head)
  {
     head = old_head->next;
     break;
  }
  else
  {
     old_head = head;
  }
}

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

Answer 2

Как уже объяснил @Alan Birtles, вы не будете застревать в то время как -l oop. Однако важно отметить, что ваш код, скорее всего, будет страдать от проблемы ABA. Рассмотрим следующий сценарий:

• стек выглядит следующим образом: A->B->C (т. Е. Заголовок указывает на A)
• поток 1 загружает головку (т. Е. Адрес A) и следующий указатель A (B), но прежде чем он сможет выполнить CAS, он прерывается.
• поток 2 выскакивает A, затем B и затем нажимает A, т. Е. Стек теперь выглядит следующим образом: A->C
• поток 1 возобновляет и успешно обновляет голову с A до B -> boom!

Существует несколько возможных решений, позволяющих избежать проблемы ABA, например, теговые указатели или схемы одновременного восстановления памяти.