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

Листинг 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(), этот узел больше никого не интересует, и его можно безопасно удалить.

С другой стороны, если мы все-таки хотим, чтобы несколько потоков могли одновременно вызывать pop(), то нужно каким-то образом отслеживать момент, когда удаление узла становится безопасным. По сути дела, это означает, что необходимо написать специализированный сборщик мусора для узлов node. Звучит пугающе, и эта задача действительно не самая простая, но на практике все не так плохо: мы проверяем только указатели на nodeи только те узлы, к которым обращается pop(). Нас не интересуют узлы внутри push(), потому что они доступны только одному потоку, пока не окажутся в стеке. А вот внутри pop()к одному и тому же узлу могут одновременно иметь доступ несколько потоков.

Если потоков, вызывающих pop(), нет вообще, то можно без опаски удалить все узлы, ожидающие удаления. Поэтому, если после извлечения данных помещать узлы в список «подлежат удалению», то их можно будет удалить одним махом в момент, когда не будет потоков, вызывающих pop(). Но как узнать, что потоков, вызывающих pop(), действительно нет? Очень просто — подсчитывать их. Если увеличивать счетчик при входе и уменьшать при выходе, то удалять узлы из списка «подлежащих удалению» можно будет, когда счетчик становится равным нулю. Разумеется, сам счетчик должен быть атомарным, чтобы к нему можно было безопасно обращаться из нескольких потоков. В листинге 7.4 показала исправленная функция pop(), а в листинге 7.5 — вспомогательные функции, используемые в ее реализации.

Листинг 7.4.Освобождение занятой узлами памяти в момент, когда нет потоков, вызывающих pop()