Параллельное программирование на С++ в действии полностью

Если счетчик после уменьшения не равен нулю, то освобождать узлы небезопасно, поэтому если такие узлы есть (5), то нужно поместить их в начало списка ожидающих (6). Такое может случиться, если к структуре данных одновременно обращаются несколько потоков. Другие потоки могли вызвать pop() в промежутке между первой проверкой threads_in_pop (1) и «заявлением прав» на список (2) и добавить в список узлы, к которым все еще обращается один или несколько потоков. На рис. 7.1 поток С добавляет узел Y в список to_be_deleted, несмотря на то, что поток В все еще ссылается на него по указателю old_head и, значит, будет пробовать читать его указатель next. Поэтому поток А не может удалить узлы без риска вызвать неопределенное поведение в потоке В.

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