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

new_counter = old_counter;

--new_counter.internal_count; ← (1)

}

while (!count.compare_exchange_strong(← (2)

old_counter, new_counter,

std::memory_order_acquire, std::memory_order_relaxed));

if (

!new_counter.internal_count &&

!new_counter.external_counters) {

delete this; ← (3)

}

}

};

};

Реализация node::release_ref()лишь немногим отличается от аналогичного кода в lock_free_stack::pop()(см. листинг 7.11). Там мы работали с единственным внешним счетчиком, поэтому достаточно было вызвать fetch_sub. Здесь же необходимо атомарно обновить всю структуру count, хотя в действительности мы хотим модифицировать только поле internal_count (1). Поэтому никуда не деться от цикла сравнения с обменом (2). Если после уменьшения internal_countоказалось, что и внутренний, и внешний счетчик равны нулю, то это была последняя ссылка, и мы можем удалять узел (3).

Листинг 7.18.Получение новой ссылки на узел в очереди без блокировок

template

class lock_free_queue {

private:

static void increase_external_count(

std::atomic& counter,

counted_node_ptr& old_counter) {

counted_node_ptr new_counter;

do {

new_counter = old_counter;

++new_counter.external_count;

}

while (!counter.compare_exchange_strong(

old_counter, new_counter,

std::memory_order_acquire, std::memory_order_relaxed));

old_counter.external_count = new_counter.external_count;

}

};

Листинг 7.18 завершает картину. На этот раз мы не освобождаем ссылку, а получаем новую и увеличиваем внешний счетчик. Функция increase_external_count()аналогична increase_head_count()из листинга 7.12, отличаясь от нее тем, что преобразована в статическую функцию-член, которая принимает подлежащий обновлению внешний счетчик извне, а не оперирует внутренним членом класса.

Листинг 7.19.Освобождение счётчика внешних ссылок на узел в очереди без блокировок

template

class lock_free_queue {

private:

static void free_external_counter(

counted_node_ptr &old_node_ptr) {

node* const ptr = old_node_ptr.ptr;

int const count_increase = old_node_ptr.external_count — 2;

node_counter old_counter =

ptr->count.load(std::memory_order_relaxed);

node_counter new_counter;

do {

new_counter = old_counter;

--new_counter.external_counters; ← (1)

new_counter.internal_count += count_increase;← (2)

}

while (!ptr->count.compare_exchange_strong( ← (3)

old_counter, new_counter,

std::memory_order_acquire, std::memory_order_relaxed));

if (!new_counter.internal_count &&

!new_counter.external_counters) {

delete ptr;← (4)

}

}

};

Функция free_external_counter()дополняет increase_external_count(). Она аналогична эквивалентной функции из реализации lock_free_stack::pop()в листинге 7.11, но модифицировала с учетом появления поля external_counters. Она обновляет оба счетчика в одном вызове compare_exchange_strong()для всей структуры count (3)— точно так же мы поступали при уменьшении internal_countв release_ref(). Значение internal_countобновляется, как в листинге 7.11 (2), a external_countersуменьшается на единицу (1). Если теперь оба значения равны нулю, значит, ссылок на узел не осталось, поэтому его можно удалять (4). Оба обновления необходимо выполнять в одном действии (потому и нужен цикл сравнения с обменом), чтобы избежать гонки. Если бы счетчики обновлялись порознь, то два разных потока могли бы решить, что владеют последней ссылкой на узел, и удалить его, что привело бы к неопределенному поведению.

Хотя теперь функция работает и свободна от блокировок, осталась еще одна проблема, касающаяся производительности. После того как один поток начал операцию push(), успешно выполнив compare_exchange_strong()от имени old_tail.ptr->data(точка (5)в листинге 7.15), никакой другой войти в push()не может. Попытавшись это сделать, поток увидит новое значение, отличное от nullptr, в результате чего вызов compare_exchange_strong()вернет false, и потоку придется начать цикл заново. Это активное ожидание, которое только потребляет время процессора, не продвигаясь вперед ни на йоту. По сути дела, это блокировка. Первый удачный вызов push()блокирует все остальные потоки, пока не завершится, так что этот код более не свободен от блокировок . Хуже того — обычно операционная система может отдать приоритет потоку, удерживающему мьютекс, если существуют заблокированные потоки, но только не в данном случае, поэтому остальные потоки так и будут пожирать процессорное время, пока первый не закончит. И тут мы вытащим на свет очередной припасенный для освобождения от блокировок трюк: ожидающий поток может помочь потоку, который выполняет push().