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

Рис. 7.1.На примере трех потоков, вызывающих pop(), видно, почему необходимо проверять threads_in_popпосле заявления прав на список узлов, ожидающих удаления, в try_reclaim()

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

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

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