Преимущества безблокировочного алгоритма — не только и не столько в производительности

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

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

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

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

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

CRITICAL_SECTION g_csSingletonX;
X *g_px = NULL;

X *GetSingletonX()
{
    EnterCriticalSection(&g_csSingletonX);
    if (g_px == NULL)
    {
        g_px = new(nothrow) X();
    }
    LeaveCriticalSection(&g_csSingletonX);
    return g_px;
}

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

В ходе построения иерархии блокировок может оказаться, что некоторые из блокировок невозможно всегда захватывать в одном порядке, и поэтому их необходимо объединить. Синхронизация становится более грубой. Например, может оказаться, что g_csSingletonX необходимо объединить с блокировками всех конструкторов синглтонов, а также с блокировками всех методов класса X.

CRITICAL_SECTION g_csCommon;

X *GetSingletonX()
{
    EnterCriticalSection(&g_csCommon);
    if (g_px == NULL)
    {
        g_px = new(nothrow) X();
    }
    LeaveCriticalSection(&g_csCommon);
    return g_px;
}

Y *GetSingletonY()
{
    EnterCriticalSection(&g_csCommon);
    if (g_py == NULL)
    {
        g_py = new(nothrow) Y();
    }
    LeaveCriticalSection(&g_csCommon);
    return g_py;
}

void X::DoSomething()
{
    EnterCriticalSection(&g_csCommon);
    .. something ..
    LeaveCriticalSection(&g_csCommon);
}

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

Существенное преимущество безблокировочного алгоритма — раз у вас нет блокировок, то не может быть дедлоков; иерархия становится не нужна. (Если только вы не строите из безблокировочных операций «неблокирующую блокировку», как мы в примере с ненастойчивым кэшем). Другая приятная особенность безблокировочности — что раз нет блокировок, то они не останутся в «бесхозном» состоянии при аварийном завершении потока, захватившего блокировку; вам не придётся ломать голову, как продолжить корректную работу в случае WAIT_ABANDONED. Защищаемые данные всё время остаются корректны, и атомарно переходят из одного своего корректного состояния в следующее.

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

---

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

CRITICAL_SECTION g_cs;
GORILLADATA g_data;

void PokeGorilla(double intensity)
{
  EnterCriticalSection(&g_cs);
  DeformGorilla(intensity, &g_data);
  Reticulate(&g_data.spline);
  int stress = CalculateTension(&g_data.spline);
  if (stress < 25)      g_data.mood = RELAXED;
  else if (stress < 50) g_data.mood = ANNOYED;
  else                  g_data.mood = ANGRY;
  DeleteObject(g_data.hbmGorilla);
  g_data.hbmGorilla = RenderGorilla(&g_data);
  LeaveCriticalSection(&g_cs);
}

— есть ряд спорных мест. Прежде всего, соблюдается ли иерархия блокировок? Например, функции Reticulate() может потребоваться блокировка, защищающая геометрические операции; и может оказаться, что в соответствии с иерархией эту блокировку нужно захватывать перед g_cs.

Если за g_cs соревнуются много потоков, то нам стоило бы сократить время, в течение которого PokeGorilla() удерживает блокировку. Вероятно, RenderGorilla() — сложная и медленная операция. (Сами ведь знаете, как тяжело изобразить реалистичный мех.) Тогда во время вызова RenderGorilla() блокировка g_cs удерживается зря.

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

void PokeGorilla(double intensity)
{
  // Создать локальную копию
  EnterCriticalSection(&g_cs);
  GORILLADATA data = g_data;
  LeaveCriticalSection(&g_cs);

  // Произвести нужные действия над копией
  DeformGorilla(intensity, &data);
  Reticulate(&data.spline);
  int stress = CalculateTension(&data.spline);
  if (stress < 25)      data.mood = RELAXED;
  else if (stress < 50) data.mood = ANNOYED;
  else                  data.mood = ANGRY;
  data.hbmGorilla = RenderGorilla(&data);

  // Записать
  EnterCriticalSection(&g_cs);
  HBITMAP hbmToDelete = g_data.hbmGorilla;
  g_data = data;
  LeaveCriticalSection(&g_cs);
  DeleteObject(hbmToDelete);
}

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

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

Тогда мы возвращаемся к модели «сделай, запиши,(попытайся снова)» со счётчиком версий:

LONG g_lCounter;

void PokeGorilla(double intensity)
{
  BOOL fSuccess;

  do {
    // Создать локальную копию
    EnterCriticalSection(&g_cs);
    GORILLADATA data = g_data;
    LONG lCounter = g_lCounter;
    LeaveCriticalSection(&g_cs);

    // Произвести нужные действия над копией
    DeformGorilla(intensity, &data);
    Reticulate(&data.spline);
    int stress = CalculateTension(&data.spline);
    if (stress < 25)      data.mood = RELAXED;
    else if (stress < 50) data.mood = ANNOYED;
    else                  data.mood = ANGRY;
    data.hbmGorilla = RenderGorilla(&data);

    // Записать
    EnterCriticalSection(&g_cs);
    HBITMAP hbmToDelete;
    if (lCounter == g_lCounter)
    {
      hbmToDelete = g_data.hbmGorilla;
      g_data = data;
      g_lCounter++;
      fSuccess = TRUE;
    } else {
      hbmToDelete = data.hbmGorilla;
      fSuccess = FALSE;
    }
    LeaveCriticalSection(&g_cs);
    DeleteObject(hbmToDelete);
  } while (!fSuccess);
}

Кроме привычных горилльих данных, мы храним номер версии и увеличиваем его при каждом тычке. По-настоящему, этот номер лучше было бы хранить в самой структуре GORILLADATA. (Нет, по-настоящему лучше было бы не тыкать гориллу!) В безблокировочном алгоритме мы бы проверяли значение номера версии операцией InterlockedCompareExchangeRelease; но структуру GORILLADATA невозможно обновить атомарно, так что мы для её проверки и одновременного обновления пользуемся критической секцией. Тем не менее, модель остаётся та же, что и прежде: если гориллу ткнули за нашей спиной, мы вынуждены выкинуть все полученные нами результаты, и начать вычисления по-новой, чтоб отразить в окончательном результате оба тычка.