目录

一、引言

二、死锁基本概念与必要条件

三、经典死锁场景分析

3.1 哲学家就餐问题

3.2 违反锁顺序原则

四、死锁的处理策略

4.1 破坏互斥条件

4.2 破坏请求与保持条件

4.3 破坏不可剥夺条件

4.4 破坏循环等待条件

五、死锁的避免

5.1 资源排序策略

5.2 银行家算法

六、结语

---

一、引言

前几天在Boss直聘上看到这样一个帖子：

面试官：你告诉我什么是死锁就给你发offer。

面试者：你给我offer我就告诉你什么是死锁。

于是，我就决定写下这篇文章。

二、死锁基本概念与必要条件

假设，张三是你多年未联系的朋友。在一个天昏地暗的下午，你从睡梦中醒来，打开手机查看微信消息，看到张三给你发了条信息，“兄弟，能不能先借我100块钱，没钱交房租了，下个月发工资了还你。”你心里想着，毕竟大家朋友一场，况且他下个月发工资了就还，于是你立马给他转了100块。

过了一个月，约定还钱的日期到了。

那天早上你一起床就急忙打开手机，看好兄弟张三有没有把钱还你。可是，微信上唯一的红点是“微信记账本”，昨日支出：xxx元。你心里想，应该是他还没起床。

时间很快就到了晚上，还是迟迟没有收到张三的信息。你心里想，也许是他不小心忘了。于是你决定第二天中午问一下他。

到了第二天中午。

你：兄弟，我现在手头紧，食堂的饭都快吃不起了，你看能不能把那100块钱先还我。

张三：对不住了兄弟，我现在手上也没钱，不过你别担心，有个朋友前几天借了我几百块钱，等他还我了，我再把借你的100块钱还给你。

你：……

大费周章的举了上面的例子，没有个人情绪（无奈），主要是让大家对进程死锁有一个感性的认识。下面，正式提出进程死锁的概念。

在操作系统中，进程死锁是指两个或多个进程在执行过程中，因争夺资源而造成的相互等待的现象。这些进程在无外力帮助的情况下，都无法继续推进。这时候，死锁就产生了。

不过，死锁的产生也是有条件的，以下四个条件缺一不可：

1. 互斥条件：资源每次只能被一个进程使用。
2. 请求与保持：进程在申请新资源的同时保持对已有资源的占有。
3. 不可剥夺：进程已获得的资源在未使用完之前，不能被其他进程强行剥夺，只能由该进程显示释放。
4. 循环等待：存在一个进程资源的循环等待链，链中每个进程已获得的资源被链中下一个进程所请求。

明白了死锁的概念以后再回过头看上面的例子——你等张三还钱，张三等他的朋友还自己钱，然后才有钱还你。它并没有形成闭环，但是存在一个等一个的情况。对于进程来说，一个等一个的情况就是这些进程都阻塞了。

三、经典死锁场景分析

3.1 哲学家就餐问题

网上找的图基本都是圆桌的，虽然图片精美，但不是很好理解，所以自己花了一个展开图。

哲学家问题是这样子的，5位哲学家，5根筷子，在进餐时所有哲学家同时拿起自己左手边的筷子，但是哲学家们发现只有一根筷子吃不了，于是右手都在等着拿到右边的筷子，如下图：

每位哲学家都在等待右手边的筷子，但是所有哲学家右手边的筷子又都被不同的哲学家占有不放，于是就构成了上图中的循环等待。此刻，死锁形成。

3.2 违反锁顺序原则

下面写一段代码演示一下这种死锁的情况。

#include <pthread.h>
#include <stdio.h>
#include <unistd.h>

// 定义两个互斥锁
pthread_mutex_t mutex1 = PTHREAD_MUTEX_INITIALIZER;
pthread_mutex_t mutex2 = PTHREAD_MUTEX_INITIALIZER;

void* thread1_function(void* arg) {
    pthread_mutex_lock(&mutex1);   // 线程1获取mutex1
    printf("Thread 1 acquired mutex1\n");
    sleep(1); // 让出CPU，模拟线程切换

    pthread_mutex_lock(&mutex2);   // 线程1尝试获取mutex2
    printf("Thread 1 acquired mutex2\n");

    // 临界区代码（操作共享资源）

    // 按相反顺序释放锁
    pthread_mutex_unlock(&mutex2);
    pthread_mutex_unlock(&mutex1);
    return NULL;
}

void* thread2_function(void* arg) {
    pthread_mutex_lock(&mutex2);   // 线程2获取mutex2
    printf("Thread 2 acquired mutex2\n");
    sleep(1); // 让出CPU，模拟线程切换

    pthread_mutex_lock(&mutex1);   // 线程2尝试获取mutex1
    printf("Thread 2 acquired mutex1\n");

    // 临界区代码（操作共享资源）

    // 按相反顺序释放锁
    pthread_mutex_unlock(&mutex1);
    pthread_mutex_unlock(&mutex2);
    return NULL;
}

int main() {
    pthread_t thread1, thread2;

    pthread_create(&thread1, NULL, thread1_function, NULL);
    pthread_create(&thread2, NULL, thread2_function, NULL);

    pthread_join(thread1, NULL);
    pthread_join(thread2, NULL);

    printf("Both threads completed\n");
    return 0;
}

运行结果（可能，由于线程调度顺序不一定每次都能制造死锁）：

线程1获取mutex1，线程2获取mutex2。

然后线程1尝试获取mutex2（但是被线程2持有），线程2尝试获取mutex1（但是被线程1持有）。

两者互相等待，形成死锁。

上面这两个案列，对比死锁的形成条件，它们都满足。

四、死锁的处理策略

上面演示了两种形成死锁的情况，下面讨论如何解决死锁。

我们知道，死锁产生是有条件的，4个，而且缺一不可。所以，我们只要破坏这四个条件中的一个或多个，就可以打破死锁。

4.1 破坏互斥条件

互斥条件说的是，资源每次只能被一个进程使用。那么如果将资源变成共享资源，也就是说一次可以被多个进程所访问，这样就可以避免死锁了，但是这么做的话不一定妥当。比如多个进程往同一个文件里写入数据，我们加锁是为了避免数据混乱，如果此时把这个锁给去掉了，虽然是不会产生死锁了，但是这种方式所带来的结果不是我们想要的。

4.2 破坏请求与保持条件

请求与保持条件说的是，进程在申请新资源时保持对已有资源的占有。进程至少持有了一个资源，但是又提出申请新资源的请求，但是申请的资源在被其他进程占有，进而导致申请新资源的进程阻塞。

导致进程阻塞的根本原因是它所需要的资源系统未给它准备好。所以我们就可以采用静态分配资源的方法，也就是说在进程启动之前就要为它准备好整个运行过程中所需要的资源。如果资源没有全部就位，那么就不让该进程启动。这样就不会阻塞了，也就不会产生死锁。

但是这种静态分配资源的做法，有很明显的不足。比如进程A，它对某一个资源的使用的时间其实很短，也就是占进程A总运行时间的一小小部分。但是该资源在进程A运行的整个过程中，其他进程是不能够使用的。这么做，一来对资源的利用率低，二来就是可能会导致一些进程饥饿。该资源本来可以继续被其他进程使用的，但是进程A在整个运行过程中使用完毕后还占用它，需要它的进程就只能等待进程A将该资源释放。

4.3 破坏不可剥夺条件

不可剥夺条件说的是，进程已获得的资源在未使用完之前，不能被其他进程强行剥夺，只能由它显示释放。所以为了破坏不可剥夺条件，有如下两种做法。

第一，当进程A请求某个资源，而该资源正在被其他进程占用，那么进程A应该立即释放自己持有的资源，即使这些资源未使用完毕。

第二，进程A申请某个资源，该资源被进程B持有，操作系统可以对这个请求的合理性做出判断，如果觉得合理（比如进程A的优先级更高），那么操作系统就应该剥夺进程B持有这个资源的权利，然后将该资源分配给进程A。

4.4 破坏循环等待条件

循环等待条件说的是，存在一个进程资源循环等待链，链中每个进程已获得的资源被链中下一个进程所请求。为了破坏循环等待条件，可以采用顺序资源分配法。

所谓顺序资源分配法，其核心思想是通过限制进程请求资源的顺序，来破坏循环等待条件。做法是，系统对所有的资源进行编号，进程在请求资源时只能申请比已分配资源编号大的资源。可能不太好理解，下面举个例子说明一下。

假设系统中有三种资源：R1、R2和R3，它们的编号分别为1、2和3。进程A已经分配到了R1，那么它接下来只能请求R2或R3，而不能请求R1。如果进程B已经分配到了R2，它只能请求R3，不能请求R1或R2。这样，就不可能出现进程A等待R2，而进程B等待R1的情况，从而避免了循环等待条件的出现。这个例子中，进程A是有可能要申请R2，但是由于R2已经被其他进程持有导致进程A阻塞，但是这种阻塞不是永久的，因为这种等待不是循环等待，一旦进程B执行完毕释放R2，进程A就有机会拿到R2。

五、死锁的避免

5.1 资源排序策略

资源排序策略就是上面讲到的资源顺序分配法。通过限制进程申请资源的顺序，破坏形成死锁条件之一的循环等待条件。

5.2 银行家算法

在介绍银行家算法之前，首先介绍一个概念——安全序列。

假设有一批进程p1，p2，p3，系统按照p2--->p1--->p3的顺序依次执行每个进程，不会出现死锁，那么这个执行序列就可以称为安全序列。如果系统按照安全序列去执行每一个进程，那么系统就会处于安全状态，安全状态下一定不会发生死锁。

其次，举例说明如何确定安全序列。

假设系统中有3类资源：A、B、C，其可用数量分别为10、5、4。系统中有3个进程P₀、P₁、P₂它们对资源的最大需求和已分配资源情况如下表：

进程	最大需求	已分配资源
P₀	（7，5，3）	（0，1，0）
P₁	（3,   2,  2）	（2，0，0）
P₂	（9，0，2）	（3,   0,  2）

 

 

 

 

 

减去上面分配的资源后，系统当前可用的资源为：（5, 4, 2）

检查每个进程的需求数量：计算每个进程还需要的资源数量，即最大需求减去已分配资源。

P₀还需要：(7, 4, 3)

P₁还需要：(1, 2, 2)

P₂还需要：(6, 0, 0)

寻找可以安全完成的进程：寻找一个进程，它的需求数量小于或等于当前可用资源数量。如果找到，就假设该进程完成并释放其已分配的资源，更新可用资源数量，然后继续寻找下一个可以安全完成的进程。

第一次寻找：p1的需求数量为(1, 2, 2)，小于等于可用资源，可以安全完成。假设P₁完成，释放其已分配资源(2, 0, 0)，更新可用资源为(7, 4, 2)。

第二次寻找：p2的需求数量为(6, 0, 0)，小于等于可用资源，可以安全完成。假设P2完成，释放其已分配资源(3, 0, 2)，更新可用资源为(10, 4, 4)。

第三次寻找：p0的需求数量为(7, 4, 3)，小于等于可用资源，可以安全完成。假设P0完成，释放其已分配资源(0, 1, 0)，更新可用资源为(10, 5, 4)。

所以，p1--->p2--->p0就是一个安全序列。

之所以要求进程需求资源的数量小于或等于当前可用资源的数量，是因为如果剩余的资源数量不能满足该进程的话，就算把资源分配给它，它也依然因为资源不满足而阻塞，剩余的进程也因为没有请求到所需要的资源而阻塞，这就可能会导致死锁。

最后，正式介绍银行家算法。其实，前面的内容就是银行家算法的核心了。

银行家算法是一种预防死锁的算法，它通过保证系统处于安全状态来避免死锁的发生。保护系统处于安全状态的做法就是按照安全序列依次执行进程。

六、结语

如有错误，恳请指出！

---

完~