В чем смысл этого цикла for в реализации очереди без блокировки в книге «Параллелизм C++ в действии»?
Я читаю книгу Энтони Уильямса «Параллелизм на C++ в действии, второе издание» и столкнулся с этим кодом:
template<typename T>
class lock_free_queue
{
private:
void set_new_tail(counted_node_ptr &old_tail,
counted_node_ptr const &new_tail)
{
node* const current_tail_ptr=old_tail.ptr;
while(!tail.compare_exchange_weak(old_tail,new_tail) &&
old_tail.ptr==current_tail_ptr);
if (old_tail.ptr==current_tail_ptr)
free_external_counter(old_tail);
else
current_tail_ptr->release_ref();
}
public:
void push(T new_value)
{
std::unique_ptr<T> new_data(new T(new_value));
counted_node_ptr new_next;
new_next.ptr=new node;
new_next.external_count=1;
counted_node_ptr old_tail=tail.load();
for(;;)
{
increase_external_count(tail,old_tail);
T* old_data=nullptr;
if (old_tail.ptr->data.compare_exchange_strong(
old_data,new_data.get()))
{
counted_node_ptr old_next = {0};
if (!old_tail.ptr->next.compare_exchange_strong(
old_next,new_next))
{
delete new_next.ptr;
new_next=old_next;
}
set_new_tail(old_tail, new_next);
new_data.release();
break;
}
else
{
counted_node_ptr old_next = {0};
if (old_tail.ptr->next.compare_exchange_strong(
old_next,new_next))
{
old_next=new_next;
new_next.ptr=new node;
}
set_new_tail(old_tail, old_next);
}
}
}
};
Оставшаяся часть находится в GitHub, то есть с listing_7.19.cpp по listing_7.22.cpp.
Здесь я сталкиваюсь с некоторыми проблемами, которые я не могу понять в этой части:
for(;;)
{
increase_external_count(tail,old_tail);
T* old_data=nullptr;
if (old_tail.ptr->data.compare_exchange_strong(
old_data,new_data.get()))
{
counted_node_ptr old_next = {0};
if (!old_tail.ptr->next.compare_exchange_strong(
old_next,new_next))
{
delete new_next.ptr;
new_next=old_next;
}
set_new_tail(old_tail, new_next);
new_data.release();
break;
}
else
{
counted_node_ptr old_next = {0};
if (old_tail.ptr->next.compare_exchange_strong(
old_next,new_next))
{
old_next=new_next;
new_next.ptr=new node;
}
set_new_tail(old_tail, old_next);
}
}
Во-первых, я думаю, что old_tail не является нулевым, почему в этом выражении это сравнивается с old_data (который является nullptr)?
if (old_tail.ptr->data.compare_exchange_strong( old_data,new_data.get()))
И что на самом деле делает приведенный выше цикл for?
Я совершенно не могу этого понять.
Я не могу понять, почему мы устанавливаем ожидаемое значение как nullptr в T* old_data=nullptr; if (old_tail.ptr->data.compare_exchange_strong( old_data,new_data.get())) @DrewDormann
Ответы 2
Я не смотрел код GitHub, но, по-видимому, ld_tail.ptr->data — это std::atomic, и в этом случае Compare_exchange_strong() принимает ссылку на переменную в своем первом параметре и обновит эту переменную результатом сравнения.
Атомарно сравнивает [представление объекта (до C++20)] [представление значения (начиная с C++20)]
*thisс представлениемexpected. Если они побитово равны, первый заменяется наdesired(выполняет операцию чтения-изменения-записи). В противном случае фактическое значение, хранящееся в*this, загружается вexpected(выполняется операция загрузки).
Итак, инициализация переменной old_data с помощью nullptr сначала означает, что автор проверяет, имеет ли атомарная data значение nullptr или нет. Если да, то data будет обновлено значением второго параметра (new_data).
Цикл for повторяет попытку обновления, пока оно не произойдет.
Если вопрос в том, зачем это писать:
T* old_data=nullptr;
if (old_tail.ptr->data.compare_exchange_strong(old_data,new_data.get()))
//...
Вместо того, чтобы сказать это:
if (old_tail.ptr->data.compare_exchange_strong(nullptr,new_data.get()))
//...
Это потому, что compare_exchange_strong() возвращает значение в точке сравнения в первом аргументе, поэтому для него требуется изменяемое l-значение (ссылка).
В примере кода возвращаемое значение не используется. Но не существует версии члена, которая принимает константу.
Если вопрос «что делает цикл for(;;)?»
Ответ заключается в использовании compare_exchange_strong(), чтобы попытаться стать потоком, который либо заполняет данные в хвосте, либо добавляет новый хвост для заполнения.
Логика не блокируется (если соответствующие атомарные операции на целевой платформе не блокируются - это не гарантируется), но недостатком является то, что может потребоваться несколько попыток (итераций), чтобы поток стал «победителем», а при высокой нагрузке существует риск « live lock», поскольку не гарантируется успех данного потока.
Реализации без блокировки кажутся привлекательными, но иногда имеют недостатки, которые могут быть хуже, чем блокировка и выполнение работы за один проход.
Конечно, введение блокировки в виде std::mutex не гарантирует какой-либо справедливости, и (опять же) сценарии с высокой нагрузкой могут привести к поведению живой блокировки. Но дело в том, что показанная реализация не обязательно является панацеей.
Этот код демонстрирует первый пункт:
#include <iostream>
#include <atomic>
int main() {
int value1{1};
int value2{2};
std::atomic<int *> x(&value1);
int * e=nullptr;
auto r{x.compare_exchange_strong(e,&value2)};
std::cout<<r<<' '<<e<<' '<<&value1<<'\n';
return 0;
}
Типичный результат:
0 0x7ffe378b5340 0x7ffe378b5340
Обратите внимание, что адрес, возвращаемый для e, является адресом value1.
Пожалуйста, по одному вопросу на вопрос! Вы спрашиваете, что именно делает
compare_exchange_strong? Или вы просите нас объяснить весь циклfor(;;)?