ph_piter 9 июн 2022 в 10:00

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

9 мин

16K

Блог компании Издательский дом «Питер»Программирование*C++*Assembler*Параллельное программирование*

Перевод

Часто возникает путаница с тем, что же понимается в компьютерных науках под «атомарностью». Как правило, атомарность – это свойство процесса, означающее, что он совершается за один шаг или операцию. Но в языке 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;
}

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

Причина, по которой 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 успешно пройдет в последнем известном верхнем узле стека. То же касается и операции выталкивания из стека.

Теги:

Хабы: