介绍

是指两个或两个以上的进程在执行过程中，因争夺资源而造成的一种互相等待的现象，若无外力作用，它们都将无法推进下去。称此时系统处于死锁状态或系统产生了死锁。
也可以说：指在多道程序系统中，一组进程中的每一个进程均无限期地等待被该进程中的另一个进程所占用且永远不会释放的资源。处于死锁状态的进程称为死锁进程

举例

进程P1和P2在运行时都使用输入、输出设备，假定系统中只有一台输入设备，一台输出设备，则进程形式如下：

在多道程序环境下，多个进程同时运行，如下图，P1使用输入设备时，输出设备在空闲，可分配给P2进程使用

死锁过程

当进程P1申请并获得输入设备后(运行完①后)，由于进程切换或某种原因，停止前进(阻塞)，此时P2到达，P2完成对输出设备的申请(完成I后)，接下来申请输入设备(运行II)，由于设备被P1占用，导致P2被阻塞而进入等待状态。若P1进程重新获得运行机会，接下来要申请输出设备，而输出设备被P2占用，导致P1也进入阻塞状态。而P1和P2就这样进入无限地等待对方释放资源从而唤醒自己(等待与唤醒可查看的PV操作)，从而想入僵局

死锁产生的原因

• 竞争资源，系统资源在分配时出现问题，进程间对资源的相互争夺而造成僵局
• 多道程序运行时，进程推进顺序不合理(如PV操作，导致进程阻塞)

死锁产生的必要条件

• 互斥条件。一个资源只能被一个进程占用，其他进程要使用，只能等待该资源没有被其它进程占用
• 不可剥夺条件。在该进程为完成时，其它资源不能剥夺该进程对资源的使用权，只能等待该进程主动释放资源
• 请求和保持条件。进程需要先申请它所需要的一部分资源，得到后再去申请新的资源，在申请新的资源的时候，还保持着对已分配的资源占有
• 循环等待条件。发生死锁时，必然存在一个进程等待队列，如P1等待P2占用的资源.P2等待P3占用的资源...形成一个进程等待环路，即前一个进程占用后一个进程需要的资源

解决死锁的方法

• 预防死锁。破坏死锁发生的条件
• 避免死锁。在系统资源分配时，采用某种方法防止系统进入不安全模式(系统资源不满足对进程资源的需要量，即系统无资源可分配了)。
• 检测与解除死锁。在系统中设置检测机构，定时检测死锁是否发生
• 忽略死锁。对那些发生死锁的几率极低，而解决的代价太大或暂时没办法解决，暂时忽略

死锁预防

在系统运行时，采取措施，事先评估系统的可能性，防止死锁四个必然条件的同时发生。即防范于未然

破坏不可剥夺条件

一个等待的进程的全部资源可以被剥夺

方法如下

• 一个进程已占用某些资源，又要申请新的资源，但资源不能立即得到满足，转入等待状态，在进入等待状态前，释放其得到的所有资源
• 在一个进程申请资源时，检查这些资源是否可用，如不可用，则检查资源是否被等待资源占有。若是，则剥夺等待进程的所有资源，分配给该资源。如果资源没有被等待进程占有，则该进程将进入等待状态，进入前，剥夺全部资源

破坏请求和保持条件

• 在该进程执行前就申请所需要的全部资源
• 当进程没有占用资源时才允许它去申请资源

打破互斥

允许多个进程同时访问一个资源

打破循环等待

即对资源进行事先分类，按号分配

死锁的避免

思想

系统对进程发出的每一个系统能够满足的资源申请进行动态检查，并根据检查结果决定是否分配资源；如果分配后系统不会发生死锁，则予与分配，否则，不予分配。

安全状态与安全序列

安全状态

如果操作系统能保证所有的进程在有限时间内得到所需的全部资源，则称系统处于“安全状态”,

例子

现有12个同类资源供3个进程共享，进程P1总共需要9个资源，但第一次先申请2个;进程P2总共需要10个资源，第一次要求分配5个资源;P3总共需要4个资源第一次请求2个资源。经过第一次分配后，系统还有3个资源未分配

经过第一次分配后，系统状态如下

此时系统处于安全状态，可以把其中2个资源分配给进程P3，因为它只需要2个，待P3进程执行完后释放资源，归还资源4个，系统还剩下5个资源。可以分配给进程P2，P2结束释放资源，系统得到资源10个，最后分配给P1进程。这样三个进程都得到全部资源。其安全序列为P1，P2，P3

不安全状态，承上面例题最后

若进程P1提出再申请一个资源的要求，系统从剩余资源中分配1个给P1后剩余2个资源，如下表所示:

系统只剩下2个资源，把它分配给P3进程使用，P3进程释放后只有4个资源，不够P1和P2进程使用，不能在有限的时间内得到全部所需资源，找不到安全序列，系统从安全状态转到不安全状态，就会发生死锁

银行家算法

由Dijkastra提出的死锁避免算法

算法思想

把操作系统的各种资源比作周转资金，申请资源的进程比作向银行贷款的顾客。那么操作系统的资源分配问题就如同银行家利用其资金贷款的问题。
-方面银行家能贷款给若干顾客，满足顾客对资金的要求
另一方面，银行家可以安全地收回其全部贷款而不至于破产

规则如下

• 当一个顾客对资金的最大需求量不能超过银行家现有的资金时可接纳该顾客
• 顾客可以分期贷款，但贷款的总数不能超过最大需求量
• 当银行家现有的资金不能满足顾客尚需的贷款数额时，对顾客的贷款可推迟支付，但总能使顾客在有限的时间内得到贷款
• 当顾客得到所需的全部资金时，一定能在有限的时间内归还所有资金

进程说法

• 进程首先提出对资源的最大需求量
• 当进程在执行中每次执行中申请资源时，系统测试该进程占用的资源与本次申请的资源数之和不能超过该进程对资源的最大需求量，若超过拒绝分配
• 系统再测试系统现存资源能否满足该进程尚需的最大资源，若能，则分配，否则，推迟分配
• 保证再任何时刻至少由一个进程可以得到全部的资源而执行结束，执行结束后归还资源

例子1

假定系统中有五个进程{P1,P2,P3,P4，P5}和三类资源{A，B,C}，各种资源的数量分别为10、5、7，

资源第一次分配后情况如下所示。

安全序列为：P2、P4、P5、P3、P1，系统处于安全状态

应用该算法，还可找出安全序列P2、P4、P5、P1、P3，表明该系统状态安全，可以实施资源分配，如下图

如果此时P5又申请资源：A类3个、B类3个、C类0个。系统不能分配，因为超过当前系统剩余资源量。若此时P1申请：A类0个、B类2个、C类0个，系统也不能分配，因为新的系统状态，就不能分配了，导致系统进入不安全状态

不安全状态并非是死锁状态，只是有死锁的可能性

安全状态与不安全状态关系

系统中不存在安全序列，则称系统为不安全状态。
不安全状态不一定导致死锁，但死锁状态一定是不安全状态，即系统若处于不安全状态则可能会发生死锁

死锁避免和死锁预防的区别

死锁预防是破坏产生死锁的四个必要条件之一，严格地防止死锁的出现。
死锁避免是在系统运行过程中注意避免死锁的发生，即使死锁的必要条件存在，也不一定发生死锁。

求最少资源数

临界资源数 = 进程总数*(每个进程所需最大资源总数 - 1)     减一是为了保证进程至少有一个进程能得到全部所需资源，然后该进程结束释放资源，剩下的进程也可运行
最少资源数 = 临界资源数 + 1		//保证至少还有一个资源，系统不会发生死锁

例题1：

5个并发进程，每个进程需要3个A类资源，A类资源需要多少才保证系统不死锁？
解：由公式可得：5 * (3 - 1) = 10个
如果每个进程分配3个， 这个时候每个进程都不可以运行，如果这时系统还有1个资源，就能保证5个进程其中1个得到3个资源，该进程完成之后释放资源为3，剩下的进程也就可以运行完毕。

例题2：

一台计算机有8台磁带机，它们由N个进程竞争使用，每个进程可能需要3台磁带机。请问N为多少时，系统没有死锁危险
解：总资源数为8台，要向不发生死锁，则总资源数必须要大于进程所需最大资源数，即8 > n(3 - 1); n < 4时，都可以

参考

• 王陸-操作系统——死锁的概念以及死锁处理策略
• 多学就会融会贯通-死锁产生和避免及计算题
• 土味儿~-求多个进程并发运行时，不发生死锁时的最少共享资源数