Какое минимальное количество мьютексов необходимо для возникновения дедлока?

Минимальное количество мьютексов для возникновения дедлока — два.

Дедлок может произойти при соблюдении четырех условий (условия Коффмана):

1. Взаимное исключение (Mutual Exclusion): Ресурсы должны быть несовместно используемыми (non-shareable). В данном случае, мьютексы обеспечивают это.
2. Удержание и ожидание (Hold and Wait): Процесс, уже владеющий одним мьютексом, пытается захватить еще один мьютекс, который занят другим процессом.
3. Непередаваемость (No Preemption): Захваченный мьютекс не может быть принудительно отобран у процесса; он может быть освобожден только самим процессом.
4. Циклическое ожидание (Circular Wait): Существует цепочка процессов, где каждый процесс ожидает мьютекс, захваченный следующим процессом в цепочке, и последний процесс в цепочке ожидает мьютекс, захваченный первым процессом.

Пример с двумя мьютексами:

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

std::mutex mtx1;
std::mutex mtx2;

void thread1_func() {
    mtx1.lock(); // Поток 1 захватывает mtx1
    std::cout << "Thread 1 acquired mtx1" << std::endl;
    // Искусственная задержка, чтобы увеличить вероятность дедлока
    std::this_thread::sleep_for(std::chrono::milliseconds(100));
    mtx2.lock(); // Поток 1 пытается захватить mtx2 (возможно, уже занят Потоком 2)
    std::cout << "Thread 1 acquired mtx2" << std::endl;

    mtx2.unlock();
    mtx1.unlock();
}

void thread2_func() {
    mtx2.lock(); // Поток 2 захватывает mtx2
    std::cout << "Thread 2 acquired mtx2" << std::endl;
    // Искусственная задержка, чтобы увеличить вероятность дедлока
    std::this_thread::sleep_for(std::chrono::milliseconds(100));
    mtx1.lock(); // Поток 2 пытается захватить mtx1 (возможно, уже занят Потоком 1)
    std::cout << "Thread 2 acquired mtx1" << std::endl;

    mtx1.unlock();
    mtx2.unlock();
}

int main() {
    std::thread t1(thread1_func);
    std::thread t2(thread2_func);

    t1.join();
    t2.join();

    return 0;
}

В этом примере, если Поток 1 захватит mtx1, а Поток 2 захватит mtx2 почти одновременно, то Поток 1 будет ждать mtx2 (который занят Потоком 2), а Поток 2 будет ждать mtx1 (который занят Потоком 1). Возникает циклическое ожидание между двумя потоками и двумя мьютексами.