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

Прежде всего, необходимо место для хранения указателя на интересующий нас объект — сам указатель опасности . Это место должно быть видно из всех потоков, причем указатель опасности должен существовать в каждом потоке, который может получить доступ к структуре данных. Корректное и эффективное выделение такого места — непростая задача, поэтому отложим ее на потом, а пока предположим, что существует функция get_hazard_pointer_for_current_thread(), которая возвращает ссылку на указатель опасности. Затем нужно установить указатель опасности перед чтением указателя, который мы намерены разыменовать, — в данном случае указателя headна начало списка:

std::shared_ptr pop() {

std::atomic& hp =

get_hazard_pointer_for_current_thread();

node* old_head = head.load();← (1)

node* temp;

do {

temp = old_head;

hp.store(old_head); ← (2)

old_head = head.load();

} while (old_head != temp); ← (3)

// ...

}

Это необходимо делать в цикле while, чтобы узел nodeслучайно не был удалён между чтением старого указателя head (1)и установкой указателя опасности (2). В течение этого промежутка времени ни один поток не знает, что мы собираемся обратиться к этому узлу. К счастью, если кто-то собирается удалить старый узел head, то сам указатель headдолжен был быть изменен, так что мы можем это проверить и не выходить из цикла, пока не будем твердо уверены, что указатель headпо-прежнему имеет то же значение, которое было записано в указатель опасности (3). Такое использование указателей опасности опирается на тот факт, что можно безопасно использовать значение указателя даже после того, как объект, на который он указывает, уже удалён. Технически для стандартных реализаций newи deleteэто считается неопределенным поведением, поэтому либо убедитесь, что ваша реализация стандартной библиотеки допускает такое использование, либо реализуйте собственный распределитель.

Установив указатель опасности, мы можем продолжить выполнение pop(), будучи уверены, что ни один другой поток не попытается «вытащить» из-под нас узлы. Ну почти уверены: при каждом перечитывании old_headнеобходимо обновлять указатель опасности перед тем, как разыменовывать вновь прочитанное значение указателя. После того как узел извлечён из списка, мы можем очистить наш собственный указатель опасности. Если на наш узел не ссылаются другие указатели опасности, то его можно удалять; в противном случае его следует поместить в список узлов, ожидающих удаления. В листинге ниже приведен полный код функции pop(), реализованной по такой схеме.

Листинг 7.6.Реализация функции pop()с помощью указателей опасности

std::shared_ptr pop() {

std::atomic& hp =

get_hazard_pointer_for_current_thread();

node* old_head = head.load();

do {

node* temp; (1) Цикл, пока указатель

do ←┤ опасности не установлен

{ │ на head

temp = old_head;

hp.store(old_head);

old_head = head.load();

} while (old_head != temp);

}

while (old_head &&

!head.compare_exchange_strong(old_head, old_head->next))

hp.store(nullptr);← (2) Закончив, очищаем указатель опасности

std::shared_ptr res;

if (old_head) {

res.swap(old_head->data);

if (outstanding_hazard_pointers_for(old_head))←┐ Прежде чем

{ ├ (3) удалять узел,

reclaim_later(old_head); │ проверяем, ← (4)

} │ нет ли ссы-

else │ лающихся на

{ │ него указате-

│ лей опасности

delete old_head; ← (5)

}

delete_nodes_with_no_hazards();← (6)

}

return res;

}

Начнём с того, что мы перенесли цикл, в котором устанавливается указатель опасности, во внешний цикл, где перечитывается old_head, если операция сравнения с обменом завершается неудачно (1). Здесь мы используем функцию compare_exchange_strong(), потому что фактическая работа делается внутри цикла while: ложный отказ в compare_exchange_weak()привел бы к ненужному сбросу указателя опасности. Таким образом, гарантируется, что указатель опасности установлен перед разыменованием old_head. Заявив свои права на узел, мы можем очистить указатель опасности (2). Получив узел в свое распоряжение, мы должны проверить, не ссылаются ли на него указатели опасности, принадлежащие другим потокам (3). Если это так, то удалять узел пока нельзя, а нужно поместить его в список ожидающих (4); в противном случае узел можно удалять немедленно (5). Наконец, мы добавили вызов функции, в которой проверяется, существуют ли узлы, для которых мы ранее вызывали reclaim_later(). Если не осталось указателей опасности, ссылающихся на эти узлы, то мы можем спокойно удалить их (6). Те же узлы, на которые еще ссылается хотя бы один указатель опасности, остаются в списке и будут проверены следующим потоком, вызвавшим pop().