Перевод статьи Джефа Прешинга Atomic vs. Non-Atomic Operations. Оригинальная статья: http://preshing.com/20130618/atomic-vs-non-atomic-operations/
В Сети уже очень много написано об атомарных операциях, но в основном авторы рассматривают операции чтения-модификации-записи. Однако, существуют и другие атомарные операции, например, атомарные операции загрузки (load) и сохранения (store), которые не менее важны. В этой статье я сравню атомарные загрузки и сохранения с их неатомарными аналогами на уровне процессора и компилятора C/C++. По ходу статьи мы также разберемся с концепцией «состояния гонок» с точки зрения стандарта C++11.
Операция в общей области памяти называется атомарной, если она завершается в один шаг относительно других потоков, имеющих доступ к этой памяти. Во время выполнения такой операции над переменной, ни один поток не может наблюдать изменение наполовину завершенным. Атомарная загрузка гарантирует, что переменная будет загружена целиком в один момент времени. Неатомарные операции не дают такой гарантии.
Без подобных гарантии неблокирующее программирование было бы невозможно, поскольку было бы нельзя разрешить нескольким потокам оперировать одновременно одной переменной. Мы можем сформулировать правило:
В любой момент времени когда два потока одновременно оперируют общей переменной, и один из них производит запись, оба потока обязаны использовать атомарные операции.
Если вы нарушаете это правило, и каждый поток использует неатомарные операции, вы оказываетесь в ситауции, которую стандарт C++11 называет состояние гонок по данным (data race) (не путайте с похожей концепцией из Java, или более общим понятием состояния гонок (race condition)). Стандарт C++11 не объясняет, почему состояние гонок плохо, однако утверждает, что в таком состоянии вы получите неопределенное поведение (§1.10.21). Причина опасности таких состояний гонок, однако, очень проста: в них операции чтения и записи разорваны (torn read/write).
Операция с памятью может быть неатомарной даже на одноядерном процессоре только потому, что она использует несколько инструкций процессора. Однако и одна инструкция процессора на некоторых платформах также может быть неатомарной. Поэтому, если вы пишите переносимый код для другой платформы, вы никак не можете опираться на предположение об атомарности отдельной инструкции. Давайте рассмотрим несколько примеров.
Неатомарные операции из нескольких инструкций
Допустим, у нас есть 64-битная глобальная переменная, инициализированная нулем.
uint64_t sharedValue = 0;
В какой-то момент времени мы присвоим ей значение:
void storeValue()
{
sharedValue = 0x100000002;
}
Если мы скомпилируем этот код с помощью 32-битного компилятора GCC, мы получим такой машинный код:
$ gcc -O2 -S -masm=intel test.c
$ cat test.s
...
mov DWORD PTR sharedValue, 2
mov DWORD PTR sharedValue+4, 1
ret
...
Видно, что компилятор реализовал 64-битное присваивание с помощью двух процессорных инструкций. Первая инструкция присваивае нижним 32 битам значение 0x00000002, и вторая заносит в верхние биты значение 0x00000001. Очевидно, что такое присваивание неатомарно. Если к переменной sharedValue одновременно пытаются получить доступ различные потоки, можно получить несколько ошибочных ситуаций:
- Если поток, вызывающий storeValue, будет прерван между двумя инструкциями записи, то он оставит в памяти значение 0x0000000000000002 — это разорванная операция записи. Если в этот момент другой поток попытается прочитать sharedValue, он получит неправильное значение, которое никто и не собирался сохранять.
- Более того, если записывающий поток был остановлен между инструкциями записи, а другой поток поменяет значение sharedValue перед тем, как первый поток возобновит работу, мы получим постоянно разорванную запись: верхняя половина значения переменной будет установлена одним потоком, а нижняя — вторым.
- Чтобы получить разорванную запись на мультиядерных процессорах потоки даже не нужно прерывать: любой поток, выполняющийся на другом ядре, может прочитать значение переменной в момент, когда только половина нового значения записана в память.
Параллельное чтение из sharedVariable также имеет свои проблемы:
uint64_t loadValue()
{
return sharedValue;
}
$ gcc -O2 -S -masm=intel test.c
$ cat test.s
...
mov eax, DWORD PTR sharedValue
mov edx, DWORD PTR sharedValue+4
ret
...
Здесь таким же образом компилятор реализует чтение двумя инструкциями: сначала нижние 32 бита считываются в регистр EAX, а потом верхние 32 бита считываются в EDX. В этом случае, если параллельная запись будет произведена между этими двумя инструкциями, мы получим разорванную операцию считывания, даже если запись была атомарной.
Эти проблемы отнюдь не теоретические. Тесты библиотеки Mintomic включает тест test_load_store_64_fail, в котором один поток сохраняет набор 64-битных значений в переменную используя обычный оператор присваивания, а другой поток производит обычную загрузку из той же самой переменной, проверяя результат каждой операции. В многопоточном режиме x86 этот тест ожидаемо падает.
Неатомарные инструкции процессора
Операция с памятью может быть неатомарной даже если она выполняется одной инструкцией процессора. Например, в наборе инструкций ARMv7 есть инструкция strd, которая сохраняет содержимое двух 32-битных регистров в 64-битной переменной в памяти.
strd r0, r1, [r2]
На некоторых ARMv7 процессорах эта инструкция не является атомарной. Когда процессор видит такую инструкцию, он на самом деле выполняет две отдельные операции (§A3.5.3). Как и в предыдущем примере, другой поток, выполняющийся на другом ядре, может попасть в ситуацию разорванной записи. Интересно, что ситуация разорванной записи может возникнуть и на одном ядре: системное прерывание — скажем, для запланированной смены контекста потока — может возникнуть между внутренними операциями 32-битного сохранения! В этом случае, когда поток возобновит свою работу, он начнет выполнять инструкцию strd заново.
Другой пример, всем известная операция архитектуры x86, 32-битная операция mov атомарна в том случае, когда операнд в памяти выровнен, и не атомарна в противном случае. То есть, атомарность гарантируется только в случае, когда 32-битное целое число находится по адресу, который делится на 4. Mintimoc содержит тестовый пример test_load_store_32_fail, который проверяет это условие. Этот тест всегда выполняется успешно на x86, но если его модифицировать так, чтобы переменная sharedInt находилась по невыровненному адресу, тест упадет. На моем Core 2 Quad 6600 тест падает, когда sharedInt разделен между различными линиями кеша:
// Force sharedInt to cross a cache line boundary:
#pragma pack(2)
MINT_DECL_ALIGNED(static struct, 64)
{
char padding[62];
mint_atomic32_t sharedInt;
}
g_wrapper;
Думаю, мы рассмотрели достаточно нюансов процессорного выполнения. Давайте взглянем на атомарность на уровне C/C++.
Все операции C/C++ считаются неатомарными
В C/C++ каждая операция считается неатомарной до тех пор, пока другое не будет явно указано прозводителем компилятора или аппаратной платформы — даже обычное 32-битное присваивание.
uint32_t foo = 0;
void storeFoo()
{
foo = 0x80286;
}
Стандарты языка ничего не говорят по поводу атомарности в этом случае. Возможно, целочисленное присваивание атомарно, может быть нет. Поскольку неатомарные операции не дают никаких гарантий, обычное целочисленное присваивание в C является неатомарным по определению.
На практике мы обычно обладаем некоторой информацией о платформах, для которых создается код. Например, мы обычно знаем, что на всех современных процессорах x86, x64, Itanium, SPARC, ARM и PowerPC обычное 32-битное присваивание атомарно в том случае, если переменная назначения выровнена. В этом можно убедиться, перечитав соответствующий раздел документации процессора и/или компилятора. Я могу сказать, что в игровой индустрии атомарность очень многих 32-битных присваиваний гарантируется этим конкретным свойством.
Как бы там ни было, при написании действительно переносимого кода C и C++, мы следуем давно установившейся традиции считать, что мы не знаем ничего более того, что нам говорят стандарты языка. Переносимые C и C++ спроектированы так, чтобы выполнятся на любом возможном вычислительном устройстве прошлого, настоящего и будущего. Я, например, люблю представлять устройство, память которого можно менять только предварительно заполнив ее случайным мусором:
На таком устройстве вы уж точно не захотите произвести параллальное считывание, так же как и обычное присваивание, потому что слишком высок риск получить в результате случайное значение.
В C++11 наконец-то появился способ выполнять действительно переносимые атомарные сохранения и загрузки. Эти операции, произведенные с помощью атомарной библиотеки C++11 будут работать даже на условном устройстве, описанном ранее: даже если это будет означать, что библиотеке прийдется блокировать мьютекс для того, чтобы сделать каждую операцию атомарной. Моя библиотека Mintomic которую я выпустил недавно, не поддерживает такое количество различных платформ, но работает на некоторых старых компьютерах, оптимизирована вручную и гарантировано неблокирующая.
Расслабленные (relaxed) атомарные операции
Давайте вернемся к примеру с sharedValuem который мы рассматривали в начале. Давайте перепишем его с использованием Mintomic так, чтобы все операции выполнялись атомарно на каждой платформе, которую поддерживает Mintomic. Для начала мы объявим sharedValue как один из атомарных типов Mintomic:
#include <mintomic/mintomic.h>
mint_atomic64_t sharedValue = { 0 };
Тип mint_atomic64_t гарантирует корректное выравнивание в памяти для атомарного доступа на каждой платформе. Это важно, поскольку, например, компилятор gcc 4.2 для ARM в среде разработки Xcode 3.2.5 не гарантирует, что тип uint64_t будет выровнен на 8 байтов.
В функции storeValue вместо выполнения обычного неатомарного присваивания, мы должны выполнить mint_store_64_relaxed.
void storeValue()
{
mint_store_64_relaxed(&sharedValue, 0x100000002);
}
Аналогично, в loadValue мы вызываем mint_load_64_relaxed.
uint64_t loadValue()
{
return mint_load_64_relaxed(&sharedValue);
}
Если использовать терминологию C++11, то эти функции сейчас свободны от состояний гонок по данным (data race free). Если они будут вызваны одновременно, абсолютно невозможно оказаться в ситуации разорванного чтения или записи, независимо от того, на какой платформе выполняется код: ARMv6/ARMv7(режимы Thumb или ARM), x86, x64 или PowerPC. Если вам интересно как работают mint_load_64_relaxed и mint_store_64_relaxed, то обе функции используют инструкцию cmpxchg8b на платформе x86. Подробности реализации для других платформ можно найти в реализации Mintomic.
Вот такой же код с использованием стандартной библиотеки C++11:
#include <atomic>
std::atomic<uint64_t> sharedValue(0);
void storeValue()
{
sharedValue.store(0x100000002, std::memory_order_relaxed);
}
uint64_t loadValue()
{
return sharedValue.load(std::memory_order_relaxed);
}
uint64_t loadValue()
{
return mint_load_64_relaxed(&sharedValue);
}
Вы должны были заметить, что оба примера используют расслабленные атомарные операции, что подтверждается суффиксом _relaxed в идентификаторах. Этот суффикс напоминает об определенных гарантиях относительно упорядочивания памяти (memory ordering).
В частности, для таких операций допукается переупорядочивание операций с памятью в соответствии с переупорядочиванием компилятором либо с переупорядочиванием памяти процессором. Компилятор даже может оптимизировать избыточные атомарные операции, так же как и неатомарные. Но во всех этих случаях атомарность оперций сохраняется.
Я думаю, что в случае выполнения параллельных операций с памятью, использование функций атомарных библиотек Mintomic или C++11 является хорошей практикой, даже если вы уверены, что обычные операции чтения либо записи будут атомарны на спользуемой вами платформе. Использование атомарных библиотек будет служить лишним напоминанием, что переменные могут быть использованы в конкурентной среде.
Надеюсь, теперь вам стало понятнее, почему Самая простая в мире неблокирующая хэш-таблица использует Mintomic для манипуляции общей памятью одновременно с другими потоками.
Об авторе. Джефф Прешинг работает архитектором ПО в игровой компании Ubisoft и специализируется на многопоточном программировании и неблокирующих алгоритмах. В этом году он делал доклад о многопоточной разработке игр в соответствии со стандартом С++11 на конференции CppCon, видео этого доклада было и на Хабре. Он ведет интересный блог Preshing on Programming, посвященный в том числе и тонкостям неблокирующего программирования и связанных с ним нюансов C++.
Я бы хотел много статей из его блога перевести для сообщества, но поскольку его записи часто ссылаются одна на другую, выбрать статью для первого перевода достаточно сложно. Я попытался выбрать такую статью, которая бы минимально базировалась на других. Хотя рассматриваемый вопрос достаточно прост, я надеюсь, он все же будет интересен многим, кто начинает знакомиться с многопоточным программированием в C++.
