Стек без блокировки C 11

#c 11 #stack #lock-free

#c 11 #стек #без блокировки

Вопрос:

Я читаю параллелизм C в действии Энтони Уильямса и не понимаю его push реализацию lock_free_stack класса.

С какой стати atomic load не находится в цикле while? Причина, которую он привел, заключается в:

Поэтому вам не нужно перезагружать head каждый раз в цикле, потому что компилятор делает это за вас.

Но я не понимаю картину. Может ли кто-нибудь пролить свет на это?

 template<typename T>
class lock_free_stack
{
private:
 struct node
 {
   T data;
   node* next;
   node(T constamp; data_) : 
     data(data_)
   {}
 };
 std::atomic<node*> head;
public:
 void push(T constamp; data)
 {
   node* const new_node=new node(data); 
   new_node->next=head.load(); 
   while(!head.compare_exchange_weak(new_node->next,new_node)); 
 }
};
  

Ответ №1:

Ключ находится в интерфейсе к compare_exchange_weak , который в этом случае принимает 2 аргумента. Первое — это ссылка на ожидаемое значение, а второе — на желаемое. Если текущее значение atomic не равно ожидаемому вводу, оно вернет false, и ожидаемый ввод будет установлен на текущее значение.

Итак, в этом случае то, что он делает, — это настройка new_node->next = head . Затем он говорит, что если head значение по-прежнему равно new_node->next , замените его на head . Если это больше не то значение, оно использует ссылку на new_node->next , чтобы присвоить ему текущее значение head . Поскольку каждая итерация цикла, в котором происходит сбой, также заменяет new_node->next текущее значение head , нет чтения для дублирования этого в теле цикла.

Комментарии:

1. Да, теперь это имеет смысл. Спасибо!

Ответ №2:

Из документации compare_exchange_weak :

Атомарно сравнивает значение, сохраненное в *this, со значением expected , и, если они равны, заменяет первое на желаемое (выполняет операцию чтения-изменения-записи). В противном случае загружает фактическое значение, сохраненное в *this, в ожидаемое (выполняет операцию загрузки).

Как вы видите, в противном случае фактическое значение head загружается в ожидаемое.