Увеличив счетчик, мы можем без опаски разыменовать поле ptr объекта, загруженного из head, и получить тем самым доступ к адресуемому узлу (2). Если оказалось, что указатель нулевой, то мы находимся в конце списка — больше записей нет. В противном случае мы можем попытаться исключить узел из списка, выполнив compare_exchange_strong() с головным узлом head (3).
Если compare_exchange_strong() возвращает true, то мы приняли на себя владение узлом и можем с помощью функции swap() вытащить из него данные, которые впоследствии вернём (4). Тем самым гарантируется, что данные случайно не изменятся, если вдруг другие обращающиеся к стеку другие потоки удерживают указатели на этот узел. Затем можно прибавить внешний счетчик к внутреннему с помощью атомарной операции fetch_add (6). Если теперь счетчик ссылок стал равен нулю, то fetch_add) было противоположно только что прибавленному, и тогда узел можно удалять. Важно отметить, что прибавленное значение на самом деле
Если сравнение с обменом (3) head, которое вернула функция compare_exchange_strong(). Но прежде необходимо уменьшить счетчик ссылок на узел, который мы пытались исключить раньше. Этот поток больше не будет к нему обращаться. Если наш поток — последний, удерживавший ссылку на этот узел (потому что другой поток вытолкнул его из стека), то внутренний счетчик ссылок равен 1, так что после вычитания 1 он обратится в нуль. В таком случае мы можем удалить узел прямо здесь, не дожидаясь перехода к следующей итерации цикла (8).
До сих мы задавали для всех атомарных операций упорядочение доступа к памяти std::memory_order_seq_cst. В большинстве систем это самый неэффективный режим с точки зрения времени выполнения и накладных расходов на синхронизацию, причем в ряде случаев разница весьма ощутима. Но теперь, определившись с логикой структуры данных, можно подумать и о том, чтобы ослабить некоторые требования к упорядочению, — все-таки не хотелось бы, чтобы пользователи стека несли лишние расходы. Итак, перед тем как расстаться со стеком и перейти к проектированию свободной от блокировок очереди, еще раз присмотримся к операциям стека и спросим себя, нельзя ли где-нибудь использовать более слабое упорядочение доступа, сохранив тот же уровень безопасности?
Прежде чем менять схему упорядочения, нужно исследовать все операции и определить, какие между ними должны быть отношения. Затем можно будет вернуться и найти минимальное упорядочение, которое эти отношения обеспечивает. Чтобы это сделать, потребуется взглянуть на ситуацию с точки зрения потоков в нескольких разных сценариях. Простейший сценарий возникает, когда один поток помещает элемент данных в стек, а другой через некоторое время извлекает его оттуда, с него и начнем.
В этом сценарии есть три существенных участника. Во-первых, структура counted_node_ptr, используемая для передачи данных — узла head. Во-вторых, структура node, на которую head ссылается. И, в-третьих, сами данные, на которые указывает узел.
Поток, выполняющий push(), сначала конструирует элемент данных и объект node, затем устанавливает head. Поток, выполняющий pop(), сначала загружает значение head, затем в цикле сравнения с обменом увеличивает хранящийся в нем счетчик ссылок, после чего читает структуру node, чтобы извлечь из нее значение next. Из этой последовательности можно вывести требуемое отношение; значение next — простой неатомарный объект, поэтому для его безопасного чтения должно существовать отношение происходит-раньше между операциями сохранения (в заталкивающем потоке) и загрузки (в выталкивающем потоке). Поскольку в push() имеется единственная атомарная операция — compare_exchange_weak(), а для существования отношения происходит-раньше между потоками нам нужна операция compare_exchange_weak() необходимо задать упорядочение std::memory_order_release или более сильное. Если compare_exchange_weak() вернула false, то ничего не было изменено, и мы можем продолжить цикл, следовательно в этом случае нужна только семантика std::memory_order_relaxed:
