Что такое DeadLock?

# DeadLock: полный разбор

Дедлок (deadlock) — это состояние, когда два или более потока бесконечно ждут друг друга, и ни один не может продолжить выполнение. Это классическая проблема в параллельном программировании.

Необходимые условия для дедлока

Для возникновения дедлока ОДНОВРЕМЕННО должны выполниться 4 условия (Coffman's conditions):

1. Взаимное исключение (Mutual Exclusion)

Ресурсы не могут быть разделены между потоками. Только один поток может владеть ресурсом (мьютекс, lock).

2. Удерживание и ожидание (Hold and Wait)

Поток, владеющий одним ресурсом, может запросить другой ресурс.

3. Отсутствие вытеснения (No Preemption)

Ресурс не может быть силовым образом взят у потока; поток должен добровольно его освободить.

4. Циклическое ожидание (Circular Wait)

Цепочка потоков, где каждый ждёт ресурса, который держит следующий.

Классический пример

std::mutex mutex_A, mutex_B;

void thread1_func() {
    {
        std::lock_guard<std::mutex> lock_a(mutex_A);
        std::cout << "Thread 1: acquired A, waiting for B...\n";
        std::this_thread::sleep_for(std::chrono::milliseconds(100));
        
        // Thread 1 ждёт B, но Thread 2 его держит
        std::lock_guard<std::mutex> lock_b(mutex_B);  // DEADLOCK здесь
        std::cout << "Thread 1: acquired B\n";
    }
}

void thread2_func() {
    {
        std::lock_guard<std::mutex> lock_b(mutex_B);
        std::cout << "Thread 2: acquired B, waiting for A...\n";
        std::this_thread::sleep_for(std::chrono::milliseconds(100));
        
        // Thread 2 ждёт A, но Thread 1 его держит
        std::lock_guard<std::mutex> lock_a(mutex_A);  // DEADLOCK здесь
        std::cout << "Thread 2: acquired A\n";
    }
}

int main() {
    std::thread t1(thread1_func);
    std::thread t2(thread2_func);
    
    t1.join();  // Вечно зависает!
    t2.join();
    
    return 0;
}

Поток 1 держит A и ждёт B → Поток 2 держит B и ждёт A → DEADLOCK

Стратегии предотвращения

1. Порядокизация (Lock Ordering)

Всегда захватывай мьютексы в одном и том же порядке.

// ✅ ХОРОШО: всегда A потом B
void thread1_func() {
    std::lock_guard<std::mutex> lock_a(mutex_A);
    std::lock_guard<std::mutex> lock_b(mutex_B);
    // работаем
}

void thread2_func() {
    std::lock_guard<std::mutex> lock_a(mutex_A);  // Тот же порядок!
    std::lock_guard<std::mutex> lock_b(mutex_B);
    // работаем
}

Проблема: Работает только при малом числе мьютексов. С десятками сложно контролировать порядок.

2. Atоmic lock (std::lock)

Одновременное захватывание нескольких мьютексов без дедлока.

// ✅ ОТЛИЧНО: автоматически избегает deadlock
void critical_section() {
    std::lock(mutex_A, mutex_B);
    
    std::lock_guard<std::mutex> lock_a(mutex_A, std::adopt_lock);
    std::lock_guard<std::mutex> lock_b(mutex_B, std::adopt_lock);
    
    // Работаем с обоими ресурсами
    // Деструкторы lock_guard автоматически разблокируют в правильном порядке
}

Как работает: std::lock использует внутри deadlock avoidance алгоритм (обычно try-lock with backoff).

3. Try-lock с timeout

Попытка захватить с таймаутом и откат при таймауте.

bool try_critical_section() {
    std::unique_lock<std::mutex> lock_a(mutex_A, std::defer_lock);
    std::unique_lock<std::mutex> lock_b(mutex_B, std::defer_lock);
    
    // Пытаемся захватить оба с таймаутом
    if (!lock_a.try_lock_for(std::chrono::milliseconds(100))) {
        return false;  // отступаем, чтобы другой поток смог прогрессировать
    }
    
    if (!lock_b.try_lock_for(std::chrono::milliseconds(100))) {
        return false;  // A разблокируется автоматически при выходе
    }
    
    // Обе блокировки успешно захвачены
    return true;
}

4. Избегай вложенных блокировок

Лучше всего — переструктурировать так, чтобы потребность в нескольких мьютексах не возникала.

// ❌ ПЛОХО: вложенные блокировки
void process() {
    {
        std::lock_guard<std::mutex> lock_a(mutex_A);
        // ...
        {
            std::lock_guard<std::mutex> lock_b(mutex_B);  // вложено!
        }
    }
}

// ✅ ХОРОШО: слой абстракции
class SafeDataStore {
    std::mutex mu;
    std::map<int, Data> data;
    
public:
    void update_multiple(int id1, int id2, const Data& d) {
        std::lock_guard<std::mutex> lock(mu);  // Один мьютекс!
        data[id1] = d;
        data[id2] = d;
    }
};

5. Condition variables вместо busy-waiting

// ❌ ПЛОХО: активное ожидание + риск deadlock
while (condition_not_met) {
    // пытаемся захватить ресурсы
}

// ✅ ХОРОШО: condition variable
std::condition_variable cv;
std::mutex mu;

void waiter() {
    std::unique_lock<std::mutex> lock(mu);
    cv.wait(lock, [] { return condition_met; });
    // работаем
}

void notifier() {
    {
        std::lock_guard<std::mutex> lock(mu);
        // изменяем условие
    }
    cv.notify_one();
}

Обнаружение дедлока

ThreadSanitizer

g++ -fsanitize=thread -g program.cpp -o program
./program
# Выведет: WARNING: ThreadSanitizer: lock-order-inversion detected

Timeout detection

if (!std::unique_lock<std::mutex> lock(mu, std::chrono::seconds(5))) {
    // Предполагаемый deadlock!
    std::cerr << "Possible deadlock detected!\n";
    abort();
}

Real-world пример: Database transaction deadlock

void transfer_money(Account& from, Account& to, int amount) {
    // Вариант 1: дедлок если другой поток делает transfer(to, from)
    from.lock();
    to.lock();
    
    // Вариант 2: безопасно
    std::lock(from.mutex, to.mutex);
    std::lock_guard<std::mutex> lock_from(from.mutex, std::adopt_lock);
    std::lock_guard<std::mutex> lock_to(to.mutex, std::adopt_lock);
    
    from.balance -= amount;
    to.balance += amount;
}

Резюме

Дедлок — это взаимная блокировка, где потоки ждут друг друга в цикле.

Профилактика:

1. std::lock() для захватывания нескольких мьютексов
2. Порядокизация мьютексов
3. Избегай вложенных блокировок
4. Используй condition variables
5. ThreadSanitizer для отладки

В production коде дедлоки — одна из самых сложных ошибок для дебага, так что профилактика критична.