Модель памяти представляет из себя спецификацию допустимого поведения многопоточных программ, работающих с разделяемой памятью (shared memory) [1]. Наиболее примитивной моделью является последовательная согласованность, где все инструкции из всех потоков образуют общий порядок, согласованный с порядком выполнения программы в каждом потоке [2].

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

[1] Memory consistency primer

[2] Flight data recorder

(1) Последовательная согласованность

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

Последовательная согласованность является моделью памяти, которые некоторые языки программирования предлагают в многопроцессорной среде. В C++11 вы можете объявлять все общие (shared) переменные как атомарные (atomic) типы C++11 с дефолтными ограничениями порядка использования памяти. В Java вы можете указать все общие переменные как volatile [1] [2].

Чтобы сформировать этот порядок выполнения, компилятору необходимо вставлять дополнительные инструкции, такие как, например, барьеры памяти (memory fences).

std::atomic<int> x(0), y(0);

//thread1
x = 1;
//thread2
y = 1;

//thread3
if(x==1 && y==0)
    print ("x first");
//thread4
if(y==1 && x==0)
    print ("y first");

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

[1] Sequential consistency_1

[2] Sequential consistency_2

(2) Параллелизм требует синхронизации

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

При многопоточном выполнении неконтролируемое планирование приводит к состоянию гонки, где результаты зависят от времени выполнения кода. При определенной доле невезения (например, при переключении контекста в несвоевременные моменты выполнения) мы будем получать некорректные результаты. [1]

(i) взаимное исключение (атомарность)

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

(ii) ожидание другого потока (условная переменная)

Во многих случаях поток продолжает свое выполнение только тогда, когда удовлетворяется определенное условие. Таким образом, один поток должен ждать, пока другой завершит какое-либо действие, прежде чем продолжить свою работу. [2] [3]

[1] OSTEP threads
[2] OSTEP conditional variable
[3] Wiki conditional variable
[4] Memory fence

(3) Порядок операций с памятью имеет значение

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

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

(i) Что гарантирует процессор

  • взаимозависимые обращения к памяти будут выполняться по порядку на любом процессоре;

  • перекрывающиеся загрузки и сохранения внутри определенного процессора будут выглядеть упорядоченными в рамках этого процессора;

  • перекрывающиеся обращения к памяти могут быть объединены или опущены.

(ii) Преобразование кода

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

Оптимизации компилятора:

  • что знает компилятор
    --> все операции с памятью в этом конкретном потоке и что именно они делают, включая зависимости данных;
    --> как быть достаточно осторожным в рамках возможных псевдонимов

  • что он не знает
    --> какие ячейки памяти являются «изменяемыми разделяемыми» (mutable shared) переменными и могут изменяться асинхронно из-за операции с памятью в другом потоке
    --> как быть достаточно осторожным в рамках возможного общего доступа

  • решение: дайте ему знать --> каким-нибудь образом выделите операции над «изменяемыми разделяемыми» локациями

Независимые операции с памятью эффективно выполняются в случайном порядке, но это может быть проблемой для взаимодействия CPU-CPU и для ввода-вывода, и, следовательно, нам нужен порядок выполнения.

(iii) порядок выполнения является контрактом

Вы гарантируете: правильно синхронизировать вашу программу (без состояний гонки)
«Система» гарантирует: обеспечить иллюзию выполнения написанной вами программы

(4) Техники упорядочения операций с памятью

Чтобы гарантировать последовательную согласованность, вам нужно в первую очередь подумать о том, как предотвратить переупорядочивание памяти. Среди доступных техник можно выделить легковесную синхронизацию (lightweight sync) или барьеры (fence), строгие барьеры (full fence), или семантику захвата/освобождения (acquire/release).

Семантика сохранения (release) делает все предыдущие доступы к данным видимыми потоку, выполняющему загрузку (acquire), который связан (сопряжен) с этими сохраненными данными).

Автоматизация захвата и освобождения:

--> не прописывайте барьеры вручную.
--> заставьте компилятор расставлять барьеры за вас, используя абстракции «критических секций» (critical region): мьютексы и переменные std::atomic<>.

(i) #1: используйте мьютексы

Используйте взаимоисключающие блокировки (mutex) для защиты кода, который читает/записывает разделяемые переменные.

Плюсы:
Минусы: требует особой осторожности при каждом использовании общих переменных.

//Захват/освобождение:
mut_x.lock(); //"захват" mut_x ==> ld.acq mut_x
... read/write x ...
mut_x.unlock(); //"освобождение" mut_x ==> st.rel mut_x

(ii) #2: std::atomic<>

Специальные атомарные типы автоматически защищены от переупорядочения.

Плюсы: просто пометьте саму переменную при объявлении, а не в каждом месте, где она используется.
Минусы: писать корректный атомарный код куда сложнее, чем кажется.

std::atomics: read=acquire, write=release
while(whose_turn != me){} //считываем whose_turn ==> ld.acq whose_turn
... read/write x ...
whose_turn = someone_else; //записываем whose_turn ==> st.rel whose_turn

(iii) #3: барьеры и упорядоченные API

Барьеры памяти — это класс инструкций, обеспечивающих загрузку/сохранение памяти в ожидаемом порядке. В отличие от высокоуровневых мьютексов и атомарных объектов, барьеры памяти аппаратно-зависимы.

Программирование без блокировок (lock-free programming)

Lock-free программа никогда не может быть полностью остановлена ​​ни одним потоком. Речь идет о любых «блокировках», например, взаимных, динамических или даже вредоносных [1] [2].

[1] Sequential consistency
[2] Lock free programming
[3] Acquire and release semantics

(5) Схема объекта

Все данные в программе C++ состоят из объектов, каждый из которых является «областью хранения» (region of storage).

Объекты могут быть просто фундаментальными типами, такими как int или float, а также они могут быть экземплярами определяемых пользователем классов.

Независимо от типа объект хранится в одной или нескольких ячейках памяти (memory locations). Каждая такая ячейка памяти является либо объектом (или подобъектом) скалярного типа, например short или my_class*, или их смежные комбинации [1].

  • Каждая переменная является объектом, даже те, которые являются членами других объектов. 

  • Каждый объект занимает хотя бы одну ячейку памяти.

  • Переменные фундаментальных типов (например, int или char) занимают ровно одну ячейку памяти, независимо от их размера, даже если они являются смежными или частью массива.

  • Смежные битовые поля являются частью одной и той же ячейки памяти.

Даны две глобальные переменные char c и char d:

//Thread 1
{ lock_guard<mutex> lock(cMutex);
  c = 1;
}
//Thread 2
{ lock_guard<mutex> lock(dMutex);
  d = 1;
}

В идеальном C++11 состояния гонки нет, но в реальной жизни она есть (например, [2] и смежные битовые поля как один объект):

//система последовательно размещает c, а затем d 
char tmp[4]; //32-битный кэш
memcpy(&tmp[0], &c, 4); //читаем 32 бита, начиная с c
tmp[1] = 1; //устанавливаем только биты d
memcpy(&c, &temp[0], 4); //записываем 32 бита обратно
//thread 2 тоже незаметно записывает в c, не удерживая cMutex

[1] Bit field
[2] False sharing

Допущения и аллокация в реестре

  • Предположение (speculation)

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

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

if(cond)    |   {
lock x      |    unique_lock<mutex> hold(mut, defer_lock)
...         |     if(cond)
if(cond)    |      hold.lock();
use x       |    ...
...         |     if(cond)
if(cond)    |      use x
unlock x    |    ...
            |   }//как если бы "if(cond) hold.unlock()"

Приведенный выше общий шаблон безопасен для относительной моделей памяти C++11. Но остерегайтесь ошибок компилятора...

//x - общая переменная
if(cond)
 x = 42;
//условие считается истинным, перепишите код
r1 = x;   //читаем, что там
x = 42;   //упс: оптимистичная запись НЕ является условной
if(!cond) //проверяем, не ошиблись ли мы
x = r1;   //упс: обратная запись НЕ соответствует последовательной согласованности

  • Аллокации в регистр

Условные блокировки:

--> Проблема: ваш код условно блокируется, но в вашей системе ошибка, которая изменяет условную запись на безусловную.

(6) Техники C++11

(i) std::lock_guard

Класс lock_guard представляет собой оболочку мьютекса, которая обеспечивает удобный механизм в стиле RAII для владения мьютексом на время действия блокировки с областью видимости (scoped block).

Когда lockguard объект создан, он пытается завладеть переданным ему мьютексом. Когда управление покидает область видимости, в которой lockguard объект был создан, lock_guard уничтожается и мьютекс освобождается.

#include <thread>
#include <mutex>
#include <iostream>

int g_i = 0;
std::mutex g_i_mutex; //защищает g_i

void safe_incremenet(){
  std::lock_guard<std::mutex> lock(g_i_mutex);
  ++ g_i;
  std::cout << std::this_thread::get_id() << ":" << g_i << '\n';
  
  //g_i_mutex автоматически освобождается, когда блокировка выходит за пределы области видимости
}

int main(){
  std::cout << __func__ << ": " << g_i << '\n';
  
  std::thread t1(safe_increment);
  std::thread t2(safe_increment);
  
  t1.join();
  t2.join();
  
  std<<cout << __func__ << ": " << g_i << '\n';
}

(ii) Использование std::atomic для параллелизма

Инстансы шаблона std::atomic предлагают операции, которые гарантированно будут рассматриваться как атомарные другими потоками. Когда объект std::atomic создан, операции над ним будут вести себя так, как если бы они находились внутри критической секции, защищенной мьютексом, но эти операции обычно реализуются с использованием специальных машинных инструкций, которые более эффективны, чем в случае использования мьютекса.

std::atomic<int> ai(0); //инициализация ai в 0
ai = 10; //атомарно устанавливаем ai в 10
std::cout << ai; //атомарно считываем значение ai
++ai; //атомарно увеличиваем ai до 11
--ai; //атомарно уменьшаем ai до 10

Во время выполнения этих операторов другие потоки, читающие ai, могут видеть только значения 0, 10 или 11. Никакие другие значения невозможны (если полагать, что это единственный поток, модифицирующий ai).

std::atomic гарантирует только то, что чтение ai является атомарным, но не гарантирует, что все выражение будет выполняться атомарно.

Между моментом чтения значения ai и вызовом оператора << для записи в стандартный вывод другой поток мог изменить значение ai.

После создания объекта std::atomic все его функции-члены, в том числе содержащие RMW-операции, гарантированно будут восприниматься другими потоками как атомарные.

(iii) Непереносимые по своей сути фичи 

Для поддержки низкоуровневого программирования C++ определяет некоторые фичи, зависящие от машины:

  • Битовые поля
    Битовое поле содержит определенное количество битов, а структура памяти битового поля зависит от машины.

  • volatile
    Ключевое слово volatile указывает компилятору, что он не должен выполнять оптимизацию таких объектов.

Потоки С++

(1) Управление потоками

(i) базовые элементы управления

  • detach thread [1]
    Отделяет поток, представленный объектом, от вызывающего потока, позволяя им выполняться независимо друг от друга.
    Оба потока продолжают работать без блокировки и синхронизации.
    Когда любой из них завершает выполнение, его ресурсы освобождаются.
    Вызов detach() для объекта потока оставляет поток работать в фоновом режиме, и к нему больше нельзя присоединиться.

  • join thread [2]
    Функция возвращается после завершения выполнения потока.

  • передача владения потоком std::thread t2=std::move(t1)

[1] Thread detach

[2] Thread join

//компилируем: -std=c++0x -pthread
//функция, которую мы хотим выполнить в новом потоке
void task1(string msg){
    cout << "task1 says: " << msg;
}

int main(){
    //создает новый поток и запускает его
    //формирует: thread(Function&& f, Args&&... args);
    thread t1(task1, "Hello");
    
    //заставляет главный поток (main thread) дождаться завершения нового потока, а затем продолжить выполнение
    t1.join();
}
void pause_thread(int n){
    std::this_thread::sleep_for (std::chrono::seconds(n));
    std::cout << "pause of " << n << " seconds ended\n";
}

int main(){
    std::cout << "spawning and detaching 3 threads ...\n";
    std::thread(pause_thread, 1).detach();
    std::thread(pause_thread, 2).detach();
    std::thread(pause_thread, 3).detach();
    
    std::cout << "Done spawning thread.\n";
    //даем отсоединенным потокам время для завершения (но не гарантию)
    pause_thread(5);
    return 0;
}

Материал подготовлен в рамках курса "C++ Developer. Professional". Приходите на открытые уроки курса:

  • 28 сентября: Асинхронное программирование с помощью boost.asio: рассмотрим использование библиотеки и как работать с io_context, корутинами, strand, executor, thread_pool. Регистрация

  • 12 октября: Инструменты многопоточного программирования в стандартной библиотеке. Регистрация