什么是死锁
死锁是指两个或两个以上的进程在执行过程中，由于竞争资源或者由于彼此通信而造成的一种阻塞的现象，若无外力作用，它们都将无法推进下去。此时称系统处于死锁状态或系统产生了死锁，这些永远在互相等待的进程称为死锁进程
系统模型
进程在使用资源之前必须先申请资源，在使用资源之后要释放资源。进程所申请的资源数量不能超过系统所有资源的总量。
在正常操作模式下，进程只能按如下顺序使用资源：
①申请：如果申请不能立即被允许，那么申请进程必须等待，直到它获得该资源为止。
②使用：进程对资源进行操作。
③释放：进程释放资源
死锁发生的必要条件
下面四个同时满足就会死锁
- 互斥：至少有一个资源处于非共享状态（即一次只有一个进程能使用这个资源）
- 占优并等待：一个进程必须占有一个资源，并且等待一个被其他进程占有的另一个资源。
- 非强占：资源不能被强占，即资源只能在进程完成后自动释放
- 循环等待：第二条的情况循环发生，即P0等待的资源被P1占有，P1等待的资源被P2占有…Pn等待的资源被P0占有
资源分配图
系统资源分配图是一种用于精确描述死锁问题的有向图，这个图的点有两类
- 系统活动进程的集合P
- 系统所有资源类型的集合
表示方法：
进程Pi已经申请了Rj的一个实例，并正在等待该资源：Pi->Rj,称为申请边
资源类型Rj的一个实例已经分配给了进程Pi：Rj->Pi，称为分配边
申请边和分配边不同时存在与两点之间，当该申请可以得到满足时，申请边立即转换为分配边
根据资源分配图的定义，可以用该图简单的判断是否有死锁：
如果资源分配图没有环，那么一定没有死锁
如果资源分配图有环，那么如果所有的资源只有一个实例，那么一定会发生死锁。
如果资源分配图有环，但一些资源的实例不止一个，那么不一定会发生死锁。
死锁处理方法
从原理上，有一下几种方法：
使用协议预防和避免死锁，确保系统不会进入死锁
允许系统进入死锁状态，但能检测它，并加以恢复
忽视这种问题，认为死锁不可能在系统内发生（多为操作系统采用的方法）
死锁预防
死锁预防是确保死锁发生的必要条件不全被满足，每个条件都可以采取一些手段来避免
互斥->共享资源
通常不能通过否定互斥条件来预防死锁，有的资源本身就是非共享的
占有并等待
为了确保这一条件不发生，需要保证：当一个进程申请一个资源的时候，它不能占有其他资源，对于这一要求，有以下协议可以采用：
每个进程在开始的时候就申请所有需要的资源，从而确保如果一个进程如果无法申请到应得的资源就不会调用。（实现要求申请资源的系统调用在所有其他系统调用之前进行）
要求进程在没有资源时才能申请资源。一个进程在任意时刻都能申请资源，但必须确保他释放了其他的资源。(用完就丢)
这两种协议的有两个主要缺点：
资源利用率低，许多资源可能已分配，但很长时间没有被使用
可能导发生饥饿，如一个进程需要多个资源，但因为有一个资源没有办法申请而永久等待
非抢占
为了确保这一条件，有一个协议可以解决：
如果一个进程申请了另一个不能立即分配的资源，处于等待状态，那么这个进程现已分配的其他任何资源都可被抢占
循环等待
这是最后一个条件，要确保此条件不成立的方法是对所有资源类型进行完全排序。并要求每个进程按递增顺序申请资源。
给所有的资源分配一个不同的整数，以进行排序，一个进程开始的时候可以申请任意资源，假设资源对应的整数是Ri，那么其后申请的任意资源Rj必须满足Rj > Ri,除非Ri得到释放
死锁预防普遍的副作用是低设备利用率和系统吞吐率。
安全状态
安全序列:
如果系统能按某个顺序为每个进程分配资源（不超过最大值）并能避免死锁，那么系统状态就是安全的，即如果存在一个安全序列，那么系统就处于安全状态。否则系统处于不安全状态
不安全状态不是死锁状态，两者是包含于被包含的关系。
可以通过一个实例来看一下安全状态和不安全状态
| 进程 | 最大需求 | 情况1（安全） | 情况2（不安全） |
|---|---|---|---|
| P0 | 10 | 5 | 5 |
| P1 | 4 | 2 | 2 |
| P2 | 9 | 2 | 3 |
假设现在的最大资源总数为12，情况1时系统处于安全状态。情况2时是危险状态
死锁恢复
- 简单的终止一个到多个进程以打破循环
- 从一个或多个进程中强占资源
进程终止
进程终止后，这个进程占有的所有资源都会被回收。
以及进程终止有两种方式：
终止所有产生死锁的进程。这样可以保证终止了死锁，但是很明显代价很大，因为恢复后可能很多计算过程都需要重新完成。
一次终止一个进程直到死锁状态被打破。但这种方法开销很大，因为每结束一个进程，都需要调用检测算法检查进程是否仍然处于死锁中。
因此如何终止进程是一个经济问题，也就是如何让进程终止后的代价最小化，这需要考虑多个方面，包括但不限于：进程优先级、进程已执行时间、进程当前使用资源数，进程最大资源需求、进程是否交互、需要终止的进程数量。
资源抢占
通过抢占一个进程的资源给其他进程，从而一步步打破死锁。这一个办法需要处理的问题有三个：
选择一个牺牲品。要抢占资源，需要判断抢占哪一个进程的资源，这同样是一个“代价最小”的问题。
回滚。当一个进程被另一个进程抢占资源的时候，需要对该进程进行一定的处理，很显然因为缺少资源，该进程不能正常执行，那么就需要让该进程回滚到一个状态以便最后能重新执行。
饥饿。当基于一个策略来判断谁来作为被抢占资源的进程时，同一个进程很容易被反复选中作为被抢占资源的进程（破窗效应），这是抢占资源的算法需要考虑的问题。一个方法是在代价因素中加入一个进程的回滚次数。