Параллельное программирование на С++ в действии

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

5.1.1. Объекты и ячейки памяти

Любые данные в программе на С++ состоят из объектов. Это не значит, что можно создать новый класс, производный от

int

Некоторые объекты являются простыми значениями таких фундаментальных типов, как

int

float

Вне зависимости от типа объект хранится в одной или нескольких ячейках памяти. Каждая такая ячейка — это либо объект (или подобъект) скалярного типа, например

unsigned short

my_class*

struct

Рис. 5.1. Разбиение

struct

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

bf1

bf2

s

std::string

bf3

bf4

Отсюда можно сделать несколько важных выводов:

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

• каждый объект занимает по меньшей мере одну ячейку памяти;

• переменные фундаментальных типов, например

int

char

• соседние битовые поля размещаются в одной ячейке памяти.

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

5.1.2. Объекты, ячейки памяти и параллелизм

Для многопоточных приложений на С++ понятие ячейки памяти критически важно. Если два потока обращаются к разным ячейкам памяти, то никаких проблем не возникает и всё работает, как надо. Но если потоки обращаются к одной и той же ячейке, то необходима осторожность. Если ни один поток не обновляет ячейку памяти, то всё хорошо — доступ к данным для чтения не нуждается ни в защите, ни в синхронизации. Если же какой-то поток модифицирует данные, то возможно состояние гонки, описанное в главе 3.

Чтобы избежать гонки, необходимо принудительно упорядочить обращения из двух потоков. Один из возможных способов такого упорядочения дают мьютексы (см. главу 3) — если захватывать один и тот же мьютекс перед каждым обращением, то одновременно получить доступ к ячейке памяти сможет только один поток, так что упорядочение налицо. Другой способ упорядочить доступ из двух потоков — воспользоваться свойствами синхронизации, присущими атомарным операциям (о том, что это такое, см. раздел 5.2) над теми же или другими ячейками памяти. Такое использование атомарных операций описано в разделе 5.3. Если к одной и той же ячейке обращаются более двух потоков, то упорядочение должно быть определено для каждой пары.

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

Эта фраза критически важна: неопределенное поведение — один из самых грязных закоулков С++. Согласно стандарту языка, любое неопределенное поведение отменяет всякие гарантии — поведение всего приложения становится неопределённым, и оно может делать все, что угодно. Я знаю один пример неопределённого поведения, в результате которого загорелся монитор. Хотя маловероятно, что такое приключится с вами, гонка за данными безусловно является серьезной ошибкой, которой следует всеми силами избегать.

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

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

5.1.3. Порядок модификации

Для каждого объекта в программе на С++ определён порядок модификации, состоящий из всех операций записи в объект из всех потоков программы, начиная с инициализации объекта. В большинстве случаев порядок меняется от запуска к запуску, но при любом выполнении программы все имеющиеся в системе потоки должны договориться о порядке модификации. Если объект не принадлежит одному из описанных в разделе 5.2 атомарных типов, то вы сами отвечаете за обеспечение синхронизации, достаточной для того, чтобы потоки могли договориться о порядке модификации каждой переменной. Если разные потоки видят разные последовательности значений одной и той же переменной, то имеет место гонка за данными и, как следствие, неопределённое поведение (см. раздел 5.1.2). Если вы используете атомарные операции, то за обеспечение необходимой синхронизации отвечает компилятор.

Это требование означает, что некоторые виды спекулятивного исполнения[11] не разрешены, потому что после того как некоторый поток увидел определённое значение объекта при данном порядке модификации, последующие операции чтения в том же потоке должны возвращать более поздние значения, а последующие операции записи в тот же объект в этом потоке должны происходить позже при данном порядке модификации. Кроме того, операция чтения объекта, следующая за операцией записи в этот объект, должна вернуть либо записанное значение, либо другое значение, которое было записано позже при данном порядке модификации этого объекта. Хотя все потоки обязаны договориться о порядке модификации каждого объекта в программе, не требуется, чтобы они договаривались об относительном порядке операций над разными объектами. Дополнительные сведения об упорядочении операций, выполняемых в разных потоках, см. в разделе 5.3.3.

Итак, что понимается под атомарной операцией и как ими можно воспользоваться для принудительного упорядочения?

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

И наоборот, если операция не атомарная, то другой поток может видеть, что она выполнена частично. Если это операция сохранения, то значение, наблюдаемое другим потоком, может не совпадать ни со значением до начала сохранения, ни с сохраненным значением. С другой стороны, операция загрузки может извлечь часть объекта, после чего значение будет модифицировано другим потоком, а затем операция прочитает оставшуюся часть объекта. В результате будет извлечено значение, которое объект не имел ни до, ни после модификации. Это простая проблематичная гонка, описанная в главе 3, но на этом уровне она может представлять собой гонку за данными (см. раздел 5.1) и, стало быть, являться причиной неопределённого поведения.

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

5.2.1. Стандартные атомарные типы

Все стандартные атомарные типы определены в заголовке

is_lock_free()

x.is_lock_free()

true

x.is_lock_free()

false

Единственный тип, в котором функция-член

is_lock_free()

std::atomic_flag

std::atomic_flag

test_and_set()

clear()

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

std::atomic<>

std::atomic

std::atomic

&=

Помимо прямого использования шаблона класса

std::atomic<>

std::atomic<>

std::atomic<>

Таблица 5.1. Альтернативные имена стандартных атомарных типов и соответствующие им специализации

std::atomic<>

atomic_bool

std::atomic

atomic_char

std::atomic

atomic_schar

std::atomic

atomic_uhar

std::atomic

atomic_int

std::atomic

atomic_uint

std::atomic

atomic_short

std::atomic

atomic_ushort

std::atomic

atomic_long

std::atomic

atomic_ulong

std::atomic

atomic_llong

std::atomic

atomic_ullong

std::atomic

atomic_char16_t

std::atomic

atomic_char32_t

std::atomic

atomic_wchar_t

std::atomic

Помимо основных атомарных типов, в стандартной библиотеке С++ определены также псевдонимы

typedef

typedef

std::size_t

Таблица 5.2. Соответствие между стандартными атомарными и встроенными

typedef

typedef

typedef

atomic_int_least8_t

int_least8_t

atomic_uint_least8_t

uint_least8_t

atomic_int_least16_t

int_least16_t

atomic_uint_least16_t

uint_least16_t

atomic_int_least32_t

int_least32_t

atomic_uint_least32_t

uint_least32_t

atomic_int_least64_t

int_least64_t

atomic_uint_least64_t

uint_least64_t

atomic_int_fast8_t

int_fast8_t

atomic_uint_fast8_t

uint_fast8_t

atomic_int_fast16_t

int_fast16_t

atomic_uint_fast16_t

uint_fast16_t

atomic_int_fast32_t

int_fast32_t

atomic_uint_fast32_t

uint_fast32_t

atomic_int_fast64_t

int_fast64_t

atomic_uint_fast64_t

uint_fast64_t

atomic_intptr_t

intptr_t

atomic_uintptr_t

uintptr_t

atomic_size_t

size_t

atomic_ptrdiff_t

ptrdiff_t

atomic_intmax_t

intmax_t

atomic_uintmax_t

uintmax_t

Да уж, типов немало! Но есть простая закономерность — атомарный тип, соответствующий стандартному

typedef T

atomic_

atomic_T

signed

s

unsigned

u

long long

llong

std::atomic

T

Стандартные атомарные типы не допускают копирования и присваивания в обычном смысле, то есть не имеют копирующих конструкторов и операторов присваивания. Однако им все же можно присваивать значения соответствующих встроенных типов, и они поддерживают неявные преобразования в соответствующие встроенные типы. Кроме того, в них определены функции-члены

load()

store()

exchange()

compare_exchange_weak()

compare_exchange_strong()

+=

-=

*=

|=

std::atomic<>

++

--

fetch_add()

fetch_or()

Но шаблон класса

std::atomic<>

load()

store()

exchange()

compare_exchange_weak()

compare_exchange_strong()

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

• Операции сохранения, для которых можно задавать упорядочение

memory_order_relaxed

memory_order_release

memory_оrder_sеq_cst

• Операции загрузки, для которых можно задавать упорядочение

memory_order_relaxed

memory_order_consume

memory_order_acquire

memory_order_seq_cst

• Операции чтения-модификации-записи, для которых можно задавать упорядочение

memory_order_relaxed

memory_order_consume

memory_order_acquire

memory_order_release

memory_order_acq_rel

memory_order_seq_cst

По умолчанию для всех операций подразумевается упорядочение

memory_оrder_sеq_cst

Теперь рассмотрим, какие операции можно производить над каждым из стандартных атомарных типов, начиная с

std::atomic_flag

5.2.2. Операции над

std::atomic_flag

Простейший стандартный атомарный тип

std::atomic_flag

Объект типа

std::atomic_flag

ATOMIC_FLAG_INIT

std::atomic_flag f = ATOMIC_FLAG_INIT;

Требование применяется вне зависимости от того, где и в какой области видимости объект объявляется. Это единственный атомарный тип, к инициализации которого предъявляется столь специфическое требование, зато при этом он является также единственным типом, гарантированно свободным от блокировок. Если у объекта

std::atomic_flag

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

clear()

test_and_set()

clear()

test_and_set()

clear()

memory_order_acquire

memory_order_acq_rel

test_and_set()

memory_order_seq_cst

f.clear(std::memory_order_release);←

bool x = f.test_and_set();     ←

Здесь при вызове

clear()

test_and_set()

Объект

std::atomic_flag

std::atomic_flag

std::atomic_flag

Такая ограниченность функциональности делает тип

std::atomic_flag

test_and_set()

false

true

Листинг 5.1. Реализация мьютекса-спинлока с использованием

std::atomic_flag

class spinlock_mutex {

 std::atomic_flag flag;

public:

 spinlock_mutex():

  flag(ATOMIC_FLAG_INIT) {}

 void lock() {

  while (flag.test_and_set(std::memory_order_acquire));

 }

 void unlock() {

  flag.clear(std::memory_order_release);

 }

};

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

std::lock_guard<>

lock()

Тип

std::atomic_flag

std::atomic

5.2.3. Операции над

std::atomic

Из атомарных целочисленных типов простейшим является

std::atomic

std::atomic_flag

bool

true

false

std::atomic

bool

std::atomic b(true);

b = false;

Что касается оператора присваивания с неатомарным

bool

bool

Запись (любого значения:

true

false

clear()

std::atomic_flag

store()

test_and_set()

exchange()

std::atomic

bool

load()

store()

load()

exchange()

std::atomic b;

bool x = b.load(std::memory_order_acquire);

b.store(true);

x = b.exchange(false, std::memory_order_acq_rel);

Функция

exchange()

std::atomic

Новая операция называется «сравнить и обменять» и реализована в виде функций-членов

compare_exchange_weak()

compare_exchange_strong()

bool

true

false

В случае

compare_exchange_weak()

false

Поскольку

compare_exchange_weak()

bool expected = false;

extern atomic b; // установлена где-то в другом месте

while (!b.compare_exchange_weak(expected, true) && !expected);

Этот цикл продолжается, пока

expected

false

compare_exchange_weak()

С другой стороны,

compare_exchange_strong()

false

expected

Если мы хотим изменить переменную, каким бы ни было ее текущее значение (при этом новое значение может зависеть от текущего), то обновление

expected

expected

compare_exchange_weak()

compare_exchange_strong()

compare_exchange_weak()

compare_exchange_weak()

compare_exchange_strong()

compare_exchange_strong()

expected

std::atomic

Функции сравнения и обмена необычны еще и тем, что могут принимать два параметра упорядочения доступа к памяти. Это позволяет по-разному задавать семантику упорядочения в случае успеха и отказа; быть может, при успешном вызове требуется семантика

memory_order_acq_rel

memory_order_relaxed

memory_order_release

memory_order_acq_rel

memory_order_acquire

memory_order_seq_cst

Если упорядочение для отказа не задано, то предполагается, что оно такое же, как для успеха, с тем отличием, что часть release заменяется:

memory_order_release

memory_order_relaxed

memory_order_acq_rel

memory_order_acquire

memory_order_seq_cst

compare_exchange_weak()

std::atomic b;

bool expected;

b.compare_exchange_weak(expected, true,

memory_order_acq_rel, memory_order_acquire);

b.compare_exchange_weak(expected, true, memory_order_acq_rel);

К чему приводит задание того или иного упорядочения, я расскажу в разделе 5.3.

Еще одно отличие

std::atomic

std::atomic_flag

std::atomic

is_lock_free()

std::atomic

std::atomic_flag

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

std::atomic

5.2.4. Операции над

std::atomic

: арифметика указателей

Атомарная форма указателя на тип

T

std::atomic

bool

std::atomic

bool

std::atomic

is_lock_free()

std::atomic

load()

store(

exchange()

compare_exchange_weak()

compare_exchange_strong()

std::atomic

T*

bool

Новыми в типе

std::atomic

fetch_add()

fetch_sub()

+=

-=

++

--

x

std::atomic

Foo

x+=3

x

Foo*

fetch_add()

fetch_sub()

x.fetch_add(3)

x

exchange()

compare_exchange_weak()

compare_exchange_strong()

fetch_add()

T*

std::atomic

class Foo{};

Foo some_array[5];        │

std::atomic p(some_array);│

Foo* x = p.fetch_add(2);    ←┘

assert(x == some_array);

assert(p.load() == &some_array[2]);

x = (p -= 1);           ←┐ 

assert(x == &some_array[1]);    │

assert(p.load() == &some_array[1]);│

Функциям можно также передать в дополнительном аргументе семантику упорядочения доступа к памяти:

p.fetch_add(3, std::memory_order_release);

Поскольку

fetch_add()

fetch_sub()

memory_order_sеq_cst

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

5.2.5. Операции над стандартными атомарными целочисленными типами

Помимо обычного набора операций (

load()

store()

exchange()

compare_exchange_weak()

compare_exchange_strong()

std::atomic

std::atomic

fetch_add()

fetch_sub()

fetch_and()

fetch_or()

fetch_xor()

+=

-=

&=

|=

^=

++x

x++

--x

x--

compare_exchange_weak()

Семантика операций близка к семантике функций

fetch_add()

fetch_sub()

std::atomic

++x

x++

Мы рассмотрели все простые атомарные типы; остался только основной обобщенный шаблон класса

std::atomic<>

5.2.6. Основной шаблон класса

std::atomic<>

Наличие основного шаблона позволяет создавать атомарные варианты пользовательских типов, в дополнение к стандартным атомарным типам. Однако в качестве параметра шаблона

std::atomic<>

UDT

std::atomic

memcpy()

Наконец, тип должен допускать побитовое сравнение на равенство. Это требование из того же разряда, что требования к присваиванию — должна быть не только возможность колировать объекты с помощью

memcpy()

memcmp()

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

td::atomic

std::atomic

Отметим, что несмотря на то, что типы

std::atomic

std::atomic

memcpy

memcmp

compare_exchange_strong

compare_exchange_strong

std::atomic<>

memcmp

Если размер пользовательского типа

UDT

int

void*

std::atomic

int

void*

compare_exchange_xxx

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

std::atomic>

std::mutex

Интерфейс шаблона

std::atomic

T

std::atomic

load()

store()

exchange()

compare_exchange_weak()

compare_exchange_strong()

T

T

В табл. 5.3 перечислены операции, доступные для всех атомарных типов.

Таблица 5.3. Операции над атомарными типами

atomic_ flag

atomic 

atomic 

atomic 

atomic 

test_and_set

clear

is_lock_free

load

store

exchange

compare_exchange_weak, compare_exchange_strong

fetch_add, +=

fetch_sub, -=

fetch_or, |=

fetch_and, &=

fetch_xor, ^=

++, --

5.2.7. Свободные функции для атомарных операций

До сих пор я описывал только те операции над атомарными типами, которые реализованы функциями-членами. Однако для всех этих операций существуют также эквивалентные функции, не являющиеся членами классов. Как правило, имена свободных функций строятся по единому образцу: имя соответствующей функции-члена с префиксом

atomic_

std::atomic_load()

_explicit

std::atomic_store(&atomic_var, new_value)

std::atomic_store_explicit(&atomic_var, new_value, std::memory_order_release)

Например, для функции

std::atomic_is_lock_free()

std::atomic_is_lock_free(&a)

a.is_lock_free()

а

std::atomic_load(&a)

a.load()

a.load(std::memory_order_acquire)

std::atomic_load_explicit(&a, std::memory_order_acquire)

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

compare_exchange_weak()

compare_exchange_strong()

std::atomic_compare_exchange_weak()

std::atomic_compare_exchange_weak_explicit()

std::memory_order_seq_cst

Операции над типом

std::atomic_flag

std::atomic_flag_test_and_set()

std::atomic_flag_clear()

_explicit

std::atomic_flag_test_and_set_explicit()

std::atomic_flag_clear_explicit()

В стандартной библиотеке С++ имеются также свободные функции для атомарного доступа к экземплярам типа

std::shared_ptr<>

std::shared_ptr<>

std::shared_ptr<>*

std::shared_ptr p;

void process_global_data() {

 std::shared_ptr local = std::atomic_load(&p);

 process_data(local);

}

void update_global_data() {

 std::shared_ptr local(new my_data);

 std::atomic_store(&p, local);

}

Как и для атомарных операций над другими типами, предоставляются

_explicit

std::atomic_is_lock_free()

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

std::mutex

std::future<>

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

Листинг 5.2. Запись и чтение переменной в разных потоках

#include 

#include 

#include 

std::vector data;

std::atomic data_ready(false);

void reader_thread() {

 while (!data_ready.load()) {       ←

  std::this_thread::sleep(std::milliseconds(1));

 }

 std::cout << "Ответ=" << data[0] << "\n";←

}

void writer_thread() {

 data.push_back(42); ←

 data_ready = true;  ←

}

Оставим пока в стороне вопрос о неэффективности цикла ожидания готовности данных (1). Для работы этой программы он действительно необходим, потому что в противном случае разделение данных между потоками становится практически бесполезным: каждый элемент данных должен быть атомарным. Вы уже знаете, что неатомарные операции чтения (2) и записи (3) одних и тех же данных без принудительного упорядочения приводят к неопределённому поведению, поэтому где-то упорядочение должно производиться, иначе ничего работать не будет.

Требуемое упорядочение обеспечивают операции с переменной

data_ready

std::atomic

data_ready

data_ready

true

true

while

Рис. 5.2. Принудительное задание упорядочения неатомарных операций с помощью атомарных

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

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

5.3.1. Отношение синхронизируется-с

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

Идея такова: подходящим образом помеченная атомарная операция записи

W

x

x

W

x

W,

x

fetch_add()

compare_exchange_weak()

W

Пока оставим в стороне слова «подходящим образом помеченная», потому что по умолчанию все операции над атомарными типами помечены подходящим образом. По существу сказанное выше означает ровно то, что вы ожидаете: если поток А сохраняет значение, а поток В читает это значение, то существует отношение синхронизируется-с между сохранением в потоке А и загрузкой в потоке В — как в листинге 5.2.

Уверен, вы догадались, что нюансы как раз и скрываются за словами «подходящим образом помеченная». Модель памяти в С++ допускает применение различных ограничений на упорядочение к операциям над атомарными типами, и именно это и называется пометкой. Варианты упорядочения доступа к памяти и их связь с отношением синхронизируется-с рассматриваются в разделе 5.3.3. А пока отступим на один шаг и поговорим об отношении происходит-раньше.

5.3.2. Отношение происходит-раньше

Отношение происходит-раньше — основной строительный блок механизма упорядочения операций в программе. Оно определяет, какие операции видят последствия других операций и каких именно. В однопоточной программе всё просто: если в последовательности выполняемых операций одна стоит раньше другой, то она и происходит-раньше. Иначе говоря, если операция А в исходном коде предшествует операции В, то А происходит-раньше В. Это мы видели в листинге 5.2: запись в переменную

data

data_ready

1,2

2,1

get_num()

Листинг 5.3. Порядок определения аргументов функции не определён

#include 

void foo(int a, int b) {

 std::cout << a << "," << b << std::endl;

}

int get_num() {

 static int i = 0;

 return ++i;

}

int main() {

 foo(get_num(), get_num());←┐

}              │

Существуют случаи, когда порядок операций внутри одного предложения точно известен, например, если используется встроенный оператор «занятая» или результат одного выражения является аргументом другого выражения. Но в общем случае никакого отношения расположено-перед (а, значит, и отношения происходит-раньше) между ними не существует. Разумеется, все операции в одном предложении происходят раньше всех операций в следующем за ним предложении.

Но это просто пересказ другими словами давно известных вам правил упорядочения в однопоточной программе. А где же новое? Новым является взаимодействие между потоками: если операция А в одном потоке межпоточно происходит-раньше операции В в другом потоке, то А происходит-раньше В. Вроде бы толку немного, мы просто добавили новое отношение (межпоточно происходит-раньше), но при написании многопоточной программы это отношение оказывается очень важным.

На понятийном уровне отношение межпоточно происходит-раньше довольно простое, оно опирается на отношение синхронизируется-с, введенное в разделе 5.3.1: если операция А в одном потоке синхронизируется-с операцией В в другом потоке, то А межпоточно происходит-раньше В. Это отношение также транзитивно: если А межпоточно происходит-раньше В, а В межпоточно происходит-раньше С, то А межпоточно происходит-раньше С. Это мы тоже видели в листинге 5.2.

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

Именно эти критически важные правила и обеспечивают упорядоченность операций между потоками, благодаря чему программа в листинге 5.2 работает правильно. Как мы скоро увидим, существуют дополнительные нюансы, связанные с зависимостями между данными. Чтобы разобраться в них, мне нужно будет рассмотреть признаки упорядочения доступа к памяти, используемые в атомарных операциях, и рассказать, как они связаны с отношением синхронизируется-с.

5.3.3. Упорядочение доступа к памяти для атомарных операций

Существует шесть вариантов упорядочения доступа к памяти, которые можно задавать в операциях над атомарными типами:

memory_order_relaxed

memory_order_consume

memory_order_acquire

memory_order_release

memory_order_acq_rel

memory_order_seq_cst

memory_order_seq_cst

memory_order_seq_cst

memory_order_consume

memory_order_acquire

memory_order_release

memory_order_acq_rel

memory_order_relaxed

Эти три модели упорядочения доступа к памяти влекут за собой различные издержки для процессоров с разной архитектурой. Например, в системах с точным контролем над видимостью операций процессорами, отличными от произведшего изменения, могут потребоваться дополнительные команды синхронизации для обеспечения последовательно согласованного упорядочения по сравнению с ослабленным или упорядочением захват-освобождение, а также для обеспечения упорядочения захват-освобождение по сравнению с ослабленным. Если в такой системе много процессоров, то на выполнение дополнительных команд синхронизации может уходить заметное время, что приведет к снижению общей производительности системы. С другой стороны, процессоры с архитектурой x86 или x86-64 (в частности, Intel и AMD, столь распространенные в настольных ПК) не требуют никаких дополнительных команд для обеспечения упорядочения захват-освобождение, помимо необходимых для гарантий атомарности, и даже последовательно согласованное упорядочение не нуждается в каких-то специальных действиях на операциях загрузки, хотя операции сохранения все же требуют некоторых добавочных затрат.

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

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

Упорядочение по умолчанию называется последовательно согласованным, потому что оно предполагает, что поведение программы согласовано с простым последовательным взглядом на мир. Если все операции над экземплярами атомарных типов последовательно согласованы, то поведение многопоточной программы такое же, как если бы эти операции выполнялись в какой-то определенной последовательности в одном потоке. Это самое простое для понимания упорядочение доступа к памяти, потому оно и подразумевается по умолчанию: все потоки должны видеть один и тот же порядок операций. Таким образом, становится достаточно легко рассуждать о поведении программы, написанной с использованием атомарных переменных. Можно выписать все возможные последовательности операций, выполняемых разными потоками, отбросить несогласованные и проверить, что в остальных случаях программа ведет себя, как и ожидалось. Это также означает, что порядок операций нельзя изменять; если в каком-то потоке одна операция предшествует другой, то этот порядок должен быть виден всем остальным потокам.

С точки зрения синхронизации, последовательно согласованное сохранение синхронизируется-с последовательно согласованной операцией загрузки той же переменной, в которой читается сохраненное значение. Тем самым мы получаем одно ограничение на упорядочение операций в двух или более потоках. Однако этим последовательная согласованность не исчерпывается. Любая последовательно согласованная операция, выполненная после этой загрузки, должна быть видна всякому другому потоку в системе с последовательно согласованными атомарными операциями именно как следующая за загрузкой. Пример в листинге 5.4 демонстрирует это ограничение на упорядочение в действии. Однако это ограничение не распространяется на потоки, в которых для атомарных операций задано ослабленное упорядочение — они по-прежнему могут видеть операции в другом порядке. Поэтому, чтобы получить пользу от последовательного согласования операций, его надо использовать во всех потоках.

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

В следующем листинге последовательная согласованность демонстрируется на примере. Операции загрузки и сохранения переменных

x

y

memory_order_seq_cst

Листинг 5.4. Из последовательной согласованности вытекает полная упорядоченность

#include 

#include 

#include 

std::atomic x, y;

std::atomic z;

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() {

 x = false;

 y = false;

 z = 0;

 std::thread a(write_x);

 std::thread b(write_y);

 std::thread с(read_x_then_y);

 std::thread d(read_y_then_x);

 a.join();

 b.join();

 c.join();

 d.join();

 assert(z.load() != 0); ←

}

Утверждение

assert

x

y

y

read_x_then_y

false

x

y

x

read_y_then_x

true

while

у

true

memory_order_seq_cst

memory_order_seq_cst

y

false

y

x==true

y==false

x

y

Разумеется, поскольку всё симметрично, могло бы произойти и ровно наоборот: загрузка

x

false

y

true

z

true

z

z

Операции и отношения происходит-раньше для случая, когда

read_x_then_y

x

true

y

false

y

read_x_then_y

y

write_y

memory_order_seq_cst

Рис. 5.3. Последовательная согласованность и отношения происходит-раньше

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

За пределами уютного последовательно согласованного мирка нас встречает более сложная реальность. И, пожалуй, самое трудное — смириться с тем фактом, что единого глобального порядка событий больше не существует. Это означает, что разные потоки могут по-разному видеть одни и те же операции, и с любой умозрительной моделью, предполагающей, что операции, выполняемые в разных потоках, строго перемежаются, следует распрощаться. Вы должны учитывать не только то, что события могут происходить по-настоящему одновременно, но и то, что потоки не обязаны согласовывать порядок событий между собой. Чтобы написать (или хотя бы понять) код, в котором используется упорядочение, отличное от

memory_order_seq_cst

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

Проще всего это продемонстрировать, перейдя от последовательной согласованности к ее полной противоположности — упорядочению

memory_order_relaxed

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

memory_order_relaxed

Чтобы продемонстрировать, до какой степени могут быть «ослаблены» операции в этой модели, достаточно всего двух потоков (см. листинг 5.5).

Листинг 5.5. К ослабленным операциям предъявляются очень слабые требования

#include 

#include 

#include 

std::atomic x,y;

std::atomic z;

void write_x_then_y() {

 x.store(true, std::memory_order_relaxed); ←

 y.store(true, std::memory_order_relaxed); ←

}

void read_y_then_x() {

 while (!y.load(std::memory_order_relaxed));←

 if (x.load(std::memory_order_relaxed))   ←

  ++z;

}

int main() {

 x = false;

 y = false;

 z = 0;

 std::thread а(write_x_then_y);

 std::thread b(read_y_then_x);

 a.join();

 b.join();

 assert (z.load() != 0); ←

}

На этот раз утверждение (5) может сработать, потому что операция загрузки

x

false

y

true

x

y

x

y

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

Рис. 5.4. Ослабленные атомарные операции и отношения происходит-раньше

Рассмотрим чуть более сложный пример с тремя переменными и пятью потоками.

Листинг 5.6. Ослабленные операции в нескольких потоках

#include 

#include 

#include 

std::atomic x(0), y(0), z(0);←

std::atomic go(false);    ←

unsigned const loop_count = 10;

struct read_values {

 int x, y, z;

};

read_values values1[loop_count];

read_values values2[loop_count];

read_values values3[loop_count];

read_values values4[loop_count];

read_values values5[loop_count];

void increment(

 std::atomic* var_to_inc, read_values* values) {

 while (!go) ←

  std::this_thread::yield();

 for (unsigned i = 0; i < loop_count; ++i) {

  values[i].x = x.load(std::memory_order_relaxed);

  values[i].y = y.load(std::memory_order_relaxed);

  values[i].z = z.load(std::memory_order_relaxed);

  var_to_inc->store(i + 1, std::memory_order_relaxed);←

  std::this_thread::yield();

 }

}

void read_vals(read_values* values) {

 while (!go) ←

 std::this_thread::yield();

 for (unsigned i = 0; i < loop_count; ++i) {

  values[i].x = x.load(std::memory_order_relaxed);

  values[i].y = y.load(std::memory_order_relaxed);

  values[i].z = z.load(std::memory_order_relaxed);

  std::this_thread::yield();

 }

}

void print(read_values* v) {

 for (unsigned i = 0; i < loop_count; ++i) {

  if (i)

  std::cout << ",";

  std::cout <<

   "(" << v [i] .x << "," << v[i].y << "," << v[i].z << ")";

 }

 std::cout << std::endl;

}

int main() {

 std::thread t1(increment, &x, values1);

 std::thread t2(increment, &y, values2);

 std::thread t3(increment, &z, values3);

 std::thread t4(read_vals, values4);

 std::thread t5(read_vals, values5);

 go = true; ←┐

                     │
            

 t5.join();

 t4.join();

 t3.join();

 t2.join();

 t1.join();

 print(values1);←┐

 print(values2); │

 print(values3);

 print(values4);

 print(values5);

}

По существу, это очень простая программа. У нас есть три разделяемых глобальных атомарных переменных (1) и пять потоков. Каждый поток выполняет 10 итераций цикла, читая значения трех атомарных переменных в режиме

memory_order_relaxed

Атомарная переменная

go

go

true

go

true

Ниже показан один из возможных результатов прогона этой прогона:

(0,0,0),(1,0,0),(2,0,0),(3,0,0),(4,0,0),(5,7,0),(6,7,8),(7,9,8),(8,9,8),(9,9,10)

(0,0,0),(0,1,0),(0,2,0),(1,3,5),(8,4,5),(8,5,5),(8,6,6),(8,7,9),(10,8,9),(10,9,10)

(0,0,0),(0,0,1),(0,0,2),(0,0,3),(0,0,4),(0,0,5),(0,0,6),(0,0,7),(0,0,8),(0,0,9)

(1,3,0),(2,3,0),(2,4,1),(3,6,4),(3,9,5),(5,10,6),(5,10,8),(5,10,10),(9,10,10),(10,10,10)

(0,0,0),(0,0,0),(0,0,0),(6,3,7),(6,5,7),(7,7,7),(7,8,7),(8,8,7),(8,8,9),(8,8,9)

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

x

y

z

• В первом наборе значения

x

y

z

• Значения

x

y

z

• Поток 3 не видит обновлений

x

y

z

z

x

y

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

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

При первой просьбе дать значение человек может прочитать любое значение из списка, имеющегося в данный момент. В ответ на следующую просьбу он может прочитать либо то же самое значение, либо значение, расположенное позже него в списке, но никогда — значение, расположенное раньше уже прочитанного. Если вы просили записать значение, а потом прочитать, то он может сообщить либо значение, записанное в ответ на вашу просьбу, либо расположенное позже него в списке.

Теперь представьте, что в начале списка находятся значения 5, 10, 23, 3, 1, 2. Человек может прочитать любое из них. Если он скажет 10, то в следующий раз он может прочитать также 10 или любое последующее число, но не 5. Если вы позвоните пять раз, то может услышать, например, последовательность «10, 10, 1, 2, 2». Если вы попросите записать 42, он добавит это число в конец списка. Если вы затем будете просить прочитать число, то он будет повторять «42», пока в списке не появится новое число и он не захочет назвать его.

Предположим далее, что у Карла тоже есть телефон этого человека. Карл тоже может позволить ему с просьбой либо прочитать, либо записать число. При этом к Карлу применяются те же правила, что и к вам. Телефон только один, поэтому в каждый момент времени человек общается только с одним из вас, так что список в его блокноте растет строго последовательно. Но из того, что вы попросили записать его новое число, вовсе не следует, что он должен сообщить его Карлу. и наоборот. Если Карл попросил назвать число и услышал в ответ «23», то из того, что вы попросили записать число 42, не вытекает, что в следующий раз Карл услышит его. Человек может назвать Карлу любое из чисел 23, 3, 1, 2, 42 или даже 67, если после вас позвонил Фред и попросил записать это число. Он даже может назвать Карлу последовательность «23, 3, 3, 1, 67», и это не будет противоречить тому, что услышали вы. Можно представить себе, что человек запоминает, какое число кому назвал, сдвигая указатели, на которых написано имя спрашивающего, как показано на рис. 5.5.

Рис. 5.5. Блокнот человека, сидящего в боксе

Теперь представьте, что имеется целый ряд боксов, в каждом из которых сидит по человеку с блокнотом и телефоном. Это всё наши атомарные переменные. У каждой переменной свой порядок модификации (список значений в блокноте), по между ними нет никакой связи. Если каждый звонящий (вы, Карл, Анна, Дэйв и Фред) представляет поток, то именно такая картина наблюдается, когда все операции работают в режиме

memory_order_relaxed

exchange

compare_exchange_strong

Применив эту метафору к программе в листинге 5.5, можно сказать, что

write_x_then_y

x

true

y

true

read_y_then_x

y

true

x

x

false

Из-за этого с ослабленными атомарными операциями трудно иметь дело. Чтобы они были полезны для межпоточной синхронизации, их нужно сочетать с атомарными операциями, работающими в режиме с более строгой семантикой упорядочения. Я настоятельно рекомендую вообще избегать ослабленных атомарных операций, если без них можно обойтись, а, если никак нельзя, то использовать крайне осторожно. Учитывая, насколько интуитивно неочевидные результаты получились в листинге 5.5 при наличии всего двух потоков и двух переменных, нетрудно представить себе сложности, с которыми придется столкнуться, когда потоков и переменных станет больше.

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

Упорядочение захват-освобождение — шаг от ослабленного упорядочения в сторону большего порядка; полной упорядоченности операций еще нет, но какая-то синхронизация уже возможна. При такой модели атомарные операции загрузки являются операциями захвата (

memory_order_acquire

memory_order_release

fetch_add()

exchange()

memory_order_acq_rel

Листинг 5.7. Из семантики захвата-освобождения не вытекает полная упорядоченность

#include 

#include 

#include 

std::atomic x, y;

std::atomic z;

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));

 if (y.load(std::memory_order_acquire)) ←

  ++z;

}

void read_y_then_x() {

 while (!y.load(std::memory_order_acquire));

 if (x.load(std::memory_order_acquire)) ←

  ++z;

}

int main() {

 x = false;

 y = false;

 z = 0;

 std::thread a(write_x);

 std::thread b(write_y);

 std::thread с(read_x_then_y);

 std::thread d(read_y_then_x);

 a.join();

 b.join();

 c.join();

 d.join();

 assert(z.load() != 0); ←

}

В данном случае утверждение (3) может сработать (как и в случае ослабленного упорядочения), потому что обе операции загрузки —

x

y

false

x

y

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

Рис. 5.6. Захват-освобождение и отношения происходит-раньше

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

y

memory_order_release

y

memory_order_acquire

x

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

#include 

#include 

#include 

std::atomic x, y;

std::atomic z;

void write_x_then_y() {

 x.store(true,std::memory_order_relaxed);  ←

 y.store(true,std::memory_order_release);  ←

}

void read_y_then_x() {

 while (!y.load(std::memory_order_acquire));←

 if (x.load(std::memory_order_relaxed))   ←

  ++z;

}

int main() {

 x = false;

 y = false;

 z = 0;

 std::thread a(write_x_then_y);

 std::thread b(read_y_then_x);

 a.join();

 b.join();

 assert(z.load() != 0); ←

}

В конечном итоге операция загрузки

y

true

memory_order_release

memory_order_acquire

x

y

y

y

x

y

x

x

true

y

while

y

false

x

x

true

assert

К упорядочению захват-освобождение можно применить метафору человека с блокнотом в боксе, если ее немного дополнить. Во-первых, допустим, что каждое сохранение является частью некоторого пакета обновлений, поэтому, обращаясь к человеку с просьбой записать число, вы заодно сообщается ему идентификатор пакета, например: «Запиши 99 как часть пакета 423». Если речь идет о последнем сохранении в пакете, то мы сообщаем об этом: «Запиши 147, отметив, что это последнее сохранение в пакете 423». Человек в боксе честно записывает эту информацию вместе с указанным вами значением. Так моделируется операция сохранения с освобождением. Когда вы в следующий раз попросите записать значение, помер пакета нужно будет увеличить: «Запиши 41 как часть пакета 424».

Теперь, когда вы просите сообщить значение, у вас есть выбор: узнать только значение (это аналог ослабленной загрузки) или значение и сведения о том, является ли оно последним в пакете (это аналог загрузки с захватом). Если информация о пакете запрашивается, по значение не последнее в пакете, то человек ответит: «Число равно 987, и это 'обычное' значение»; если же значение последнее, то ответ прозвучит так: «Число 987, последнее в пакете 956 от Анны». Тут-то и проявляется семантика захвата-освобождения: если, запрашивая значение, вы сообщите человеку номера всех пакетов, о которых знаете, то он найдёт в своем списке последнее значение из всех известных вам пакетов и назовёт либо его, либо какое-нибудь следующее за ним в списке.

Как эта метафора моделирует семантику захвата-освобождения? Взгляните на наш пример — и поймете. В самом начале поток

а

write_x_then_y

x

true

а

а

y

true

а

b

read_y_then_x

y

true

true

y

true

а

Далее поток

b

x

а

а

true

Вспомнив определение отношения межпоточно происходит раньше в разделе 5.3.2, вы обнаружите, что одно из его существенных свойств — транзитивность: если А межпоточно происходит-раньше В и В межпоточно происходит-раньше С, то А межпоточно происходит-раньше С. Это означает, что упорядочение захват-освобождение можно использовать для синхронизации данных между несколькими потоками, даже если «промежуточные» потоки на самом деле не обращались к данным.

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

Листинг 5.9. Транзитивная синхронизация с помощью упорядочения захват-освобождение

std::atomic data[5];

std::atomic sync1(false), sync2(false);

void thread_1() {

 data[0].store(42, std::memory_order_relaxed);

 data[1].store(97, std::memory_order_relaxed);

 data[2].store(17, std::memory_order_relaxed);

 data[3].store(-141, std::memory_order_relaxed);

 data[4].store(2003, std::memory_order_relaxed);←┐

 sync1.store(true, std::memory_order_release); 

}

void thread_2()                 

{                         │

 while (!sync1.load(std::memory_order_acquire));←┘

 sync2.store(true, std::memory_order_release); ←┐

}                       

void thread_3()                 

{                         │

 while (!sync2.load(std::memory_order_acquire));←┘

 assert(data[0].load(std::memory_order_relaxed) == 42);

 assert(data[1].load(std::memory_order_relaxed) == 97);

 assert(data[2].load(std::memory_order_relaxed) == 17);

 assert(data[3].load(std::memory_order_relaxed) == -141);

 assert(data[4].load(std::memory_order_relaxed) == 2003);

}

Хотя поток

thread_2

sync1

sync2

thread_1

thread_3

assert

data

thread_1

sync1

sync1

while

thread_1

sync1

sync1

while

sync2

while

thread_3

sync2

data

data

sync1

sync1

sync2

sync2

data

data

thread_1

data

thread_3

assert

В этом случае можно было бы объединить

sync1

sync2

memory_order_acq_rel

thread_2

compare_exchange_strong()

thread_2

thread_1

std::atomic sync(0);

void thread_1() {

 // ...

 sync.store(1, std::memory_order_release);

}

void thread_2() {

 int expected = 1;

 while (!sync.compare_exchange_strong(expected, 2,

     std::memory_order_acq_rel))

  expected = 1;

}

void thread_3() {

 while(sync.load(std::memory_order_acquire) < 2);

 // ...

}

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

memory_order_acq_rel

fetch_sub

memory_order_acquire

fetch_or

memory_order_release

fetch_or

memory_order_acq_rel

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

Несмотря на интуитивно неочевидные результаты, всякий, кто использовал блокировки, вынужденно имел дело с вопросами упорядочения: блокировка мьютекса — это операция захвата, а его разблокировка — операция освобождения. Работая с мьютексами, вы на опыте узнаете, что при чтении значения необходимо захватывать тот же мьютекс, который захватывался при его записи. Точно так же обстоит дело и здесь — для обеспечения упорядочения операции захвата и освобождения должны применяться к одной и той же переменной. Если данные защищены мьютексом, то взаимно исключающая природа блокировки означает, что результат неотличим от того, который получился бы, если бы операции блокировки и разблокировки были последовательно согласованы. Аналогично, если для построения простой блокировки к атомарным переменным применяется упорядочение захват-освобождение, то с точки зрения программы, использующей такую блокировку, поведение кажется последовательно согласованным, хотя внутренние операции таковыми не являются.

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

memory_order_consume

Во введении к этому разделу я говорил, что семантика

memory_order_consume

memory_order_consume

С зависимостями по данным связаны два новых отношения: предшествует-по-зависимости (dependency-ordered-before) и переносит-зависимость-в (carries-a-dependency-to). Как и отношение расположено-перед, отношение переносит-зависимость-в применяется строго внутри одного потока и моделирует зависимость по данным между операциями — если результат операции А используется в качестве операнда операции В, то А переносит-зависимость-в В. Если результатом операции А является значение скалярного типа, например

int

С другой стороны, отношение предшествует-по-зависимости может применяться к разным потокам. Оно вводится с помощью атомарных операций загрузки, помеченных признаком

memory_order_consume

memory_order_acquire

memory_order_release

memory_order_acq_rel

memory_order_seq_cst

memory_order_consume

memory_order_acquire

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

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

memory_order_consume

memory_order_release

Листинг 5.10. Использование

std::memory_order_consume

struct X {

 int i;

 std::string s;

};

std::atomic p;

std::atomic a;

void create_x() {

 X* x = new X;

 x->i = 42;

 x->s = "hello";

 a.store(99, std::memory_order_relaxed);←

 p.store(x, std::memory_order_release); ←

}

void use_x() {

 X* x;

 while (!(x = p.load(std::memory_order_consume)))←

 std::this_thread::sleep(std::chrono::microseconds(1));

 assert(x->i == 42);               ←

 assert(x->s =="hello");             ←

 assert(a.load(std::memory_order_relaxed) == 99);←

}

int main() {

 std::thread t1(create_x);

 std::thread t2(use_x);

 t1.join();

 t2.join();

}

Хотя сохранение

а

p

p

memory_order_release

p

memory_order_consume

p

p

x

p

x

а

p

memory_order_relaxed

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

std::kill_dependency()

std::memory_order_consum

std::kill_dependency()

int global_data[] = { ... };

std::atomic index;

void f() {

 int i = index.load(std::memory_order_consume);

 do_something_with(global_data[std::kill_dependency(i)]);

}

Разумеется, в таком простом случае вы вряд ли вообще будете пользоваться семантикой

std::memory_order_consume

std::kill_dependency()

Теперь, рассмотрев основы упорядочения доступа к памяти, мы можем перейти к более сложным аспектам отношения синхронизируется-с, которые проявляются в форме последовательностей освобождений (release sequences).

5.3.4. Последовательности освобождений и отношение синхронизируется-с

В разделе 5.3.1 я упоминал, что можно получить отношение синхронизируется-с между операцией сохранения атомарной переменной и операцией загрузки той же атомарной переменной в другом потоке, даже если между ними выполняется последовательность операций чтения-модификации-записи, — при условии, что все операции помечены надлежащим признаками. Теперь, когда мы знаем обо всех возможных «признаках» упорядочения, я могу подробнее осветить этот вопрос. Если операция сохранения помечена одним из признаков

memory_order_release

memory_order_acq_rel

memory_order_seq_cst

memory_order_consume

memory_order_acquire

memory_order_seq_cst

memory_order_acquire

memory_order_seq_cst

memory_order_consume

memory_order_relaxed

Чтобы попять, что это означает и почему так важно, рассмотрим значение типа

atomic

count

Листинг 5.11. Чтение из очереди с применением атомарных операций

#include 

#include 

std::vector queue_data; std::atomic count;

void populate_queue() {

 unsigned const number_of_items = 20;

 queue_data.clear();

 for (unsigned i = 0; i < number_of_items; ++i) {

  queue_data.push_back(i);

 } ←

 count.store(number_of_items, std::memory_order_release);

}

void consume_queue_items() {

 while (true) { ←

 int item_index;

 if (

  (item_index =

  count.fetch_sub(1, std::memory_order_acquire)) <= 0) {

  wait_for_more_items();←┐

  continue;       

 }

 process(queue_data[item_index-1]);←┐

}                 

int main() {

 std::thread a(populate_queue);

 std::thread b(consume_queue_items);

 std::thread с(consume_queue_items);

 a.join();

 b.join();

 c.join();

}

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

count.store(numbеr_of_items, memory_order_release)

count.fetch_sub(1, memory_order_acquire)

count

Если поток-потребитель всего один, то всё хорошо;

fetch_sub()

memory_order_acquire

memory_order_release

fetch_sub()

store

fetch_sub()

memory_order_release

memory_order_release

fetch_sub

fetch_sub(

store()

fetch_sub()

Рис. 5.7. Последовательность освобождений для операций с очередью из листинга 5.11

В цепочке может быть сколько угодно звеньев, но при условии, что все они являются операциями чтения-модификации-записи, как

fetch_sub()

store()

memory_order_acquire

Хотя большая часть отношений синхронизации проистекает из семантики упорядочения доступа к памяти, применённой к операциям над атомарными переменными, существует возможность задать дополнительные ограничения на упорядочение с помощью барьеров (fence).

5.3.5. Барьеры

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

memory_order_relaxed

В следующем листинге демонстрируется добавление барьера между двумя атомарными операциями в каждом потоке из листинга 5.5.

Листинг 5.12. Ослабленные операции можно упорядочить с помощью барьеров

#include 

#include 

#include 

std::atomic x, y;

std::atomic z;

void write_x_then_y() {

 x.store(true, std::memory_order_relaxed);      ←

 std::atomic_thread_fence(std::memory_order_release);←

 y.store(true, std::memory_order_relaxed);      ←

}

void read_y_then_x() {

 while (!y.load(std::memory_order_relaxed));     ←

 std::atomic_thread_fence(std::memory_order_acquire);←

 if (x.load(std::memory_order_relaxed))        ←

  ++z;

}

int main() {

 x = false;

 y = false;

 z = 0;

 std::thread a(write_x_then_y);

 std::thread b(read_y_then_x);

 a.join();

 b.join();

 assert(z.load() != 0); ←

}

Барьер освобождения (2) синхронизируется-с барьером захвата (5), потому что операция загрузки

y

x

x

true

x

В данном случае барьер освобождения (2) оказывает такой же эффект, как если бы операция сохранения

y

memory_order_release

memory_order_relaxed

y

memory_order_acquire

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

write_x_then_y

x

y

void write_x_then_y() {

 std::atomic_thread_fence(std::memory_order_release);

 x.store(true, std::memory_order_relaxed);

 y.store(true, std::memory_order_relaxed);

}

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

x

y

Данный пример, как и почти все остальные в этой главе, целиком построен на переменных атомарных типов. Однако реальная польза от применения атомарных операций для навязывания упорядочения проистекает из того, что они могут упорядочивать неатомарные операции и тем самым предотвращать неопределенное поведение из-за гонок за данными, как мы видели в листинге 5.2.

5.3.6. Упорядочение неатомарных операций с помощью атомарных

Если заменить тип переменной

x

bool

Листинг 5.13. Принудительное упорядочение неатомарных операций

#include 

#include 

#include 

bool x = false;   ←┐

std::atomic y;│

std::atomic z; │

void write_x_then_y() {

 x = true;      ←┘

 std::atomic_thread_fence(std::memory_order_release);

 y.store(true, std::memory_order_relaxed);←┐

}                     

void read_y_then_x()             

{                       │

 while (!y.load(std::memory_order_relaxed));←┘

 std::atomic_thread_fence(std::memory_order_acquire);

 if (x) ←┐

  ++z;  

}

int main() {

 x = false;

 y = false;

 z = 0;

 std::thread a(write_x_then_y);

 std::thread b(read_y_then_x);

 a.join();

 b.join();       

 assert(z.load() != 0);←┘

}

Барьеры по-прежнему обеспечивают упорядочение сохранения

x

y

y

x

x

x

y

y

y

x

y

x

Но не только с помощью барьеров можно упорядочить неатомарные операции. Эффект упорядочения мы наблюдали также в листинге 5.10, где пара

memory_order_release

memory_order_consume

memory_order_relaxed

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

x

В функции

lock()

flag.test_and_set()

std::memory_order_acquire

unlock()

flag.clear()

std::memory_order_release

lock()

test_and_set()

false

lock()

test_and_set()

unlock()

flag.clear()

std::memory_order_release

Это приводит к синхронизации-с (см. раздел 5.3.1) последующим обращением к

flag.test_and_set()

lock()

std::memory_order_acquire

unlock()

unlock()

lock()

unlock()

lock()

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

lock()

unlock()