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

Чтобы поместить узлы, ожидающие удаления, в список ожидающих, мы используем уже имеющийся указатель nextдля связывания. Для того чтобы добавить цепочку в список, мы проходим до конца цепочки (9), записываем в указатель nextв последнем узле текущее значение to_be_deleted (10)и сохраняем указатель на первый узел цепочки как новый указатель to_be_deleted (11). Здесь необходимо вызывать compare_exchange_weakв цикле, чтобы не допустить утечки узлов, добавленных другим потоком. В результате в nextзаписывается указатель на последний узел цепочки, если он изменился. Добавление единственного узла в список — это особый случай, когда первый узел в добавляемой цепочке совпадает с последним (12).

Этот алгоритм работает вполне приемлемо, если нагрузка невелика, то есть существуют моменты затишья , когда в pop()нет ни одного потока. Но эта ситуация кратковременна; именно поэтому мы должны проверять, что счетчик threads_in_popпосле уменьшения обратился в нуль (3), прежде чем освобождать память, и по той же причине проверка стоит до удаления только что изъятого из стека узла (7). Удаление узла может занять относительно много времени, а мы хотим, чтобы окно, в котором другие потоки могут модифицировать список, было как можно короче. Чем больше времени проходит между моментом, когда поток впервые обнаружил, что threads_in_popравно 1, и попыткой удалить узлы, тем больше шансов, что какой-то другой поток вызовет pop(), после чего threads_in_popперестанет быть равно 1 и, стало быть, удалять узлы станет нельзя.

Если нагрузка высока, то затишье может не наступить никогда , поскольку новые потоки входят в pop()до того, как пребывавшие там успевают выйти. В таком случае список to_be_deletedбудет расти неограниченно, и мы снова сталкиваемся с утечкой памяти. Если периодов затишья не ожидается, то необходим другой механизм освобождения узлов. Главное здесь — определить, когда ни один поток больше не обращается к конкретному узлу, который, следовательно, можно освободить. Из всех возможных механизмов такого рода для понимания проще всего тот, в котором используются указатели опасности (hazard pointers).

Термин указатели опасности откосится к технике, предложенной Магедом Майклом (Maged Michael) [12] «Safe Memory Reclamation for Dynamic Lock-Free Objects Using Atomic Reads and Writes», Maged M. Michael, в сборнике PODC '02: Proceedings of the Twenty-first Annual Symposium on Principles of Distributed Computing (2002), ISBN 1-58113-485-1. . Они называются так потому, что удаление узла, на который все еще могут ссылаться другие потоки, — опасное предприятие. Если действительно существует поток, ссылающийся на данный узел, и этот поток попытается обратиться к нему по ссылке, то мы получим неопределенное поведение. Основная идея заключается в том, что поток, собирающийся получить доступ к объекту, который другой поток может захотеть удалить, сначала устанавливает указатель опасности, ссылающийся на этот объект, информируя тем самым другой поток, что удалять этот объект действительно опасно. После того как объект перестает быть нужным, указатель опасности очищается. Если вам доводилось наблюдать гребную регату между командами Оксфорда и Кембриджа, то вы могли видеть аналогичный механизм, применяемый в начале заезда: рулевой в лодке может поднять руку, сообщая, что экипаж еще не готов. Пока хотя бы один рулевой держит руку поднятой, судья не может дать старт заезду. После того как оба рулевых опустят руки, судья может давать старт, однако рулевой вправе снова поднять руку, если заезд еще не начался, а ситуация, на его взгляд, изменилась.

Собираясь удалить объект, поток должен сначала проверить указатели опасности в других имеющихся в системе потоках. Если ни один из указателей опасности не ссылается на данный объект, то его можно спокойно удалять. В противном случае удаление следует отложить. Периодически поток просматривает список отложенных объектов в поисках тех, которые уже можно удалить.

Высокоуровневое описание выглядит достаточно простым, но как это сделать на С++?

Прежде всего, необходимо место для хранения указателя на интересующий нас объект — сам указатель опасности . Это место должно быть видно из всех потоков, причем указатель опасности должен существовать в каждом потоке, который может получить доступ к структуре данных. Корректное и эффективное выделение такого места — непростая задача, поэтому отложим ее на потом, а пока предположим, что существует функция 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(), реализованной по такой схеме.