Открыть сервис
Главная → Блог → Атомарная операция

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

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

История и происхождение понятия

Понятие атомарности восходит к теории баз данных и транзакций, сформулированной в 1970-х годах. Одним из основоположников реляционной модели данных, Эдгаром Коддом, были определены правила целостности, включающие требование неделимости транзакций. В 1983 году группа исследователей во главе с Тео Хардером и Андреасом Ройтером формализовала свойства ACID (Atomicity, Consistency, Isolation, Durability — атомарность, согласованность, изоляция, долговечность), где атомарность стоит на первом месте.

С развитием многопроцессорных систем и многопоточного программирования в 1980–1990-х годах понятие атомарности перешло в область аппаратного обеспечения. Процессоры начали поддерживать специальные инструкции, позволяющие выполнять операции чтения-модификации-записи без прерывания. Первые такие инструкции, например, Test-and-Set (проверка и установка) и Compare-and-Swap (сравнение с обменом), появились в архитектурах IBM System/370 и DEC VAX.

Свойства атомарной операции

Атомарная операция обладает тремя фундаментальными свойствами:

  • Неделимость (Indivisibility): Операция не может быть разделена на более мелкие шаги, видимые для других потоков. С точки зрения внешнего наблюдателя, она происходит мгновенно.
  • Линеаризуемость (Linearizability): Результат операции становится видимым для всех остальных потоков только после её полного завершения. Это гарантирует, что порядок выполнения атомарных операций в системе является строгим и последовательным.
  • Отсутствие частичного эффекта (All-or-Nothing): Если операция прерывается (например, из-за сбоя питания), система откатывается к состоянию, предшествовавшему началу операции. Никакие промежуточные изменения не сохраняются.

Классификация атомарных операций

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

По уровню реализации

  • Аппаратные (Hardware Atomic Operations): Реализуются на уровне инструкций центрального процессора (ЦП). Примеры: XCHG (обмен) в архитектуре x86, LDREX/STREX (эксклюзивная загрузка/сохранение) в ARM, CAS (Compare-and-Swap) в большинстве современных процессоров. Эти инструкции гарантируют атомарность на уровне кэш-линии или шины памяти.
  • Программные (Software Atomic Operations): Реализуются на уровне операционной системы или языка программирования с использованием блокировок, семафоров или мьютексов. Хотя сами по себе блокировки не являются атомарными, они обеспечивают атомарность критических секций кода. Примеры: std::atomic в C++, java.util.concurrent.atomic в Java, Interlocked в .NET.
  • Транзакционные (Transactional Operations): Реализуются в системах управления базами данных (СУБД) и некоторых языках программирования (например, Software Transactional Memory). В этом случае атомарность применяется к целой группе операций, объединённых в транзакцию.

По типу действия

  • Чтение-модификация-запись (Read-Modify-Write, RMW): Операция, которая читает значение из памяти, изменяет его и записывает обратно. Примеры: Fetch-and-Add (увеличить значение на 1), Test-and-Set (установить флаг в 1 и вернуть старое значение), Compare-and-Swap (сравнить значение с ожидаемым и, если совпадает, заменить новым).
  • Атомарная загрузка и сохранение (Atomic Load/Store): Простейшие операции, гарантирующие, что чтение или запись одного машинного слова (обычно 4 или 8 байт) происходит без прерывания. На современных процессорах выровненные обращения к памяти обычно атомарны по умолчанию.
  • Атомарные флаги (Atomic Flags): Булевы переменные, поддерживающие атомарные операции установки и сброса. Часто используются для реализации спин-блокировок.

Применение атомарных операций

Атомарные операции являются фундаментом для построения надёжных и производительных параллельных систем.

В многопоточном программировании

  • Счётчики и счётчики ссылок: Атомарное увеличение и уменьшение счётчиков (например, fetch_add) используется для подсчёта количества активных потоков или ссылок на объект (std::shared_ptr в C++).
  • Спин-блокировки (Spinlocks): Реализуются с помощью атомарных операций Test-and-Set или Compare-and-Swap. Поток в цикле пытается атомарно захватить флаг блокировки, пока это не удастся.
  • Безблокировочные структуры данных (Lock-Free Data Structures): Стеки, очереди и хеш-таблицы, которые не используют блокировки, а опираются исключительно на атомарные операции (например, CAS) для обеспечения корректности. Это позволяет избежать проблем, связанных с блокировками, таких как взаимные блокировки (deadlocks) и инверсия приоритетов.
  • Барьеры памяти (Memory Barriers): Атомарные операции часто используются в сочетании с барьерами памяти для обеспечения видимости изменений между потоками. Например, std::memory_order_release и std::memory_order_acquire в C++.

В операционных системах

  • Планировщик задач: Атомарные операции используются для безопасного изменения очередей готовых к выполнению потоков.
  • Системные вызовы: Многие системные вызовы, такие как создание процессов или работа с файловыми дескрипторами, внутренне используют атомарные инструкции для синхронизации доступа к структурам ядра.

В базах данных и распределённых системах

  • Транзакции ACID: Атомарность транзакций гарантирует, что либо все операции внутри транзакции будут применены, либо ни одна. Это реализуется с помощью журналов упреждающей записи (Write-Ahead Logging, WAL) и механизмов отката (rollback).
  • Распределённые блокировки: В системах вроде ZooKeeper или etcd атомарные операции (например, create с флагом EPHEMERAL) используются для реализации распределённых мьютексов.
  • Консенсусные алгоритмы: Алгоритмы вроде Paxos и Raft требуют атомарной записи в журнал на большинстве узлов для достижения консенсуса.

Примеры в языках программирования

C++

В C++ атомарные операции предоставляются шаблоном std::atomic<T> (начиная с C++11). Пример атомарного счётчика:

```cpp

include <atomic>

std::atomic<int> counter(0);

void increment() { counter.fetch_add(1, std::memory_order_relaxed); // Атомарное увеличение } ```

Java

В Java атомарные классы находятся в пакете java.util.concurrent.atomic. Пример:

```java import java.util.concurrent.atomic.AtomicInteger; AtomicInteger counter = new AtomicInteger(0);

public void increment() { counter.incrementAndGet(); // Атомарное увеличение и возврат нового значения } ```

C# ( .NET )

В C# атомарные операции предоставляются классом Interlocked:

```csharp using System.Threading; int counter = 0;

void Increment() { Interlocked.Increment(ref counter); // Атомарное увеличение } ```

Критика и ограничения

Несмотря на свою полезность, атомарные операции имеют ряд ограничений:

  • Производительность: Атомарные операции на аппаратном уровне могут быть значительно медленнее обычных операций, так как они требуют блокировки шины памяти или кэш-линии, что приводит к инвалидации кэша у других ядер процессора. Это может снизить общую производительность системы при интенсивном использовании.
  • Сложность отладки: Ошибки, связанные с неправильным использованием атомарных операций (например, неправильный выбор порядка памяти), могут приводить к трудно воспроизводимым состояниям гонки.
  • Ограниченный набор операций: Атомарные операции поддерживают только простые типы данных (целые числа, указатели, флаги). Для сложных структур данных требуются либо блокировки, либо безблокировочные алгоритмы, которые сложны в реализации.
  • Проблема ABA: При использовании операции Compare-and-Swap может возникнуть ситуация, когда значение переменной меняется с A на B, а затем обратно на A, и операция CAS не замечает этого изменения, считая, что ничего не произошло. Для решения этой проблемы используются версии CAS с тегами (например, double-width CAS) или счётчики.

Источники

  1. Морис Херлихи, Ним Шавит. «Искусство многопроцессорного программирования». — ДМК Пресс, 2014.
  2. Эндрю Таненбаум, Херберт Бос. «Современные операционные системы». — 4-е изд. — Питер, 2015.
  3. Брайан Гетц и др. «Java Concurrency on Practice». — Addison-Wesley, 2006.
  4. Пол Дж. Лейк. «C++ Concurrency in Action». — 2nd ed. — Manning Publications, 2019.
  5. Стандарт ISO/IEC 14882:2020 (C++20), раздел 33.5 «Atomic operations library».
  6. Тео Хардер, Андреас Ройтер. «Principles of Transaction-Oriented Database Recovery». — ACM Computing Surveys, Vol. 15, No. 4, 1983.

BFOmetr — база данных и аналитика по компаниям России.

На главную BFOmetr →

Похожие материалы