堵车就是一种死锁，这时候谁倒车就是一个问题。

死锁的特征

发生死锁时，进程永远不能完成，系统资源被阻碍使用，以至于阻止了其他作业开始执行。
下面是一段互斥锁的死锁代码

/* 创建互斥锁并初始化 */
pthread_mutex_t first_mutex;
pthread_mutex_t second_mutex;

pthread_mutex_init(&first_mutex, NULL);
pthread_mutex_init(&second_mutex, NULL);
/* thread 1 在如下进程中 */
void* do_work_one(void *param){
	pthread_mutex_lock(&first_mutex);
	pthread_mutex_lock(&second_mutex);

	pthread_mutex_unlock(&second_mutex);
	pthread_mutex_unlock(&first_mutex);

	pthread_exit(0);
}
/* thread 2 在如下进程中 */
void* do_work_two(void *param){
	pthread_mutex_lock(&second_mutex);
	pthread_mutex_lock(&first_mutex);

	pthread_mutex_unlock(&first_mutex);
	pthread_mutex_unlock(&second_mutex);

	pthread_exit(0);
}

在这例子中：thread 1 获取互斥锁的顺序是 first_mutex second_mutex
thread 2 获取互斥锁的顺序是 second_mutex first_mutex
如果 thread 1 获得了 first_mutex 且 thread 2 获得了 second_mutex ，那么就有可能发生死锁。
然而这不一定会发生 因为线程的运行顺序需要由 CPU 调度决定，因此死锁的发生是不确定的事情，检测上存在难度。

必要条件

互斥：至少有一个资源处于非共享模式，一次只能有一个进程使用
占有等待：一个进程占有至少一个资源，并等待另一个资源。
非抢占：资源不能被抢占，需要进程完成后自愿释放。
循环等待：占有并等待条件
资源分配图

如果分配图存在环，那么可能出现死锁。

死锁的处理方法

通过协议预防或者避免死锁
允许系统进入死锁，但是通过检测加以恢复
忽视这个问题，死锁是不会发生的
然而，编写操作系统给予了程序员充分的信任，认为这是不会发生的。这无疑对程序员提出了更高的要求
死锁预防
显然，死锁的发生需要有四个必要条件同时发生，只要确保一个条件不成立就能预防死锁的发生。
互斥
互斥条件是死锁发生的必要条件，必须成立。至少有一个资源是非共享的，可共享资源不要求互斥访问，因此不会参与死锁。然而，不能通过否定互斥条件来预防死锁，因为有些资源本身就是非共享的。
持有并等待
实现方式是在开始执行前申请并获得所有资源。或者，只允许进程在没有资源时才能申请资源。

这种方式的问题是，资源利用率较低，而且需要资源较多的进程可能发starvation。

无抢占

当一个进程请求一个资源但是没有立刻得到满足时，它必须释放已经持有的所有资源；直到它需求的所有资源（包括刚才释放的那些资源）都可用时才能一并获取它们并继续执行。

但是互斥锁，信号量之类的资源也不能这样用；同时也会降低资源利用率。

循环等待

对所有资源类型进行排序，要求每个进程按照递增顺序申请资源。

比如，F(磁带驱动器) < F(打印机)，象征着磁带驱动器需要在打印机调用前先调用。

程序员需要保证按照这个顺序申请资源，也就是说如果程序员不听话，还是会发生死锁。这种方法也可能影响资源利用率。

死锁避免

避免死锁需要一些额外信息，例如进程未来需要使用哪些资源、资源的使用顺序等。在每次请求到来时，即使对应资源可用，系统也应该结合现有可用资源、现有已分配资源以及各个进程未来申请和释放的资源，考虑是否让这个请求等待从而避免未来可能的死锁。

不同模型可能对上述额外信息有不同的需求。最简单且最有用的模型维护这样的 资源分配状态 (resource allocation state):

每个进程声明可能对每种资源类型的 最大需求 (maximum demands)
当前系统的 available 和 allocated 的资源数目。
安全状态 | Safe State
如果系统能够按照一定顺序为每个进程分配资源，同时避免死锁，那么系统就处在 安全状态
安全序列是指：对于每个进程，进程仍然可以申请的资源数小于当前可用资源加上前面所有进程申请过的资源。

如下图，P1，P0，P2满足安全条件，因此是安全的

根据这一概念，我们可以这样定义死锁避免的算法：起初，系统处于安全状态。当有进程申请一个可用资源时，系统应确定，如果立刻进行这一分配后系统仍处于安全状态则可以分配，否则应当让进程等待。

资源分配图算法

这种算法适用于每种资源类型只有 1 个实例的情况。
我们在资源分配图的基础上增加一种边，叫 claim edge（需求边），表示某个进程未来可能会需求某种资源，用虚线表示。

当这个需求真的出现的时候，claim edge 转为 request edge；当需求被满足的时候，request edge 转为 assignment edge；当该进程释放该资源时，assignment edge 转为 claim edge。
当一个需求来了的时候，如果 request edge 转为 assignment edge 不会导致图中有一个环，注意环的检测需要 n^2 的时间复杂度，则该要求可以被满足；否则该请求应当等待。

银行家算法

银行家算法的实质就是要设法保证系统动态分配资源后不进入不安全状态，以避免可能产生的死锁。即进程提出资源请求且系统的资源能够满足该请求时，系统将判断满足此次资源请求后系统状态是否安全，如果判断结果为安全，则给该进程分配资源，否则不分配资源，申请资源的进程将阻塞。

下面是一个练习的例子：T1->T3->T4->T0->T2，系统安全。

死锁检测

每种资源类型是有单个实例

使用资源分配图的变形（wait-for 图)

在右图里找环，有的话就会死锁，最坏时间复杂度n^2

每种资源类型是有多个实例

类似银行家算法，不多赘述。
如果找不到任何安全序列，则说明系统处于死锁状态。

死锁恢复

进程终止

终止进程并不简单，它需要维护终止时的状态，并且有可能需要重新计算一些内容，同时还需要避免产生重复的副作用（如输出）；这需要花费很多时间。

终止所有死锁进程：花销很大，有些死锁程序已经运行了较长的时间，这部分内容也需要舍弃
一次终止一个，直到没有死锁：开销大，每次删掉一个就要调用死锁检测算法。
同时后者需要考虑的是，如何选择放弃的进程？应当根据具体情况，参考如下指标选择造成的代价最小的进程来终止：
进程的优先级
已经算了多久，还要算多久
用了哪些、多少资源，是否容易抢占
还需要多少资源
终止这一进程的话还需要终止多少进程
进程是交互的还是批处理的
资源抢占
不断抢占资源给其他进程用，直到消除死锁环为止。

选择牺牲进程 (Select a victim)。抢占哪些进程的哪些资源？这和前一节的讨论差不多。
回滚 (Rollback)。当一个进程的若干资源被抢占，我们需要将这个进程回滚到某个安全状态，即回滚到申请那些被抢占的资源之前。
不过一般来说，很难确定什么是安全状态，最简单的方案就是完全回滚，也就是终止进程并重新执行。回滚到足够打断死锁的状态更加经济，但是需要系统保存更多资源。
饥饿 (Starvation)。如何保证不会永远从一个进程中抢占资源？在代价评价中增加回滚次数，也类似于 priority aging。