Мотивация

Заметил недостаток качественных статей по атомикам. Сам когда-то столкнулся с тем, что хотел прочитать статью, где простым и понятным языком рассказывается об этом, но, к сожалению, найти не смог.

Причины существования атомиков

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

Рассмотрим следующий код.
Ссылка на код: https://godbolt.org/z/qWzGreMac.

int a{0};

std::thread t1 {
    [&]() {
        for (size_t i = 0; i < N; i++)
            a++;
    }};


std::thread t2 {
    [&]() {
        for (size_t i = 0; i < N; i++)
            a--;
    }};

t1.join(); // дожидаемся исполнения первого потока
t2.join(); // дожидаемся исполнения второго потока

Какое значение a будет иметь после исполнения этого кода?

Правильный ответ: непредсказуемое (грубо говоря, случайное) значение. Причиной этому является UB (Undefined Behaviour), которое вызвано data race.

Вывод значений, если зациклить нашу программу будет примерно таким:

Скрытый текст

10941 10637 1246 -39806 100000 50751 -32123 -34587 27949

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

Современные процессоры не работают напрямую с оперативной памятью (RAM), а используют кэши для обеспечения быстрого доступа к данным. Кэши процессора быстры, поскольку являются частью процессора и оптимизированы под эту задачу. Можно выделить 3 уровня кэшей:

  • L1 — Небольшой кэш, собственный для каждого ядра, размер 32Kb. Получение данных оттуда может занимать около 5 тактов.

  • L2 — Большой кэш, собственный для каждого ядра, но более медленный чем L1, размер 256Kb. Получение данных будет занимать около 20 тактов.

  • L3 — Кэш общий для всех ядер, размер 2Mb. Получение данных может занимать около 50-100 тактов.

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

Кэш состоит из блоков фиксированной длины, которые называются кэш-линиями. Чаще всего их длина составляет 64-128 байт.

Принцип работы кэшей

Чтобы максимально облегчить понимание этого процесса, опишу так легко, как только могу:

Поток 1: Копирует себе часть общего кэша (a=100)
Поток 2: Копирует себе часть общего кэша (a=100)
Поток 2: Прибавляет переменной a единицу (a=101)
Поток 1: Прибавляет переменной a единицу (a=101)
Поток 1: Сохраняет свой кэш в общий (a=101)
Поток 2: Сохраняет свой кэш в общий (a=101)

Более подробный механизм описан ниже.

Когерентность кэшей

Определение

Поскольку термин не слишком легко понять просто прочитав определение, я дам своё, грубое, но при этом простое определение, чтобы новичок смог разобраться.

Когерентность кэшей — механизм, который помогает синхронизировать копии одних и тех же данных в разных кэшах.

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

Конкретные реализации

Несмотря на существование множества различных протоколов, которые обеспечивают когерентность кэшей, в рамках данной статьи я буду рассматривать MESI.

Однако существуют и другие: AMD использует MOESI, Intel — MESIF.

Суть протокола

В чём же заключается суть этого протокола? У каждой кэш-линии есть одно из четырёх состояний:

  • (M) Modified — данные присутствуют в одном кэше и отличаются от RAM

  • (E) Exclusive — данные присутствуют только в этом кэше и совпадают с RAM

  • (S) Shared — данные присутствуют в нескольких кэшах и совпадают с RAM

  • (I) Invalid — данные в кэш-линии устарели

Ниже продемонстрирован упрощённый механизм работы:

Поток 1: Загружает кэш-линию
a = 100
кэш-линия 1 = E (Значение есть только в этой кэш-линии)

Поток 2: Загружает кэш-линию
a = 100
кэш-линия 1 = S (Значение есть в нескольких кэш-линиях и совпадает)
кэш-линия 2 = S

Поток 2: Атомарно прибавляет переменной a единицу.
a = 101
кэш-линия 1 = I (пред. S) (Состояние в этой кэш-линии устарело прямо в момент записи. Произошёл так называемый Request For Ownership — запрос на владение кэш-линией)
кэш-линия 2 = M (пред. S) (Состояние только в этой кэш-линии)

Поток 1: Видит, что кэш-линия невалидная и идёт загружать актуальную версию.
кэш-линия 1 = S (пред. I) (Значение есть в нескольких кэш-линиях и совпадает)
кэш-линия 2 = S (пред. M) (Значение есть в нескольких кэш-линиях и совпадает)

Поток 1: Прибавляет переменной a единицу
a = 102
кэш-линия 1 = M (пред. S) (Состояние только в этой кэш-линии)
кэш-линия 2 = I (пред. S) (Состояние в этой кэш-линии устарело)

В данном примере показан случай атомарной операции записи, однако если операция записи не будет атомарной, то кэш-линия не будет инвалидирована, что приведёт к data race, а следовательно и неопределённому поведению.

Решение проблемы в C++

Решением этой проблемы в C++ служит класс std::atomic<T>.
Ссылка на код: https://godbolt.org/z/5ccdzMo45.

std::atomic<int> a{0};

std::thread t1 {
    [&]() {
        for (size_t i = 0; i < N; i++)
            a++;
    }};


std::thread t2 {
    [&]() {
        for (size_t i = 0; i < N; i++)
            a--;
    }};

t1.join();
t2.join();

В данном примере все операции будут выполнены атомарно, поэтому a будет всегда принимать нулевое значение после завершения двух тредов.

Как изменился ассемблер

Рассмотрим сгенерированный ассемблер для архитектуры AMD64. Во втором случае запись результата происходит непосредственно по адресу [rdx], в отличие от первого.

add         edx, 1          ; до атомика
lock add    DWORD PTR [rdx], 1 ; после атомика

В ассемблере конструкция [rdx] означает операцию разыменования непосредственно по адресу, лежащему в rdx, а в первом же случае значение загружается в отдельный регистр, изменяется, а потом выгружается обратно в необходимую область памяти.

Префикс lock для ассемблерной инструкции означает, что инструкция выполнится с блокировкой кэш-линии. В момент вызова lock происходит смена состояния кэш-линии на (E), а после на (M).

Атомики

Атомарность

Атомарная операция — операция, которая выполняется неделимо. Это означает, что мы не можем в момент этой операции прерваться и пойти делать что-то другое. Рассмотрим наглядные примеры.

Неатомарный инкремент:

; чтение из памяти
mov eax, DWORD PTR [ebx]
; здесь наш поток может переключиться
add eax, 1
; здесь наш поток тоже может переключиться
; запись обратно в память
mov DWORD PTR [ebx], eax

Атомарный инкремент:

lock add DWORD PTR [ebx], 1

Таким образом, атомарность гарантирует выполнение операции целостно.

Доступные операции

В C++ класс std::atomic<T> имеет следующие методы:

  • Store — Атомарно записать значение в переменную

  • Load — Атомарно прочитать значение из переменной

  • Exchange — Записать новое значение и получить старое

  • CAS(compare and swap) — Сравнивает текущее значение с ожидаемым и, если они равны, то записывает желаемое значение, а если не равны, то записывает старое в желаемое, а после возвращает равны они или нет. Это может быть очень трудно понять, но с примером будет легче.

  • fail spuriously — это ситуация, когда операция оказывается неудачной, без видимой на то причины. То есть, даже если значения равны, в случае с CAS, то мы можем увидеть false.

Казалось бы всё очевидно, но compare_exchange выглядит пугающе. При этом в C++ их целых два: std::atomic<T>::compare_exchange_weak, std::atomic<T>::compare_exchange_strong. Грубо говоря, функция strong возвращает false только если гарантированно значения различны, а weak может вернуть false для одинаковых значений. Называется это fail spuriously (неожиданно провалиться).

Я бы рекомендовал использовать weak для спинлоков (CAS в цикле) и strong в остальных случаях, но, строго говоря, никто не мешает вам делать иначе.

  • Спинлок — это выполнение атомарной операции в цикле, пока она не будет выполнена успешно.

Рассмотрим на примере, как именно работает CAS (За форматирование не бейте, я старался делать строки более короткими):
Ссылка на код: https://godbolt.org/z/1q3479Eos.

std::atomic<int> a = 14;

int x = 14, y = 42;
auto result1 = a.compare_exchange_strong(x, y);

std::cout
    << "expected = " << x
    << "; desired = " << y
    << "; result = " << result1
    << "; atomic = " << a.load()
    << std::endl;

int z = 10, w = 32;

auto result2 = a.compare_exchange_strong(z, w);

std::cout
    << "expected = " << z
    << "; desired = " << w
    << "; result = " << result2
    << "; atomic = " << a.load()
    << std::endl;

При запуске кода мы увидим следующий вывод:

expected = 14; desired = 42; result = 1; atomic = 42
expected = 42; desired = 32; result = 0; atomic = 42

Что он означает? Прочитаем первую строку: изначально результат удался и в expected нам записали старое значение атомика равное 14. Вторая строчка же говорит о том, что CAS не удалось выполнить. Это случилось из-за того, что expected == 10 не было равно 42. Поэтому в expected записали актуальное значение атомика и вернули false, так-как операция не удалась.

Если до сих пор не стало понятно, то рекомендую залезть и поиграться с этим. Но, вероятно, у вас возникает вопрос: а зачем это нужно? Давайте разберём более интересный пример!

Пример

Я написал небольшой lock-free стек. Данный код никоим образом не является production-ready решением и даже близко не стоит с ним, а просто демонстрирует необходимость CAS операций.

Пример с небольшими тестами можно посмотреть здесь: https://godbolt.org/z/E973r6Md3.

class ts_stack {
private:
    struct Node {
        Node* prev;
        int value;
    };
    std::atomic<Node*> m_tail;

public:
    ts_stack() : m_tail(nullptr) {}

    bool try_add(int val) {
        // Сохраняем значение указателя на конец
        Node* old = m_tail.load();

        // Создаём новую ноду с указателем на конец
        auto node = new Node{old, val};

        // Проверяем не поменялось ли старое значение ноды
        // Если поменялось, то значит операция не удалась
        // и тогда мы удаляем нашу ноду и выходим из функции
        // мол неудачно
        auto res = m_tail.compare_exchange_strong(old, node);

        if (!res)
            delete node;

        return res;
    }

    bool try_pop(int& val) {
        // Загружаем старое значение
        auto old = m_tail.load();
        // Если оно nullptr, то мы возвращаем false
        if (old == nullptr)
            return false;
        // Теперь пытаемся заменить хвост на предпоследний элемент
        // Если он успел поменяться, то мы просто выходим из функции
        // и возвращаем при этом false, мол не смогли поменять
        auto res = m_tail.compare_exchange_strong(old, old->prev);
        if (!res)
            return false;
        // Однако, если нам удалось поменять всё таки значение,
        // то мы теперь должны его записать куда-то
        // можно было бы и возвращать, но вообще куда
        // проще передавать ссылку на значение
        val = old->value;

        // по хорошему надо бы ещё и удалять Node*,
        // потому что мы достаточно много памяти расходуется зряв
        // но об этом чуть позже
        return true;
    }
};

Я постарался написать достаточно комментариев, чтобы разъяснить все нюансы. Конечно, по хорошему стоило бы начать с рассмотрения якобы правильных стеков и понять, почему именно не стоит делать так, как делают там, но поскольку статья обзорная, то я оставлю это на какие-нибудь профильные книги.

Хочу обратить ваше внимание на момент, почему я не стал в try_pop делать delete old.

Давайте разбираться!

Поток 1:
    try_pop:
        Node* old = m_tail.load();
        Потом вернёмся сюда
Поток 2:
    try_pop:
        val = old->value;
        delete old; // представим, что я добавил эту строчку
Поток 1:
    try_pop:
        возвращаемся к тому, где были
        if (old == nullptr)
            return false;
        auto res = m_tail.compare_exchange_strong(old, old->prev);

Что же тут случилось? После вызова delete для old мы обращаемся old->prev.

Иными словами мы в двух потоках захватили один и тот же адрес хвоста, а потом в одном удалили быстрее, чем в другом закончили работу с ним. Чтобы не усложнять, я решил не решать эту проблему, но если вкратце она именуется Retention Policy и у неё есть несколько способов решения. Например, через shared_ptr или кастомный аллокатор.

Также часто встречается ABA problem, о которой я намеренно умолчу, поскольку это выходит за рамки статьи.

Модель памяти

Отношение happens-before

В повседневной жизни действия имеют определённый порядок выполнения. Например, мы сначала одеваемся, затем выходим на улицу. Так мы можем задать чёткий порядок того, какое действие случится раньше.

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

Пример

Если вы поняли всё то, что было описано выше, предлагаю перейти к рассмотрению более сложного примера.

Ко всем атомарным операциям добавлю ещё один параметр std::memory_order::relaxed. Постарайтесь понять, что именно делает код, приведённый ниже.
Ссылка на код: https://godbolt.org/z/KG7reKfeG.

std::atomic<int> x{0}, y{0};
std::atomic<bool> finish = false;

void thread1() {
    while (!finish.load(std::memory_order::relaxed)) {
        x.fetch_add(1, std::memory_order::relaxed);
        y.fetch_add(1, std::memory_order::relaxed);
    }
}

void thread2() {
    while (!finish.load(std::memory_order::relaxed)) {
        auto a = x.load(std::memory_order::relaxed);
        auto b = y.load(std::memory_order::relaxed);
        if (b > a) {
            std::cout << "x != y, " << a << " != " << b << std::endl;
            finish.store(true, std::memory_order::relaxed);
        }
    }
}

int main() {
    std::thread t1{thread1};
    std::thread t2{thread2};
    t1.join();
    t2.join();
    return 0;
}

По существу эта программа атомарно увеличивает два счётчика на единицу, сначала x, а потом y. Второй поток проверяет, всегда ли мы загрузим x больший, чем y. Если нет, то мы завершим исполнение и напечатаем на экран когда мы завершили исполнение.

Рассмотрим три возможных вариан��а поведения программы:

  1. Ошибка компиляции

  2. Программа будет жить вечно, ведь если операции атомарны, то как может быть y>x или b>a

  3. Программа рано или поздно завершится из-за того, что произойдёт переупорядочивание операций

Как можно догадаться, правильный ответ — вариант №3. На практике такое поведение наиболее вероятно, но не гарантировано стандартом.

Что происходит? Происходит переупорядочивание операций.

  • race-condition — состояние системы, при котором поведение зависит от последовательности неконтролируемых событий (в данном случае мы не можем контролировать, какой fetch_add случится раньше), что приводит к несогласованным результатам.

MemoryOrder

Процессор может переупорядочивать независимые операции друг с другом, чтобы оптимизировать исполнение программ.

memory_order_consume обойду стороной, поскольку крайне редко встречается, а также помечен как deprecated (устаревший).

Рассмотрим определения memory order:

  • memory_order_relaxed — атомарная операция без барьеров. То есть, операции могут быть переставлены как ДО, так и ПОСЛЕ

  • memory_order_acquire — это барьер на операции ПОСЛЕ. Никакая операция чтения/записи не может быть переупорядочена с данной, если она идёт ПОСЛЕ неё. Однако если она идёт перед, то может (используется для load)

  • memory_order_release — это барьер на операции ДО. Никакая операция чтения/записи не может быть переупорядочена с данной, если она идёт перед ней. Однако если она идёт ПОСЛЕ, то может (используется для store)

  • memory_order_acq_rel — это барьер на операции ПОСЛЕ и ДО. Никакая операция чтения/записи не может быть переупорядочена с данной (используется для операций, в которых есть одновременно и load, и store)

  • memory_order_seq_cst — самая строгая гарантия. Она позволяет сохранять порядок абсолютно для всех потоков. Но чем же она отличается от memory_order_acq_rel — вопрос хороший

Как это выглядит в коде

Рассмотрим несколько примеров.

Эти примеры демонстрируют разницу между различными memory order. Следует отметить, что приведённый код содержит UB, поэтому я бы сказал, что это лишь иллюстрация, для наглядной демонстрации memory order. При этом UB можно избежать, если x был бы атомиком. При этом, для воспроизведения, необходимо каждую операцию на x производить с memory_order_relaxed.

int x = 0;
std::atomic<bool> flag{false};


void thread_1() {
    x = 14;
    flag.store(true, std::memory_order_relaxed);
}

void thread_2() {
    
    while (true) {
        if (flag.load(std::memory_order_relaxed)) {
            auto res = x == 14;
            // res может быть равен false
            // потому что x == 0,
            // поскольку первый поток ещё не успел загрузить значение
        }
    }
}
void thread_1() {
    x = 14;
    flag.store(true, std::memory_order_release);
}

void thread_2() {
    
    while (true) {
        if (flag.load(std::memory_order_relaxed)) {
            auto res = x == 14;
            // res может быть равен false
            // потому что x == 0,
            // поскольку этот поток загрузил значение
            // ещё до операции flag.load
        }
    }
}
void thread_1() {
    x = 14;
    flag.store(true, std::memory_order_release);
}

void thread_2() {
    
    while (true) {
        if (flag.load(std::memory_order_acquire)) {
            auto res = x == 14;
            // res не может быть равен false
        }
    }
}

Порядок Sequentially-consistent

Классический пример для демонстрации отличия с acquire-release можно найти на cppreference.

#include <atomic>
#include <cassert>
#include <thread>
 
std::atomic<bool> x = {false};
std::atomic<bool> y = {false};
std::atomic<int> z = {0};
 
void write_x()
{
    x.store(true, std::memory_order_seq_cst);
}
 
void write_y()
{
    y.store(true, std::memory_order_seq_cst);
}
 
void read_x_then_y()
{
    while (!x.load(std::memory_order_seq_cst))
        ;
    if (y.load(std::memory_order_seq_cst))
        ++z;
}
 
void read_y_then_x()
{
    while (!y.load(std::memory_order_seq_cst))
        ;
    if (x.load(std::memory_order_seq_cst))
        ++z;
}
 
int main()
{
    std::thread a(write_x);
    std::thread b(write_y);
    std::thread c(read_x_then_y);
    std::thread d(read_y_then_x);
    a.join(); b.join(); c.join(); d.join();
    assert(z.load() != 0); // will never happen
}

Рассмотрим логику программы.

Запускается 4 потока:

  • Поток 1: пишет в переменную x значение true

  • Поток 2: пишет в переменную y значение true

  • Поток 3: ждёт пока переменная x будет true пишет в переменную z значение на единицу больше, если y уже записан

  • Поток 4: ждёт пока переменная y будет true пишет в переменную z значение на единицу больше, если x уже записан

Выше написан код с seq_cst memory order, что позволяет синхронизировать значения x и y между собой. Однако перепишем код на acquire/release memory order и проанализируем возможные переупорядочивания операций.

void write_x()
{
    // переупорядочивание не влияет на результат, так как нет других операций
    x.store(true, std::memory_order_release);
}
 
void write_y()
{
    // переупорядочивание не влияет на результат, так как нет других операций
    y.store(true, std::memory_order_release);
}
 
void read_x_then_y()
{   
    // все чтения не могут быть вынесены вверх
    while (!x.load(std::memory_order_acquire))
        ;
    // однако к этому моменту y может всё ещё иметь значение false, если второй поток не выполнил запись
    if (y.load(std::memory_order_acquire))
        ++z;
}
 
void read_y_then_x()
{
    // все чтения не могут быть вынесены вверх
    while (!y.load(std::memory_order_acquire))
        ;
    // можно было бы ожидать, что x уже установлен в true, однако без seq_cst это не гарантируется
    if (x.load(std::memory_order_acquire))
        ++z;
}

seq_cst гарантирует единый глобальный порядок всех операций для всех потоков, в то время как acquire/release не создаёт общего порядка между независимыми парами.

Свои атомарные типы данных

Что если мы хотим делать не только атомарные указатели, числа, но и атомарные структуры. Например, такую:

struct A { 
    float a;
    double b;
    int c;
};

Атомарные структуры могут иметь ограничения при большом размере структуры. Поскольку std::atomic<T> может быть реализован через std::mutex, такие атомики будут использовать блокировки и они не будут являться lock-free.

Чтобы узнать, является ли атомик lock-free, можно использовать метод is_lock_free.

Рассмотрим пример.
Ссылка на код: https://godbolt.org/z/sdEj9585f.

std::cout << "std::atomic<bool>::is_lock_free() == " << std::atomic<bool>{}.is_lock_free() << std::endl;
std::cout << "std::atomic<int>::is_lock_free() == " << std::atomic<int>{}.is_lock_free() << std::endl;
std::cout << "std::atomic<size_t>::is_lock_free() == " << std::atomic<size_t>{}.is_lock_free() << std::endl;
std::cout << "std::atomic<void*>::is_lock_free() == " << std::atomic<void*>{}.is_lock_free() << std::endl;
std::cout << "std::atomic<A>::is_lock_free() == " << std::atomic<A>{}.is_lock_free() << std::endl;

А вывод для x86-64 gcc 15.2 будет следующий 

std::atomic<bool>::is_lock_free() == 1
std::atomic<int>::is_lock_free() == 1
std::atomic<size_t>::is_lock_free() == 1
std::atomic<void*>::is_lock_free() == 1
std::atomic<A>::is_lock_free() == 0

А как же тогда будет работать наш атомик, если он не lock-free? Поведение зависит от конкретной реализации.

Заключение

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