Синхронизация против расслабленной атомики

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

Однако иногда я хочу проверить количество выделенных байтов (например, при закрытии программы), и я хочу убедиться, что все ожидающие записи зафиксированы. Я предполагаю, что в этом случае мне нужен полный барьер памяти, чтобы предотвратить перемещение любых предыдущих операций записи после барьера и предотвратить перемещение следующего чтения перед барьером.

Вопрос в том: каков правильный способ гарантировать, что расслабленные атомарные записи совершаются перед чтением? Мой текущий код правильный? (Предположим, что функции и типы соответствуют конструкциям библиотеки std, как и ожидалось.)

void* Allocator::Alloc(size_t bytes, size_t alignment)
{
    void* p = AlignedAlloc(bytes, alignment);
    AtomicFetchAdd(&allocatedBytes, AlignedMsize(p), MemoryOrder::Relaxed);
    return p;
}

void Allocator::Free(void* p)
{
    AtomicFetchSub(&allocatedBytes, AlignedMsize(p), MemoryOrder::Relaxed);
    AlignedFree(p);
}

size_t Allocator::GetAllocatedBytes()
{
    AtomicThreadFence(MemoryOrder::AcqRel);
    return AtomicLoad(&allocatedBytes, MemoryOrder::Relaxed);
}

И некоторые определения типов для контекста

enum struct MemoryOrder
{
    Relaxed = 0,
    Consume = 1,
    Acquire = 2,
    Release = 3,
    AcqRel = 4,
    SeqCst = 5,
};

struct Allocator
{
    void*  Alloc            (size_t bytes, size_t alignment);
    void   Free             (void* p);
    size_t GetAllocatedBytes();

    Atomic<size_t> allocatedBytes = { 0 };
};

Я не хочу просто по умолчанию использовать последовательную согласованность, поскольку я пытаюсь лучше понять порядок памяти.

Что меня действительно сбивает с толку, так это то, что в стандарте под [atomics.fences] все пункты говорят о синхронизации получения / атомарной операции с ограждением выпуска / атомарной операцией. Для меня совершенно непонятно, будет ли синхронизироваться операция "забор" / атомная операция с расслабленной атомарной операцией в другом потоке. Если функция ограждения AcqRel буквально отображается на инструкцию mfence, похоже, что приведенный выше код будет в порядке. Однако мне трудно убедить себя, что стандарт гарантирует это. А именно,

4 An atomic operation A that is a release operation on an atomic object M synchronizes with an acquire fence B if there exists some atomic operation X on M such that X is sequenced before B and reads the value written by A or a value written by any side effect in the release sequence headed by A.

Это, кажется, проясняет, что ограждение не будет синхронизироваться с расслабленной атомарной записью. С другой стороны, полное ограждение - это одновременно и освобождение, и ограничение приобретения, поэтому оно должно синхронизироваться с самим собой, верно?

2 A release fence A synchronizes with an acquire fence B if there exist atomic operations X and Y, both operating on some atomic object M, such that A is sequenced before X, X modifies M, Y is sequenced before B, and Y reads the value written by X or a value written by any side effect in the hypothetical release sequence X would head if it were a release operation.

Описанный сценарий

  • Неупорядоченные записи
  • Забор выпуска
  • X атомарная запись
  • Y атомарное чтение
  • B приобрести забор
  • Неупорядоченные чтения (здесь будут видны неупорядоченные записи)

Однако в моем случае у меня нет атомарной записи + атомарного чтения, поскольку сигнал между потоками и ограничением выпуска происходит с ограничением получения в потоке B. Итак, что на самом деле происходит,

  • Неупорядоченные записи
  • Забор выпуска
  • B приобрести забор
  • Неупорядоченные чтения

Ясно, что если забор выполняется до того, как начинается непоследовательная запись, это гонка, и все ставки отключены. Но мне кажется, что если ограждение выполняется после того, как начинается неупорядоченная запись, но до того, как она будет зафиксирована, она будет принудительно завершена до неупорядоченного чтения. Это именно то, что я хочу, но я не могу понять, является ли это гарантированный по стандарту.

«Я не хочу просто по умолчанию использовать последовательную согласованность» - в этом случае я будет. Поскольку это дало бы мне необходимую гарантию, и стоимость, вероятно, будет незначительной / незаметной, и я бы не стал доверять себе, чтобы получить более умные вещи, правильные для всех случаев (и я действительно, В самом деле ненавидит отладку тонких ошибок потоковой передачи, которые воспроизводятся только один раз в синюю луну и только на производственных системах клиентов в 3 часа ночи, когда они делают что-то важное / дорогое).

Jesper Juhl 13.09.2018 18:58

Конечно. Но все дело в том, чтобы понять.

Adam 13.09.2018 18:59

Я понимаю это (и поддержал ваш вопрос, потому что я думаю, что это действительно интересно и важно знать). Я просто давал вам прагматический взгляд на мой (в комментарии).

Jesper Juhl 13.09.2018 19:02

@JesperJuhl Какую более сильную гарантию дает последовательная согласованность в этом случае? невозможно определить, отражает ли загруженное значение последнее состояние памяти, поскольку синхронизация времени выполнения отсутствует.

LWimsey 13.09.2018 21:15

Я думаю, он имеет в виду выполнение операций с выделенным байтом SeqCst и снятие ограждения. Если бы они были, то каждое чтение и запись были бы синхронизированы.

Adam 13.09.2018 21:19

Если все, что вам нужно, это общая память, выделенная при завершении программы, вам просто нужно прочитать значение после того, как все порожденные потоки будут объединены.

Oliv 13.09.2018 21:46

Помимо объединения всех потоков, единственное решение для получения того, что вы хотите, - это заблокировать все потоки, но не тот, который читает выделенную память. Полный барьер памяти вам не поможет, потому что все может произойти сразу после выполнения этого барьера (вытеснение потоков и т. д.), И все ставки будут отключены!

Oliv 13.09.2018 22:17

Завершение работы является примером, но вопрос не ограничивается этим сценарием. Вопрос в том, чтобы синхронизировать расслабленную запись перед чтением. Я изо всех сил пытаюсь понять, насколько актуально приоритетное прерывание, когда цель состоит в том, чтобы «убедиться, что уже выполненные записи глобально видны, прежде чем я сделаю это чтение». Вытеснение потока каким-либо образом не отменяет ни запись, ни любую другую известную мне операцию.

Adam 14.09.2018 01:41

Ваше выражение «синхронизация расслабленной записи перед чтением» заставляет меня сомневаться в том, что вы ищете.

Oliv 14.09.2018 07:34

@JesperJuhl LWimsey прав, усиление отдельных операций для SeqCst не изменит поведения этого примера. Этот пример уже является потокобезопасным и свободен от «гонок данных» C++ (при условии, что распределитель внутренне безопасен). Путаница возникает из-за того, что Адам рассматривает сценарии, в которых вызовы к Allocator пересекаются друг с другом, а затем пытается рассуждать о них, как если бы они были заказаны.

preshing 14.09.2018 14:52

@Adam Я работал над многими играми, где мы делали именно это: считывали количество выделенных байтов, пока в других потоках все еще есть параллельные Alloc() / Free(). Обычно мы делали это, потому что просто хотели напечатать число на экране, зарегистрировать его или нарисовать на графике. Ни одно из этих значений не гарантированно было «последним» (опять же, не существует такого понятия, как «последнее», если писатели не синхронизированы с устройством чтения), и на практике значения могли быть «старыми» всего на несколько десятков циклов, что является правда ничего. У нас по-прежнему есть значимые ценности, и этого было достаточно.

preshing 14.09.2018 15:01
8
11
527
3

Ответы 3

Это не будет работать должным образом, порядок памяти acq_rel разработан специально для операций с памятью CAS и FAA, которые "одновременно" читают и записывают атомарные данные. В вашем случае вы хотите принудительно синхронизировать память перед загрузкой. Для этого вам необходимо изменить порядок памяти ваших fetchAndAdd и fetchAndSub на acq_rel и вашей нагрузки на acquire. Это может показаться большим, но на x86 это имеет очень небольшую стоимость (некоторые оптимизации компилятора), поскольку не генерирует никаких новых инструкций в коде. Что касается того, как работает синхронизация получения и выпуска, я рекомендую эту статью: http://preshing.com/20120913/acquire-and-release-semantics/

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

Насколько я понимаю атомарность C++, ослабленный порядок памяти имеет смысл при использовании в сочетании с другими атомарными операциями с использованием ограждений памяти. Например, в некоторых ситуациях атомарный a может храниться расслабленным образом, поскольку атомарный b записывается с порядком освобождения памяти и так далее.

Это не работает, так как вам нужна взаимосвязь времени выполнения (которая учитывает измененное значение), чтобы делать что-то полезное. Недостаточно только усилить упорядочение памяти

LWimsey 13.09.2018 21:13

Что ЦП по-другому будет делать в случае 1? У нас есть ситуация, когда в Core 1 могут быть буферизованные хранилища. Core 0 приходит и говорит: «Все очистите буферы хранилища, у меня есть важное чтение». Но есть ли способ у Core 0 сделать это? ARM gcc 7.2.1 генерирует одинаковый __sync_synchronize как для AcqRel, так и для SeqCst godbolt.org/z/zL8MI-. x86-64 генерирует защиту в обоих случаях. Кажется, что каждая из этих инструкций работает только на одном ядре, которое ее выполняет.

Adam 13.09.2018 21:16

Спасибо за информацию, тогда пересмотрю свой ответ.

bartop 13.09.2018 21:23

Допустим, вы создаете поток A, который вызывает Allocator::Alloc(), а затем сразу же вызываете поток B, который вызывает Allocator::GetAllocatedBytes(). Эти два вызова Allocator теперь выполняются одновременно. Вы не знаете, что на самом деле произойдет первым, потому что между ними нет порядка. Ваша единственная гарантия состоит в том, что либо поток B увидит значение allocatedBytes до того, как поток A изменит его, либо он увидит значение allocatedBytes после того, как поток A изменит его. Вы не узнаете, какое значение увидел поток B, пока не вернется GetAllocatedBytes(). (По крайней мере, поток B не увидит полностью мусорное значение для allocatedBytes, потому что на нем нет гонки данных благодаря использованию расслабленной атомики.)

Похоже, вас беспокоит случай, когда поток A дошел до AtomicFetchAdd(), но по какой-то причине изменение не видно, когда поток B вызывает AtomicLoad(). Но что с того? Это не отличается от результата, когда GetAllocatedBytes() работает полностью до AtomicFetchAdd(). И это абсолютно верный результат. Помните, либо поток B видит измененное значение, либо нет.

Даже если вы измените все атомарные операции / ограждения на MemoryOrder::SeqCst, это не будет иметь никакого значения. В описанном мной сценарии поток B все еще может видеть либо измененное значение, либо немодифицированное значение allocatedBytes, потому что два вызова Allocator выполняются одновременно.

Пока вы настаиваете на вызове GetAllocatedBytes(), в то время как другие потоки все еще вызывают Alloc() и Free(), это действительно максимум, чего вы можете ожидать. Если вы хотите получить более «точное» значение, просто не разрешайте одновременные вызовы Alloc() / Free(), пока GetAllocatedBytes() работает! Например, если программа закрывается, просто присоединитесь ко всем другим потокам перед вызовом GetAllocatedBytes(). Это даст вам точное количество выделенных байтов при завершении работы. Стандарт C++ даже гарантирует это, потому что завершение потока синхронизируется с вызовом join ().

Ситуация, которая меня беспокоит, такова: предположим, что поток B знает Поток A выполнил расслабленный атомарный подпрограмм. Затем B вызывает GetAllocatedBytes(). Возможно ли, что B прочитает значение allocatedBytesдо, запись будет видна глобально? Может ли запись все еще быть, например, в буфере хранилища других ядер?

Adam 14.09.2018 06:20

@Adam Как поток B узнает, что A выполнен Alloc? Для этого нужна синхронизация. И на этом этапе имеет смысл использовать мьютекс, атомарный забор или только одну атомарную переменную с релизом и (в B) получением. Тогда вы сможете убедиться, что получили правильное значение.

phön 14.09.2018 09:07

Для потока B совершенно невозможно знать, что поток A выполнил ослабленный атомарный пока не, некоторая информация передается между потоками, которая подтверждает это. Это может быть присоединение к потоку, это может быть отдельная атомарная защитная переменная (не показана в вашем примере), или это может быть передано с помощью переменной мьютекса / условия. Приятно то, что каждый механизм для В самом деле, зная, что произошла атомарная запись, также позволяет вам установить связь «синхронизируется с» между потоками, если все сделано правильно preshing.com/20130823/the-synchronizes-with-relation

preshing 14.09.2018 14:11

Если ваш вопрос каков правильный способ гарантировать, что расслабленные атомарные записи совершаются перед чтением это тот же атомарный объект? Ничего, это обеспечивается языком [intro.multithread]:

All modifications to a particular atomic object M occur in some particular total order, called the modification order of M.

Все потоки видят один и тот же порядок модификации. Например, представьте, что 2 распределения происходят в 2 разных потоках, а затем вы читаете счетчик в третьем потоке.

В первом потоке атомар увеличивается на 1 байт, а расслабленное выражение чтения / изменения (AtomicFetchAdd) возвращает 0: счетчик сделал этот переход: 0-> 1.

Во втором потоке атомар увеличивается на 2 байта, а расслабленное выражение чтения / изменения возвращает 1: счетчик выполняет этот переход: 1-> 3. Выражение чтения / изменения не может вернуть 0. Этот поток не может видеть переход 0-> 2, потому что другой поток выполнил переход 0-> 1.

Затем в третьем потоке вы выполняете расслабленную нагрузку. Единственные возможные значения, которые могут быть загружены: 0,1 или 3. Невозможно загрузить 2. Порядок модификации атома: 0 -> 1 -> 3. И поток наблюдателя также увидит этот порядок модификации.

Это то, что я имею в виду под «по крайней мере, поток B не увидит полностью мусорное значение» в моем ответе. Как вы сказали, он увидит одно из значений в порядке модификации allocatedBytes. Однако нет гарантии, что поток B увидит «последнее» значение, потому что, если allocatedBytes модифицируется одновременно, понятие «последнее» даже не существует. Если мы хотим, чтобы была концепция «последнего» значения, должна быть какая-то синхронизация, выполняемая где-то еще.

preshing 14.09.2018 14:39

@preshing Я с тобой согласен. Я не думаю, что цель состоит в том, чтобы дать лучший ответ, но сейчас это понимание того, о чем он на самом деле спрашивает. Его вопрос настолько странный, насколько мне известно, в нем нет смысла ... потому что он не знает чего-то фундаментального. Итак, я подумал, что, возможно, он пытался гарантировать, что это единый полный заказ для его атомного счетчика, потому что он не знал, что это также гарантировано расслабленной атомной операцией.

Oliv 14.09.2018 18:39

@preshing Как в релятивистском мире, есть нет глобального времени и нет правильных часов!

curiousguy 25.10.2019 03:03

Другие вопросы по теме