Параллельное программирование на С++ в действии полностью

4. Вернуть поле data, хранящееся в извлеченном узле node.

5. Удалить извлеченный узел.

Однако наличие нескольких потоков осложняет дело. Если два потока пытаются удалить элементы из стека, то оба могут прочитать одно и то же значение head на шаге 1. Если затем один поток успеет выполнить все операции вплоть до шага 5, прежде чем другой доберется до шага 2, то второй поток попробует разыменовать висячий указатель. Это одна из самых серьезных проблем при написании кода, свободного от блокировок, поэтому пока мы просто опустим шаг 5, смирившись с утечкой узлов.

Однако на этом трудности не кончаются. Есть еще одна проблема: если два потока прочитают одно и то же значение head, то они вернут один и тот же узел. Это вступает в противоречие с самой идеей стека, поэтому должно быть предотвращено любой ценой. Решить проблему можно так же, как мы устранили гонку в push(): использовать для обновления head операцию сравнения с обменом. Если она завершается с ошибкой, значит, либо в промежутке был добавлен новый узел, либо другой поток только что извлек узел, который собирались извлечь мы. В любом случае нужно вернуться на шаг 1 (хотя операция сравнения с обменом автоматически перечитывает head).

Если сравнение с обменом завершилось успешно, то мы точно знаем, что больше ни один поток не пытался удалить данный узел из стека, поэтому можем без опаски выполнить шаг 4. Вот первая попытка написать код pop():

template

class lock_free_stack {

public:

 void pop(T& result) {

  node* old_head = head.load();

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

  result = old_head->data;

 }

};

Вроде бы всё красиво и лаконично, но, помимо утечки узлов, осталось еще две проблемы. Во-первых, этот код не работает для пустого списка: если указатель head нулевой, то при попытке прочитать next мы получим неопределённое поведение. Это легко исправить, сравнивая в цикле while значение head с nullptr: если стек оказался пуст, мы можем либо возбудить исключение, либо вернуть булевский индикатор успеха или ошибки.

Вторая проблема касается безопасности относительно исключений. Впервые подступаясь к потокобезопасному стеку в главе 3, мы видели, что простой возврат объекта по значению небезопасен относительно исключений: если исключение возникает во время копирования возвращаемого значения, то значение будет потеряно. Тогда передача ссылки на результат оказалась приемлемым решением, которое гарантировало неизменность стека в случае исключения. К сожалению, сейчас мы лишены такой роскоши; безопасно скопировать данные можно только тогда, когда мы точно знаем, что больше никакой поток не пытается вернуть данный узел, а это означает, что узел уже удален из стека. Следовательно, передача возвращаемого значения по ссылке больше не является преимуществом, с тем же успехом можно было бы вернуть его и по значению. Чтобы безопасно вернуть значение, придется воспользоваться другим вариантом, описанным в главе 3: возвращать интеллектуальный указатель на данные.

Возврат nullptr в качестве значения интеллектуального указателя будет означать, что данных в стеке нет, но беда в том, что теперь приходится выделять память из кучи. Если делать это в pop(), то получится, что мы ровным счетом ничего не выиграли, потому что выделение памяти может возбудить исключение. Вместо этого мы будем выделять память в push(), при помещении данных в стек — память-то для структуры node выделять приходится в любом случае. Возврат std::shared_ptr<> не возбуждает исключений, поэтому pop() теперь безопасна. Собрав все вместе, мы получим код, показанный в следующем листинге.

Листинг 7.3. Свободный от блокировок стек с утечкой узлов

template

class lock_free_stack {

private:

 struct node              (1) Теперь данные

 {                         │удерживаются

  std::shared_ptr data;←┘указателем

  node* next;

  node(T const& data_) :          (2) Создаем std::shared_ptr

   data(std::make_shared(data))←┤Для только что выде-

   {}                              │ленного T

 };

 std::atomic head;

public:

 void push(T const& data) {

  node* const new_node = new node(data);

  new_node->next = head.load();

  while (!head.compare_exchange_weak(new_node->next, new_node));

 }

 std::shared_ptr pop()

 {                                                        (3) Перед разыменованием