Lock-free stack: проблема видимости при проверке указателей опасности во время pop()?

Question

Я читаю Энтони Уильяма C++ Параллелизм в действии. В главе 7 описывается процесс создания стека блокировки и иллюстрируется общие проблемы, затрудняющие программирование без блокировки. В частности, раздел 7.2.3 (Обнаружение узлов, которые не могут быть восстановлены с помощью указателей опасности) описывает, как указатели опасности могут использоваться, чтобы избежать гонки данных, и убедитесь, что в других потоках нет delete узла, на который еще ссылается другой поток.

Этот код является одной из итераций pop() проиллюстрированные в этой главе:

std::shared_ptr<T> pop() 
{ 
    std::atomic<void*>& hp = get_hazard_pointer_for_current_thread(); 
    node* old_head = head.load(); 

    do 
    { 
    node* temp; 

    do 
    { 
     temp = old_head; 
     hp.store(old_head); 
     old_head = head.load(); 
    } while(old_head != temp); 
    } 
    while(old_head && 
    !head.compare_exchange_strong(old_head,old_head->next)); 

    hp.store(nullptr); 
    std::shared_ptr<T> res; 

    if(old_head) 
    { 
    res.swap(old_head->data); 

    if(outstanding_hazard_pointers_for(old_head)) 
    { 
     reclaim_later(old_head); 
    } 
    else 
    { 
     delete old_head; 
    } 

    delete_nodes_with_no_hazards(); 
    } 

    return res; 
} 

У меня есть сомнения по поводу этого фрагмента:

if(outstanding_hazard_pointers_for(old_head)) 
    { 
     reclaim_later(old_head); 
    } 
    else 
    { 
     delete old_head; 
    } 

Цель указателей опасности удостоверяется old_head удаляется, если другие потоки не могут его использовать. Предложенная реализация outstanding_hazard_pointers_for заключается в следующем:

unsigned const max_hazard_pointers=100; 
struct hazard_pointer 
{ 
    std::atomic<std::thread::id> id; 
    std::atomic<void*> pointer; 
}; 
hazard_pointer hazard_pointers[max_hazard_pointers]; 

bool outstanding_hazard_pointers_for(void* p) 
{ 
    for(unsigned i=0; i < max_hazard_pointers; ++i) 
    { 
    if(hazard_pointers[i].pointer.load() == p) 
    { 
     return true; 
    } 
    } 

    return false; 
} 

В основном, массив указателей опасности сканируется проверить, является ли указатель на узел искал присутствует. Мне интересно, почему эта операция действительно безопасна. Выполняется атомный load(), и даже если используется последовательное согласование, load() может загружать устаревшее значение. Как следствие, p не может быть найден, и pop() будет удалять узел, который все еще используется.

Представьте происходит следующее:

• Thread А начинает выполнять pop() и выгружается просто перед выполнением:

  while(old_head && 
      !head.compare_exchange_strong(old_head,old_head->next)); 
  

  Поток А, таким образом, видит текущую голову как old_head, который сохранен в указателе опасности. old_head будет разыменовываться, когда поток просыпается и пытается вытолкнуть голову, ссылаясь на head.compare_exchange_strong(old_head, old_head->next).

• резьбы В начинает применение pop() вниз к

  if(outstanding_hazard_pointers_for(old_head)) 
  

  old_head будет нынешний глава стека, то есть тот же узел, что поток А ссылается, как old_head. Тема Б неdelete old_head тогда и только тогда в load() по указателю опасности нитяных возвращает последнее значение, сохраненным с помощью резьбы А.

В основном: Я интересно ли Thread В может load() черствое значение вместо последнего одного , С другой стороны, я не уверен, почему у этого есть, чтобы вернуть значение, заданное Thread A (old_node).

Где ошибка в этом рассуждении? Я не могу найти обоснования относительно того, почему hp.store(old_head) на другой поток произойдет до hazard_pointers[i].pointer.load().

Answer 1

Я отвечаю на свой вопрос по двум причинам: я думаю, что ответ, который я принял, не очень ясен, и JJ15k's comment подтверждает это впечатление.

В основном ключ наблюдение, что для другого потока, чтобы сделать это через if(outstanding_hazard_pointers_for(old_head))и видя же old_head видели другой поток, который был вытеснен перед выполнением while(old_head && !head.compare_exchange_strong(old_head, old_head->next)), он должен быть выполнен head.compare_exchange_strong(old_head, old_head->next) с тем же old_head. Но тогда (предполагая, что < указывает происходит, прежде чем отношения):

thread A: hp.store(old_head)  < 
thread A: old_head = head.load() < 
thread B: head.compare_exchange_strong(old_head, old_head->next) 

Помните, что поток B видит жеold_head мы загрузили в первой инструкции, и это замена это значение old_head->next. Мы по-прежнему видим одно и то же значение в head.load(), поэтому это Thread A hp.store(old_head) происходит до Thread B compare_exchange_strong.

Так что нить, которая собирается проверить, может ли быть удалена голова, содержащаяся в указателе опасности, имеет, чтобы посмотреть old_head. Также обратите внимание на основную роль, которую играет old_head = head.load() (и цикл, который содержит те утверждения, которые могут показаться излишними с первого взгляда). Без этого load операции не было бы до отношения между store от old_head до hp и compare_exchange_strong.

Надеюсь, это ответит на ваш вопрос.

Answer 2

Мое понимание кода следующее.

Если hp.store(old_head) в другой цепочке НЕ случится - до вызова hazard_pointers[i].pointer.load() в этой ветке, это означает, что этот поток успешно выполнен. head.compare_exchange_strong(old_head,old_head->next) call. Это означает, что для другого потока old_head != temp, так что он выполнит еще одну попытку сохранить нужный old_head в качестве потока hp.

И это означает, что указатель оригинала old_head в текущем потоке можно безопасно удалить, так как он фактически не используется другим потоком.