Алгоритмы без использования блокировок: однократная инициализация

Частным случаем singleton-конструктора является обычная «ленивая» инициализация множества переменных. В однопоточном приложении вы можете написать примерно такой код:

// предположим, что все допустимые значения переменных a и b удовлетворяют условиям: // a ≥ 0 и b ≥ a. Таким образом, -1 не является допустимым значением // и мы будем использовать его для того, чтобы обозначить, // что эта переменная еще не проинициализирована. int a = -1, b = -1; void LazyInitialize() {   if (a != -1) return; // уже проинициализировано   a = calculate_nominal_a();   b = calculate_nominal_b();   // Приведение значений переменных в соответствие с нашими ограничениями.   a = max(0, a);   b = max(a, b); }

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

Поток 1	Поток 2
if (a != -1) [условие не выполняется]a = calculate_nominal_a(); // возвращает 2
	if (a != -1) return; // преждевременный возврат!

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

«Ага», — скажете вы, — «это несложно исправить. Я просто буду использовать переменную b вместо a для того, чтобы обозначить, что инициализация уже завершена».

void LazyInitialize() {   if (b != -1) return; // уже проинициализировано (проверяем b, а не a)   a = calculate_nominal_a();   b = calculate_nominal_b();   // Приведение значений переменных в соответствие с нашими ограничениями.   a = max(0, a);   b = max(a, b); }

Это все равно не исключает состояния гонки:

Поток 1	Поток 2
if (b != -1) [условие не выполняется]a = calculate_nominal_a(); // возвращает 2b = calculate_nominal_b(); // возвращает 1
	if (b != -1) return; // преждевременный возврат!

«И это я могу исправить. Я просто посчитаю значения a и b и сохраню их в локальных переменных, а глобальные переменные буду обновлять только после того, как будут посчитаны окончательные значения. В этом случае второй поток не увидит частично вычисленные значения».

void LazyInitialize() {   if (b != -1) return; // уже проинициализировано    // производим все вычисления и сохраняем их сначала в локальных переменных   int temp_a = calculate_nominal_a();   int temp_b = calculate_nominal_b();   // Приведение значений переменных в соответствие с нашими ограничениями.   temp_a = max(0, temp_a);   temp_b = max(temp_a, temp_b);    // делаем временные значения постоянными<br> a = temp_a;<br> b = temp_b; }

Почти правильно, но все равно возникает состояние гонки:

Поток 1	Поток 2
if (b != -1) [условие не выполняется]temp_a = calculate_nominal_a(); // возвращает 2temp_b = calculate_nominal_b(); // возвращает 1temp_a = max(0, temp_a); // temp_a = 2temp_b = max(temp_a, temp_b); // temp_b = 2a = temp_a; // инициирована операция сохранения значения в памятьb = temp_b; // инициирована операция сохранения значения в памятьзавершено сохранение в память переменной b
	if (b != -1) return; // преждевременный возврат!
завершено сохранение в память переменной a

Нет никаких гарантий того, что результат операции присвоения b = 2 станет видимым для остальных процессоров строго после операции присвоения a = 2. Даже несмотря на то, что операции сохранения значений инициируются в нужном нам порядке, контроллер памяти может выполнить эти операции в обратном порядке, что приведет к тому, что Поток 2 увидит значения a = -1 и b = 2.

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

void LazyInitialize() {   if (b != -1) return; // уже проинициализировано   // производим все вычисления и сохраняем их сначала в локальных переменных   int temp_a = calculate_nominal_a();   int temp_b = calculate_nominal_b();   // Приведение значений переменных в соответствие с нашими ограничениями.   temp_a = max(0, temp_a);   temp_b = max(temp_a, temp_b);   // делаем временные значения постоянными   a = temp_a;    // поскольку мы используем переменную b в качестве индикатора<br> // завершения инициализации, мы должны присваивать ей значение в последнюю очередь<br> // и использовать при этом семантику освобождения.<br> InterlockedCompareExchangeRelease(<br> reinterpret_cast<LONG*>&b, temp_b, -1); }

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

Следовательно, общий шаблон будет следующим:

void LazyInitializePattern() {   if (глобальная_сигнальная_переменная != маркерное_значение) return;   ... выполнение вычислений и запись результатов в локальные переменные ...   глобальная_переменная1 = временная_переменная1;   глобальная_переменная2 = временная_переменная2;   ...   глобальная_переменнаяN = временная_переменнаяN;   // и в последнюю очередь — публикация сигнальной переменной   // с использованием семантики освобождения для гарантии того,   // что значения предыдущих переменных также будут видны   InterlockedCompareExchangeRelease(         reinterpret_cast<LONG*>&глобальная_сигнальная_переменная,         временная_сигнальная_переменная, маркерное_значение); }

Если это чересчур для вас (и учитывая то, что я в первый раз напортачил с коварной двойной проверкой-блокировкой, это чересчур и для меня), вы можете положиться на команду разработки ядра Windows, поручив ей думать обо всех этих деталях, и вместо написания этого кода вручную использовать готовые функции для однократной инициализации, инкапсулирующие всю эту логику. (Мой приятель Дорон (Doron) некоторое время назад обнародовал информацию об этих функциях однократной инициализации). Четвертая версия .NET Framework содержит соответствующую функциональность в классе Lazy<T>.

Упражнение: какие скрытые предположения были сделаны относительно функций calculate_nominal_a и calculate_nominal_b?

Упражнение: какими будут последствия, если мы будем использовать функцию InterlockedExchange вместо функции InterlockedCompareExchangeRelease?

Упражнение: действительно ли нужны переменные temp_a и temp_b в окончательной версии функции LazyInitialize или это просто пережитки предыдущих попыток избавиться от состояния гонки?

Упражнение: какие изменения нужно внести (если они вообще требуются) в случае, когда глобальные переменные являются указателями? А если — переменными для чисел с плавающей точкой?

Обновление: посмотрите переписку между пользователями Niall и Anon относительно необходимости семантики захвата (acquire semantics) при первоначальном чтении значений из переменных.