Атомарная операция
Атомарная (греч. άτομος — неделимое) операция — операция, которая либо выполняется целиком, либо не выполняется вовсе; операция, которая не может быть частично выполнена и частично не выполнена.
В данной статье описываются простейшие атомарные операции (чтение, запись и т. п.), хотя термин может относиться к более высокоуровневым операциям, таким как, например, серия запросов к СУБД в рамках одной транзакции.
Атомарные операции используются в многопроцессорных компьютерах и в многозадачных операционных системах для обеспечения доступа нескольких процессов и/или нескольких потоков одного процесса к разделяемым между ними ресурсам. Атомарная операция выполняется только одним потоком.
Классификация
[править | править код]Атомарность операций может обеспечиваться аппаратно (аппаратурой) и программно (программным кодом). В первом случае используются особые машинные инструкции, атомарность выполнения которых гарантируется аппаратурой. Во втором случае используются специальные программные средства синхронизации, с помощью которых осуществляется блокировка разделяемого ресурса; после блокировки выполняется операция, которую требуется выполнить атомарно. Блокировка представляет собой атомарную операцию, которая либо предоставляет ресурс в пользование потоку, либо сообщает потоку о том, что ресурс уже используется другим потоком или процессом (занят).
Ассемблерные инструкции и атомарность
[править | править код]![]() | В разделе не хватает ссылок на источники (см. рекомендации по поиску). |
Машинные инструкции, выполнение которых всегда можно считать атомарным:
- машинные инструкции для чтения данных из памяти по выровненному адресу и записи их в регистр общего назначения;
- машинные инструкции для чтения данных из регистра общего назначения и записи их в память по выровненному адресу;
- машинные инструкции, специально созданные для работы атомарно и обычно называемые атомарными инструкциями.
Машинные инструкции, которые не являются атомарными:
- машинные инструкции для чтения/записи данных по невыровненному адресу (выполняя одну из таких инструкций, процессор вынужден выполнить обращение к двум ячейкам памяти. В момент, когда процессор обращается к одной ячейке, другая ячейка может быть изменена другим процессором);
- все машинные инструкции вида «чтение-модификация-запись»[источник не указан 709 дней] (выполнение одной такой инструкции сводится к чтению данных из памяти, изменению данных в АЛУ и записи данных в память. После чтения данных из памяти содержимое памяти может измениться);
- строковые машинные инструкции процессоров 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++ не означает реальной необходимости применения атомарных операций). В случае необходимости программист может использовать атомарные инструкции одним из следующих способов:
- вставить атомарные инструкции в код, используя предоставляемый компилятором ассемблер, например, GCC Inline Assembly компилятора gcc;
- использовать функции, предоставляемые компилятором и вызывающие атомарные инструкции, например, функции семейств __builtin_ или __sync_ компилятора gcc;
- использовать функции, предоставляемые библиотеками и вызывающие атомарные инструкции, например, функции библиотеки Glib;
- использовать языки программирования, поддерживающие атомарность, например, языки стандартов C11 и C++14, поддерживающие типы _Atomic и atomic и функции семейства atomic_[5].
См. также
[править | править код]Примечания
[править | править код]- ↑ CMPXCHG — Compare and exchange Архивная копия от 2 ноября 2012 на Wayback Machine.
- ↑ CMPXCHG8B — Compare and exchange 8 bytes Архивная копия от 30 ноября 2012 на Wayback Machine.
- ↑ 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.»
- ↑ Атомарные операции. История вопроса . Дата обращения: 12 ноября 2012. Архивировано 17 ноября 2012 года.
- ↑ 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 (англ.).
- Атомарные операции. Современный тренд