Как можно избежать deadlock?

Как избежать Deadlock

Dead lock — это ситуация, когда два или более потока ждут друг друга и неспособны продолжить выполнение. Это критическая ошибка в многопоточных приложениях. Существуют проверенные стратегии для избежания deadlock.

Условия deadlock (все 4 должны быть верны)

1. Mutual Exclusion — ресурс не может использоваться двумя потоками одновременно
2. Hold and Wait — процесс держит ресурс и ждёт другой
3. No Preemption — ресурс нельзя отобрать насильно
4. Circular Wait — циклическая цепочка зависимостей

Стратегия 1: Установить порядок захвата (BEST)

Самый надёжный способ — всегда захватывать мьютексы в одном порядке:

#include <mutex>
#include <thread>

class Account {
private:
    int id;
    double balance;
    mutable std::mutex lock;
public:
    Account(int id, double balance) : id(id), balance(balance) {}
    
    // ПЛОХО - deadlock возможен
    void transferUnsafe(Account& other, double amount) {
        std::lock_guard<std::mutex> lock1(this->lock);
        std::this_thread::sleep_for(std::chrono::milliseconds(1));
        std::lock_guard<std::mutex> lock2(other.lock);  // Может повиснуть
        
        this->balance -= amount;
        other.balance += amount;
    }
    
    // ХОРОШО - всегда захватываем в порядке ID
    void transfer(Account& other, double amount) {
        Account& first = (this->id < other.id) ? *this : other;
        Account& second = (this->id < other.id) ? other : *this;
        
        std::lock_guard<std::mutex> lock1(first.lock);
        std::lock_guard<std::mutex> lock2(second.lock);
        
        this->balance -= amount;
        other.balance += amount;
    }
};

int main() {
    Account a(1, 1000);
    Account b(2, 500);
    
    std::thread t1([&] { a.transfer(b, 100); });
    std::thread t2([&] { b.transfer(a, 50); });
    
    t1.join();
    t2.join();
    // Deadlock невозможен, т.к. порядок всегда: 1->2
    return 0;
}

Стратегия 2: std::lock - одновременный захват

#include <mutex>

class Account {
private:
    int id;
    double balance;
    mutable std::mutex lock;
public:
    void transfer(Account& other, double amount) {
        // std::lock захватывает оба мьютекса атомарно
        // Избегает deadlock автоматически
        std::lock(this->lock, other.lock);
        
        std::lock_guard<std::mutex> lock1(this->lock, std::adopt_lock);
        std::lock_guard<std::mutex> lock2(other.lock, std::adopt_lock);
        // std::adopt_lock говорит, что мьютекс уже захвачен
        
        this->balance -= amount;
        other.balance += amount;
    }
};

Стратегия 3: Timeout при захвате

Если можно повторить операцию, используй try_lock_for:

std::mutex mtx1, mtx2;

bool safeTransaction() {
    using ms = std::chrono::milliseconds;
    
    std::unique_lock<std::mutex> lock1(mtx1, std::defer_lock);
    std::unique_lock<std::mutex> lock2(mtx2, std::defer_lock);
    
    // Ждём до 100мс на каждый мьютекс
    if (!lock1.try_lock_for(ms(100))) {
        return false;  // Не смогли захватить - повторим позже
    }
    if (!lock2.try_lock_for(ms(100))) {
        return false;  // Отпустим lock1, повторим
    }
    
    // Успешно захватили оба
    return true;
}

Стратегия 4: Минимизировать критическую секцию

// ПЛОХО - deadlock может произойти в long_operation()
std::lock_guard<std::mutex> lock(mtx);
long_operation();  // Занимает много времени
accessing_shared_data();

// ХОРОШО - критическая секция минимальна
int result;
{
    std::lock_guard<std::mutex> lock(mtx);
    result = reading_shared_data();
}
long_operation();  // Вне критической секции
process_result(result);

Стратегия 5: Использовать read-write мьютекс

#include <shared_mutex>

class Cache {
private:
    mutable std::shared_mutex rwLock;
    std::unordered_map<std::string, std::string> data;
public:
    // Множество читателей могут работать одновременно
    std::string get(const std::string& key) const {
        std::shared_lock<std::shared_mutex> lock(rwLock);
        auto it = data.find(key);
        return (it != data.end()) ? it->second : "";
    }
    
    // Только один писатель
    void set(const std::string& key, const std::string& value) {
        std::unique_lock<std::shared_mutex> lock(rwLock);
        data[key] = value;
    }
};

Стратегия 6: Использовать lock-free структуры

#include <atomic>
#include <queue>

class LockFreeQueue {
private:
    struct Node {
        int value;
        std::atomic<Node*> next;
    };
    std::atomic<Node*> head;
public:
    // Нет мьютексов - нет deadlock!
    void push(int value) {
        Node* newNode = new Node{value, nullptr};
        Node* oldHead;
        do {
            oldHead = head.load();
            newNode->next = oldHead;
        } while (!head.compare_exchange_weak(oldHead, newNode));
    }
};

Стратегия 7: Избегать nested locks

// ПЛОХО - nested locking
std::lock_guard<std::mutex> lock1(mtx1);
{
    std::lock_guard<std::mutex> lock2(mtx2);  // Вложенный
    // Если нить 2 делает обратно - 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);

Стратегия 8: Thread-safe по дизайну

// Используй immutable объекты где можно
class ImmutableConfig {
private:
    const int maxConnections;  // const - не нужны мьютексы
    const std::string hostName;  // const
public:
    ImmutableConfig(int max, const std::string& host)
        : maxConnections(max), hostName(host) {}
    
    int getMaxConnections() const { return maxConnections; }
    std::string getHost() const { return hostName; }
    // Нет deadlock - нет shared mutable state!
};

Практический чек-лист

✅ ДА:

• Всегда захватывай мьютексы в одном порядке
• Используй std::lock для одновременного захвата
• Минимизируй размер критической секции
• Используй read-write мьютексы где возможно
• Документируй порядок захвата (например, в comments)

❌ НЕТ:

• Не захватывай A потом B в одном месте, B потом A в другом
• Не вызывай функции, требующие других мьютексов, внутри критической секции
• Не полагайся на timeout как на основное решение
• Не используй recursive_mutex без веских причин

Тестирование на deadlock

# Thread Sanitizer обнаружит потенциальные deadlock
g++ -g -fsanitize=thread program.cpp
./a.out

# Stress тестирование
for i in {1..1000}; do ./a.out; done

Избежание deadlock требует дисциплины и понимания порядков захватов. Главное правило: всегда захватывай ресурсы в одном и том же порядке.