Одновременность: когда два потока делят данные

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

Начнём с самого маленького примера. Два потока, каждый миллион раз увеличивает один общий счётчик. Любой программист скажет, что ответ 2000000. Запустите и прочитайте число.

/* counter.c */
#include <pthread.h>
#include <stdio.h>

static long counter = 0;

static void *worker(void *arg) {
  (void)arg;
  for (long i = 0; i < 1000000; i++) {
    counter = counter + 1;
  }
  return NULL;
}

int main(void) {
  pthread_t a, b;
  pthread_create(&a, NULL, worker, NULL);
  pthread_create(&b, NULL, worker, NULL);
  pthread_join(a, NULL);
  pthread_join(b, NULL);
  printf("%ld\n", counter);
  return 0;
}

/* $ gcc -O2 -pthread counter.c -o counter && ./counter
 * 2000000   <- never guaranteed
 * 1431927   <- typical instead
 */Два потока, один общий счётчик, ни одной блокировки. Компилируется через gcc -O2 -pthread. Напечатанное значение меняется от запуска к запуску.

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

counter = 0

T1  r1 <- counter     r1 = 3417
T2  r2 <- counter     r2 = 3417
T1  r1 <- r1 + 1      r1 = 3418
T2  r2 <- r2 + 1      r2 = 3418
T1  counter <- r1     counter = 3418
T2  counter <- r2     counter = 3418

T1 done.  T2 done.  counter = 3418

Оба потока прочитали 3417, оба прибавили единицу, оба записали 3418. Приращений было два, а счётчик сдвинулся на один. Это и есть состояние гонки: результат зависит от того, какой порядок случайно выбрал планировщик, а не от программы. На реальном запуске программы выше получается около 1,4 миллиона вместо 2 миллионов, причём каждый раз другое число. Ошибка не редкая и не случайный шум. Это закономерное следствие чередования, которым вы не управляли.

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

Для одного счётчика есть ответ легче. У процессоров есть атомарные команды «прочитать — изменить — записать» (lock xadd на x86, ldrex и strex на ARM), и компилятор выставляет их наружу как атомарные операции. Ни объекта блокировки, ни ожидающего потока, ни отдельной критической секции.

atomic_long counter = 0;

void *worker(void *arg) {
  (void)arg;
  for (long i = 0; i < 1000000; i++) {
    atomic_fetch_add_explicit(&counter, 1, memory_order_relaxed);
  }
  return NULL;
}

/* lock xadd   -> uncontended, a few nanoseconds
 * contended   -> the cache line is ping-ponged between cores
 */

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

Теперь неприятная часть: почему программа со счётчиком прошла ваш тест? Гонке нужно конкретное чередование, а чередования не равновероятны. На одном свободном ядре оба потока подолгу работают до конца, и в плохое окно программа попадает, может быть, раз на миллион итераций цикла. На загруженной машине, или с подключённым отладчиком, или в проде под нагрузкой это окно ловится постоянно. Поэтому тест проходит на ноутбуке, а инцидент случается на сервере с 32 ядрами. Ошибки одновременности зависят от времени, а значит отсутствие сбоя не является доказательством правильности. Хуже того, добавленная для расследования печать может настолько изменить timing, что ошибка спрячется совсем.

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