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

Материал из Википедии — свободной энциклопедии
(перенаправлено с «Атомарность»)
Перейти к: навигация, поиск

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

Атомарная операция открыта влиянию только одного потока.

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

Описание[править | править исходный текст]

Зачастую атомарная операция представляет собой ассемблерную инструкцию, однако не обязательно. Также, что более существенно, не каждая ассемблерная инструкция атомарна.

Ассемблерные инструкции и атомарность[править | править исходный текст]

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

  • Все инструкции вида Операция Регистр-Регистр можно считать атомарными так как регистры за пределами вычислительного процессорного ядра не видны
  • Загрузка данных из памяти по выровненному адресу в регистр общего назначения
  • Сохранение данных из регистра общего назначения в память по выровненному адресу
  • Специальные операции для атомарной работы (их обычно и называют атомарными операциями, предмет данной статьи)

Операции, которые не являются атомарными:

  • Чтение/запись данные по невыровненному адресу. Выполняя подобную инструкцию процессор вынужден выполнить обращение к двум ячейкам памяти. В момент когда процессор производит обращение к одной ячейке другая может быть модифицирована другим процессором.
  • Все Операции Чтение-Модификация-Запись (англ.). Несмотря на то что ассемблерная операция одна, ее выполнение сводится к чтению из памяти, изменению значения в АЛУ и записи в память. После чтения значение в памяти может измениться.
  • Строковые команды x86
  • Команды push/pop x86
  • Операции с специальными управляющими регистрами. Могут занимать многие процессорные такты и иногда порождает десятки а иногда и сотни обращений к памяти. Такие операции встречаются только в системном программном обеспечении.

Атомарные инструкции x86[править | править исходный текст]

  • CMPXCHG/CMPXCHG8B/CMPXCHG16B — основная атомарная команда x86 сравнение и обмен. При использовании с префиксом LOCK[1][2] выполняет атомарно сравнение переменной с указанным значением и пересылку в зависимости от данного сравнения. Является основой реализации всех безблокировочных алгоритмов. Часто используется в реализации спинлоков и RWLock'ов, а также практически всех высокоуровневых синхронизирующих элементов таких как Семафоры, Мьютексы, События и пр в качестве внутренней реализации
  • XCHG — Операция обмена между памятью и регистром выполняется атомарно на x86-процессорах.[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). Если операция не выполнена, следует повторить всю последовательность операций от момента чтения переменной из памяти до попытки сохранения в память.

Атомарные инструкции и компилятор[править | править исходный текст]

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

  1. Ассемблерная вставка соответствующей атомарной инструкции
  2. Использование расширения компилятора (функции семейства __builtin_ или __sync_)
  3. Использование «высокоуровневой» обертки в виде специальной библиотеки, например, Glib
  4. Использование новых языков C11 или C++11, поддерживающих типы _Atomic и atomic и функции семейства atomic_[5]

См. также[править | править исходный текст]

Примечания[править | править исходный текст]

  1. CMPXCHG - Compare and Exchange
  2. CMPXCHG8B - Compare and Exchange 8 Bytes
  3. http://faydoc.tripod.com/cpu/xchg.htm " 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. Атомарные операции. История вопроса
  5. Atomic operations library - cppreference.com

Ссылки[править | править исходный текст]