Как стать автором
Обновить

Потоко-безопасная ленивая инициализация в C++

Время на прочтение 9 мин
Количество просмотров 13K
Автор оригинала: Raymond Chen
Реймонд Чен написал занятную серию блогпостов о беззамочной синхронизации. Мне бы хотелось опубликовать эти заметки и для хаброчитателей. Данный пост — введение в серию, скомпилированное из трёх старых постов Чена.
  1. Ленивая инициализация встроенными средствами C++
  2. Беззамочная синхронизация
  3. Беззамочная потоко-безопасная ленивая инициализация


Ленивая инициализация встроенными средствами C++


Инициализация статических локальных переменных в C++ непотокобезопасна, причём намеренно!

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

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

int ComputeSomething()
{
  static int cachedResult = ComputeSomethingSlowly();
  return cachedResult;
}

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

Всё дело в том, что компилятор превращает инициализацию статических локальных переменных в нечто такое:
int ComputeSomething()
{
  static bool cachedResult_computed = false;
  static int cachedResult;
  if (!cachedResult_computed) {
    cachedResult_computed = true;
    cachedResult = ComputeSomethingSlowly();
  }

  return cachedResult;
}

Теперь рейс-кондишн виден невооружённым взглядом. Представьте себе, что два потока вызвали ComputeSomething() одновременно. Первый поток успевает выполнить лишь cachedResult_computed = true, прежде чем система переключается на второй поток. Теперь второй поток видит установленный флаг cachedResult_computed, пропускает инициализацию переменной, и возьмёт её неинициализированное значение.

И это не баг в компиляторе — так было предписано стандартом C++. (Потом, в редакции TC1, требование потоконебезопасности удалили, оставив «undefined behavior» в случае одновременного выполнения инициализации.)

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

class Something { ... };
int ComputeSomething()
{
  static Something s;
  return s.ComputeIt();
}

Такой код развернётся в

class Something { ... };
int ComputeSomething()
{
  static bool s_constructed = false;
  static uninitialized Something s;
  if (!s_constructed) {
    s_constructed = true;
    new(&s) Something; // создать s
    atexit(DestructS);
  }

  return s.ComputeIt();
}
// Уничтожить s при завершении процесса
void DestructS()
{
ComputeSomething::s.~Something();
}


Теперь рейс-кондишнов возможно несколько. Как и раньше, один из потоков может опередить другой, и схватить значение s до её инициализации. Но вдобавок к тому, если первый поток успел проверить значение s_constructed, но не успел установить его в true, то объект s дважды создастся и дважды уничтожится. (Вернее, один объект «утечёт», а второй уничтожится дважды.) Не шуточки!

Но и это ещё не всё. Глядите, что происходит, если инициализируемых статических локальных переменных будет две:
int ComputeSomething()
{
  static Something s(0);
  static Something t(1);
  return s.ComputeIt() + t.ComputeIt();
}

Компилятор, чтобы сэкономить память, сохранит оба флага в одной переменной:
class Something { ... };
int ComputeSomething()
{
  static char constructed = 0;
  static uninitialized Something s;
  if (!(constructed & 1)) {
    constructed |= 1;
    new(&s) Something; // создать s
    atexit(DestructS);
  }
  static uninitialized Something t;
  if (!(constructed & 2)) {
    constructed |= 2;
    new(&t) Something; // создать t
    atexit(DestructT);
  }

  return s.ComputeIt() + t.ComputeIt();
}

Отлично, теперь у нас несколько потоков выполняют над общей переменной логические операции безо всякой синхронизации. Посмотрим, что произойдёт, если один поток попытается выполнить constructed |= 1 одновременно с тем, как другой поток выполняет constructed |= 2.

В процессорах x86/x64 есть команды, работающие с операндом в памяти непосредственно. Компилятор сгенерирует машинный код
  or constructed, 1
...
  or constructed, 2

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

В процессорах ia64/alpha логические команды работают только с регистрами, поэтому такое может случиться даже на однопроцессорной машине. Компилятор разбивает каждую из операций |= на три машинных команды:
  ldl t1,0(a0)     ; чтение
  addl t1,1,t1     ; изменение
  stl t1,1,0(a0)   ; запись

Если выполнение потока прерывается между чтением старого значения и записью нового, то новое значение может «затереть» изменения, внесённые из других потоков.

Возможно, стоит защитить инициализацию статических переменных критической секцией:
int ComputeSomething()
{
EnterCriticalSection(...);
static int cachedResult = ComputeSomethingSlowly();
LeaveCriticalSection(...);
return cachedResult;
}

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

Но что, если ComputeSomething() вызывается снова из того же самого потока? («We've traced the call; it's coming from inside the thread!») Например, если ComputeSomethingSlowly() явно или неявно сама вызывает ComputeSomething(). (Звучит надуманно? А представьте себе, что ComputeSomethingSlowly() показывает диалоговое окно, и цикл обработки сообщений через DispatchMessage() вызывает обработчик какого-нибудь события, и этот обработчик сам использует ComputeSomething())
В таком случае вызывающий поток будет уже владеть критической секцией, войдёт внутрь безо всяких затруднений, и схватит-таки неинициализированное значение.

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

Беззамочная синхронизация


Операции InterlockedXxx — эффективная реализация атомарных операций над 32-битными значениями и указателями. Но атомарность сама по себе не гарантирует потоко-безопасность.

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

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

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

// Неверно!
LONG InterlockedMultiply(volatile LONG *plMultiplicand, LONG lMultiplier)
{
  EnterCriticalSection(&SomeCriticalSection);
  LONG lResult = *plMultiplicand *= lMultiplier;
  LeaveCriticalSection(&SomeCriticalSection);
  return lResult;
}

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

int x = 2;
Thread1()
{
  InterlockedIncrement(&x);
}

Thread2()
{
  InterlockedMultiply(&x, 5);
}

Если умножение атомарное, то в итоге двух операций может получиться результат x = 15 либо x = 11, в зависимости от того, которая из операций успеет выполниться раньше. Но наше «атомарное» умножение позволяет получить и другие значения, довольно неожиданные:

Поток 1 Поток 2
исходно: x = 2
InterlockedMultiply(&x, 5)
EnterCriticalSection
прочитать x (прочитано: 2)
InterlockedIncrement(&x);
        теперь x = 3
умножить на 5 (результат: 10)
записать x (записано: 10)
LeaveCriticalSection
результат: x = 10
Не такое уж оно и атомарное! Как же его исправить?

Если выполняемая операция — «чистая функция», не зависящая от глобальных данных, то для её атомарной реализации можно задействовать InterlockedCompareExchange:

LONG InterlockedMultiply(volatile LONG *plMultiplicand, LONG lMultiplier)
{
  LONG lOriginal, lResult;
  do {
    lOriginal = *plMultiplicand;
    lResult = lOriginal * lMultiplier;
  } while (InterlockedCompareExchange(plMultiplicand,
                                      lResult, lOriginal) != lOriginal);
  return lResult;
}

Операция состоит из трёх шагов.

Первый — «захват» значений параметров: lOriginal = *plMultiplicand;

Второй — выполнение операции над захваченными значениями: lResult = lOriginal * lMultiplier;

Третий — сохранение результата только в том случае, если значения параметров не изменились: InterlockedCompareExchange(plMultiplicand, lResult, lOriginal)

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

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

Не упускайте из виду, что операция не должна пользоваться никакими другими данными! InterlockedCompareExchange неспособна проверить, не изменились ли значения глобальных переменных, которыми пользовалась операция. Иначе возможна ситуация, известная как «проблема ABA»: при первом выполнении операции значение параметра было A; затем, незаметно для выполняющегося потока, его значение изменилось на B, и потом снова на A. InterlockedCompareExchange не заметит, что что-то поменялось, и сохранит вычисленное в первый раз значение. Если заодно с параметром изменились другие влиявшие на результат данные, то записанный результат окажется неверным.



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

Беззамочная потоко-безопасная ленивая инициализация


Допустим, мы решили лениво инициализировать пару переменных. В однопоточной программе это не вызывает сложностей:

// Возможные значения для 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);
}

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

«А, ну это легко исправить! Чтобы узнать, выполнена ли инициализация, будем проверять не a, а b

void LazyInitialize()
{
if (b != -1) return; // уже инициализировано

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(); // возвращает 2
b = calculate_nominal_b(); // возвращает 1
if (b != -1) return; // слишком рано!
Второй поток возьмёт значения a и b, не соответствующие наложенным ограничениям.

«Можно защититься и от этого! Я буду вычислять значения 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);

// записываем окончательные значения в глобальные переменные
a = temp_a;
b = temp_b;

}

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

Запись b в память необходимо оформить как операцию Release; тогда все предыдущие операции вынуждены отразиться в памяти до того, как другие процессоры увидят новое значение 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 как признак завершённой
// инициализации, записываем её в последнюю очередь,
// причём операцией Release
InterlockedCompareExchangeRelease(
    reinterpret_cast<LONG*>&b, temp_b, -1);

}

Получившийся код похож на беззамочную атомарную операцию, только без входных параметров: сначала все вычисления выполняются в локальных переменных, и затем записываются в память одной операцией InterlockedCompareExchangeRelease. В предположении, что calculate_nominal_a() и calculate_nominal_b() возвращают всегда одни и те же значения, нам не нужно выполнять операцию заново в случае неудачи: если переменные инициализированы не нами, значит, другой поток просто уже сделал за нас нашу работу. (Обратите внимание: в случае неудачи InterlockedCompareExchangeRelease, переменная a будет всё равно перезаписана нашим потоком!)

Напоследок, Реймонд предложил загадку: можно ли обойтись без переменной temp_a? Ведь в любом случае значение a используется лишь после того, как поток убедился, что инициализация завершена.
Теги:
Хабы:
+43
Комментарии 21
Комментарии Комментарии 21

Публикации

Истории

Ближайшие события

Московский туристический хакатон
Дата 23 марта – 7 апреля
Место
Москва Онлайн
Геймтон «DatsEdenSpace» от DatsTeam
Дата 5 – 6 апреля
Время 17:00 – 20:00
Место
Онлайн