目录
死锁
什么是死锁
哲学家进餐问题中，如果5位哲学家进程并发执行，都拿起了左手边的筷子 每位哲学家都在等待自己右边的人放下筷子，这些哲学家进程都因等待筷子资源而被阻塞。即发生“死锁”
在并发环境下，各进程因竞争资源而造成的一种互相等待对方手里的资源，导致各进程都阻塞，都无法向前推进的现象，就是“锁” 发生死锁后若无外力干涉，这些进程都将无法向前推进。
死锁 饥饿 死循环的区别
饥饿 ： 长时间得不到想要的资源 进程无法继续
死循环: 程序员写的程序 进程执行的时候 一直跳不出某个循环
死锁必要条件
- 互斥
- 不可抢夺
- 循环与等待
- 请求和保持
发生死锁 一定循环等待 但循环等待时不一定发生死锁
什么时候发生死锁
- 系统资源的竞争 打印机
- 进程推进顺序非法 P1 P2 进程 占有R1 R2 资源后 又想占用对方拥有的资源
public class DeadLock {
private static Object lockA = new Object();
private static Object lockB = new Object();
public static void Thread1() throws InterruptedException {
synchronized (lockA) {
System.out.println("get lockA..........");
Thread.sleep(1000);
synchronized (lockB) {
System.out.println("get lockB.........");
}
}
}
public static void Thread2() throws InterruptedException {
synchronized (lockB) {
System.out.println("get lockB..........");
Thread.sleep(1000);
synchronized (lockA) {
System.out.println("get lockA.........");
}
}
}
public static void main(String[] args) throws InterruptedException {
Thread A = new Thread(new Runnable() {
@Override
public void run() {
try {
Thread1();
} catch (InterruptedException e) {
e.printStackTrace();
}
}
});
Thread B = new Thread(new Runnable() {
@Override
public void run() {
try {
Thread2();
} catch (InterruptedException e) {
e.printStackTrace();
}
}
});
A.start();
B.start();
}
}
运行结果: 程序永远不会结束
查看
使用 Jstack 22052
- 信号量的使用不当 生产者-消费者问题 实现互斥的P操作实现同步之前，就有可能导致死锁
死锁的处理策略
- 预防死锁。破坏死锁产生的四个必要条件中的一个或几个。
- 避免死锁。用某种方法防止系统进入不安全状态，从而避免死锁（银行家算法）
- 死锁的检测和解除。允许死锁的发生，不过操作系统会负责检测出死锁的发生，然后采取某种措 施解除死锁。
预防死锁
破坏互斥条件
把只能互斥使用的资源改造为允许共享使用，则系统不会进入死锁状态。比如：SPOOLing技术。 操作系统可以采用 SPOOLing技术把独占设备在逻辑上改造成共享设备。SPOOLing技术使得各个进程认为自己的请求被立即处理 而没有阻塞等待 实则放入另一个输出进程等待
改为共享
缺点:不是所有的资源都可以改造成可共享使用的资源 考虑到安全性 仍需要互斥
破坏不剥夺条件
方案一：当某个进程请求新的资源得不到满足时，它必须立即释放保持的所有资源，
方案二：当某个进程需要的资源被其他进程所占有的时候，可以由操作系统协助，将想要的资源强行剥夺
缺点:1. 实现比较复杂 2. 增加系统开销 3.容易造成进程饥饿
破坏请求和保持
进程在运行前一次申请完它所需要的全部资源，在它的资源未满足前，不让它投入运行。一旦投入运行后，这些资源就一直归它所有，该进程就不会再请求别的任何资源了该策略实现起来简单
一次性满足
缺点：造成资源浪费 有些进程可能只是保持很短事件
破坏循环等待条件
给系统中的资源编号，规定每个进程必须按编号递増的顺序请求资源，同类资源（即编号相同的资源）一次申请完。
即一个进程只有已占有小编号的资源时，才有资格申请更大编号的资源。按此规则，已持有大编号资源的进程不可能逆向地回来申请小编号的资源，从而就不会产生循环等待的现象。
小能往大走 大不能往小走
缺点:1. 不方便增加新设备 2. 实际申请顺序和编号可能不同
避免死锁
使用安全序列
如果系统按照这种序列分配资源，则每个进程都能顺利完成。只要能找出一个安全序列，系统就是安全状态。当然，安全序列可能有多个。分配了资源之后，系统中找不出任何一个安全序列，系统就进入了不安全状态。这就意味着之后可能所有进程都无法顺利的执行下去。
银行家算法
核心思想：在进程提出资源申请时，先预判此次分配是否会导致系统进入不安全状态。如果会进入不安全状态，就暂时不答应这次请求，让该进程先阻塞等待。
数据结构： 长度为m的一维数组
Available表示还有多少可用资源
n * m矩阵Max表示各进程对资源的最大需求数
n*m矩阵 Allocation表示已经给各进程分配了多少资源
Max - Allocation=Need矩阵表示各进程最多还需要多少资源
用长度为m的一位数组 Request表示进程此次申请的各种资源数
银行家算法步骤:
①检查此次申请是否超过了之前声明的最大需求数 ②检查此时系统剩余的可用资源是否还能满足这次请求 ③试探着分配，更改各数据结构 ④用安全性算法检查此次分配是否会导致系统进入不安全状态安全性算法步骤检查当前的剩余可用资源是否能满足某个进程的最大需求，如果可以，就把该进程加入安全序列，并把该进程持有的资源全部回收。 不断重复上述过程，看最终是否能让所有进程都加入安全序列
安全性算法步骤： 检查当前的剩余可用资源是否能满足某个进程的最大需求，如果可以，就把该进程加入安全序列，并把该进程持有的资源全部回收。 不断重复上述过程，看最终是否能让所有进程都加入安全序列。
检测和解除
没有预防死锁 或者 避免死锁的话 系统应该提供下面2个算法
①死锁检测算法：用于检测系统状态，以确定系统中是否发生了死锁。 ②死锁解除算法：当认定系统中已经发生了死锁，利用该算法可将系统从死锁状态中解脱出来
可利用有向图这一数据结构保存资源的请求和分配信息 提供一种算法，利用上述信息来检测系统是否已进入死锁状态。
如果最终能消除所有边，就称这个图是可完全简化的。此时一定没有发生死锁（相当于能找到一个安全序列） 如果最终不能消除所有边，那么此时就是发生了死锁
解除
- 资源剥夺法。挂起（暂时放到外存上）某些死锁进程，并抢占它的资源，将这些资源分配绐其他的死锁进程。但是应防止被挂起的进程长时间得不到资源而饥饿
- 撤销进程法（或称终止进程法）。强制撤销部分、甚至全部死锁进程，并剥夺这些进程的资源。这种方式的优点是实现简单，但所付出的代价可能会很大。因为有些进程可能已经运行了很长时间，已经接近结束了，一旦被终止可谓功亏一篑，以后还得从头再来。
- 进程回退法。让一个或多个死锁进程回退到足以避免死锁的地步。这就要求系统要记录进程的历史信息，设置还原点。
应该考虑
- 进程优先级
- 已执行多长时间
- 还要多久能完成
- 进程已经使用了多少资源
- 进程是交互式的还是批处理式的
