Простое руководство по атомарности в C++

Часто возникает путаница с тем, что же понимается в компьютерных науках под «атомарностью». Как правило, атомарность – это свойство процесса, означающее, что он совершается за один шаг или операцию. Но в языке C++  атомарность определяется гораздо более специфичным образом. На самом деле, при использовании std::atomic  с классами и типами еще не гарантируется, что весь код будет подлинно атомарным. Хотя, атомарные типы и входят в состав языка C++, сами атомарные операции должны поддерживаться на уровне того аппаратного обеспечения, на котором работает программа. Эта статья – простое руководство, помогающее понять, что же представляет собой атомарность в C++.

Типы

В C++ в шаблонный класс std::atomic<> можно обертывать и многие другие типы, что способствует атомарным операциям над соответствующим типом. Этот шаблон ни в коем случае не гарантирует, что все операции на самом деле получатся атомарными. Если какие-либо атомарные операции не поддерживаются задействованным CPU, то компилятор прибегнет к резервным вариантам на основе мьютексов. Хорошо, что есть полезная функция и гарантированный булев член атомарных типов – при помощи этих вещей можно проверить, CPU атомарные операции над типами или нет.

#include <atomic> #include <cstdio>  int main() {     printf("is lock free? %s\n", std::atomic<int>::is_always_lock_free ? "true" : "false");     std::atomic<int> a(3);     printf("is this lock free? %s\n", a.is_lock_free() ? "true" : "false");     return 0; }

В вышеприведенном коде также подчеркивается еще один важный факт об атомарности: атомарны только операции, но не типы и не данные. Число int ничем не отличается от std::atomic<int> в том смысле, какие данные оно представляет. Кроме того, типы std::atomic<> устроены так, что только атомарные операции предназначены для работы с теми данными, что представлены этим типом. Таким образом, атомарные и неатомарные операции никогда не перемешиваются.

Загрузка и сохранение

Простейшими атомарными операциями являются загрузка и сохранение. Хотя, вы можете буквально представлять операцию «хранение значения в переменной», на самом деле, в атомарном хранилище данных происходит нечто иное. Во-первых, не забывайте, что цель атомарности – обеспечить возможность, чтобы много потоков могли изменять одни и те же данные, и это было потокобезопасно. Чтобы такое было возможно, эти данные должны существовать в разделяемой памяти или в кэше. Следовательно, при атомарной загрузке данные переносятся из разделяемой памяти либо в регистр, либо в участок памяти, специфичный для конкретного потока – в зависимости от архитектуры процессора. При атомарном сохранении данные атомарно записываются в разделяемую память.

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

Атомарность как момент времени

Возьмем переменную a, имеющую значение 3 в момент t1. Если атомарная загрузка применена в момент t1, то в результате этой операции загрузки будет получено значение 3. Однако, если загрузка произойдет на миг позже, в момент t2, то в результате может быть получено не 3, а другое значение, просто потому, что в момент t1 могла произойти другая операция.

Допустим, переменная a инициализируется в значении 1, так, что представление a до того, как над ней совершены какие-либо операции, должно быть равно 1. Если к переменной a применяется операция сохранения, а затем операция загрузки, то нет никакой гарантии, что по результатам второй операции будет извлечено именно то значение, которое было сохранено в переменной в результате первой операции. Дело в том, что сохранение и загрузка происходят в два разных момента времени. А эмпирически из опыта работы с атомарными операциями известно, что между двумя моментами времени может быть осуществлено практически бесконечное количество операций.

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

#include <atomic> #include <cstdio> #include <thread>  static std::atomic<int> foobar(8); static std::atomic<bool> start(false);  int main() {     std::thread t1 = std::thread([]{         int records[10];         while (!start.load());         for (size_t i = 0; i < 10; ++i) {             foobar.store(3);             records[i] = foobar.load();         }         for (size_t j = 0; j < 10; ++j) {             printf("t1 %zu - %d\n", j, records[j]);         }     });      std::thread t2 = std::thread([]{         int records[10];         while (!start.load());         for (size_t i = 0; i < 10; ++i) {             foobar.store(6);             records[i] = foobar.load();         }         for (size_t j = 0; j < 10; ++j) {             printf("t2 %zu - %d\n", j, records[j]);         }     });     start.store(true);      t1.join();     t2.join();     return 0;

Если вы скомпилируете и выполните эту программу, то можете получить примерно следующий результат:

t1 0 - 3 t1 1 - 3 t1 2 - 3 t1 3 - 3 t1 4 - 3 t1 5 - 3 t1 6 - 3 t1 7 - 3 t1 8 - 3 t1 9 - 3 t2 0 - 6 t2 1 - 6 t2 2 - 6 t2 3 - 6 t2 4 - 6 t2 5 - 6 t2 6 - 6 t2 7 - 6 t2 8 - 6 t2 9 - 6

Он может показаться странным – ведь, судя по выводу, каждый из потоков был в состоянии загрузить именно то значение, которое сохранил. Возможно, операции в этой программе совершались в таком порядке: поток t1 загружал начальную переменную, затем завершал все свои операции загрузки и сохранения, а потом поток t2 загружал начальную переменную и завершал все свои операции сохранения и загрузки. В результате потоку приходилось выполнять дополнительную работу, происходящую вне разделяемой памяти, например, for (int k = 0; k < 1000; ++k); . Если сделать так и запустить программу, то начнет проявляться разбежка между значениями, которые загружал каждый из потоков.

Операции обмена

Обмен (exchange), также называемый перестановкой (swap) – это операция, при которой в атомарной переменной заменяется некоторое значение и возвращается значение, которое было в ней ранее. Операции обмена – это и сохранение, и загрузка за один атомарный ход. Однако, до этой операции значение атомарной переменной не проверяется. Следовательно, обмен также может считаться безусловным. При обмене не предоставляется атомарного решения для загрузки с последующим сохранением.

Операцию обмена также иногда называют «системой с когерентным доступом к кэшу». Это значит, что, вслед за обменом, любая последующая операция отражает то значение, которое при обмене записывается в переменную. В качестве иллюстрации продемонстрирую, как в данном случае может использоваться единственный рабочий поток.

#include <atomic> #include <cstdio> #include <thread>  static std::atomic<int> foobar(8);  int main() {     std::thread t1 = std::thread([]{         int value = 4;         for (int i = 0; i < 100000; ++i)         {             value = foobar.exchange(value);         }     });     printf("%d\n", foobar.load());     foobar.exchange(14);     printf("%d\n", foobar.load());     printf("%d\n", foobar.load());     printf("%d\n", foobar.load());     printf("%d\n", foobar.load());     t1.join();     return 0; }

В вышеприведенном примере рабочий поток получает большую задачу: поменять значение 100 000 раз. В течение этого времени главная функция меняет значение, сохраненное в foobar, на 14 . Каждый последующий вызов вслед за обменом в главной функции теперь будет возвращать 14 .

Операции выборки данных 

Операции выборки данных (fetch), например, «выбрать и сложить» или «выбрать и вычесть» применяют к атомарной переменной некоторую операцию и выбирают то значение, которое находилось в переменной до совершения операции. Операции выборки работают примерно так же, как операции обмена, в том смысле, что атомарный обмен заключается лишь в записи значения и «выборке» предыдущего значения. Есть несколько типов операций выборки, и в C++ поддерживаются следующие из них:

• fetch_add

• fetch_sub

• fetch_and

• fetch_or

• fetch_xor

Одно ограничение атомарных операций выборки данных заключается в том, что они обеспечивают лишь эквивалент постфиксной операции, например, x++; . Операции выборки данных возвращают значение до операции и никогда после. Возвращение значения после операции потребовало бы дополнительной атомарной загрузки, из-за чего две операции стали бы неатомарными относительно значения переменной. В примере ниже реализован счетчик на основе операций fetch_add и fetch_sub .

#include <atomic> #include <cstdio>  struct Counter {      Counter(): count(0) {}      std::atomic<unsigned> count;      unsigned operator++(int) {         return count.fetch_add(1);     }      unsigned operator--(int) {         return count.fetch_sub(1);     } };   int main() {     Counter a;     printf("%u\n", a++);     printf("%u\n", a++);     printf("%u\n", a--);     printf("%u\n", a--);     return 0; }

Если этот код скомпилировать и выполнить, он выведет на экран

0 1 2 1

Причина, по которой fetch_sub сначала возвращает 2, заключается в том, что fetch_add возвращает значение до того, как прирастить его. Следующий вызов fetch_sub возвращает 1, указывая, что предыдущий вызов вычел 1 после того, как было выбрано предыдущее значение.

Возможно, вы уже заметили, что у типичных арифметических операций, например, у умножения и деления, нет эквивалентов из рода fetch. Эта ситуация восходит к фундаментальной идее, лежащей в основе атомарных операций – всем им нужна аппаратная поддержка. Нет такого железа, которое поддерживало бы атомарное умножение или деление. В самом деле, существуют подходы с негарантированным результатом, реализующие такие операции программно. Например, можно поступить так: атомарно загрузить целое число, умножить его, а затем атомарно сохранить результат, чтобы получилось:

std::atomic<int> a(3); int b = a.load() * 3; a.store(b);

Но при таком подходе возникает проблема. Возможно, что между второй и третьей строкой из предыдущего примера другой поток изменит значение a, поэтому цель «умножить на 3» не будет достигнута, ведь b – это произведение предыдущего значения a и 3. Если просто сохранить b в a, это может привести к несогласованности данных. В таком сценарии нет ничего опасного, отсутствует вероятность утечки в памяти или ошибки сегментации. Да, в многопоточной программе у всех потоков должно быть общее согласованное представление о данных с атомарными составляющими, чтобы задачи успешно решались. Поэтому в атомарной операции нужно предусмотреть концепцию «отказа».

Сравнение с обменом

Сравнение с обменом, также именуемое сравнением с перестановкой (CAS) – это самая мощная операция, доступная в C++. В большинстве случаев так обеспечивается атомарное сравнение актуального значения атомарной переменной и другого значения. Если результат сравнения будет true, то программа попытается сохранить желаемое значение. Несмотря на то, что сравнение с обменом является атомарной операцией, эта операция, конечно же, может закончиться неудачно – если в работу вмешается другой поток и изменит значение переменной между актом ее считывания и актом ее записи. Операция сравнения с обменом иначе называется «чтение-изменение-запись» (RMW).

Процессоры по-разному реализуют сравнение с обменом. В некоторых процессорах со строгим порядком операций, например, из семейства x86, сравнение с обменом выполняется в рамках единственной ассемблерной инструкции. Поэтому сравнение с обменом не удастся лишь в том случае, если другой поток действительно изменит значение атомарной переменной до того, как состоится операция сравнения с обменом. В процессорах с нестрогим порядком операций сравнение с обменом реализуется в двух ассемблерных инструкциях, как правило, по принципу LLCS (блокируемая загрузка и условное сохранение). LLCS может время от времени отказывать в силу использования двух инструкций – например, если у потока переключится контекст.

В C++ есть две функции, выполняющие сравнение с обменом, compare_exchange_weak и compare_exchange_strong. Слабая версия больше подходит для ситуаций, в которых операции вызываются циклически. Циклический вызов сравнения с обменом – распространенная ситуация, когда требуется реализовать неблокирующие структуры данных. Например, рассмотрим простейшую неблокирующую структуру данных такого рода – стек.

#include <iostream> #include <atomic>  template<class T> class LFS { public: struct node {     T data;     node<T>* next;     node(const T& data) : data(data), next(nullptr) {} }; void push(const T& val) { node<T>* new_node = new node<T>(val); new_node->next = _head.load(); while(!_head.compare_exchange_weak(new_node->next, new_node)); }  bool pop() { node<T>* got = _head.load(); node<T>* nextn = nullptr; do { if(got == nullptr) { return false; } nextn = got->next; } while(!_head.compare_exchange_weak(got, nextn)); delete got; return true; } private: std::atomic<node<T>*> _head; };

У вышеприведенного стека два метода — push и pop. Каждый из них удовлетворяет главному критерию неблокируемости: один поток постоянно прогрессирует и завершает свою задачу выталкивания из стека или записи в стек. Если будет много потоков вызовут compare_exchange_weak, то только у одного из них эта попытка будет успешной. Все остальные потоки потерпят с compare_exchange_weak неудачу – то есть, загрузят то значение, которое прямо сейчас сохранено в переменной. Такой цикл, фактически, обеспечивает, чтобы операция сравнения с обменом «повторялась с последним известным значением» атомарной переменной.

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