Энтони Уильямс - Параллельное программирование на С++ в действии. Практика разработки многопоточных программ

Теперь, когда у нас есть средства для добавления данных в стек, надо научиться их извлекать обратно. На первый взгляд, тут всё просто.

1. Прочитать текущее значение head.

2. Прочитать head->next.

3. Записать в headзначение head->next.

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) Перед разыменованием

node* old_head = head.load();│ проверяем, что old_head—

while (old_head && ←┘ ненулевой указатель

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

return old_head ? old_head->data : std::shared_ptr();← (4)

}

};

Теперь данные удерживаются указателем (1), поэтому мы должны выделять память для них из кучи в конструкторе узле (2). Кроме того, перед тем как разыменовывать old_headв цикле compare_exchange_weak() (3), следует проверять указатель на нуль. Наконец, мы либо возвращаем ассоциированные с узлом данные, если узел имеется, либо нулевой указатель, если его нет (4). Отметим, что этот алгоритм свободен от блокировок , но не свободен от ожидания , потому что цикл whileв push()и pop()теоретически может выполняться бесконечно, если compare_exchange_weak()будет каждый раз возвращать false.

Если бы у нас был сборщик мусора (как в управляемых языках типа С# или Java), то на этом можно было бы ставить точку — старый узел был бы убран и повторно использован после того, как все потоки перестанут к нему обращаться. Но сегодня мало найдётся компиляторов С++ с встроенным сборщиком мусора, поэтому прибираться за собой нужно самостоятельно.

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

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