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

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

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

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

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

Описание[править | править вики-текст]

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

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

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

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

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

  • Чтение/запись данных по невыровненному адресу. Выполняя подобную инструкцию, процессор вынужден выполнить обращение к двум ячейкам памяти. В момент, когда процессор производит обращение к одной ячейке другая может быть модифицирована другим процессором.
  • Все операции Чтение-Модификация-Запись (англ.). Несмотря на то, что ассемблерная операция одна, ее выполнение сводится к чтению из памяти, изменению значения в АЛУ и записи в память. После чтения значение в памяти может измениться.
  • Строковые команды 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

Ссылки[править | править вики-текст]