Параллельное программирование на С++ в действии — страница 18 из 53

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

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

#include 
#include 
#include 

std::vector data;
std::atomic data_ready(false);

void reader_thread() {

 while (!data_ready.load()) {            ←(1)

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

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

}

void writer_thread() {

 data.push_back(42); ←(3) data_ready = true;  ←(4)

}

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

Требуемое упорядочение обеспечивают операции с переменной data_ready типа std::atomic и делается это благодаря отношениям происходит-раньше и синхронизируется-с, заложенным в модель памяти. Запись данных (3) происходит-раньше записи флага data_ready(4), а чтение флага (1) происходит-раньше чтения данных (2). Когда прочитанное значение data_ready(1) равно true, операция записи синхронизируется-с этой операцией чтения, что приводит к порождению отношения происходит-раньше. Поскольку отношение происходит-раньше транзитивно, то запись данных (3) происходит-раньше записи флага (4), которая происходит-раньше чтения значения true из этого флага (1), которое в свою очередь происходит-раньше чтения данных (2). И таким образом мы получаем принудительное упорядочение: запись данных происходит-раньше чтения данных, и программа работает правильно. На рис. 5.2 изображены важные отношения происходит-раньше в обоих потоках. Я включил две итерации цикла while в потоке-читателе.

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

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

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

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

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

Идея такова: подходящим образом помеченная атомарная операция записи W над переменной x синхронизируется-с подходящим образом помеченной атомарной операцией чтения над переменной x, которая читает значение, сохраненное либо данной операцией записи (W), либо следующей за ней атомарной операцией записи над x в том же потоке, который выполнил первоначальную операцию W, либо последовательностью атомарных операций чтения-модификации-записи над x (например, fetch_add() или compare_exchange_weak()) в любом потоке, при условии, что значение, прочитанное первым потоком в этой последовательности, является значением, записанным операцией W (см. раздел 5.3.4).

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

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

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

Отношение происходит-раньше — основной строительный блок механизма упорядочения операций в программе. Оно определяет, какие операции видят последствия других операций и каких именно. В однопоточной программе всё просто: если в последовательности выполняемых операций одна стоит раньше другой, то она и происходит-раньше. Иначе говоря, если операция А в исходном коде предшествует операции В, то А происходит-раньше В. Это мы видели в листинге 5.2: запись в переменную data(3) происходит-раньше записи в переменную data_ready(4). В общем случае между операциями, которые входят в состав одного предложения языка, нет отношения происходит-раньше, поскольку они не упорядочены. По-другому то же самое можно выразить, сказав, что порядок не определён. Мы знаем, что программа, приведённая в следующем листинге, напечатает "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());←┐Порядок обращений}                           │к 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); ←(1)

}

void write_y() {

 y.store(true, std::memory_order_seq_cst); ←(2)

}

void read_x_then_y() {

 while (!x.load(std::memory_order_seq_cst));←(3)

 if (y.load(std::memory_order_seq_cst))
  ++z;
}

void read_y_then_x() {

 while (!y.load(std::memory_order_seq_cst));←(4)

 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); ←(5)

}

Утверждение assert(5) не может сработать, потому что первым должно произойти сохранение x(1) или сохранение y(2), пусть даже точно не сказано, какое именно. Если загрузка y в функции read_x_then_y(3) возвращает false, то сохранение x должно было произойти раньше сохранения y, и в таком случае загрузка x в read_y_then_x(4) должна вернуть true, потому что наличие цикла while гарантирует, что в этой точке у равно true. Поскольку семантика memory_order_seq_cst требует полного упорядочения всех операций, помеченных признаком memory_order_seq_cst, то существует подразумеваемое отношение порядка между операцией загрузки y, которая возвращает false(3), и операцией сохранения y(1). Чтобы имело место единственное полное упорядочение в случае, когда некоторый поток сначала видит x==true, затем y==false, необходимо, чтобы при таком упорядочении сохранение x происходило раньше сохранения y.

Разумеется, поскольку всё симметрично, могло бы произойти и ровно наоборот: загрузка x(4) возвращает false, и тогда загрузка y(3) обязана вернуть true. В обоих случаях z равно 1. Может быть и так, что обе операции вернут true, и тогда z будет равно 2. Но ни в каком случае z не может оказаться равным нулю.

Операции и отношения происходит-раньше для случая, когда read_x_then_y видит, что x равно true, а y равно false, изображены на рис. 5.3. Пунктирная линия от операции загрузки 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); ←(1) y.store(true, std::memory_order_relaxed); ←(2)

}

void read_y_then_x() {

 while (!y.load(std::memory_order_relaxed));←(3) if (x.load(std::memory_order_relaxed))     ←(4)

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

}

На этот раз утверждение (5)может сработать, потому что операция загрузки x(4) может прочитать false, даже если загрузка y(3) прочитает true, а сохранение x(1) происходит-раньше сохранения y(2). x и y — разные переменные, поэтому нет никаких гарантий относительно порядка видимости результатов операций над каждой из них.

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

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

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

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

#include 
#include 
#include 

std::atomic x(0), y(0), z(0);←(1)std::atomic go(false);      ←(2)

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) ←(3) В цикле ждем сигнала

  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);←(4)

  std::this_thread::yield();
 }
}

void read_vals(read_values* values) {

 while (!go) ←(5) В цикле ждем сигнала

 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; ←┐Сигнал к началу выполнения│(6) главного цикла

 t5.join();
 t4.join();
 t3.join();
 t2.join();
 t1.join();

 print(values1);←┐

 print(values2); │Печатаем получившиеся print(values3);(7) значения

 print(values4);
 print(values5);
}

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

Атомарная переменная go(2) служит для того, чтобы все потоки начали работу по возможности одновременно. Запуск потока — накладная операция и, не будь явной задержки, первый поток мог бы завершиться еще до того, как последний зачал работать. Каждый поток ждет, пока переменная go станет равна true, и только потом входит в главный цикл (3), (5), а переменная go устанавливается в true только после запуска всех потоков (6).

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

(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 увеличиваются на 1 в каждой тройке, во втором наборе на 1 увеличиваются значения 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.4, переработанная под семантику захвата-освобождения вместо семантики последовательной согласованности.

Листинг 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)) ←(1)

  ++z;
}

void read_y_then_x() {
 while (!y.load(std::memory_order_acquire));

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

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

}

В данном случае утверждение (3)может сработать (как и в случае ослабленного упорядочения), потому что обе операции загрузки — x(2) и y(1) могут прочитать значение 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);   ←(1) y.store(true,std::memory_order_release);   ←(2)

}

void read_y_then_x() {

 while (!y.load(std::memory_order_acquire));←(3) if (x.load(std::memory_order_relaxed))     ←(4)

  ++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); ←(5)

}

В конечном итоге операция загрузки y(3) увидит значение true, записанное операцией сохранения (2). Поскольку сохранение производится в режиме memory_order_release, а загрузка — в режиме memory_order_acquire, то сохранение синхронизируется-с загрузкой. Сохранение x(1) происходит-раньше сохранения y(2), потому что обе операции выполняются в одном потоке. Поскольку сохранение y синхронизируется-с загрузкой y, то сохранение x также происходит-раньше загрузки y, и, следовательно, происходит-раньше загрузки x(4). Таким образом, операция загрузки xдолжна прочитать true, и, значит, утверждение (5)не может сработать. Если бы загрузка y не повторялась в цикле while, то высказанное утверждение могло бы оказаться неверным; операция загрузки y могла бы прочитать false, и тогда не было бы никаких ограничений на значение, прочитанное из x. Для обеспечения синхронизации операции захвата и освобождения должны употребляться парами. Значение, сохраненное операций восстановления, должно быть видно операции захвата, иначе ни та, ни другая не возымеют эффекта. Если бы сохранение в предложении (2) или загрузка в предложении (3) выполнялись в ослабленной операции, то обращения к x не были бы упорядочены, и, значит, нельзя было бы гарантировать, что операция загрузки в предложении (4) прочитает значение true, поэтому утверждение assert могло бы сработать.

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

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

Как эта метафора моделирует семантику захвата-освобождения? Взгляните на наш пример — и поймете. В самом начале поток а вызывает функцию write_x_then_y и говорит человеку в боксе x: «Запиши true, как часть пакета 1 от потока а». Затем поток а говорит человеку в боксе y: «Запиши true, как последнюю операцию записи в пакете 1 от потока а». Тем временем поток b выполняет функцию read_y_then_x. Он раз за разом просит человека в боксе y сообщить значение вместе с информацией о пакете, пока не услышит в ответ «true». Возможно, спросить придется много раз, но в конце концов человек обязательно ответит «true». Однако человек в боксе y говорит не просто «true», а еще добавляет: «Это последняя операция записи в пакете 1 от потока а».

Далее поток b просит человека в боксе x назвать значение, но на это раз говорит: «Сообщи мне значение и, кстати, я знаю о пакете 1 от потока а». Человек в боксе x ищет в своем списке последнее упоминание о пакете 1 от потока а. Он находит единственное значение 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);  (1)sync1

}

void thread_2()                                 (2)Цикл до{                                                │установки while (!sync1.load(std::memory_order_acquire));←┘sync1 sync2.store(true, std::memory_order_release); ←┐Установить}                                              (3) sync2
void thread_3()                                 (4)Цикл до{                                                │установки while (!sync2.load(std::memory_order_acquire));←┘sync2

 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(2) и sync2(3), этого достаточно для синхронизации между thread_1 и thread_3 и, стало быть, гарантии несрабатывания утверждений assert. Прежде всего, операции сохранения в элементы массива data в потоке thread_1 происходят-раньше сохранения sync1(1), потому что они связаны отношением расположено-перед в одном потоке. Поскольку операция загрузки sync1(2) находится внутри цикла while, она в конце концов увидит значение, сохраненное в thread_1 и, значит, образует вторую половину пары освобождение-захват. Поэтому сохранение sync1 происходит-раньше последней загрузки sync1 в цикле while. Эта операция загрузки расположена-перед (и, значит, происходит-раньше) операцией сохранения sync2(3), которая образует пару освобождение-захват вместе с последней операцией загрузки в цикле while в потоке thread_3(4). Таким образом, сохранение sync2(3) происходит-раньше загрузки (4), которая происходит-раньше загрузок data. В силу транзитивности отношения происходит-раньше всю эту цепочку можно соединить: операции сохранения data происходят-раньше операций сохранения sync1(1), которые происходят-раньше загрузки sync1(2), которая происходит-раньше сохранения sync2(3), которая происходит-раньше загрузки sync2(4), которая происходит-раньше загрузок 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 особая: она связана с зависимостями по данным и позволяет учесть соответствующие нюансы в отношении межпоточно происходит-раньше, о котором шла речь в разделе 5.3.2.

С зависимостями по данным связаны два новых отношения: предшествует-по-зависимости (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);←(1) p.store(x, std::memory_order_release); ←(2)

}

void use_x() {
 X* x;

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

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

 assert(x->i == 42);                             ←(4) assert(x->s =="hello");                         ←(5) assert(a.load(std::memory_order_relaxed) == 99);←(6)

}

int main() {
 std::thread t1(create_x);
 std::thread t2(use_x);
 t1.join();
 t2.join();
}

Хотя сохранение а(1) расположено перед сохранением p(2) и сохранение p помечено признаком memory_order_release, но загрузка p(3) помечена признаком memory_order_consume. Это означает, что сохранение p происходит-раньше только тех выражений, которые зависят от значения, загруженного из p. Поэтому утверждения о членах-данных структуры x(4), (5) гарантированно не сработают, так как загрузка p переносит-зависимость-в эти выражения посредством переменной x. С другой стороны, утверждение о значении а(6) может как сработать, так и не сработать; эта операция не зависит от значения, загруженного из p, поэтому нет никаких гарантий о прочитанном значении. Это ясно следует из того, что она помечена признаком memory_order_relaxed.

Иногда нам не нужны издержки, которыми сопровождается перенос зависимости. Мы хотим, чтобы компилятор мог кэшировать значения в регистрах и изменять порядок операций во имя оптимизации кода, а не волновался по поводу зависимостей. В таких случаях можно воспользоваться шаблоном функции std::kill_dependency() для явного разрыва цепочки зависимостей. Эта функция просто копирует переданный ей аргумент в возвращаемое значение, но попутно разрывает цепочку зависимостей. Например, если имеется глобальный массив с доступом только для чтения, и вы используете семантику std::memory_order_consume при чтении какого-то элемента этого массива из другого потока, то с помощью 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);

 } ←(1) Начальное сохранение

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

void consume_queue_items() {

 while (true) { ←(2) Операция ЧМЗ

 int item_index;
 if (
  (item_index =
   count.fetch_sub(1, std::memory_order_acquire)) <= 0) {

   wait_for_more_items();←┐Ждем дополнительных   continue;             (3) элементов

 }

 process(queue_data[item_index-1]);←┐Чтение из queue_data}                                  (4) безопасно

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)(1), чтобы другие потоки узнали о готовности данных. Потоки- потребители, читающие данные из очереди, могли бы затем вызвать count.fetch_sub(1, memory_order_acquire)(2), чтобы проверить, есть ли элементы в очереди перед тем, как фактически читать из разделяемого буфера (4). Если счетчик count стал равен 0, то больше элементов нет, и поток должен ждать (3).

Если поток-потребитель всего один, то всё хорошо; fetch_sub() — это операция чтения с семантикой memory_order_acquire, а операция сохранения была помечена признаком memory_order_release, поэтому сохранение синхронизируется-с загрузкой, и поток может читать данные из буфера. Но если читают два потока, то второй вызов fetch_sub() увидит значение, записанное при первом вызове, а не то, которое было записано операцией store. Без правила о последовательности освобождений между вторым и первым потоком не было бы отношения происходит-раньше, поэтому было бы небезопасно читать из разделяемого буфера, если только и для первого вызова fetch_sub() тоже не задана семантика memory_order_release; однако, задав ее, мы ввели бы излишнюю синхронизацию между двумя потоками-потребителями. Без правила о последовательности освобождений или задания семантики memory_order_release для всех операций fetch_sub не было бы никакого механизма, гарантирующего, что операции сохранения в queue_data видны второму потребителю, следовательно, мы имели бы гонку за данными. К счастью, первый вызов fetch_sub() на самом деле участвует в последовательности освобождений, и вызов store() синхронизируется-с вторым вызовом fetch_sub(). Однако отношения синхронизируется-с между двумя потоками-потребителями все еще не существует. Это изображено на рис. 5.7, где пунктирные линии показывают последовательность освобождений, а сплошные — отношения происходит-раньше.

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

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

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

5.3.5. Барьеры

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

В следующем листинге демонстрируется добавление барьера между двумя атомарными операциями в каждом потоке из листинга 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);           ←(1) std::atomic_thread_fence(std::memory_order_release);←(2) y.store(true, std::memory_order_relaxed);           ←(3)

}

void read_y_then_x() {

 while (!y.load(std::memory_order_relaxed));         ←(4) std::atomic_thread_fence(std::memory_order_acquire);←(5) if (x.load(std::memory_order_relaxed))              ←(6)

  ++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); ←(7)

}

Барьер освобождения (2) синхронизируется-с барьером захвата (5), потому что операция загрузки y в точке (4) читает значение, сохраненное в точке (3). Это означает, что сохранение x(1) происходит-раньше загрузки x(6), поэтому прочитанное значение должно быть равно true, и утверждение (7) не сработает. Здесь мы наблюдаем разительное отличие от исходного случая без барьеров, когда сохранение и загрузка x не были упорядочены, и утверждение могло сработать. Отметим, что оба барьера обязательны: чтобы получить отношение синхронизируется-с необходимо освобождение в одном потоке и захват в другом.

В данном случае барьер освобождения (2) оказывает такой же эффект, как если бы операция сохранения y(3) была помечена признаком memory_order_release, а не memory_order_relaxed. Аналогично эффект от барьера захвата (5) такой же, как если бы операция загрузки y(4) была помечена признаком memory_order_acquire. Это общее свойство всех барьеров: если операция захвата видит результат сохранения, имевшего место после барьера освобождения, то барьер синхронизируется-с этой операцией захвата. Если же операция загрузки, имевшая место до барьера захвата, видит результат операции освобождения, то операция освобождения синхронизируется-с барьером захвата. Разумеется, можно поставить барьеры по обе стороны, как в примере выше, и в таком случае если загрузка, которая имела место до барьера захвата, видит значение, записанное операцией сохранения, имевшей место после барьера освобождения, то барьер освобождения синхронизируется-с барьером захвата.

Хотя барьерная синхронизация зависит от значений, прочитанных или записанных операциями до и после барьеров, важно отметить, что точкой синхронизации является сам барьер. Если взять функцию write_x_then_y из листинга 5.12 и перенести запись в x после барьера, как показано ниже, то уже не гарантируется, что условие в утверждение будет истинным, несмотря на то что запись в 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 в листинге 5.12 обычным неатомарным типом bool (как в листинге ниже), то гарантируется точно такое же поведение, как и раньше.

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

#include 
#include 
#include 

bool x = false;    ←┐Теперь x — простаяstd::atomic y;│неатомарнаяstd::atomic z; │переменнаяvoid write_x_then_y() {(1) Сохранение x x = true;            ←┘перед барьером

 std::atomic_thread_fence(std::memory_order_release);

 y.store(true, std::memory_order_relaxed);←┐Сохранение y}                                         (2) после барьера
void read_y_then_x()                        (3) Ждем, пока не{                                            │увидим значение, while (!y.load(std::memory_order_relaxed));←┘записанное в 2

 std::atomic_thread_fence(std::memory_order_acquire);

 if (x) ←┐Здесь будет прочитано  ++z;   (4) значение, записанное в 1

}

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();             (5) Это утверждение assert(z.load() != 0);←┘не сработает

}

Барьеры по-прежнему обеспечивают упорядочение сохранения x(1) и y(2) и загрузки y(3) и x(4), и, как и раньше, существует отношение происходит-раньше между сохранением x и загрузкой x, поэтому утверждение (5) не сработает. Сохранение y(2) и загрузка y(3) тем не менее должны быть атомарными, иначе возникла бы гонка за y, но барьеры упорядочивают операции над x после того, как поток-читатель увидел сохраненное значение y. Такое принудительное упорядочение означает, что гонки за x нет, хотя ее значение модифицируется в одном потоке, а читается в другом.

Но не только с помощью барьеров можно упорядочить неатомарные операции. Эффект упорядочения мы наблюдали также в листинге 5.10, где пара memory_order_release / memory_order_consume упорядочивала неатомарные операции доступа к динамически выделенному объекту. Многие примеры из этой главы можно было бы переписать, заменив некоторые операции с семантикой memory_order_relaxed простыми неатомарными операциями.

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

В функции 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() — это операция захвата над некоторой внутренней ячейкой памяти, a unlock() — операция освобождения над той же ячейкой памяти.

5.4. Резюме