死锁及其必要条件
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. 避免死锁
在产生死锁的四个必要条件中,互斥条件通常是必要的,往往不可破坏。因此,要避免死锁,可以从另外三个条件入手。
以下是操作系统中避免死锁的一些做法:
破坏请求与保持条件
进程在开始执行前,一次性申请所有需要的资源,而不是逐个申请。如果无法一次性获取所有资源,进程将释放已经占有的资源,并重新开始。
系统在分配资源时,要求进程在运行之前申请并获得所有需要的资源。只有当所有资源都可用时,才将它们分配给进程。
如果一个进程在等待某个资源时,发现自己占有的资源被其他进程所需要,可以释放已占有的资源,并重新申请所需的资源。
破坏不可剥夺条件
当一个进程在等待某个资源时,如果该资源被另一个进程所占用,并且当前进程的优先级更高,系统可以选择剥夺该资源,并将其分配给当前进程。
如果一个进程在等待某个资源时,可以回滚(撤销)该进程已经执行的操作,释放已占有的资源,以满足其他进程的需求。
破坏循环等待条件
- 对系统中的资源进行编号或排序,规定所有进程或线程只能按照一定的顺序请求资源,避免形成循环等待的环路。