Сколько мьютексов необходимо для Deadlock?

Сколько мьютексов необходимо для Deadlock

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

Классический случай: 2 мьютекса, 2 потока

Это самый простой пример deadlock'а:

#include <mutex>
#include <thread>
#include <iostream>

std::mutex mtx1, mtx2;

void thread1_func() {
    std::lock_guard<std::mutex> lock1(mtx1);  // Захватываем mtx1
    std::cout << "Thread 1 locked mtx1\n";
    
    std::this_thread::sleep_for(std::chrono::milliseconds(100));
    
    std::lock_guard<std::mutex> lock2(mtx2);  // Пытаемся захватить mtx2
    std::cout << "Thread 1 locked mtx2\n";    // НИКОГДА НЕ ВЫПОЛНИТСЯ
}

void thread2_func() {
    std::lock_guard<std::mutex> lock2(mtx2);  // Захватываем mtx2
    std::cout << "Thread 2 locked mtx2\n";
    
    std::this_thread::sleep_for(std::chrono::milliseconds(100));
    
    std::lock_guard<std::mutex> lock1(mtx1);  // Пытаемся захватить mtx1
    std::cout << "Thread 2 locked mtx1\n";    // НИКОГДА НЕ ВЫПОЛНИТСЯ
}

int main() {
    std::thread t1(thread1_func);
    std::thread t2(thread2_func);
    
    t1.join();
    t2.join();
    
    return 0;
}

// Результат: DEADLOCK!
// Thread 1 ждет mtx2 (заблокирован Thread 2)
// Thread 2 ждет mtx1 (заблокирован Thread 1)
// Программа зависает навечно

Что произошло:

Время  Thread 1                    Thread 2
------------------------------------------------------
1      Захватывает mtx1
2                                 Захватывает mtx2
3      Пытается захватить mtx2     Ждет...
4      Ждет...                     Пытается захватить mtx1
5      DEADLOCK: оба ждут друг друга

Может ли быть deadlock с 1 мьютексом?

Технически да, но нужны 2+ потока и рекурсивный мьютекс:

#include <mutex>
#include <thread>

std::mutex mtx;

void risky_function() {
    std::lock_guard<std::mutex> lock(mtx);
    // Некорректно: пытаемся захватить mtx снова
    // Если mtx обычный (non-recursive), это DEADLOCK
}

void thread_func() {
    std::lock_guard<std::mutex> lock(mtx);
    risky_function();  // DEADLOCK с обычным mutex!
}

// Решение: использовать recursive_mutex
std::recursive_mutex rmtx;

void thread_func_ok() {
    std::lock_guard<std::recursive_mutex> lock(rmtx);
    std::lock_guard<std::recursive_mutex> lock2(rmtx);  // OK, не deadlock
}

Более сложный случай: 3+ мьютекса

Deadlock может быть намного сложнее:

#include <mutex>
#include <thread>

std::mutex mtx1, mtx2, mtx3;

void thread1_func() {
    std::lock_guard<std::mutex> lock1(mtx1);
    std::this_thread::sleep_for(std::chrono::milliseconds(10));
    std::lock_guard<std::mutex> lock2(mtx2);
}

void thread2_func() {
    std::lock_guard<std::mutex> lock2(mtx2);
    std::this_thread::sleep_for(std::chrono::milliseconds(10));
    std::lock_guard<std::mutex> lock3(mtx3);
}

void thread3_func() {
    std::lock_guard<std::mutex> lock3(mtx3);
    std::this_thread::sleep_for(std::chrono::milliseconds(10));
    std::lock_guard<std::mutex> lock1(mtx1);
}

int main() {
    std::thread t1(thread1_func);
    std::thread t2(thread2_func);
    std::thread t3(thread3_func);
    
    // DEADLOCK: циклическая зависимость
    // T1 -> mtx2 -> T2 -> mtx3 -> T3 -> mtx1 -> T1
    
    t1.join();
    t2.join();
    t3.join();
}

Условия для Deadlock (Coffman Conditions)

Все эти условия должны быть выполнены одновременно:

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

Ресурс (мьютекс) может быть захвачен только одним потоком:

std::mutex mtx;
// Только один поток может держать mtx

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

Поток может держать ресурс и ждать другого:

std::lock_guard<std::mutex> lock1(mtx1);  // Удерживаем mtx1
std::lock_guard<std::mutex> lock2(mtx2);  // Ждем mtx2

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

Нельзя отобрать ресурс у потока без его согласия:

// В C++ нельзя просто "отобрать" мьютекс у потока
// Если потокусчный поток не освобождает мьютекс, остальные ждут

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

Создается цикл зависимостей:

// T1 -> mtx1 -> mtx2 -> T2 -> mtx2 -> mtx1 -> T1
// Это цикл, deadlock неизбежен

Как предотвратить Deadlock

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

// Плохо: разные порядки в разных местах
void func_a() {
    lock(mtx1);
    lock(mtx2);
}

void func_b() {
    lock(mtx2);  // ДРУГОЙ порядок!
    lock(mtx1);
}

// Хорошо: всегда mtx1, потом mtx2
void func_a() {
    lock(mtx1);
    lock(mtx2);
}

void func_b() {
    lock(mtx1);  // Одинаковый порядок
    lock(mtx2);
}

2. Используй std::lock для одновременного захвата

#include <mutex>

std::mutex mtx1, mtx2;

void safe_function() {
    // Захватывает оба мьютекса одновременно, избегая deadlock
    std::lock(mtx1, mtx2);
    
    std::lock_guard<std::mutex> lock1(mtx1, std::adopt_lock);
    std::lock_guard<std::mutex> lock2(mtx2, std::adopt_lock);
    
    // Работаем с обоими ресурсами
    // Деструкторы lock_guard освободят мьютексы
}

3. Ограничи критические секции

// Плохо: длинная критическая секция
{
    std::lock_guard<std::mutex> lock(mtx);
    
    // Много работы
    sleep(1000);
    
    // Возможность для deadlock растет
}

// Хорошо: минимальная критическая секция
{
    std::lock_guard<std::mutex> lock(mtx);
    // Только необходимая работа
}

4. Используй unique_lock с timeout

#include <chrono>

std::mutex mtx1, mtx2;

void safe_with_timeout() {
    std::unique_lock<std::mutex> lock1(mtx1);
    
    if (!lock2.try_lock_for(std::chrono::seconds(1))) {
        // Timeout: отпускаем lock1 и повторяем
        lock1.unlock();
        throw std::runtime_error("Timeout acquiring mtx2");
    }
    
    std::unique_lock<std::mutex> lock2(mtx2, std::adopt_lock);
}

5. Иерархия мьютексов

Создай свой класс для отслеживания порядка:

class HierarchyMutex {
private:
    std::mutex mtx;
    unsigned long const hierarchy_value;
    unsigned long previous_hierarchy_value;
    static thread_local unsigned long this_thread_hierarchy_value;

public:
    explicit HierarchyMutex(unsigned long value) 
        : hierarchy_value(value), previous_hierarchy_value(0) {}

    void lock() {
        check_for_hierarchy_violation();
        mtx.lock();
        update_hierarchy_value();
    }

private:
    void check_for_hierarchy_violation() {
        if (this_thread_hierarchy_value >= hierarchy_value) {
            throw std::logic_error("mutex hierarchy violated");
        }
    }

    void update_hierarchy_value() {
        previous_hierarchy_value = this_thread_hierarchy_value;
        this_thread_hierarchy_value = hierarchy_value;
    }
};

// Использование:
HierarchyMutex mtx1(10);  // Высокий уровень
HierarchyMutex mtx2(5);   // Низкий уровень

// Правильный порядок: от высокого к низкому
mtx1.lock();
mtx2.lock();

Таблица рисков

Обнаружение Deadlock

// 1. ThreadSanitizer (компилятор флаг)
// g++ -fsanitize=thread program.cpp

// 2. Valgrind
// valgrind --tool=helgrind ./program

// 3. Логирование захвата мьютексов
class LoggingMutex {
private:
    std::mutex mtx;
    std::string name;

public:
    LoggingMutex(const std::string& n) : name(n) {}

    void lock() {
        std::cout << "Thread " << std::this_thread::get_id() 
                  << " locking " << name << "\n";
        mtx.lock();
        std::cout << "Thread " << std::this_thread::get_id() 
                  << " locked " << name << "\n";
    }
};

Итог: Deadlock требует минимум 2 мьютекса и 2 потока, но появляется только при циклических зависимостях. Предотвращай deadlock через: 1) единый порядок захвата, 2) std::lock для одновременного захвата, 3) ограничение критических секций, 4) использование timeout, 5) иерархию мьютексов. Тестируй с ThreadSanitizer и Valgrind.