Грабли потоков — deadlock, livelock, priority inversion, false sharing

Race conditions — не единственная проблема многопоточного кода. Есть ещё четыре классические грабли, на которые наступали все, кто писал параллельный код: deadlock (взаимная блокировка), livelock (потоки крутятся, но не двигаются), priority inversion (высокоприоритетный поток ждёт низкоприоритетного), false sharing (CPU тормозят из-за невидимой шарящейся cache line).

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

Deadlock — взаимная блокировка

Deadlock происходит, когда два или более потоков ждут друг друга. Простейший случай: поток A держит lock1 и хочет lock2; поток B держит lock2 и хочет lock1. Оба будут ждать вечно.

Четыре условия Коффмана (deadlock возможен, только если все четыре):

1. Mutual exclusion — ресурсы захватываются эксклюзивно.
2. Hold and wait — поток держит ресурс и ждёт другой.
3. No preemption — ресурсы нельзя силой отобрать.
4. Circular wait — цикл в графе ожиданий: A ждёт B, B ждёт C, … C ждёт A.

Чтобы избежать deadlock, надо нарушить хотя бы одно условие.

Стратегии избежания deadlock:

Реальный пример: банковский перевод между счетами.

# ПЛОХО -- возможен deadlock:
def transfer(from_account, to_account, amount):
    with from_account.lock:    # захват A
        with to_account.lock:  # захват B
            from_account.balance -= amount
            to_account.balance += amount

# Если параллельно вызвать:
# Thread 1: transfer(A, B, 100)  -- захватывает A, хочет B
# Thread 2: transfer(B, A, 50)   -- захватывает B, хочет A
# Deadlock!

# ХОРОШО -- lock ordering по ID счёта:
def transfer(from_account, to_account, amount):
    first, second = sorted([from_account, to_account], key=lambda a: a.id)
    with first.lock:
        with second.lock:
            from_account.balance -= amount
            to_account.balance += amount
# Все потоки захватывают сначала меньший ID, потом больший -- цикла быть не может

Отладка deadlock:

# Способ 1: gdb на повисший процесс
sudo gdb -p PID
(gdb) info threads
(gdb) thread apply all bt
# Видим, какие потоки ждут какие futex/mutex

# Способ 2: для Python -- py-spy
pip install py-spy
sudo py-spy dump --pid PID
# Покажет stack trace всех потоков -- видно, где висят

# Способ 3: для Java
jstack PID
# Java умеет детектировать deadlock и явно покажет:
# "Found one Java-level deadlock"

# Способ 4: для running C/C++ программы посмотреть, что ждут futex'ы:
sudo strace -p PID
# Если все потоки в futex_wait -- deadlock или просто тишина (idle)

Livelock — потоки крутятся, но не работают

Livelock похож на deadlock, но потоки не заблокированы — они что-то делают (CPU 100%), просто это «что-то» бесполезно. Классический пример: два человека встретились в коридоре, оба отступили в одну сторону, столкнулись, оба отступили в другую — и так бесконечно.

Livelock часто возникает в lock-free алгоритмах с retry-циклом. Если все потоки одновременно делают CAS, и при failure ретраются — они могут затоптать друг друга бесконечно.

Решения для livelock:

1. Рандомизация backoff. Случайная задержка перед retry — два потока с разными задержками не будут синхронизироваться.
2. Exponential backoff. При каждом failure увеличиваем задержку — 1ms, 2ms, 4ms, 8ms…
3. Приоритеты. Один поток имеет приоритет, другой всегда уступает.
4. Гарантия прогресса. Алгоритм должен быть lock-free (хоть один поток гарантированно прогрессирует) или wait-free (все потоки гарантированно прогрессируют).

# Пример livelock в bad lock-free counter:
import threading, time
counter = [0]
def bad_lock_free():
    while True:
        old = counter[0]
        new = old + 1
        # Симуляция CAS: проверяем, что значение не изменилось
        if counter[0] == old:
            counter[0] = new
            return
        # Иначе ретраемся -- всегда вместе с другими потоками

# С двумя потоками иногда работает, с многими -- livelock

Priority inversion — высокоприоритетный ждёт низкоприоритетного

Этот баг знаменит тем, что положил Mars Pathfinder в 1997 году. Высокоприоритетный поток ждёт mutex, который держит низкоприоритетный поток. А среднеприоритетный поток вытесняет низкоприоритетного с CPU. Получается: высокий ждёт низкого, который не получает CPU из-за среднего — задержка.

Решения для priority inversion:

1. Priority inheritance (наследование приоритета). Когда высокоприоритетный поток ждёт mutex, держатель mutex временно «наследует» этот приоритет. Низкоприоритетный T1 становится временно высокоприоритетным — его не вытесняет T2. Pthreads поддерживает: pthread_mutexattr_setprotocol(PTHREAD_PRIO_INHERIT).

2. Priority ceiling. Mutex заранее знает свой потолок приоритета — все владельцы получают этот приоритет.

3. Избегать смешивания приоритетов в общем коде. Если есть real-time потоки и обычные — держите для них раздельные данные.

В Mars Pathfinder было всё: real-time-планировщик, mutex без priority inheritance, и три потока разных приоритетов. Решилось включением priority inheritance через pthread_mutexattr.

# В Linux priority inheritance включается так:
# (в pthread_mutexattr_setprotocol -- C-код)
# pthread_mutexattr_t attr;
# pthread_mutexattr_init(&attr);
# pthread_mutexattr_setprotocol(&attr, PTHREAD_PRIO_INHERIT);
# pthread_mutex_init(&mutex, &attr);

# Real-time потоки обычно настраиваются через chrt:
chrt -f -p 80 PID    # SCHED_FIFO с приоритетом 80
# Подробнее в модуле 5 -- scheduling

False sharing — невидимый враг производительности

False sharing — проблема не корректности, а производительности. Два потока работают с разными переменными, но эти переменные оказались на одной cache line (типично 64 байта на x86). Из-за cache coherence protocol (MESI) cache line «гонится» между ядрами, и работа замедляется в 10-100 раз.

Как избежать false sharing:

1. Padding. Между переменными разных потоков добавить пустое место, чтобы они оказались на разных cache lines.

   struct Counter {
       atomic<int> value;
       char padding[60];  // 64 - 4 = 60 байт padding
   };
   Counter counters[N_THREADS];  // каждый на своей cache line

2. Alignment. Использовать alignas(64) (C++) или #[repr(align(64))] (Rust). Гарантирует, что переменная начинается с новой cache line.

3. Thread-local storage. Использовать локальные переменные потока, синхронизироваться только в конце.

# Замерим false sharing экспериментально:
cat > /tmp/false.c << 'EOF'
#include <pthread.h>
#include <stdio.h>
#include <stdatomic.h>
#include <time.h>

#define N 4
#define ITER 100000000

// Плохо: counters на одной cache line
atomic_int bad[N];
// Хорошо: padding между counters
struct Padded { atomic_int v; char pad[60]; } good[N] __attribute__((aligned(64)));

void* w_bad(void* a) {
    int i = (long)a;
    for (long j = 0; j < ITER; j++) atomic_fetch_add(&bad[i], 1);
    return NULL;
}
void* w_good(void* a) {
    int i = (long)a;
    for (long j = 0; j < ITER; j++) atomic_fetch_add(&good[i].v, 1);
    return NULL;
}

void run(void* (*f)(void*), const char* name) {
    pthread_t t[N];
    struct timespec t1, t2;
    clock_gettime(CLOCK_MONOTONIC, &t1);
    for (long i = 0; i < N; i++) pthread_create(&t[i], NULL, f, (void*)i);
    for (int i = 0; i < N; i++) pthread_join(t[i], NULL);
    clock_gettime(CLOCK_MONOTONIC, &t2);
    double sec = (t2.tv_sec - t1.tv_sec) + (t2.tv_nsec - t1.tv_nsec)/1e9;
    printf("%s: %.2f sec\n", name, sec);
}

int main() {
    run(w_bad, "with false sharing");
    run(w_good, "with padding");
}
EOF
gcc -O2 /tmp/false.c -lpthread -o /tmp/false
/tmp/false
# Типично: bad = 3-5 секунд, good = 0.5-1 секунда (5-10x разница)

False sharing особенно опасен в data engineering: счётчики метрик, аккумуляторы статистики, lock-free queues. Профилировщики типа perf c2c умеют детектировать false sharing — посмотрите эту команду, если занимаетесь HPC.

Сводная таблица проблем

Попробуй сам

# 1. Создадим deadlock и проверим через py-spy:
cat > /tmp/dead.py << 'EOF'
import threading, time
a = threading.Lock()
b = threading.Lock()
def w1():
    with a:
        time.sleep(0.1)
        with b:
            print("w1 done")
def w2():
    with b:
        time.sleep(0.1)
        with a:
            print("w2 done")
threading.Thread(target=w1, daemon=True).start()
threading.Thread(target=w2, daemon=True).start()
time.sleep(60)
EOF
python3 /tmp/dead.py &
DPID=$!
sleep 2

# pip install py-spy
sudo py-spy dump --pid $DPID
# Покажет, что оба потока в .acquire() -- классический deadlock

kill $DPID

# 2. Замерьте false sharing:
# Скомпилируйте /tmp/false.c (см. выше) и запустите
# Разница 5-10x между bad и good версиями

# 3. Найдите cache line size вашей системы:
getconf LEVEL1_DCACHE_LINESIZE
# Типично 64 (x86) или 128 (некоторые ARM/POWER)

# 4. perf c2c -- детектор false sharing:
# perf c2c record ./your-program
# perf c2c report
# Покажет горячие cache lines и кто на них контентится