死锁详解

死锁的定义

　　所谓死锁，是指多个进程在运行过程中因争夺资源而造成的一种僵局，每个进程持有某种资源而又都等待着别的进程释放它或它们现在保持着的资源，当进程处于这种僵持状态时，若无外力作用，它们都将无法再向前推进的情况，称这一组进程产生了死锁。

死锁的原因

　　1.竞争资源

　　2.进程间推进顺序非法

死锁的条件（四个必要条件）

　　1.互斥条件：进程要求对所分配的资源进行排它性控制，即在一段时间内某资源仅为一进程所占用。

　　2.请求和保持条件：当进程因请求资源而阻塞时，对已获得的资源保持不放。

　　3.不剥夺条件：进程已获得的资源在未使用完之前，不能剥夺，只能在使用完时由自己释放。

　　4.环路等待条件：在发生死锁时，必然存在一个进程--资源的环形链。

死锁的解决方法

　　1.预防死锁（通过设置某些限制条件，以破坏产生死锁的四个条件中的一个或者几个，来防止发生死锁）

　　　　理论上

1.资源一次性分配：一次性分配所有资源，这样就不会再有请求了：（破坏请求条件）

　　　　　　　　是由设备的固有特性所决定的，不仅不能改变，相反还应加以保证。故这个条件不能用于预防。

　　　　　　　　共享资源能共享是系统本身设定。

2.只要有一个资源得不到分配，也不给这个进程分配其他的资源：（破坏请保持条件）

　　　　　　　　其特点为：资源严重浪费，进程延迟进行。

3.可剥夺资源：即当某进程获得了部分资源，但得不到其它资源，则释放已占有的资源（破坏不可剥夺条件）

　　　　　　　　此方法实现比较复杂，且要付出很大代价；此外，还因为反复地申请和释放资源，而使进程的执行无限地推迟，延长了周转时间，增加了系统的开销，降低了系统吞吐量。

　　　　　　4.资源有序分配法：系统给每类资源赋予一个编号，每一个进程按编号递增的顺序请求资源，释放则相反（破坏环路等待条件）

　　　　实际上

　　　　　　1、以确定的顺序获得锁

　　　　　　2、超时放弃

　　　　　　　　使用synchronized关键词提供的内置锁时，只要线程没有获得锁，那么就会永远等待下去，然而Lock接口提供了boolean tryLock(long time, TimeUnit unit) throws InterruptedException方法，该方法可以按照固定时长等待锁，因此线程可以在获取锁超时以后，主动释放之前已经获得的所有的锁。通过这种方式，也可以很有效地避免死锁

　　2.避免死锁（系统在分配资源时根据资源的使用情况提前作出预测，从而避免死锁的发生）

　　　　避免死锁与预防死锁的区别在于：

　　　　　　预防死锁是设法至少破坏产生死锁的必要条件之一，严格地防止死锁的出现。

　　　　　　避免死锁，它是在进程请求分配资源时，采用某种算法（银行家算法）来预防可能发生的死锁：系统在进行资源分配之前预先计算资源分配的安全性。若此次分配不会导致系统进入不安全的状态，则将资源分配给进程；否则，进程等待。

　　　　在避免死锁（或银行家算法）中必须谈到两种系统状态：

　　　　　　①安全状态，指系统能按照某种顺序，为每个进程分配所需的资源，直至最大需求，使得每个进程都能顺利完成。

　　　　　　②非安全状态：即在某个时刻系统中不存在一个安全序列，则称系统处于不安全状态或非安全状态。

　　　　　　总结：虽然并非所有不安全状态都是死锁状态，但当系统进入不安全状态后，便有可能进入死锁状态；反之只要系统处于安全状态，系统便可避免进入死锁状态。因此，避免死锁的实质是如何使系统不进入不安全状态。

　　　　银行家算法：首先需要定义状态和安全状态的概念。系统的状态是当前给进程分配的资源情况。因此，状态包含两个向量Resource（系统中每种资源的总量）和Available（未分配给进程的每种资源的总量）及两个矩阵Claim（表示进程对资源的需求）和Allocation（表示当前分配给进程的资源）。安全状态是指至少有一个资源分配序列不会导致死锁。当进程请求一组资源时，假设同意该请求，从而改变了系统的状态，然后确定其结果是否还处于安全状态。如果是，同意这个请求；如果不是，阻塞该进程知道同意该请求后系统状态仍然是安全的。（具体可查看 银行家算法解析说明）

　　3.检测死锁（允许系统在运行的过程中产生死锁，但是，系统中有相应的管理模块可以及时检测出已经产生的死锁，并且精确地确定与死锁有关的进程和资源，然后采取适当措施，清除系统中已经产生的死锁）

　　　　（1）首先为每个进程和每个资源指定一个唯一的号码；

　　　　（2）然后建立资源分配表和进程等待表。

　　　　（3）检查系统中由进程和资源构成的有向图是否构成一个或多个环路，若是，则存在死锁，否则不存在。其实质是确定是否存在环路等待现象，一但发现这种环路便认定死锁存在，并识别出该环路涉及的有关进程，以供系统采取适当的措施来解除死锁。

　　4.解除死锁

　　　　当发现有进程死锁后，便应立即把它从死锁状态中解脱出来，常采用的方法有：

　　　　　　剥夺资源：从其它进程剥夺足够数量的资源给死锁进程，以解除死锁状态；

　　　　　　撤消进程：可以直接撤消死锁进程或撤消代价最小的进程，直至有足够的资源可用，让死锁状态消除为止；所谓代价是指优先级、运行代价、进程的重要性和价值等。