CS Notes

synchronization

17 min read

Синхронизация

← Права доступа и capabilities | Модель памяти →

Права доступа и capabilities определяют, кто может обращаться к ресурсу: ядро проверяет UID, GID и capability-флаги при каждом системном вызове. Но когда несколько потоков одного процесса — с одинаковыми UID и capabilities — одновременно обращаются к одним и тем же данным в памяти, разрешение доступа не спасает от повреждения. Нужен другой механизм: не «кому можно», а «в каком порядке и когда».

Потоки разделяют адресное пространство — любой из них может прочитать и записать любой адрес в heap и в секции данных процесса. Планировщик при этом может прервать поток между любыми двумя машинными инструкциями, передав ядро другому потоку. Сочетание этих двух фактов — общая память и вытеснение — порождает гонки (race conditions): результат программы начинает зависеть от порядка, в котором планировщик чередует потоки.

Потерянный инкремент

Два потока инкрементируют общий счётчик по миллиону раз каждый. Ожидание — 2 000 000. Реальность:

#include <pthread.h>
#include <stdio.h>
 
static int counter = 0;
 
void *worker(void *arg) {
    for (int i = 0; i < 1000000; i++)
        counter++;
    return NULL;
}
 
int main(void) {
    pthread_t t1, t2;
    pthread_create(&t1, NULL, worker, NULL);
    pthread_create(&t2, NULL, worker, NULL);
    pthread_join(t1, NULL);
    pthread_join(t2, NULL);
    printf("counter = %d\n", counter);   /* ~1 200 000 */
    return 0;
}

Результат — примерно 1 200 000 вместо 2 000 000. Потеряно 800 тысяч инкрементов. Причина в том, что counter++ — не одна инструкция.

Компилятор превращает counter++ в три операции: load значения из памяти в регистр, add единицы к регистру, store результата обратно в память. Планировщик может вытеснить поток между любыми из этих шагов:

поток A                          поток B
-------                          -------
load counter -> rax (= 0)
                                 load counter -> rax (= 0)
add rax, 1         (rax = 1)
                                 add rax, 1         (rax = 1)
store rax -> counter (= 1)
                                 store rax -> counter (= 1)

Оба потока прочитали 0, оба записали 1. Два инкремента — а счётчик вырос на единицу. Это lost update (потерянное обновление): запись одного потока затирает запись другого, потому что между чтением и записью вклинился чужой поток.

Гонка и гонка данных

Термин гонка (race condition) описывает ситуацию, когда результат программы зависит от временного порядка операций нескольких потоков. Потерянный инкремент — пример гонки: если планировщик чередует потоки иначе, результат меняется.

Стандарты C и C++ вводят более узкое понятие — гонку данных (data race): одновременный доступ двух потоков к одной ячейке памяти, где хотя бы один доступ — запись, и ни один из них не использует атомарную операцию или блокировку. По стандарту гонка данных — это неопределённое поведение (undefined behavior): компилятор может оптимизировать код в предположении, что гонок нет, и программа может делать что угодно.

Разница между двумя понятиями: гонка данных — свойство конкретных обращений к памяти, её можно обнаружить инструментами вроде ThreadSanitizer. Гонка — ошибка на уровне логики, где корректность зависит от тайминга. Классический пример — TOCTOU (time-of-check-to-time-of-use, разрыв между проверкой и использованием): программа проверяет, существует ли файл (access()), затем открывает его (open()). Между проверкой и открытием другой процесс может удалить файл или заменить его символической ссылкой. Каждая из двух операций по отдельности потокобезопасна — гонки данных нет, но логическая гонка есть.

Rust устраняет гонки данных на уровне системы типов: &mut T — единственная мутабельная ссылка, &T — произвольное количество иммутабельных. Компилятор отклоняет код, где два потока могут одновременно писать в одну ячейку без синхронизации. Но логические гонки (TOCTOU, lost update на уровне бизнес-логики) остаются возможными и в safe Rust.

Критическая секция

Участок кода, в котором поток работает с разделяемыми данными, называется критической секцией (critical section). В примере со счётчиком критическая секция — три инструкции load-add-store. Корректность требует, чтобы в каждый момент времени в критической секции находился только один поток.

Напрашивается решение — завести флаг locked:

/* наивная попытка */
volatile int locked = 0;
 
void naive_lock(void) {
    while (locked)          /* ждём, пока занято */
        ;
    locked = 1;             /* захватываем */
}

Попытка не работает: проверка locked == 0 и присваивание locked = 1 — это ровно та же пара load + store. Два потока могут оба прочитать locked == 0 и оба записать 1, считая, что блокировка захвачена. Та же гонка, рекурсия проблемы. Для решения нужна аппаратная поддержка — инструкция, выполняющая чтение и запись как одну неделимую операцию.

Три инструмента синхронизации

Задача синхронизации решается на трёх уровнях. Атомарная инструкция CAS (Compare-And-Swap) обеспечивает неделимость одной операции чтения-модификации-записи. Мьютекс (mutex) защищает произвольный блок кода, внутри которого может быть десятки операций, а не одна. Futex — это механизм реализации мьютекса в Linux, который избегает системного вызова при отсутствии конкуренции. Три уровня — не альтернативы, а слои: мьютекс построен на основе CAS, а futex — способ сделать мьютекс быстрым.

  программист использует:

  +----------------+
  |     mutex      |  lock()/unlock() -- защищает блок кода
  +-------+--------+
          |
          | реализован через
          v
  +----------------+
  |     futex      |  fast path: CAS в user space (~10 ns)
  |                |  slow path: futex() syscall, поток спит
  +-------+--------+
          |
          | построен на
          v
  +----------------+
  |     CAS        |  одна атомарная аппаратная
  |  (процессор)   |  read-modify-write инструкция
  +----------------+

Compare-and-swap

CAS (compare-and-swap) — атомарная операция, выполняющая чтение, сравнение и условную запись как единое целое. Она принимает три аргумента: адрес ячейки, ожидаемое значение и новое значение. Если текущее содержимое ячейки совпадает с ожидаемым — CAS записывает новое и возвращает успех. Если содержимое изменилось (другой поток успел записать своё) — CAS не трогает ячейку и возвращает неудачу.

С помощью CAS счётчик инкрементируется без потерь:

#include <stdatomic.h>
 
void atomic_increment(atomic_int *ptr) {
    int old;
    do {
        old = atomic_load(ptr);           /* читаем текущее значение */
    } while (!atomic_compare_exchange_weak(ptr, &old, old + 1));
    /* weak может отказать и при отсутствии реальной конкуренции  */
    /* (spurious failure), поэтому CAS всегда обёрнут в цикл     */
}

Цикл работает так: поток читает текущее значение, вычисляет новое, затем пытается записать через CAS. Если значение изменилось (другой поток успел записать своё) или произошёл spurious failure (на архитектурах с LL/SC-реализацией), CAS отказывает — цикл повторяется с обновлённым значением. При низкой конкуренции цикл срабатывает с первой попытки. При высокой конкуренции потоки повторяют попытки, но ни один инкремент не теряется.

На практике для простого инкремента не нужно писать CAS-цикл вручную. В C — atomic_fetch_add(&counter, 1), в Rust — counter.fetch_add(1, Ordering::Relaxed). Компилятор превращает вызов в аппаратный атомарный RMW-примитив.

Стоимость атомарных операций

Атомарная инструкция без конкуренции (uncontended) стоит ~5-20 нс. При конкуренции (contended) цена вырастает до ~50-200 нс: каждая операция требует получения кеш-линии от другого ядра — подробности в атомарных инструкциях и когерентности кешей.

Для счётчика — одной операции read-modify-write — атомарный инкремент идеален. Но что, если критическая секция содержит десяток операций? Банковский перевод: прочитать баланс счёта A, прочитать баланс счёта B, проверить, что на A достаточно средств, списать с A, зачислить на B. CAS защищает одну ячейку за раз — он не может обеспечить атомарность всех пяти шагов вместе.

Мьютекс

Мьютекс (mutex, от mutual exclusion — взаимное исключение) защищает произвольный блок кода. Поток вызывает lock() перед входом в критическую секцию и unlock() при выходе. Если мьютекс уже захвачен другим потоком, lock() блокирует текущий поток до освобождения.

#include <pthread.h>
 
static int counter = 0;
static pthread_mutex_t mtx = PTHREAD_MUTEX_INITIALIZER;
 
void *worker(void *arg) {
    for (int i = 0; i < 1000000; i++) {
        pthread_mutex_lock(&mtx);
        counter++;                    /* критическая секция */
        pthread_mutex_unlock(&mtx);
    }
    return NULL;
}

Теперь counter == 2 000 000 всегда. Но производительность упала: каждый инкремент обёрнут в lock/unlock, а это десятки наносекунд накладных расходов. Для счётчика правильным решением остаётся atomic_fetch_add. Мьютекс нужен, когда критическая секция — не одна инструкция, а несколько связанных операций, которые должны выполниться целиком или не выполниться вовсе.

Внутри мьютекс использует CAS для захвата: lock() пытается атомарно записать 1 в поле состояния (0 = свободен, 1 = занят). Если CAS удался — мьютекс захвачен. Вопрос в том, что делать, если CAS не удался и мьютекс занят.

Спинлок и спящий мьютекс

Два варианта ожидания освобождения мьютекса.

Спинлок (spinlock) крутится в цикле, непрерывно повторяя CAS: «занят? а сейчас? а сейчас?». Поток не уходит в ядро, не теряет свой квант — но сжигает процессорное время. Спинлок оправдан, когда критическая секция короче стоимости системного вызова: если мьютекс удерживается 50 нс, а вход в ядро для усыпления стоит 1-2 мкс, дешевле покрутиться. Ядро Linux использует спинлоки для защиты коротких участков кода, выполняемых с запрещёнными прерываниями.

Спящий мьютекс при неудачном CAS просит ядро усыпить текущий поток. Поток переходит из состояния RUNNING в SLEEPING и не потребляет процессорное время. При unlock() ядро будит один из спящих потоков. Стоимость усыпления и пробуждения — 1-2 мкс (два переключения контекста), но эта цена разовая: пока поток спит, ядро работает с другими потоками. Для критических секций длиннее 100 нс или при высокой конкуренции спящий мьютекс выгоднее спинлока.

pthread_mutex_t на Linux — спящий мьютекс. Но реализован он хитрее, чем простой выбор «spin или sleep».

Futex: быстрый путь без ядра

До 2002 года Linux-реализация потоков (LinuxThreads) на каждый lock() и unlock() выполняла системный вызов — переход из user space в kernel space и обратно. Каждый вызов стоил 1-2 мкс, даже если мьютекс свободен и конкуренции нет. Для приложения, выполняющего миллионы операций lock/unlock в секунду, накладные расходы становились узким местом.

Futex (fast userspace mutex) — механизм, введённый в Linux 2.5.7 (2002) вместе с NPTL (Native POSIX Threads Library). Идея: хранить состояние мьютекса в обычной переменной в user space и входить в ядро только тогда, когда действительно нужно ждать.

Захват (lock) работает в два шага. Fast path: CAS пытается атомарно переключить состояние мьютекса с 0 (свободен) на 1 (занят). Если CAS удался — мьютекс захвачен, системного вызова не было. Одна атомарная инструкция, ~10-20 нс. Slow path: если CAS обнаружил, что мьютекс занят, поток выполняет системный вызов futex(FUTEX_WAIT). Ядро проверяет значение переменной ещё раз (чтобы мьютекс не был освобождён между неудачным CAS и входом в ядро) и, если мьютекс по-прежнему занят, усыпляет поток.

Освобождение (unlock): CAS записывает 0 в переменную мьютекса. Если были ожидающие потоки (что определяется по значению переменной: обычно 2 = «занят и есть ожидающие»), выполняется futex(FUTEX_WAKE) — ядро будит один из спящих потоков.

lock():

    CAS(state, 0 -> 1)
         |
    +----+----+
    |         |
  удалось   не удалось
    |         |
  готово    futex(FUTEX_WAIT)
  ~10 ns    поток спит в ядре


unlock():

    state = 0
         |
    есть ожидающие?
    +----+----+
    |         |
   нет       да
    |         |
  готово    futex(FUTEX_WAKE)
  ~10 ns    будим один поток

Все реализации pthread_mutex_lock на Linux используют futex. Когда профилировщик показывает 10 нс на uncontended lock/unlock, это и есть fast path: два CAS без единого системного вызова.

Семафор

CAS защищает одну переменную, мьютекс впускает в критическую секцию один поток. Семафор (semaphore) обобщает: он хранит счётчик и впускает до N потоков одновременно.

Операция sem_wait() атомарно уменьшает счётчик на 1. Если счётчик уже 0, поток засыпает. Операция sem_post() увеличивает счётчик на 1 и будит одного из ожидающих потоков. Бинарный семафор (N=1) по поведению похож на мьютекс, но у семафора нет понятия владельца — sem_post() может вызвать любой поток, не обязательно тот, кто вызвал sem_wait().

Типичный пример — пул из 10 подключений к базе данных. Семафор инициализируется значением 10. Каждый поток перед использованием подключения вызывает sem_wait(). Первые 10 потоков проходят без ожидания, одиннадцатый засыпает до тех пор, пока один из первых десяти не вернёт подключение через sem_post().

RWLock: читатели и писатели

Мьютекс последователен: пока один поток читает данные внутри критической секции, остальные ждут, хотя чтение не модифицирует данные и несколько одновременных чтений безопасны. RWLock (read-write lock) разделяет доступ: одновременно допускается произвольное количество читателей ИЛИ один писатель.

RWLock: допустимые состояния

  ┌─────────────────────────────────────────────┐
  │  N читателей (rdlock)      0 писателей      │  ok
  │  0 читателей               1 писатель (wrlock)│  ok
  │  N читателей               1 писатель        │  запрещено
  │  0 читателей               M писателей       │  запрещено
  └─────────────────────────────────────────────┘

RWLock выгоден, когда операций чтения значительно больше, чем записи: конфигурация, роутинг-таблица, кеш ответов. Но захват RWLock стоит дороже мьютекса — 30-50 нс против 10-20 нс, потому что внутри атомарно обновляется счётчик читателей. Если чтения не преобладают (скажем, соотношение 3:1), накладные расходы RWLock могут перевесить выигрыш от параллельности, и простой мьютекс окажется быстрее.

Условная переменная: ожидание события

Мьютекс защищает данные, но не умеет ждать, пока данные изменятся определённым образом. Классическая задача — producer-consumer: один поток добавляет элементы в очередь, другой забирает и обрабатывает. Consumer должен ждать, пока очередь не станет непустой. Крутиться в цикле с lock(); check(); unlock(); — это busy wait (активное ожидание), расход CPU впустую.

Условная переменная (condition variable, condvar) позволяет потоку атомарно освободить мьютекс и уснуть, ожидая сигнала от другого потока. pthread_cond_wait(&cond, &mtx) выполняет три действия как единое целое: освобождает мьютекс, добавляет поток в очередь ожидания, усыпляет поток. Когда другой поток вызывает pthread_cond_signal(&cond), один из ожидающих просыпается, автоматически захватывает мьютекс обратно и продолжает выполнение.

#include <pthread.h>
#include <stdbool.h>
 
#define QUEUE_SIZE 16
 
static int queue[QUEUE_SIZE];
static int count = 0;
static pthread_mutex_t mtx  = PTHREAD_MUTEX_INITIALIZER;
static pthread_cond_t  not_empty = PTHREAD_COND_INITIALIZER;
static pthread_cond_t  not_full  = PTHREAD_COND_INITIALIZER;
 
void *producer(void *arg) {
    for (int i = 0; i < 1000000; i++) {
        pthread_mutex_lock(&mtx);
        while (count == QUEUE_SIZE)             /* очередь полна */
            pthread_cond_wait(&not_full, &mtx); /* спим, мьютекс отпущен */
        queue[count++] = i;
        pthread_cond_signal(&not_empty);        /* будим consumer */
        pthread_mutex_unlock(&mtx);
    }
    return NULL;
}
 
void *consumer(void *arg) {
    for (int i = 0; i < 1000000; i++) {
        pthread_mutex_lock(&mtx);
        while (count == 0)                       /* очередь пуста */
            pthread_cond_wait(&not_empty, &mtx); /* спим, мьютекс отпущен */
        int item = queue[--count];
        pthread_cond_signal(&not_full);          /* будим producer */
        pthread_mutex_unlock(&mtx);
        /* обработка item */
    }
    return NULL;
}

Проверка условия — while, не if. Это принципиально. POSIX допускает ложные пробуждения (spurious wakeups): поток может проснуться без явного сигнала. Причина — оптимизация реализации: ядро может разбудить поток при изменении состояния, которое не связано с сигналом condvar. Если проверка — if, поток после ложного пробуждения пройдёт дальше, не проверив условие повторно, и возьмёт из пустой очереди мусор. Цикл while перепроверяет условие после каждого пробуждения.

Банковский перевод: блокировка нескольких ресурсов

Вернёмся к банковскому переводу. transfer(A, B, amount): списать amount с баланса A, зачислить на баланс B. Вся операция должна быть атомарной — промежуточное состояние (деньги списаны, но не зачислены) не должно быть видно другим потокам.

CAS не подходит: можно атомарно обновить баланс A, но между обновлением A и обновлением B другой поток может прочитать несогласованное состояние — деньги исчезли из A, но не появились в B. Нужен мьютекс, причём на оба счёта:

struct account {
    int id;
    int balance;
    pthread_mutex_t mtx;
};
 
void transfer(struct account *from, struct account *to, int amount) {
    pthread_mutex_lock(&from->mtx);
    pthread_mutex_lock(&to->mtx);
 
    if (from->balance >= amount) {
        from->balance -= amount;
        to->balance   += amount;
    }
 
    pthread_mutex_unlock(&to->mtx);
    pthread_mutex_unlock(&from->mtx);
}

Код работает — но содержит ловушку.

Deadlock

Поток 1 вызывает transfer(A, B, 100): захватывает мьютекс A, пытается захватить мьютекс B. Параллельно поток 2 вызывает transfer(B, A, 50): захватывает мьютекс B, пытается захватить мьютекс A. Каждый поток удерживает ресурс, который нужен другому, и ждёт ресурс, который удерживает другой. Ни один из них не может продвинуться. Это взаимная блокировка (deadlock).

поток 1                          поток 2
-------                          -------
lock(A.mtx)    -- ok             lock(B.mtx)    -- ok
lock(B.mtx)    -- ждёт...        lock(A.mtx)    -- ждёт...
    |                                |
    +-------->  deadlock  <----------+

Deadlock возникает при одновременном выполнении четырёх условий:

  1. Взаимное исключение (mutual exclusion) — ресурс может удерживаться только одним потоком. Это свойство самого мьютекса, его нельзя убрать.

  2. Удержание и ожидание (hold and wait) — поток, удерживая один ресурс, ожидает другой.

  3. Неотнимаемость (no preemption) — мьютекс не может быть отобран у потока принудительно, только добровольно освобождён.

  4. Циклическое ожидание (circular wait) — поток 1 ждёт ресурс потока 2, поток 2 ждёт ресурс потока 1.

Достаточно разорвать одно из четырёх условий, чтобы deadlock стал невозможен. На практике разрывают четвёртое — циклическое ожидание — через упорядочивание блокировок (lock ordering): всегда захватывать мьютексы в фиксированном порядке. В банковском переводе — по возрастанию id счёта:

void transfer_safe(struct account *a, struct account *b, int amount) {
    struct account *first  = a->id < b->id ? a : b;
    struct account *second = a->id < b->id ? b : a;
 
    pthread_mutex_lock(&first->mtx);
    pthread_mutex_lock(&second->mtx);
 
    if (a->balance >= amount) {
        a->balance -= amount;
        b->balance += amount;
    }
 
    pthread_mutex_unlock(&second->mtx);
    pthread_mutex_unlock(&first->mtx);
}

Теперь оба потока сначала захватывают мьютекс с меньшим id. Циклического ожидания быть не может: если мьютекс A (id=1) захвачен, мьютекс B (id=2) ещё не захвачен — второй поток будет ждать A, не удерживая B.

Альтернативный подход — try-lock с откатом: pthread_mutex_trylock() пытается захватить мьютекс без блокировки. Если захват не удался, поток освобождает все удерживаемые мьютексы, ждёт случайное время (backoff — отступление с паузой) и пытается заново. Этот подход разрывает условие «hold and wait», но при высокой конкуренции приводит к livelock (живая блокировка) — потоки бесконечно отпускают и перезахватывают, не продвигаясь.

Типы мьютексов pthread

pthread_mutex инициализируется с атрибутами, которые меняют поведение при ошибках программиста. Тип задаётся через pthread_mutexattr_settype() до pthread_mutex_init().

PTHREAD_MUTEX_DEFAULT (он же NORMAL) — базовый тип. Если поток попытается захватить мьютекс, который он сам уже держит — deadlock: поток ждёт освобождения мьютекса, который сам же удерживает. Если поток B попытается unlock() мьютекс, захваченный потоком A — поведение не определено.

PTHREAD_MUTEX_ERRORCHECK — при повторном захвате тем же потоком lock() возвращает EDEADLK вместо зависания. При unlock() чужого мьютекса — возвращает EPERM. Дороже на ~5–10 нс: реализация pthread хранит владельца и проверяет его на userspace fast path, а при конкуренции всё равно уходит в ядро через futex. Это полезный режим для отладки, потому что ловит баги раньше, чем они превращаются в немой deadlock.

PTHREAD_MUTEX_RECURSIVE — разрешает одному потоку захватывать мьютекс несколько раз. Внутри ведётся счётчик: первый lock() — счётчик 1, второй lock() из того же потока — счётчик 2. Каждый unlock() уменьшает счётчик, мьютекс освобождается при 0. Полезен, когда функция A захватывает мьютекс и вызывает функцию B, которая тоже его захватывает. На практике считается антипаттерном — если функции не знают, под каким мьютексом вызваны, архитектура запутана.

Отмена потока

Иногда поток нужно остановить извне — пользователь нажал «отмена», результат больше не нужен. pthread_cancel(thread_id) не убивает поток мгновенно — устанавливает флаг «отмена запрошена». Поток завершается, когда достигает cancellation point (точки отмены) — большинство блокирующих функций: read(), write(), sleep(), pthread_cond_wait().

Поток контролирует отмену через pthread_setcancelstate(): PTHREAD_CANCEL_DISABLE игнорирует запрос, PTHREAD_CANCEL_ENABLE разрешает. pthread_setcanceltype() выбирает момент: DEFERRED (по умолчанию, только в cancellation points) или ASYNCHRONOUS (в любой момент — почти невозможно использовать корректно, ресурсы остаются незакрытыми).

На практике cancellation используется редко. Более предсказуемый подход — cooperative cancellation через атомарный флаг:

atomic_bool should_stop = false;
 
// в потоке:
while (!atomic_load(&should_stop)) {
    do_work();
}
 
// извне:
atomic_store(&should_stop, true);
pthread_join(thread_id, NULL);

За пределами мьютекса

Мьютекс и CAS решили задачу корректного доступа к общим данным. CAS стоит 5-20 нс без конкуренции, мьютекс через futex — 10-20 нс. Существует и радикально иной подход: вместо координации доступа к общим данным между потоками — обрабатывать все запросы в одном потоке, исключив гонки по конструкции. Event loop Redis работает именно так: один поток обрабатывает все команды последовательно, а мультиплексирование позволяет ему обслуживать тысячи клиентов без блокировки.

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

См. также

  • Ruby Mutex и GVL — Mutex#synchronize обёрнут над pthread_mutex; GVL — внутренний мьютекс VM, сериализующий исполнение Ruby bytecode даже при явных lock’ах пользователя

Sources

← Права доступа и capabilities | Модель памяти →

Graph View

Backlinks