死锁

deadlocks（死锁）

由于资源占用是互斥的，当某个进程提出申请资源后，使得有关进程在无外力协助下，永远分配不到必需的资源而无法继续运行，这就产生了一种特殊现象死锁。 

 一种情形，此时执行程序中两个或多个线程发生永久堵塞（等待），每个线程都在等待被其他线程占用并堵塞了的资源。例如，如果线程A锁住了记录1并等待记录2，而线程B锁住了记录2并等待记录1，这样两个线程就发生了死锁现象。

最好的死锁例子可能是Kansas立法机构于20世纪早期通过的一个法规，其中说到“当两列车在十字路口逼近时，它们要完全停下来，且在一列列车开走之前另一列列车不能启动。”
死锁－－在多道程序设计环境下，多个进程可能竞争一定数量的资源。一个进程申请资源，如果资源不可用，那么进程进入等待状态。如果所申请的资源被其他等待进程占有，那么该等待进程有可能无法改变状态。

a、互斥
至少有一个资源必须处于非共享模式；即一次只有一个进程使用。如果另一个进程申请该资源，那么申请进程必须延迟直到该资源释放为止。
b、占有并等待
一个进程必须占有至少一个资源，并等待另一资源，而该资源为其他进程占有。
c、非抢占
资源不能被抢占；即，只在进程完成其任务之后，才会释放其资源。

d、循环等待
有一组进程{P0，P1，...，Pn}，P0等待的资源为P1所占有，P1等待的资源为P2所占有，Pn-1等待的资源为Pn所占有，Pn等待的资源为P0所占有。
四个条件必须同时满足才会出现死锁，循环等待条件意味着占有并等待条件，这样四个条件并不完全独立。

出先死锁有四个必要条件。只要确保至少一个必要条件不成立，就能预防死锁的发生。

1、确保占有并等待条件不会在系统内出现。必须保证：当一个进程申请一个资源时，它不能占有其他资源。一种可以使用的协议是每个进程在执行前申请并获得所有资源。另外一种协议允许进程在没有资源时才可申请资源。
2、确保“非抢占”。为了确保这一条件不成立，可使用如下协议。如果一个进程占有资源并申请另一个不能立即分配的资源，那么其现已分配的资源都被抢占。
3、确保“循环等待”
确保此条件不成立的方法是对所有资源类型进行完全排序，且要求每个进程按递增顺序来申请资源。

银行家算法：
1),进程一开始向系统提出最大需求量.
2),进程每次提出新的需求(分期贷款)都统计是否超出它事先提出的最大需求量.
3),若正常,则判断该进程所需剩余剩余量(包括本次申请)是否超出系统所掌握的
剩余资源量,若不超出,则分配,否则等待.

如果一个系统既不采用死锁预防算法也不采用死锁避免算法，那么可能会出现死锁。在这种环境下，系统应提供：
1、一个用来检查系统状态从而确定是否出现了死锁的算法；
2、一个用来从死锁状态中恢复的算法。
方法：
a、每种资源类型只有单个实例
b、每种资源类型有多个单个实例的算法
c、应用检测算法

1、进程终止
a、终止所有死锁进程
b、一次只终止一个进程直到取消死锁循环为止
具体操作需注意：
1)选择中断顺序
2)进程的优先级
3)多少个进程需要计算，需要多长时间
4)进程使用的资源
5)进程完成还需要多少资源
6)多少个进程需要被中断
7)进程是交互的还是批处理
2、资源抢占
需要解决的问题：选择一个牺牲品、回滚、饥饿

死锁问题可用称为系统资源分配图的有向图进行更为精确地描述。这种图有一个节点的集合V和一个边的集合E组成。节点的集合V分成两种类型的节点＝{P0，P1，...，Pn}和R＝{R0，R1，...，Rn}。

如果图没有环，那么系统就没有进程死锁。如果图有环，那么可能存在死锁。

无限期阻塞问题或饥饿，即进程在信号量内无穷等待的情况。