Как стать автором
Обновить

Комментарии 38

На самом деле, интереснее каноничный пример с синглтоном:
static Singleton* singleton = nullptr;
static std::mutex mtx;
 
Singleton *instance() {
	if (singleton ) // early return to avoid touching mutex every call
		return singleton;
 
	std::unique_lock l(mtx); // `mutex` locks here (acquire memory)
	if (!singleton)
		singleton = new Singleton();
        return singleton;
	// `mutex` unlocks here (release memory)
}


Казалось бы, тут всё хорошо? Но нет, Александреску в своей статье пишет что всё плохо.
singleton = new Singleton();

может развернуться в что-то типа такого

// выделили память и записали указатель,
singleton = (Singleton*)malloc(sizeof(Singleton)); 
// если второй тред прочитает указатель в этом месте, то всё упадет
// а вот теперь создали объект (тут еще куча операций)
new (singleton) Singleton();

Мы же хотим что-то типа такого

auto tmp = (Singleton*)malloc(sizeof(Singleton)); // выделили память
new (tmp) Singleton(); // создали объект
singleton = tmp; // записали указатель

Но, понятное дело, гарантий что будет выбран вариант 2 нам никто не дает (скорее всего, не будет, потому что это медленнее). Если же руками написать этот код, то компилятор также может соптимизировать в вариант 1.
К счастью, начиная с С++11 не должна больше болеть голова о синглтонах=)
Самый простой для понимания флаг синхронизации памяти — relaxed.

Флаг синхронизации памяти «единая последовательность» (sequential consistency, seq_cst) самый строгий и понятный


Хорошо, когда самых понятных флагов два. Лучше бы, конечно, три.
Спасибо, что заметили. Поменяю слова. Вообще «понятный», «простой для понимания» — это слишком субъективно.
Пожалуйста, Хорошего кодинга на leetcode!
Можно ли использовать std::atomic с разделяемой памятью? Насколько это безопасно?
НЛО прилетело и опубликовало эту надпись здесь
Можете, пожалуйста, пояснить свою мысль? Мне казалось, PTHREAD_PROCESS_SHARED даёт возможность ОС правильно обрабатывать ситуацию, если заблокировать spinlock не получилось и пришлось воспользоваться futex() (который иначе будет вызван с FUTEX_PRIVATE_FLAG). А shared memory в архитектуре абстрактной машины ничем не отличается, используется ли в 1 или разных процессах.

Почему нет гарантий? std::atomic — это про память и инструкции процессора. И, насколько мне известно, стандарт не регламентирует в какой именно памяти должна быть расположена atomic переменная. Кмк тут все зависит от конкретной имплементации std::atomic.

НЛО прилетело и опубликовало эту надпись здесь
Классная статья, подписался!
Статья весьма хорошая и интересная, но пара неточностей несколько снижает, на мой взгляд, её полезность.
1. Выполнение нескольких потоков на одном процессоре в режиме разделения времени не дает гарантии того, что выполнение оператором C++ операции вида read-modify-write будет защищено от вмешательства со стороны другого потока. Потому что эта операция транслируется в несколько машинных команд. Выполнение потока может быть прервано после одной из команд середине операции, и управление после этого может быть передано другому потоку, который внесет конфликтующие изменения.
В однопроцессорной системе есть только гарантия того, что данные не будут изменены другим потоком во время выполнения одной машинной команды, а в многопроцессорной — нет и этой гарантии. Однако с точки зрения программы на языке высокого уровня это мало что меняет.
2. Мьютекс не реализуется через атомарные операции. Для его работы требуется обращение к ядру ОС. Потому что при возникновении состояния ожидания потока необходимо обратиться к планировщику в ядре ОС, чтобы он запустил на выполнение другой поток (варианты планировщиков пользовательского режима, в которых единицей исполнения является не поток режима ядра, а другие конструкции, аналогичные promise или Task в других языках, я не тут не рассмартриваю). Ядро ОС же может использовать для синхронизации доступа к общим для нескольких процессоров структурам данных другие механизмы (например, спин-блокировки или межпроцессорные прерывания).
Да, существуют «легкие» варианты реализации мьютекса (в Windows — критическая секция), в которых обращение к ядру откладывается, насколько это возможно, чтобы не вызывать ядро, когда блокировка с передачей управления другому потоку не происходит либо состояние блокировки очень быстро проходит. И для реализации такого поведения действительно используются атомарные операции. Но для осуществления передачи процессора для выполнения другого потока обращение к ядру неизбежно.
Полную семантику мьютексов — с перепланированием потоков — на атомарных операциях реализовать невозможно, максимум что возможно — это реализовать семантику спин-блокировки, которая захватывает процессор вместо того, чтобы передать его другому потоку для выполнения.

Впрочем, в большинстве практических применений эти неточности существенной роли не играют.
И ещё. Я считаю, что, говоря о разнице между compare_exchange_strong и compare_exchange_weak, следовало бы уделить ей больше внимания хотя бы в практическом аспекте: что для надежного использования compare_exchange_weak необходимо организовывать циклическую поверку при неудачном сравнении, а вариант compare_exchange_strong этого не требует, но зато он обходится дороже (потому как требует немедленной синхронизации кэшей процессоров, что в некоторых архитектурах является весьма дорогой операцией) — в статье по приведенной ссылке все это, естественно, есть, но далеко не в первых ее словах.
Спасибо за ваши развернутые замечания!

По 1. Полностью с вами согласен. Я подправлю текст статьи.

По 2. Все таки не соглашусь с вами. Атомарные операции (инструкции процессора) — более фундаментальное понятие, чем мьютекс в операционной системе. Реализация мьютексов в OS реализованы на атомиках (по крайней мере в linux).

Вот кусок из mutex.c из исходных кодов линукс:
/*
 * Optimistic trylock that only works in the uncontended case. Make sure to
 * follow with a __mutex_trylock() before failing.
 */
static __always_inline bool __mutex_trylock_fast(struct mutex *lock)
{
	unsigned long curr = (unsigned long)current;
	unsigned long zero = 0UL;

	if (atomic_long_try_cmpxchg_acquire(&lock->owner, &zero, curr))
		return true;

	return false;
}

static __always_inline bool __mutex_unlock_fast(struct mutex *lock)
{
	unsigned long curr = (unsigned long)current;

	if (atomic_long_cmpxchg_release(&lock->owner, curr, 0UL) == curr)
		return true;

	return false;
}


Вы правы, что мьютекс в OS более «умный», чем спин лок и взаимодействует с планировщиком потоков, но это не убирает с него обязанностей атомарно «включить» или «выключить» блокировку, что реализована на атомиках, как показывает исходный код выше.

3. Про compare_exchange_weak vs strong. Я с вами согласен. Но этот вопрос достаточно внятно описан в документации этих методов. Мне не хотелось тратить время читателя на «простые вещи», описанные в документации. В том числе на такие, как std::atomic::is_lock_free и std::atomic_flag.

Поясните, пожалуйста. Когда в примере с мьютексом вы пишете: "Он так же делает доступным те изменения памяти, которые были сделаны до вызова unlock() в коде, который будет работать после вызова lock()" — дело касается всех модифицированных переменных, не только атомиков?


Или другим потокам будут гарантированно видны только все изменённые атомики? Или всё-таки для получения актуального значения атомика надо вызвать load или acquire-операцию? В чём заключается роль мьютекса по синхронизации изменений памяти?

В этом, собственно, и есть смысл мьютекса. Сериализовать доступ к данным, которые он защищает. Сам по себе как таковой он редко нужен. А блокировка/разблокировка в этом смысле как раз соответствуют захвату/отпусканию.
Все операции, которые ниже load/acquire так и останутся ниже; они не могут быть переупорядочены вверх и выполниться до захвата/лока. Те, которые выше — могут просочиться вниз и выполниться уже после. Все, которые выше save/release не могут просочиться ниже. Те, которые изначально были ниже — могут выполниться раньше. И вот это вот, что операции ниже/выше блока acquire-release могут дрейфовать в него — и есть разница между полным барьером со строгой последовательностью и "полубарьером". Но главный паттерн "захватили мьютекс, изменили переменную, отпустили мьютекс" при этом работает. Гарантия, что сперва захватится мьютекс, а потом изменится переменная. И отпускание состоится после изменений. А значит захват мьютекса в другом потоке, когда он состоялся, гарантирует, что изменения, если они были, ему видимы.


А вот вторая часть непонятна. Для получения значения (любого) нужно выполнить load-операцию. Чтобы при этом сохранилась ещё и последовательность — при записи значения должно быть release, при чтении — acquire. Именно так, парой. Если хотя бы одна операция (чтение или запись) relaxed, то последовательность уже не гарантируется. Один процессор записал единичку в relaxed режиме, другой пока об этом знать не знает и читает всё ещё нолик.

К моему стыду я не понимаю как «ожидание» реализовано на процессоре (пусть 86, например), поэтому задам вопрос здесь, вроде тематика подходит. Для простоты — пусть у нас есть всего один поток, есть какой-то код, который захватил мьютекс, и есть второй, который его ждет. Что именно (на уровне байткода, наверное?) происходит в момент «ожидания»? Можно просто ссылку что «покурить», буду благодарен.

Ну и второй вопрос, который как по мне схож. Вот у меня есть ядро процессора, оно выполняет 100 операций в секунду. Но в данный момент у меня есть ему предложить только 50. Понятное дело что там есть какое-то квантование по времени. Но что делает ядро в те кванты, когда делать нечего? Молотит nop'ы? Думаю что сейчас врятли, энергоэффективность же. Считаем что частоту снижать уже некуда (я сейчас про всякие «base clock 1.2, boost clock 100500 GHz». Или оно все равно снижает ниже, просто юзер не в курсе?
Что именно (на уровне байткода, наверное?) происходит в момент «ожидания»?

Зависит от реализации мьютекса. В общем случае переключается на другой поток. Но вот при ожидании на critical section из Windows сперва делается спинлок («крутится»), а потом, по прошествии некоторого времени (определяется глобально для системы ключом реестра), опять таки переключается на другой поток.

futex в Linux, на котором основана в том числе реализация mutex, работает точно также — пытаемся решить максимум в userspace и только если все плохо делаем "тяжелые" системные вызовы

На второй вопрос. Если речь про ОС с планировщиком, то планировщик переключит выполнение на idle процесс/поток (реализован как вечный цикл) или выполнит остановку процессора (в будущем процессор будет разбужен прерыванием аппаратного таймера с возвратом в планировщик). Все зависит от того что дешевле
Немного оффтоп: есть какие-то рекомендации, когда надо полагаться на средства языка и ОС, а когда стоит вкорячить собственный планировщик в программу?
До 10 000 rps заморачиваться с уходом от ОС точно не стоит. До 100 000 rps можно начать задумываться, но тоже не обязательно. До больших скоростей я нечасто добирался.
Ну либо если какаято система реального времени
Программист: *хочет синхронизировать данные между двумя потоками*.
Язык программирования: вот вам конструкция для синхронизации.
Программист: спасибо.
Язык программирования: только помните, что есть нюансы для разных архитектур
Язык программирования: и 5 флагов, меняющих алгоритм работы, не синхронизируя то одно, то другое.
Программист:
Язык программирования: а если сделать вот так (*с виду логичная и непротиворечивая конструкция*), то всё упадет в самый неожиданный момент!
Программист:
Язык программирования: в следующей версии стандарта будет ещё удобнее, добавим ещё десяток флагов и способов синхронизации (с нюансами, как вы любите), не благодарите!

А что будет, если один атомик пытаются инкрементить сразу два потока на двух разных процессорах с помощью fetch_add ( 1, std::memory_order_relaxed )? Может ли случиться, что результат будет, как будто инкремент случился лишь единожды?
Вопрос именно про модель relaxed.
Один поток взял и увеличил переменную, как положено, атомарно. Никому специально ничего не сказал (потому что relaxed).
Второй взял её же из кэша и тоже увеличил. Тоже, как положено, атомарно. Но при этом изменений от первого потока ещё не увидел, потому что синхронизации/барьеров нет.

А что будет, если один атомик пытаются инкрементить сразу два потока на двух разных процессорах с помощью fetch_add ( 1, std::memory_order_relaxed )? Может ли случиться, что результат будет, как будто инкремент случился лишь единожды?
Нет. Реализация гарантирует что все будет работать правильно.
Один поток взял и увеличил переменную, как положено, атомарно. Никому специально ничего не сказал (потому что relaxed).
Второй взял её же из кэша и тоже увеличил. Тоже, как положено, атомарно. Но при этом изменений от первого потока ещё не увидел, потому что синхронизации/барьеров нет.
Мemory order это больше не про использование кеша, это про видимый порядок операций чтения/записи из другого потока. Грубо, зачитывать/записывать ли все измененные данные до/после указанной операции. Сам адрес в любом случае будет обновлен в кеше перед операцией. Fetch_add(1, std::memory_order_relaxed), не является эквивалентом i++. По-этому и говорят что атомарные операции медленные, т.к. мы вынуждены тратить время на синхронизацию кеша.
Может ли случиться, что результат будет, как будто инкремент случился лишь единожды?

Нет, инкремент случится всегда дважды. Об этом пример 1, как раз.
godbolt.org/z/jx85P9

Код:
counter.fetch_add(1, std::memory_order_relaxed);

Транслируется в команду на x86-64:
lock add        QWORD PTR counter[rip], 1

На уровне ЦПУ это работает так: выполнить оператор add, захватив эксклюзивный доступ к кэш линии. Это соответсвует состоянию Exclusive в протоколе синхронизации кешей MESI ( en.wikipedia.org/wiki/MESI_protocol ). Состояние exclusive означает, что в линии кэша ядра лежит актуальное значение (соотвествующее main memory) и в других ядрах кэш линии инвалидируется (состояние invalid).

Когда два ядра захотят выполнить fetch_add(1, std::memory_order_relaxed), то им придется по-очереди захватить exclusive лок на кэш линию и каждое ядро (поток) прибавит свою единичку правильно.

Ядре (архитектура x86-64), выполняющем print_metrics(), кэш линия с counter будет в состоянии invalid, ядро запросит чтение из этой кэш линии, и она перейдет в состояние shared на всех ядрах. В этот момент в кэш линии уже будет актуальное значение, совпадающее с количеством fetch_add(1), которые успели выполнится в других потоках.

Ну вот этот момент и смущает. Если это особенность именно архитектуры (вот, решили разработчики компилятора использовать именно такую команду) — то это одно.
А если доступ всегда by design оказывается синхронизированным — то выходит, чистый атомик "всегда безопасен". Например, как переменная для счётчика ссылок. Можно не глядя инкрементить/декрементить, и только если счётчик обнулился — возможно, для верности имеет смысл поставить полный барьер, чтобы удаление объекта спекулятивно не выполнилось до самой проверки.
Если же такой алгоритм специфичен только для x86-64, а на каком-нибудь cortex или itanium всё иначе — тогда не так всё прозрачно.

Я описал как в железа на x86-x64. На других архитектурах механизмы другие, но будут соблюдены гарантии модели памяти C++. Компилятор не в праве компилировать корректный с точки зрения стандарта языка код в некорректный машинный код.

Поэтому — да, так всегда by design языка.

Кстати, насчет счетчика ссылок. Для инкремента можно использовать relaxed, а для декремента нужен acquire/release, т.к. декремент счетчика ссылок до 0 должен быть синхронизирован для однократного вызова деструктора объекта и деаллокации памяти.
На самом деле, думать об атомиках в терминах кэшей достаточно бесполезно. Можно (условно) считать что кэши процессора всегда когерентны — если вы записали в ячейку памяти, то другие ядра это увидят. Проблема в том что помимо кешей есть и другие уровни абстракции (буфер записи в кеш) и регистры процессора, которые не обязаны быть когерентными. Гадать, попало ваше значение в кэш или ещё находится в регистре — занятие неблагодарное, не надо об этом думать=)

Основная проблема не в том когда данные попадут в память (в кэш, в оперативку), а в видимом порядке действий — компилятор/процессор вольны переставлять (независимые по данным инструкции) как им покажется удобным. У меня на работе код изобилует примерами типа 3 (безо всяких атомиков) — люди ничего не слышали про reordering и думают — ну раз я записал в bool ready true, то значит могу читать данные из другого потока (но нет).

Атомики решают проблему на более высоком уровне — они служат барьерами памяти — если есть разделяемый доступ, то обязательно нужен (какой-то) атомик или другой примитив синхронизации (мьютекс, семафор). Если барьера памяти нет, то это UB. Возможно на вашем x86_64 все будет работать потому что это strong-ordered архитектура и без каких-либо атомиков, но по стандарту — это UB, этот код не переносим.

О механике acquire/release так же удобно думать высокоуровнево — когда вам нужен ресурс, вы захватываете его через «acquire», когда закончили — отпускаете с «release».

Я не устаю рекомендовать цикл статей kixmax про lock-free программирование, там есть ответы на ваши вопросы.

Считать можно, но зачем тогда relaxed, если всё всегда синхронизируется?
Я его воспринимаю как раз как "просто атомик", без всяких гарантий. Т.е. ровно то, что операция чтения/модификации/записи выполнится атомарно. А то, что результат мгновенно окажется видимым в других потоках на других процессорах — не факт. Или то, что оно выполнится прямо сейчас, а не пару десятков инструкций спустя — тоже не факт. И если такие гарантии становятся нужны — там уже да, надо явно писать ack для load, rel для store, или (как в случае с изменяющими операциями над одной переменной) — комбинированный acquire_release, два-в-одном. Но эти задачи возникают, когда кроме атомиков подразумеваются ещё некие сущности, не-атомарные, доступ к которым хочется упорядочить с помощью атомиков. Если мне нужно передать данные через барьер — я сохраню данные, а потом флажок в атомик с release, в другом потоке прочитаю атомик с acquire и буду уверен, что данные валидны. Или сохраню указатель на данные прямо в атомик с release, а в другом потоке прочитаю его с consume и тоже буду уверен. Но это всё уже подразумевает зависимости и барьеры (или полубарьеры). А вот от relaxed ожидается шустрая работа без лишних синхронизаций и барьеров

relaxed нужен для того чтобы подсказать компилятору\процессору что вот эта переменная (потенциально) используется для синхронизации.
без нее код типа
bool done = false; //global static
void doWork() {
while (!done)
    foo();
}


может быть соптимизирован в
bool done = false; //global static
void doWork() {
if (done)
    return;
while (true)
    foo();
}


Обусловлено это тем что компилятор волен предполагать что переменная done не меняется в _этом_ потоке (например, если он сможет это доказать, заинлайнив foo), а значит оба варианта эквивалентны.
На практике я такого поведения не встречал (компилятору сложно доказать утверждение выше) и любой sane компилятор так делать не будет, но насколько я знаю, никто ему это не запрещает делать (привет, то самое UB). Миф про volatile же не на ровном месте появился.
А разве в этом конкретном случае bool volatile done не решает проблему?
От примитивов синхронизации нужно несколько вещей
1. отсутствие оптимизаций компилятора (как пример выше)
2. отсутствие оптимизаций процессора (например, перестановка операций в рантайме)
3. неделимость (атомарность) самой операции.
4. что-то еще забыл?

volatile помогает только с пунктом 1, но одного этого мало. В данном примере его, возможно, и достаточно (но стандарт С++ говорит, что нет).
Пример с relaxed и пунктом 3 подробно разобран в статье на примере инкремента. Это второй юзкейз relaxed, я не стал про него потому что про это уже написали до меня весьма подробно.
Атомики/мьютексы обладают всеми тремя пунктами требований, volatile — только одним из них.
Разве в этом случае нужны второй и третий пункты? Про ордеринг тут не идет речи, так как мы просто ждем переключение флага; в крайнем случае нужен будет барьер на потоке-переключателе. И атомарность тут ни к чему — тут ведь не инкремент, а запись ненулевого значения туда, где было нулевое, все будет в порядке даже на платформах, где запись bool неатомарна (хотя такие вряд ли существуют).
Я на это уже ответил — я не знаю причин, почему именно этот пример не работал бы с volatile. Но он и без volatile может работать (у меня весь проект на работе такой) — можно проверить disasm что там нет неожиданностей.
Проблема x86 именно в том что там есть из коробки многие базовые вещи, предоставляемые атомиками — это и отсутствие reorder'а и когерентность кешей — ваш lock-free алгоритм может работать даже если написан неверно или вообще без атомиков.
Здравствуйте, у меня вопрос по примеру с мьютексом и синглтоном.
singleton->do_job() приводит к segmentation fault (указатель singleton не обязан был быть синхронизирован с потоком thread1)

Правильно ли я понимаю, что для того, чтобы указатель был синхронизирован с потоком thread1 необходимо вызвать
std::unique_lock l(mtx); // `mutex` locks here (acquire memory)

?
Как я понял именно в этот момент произойдет синхронизация памяти между потоками и указатель в thread2 станет валидным.
Да, вы правильно поняли. На самом деле нужно убрать предварительную проверку:
if (initialized) // early return to avoid touching mutex every call
	return;

А можно ли сделать initialized тоже атомиком?

Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.