В предыдущей статье мы заглянули внутрь процессора, пусть и гипотетического. Мы выяснили, что для корректного выполнения параллельного кода процессору необходимо подсказывать, до каких пределов ему разрешено проводить свои внутренние оптимизации чтения/записи. Эти подсказки – барьеры памяти. Барьеры памяти позволяют в той или иной мере упорядочить обращения к памяти (точнее, кэшу, — процессор взаимодействует с внешним миром только через кэш). “Тяжесть” такого упорядочения может быть разной, — каждая архитектура может предоставлять целый набор барьеров “на выбор”. Используя те или иные барьеры памяти, мы можем построить разные модели памяти — набор гарантий, которые будут выполняться для наших программ.

В этой статье мы рассмотрим модель памяти C++11.

Исторический миниобзор
Поначалу производители не публиковали открытую спецификацию модели памяти процессора, то есть набор правил, по которым weakly-ordered процессор работает с памятью, тем самым надеясь, я думаю, выгадать себе пространство для маневра в будущем (действительно, зачем ограничивать себя в развитии архитектуры, беря какие-то обязательства?) Но затем производители вы��устили джинна из бутылки, — гигагерцы уперлись в потолок, и производители начали повсеместно внедрять многоядерность. В результате реальная мультипоточность пошла в массы. Первыми забили тревогу разработчики операционных систем: им надо поддерживать многоядерность в ядре, а спецификаций weakly ordered архитектуры нет. Затем подтянулись органы стандартизации языков: программы становятся всё более распараллеленными, пора стандартизировать модель памяти языка, дать какие-то гарантии при конкурентном многопоточном выполнении, а спецификаций модели памяти процессоров нет. В результате на сегодняшний день практически у всех современных архитектур процессоров есть открытые спецификации модели памяти, и немалую роль в появлении таких спецификаций сыграла работа над стандартами модели памяти Java, .NET, C++.

C++ издревле славится своей способностью на высоком уровне выражать низкоуровневые вещи. При разработке модели памяти C++11 стояла задача не нарушить этого свойства, то есть дать программистам максимальную гибкость. Проанализировав существующие на тот момент модели памяти других языков (в основном Java) и типичные примеры внутреннего устройства примитивов синхронизации и lock-free алгоритмов, разработчики стандарта выдвинули не одну, а три модели памяти:
  • sequential consistency (последовательная согласованность)
  • acquire/release семантика
  • relaxed memory ordering (слабый порядок)

Все эти модели памяти определяются в C++ одним перечислением – std::memory_order, имеющим следующие 6 констант:
  • memory_order_seq_cst – указывает на sequential consistent модель
  • memory_order_acquire, memory_order_release, memory_order_acq_rel, memory_order_consume – относятся к модели, основанной на acquire/release семантике
  • memory_order_relaxed – указывает на relaxed-модель

Прежде чем рассматривать эти модели, следует определиться, как указывать модель памяти в программе. Здесь мы должны снова вернуться к атомарным операциям.
Операции, которые я приводил в статье про атомарность, по большому счету не имеют ничего общего с определенными в C++11, так как в стандарте желаемый memory_order указывается как аргумент атомарной операции. Тому есть две причины:
  • Семантическая: по сути, желаемое упорядочение (барьер памяти) относится именно к атомарной операции, которую мы выполняем. Расстановка барьеров в read/write-подходе является шаманством именно потому, что сам барьер вообще никак семантически не связан с тем кодом, в котором он присутствует, — просто инструкция среди равнозначных. Кроме того, расстановка read/write барьеров очень зависит от архитектуры.
  • Практическая: Intel Itanium имеет особый, отличный от других архитектур, способ указания упорядочения памяти для инструкций чтения/памяти и RMW-операций. В Itanium тип упорядочения указывается как опциональный флаг самой инструкции: acquire, release или relaxed. Причем отдельных инструкций (барьеров памяти) для указания acquire/release-семантики в архитектуре не предусмотрено, есть только инструкция тяжелого полного барьера памяти

Вот как выглядят операции atomic<T> на самом деле: каждая специализация класса std::atomic<T> до��жна иметь как минимум следующие методы
void store(T, memory_order = memory_order_seq_cst);
T load(memory_order = memory_order_seq_cst) const;
T exchange(T, memory_order = memory_order_seq_cst);
bool compare_exchange_weak(T&, T, memory_order = memory_order_seq_cst);
bool compare_exchange_strong(T&, T, memory_order = memory_order_seq_cst);

Отдельные барьеры памяти
Конечно, С++11 имеет и отдельные свободные функции барьера памяти:
void atomic_thread_fence(memory_order);
void atomic_signal_fence(memory_order);

atomic_thread_fence позволяет, фактически, использовать подход отдельных read/write-барьеров, признанный устаревшим. Хотя сами способы упорядочения memory_order не предоставляют способа указать read-барьер (Load/Load) или write-барьер (Store/Store).
atomic_signal_fence предназначена для использования в обработчиках сигналов. Как правило, эта функция не генерирует никакого кода, но является барьером компилятора.

Как видно, моделью памяти по умолчанию в C++11 является sequential consistency. Её-то мы и рассмотрим первой. Но сначала несколько слов о барьерах компилятора.

Барьеры компилятора


Кто может переупорядочить код, написанный нами? Мы выяснили, что это может делать процессор. Но есть ещё один источник переупорядочения – компилятор.
Многие способы оптимизации (особенно глобальной) и эвристики разрабатывались (и разрабатываются по сей день) в предположении (быть может, неявном) однопоточного выполнения. Компилятору довольно трудно (скорее, даже теоретически невозможно) понять, что ваш код – многопоточный. Поэтому компилятору нужны подсказки – барьеры. Такой барьер говорит компилятору: не смей код перед барьером перемещать (смешивать) в код за барьером, и наоборот. Сам барьер компилятора не генерирует никакого кода.
Для MS Visual С++ барьер компилятора – это псевдофункция _ReadWriteBarrier() (это имя меня всегда ставило в тупик: полная ассоциация с read/write memory barrier – самым тяжелым барьером памяти). Для GCC и Clang – это изящная конструкция
__asm__ __volatile__ ( "" ::: "memory" )

Надо отметить, что ассемблерные вставки __asm__ __volatile__ ( … ) также являются в некотором роде барьером для GCC/Clang: компилятор не имеет права ни выкидывать, ни перемещать их вверх/вниз по коду (об этом говорит модификатор __volatile__).
Константы memory_order воздействуют на компилятор, поддерживающий C++11, в той же мере, как и на процессор, — они являются барьером компилятора, ограничивая ��озможности компилятора по переупорядочению (то есть оптимизации) нашего кода. Поэтому указание особых барьеров компилятора не требуется, если, конечно, компилятор полностью поддерживает новый стандарт.


Sequential consistency


Предположим, мы реализовали lock-free стек (это самая простейшая из lock-free структура данных), скомпилировали его и тестируем. И получаем корку (core file). В чем дело? Мы станем искать ошибку, прогоняя в уме (никакой дебаггер нам здесь не поможет) строку за строкой реализацию нашего lock-free стека, пытаясь сэмулировать многопоточность и ответить на вопрос, какое фатальное сочетание выполнения строки K потока 1 и одновременно строки N потока 2 привело к краху. Быть может, мы найдем и исправим какие-то ошибки, но все равно – наш lock-free стек будет падать. Почему?
Оказывается, то, что мы делаем, пытаясь найти ошибку и сопоставляя в уме строки программы для выполняющихся одновременно потоков, называется гарантией sequential consistency. Это строгая модель памяти, которая предполагает, что процессор делает все именно в том порядке, как написано в программе. Например, для такого кода:
// Thread 1
atomic<int> a, b ;
a.store( 5 );
int vb = b.load();

// Thread 2
atomic<int> x,y ;
int vx = x.load() ;
y.store( 42 ) ;

допустимыми для sequential consistency являются любые сценарии выполнения, кроме тех, которые меняют местами a.store / b.load и x.load / y.store. Заметим, что в этом коде я не указываю явно memory_order-аргумент в load/store, — я полагаюсь на значение аргумента по умолчанию.
Точно такая же гарантия распространяется и на компилятор: компилятору запрещено переупорядочивать наш код таким образом, что операции после memory_order_seq_cst были бы перемещены выше этого барьера, и наоборот, — операции перед seq_cst-барьером не могут быть опущены ниже барьера.
Модель sequential consistency интуитивно близка человеку, но имеет очень существенный недостаток: она слишком строга для современных процессоров. Она приводит к самым тяжелым барьерам памяти, не позволяя процессору применить в полной мере спекулятивное выполнение. Поэтому новый стандарт C++ принял такой компромисс:
  • Модель sequential consistency принять как модель по умолчанию для атомарных операций за её строгость и понятность
  • Ввести в C++ другие, более слабые модели памяти, позволяющие реализовать потенциал современных архитектур

В качестве дополнения к sequential consistency была предложена модель, основанная на acquire/release семантике.


Acquire/release семантика


Из названия acquire-release семантики можно сделать вывод, что эта семантика как-то связана с захватом (acquire) и освобождением (release) ресурсов. Действительно, это так. Захват ресурса – это его чтение из памяти в регистр, освобождение – запись из регистра в память:
load memory, register ;
membar #LoadLoad | #LoadStore ; // acquire-барьер

// Операции внутри acquire/release-секции
...

membar #LoadStore | #StoreStore ; // release-барьер
store regiser, memory ;

Как видно, в этом коде мы обошлись без применения тяжелого барьера #StoreLoad. Также можно заметить, что как acquire-барьер, так и release-барьер представляют собой полубарьеры: acquire не упорядочивает предыдущие store-операции с последующими load/store, а release не упорядочивает предыдущие load с последующими, равно как и предыдущие store с последующими load. Это относится как к процессору, так и к компилятору.
Acquire/release являются барьерами для всего кода, который заключен между acquire/release. Некоторые операции перед acquire-барьером могут просочиться (могут быть переупорядочены процессором или компилятором) внутрь acquire/release-секции, также как и некоторые операции после release-барьера могут быть перенесены вверх (опять-таки, процессором или компилятором), внутрь acquire/release-секции. Но операции, заключенные внутри acquire-release, не выйдут за её пределы.

Наверно, самый простой пример применения acquire/release-семантики – это spin-lock.
Lock-free и spin-lock
Может показаться странным, что в статье цикла о lock-free алгоритмах я привожу пример алгоритма блокировки. Требуется объясниться.
Я не ярый поклонник чистого lock-free, ни в коем случае. Да, чистый lock-free (а тем паче wait-free) алгоритм меня радует, и радует вдвойне, если получается его реализовать (не всегда такое происходит). Я являюсь сторонником прагматического подхода: всё, что эффективно, то хорошо. Поэтому я не брезгую применять блокировки там, где они могут дать выгоду. Spin-lock может дать значительную выгоду по сравнению с обычными мьютексами, если он «охраняет» очень маленький кусочек кода – несколько ассемблерных инструкций. К тому же spin-lock, несмотря на свою простоту, — неиссякаемый источник всяческих интересных оптимизаций.

Вот как выглядит простейший spin-lock на acquire/release (знатоки C++ укажут, что для реализации spin-lock надо бы использовать специальный тип atomic_flag, но я построю spin-lock на атомарной переменной (даже не булевой) – так наглядней с точки зрения этой статьи):
class spin_lock 
{
    atomic<unsigned int> m_spin ;
public:
    spin_lock(): m_spin(0) {}
    ~spin_lock() { assert( m_spin.load(memory_order_relaxed) == 0);}

    void lock()
    {
        unsigned int nCur;
        do { nCur = 0; }
        while ( !m_spin.compare_exchange_weak( nCur, 1, memory_order_acquire ));
    }
    void unlock()
    {
        m_spin.store( 0, memory_order_release );
    }
};

Заметим, что в этом коде то, что compare_exchange принимает свой первый аргумент по ссылке и изменяет его, если CAS неудачен, мне очень мешает! Приходится писать do-while цикл с непустым телом.
В методе lock овладения блокировкой я использую acquire-семантику, а в методе unlock – release-семантику (кстати, acquire/release семантика повела свою историю как раз из примитивов синхронизации: разработчики стандарта внимательно проанализировали реализацию различных примитивов синхронизации и вывели паттерн acquire/release.) Как я писал выше, барьеры, проставляемые в этом случае, не позволяют коду, заключенному между lock() и unlock(), просочиться наружу, — то, что нам и нужно! А атомарность переменной m_spin гарантирует нам, что пока m_spin=1, никто не сможет овладеть блокировкой, — опять то, что и требуется!
В алгоритме мы видим, что я использую compare_exchange_weak. Что это такое?


Слабый и сильный CAS


Как вы помните, архитектура процессоров может относиться к одному из ��вух классов: либо процессор реализует атомарный примитив CAS (compare-and-swap), либо пару LL/SC (load-linked/store-conditional). Пара LL/SC позволяет реализовать атомарный CAS, но сама по себе не является атомарной в силу многих причин. Одна из этих причин – код, выполняющийся внутри LL/SC, может быть прерван операционной системой; например, именно в этот момент ОС принимает решение вытеснить текущий поток. Соответственно, store-conditional потом, после возобновления, не сработает. То есть наш CAS возвратит false, хотя на самом деле причина этого false может быть не в данных, а в стороннем событии – прерывании потока.
Именно это соображение подвигло разработчиков стандарта ввести два примитива compare_exchange – слабый (weak) и сильный (strong). Называются эти примитивы соответственно compare_exchange_weak и compare_exchange_strong. Слабая версия может быть неудачной, то есть возвратить false, даже в том случае, если текущее значение переменной равно ожидаемому. То есть слабый CAS может нарушить семантику CAS и возвратить false, когда на самом деле надо возвращать true (но не наоборот!) Сильный CAS этого сделать не может: он строго следует семантике CAS. Конечно, это может чего-то стоить.
Когда следует применять слабый, а когда – сильный CAS? Я для себя вывел такое правило: если CAS используется в цикле (а это основной паттерн использования CAS) и в цикле нет наворота операций (то есть тело цикла – легкое), то я использую compare_exchange_weak – слабый CAS. В противном случае – сильный compare_exchange_strong.

Memory order для acquire/release семантики


Как я отмечал выше, для acquire/release семантики определены следующие значения memory_order:
  • memory_order_acquire
  • memory_order_consume
  • memory_order_release
  • memory_order_acq_rel

Для чтения (load) допустимыми являются значения memory_order_acquire и memory_order_consume.
Для записи (store) – только memory_order_release.
Memory_order_acq_rel является допустимым только для RMW-операций – compare_exchange, exchange, fetch_xxx. Вообще, атомарный RMW-примитив может обладать acquire-семантикой memory_order_acquire, release-семантикой memory_order_release или той и другой вместе — memory_order_acq_rel. Для RMW-операций эти константы определяют именно семантику, так как read-modify-write примитив одновременно выполняет атомарные чтение и запись. Семантически RMW-операция может рассматриваться либо как acquire-чтение, либо как release-запись, либо как то и другое.
Определить семантику RMW-операции можно только в алгоритме, где она применяется. Часто в lock-free алгоритмах можно выделить части, чем-то похожие spin-lock: в начале мы получаем (acquire) некий ресурс, что-то делаем (обычно вычисляем новое значение) и в конце мы устанавливаем (release) новое значение ресурса. Если получение ресурса выполняется RMW-операцией (обычно это CAS), то такая операция вполне вероятно имеет acquire-семантику. Если установка нового значения выполняется RMW-примитивом (CAS или exchange), то он вполне вероятно имеет release-семантику. “Вполне вероятно” вставлено неспроста: требуется детальный анализ алгоритма, прежде чем можно будет понять, какая семантика подходит для RMW-операции.
Если же RMW-примитив выполняется отдельно (невозможно выделить паттерн acquire/release), то возможны 3 варианта для семантики:
  • memory_order_seq_cst – RMW-операция является ключевым звеном алгоритма, переупорядочение кода, перенос чтения и записи вверх-вниз может привести к ошибке
  • memory_order_acq_rel – чем-то аналогично memory_order_seq_cst, но RMW-операция находится внутри acquire/release-секции
  • memory_order_relaxed – перенос RMW-операции (её load и store-частей) вверх-вниз по коду (например, в пределах acquire/release секции, если операция находится внутри такой секции) не приводит к ошибкам

Все эти советы следует воспринимать только как попытку наметить какие-то общие принципы навешивания той или иной семантики на RMW-примитив. Для каждого алгоритма следует проводить детальный анализ.

Consume-семантика


Существует отдельная, более слабая, разновидность acquire-семантики – consume-семантика чтения. Эта семантика была введена как «дань памяти» процессору DEC Alpha.
Архитектура Alpha имеет существенное отличие от других современных архитектур: она могла нарушать зависимость по данным. В таком примере кода:
struct foo {
	int x;
	int y;
} ;
atomic<foo *> pFoo ;

foo * p = pFoo.load( memory_order_relaxed );
int x = p->x;

Она могла переупорядочить чтение p->x и собственно получение p (не спрашивайте меня, как такое возможно, — это свойство Alpha; с Alpha мне не приходилось работать, так что ни подтвердить, ни опровергнуть это я не могу).
Для предотвращения такого переупорядочения была введена consume-семантика. Она применима для атомарного чтения указателя на структуру, после чего следует чтение полей структуры. В данном примере указатель pFoo следует читать так:
foo * p = pFoo.load( memory_order_consume );
int x = p->x;

Consume семантика стоит где-то посередине между relaxed- и acquire-семантикой чтения. На многих современных архитектурах она отображается на relaxed-чтение.

И ещё раз о CAS


Выше я привел интерфейс atomic<T> с двумя CAS – weak и strong. На самом деле, существует ещё два варианта CAS – с дополнительным аргументом memory_order:
bool compare_exchange_weak(T&, T, memory_order successOrder, memory_order failedOrder );
bool compare_exchange_strong(T&, T, memory_order successOrder, memory_order failedOrder );

Что это за аргумент – failedOrder?
Вспомним, что CAS – это read-modify-write примитив. Даже в случае неудачи он выполняет атомарное чтение. Аргумент failedOrder как раз и определяет семантику этого чтения в случае неудачи CAS. Поддерживаются те же значения, что для обычного чтения.
На практике указание «семантики при неудаче» требуется довольно редко. Конечно, всё зависит от алгоритма!

Relaxed-семантика


Наконец, третий тип модели атомарных операций – relaxed-семантика, которая применима ко всем атомарным примитивам – load, store, всем RMW, — и которая не накладывает почти никаких ограничений и поэтому позволяет процессору переупорядочивать почти в полной мере, демонстрируя свою полную мощь. Почему почти?
Во-первых, требование стандарта – соблюдать атомарность relaxed-операций. То есть даже relaxed-операция должна быть неделимой, без частичных эффектов.
Во-вторых, для атомарной relaxed-записи стандартом запрещена спекулятивная запись.
Эти требования могут налагать ограничения на реализацию атомарны�� relaxed-операций в некоторых weakly ordered архитектурах. Например, relaxed load атомарной переменной на Intel Itanium реализуется как load.acq (acquire-чтение, не путать Itanium acquire с C++ acquire).
Реквием по Итаниуму
В своих статьях я часто упоминаю Intel Itanium. Может возникнуть впечатление, что я фанат архитектуры Itanium, которая, похоже, медленно умирает. Нет, я не фанат, но…
VLIW-архитектура Itanium в чем-то отличается от других по принципу построения системы команд. Memory ordering указывается как суффикс load/store/RMW-инструкций, — такого нет в других современных архитектурах. Даже используемые термины – acquire, release, — наводят мысль, не списан ли C++11 с Итаниума.
Если мы вспомним историю, Itanium – это та архитектура (или ее потомок), на которой мы все сейчас бы сидели, если бы в свое время AMD не подсуетилась и не выпустила AMD64 – 64-битное расширение x86. Intel же в это время неспешно разрабатывала новую архитектуру под 64-битные вычисления. И туманно намекала об этой новой архитектуре. Из намеков можно было понять, что нас ждет Итаниум на десктопе. Кстати, майкросовтовские порт Windows и компилятора Visual C++ под Itanium также косвенно свидетельствуют об этом (кто-нибудь видел работающие винды на итаниуме?) Но шустрая AMD разрушила планы Intel, и последней пришлось срочно догонять, внедряя 64 бита в x86. Итаниум так и остался в серверном сегменте, где потихоньку умирал, не получая должных ресурсов на развитие.
Между тем, Итаниум со своим “пучком” инструкций в “очень длинном слове” (VLIW – very long instruction word) является до сих пор интересным и прорывным процессором. То, что современные процессоры делают сами, — загружают свои исполнительные блоки, переупорядочивая операции, — в Итаниуме было доверено компилятору. Но компиляторы не справились с такой задачей и генерировали (и до сих пор генерируют) не слишком оптимальный код. В результате производительность Итаниума проседала в несколько раз – и только за счет нерационального (с точки зрения Итаниума) распределения инструкций по “пучкам” VLIW (не помню, как это называется в Итаниуме, но перевод – “пучок” – запомнился), что приводило к нерациональной загрузке его исполнительных блоков.
Так что Itanium – это наше нереализованное будущее.
Хотя, кто знает, быть может, ещё рано писать реквием?..


Happens-before, synchronized-with и прочие отношения


Тот, кто знаком со стандартом C++11, спросят: «А где же отношения, определяющие семантику атомарных операций, — happened before, synchronized-with и прочие?»
Я отвечу – в стандарте.
Хорошее рассмотрение именно в терминах стандарта дано в книге Энтони Вильямса C++ Concurrency in Action (есть русский перевод), пятая глава. Там есть много детально разобранных в терминах отношений примеров.
Разработчики стандарта сделали важную работу – они вывели правила (отношения) для модели памяти C++, причем эти правила описывали не расстановку барьеров памяти, а гарантии взаимодействия потоков. В результате получилось компактное аксиоматическое описание модели памяти C++.
К сожалению, применять эти отношения на практике чрезвычайно сложно по причине огромного количества вариантов, которые требуется рассмотреть для доказательства корректности указания memory_order в более-менее сложном lock-free алгоритме. Именно поэтому моделью по умолчанию является sequential consistency – эта модель вовсе не требует указывать какие-то специальные memory_order-аргументы для атомарных операций. Как отмечалось, эта модель является и самой тормозной.
Применение более слабых моделей – acquire/release или relaxed – требует верификации алгоритма.

UPD: Хабражитель cheremin справедливо указал на неточность последнего утверждения. Действительно, сама по себе sequential consistency не гарантирует ничего, — можно написать чушь и с её использованием. Поэтому уточняю: верификация lock-free алгоритма требуется всегда, для любой модели памяти, а в случае слабых моделей — требуется особо.


Верификация lock-free алгоритмов


До недавнего времени мне был известно только одно средство верификации — библиотека relacy Дмитрия Вьюкова. К сожалению, это средство требует построения особой модели. Фактически, следует сначала построить упрощенную модель lock-free алгоритма в терминах библиотеки relacy (почему упрощенную? – потому что, строя модель, обычно убираешь всякие полезные фенечки, не относящиеся непосредственно к рассматриваемому алгоритму). Эту модель затем нужно отладить, и только потом, когда все отлажено и все атомарные операции снабжены корректными memory_order-аргументами, можно написать уже production-версию алгоритма. Такой подход идеаль��о подходит разработчикам lock-free алгоритмов и структур данных, — тем, кто их придумывает. Собственно, для разработчиков на такой модели всё и заканчивается. Но имплементаторам (мне нравится русский термин «воплотитель» – он подчеркивает, что субъект ничего сам не придумывает, а только творчески воплощает в жизнь чью-то мысль) такой двухступенчатый подход зачастую не подходит (вследствие природной лени), — им нужно всё здесь и сейчас, и желательно побыстрее.
Видимо, сам автор relacy, Дмитрий Вьюков, понимал этот недостаток своего детища (никакой иронии – relacy действительно прорывной проект в своей области), и однажды в интервью на форуме Intel высказал мысль – сделать так, чтобы средство верификации (relacy или что-то подобное) было внедрено внутрь стандартной библиотеки. Тогда никакой дополнительной модели делать уже не придется. Чем-то это напоминает концепцию safe iterators в дебажной STL.
Недавно Дмитрий вместе со своими соратниками из Google представили новый инструмент ThreadSanitizer. Этот инструмент позволяет проверить наличие data race (гонки по данным) в программе, то есть, фактически, правильное применение упорядочения в атомарных операциях. Более того, этот инструмент внедрен даже не в STL, а ещё глубже — в компилятор (Clang 3.2, а затем в GCC 4.8).
Применение ThreadSanitizer довольно простое – достаточно скомпилировать программу с определенными ключами, сделать тестовый прогон — и наслаждаться изучением обширных логов. Я в своей библиотеке libcds планирую в ближайшее время применить данный инструмент, дабы убедиться, какой я олух что в libcds всё в порядке.
Важность верификации для архитектуры x86
Архитектура x86, пожалуй, является менее всего расслабленной (weakly-ordered) среди всех расслабленных. Это её достоинство, но в этом же кроется и главная опасность для lock-free алгоритмов: то, что будет надежно работать в x86, может быть совершенно неработоспособным на процессорах других архитектур.
А дело все в том, что многие из memory_order-значений отображаются в коде в null (даже не в nop!), — x86 просто не требует этих барьеров. Например, release-семантика записи – это обычный атомарный mov из регистра в память, такой же mov применяется для relaxed-записи.
Поэтому отлаживать lock-free алгоритмы, претендующие на общеупотребительность для любой архитектуры, на x86-платформе необходимо только с каким-либо средством верификации или эмулятором более расслабленной модели памяти.


«Я не понимаю...» — Критика стандарта


Да, я беру на себя смелость критиковать стандарт C++11! Я не понимаю, почему в стандарте был выбран подход, когда семантика указывается аргументом атомарной операции. Куда логичнее было бы воспользоваться шаблонами и определить что-то такое:
template <typename T>
class atomic {
    template <memory_order Order = memory_order_seq_cst>
    T load() const ;

    template <memory_order Order = memory_order_seq_cst>
    void store( T val ) ;

    template <memory_order SuccessOrder = memory_order_seq_cst>
    bool compare_exchange_weak( T& expected, T desired ) ;

   // и так далее
};

Поясню, почему я считаю, что такое определение более корректно.
Как уже неоднократно указывалось, семантика атомарных операций влияет не только на процессор, но и на компилятор. Для компилятора семантика выступает в роли [полу]барьеров оптимизации. Кроме того, компилятор должен следить за тем, чтобы атомарной операции была назначена допустимая семантика (вспомните, что, например, release-семантика неприменима к чтению). Поэтому семантика должна быть определена на этапе компиляции. Я не представляю, что будет делать компилятор в таком коде:
extern std::memory_order currentOrder ;
std::Atomic<unsigned int> atomicInt ;
atomicInt.store( 42, currentOrder ) ;

Этот код формально не противоречит стандарту C++11. Тем не менее, все, что может здесь сделать компилятор, это:
  • либо выдать ошибку, — тогда зачем вообще допускается такой интерфейс атомарных операций, который может привести к ошибке?
  • либо применить семантику sequential consistent – из соображений «не было бы хуже». Но тогда переменная currentOrder просто игнорируется, а наша программа получает тормоза, которых мы хотели избежать
  • либо сгенерировать switch/case по всем возможным значениям currentOrder. В этом случае вместо одной-двух ассемблерных инструкций мы получим неэффективный код. Да и проблема подходящей для операции семантики не решается, — вполне возможно вызвать release-чтение или acquire-запись

Шаблонный же подход лишен таких недостатков. В шаблонных функциях мы должны указать именно константу времени компиляции из перечисления memory_order. Да, вызов атомарных операций может быть несколько угловат:
std::Atomic<int> atomicInt ;
atomicInt.store<std::memory_order_release>( 42 ) ;
// или даже так:
atomicInt.template store<std::memory_order_release>( 42 ) ;

Но, по моему мнению, такая «угловатость» компенсируется преимуществами шаблонного подхода, — однозначностью указания семантики операции во время компиляции.
Единственное объяснение C++11 подхода, которое приходит мне на ум, — пресловутая совместимость с C. Ведь помимо класса std::atomic стандарт C++11 вводит свободные C-шные атомарные функции atomic_load, atomic_store и пр.
Отмечу, что в libcds во времена, когда C++11 ещё был только в проекте, я реализовал атомарные примитивы именно в терминах шаблонов. Потом пришел к мнению, что надо все-таки следовать стандарту, и перелопатил очередную версию libcds под интерфейс атомарных операций C++11.

Конец Основ


Эта статья – заключение Основ.
Конец основ по мнению Гугла

Именно эту картинку выдал мне Гугл первой по запросу «конец Основ». А что, какая-то логика в этом есть…

Далее обязуюсь рассказывать уже “по теме” – lock-free структуры данных и сопутствующие алгоритмы.

Lock-free структуры данных
Начало
Основы:

Внутри:

Извне: