Атомарная операция

Атомарная (греч. άτομος — неделимое) операция — операция, которая либо выполняется целиком, либо не выполняется вовсе; операция, которая не может быть частично выполнена и частично не выполнена.

В данной статье описываются простейшие атомарные операции (чтение, запись и т. п.), хотя термин может относиться к более высокоуровневым операциям, таким как, например, серия запросов к СУБД в рамках одной транзакции.

Атомарные операции используются в многопроцессорных компьютерах и в многозадачных операционных системах для обеспечения доступа нескольких процессов и/или нескольких потоков одного процесса к разделяемым между ними ресурсам. Атомарная операция выполняется только одним потоком.

Классификация

Атомарность операций может обеспечиваться аппаратно (аппаратурой) и программно (программным кодом). В первом случае используются особые машинные инструкции, атомарность выполнения которых гарантируется аппаратурой. Во втором случае используются специальные программные средства синхронизации, с помощью которых осуществляется блокировка разделяемого ресурса; после блокировки выполняется операция, которую требуется выполнить атомарно. Блокировка представляет собой атомарную операцию, которая либо предоставляет ресурс в пользование потоку, либо сообщает потоку о том, что ресурс уже используется другим потоком или процессом (занят).

Ассемблерные инструкции и атомарность

Основная статья: Инструкция (информатика)

Машинные инструкции, выполнение которых всегда можно считать атомарным:

• машинные инструкции для чтения данных из памяти по выровненному адресу и записи их в регистр общего назначения;
• машинные инструкции для чтения данных из регистра общего назначения и записи их в память по выровненному адресу;
• машинные инструкции, специально созданные для работы атомарно и обычно называемые атомарными инструкциями.

Машинные инструкции, которые не являются атомарными:

• машинные инструкции для чтения/записи данных по невыровненному адресу (выполняя одну из таких инструкций, процессор вынужден выполнить обращение к двум ячейкам памяти. В момент, когда процессор обращается к одной ячейке, другая ячейка может быть изменена другим процессором);
• все машинные инструкции вида «чтение-модификация-запись»^{[источник не указан 813 дней]} (выполнение одной такой инструкции сводится к чтению данных из памяти, изменению данных в АЛУ и записи данных в память. После чтения данных из памяти содержимое памяти может измениться);
• строковые машинные инструкции процессоров x86;
• машинные инструкции push и pop процессоров x86;
• машинные инструкции, работающие со специальными управляющими регистрами (подобные инструкции могут выполняться в течение нескольких процессорных тактов и порождать десятки или сотни обращений к памяти, используются только в системном программном обеспечении).

Атомарные инструкции процессоров x86

Атомарные инструкции процессоров архитектуры x86:

• CMPXCHG, CMPXCHG8B, CMPXCHG16B — основная атомарная инструкция процессоров x86, выполняющая сравнение и обмен. При использовании с префиксом LOCK^[1][2] атомарно сравнивает значение переменной с указанным значением и, в зависимости от результата сравнения, записывает в переменную указанное значение или ничего не делает. Является основой реализации всех безблокировочных алгоритмов, часто используется в реализации спинлоков, RWLock’ов и практически всех высокоуровневых синхронизирующих элементов, таких как семафоры, мьютексы, события и пр.;
• XCHG — операция для обмена данными между регистром и ячейкой памяти или между двумя регистрами. Атомарность этой операции имеет значение в случае, когда операндом команды выступает ячейка памяти. На процессорах x86 выполняется атомарно даже без использования префикса LOCK^[3] (по этой причине следует избегать применения этой команды просто для обмена значений регистра и ячейки памяти, это вызовет ненужные и весьма существенные задержки выполнения кода). Часто используется в реализации спинлоков.

Кроме того, многие машинные инструкции вида «чтение-модификация-запись» выполняются атомарно при наличии префикса LOCK^[4] (опкод 0xF0), например, следующие:

• команды сложения и вычитания ADD, ADC, SUB и SBB в случае, если операнд-приёмник — адрес ячейки памяти;
• команды инкремента и декремента INC и DEC;
• логические команды AND, OR и XOR;
• однооперандные команды NEG и NOT;
• битовые операции BTS, BTR и BTC;
• операция сложения и обмена XADD.

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

Атомарные инструкции процессоров RISC

Особенностью процессоров архитектур RISC является отсутствие инструкций вида «чтение-модификация-запись». В процессорах RISC с архитектурами DEC Alpha, PowerPC, MIPS и ARM (ARMv6 и старше) поддерживается механизм неблокирующего эксклюзивного доступа к памяти. Атомарные операции реализуются с использованием пары инструкций эксклюзивного чтения-записи LL и SC следующим образом:

• загрузка с пометкой (LL — load linked);
• изменение данных;
• попытка записи (SC — store conditional).

Первая инструкция (LL) загружает данные из ячейки памяти в регистр и помечает ячейку, как ячейку для эксклюзивного доступа. Далее производятся необходимые изменения данных в регистре. Запись данных из регистра в память (SC) производится только в том случае, если значение ячейки памяти не менялось. Если значение менялось, три операции (LL, изменение данных и SC) следует повторить.

Атомарные инструкции и компиляторы

Компиляторы языков высокого уровня, как правило, не используют при генерации кода атомарные инструкции, поскольку, во-первых, атомарные операции во много раз более ресурсоёмкие, чем обычные, а во-вторых, у компилятора нет информации о том, когда доступ к данным должен осуществляться атомарно (так как даже модификатор volatile для переменной в языках C/C++ не означает реальной необходимости применения атомарных операций). В случае необходимости программист может использовать атомарные инструкции одним из следующих способов:

1. вставить атомарные инструкции в код, используя предоставляемый компилятором ассемблер, например, GCC Inline Assembly компилятора gcc;
2. использовать функции, предоставляемые компилятором и вызывающие атомарные инструкции, например, функции семейств __builtin_ или __sync_ компилятора gcc;
3. использовать функции, предоставляемые библиотеками и вызывающие атомарные инструкции, например, функции библиотеки Glib;
4. использовать языки программирования, поддерживающие атомарность, например, языки стандартов C11 и C++14, поддерживающие типы _Atomic и atomic и функции семейства atomic_^[5].

См. также

• Сериализуемость
• Линеаризуемость
• Последовательная консистентность

Примечания

1. CMPXCHG — Compare and exchange Архивная копия от 2 ноября 2012 на Wayback Machine.
2. CMPXCHG8B — Compare and exchange 8 bytes Архивная копия от 30 ноября 2012 на Wayback Machine.
3. http://faydoc.tripod.com/cpu/xchg.htm Архивная копия от 20 ноября 2012 на Wayback Machine «If a memory operand is referenced, the processor’s locking protocol is automatically implemented for the duration of the exchange operation, regardless of the presence or absence of the LOCK prefix or of the value of the IOPL.»
4. Атомарные операции. История вопроса  (неопр.). Дата обращения: 12 ноября 2012. Архивировано 17 ноября 2012 года.
5. Atomic operations library — cppreference.com  (неопр.). Дата обращения: 12 ноября 2012. Архивировано 13 августа 2015 года.

Ссылки

• 3.1.3 Atomic Operations / Paul E. McKenney, Is Parallel Programming Hard, And, If So, What Can You Do About It? (page 31), 2016-07-31 (англ.).
• Linux-Kernel Memory Model. Atomic Operations / Paul E. McKenney, ISO/IEC JTC1 SC22 WG21 N4374 — 2015-02-06 (англ.).
• Evaluating the Cost of Atomic Operations on Modern Architectures / 2015 International Conference on Parallel Architecture and Compilation (PACT), 445—456 doi:10.1109/PACT.2015.24 (англ.).
• Atomic operation / OSDev Wiki (англ.).
• Atomic Operations в PCI-express (англ.).
• Атомарные операции. Современный тренд