死锁避免

操作系统中不可避免的一个问题就是死锁,如今的系统都是高并发,多进程(线程)并行的,所以死锁问题也就不可避免的会发生,所以我们也需要对如何在编程中避免死锁问题做一定了解.

1. 资源轨迹图

   
   image.png
   

   这张图虽然不能说明算法的实现,但是可以帮助我们理解这个算法的思想.在这里,我们看到处理两个进程和两种资源的模型.横轴表示进程A执行的指令,纵轴表示进程B执行的指令.进程A在I1处请求一台打印机,在I3处释放,在I2处请求一台绘图仪,在I4处释放.对于B,其在I5-I7之间需要绘图仪,在I6-I8之间需要打印机.
   图中的每一点都表示出两个进程的连接状态.初始点为p,没有进程执行任何指令.如果调度程序选中A运行,那么A在执行一段指令之后到达q,此时B没有执行任何指令.在q点,如果轨迹沿着垂直方向移动,说明调度程序选中B运行.在单处理器的情况下,所有路径都只能是水平的或垂直方向的,不会出现斜向的.另外,运动方向一定是向上或是向右的,不会向左或向下,因为进程的执行不可能后退.
   当进程A由r向s移动穿过I1线时,它请求并获得打印机.当进程B到达t时,它请求绘图仪.
   阴影区域由于互斥使用的规则,是不可能进入的.
   如果系统一旦进入由I1,I2,I5,I6组成的矩形区域,那么最后一定会到达I2和I6的交叉点,这时就产生死锁.在这一点,A请求绘图仪,B请求打印机,而且这两种资源都已经被分配.整个矩形区域都是不安全的,因此决不能进入该区域.在点t处唯一的办法是运行进程A直到I4.过了I4,可以按照任意路线前进,直到终点u.
   值得注意的是,如果在点t处进程B请求资源,要避免死锁,必须将B挂起,直到A请求并释放绘图仪.

2. 安全状态和不安全状态
   在任何时刻,如果没有死锁发生,并且即使所有进程突然请求对资源的最大需求,也仍然存在某种调度次序能够使得每个进程运行完毕,则称这个状态是安全的.我们用一个例子来说明一下:

   
   image.png
   

   图中6-9a的状态是安全的,因为我们可以先让B完成,B完成之后释放资源,然后我们就有足够的资源让C来运行,之后C运行直到完成,然后释放资源,这时我们有足够的资源让A运行直到完成,所以通过我们的仔细调度,我们成功的避免死锁,过程如上图所示a-e的过程,所以6-9a的状态也是安全的.
   但是,如果我们考虑另外一种情况,假设初始状态如图6-10a所示,但是这次A请求并得到一个资源,如图6-10b所示,我们再利用上面的思路,实际上是不能找到一个合适的序列来完成所有工作,过程如6-10图所示,无论我们怎么分配资源,工作都无法完成.所以,从6-10a到6-10b的分配方案,从安全状态进入到了不安全状态.所以回过头来看,我们不能满足A的请求.

   
   image.png
   值得注意的是,不安全状态并不是死锁状态,从6-10b出发,系统能运行一段时间.实际上,B进程是能够完成的.另外,如果A在请求其他资源实例之前,先释放一个资源实例,那么C就可以先完成,从而避免死锁.
   因此,安全状态与不安全状态的区别在于:从安全状态出发,系统保证所有进程都能够完成,而从不安全状态出发,就没有这样的保证.(个人理解是必须一直保持安全状态而不能进入不安全状态,并不是单单从安全状态出发就能保证不发生死锁).

3. 银行家算法

   
   image.png
   

   图中最右边的三个向量分别表示现有资源E,已分配资源P和可用资源A.
   检查一个状态是否安全的算法如下:

   1. 查找右边矩阵是否有一行,其没有被满足的资源数均小于或等于A.(也就是说这个进程要求是能够被满足的),如果不存在这样的行,那么系统将会死锁,因为任何进程都无法运行结束(假定进程会一直占有资源直到它们终止为止)
   2. 假若找到这样一行,那么可以假设它获得的所需资源并运行到结束,,将该进程标记为终止,并将其资源加到向量A上.
   3. 重复以上两步,或者直到所有的进程都标记为终止,其初始状态是安全的.或者所有进程的资源需求都得不到满足,此时就是发生了死锁.

   对于图中的情况,如果进程B现在请求一台打印机,可以满足它的条件,因为系统状态仍然是安全的(进程D可以结束,然后是A或E结束,剩下的进程都相继结束).
   但是如果是在B获得两台打印机中的一台之后,E试图获得最后一台打印机,则不能满足其要求,原因很简单,大家可以简单想想.
   不过值得说的是,银行家算法虽然是很经典的测试是否死锁的算法,但是并没有广泛应用在实际上,因为很少有进程能够在一开始就知道它所需要的资源的最大值,而且进程数也不是固定的,会有用户不断登入登出.

总结:这篇文章的死锁避免是从操作系统资源的角度来看的死锁,而不是从进程的角度来看,所以基本也没涉及代码,但是这里面的思维和算法倒是非常值得我们学习的.死锁在系统运行过程中是一个非常麻烦的问题,从本质上来看也是无法避免的(因为部分资源的有效性及互斥使用性),所以要避免死锁也是个十分值得深入研究的问题.另外在死锁问题有时候很难被发现,只有当我们发现我们的程序很久没有动静的时候才会察觉,这个时候再去查看问题,可能系统已经死锁了很久.对于操作系统而言,它要做的就是对于任何进程要求的系统可以满足的资源做动态检查,再根据检查结果决定是否分配资源,因此以上所说的算法也主要是用于对资源分配的动态规划,以避免死锁