死锁及其必要条件

1. 死锁的产生

死锁（Deadlock）是一个常见的并发编程问题，它发生在多个进程或线程之间，每个线程都持有资源并等待其他线程释放资源，导致所有线程都无法继续执行的情况。

下面是一个简单的例子。假设有 mutex1 和 mutex2 这两个互斥锁。

// 线程1
void thread1() {
    while (true) {
        ...
        mutex1.lock();
        mutex2.lock();
        /* do something ... */
        mutex1.unlock();
        mutex2.unlock();
        ...
    }
}

// 线程2
void thread2() {
    while (true) {
        ...
        mutex2.lock();
        mutex1.lock();
        /* do something ... */
        mutex1.unlock();
        mutex2.unlock();
        ...
    }
}

如果线程1在获取了 mutex1 之后被切换，随后线程2获取了 mutex2，这样，死锁就产生了。线程1无法继续获取 mutex2，线程2也无法继续获取 mutex1，程序进入循环等待。

死锁不一定只在多线程中出现，单线程下也可能出现死锁，比如下面的情况。

void thread1() {
    while (true) {
        ...
        mutex1.lock();
        /* do something ... */
        if (...)
            continue;
        mutex1.unlock();
        ...
    }
}

因为某些情况，线程在持有锁期间跳过了释放锁的代码，导致锁没有正确地释放，再次尝试加锁时，就会产生死锁。

产生死锁的四个必要条件

互斥条件：至少有一个资源同时只能被一个线程占用，即该资源具有互斥属性，其他线程在占用该资源时被阻塞。这意味着当一个线程占用了某个资源后，其他线程无法同时占用该资源。
请求与保持：线程在申请资源时，可以保持已占用的资源不释放。换句话说，一个线程在等待其他资源时，仍然持有已分配到的资源。
不可剥夺：已分配给线程的资源不能被强行剥夺，只能由持有者主动释放。这意味着其他线程无法抢占已被占用的资源，只能等待资源的主动释放。
循环等待：存在一个线程的资源申请序列，使得每个线程都在等待下一个线程所占用的资源。形成一个环路，导致循环等待。

2. 避免死锁

在产生死锁的四个必要条件中，互斥条件通常是必要的，往往不可破坏。因此，要避免死锁，可以从另外三个条件入手。

以下是操作系统中避免死锁的一些做法：

破坏请求与保持条件

进程在开始执行前，一次性申请所有需要的资源，而不是逐个申请。如果无法一次性获取所有资源，进程将释放已经占有的资源，并重新开始。
系统在分配资源时，要求进程在运行之前申请并获得所有需要的资源。只有当所有资源都可用时，才将它们分配给进程。
如果一个进程在等待某个资源时，发现自己占有的资源被其他进程所需要，可以释放已占有的资源，并重新申请所需的资源。

破坏不可剥夺条件

当一个进程在等待某个资源时，如果该资源被另一个进程所占用，并且当前进程的优先级更高，系统可以选择剥夺该资源，并将其分配给当前进程。
如果一个进程在等待某个资源时，可以回滚（撤销）该进程已经执行的操作，释放已占有的资源，以满足其他进程的需求。

破坏循环等待条件

对系统中的资源进行编号或排序，规定所有进程或线程只能按照一定的顺序请求资源，避免形成循环等待的环路。