一、基本概念
2.1 死锁的概念
死锁指的是多个进程/线程循环等待其它地方占有的资源而无限地僵持下去的局面,其根本原因是对有限资源的操作不当。
举一个简单的例子:线程A
执行一段代码时首先获取了锁Lock1
,而与此同时线程B
执行一段代码时获取了锁Lock2
,那么当线程A
接下来要执行一段需要获取锁Lock2
的代码时,发现该锁已经被线程B
持有了它就会等待,而线程B
又恰巧需要执行一段需要获取锁Lock1
的代码,就会造成死锁。
上面的例子的代码如下所示:
public class LockSample {
private static final Object mLock1 = new Object();
private static final Object mLock2 = new Object();
public static void startRun() {
Thread1 thread1 = new Thread1();
Thread2 thread2 = new Thread2();
thread1.start();
thread2.start();
}
private static class Thread1 extends Thread {
@Override
public void run() {
synchronized (mLock1) {
Log.d("LockSample", "Thread1 run Lock1");
try {
Thread.sleep(500);
synchronized (mLock2) {
Log.d("LockSample", "Thread1 run Lock2");
}
} catch (InterruptedException e) {
e.printStackTrace();
}
}
}
}
private static class Thread2 extends Thread {
@Override
public void run() {
synchronized (mLock2) {
Log.d("LockSample", "Thread2 run Lock2");
try {
Thread.sleep(500);
synchronized (mLock1) {
Log.d("LockSample", "Thread2 run Lock1");
}
} catch (InterruptedException e) {
e.printStackTrace();
}
}
}
}
}
运行结果如下所示,这两个线程第二个同步代码块中的代码都没有得到执行。
死锁的结果
2.2 产生死锁的四个条件
产生死锁有四个 必要条件,只要有一个条件不满足,死锁就可以排除:
- 互斥条件:某个资源在一段时间内只能由一个进程/线程占有,不能被两个或以上的进程/线程占有。
- 不可抢占条件:进程/线程所获得的资源在未使用完毕之前,资源申请者不能强行从资源占有者手中抢夺资源,而只能由资源占有者自行释放。
- 占有且申请条件:进程/线程至少已经占有一个条件,但又申请新的资源;由于该资源已经被其它占有,此时该进程/线程阻塞;但是它在等待新的资源时,仍然占有已用的资源。
- 环路等待:存在一个等待序列
{P1, P2, ..Pn}
,其中P1
等待P2
所占有的资源,P2
等待P3
占有的资源,...,而Pn
等待P1
所占有的资源,形成一个循环等待环。
二、解决死锁的方法
解决死锁的方法分为死锁的预防,避免,检测与恢复三种,下面我们分三个小节来介绍。
2.1 死锁的预防
死锁的预防是保证系统不进入死锁状态的一种策略。它的基本思想是要求进程/线程 申请资源时遵循某种协议,从而 打破死锁的四个必要条件中的一个或多个,可以分为直接的死锁预防和间接的死锁预防两种。
2.1.1 直接的死锁预防
- 打破互斥条件,运行进程同时访问某些资源。
- 打破不可抢占条件,允许进程强行从占有者那里获取某些资源。
- 打破占有且申请条件,实现进程预分配策略。
2.1.2 间接的死锁预防
通过定义资源的线性顺序来预防。如果一个进程已经分配到了R
类型的资源,那么它接下来请求的资源只能是那些排在R
类型之后的资源。
2.2 死锁的避免
在死锁的避免中,是否允许当前的资源分配请求时通过 判断该请求是否可能导致死锁来决定的,因此,死锁避免需要知道将来的资源请求情况。
2.2.1 进程启动拒绝
只有所有 当前进程/线程的最大请求量加上新的请求 可以满足时,才会启动该进程/线程,这个策略很难最优,因为它假设最坏情况,所有进程/线程同时开始它们的最大请求。
2.2.2 资源分配拒绝(银行家算法)
- 安全状态是指至少有一个资源分配序列不会导致死锁(即所有进程都能运行到结束)。
- 死锁避免策略:当进程请求一组资源时,假设同意该请求,从而改变了系统的状态,然后确定其结果时候还处于安全状态。
- 死锁避免的优点是它不需要死锁预防中的抢占和回滚进程,并且比死锁预防的限制少。但是它也有许多限制:
- 必须事先声明每个进程请求的最大资源。
- 考虑的进程必须是无关的,也就是说它们执行的顺序没有任何同步的限制。
- 分配的资源数目是固定的。
- 在占有资源时,进程不能退出。
2.3 死锁检测与恢复
2.3.1 死锁的检测
- 死锁检测不限制资源访问或约束进程行为,只要有可能,被请求的资源就被授权给进程,操作系统周期性地执行一个算法检测前面的条件4。
- 算法主要是一个标记没有死锁的进程,当且仅当算法的最后结果有未标记的进程时存在死锁。
- 算法的策略是查找一个进程,使得可用资源可以满足该进程的资源请求,然后假设同意这些资源,让该进程运行直到结束,再释放它的所有资源。然后算法再寻找另一个可以满足资源请求的进程。
2.3.2 死锁的恢复
- 取消所有死锁进程。
- 把每个死锁进程回滚到前面定义的某些检查点。
- 连续取消死锁进程直到不再死锁。
- 连续抢占资源直到不再死锁。
更多文章,欢迎访问我的 Android 知识梳理系列:
- Android 知识梳理目录:http://www.jianshu.com/p/fd82d18994ce
- Android 面试文档分享:http://www.jianshu.com/p/8456fe6b27c4
网友评论