std::atomic. Модель памяти C++ в примерах

в 4:31, , рубрики: c++, атомики, многопоточность, Программирование

Для написания эффективных и корректных многопоточных приложений очень важно знать какие существуют механизмы синхронизации памяти между потоками исполнения, какие гарантии предоставляют элементы многопоточного программирования, такие как мьютекс, join потока и другие. Особенно это касается модели памяти C++, которая была создана сложной таковой, чтобы обеспечивать оптимальный многопоточный код под множество архитектур процессоров. Кстати, язык программирования Rust, будучи построенным на LLVM, использует модель памяти такую же, как в C++. Поэтому материал в этой статье будет полезен программистам на обоих языках. Но все примеры будут на языке C++. Я буду рассказывать про std::atomic, std::memory_order и на каких трех слонах стоят атомики.


В стандарте C++11 появилась возможность писать многопоточные программы на C++, используя только стандартные средства языка. В то время многоядерные процессоры уже завоевали рынок. Особенность выполнения программы на многоядерном процессоре в том, что инструкции программы из разных потоков физически могут исполняться одновременно. Ранее многопоточность на одном ядре эмулировалась частым переключением контекста исполнения с одного потока на последующие. Для оптимизации работы с памятью у каждого ядра имеется его личный кэш памяти, над ним стоит общий кэш памяти процессора, далее оперативная память. Задача синхронизации памяти между ядрами - поддержка консистентного представления данных на каждом ядре (читай в каждом потоке). Очевидно, что если применить строгую упорядоченность изменений памяти, то операции на разных ядрах уже не будут выполнятся параллельно: остальные ядра будут ожидать, когда одно ядро выполнит инструкции изменения данных. Поэтому процессоры поддерживают работу с памятью с менее строгими гарантиями консистентности памяти. Более того, разработчику программы предоставляется выбор, какие гарантии по доступу к памяти из разных потоков требуются для достижения максимальной корректности и производительности многопоточной программы. Задача предоставить разные гарантии по памяти решалась по-разному для разных архитектур процессоров. Наиболее популярные архитектуры x86-64 и ARM имеют разные представления о том, как синхронизировать память.

Язык C++ компилируется под множество архитектур, поэтому в вопросе синхронизации данных между потоками в С++11 была добавлена модель памяти, которая обобщает механизмы синхронизации различных архитектур, позволяя генерировать для каждого процессора оптимальных код с необходимой степенью синхронизации.

Отсюда следует несколько важных выводов: модель синхронизации памяти C++ — это "искусственные" правила, которые учитывают особенности различных архитектур процессоров. В модели C++ некоторые конструкции, описанные стандартом как undefined behavior (UB), могут корректно работать на одной архитектуре, но приводить к ошибкам работы с памятью на других архитектурах.

Наша задача, как разработчиков на языке C++, состоит в том, чтобы писать корректный с точки зрения стандарта языка код. В этом случае мы можем быть уверены, что для каждой платформы будет сгенерирован корректный машинный код.

Код каждого потока компилируется и выполняется так, как будто он один в программе. Вся синхронизация данных между потоками возложена на плечи атомиков (std::atomic), т.к. именно они предоставляют возможность форсировать "передачу" изменений данных в другой поток. Далее я покажу, что мьютексы (std::mutex) и другие многопоточные примитивы либо реализованы на атомиках, либо предоставляют гарантии, семантически похожие на атомарные операции.  Поэтому ключом к написанию корректных многопоточных программ является понимание того, как конкретно работают атомики.

Три слона

На мой взгляд, основная проблема с атомиками в C++ состоит в том, что они несут сразу три функции. Так на каких же трех слонах держатся атомики?

  1. Атомики позволяют реализовать… атомарные операции.

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

  3. Синхронизируют память в двух и более потоках выполнения.

Атомарная операция — это операция, которую невозможно наблюдать в промежуточном состоянии, она либо выполнена либо нет. Атомарные операции могут состоять из нескольких операций. Если говорить про тип std::atomic, то он предоставляет ряд примитивных операций: load, store, fetch_add, compare_exchange_* и другие. Последние две операции — это read-modify-write операции, атомарность которых обеспечивается специальными инструкциями процессора.

Рассмотрим простой пример read-modify-write операции, а именно прибавление к числу единицы. Пример 0, link:

static int v1 = 0;
static std::atomic<int> v2{ 0 };

void add_v1() {
	v1++;
 
  /* Generated asm for x86-64:

  mov eax, DWORD PTR v1[rip]
  add eax, 1
  mov DWORD PTR v1[rip], eax
  */
}
 
void add_v2() {
	v2.fetch_add(1);
 
  /* Generated asm for x86-64 (simplified):

  mov edx, OFFSET FLAT:_ZL2v2
  lock xadd DWORD PTR [rdx], 1
  */
}

В случае с обычной переменной  v1 типа int имеем три отдельных операций: read-modify-write. Нет гарантий, что другое ядро процессора не выполняет другой операции над v1. Операция над v2 в машинных кодах представлена как одна операция с lock сигналом на уровне процессора, гарантирующим, что к кэш линии, в которой лежит v2, эксклюзивно имеет доступ только ядро, выполняющее эту инструкцию.

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

Про синхронизацию данных между потоками. Если мы хотим изменить данные в одном потоке и сделать так, чтобы эти изменения были видны в другом потоке, то нам необходимы примитивы многопоточного программирования. Фундаментальным таким примитивом являются атомики, остальные, например мьютексы, либо реализованы на основе атомиков, либо повторяют семантику атомиков. Все остальные попытки записывать и читать одни и те же данные из разных потоков могут приводить к UB.

Случаи, когда синхронизация памяти не требуется:

  1. Если все потоки, работающие с одним участком памяти, используют ее только на чтение

  2. Если разные потоки используют эксклюзивно разные участки памяти

Далее будет рассмотрены более сложные случаи, когда требуется чтение и запись одного участка памяти из разных потоков. Язык C++ предоставляет три способа синхронизации памяти. По мере возрастания строгости: relaxed, release/acquire и sequential consistency. Рассмотрим их.

Неделимый, но расслабленный

Самый простой для понимания флаг синхронизации памяти — relaxed. Он гарантирует только свойство атомарности операций, при этом не может участвовать в процессе синхронизации данных между потоками. Свойства:

  • модификация переменной "появится" в другом потоке не сразу

  • поток thread2 "увидит" значения одной и той же переменной в том же порядке, в котором происходили её  модификации в потоке thread1

  • порядок модификаций разных переменных в потоке thread1 не сохранится в потоке thread2

Можно использовать relaxed модификатор в качестве счетчика. Пример 1, link:

std::atomic<size_t> counter{ 0 };
 
// process can be called from different threads
void process(Request req) {
	counter.fetch_add(1, std::memory_order_relaxed);
	// ...
}

void print_metrics() {
	std::cout << "Number of requests = " << counter.load() << "n";
	// ...
}

Использование в качестве флага остановки. Пример 2, link:

std::atomic<bool> stopped{ false };
 
void thread1() {
	while (!stopped.load(std::memory_order_relaxed)) {
		// ...
	}
}
 
void stop_thread1() {
	stopped.store(true, std::memory_order_relaxed);
}

В данном примере не важен порядок в котором thread1 увидит изменения из потока, вызывающего stop_thread1. Также не важно то, чтобы thread1 мгновенно (синхронно) увидел выставление флага stopped в true.

Пример неверного использования relaxed в качестве флага готовности данных. Пример 3, link:

std::string data;
std::atomic<bool> ready{ false };
 
void thread1() {
	data = "very important bytes";
	ready.store(true, std::memory_order_relaxed);
}
 
void thread2() {
	while (!ready.load(std::memory_order_relaxed));
	std::cout << "data is ready: " << data << "n"; // potentially memory corruption is here
}

Тут нет гарантий, что поток thread2 увидит изменения data ранее, чем изменение флага ready, т.к. синхронизацию памяти флаг relaxed не обеспечивает.

Полный порядок

Флаг синхронизации памяти "единая последовательность" (sequential consistency, seq_cst) самый строгий и понятный. Его свойства:

  • порядок модификаций разных атомарных переменных в потоке thread1 сохранится в потоке thread2

  • все потоки будут видеть один и тот же порядок модификации всех атомарных переменных. Сами модификации могут происходить в разных потоках

  • все модификации памяти (не только модификации над атомиками) в потоке thread1, выполняющей store на атомарной переменной, будут видны после выполнения load этой же переменной в потоке thread2

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

Этот флаг синхронизации памяти в C++ используется по-умолчанию, т.к. с ним меньше всего проблем с точки зрения корректности выполнения программы. Но seq_cst является дорогой операцией для процессоров, в которых вычислительные ядра слабо связаны между собой в плане механизмов обеспечения консистентности памяти. Например, для x86-64 seq_cst дешевле, чем для ARM архитектур.

Продемонстрируем второе свойство. Пример 4, из книги [1], link:

std::atomic<bool> x, y;
std::atomic<int> z;
 
void thread_write_x() {
	x.store(true, std::memory_order_seq_cst);
}
 
void thread_write_y() {
	y.store(true, std::memory_order_seq_cst);
}
 
void thread_read_x_then_y() {
	while (!x.load(std::memory_order_seq_cst));
	if (y.load(std::memory_order_seq_cst)) {
		++z;
	}
}
 
 
void thread_read_y_then_x() {
	while (!y.load(std::memory_order_seq_cst));
	if (x.load(std::memory_order_seq_cst)) {
		++z;
	}
}

После того, как все четыре потока отработают, значение переменной z будет равно 1 или 2, потому что потоки thread_read_x_then_y и thread_read_y_then_x "увидят" изменения x и y в одном и том же порядке. От запуска к запуску это могут быть: сначала x = true, потом y = true, или сначала y = true, потом x = true.

Модификатор seq_cst всегда может быть использован вместо relaxed и acquire/release, еще и поэтому он является модификатором по-умолчанию. Удобно использовать seq_cst для отладки проблем, связанных с гонкой данных в многопоточной программе: добиваемся корректной работы программы и далее заменяем seq_cst на менее строгие флаги синхронизации памяти. Примеры 1 и 2 также будут корректно работать, если заменить relaxed на seq_cst, а пример 3 начнет работать корректно после такой замены.

Синхронизация пары. Acquire/Release

Флаг синхронизации памяти acquire/release является более тонким способом синхронизировать данные между парой потоков. Два ключевых слова: memory_order_acquire и memory_order_release работают только в паре над одним атомарным объектом. Рассмотрим их свойства:

  • модификация атомарной переменной с release будет мгновенно видна в другом потоке, выполняющим чтение этой же атомарной переменной с acquire

  • все модификации памяти в потоке thread1, выполняющей запись атомарной переменной с release, будут видны после выполнения чтения той же переменной с acquire в потоке thread2

  • процессор и компилятор не могут перенести операции записи в память ниже release операции в потоке thread1, и нельзя перемещать выше операции чтения из памяти выше acquire операции в потоке thread2

Важно понимать, что нет полного порядка между операциями над разными атомиками, происходящих в разных потоках. Например, в примере 4 если все операции store заменить на memory_order_release, а операции load заменить на memory_order_acquire, то значение z после выполнения программы может быть равно 0, 1 или 2. Это связано с тем, что, независимо от того в каком порядке по времени выполнения выполнены store для x и y, потоки thread_read_x_then_y и thread_read_y_then_x могут увидеть эти изменения в разных порядках. Кстати, такими же изменениями для load и store можно исправить пример 3. Такое изменение будет корректным и производительными, т.к. тут нам не требуется единый порядок изменений между всеми потоками (как в случае с seq_cst ), а требуется синхронизировать память между двумя потоками.

Используя release, мы даем инструкцию, что данные в этом потоке готовы для чтения из другого потока. Используя acquire, мы даем инструкцию "подгрузить" все данные, которые подготовил для нас первый поток. Но если мы делаем release и acquire на разных атомарных переменных, то получим UB вместо синхронизации памяти.

Рассмотрим реализацию простейшего мьютекса, который ожидает в цикле сброса флага, для того, чтобы получить lock. Такой мьютекс называют spinlock. Это не самый эффективный способ реализации мьютекса, но он обладает всеми нужными свойствами, на которые я хочу обратить внимание. Пример 5, link

class mutex {
public:
	void lock() {
		bool expected = false;
		while(!_locked.compare_exchange_weak(expected, true, std::memory_order_acquire)) {
			expected = false;
		}
	}
 
	void unlock() {
		_locked.store(false, std::memory_order_release);
	}
 
private:
	std::atomic<bool> _locked;
};

Функция lock() непрерывно пробует сменить значение с false на true с модификатором синхронизации памяти acquire. Разница между compare_exchage_weak и strong незначительна, про нее можно почитать на cppreference. Функция unlock() выставляет значение в false с синхронизацией release. Обратите внимание, что мьютекс не только обеспечивает эксклюзивным доступ к блоку кода, который он защищает. Он так же делает доступным те изменения памяти, которые были сделаны до вызова unlock() в коде, который будет работать после вызова lock(). Это важное свойство. Иногда может сложиться ошибочное мнение, что мьютекс в конкретном месте не нужен.

Рассмотрим такой пример, называемый Double Checked Locking Anti-Pattern из [2]. Пример 6, link:

struct Singleton {
	// ...
};
 
static Singleton* singleton = nullptr;
static std::mutex mtx;
static bool initialized = false;
 
void lazy_init() {
	if (initialized) // early return to avoid touching mutex every call
		return;
 
	std::unique_lock l(mtx); // `mutex` locks here (acquire memory)
	if (!initialized) {
		singleton = new Singleton();
		initialized = true;
	}
	// `mutex` unlocks here (release memory)
}

Идея проста: хотим единожды в рантайме инициализировать объект Singleton. Это нужно сделать потокобезопасно, поэтому имеем мьютекс и флаг инициализации. Т.к. создается объект единожды, а используется singleton указатель в read-only режиме всю оставшуюся жизнь программы, то кажется разумным добавить предварительную проверку if (initialized) return. Данный код будет корректно работать на архитектурах процессора с более строгими гарантиями консистентности памяти, например в x86-64. Но данный код неверный с точки зрения стандарта C++. Давайте рассмотрим такой сценарий использования:

void thread1() {
	lazy_init();
	singleton->do_job();
}
 
void thread2() {
	lazy_init();
	singleton->do_job();
}

Рассмотрим следующую последовательность действий во времени:

1. сначала отрабатывает thread1 -> выполняет инициализацию под мьютексом:

  • lock мьютекса (acquire)

  • singleton = ..

  • initialized = true

  • unlock мьютекса (release)

2. далее в игру вступает thread2:

  • if(initalized) возвращает true (память, где содержится initialized могла быть неявно синхронизирована между ядрами процессора)

  • singleton->do_job() приводит к segmentation fault (указатель singleton не обязан был быть синхронизирован с потоком thread1)

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

Семантика acquire/release классов стандартной библиотеки

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

std::thread::(constructor) vs функция потока

Вызов конструктора объекта std::thread (release) синхронизирован со стартом работы функции нового потока (acquire). Таким образом функция потока может видеть все изменения памяти, которые произошли до вызова конструктора в исходном потоке.

std::thread::join vs владеющий поток

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

std::mutex::lock vs std::mutex::unlock

успешный lock синхронизирует память, которая была изменена до вызова предыдущего unlock.

std::promise::set_value vs std::future::wait

set_value синхронизирует память с успешным wait.

И так далее. Полный список можно найти в книге [1].

Что это все значит? Повторю эту важную мысль еще раз: это значит, на примере std::promise::set_value и std::future::wait, что тут мы не только получили данные, которые содержатся в примитиве синхронизации, но и нам доступны все изменения памяти, которые были в потоке до того, как он выполнил set_value. Это маленькое чудо нам кажется само собой разумеющееся с нашим бытовым, последовательным причинно-следственным, взглядом на мир. Но в мире многоядерного процессора, законы которого больше похожи на квантовую физику, которую никто до конца не понимает, нет единого последовательно порядка изменения памяти в разных ядрах процессора, если это не затребовано разработчиком явно, или неявно через многопоточные примитивы.

Заключение

Сложно представить современную C++ программу, которая была бы однопоточной. Опасно писать многопоточные программы, не имея представления о правилах синхронизации памяти. Я считаю, что нужно знать как работают атомики в C++. Чтобы не совершать ошибок типа volatile bool, чтобы понимать какие изменения в каких потоках будут видны после использования того или иного многопоточного примитива, чтобы использовать read-modify-write атомарные операции вместо мьютекса, там где это возможно. Данная статья помогла мне систематизировать материал, который я находил в разных источниках и освежить знания в памяти. Надеюсь, она поможет и вам!

Источники

[1] Anthony Williams. C++ Concurrency in Action. https://www.amazon.com/C-Concurrency-Action-Practical-Multithreading/dp/1933988770

[2] Tony van Eerd. C++ Memory Model & Lock-Free Programming. https://www.youtube.com/watch?v=14ntPfyNaKE

Автор: Дмитрий

Источник

* - обязательные к заполнению поля


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js