死锁相关

1 死锁的基本概念
1.1  死锁
指多个进程在运行过程中因争夺资源而造成的一种僵局（deadly-Embrace)，若无外力作用，这些进程都将无法向前推进。

1.2 产生死锁的原因
原因两点如下：
1． 竞争资源。
2． 进程间推进顺序非法。
其根本原因：是系统提供的资源个数少于并发进程所要求的该类资源数。

1.3 产生死锁的必要条件
产生死锁必须具备以下四个条件，这四个条件是Coffman首先提出的，所以称为Coffman 条件：
1. 互斥（Mutual exclusion）：线程所使用的资源中至少有一个是不能共享的，它在同一时刻只能由一个线程使用。
2. 持有与等待（Hold and wait）：至少有一个线程已经持有了资源，并且正在等待获取其他的线程所持有的资源。
3. 非抢占式（No pre-emption）：如果一个线程已经持有了某个资源，那么在这个线程释放这个资源之前，别的线程不能把它抢夺过去使用。
4. 循环等待（Circular wait）：假设有N个线程在运行，第一个线程持有了一个资源，并且正在等待获取第二个线程持有的资源，而第二个线程正在等待获取第三个线程持有的资源，依此类推……第N个线程正在等待获取第一个线程持有的资源，由此形成一个循环等待。

1.4 处理死锁的基本方法
目前处理死锁的基本方法有四种：
 预防死锁：指通过设置某些限制条件，去破坏产生死锁的四个必要条件中的一个或几个条件，来防止死锁的发生。
 避免死锁：指在资源的动态分配过程中，用某种方法去防止系统进入不安全状态，从而避免死锁的发生。
 检测死锁：允许系统在运行过程中发生死锁，但可设置检测机构及时检测死锁的发生，并采取适当措施加以清除。
 解除死锁：当检测出死锁后，便采取适当措施将进程从死锁状态中解脱出来。



2 预防死锁
2 .1 预防死锁
—— 破坏死锁的四个必要条件（常针对条件2,3,4)

3 死锁的避免
在死锁预防的几种方法中，都施加了较强的限制条件，严重降低了系统性能。在死锁避免的方法中，所施加的限制条件较弱，则可获得让人满意的系统性能。在该方法中把系统的状态分为安全状态和不安全状态。
2.1 系统的安全状态
2.1.1 安全状态
概念：
指在某一时刻，系统能按某种进程顺序(p1,p2,…，pn)来为每个进程Pi分配其资源,直到满足每个进程对资源的最大需求,使每个进程都可顺利地完成，则称此时的系统状态为安全状态称序列(p1,p2,…，pn)为安全序列。
若某一时刻系统中不存在这样一个安全序列，则称此时的系统状态为不安全状态。
注：在死锁避免的方法中，允许进程动态申请资源，系统在进行资源分配之前，先计算资源分配的安全性，若此次分配不会导致系统进入不安全状态，便将资源分配给进程，否则进程等待。

基本事实
 如果一个系统在安全状态，就没有死锁
 如果一个系统处于不安全状态，就有可能死锁
 避免死锁的实质：确保系统不进入不安全状态）


2.2 避免死锁的银行家算法
银行家算法的意义：银行家算法是用于避免死锁的，什么意思？就是一旦有进程提出资源请求，那可以用银行家算法来进行资源分配和检测，当分配后检测到系统是不安全状态（可能死锁），则不能进行分配；若是安全状态，则可按其请求给其分配资源。

2.3 死锁的检测和解除
如果在一个系统中，即未采用死锁预防方法，也未采用死锁避免方法，而是直接为进程分配资源，则系统中便有可能发生死锁。一旦死锁发生，系统应能将其找到并加以消除，为此需提供死锁检测和解除的手段。
2.3.1 资源分配图和死锁定理
    检测死锁的基本思想: 是在操作系统中保存资源的请求和分配信息，利用某种算法对这些信息加以检查，以判断是否存在死锁。
2.3.2 死锁的解除
一旦检测出系统中出现了死锁，就应将陷入死锁的进程从死锁状态中解脱出来，常用的解除死锁方法有两种:
1， 资源剥夺法:当发现死锁后,从其他进程剥夺足够数量的资源给死锁进程,以解除死锁状态.
2， 撤消进程法:最简单的方法是使全部死锁进程都撤销；或者就是按某步骤来顺序的撤销进程，直到有资源可用，使死锁状态解除。