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

Прежде чем менять схему упорядочения, нужно исследовать все операции и определить, какие между ними должны быть отношения. Затем можно будет вернуться и найти минимальное упорядочение, которое эти отношения обеспечивает. Чтобы это сделать, потребуется взглянуть на ситуацию с точки зрения потоков в нескольких разных сценариях. Простейший сценарий возникает, когда один поток помещает элемент данных в стек, а другой через некоторое время извлекает его оттуда, с него и начнем.

В этом сценарии есть три существенных участника. Во-первых, структура counted_node_ptr, используемая для передачи данных — узла head. Во-вторых, структура node, на которую headссылается. И, в-третьих, сами данные, на которые указывает узел.

Поток, выполняющий push(), сначала конструирует элемент данных и объект node, затем устанавливает head. Поток, выполняющий pop(), сначала загружает значение head, затем в цикле сравнения с обменом увеличивает хранящийся в нем счетчик ссылок, после чего читает структуру node, чтобы извлечь из нее значение next. Из этой последовательности можно вывести требуемое отношение; значение next— простой неатомарный объект, поэтому для его безопасного чтения должно существовать отношение происходит-раньше между операциями сохранения (в заталкивающем потоке) и загрузки (в выталкивающем потоке). Поскольку в push()имеется единственная атомарная операция — compare_exchange_weak(), а для существования отношения происходит-раньше между потоками нам нужна операция освобождения (release), то для функции compare_exchange_weak()необходимо задать упорядочение std::memory_order_releaseили более сильное. Если compare_exchange_weak()вернула false, то ничего не было изменено, и мы можем продолжить цикл, следовательно в этом случае нужна только семантика std::memory_order_relaxed:

void push(T const& data) {

counted_node_ptr new_node;

new_node.ptr = new node(data);

new_node.external_count = 1;

new_node.ptr->next = head.load(std::memory_order_relaxed);

while (!head.compare_exchange_weak(

new_node.ptr->next, new_node,

std::memory_order_release, std::memory_order_relaxed));

}

А что можно сказать о коде pop()? Чтобы получить желаемое отношение происходит-раньше, перед доступом к nextнеобходима операция с семантикой std::memory_order_acquireили более сильной. Указатель, который разыменовывается для доступа к полю next, — это прежнее значение, прочитанное операцией compare_exchange_strong()в increase_head_count(), поэтому указанная семантика нужна в случае успеха. Как и в push(), если обмен закончился неудачно, мы просто повторяем цикл, поэтому для отказа можно задать ослабленное упорядочение:

void increase_head_count(counted_node_ptr& old_counter) {

counted_node_ptr new_counter;

do {

new_counter = old_counter;

++new_counter.external_count;

}

while (!head.compare_exchange_strong(

old_counter, new_counter,

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

old_counter.external_count = new_counter.external_count;

}

Если вызов compare_exchange_strong()завершается успешно, то мы знаем, что раньше в поле ptrпрочитанного значения находилось то, что теперь хранится в переменной old_counter. Поскольку сохранение в push()было операцией освобождения, а данный вызов compare_exchange_strong()— операция захвата, то сохранение синхронизируется-с загрузкой, и мы имеем отношение происходит-раньше. Следовательно, сохранение в поле ptrв push()происходит-раньше доступа к ptr->nextв pop(), и мы в безопасности.

Отметим, что для этого анализа порядок доступа к памяти в начальном вызове head.load()не имел значения, поэтому в нем безопасно задать семантику std::memory_order_relaxed.

Далее на очереди операция compare_exchange_strong(), которая записывает в headзначение old_head.ptr->next. Нужно ли наложить на нее какие-нибудь ограничения, чтобы гарантировать целостность данных в этом потоке? Если обмен завершается успешно, то мы обращаемся к ptr->data, поэтому должны быть уверены, что сохранение ptr->dataв потоке, выполняющем push(), происходит-раньше загрузки. Но такая уверенность уже есть: операция захвата в increase_head_count()гарантирует, что существует отношение синхронизируется-с между сохранением в потоке, выполняющем push(), и операцией сравнения с обменом. Поскольку сохранение данных в потоке, выполняющем push(), расположено перед сохранением head, а вызов increase_head_count()расположен перед загрузкой ptr->data, то отношение происходит-раньше имеет место, и всё будет хорошо, даже если для операции сравнения с обменом в pop()задана семантика std::memory_order_relaxed. Есть еще всего одно место, где изменяется ptr->data— тот самый вызов swap(), на который вы сейчас смотрите, и ни один другой поток не может оперировать тем же узлом — в этом и заключается смысл сравнения с обменом.