死锁的产生和解决
死锁
死锁是指两个或两个以上的进程在执行过程中,由于竞争资源或者由于彼此通信而造成的一种阻塞的现象,若无外力的作用,他们都将无法推进下去。此时称系统处于死锁状态或者说系统产生了死锁,这些永远相互等待的进程称为死锁进程;
- 集合中的每一个进程都在等待只能由本集合的其他进程才能引发的事件,那么该组进程是死锁的;例如:线程A锁住了锁1并等待锁2的释放,而线程B锁住了锁2并等待锁1的释放,这样两个线程就产生了死锁的情况;
注意:死锁 ≠ 阻塞
产生死锁的条件
产生死锁的条件一共有四个:
-
互斥条件
指进程对所分配的资源进行排它性使用,即一段时间内某个资源只由一个进程占用。如果此时还有其他的进程请求资源,则请求者只能等待,直到占有资源的进程释放资源; -
请求和保持条件
指进程已经保持了至少一个资源,但又提出了新的资源请求,而该资源已经被其他的进程占有,此时请求阻塞,但是又对自己已经获得的其他资源占有不放; -
不剥夺条件
指进程已经获得的资源,在未使用完成之前,不能被剥夺,只能在使用完成后由自己释放; -
环路等待条件
指在发生死锁时,必然存在一个进程——资源的环形链,即进程集合{P0,P1,P2…Pn}中的P0正在等待一个P1占用的资源;P1正在等待P2占用的资源,…,Pn正在等待P0占用的资源;
预防死锁的产生
在看完上述的产生死锁的四大基本条件,我们可以知道预防死锁的产生本质上就是打破四个必要条件之一就能有效地预防死锁的发生。
- 打破互斥条件
改造独占性资源为虚拟资源,大部分资源已经无法改造;
- 打破不可抢占条件
当一个进程占有一个独占资源后又申请一独占性资源而无法满足,则退出原来占有的资源;
- 打破占有且申请条件
方法1 : 采用资源预先分配策略,即进程运行前申请全部资源,满足则运行,不然就等待;
优点 | 缺点 |
---|---|
简单易实施且安全 | 因为某项资源不满足,进程无法启动,而其他已经满足的了的资源也不会得到利用,严重降低了资源的利用率,造成资源浪费。使进程发生饥饿现象 |
方法2 : 该方法允许进程只获得运行初期需要的资源,便开始运行,在运行过程中逐步释放掉分配到的已经使用完毕的资源,然后再去请求新的资源。提高资源的利用率,减少进程的饥饿现象;
- 打破循环等待条件
实现资源有序分配,对所有设备实现分类编号,所有进程只能采用按序号递增的形式申请资源;
死锁的避免
在使用前进行判断,只允许不会产生死锁的进程申请资源。
死锁避免是利用额外的检验信息,在分配资源时判断是否会出现死锁,只有在不会出现的情况下才分配资源;
避免死锁的两种方法
- 如果一个进程的请求会导致死锁,则不启动该进程;
- 如果一个进程的增加资源请求会导致死锁,则拒绝该请求;
银行家算法——避免死锁的算法
- 相关的数据结构
a.可利用资源向量Available : 用于表示系统里面各种资源剩余的数目。假设系统里面拥有的资源为m种(m ≈ ∞),所以,我们用一个有m个元素的数组来表示各种资源。数组元素的初始值为系统里面所分配的该类全部可用资源的数目,其数值随着该类资源的分配与回收动态的改变;
b.最大需求矩阵Max : 用于表示各个进程对各种资源的最大需求量。
c.分配矩阵Allocation : 用于表示已经分配给各个进程的各种资源的数目。该矩阵的大小和Max一样。
d.需求矩阵Need : 用于表示进程仍然需要的资源数目。
系统可能美玉办法一下子就满足某个进程的最大需求,通常系统都会先分配一部分资源保证进程可以执行。那么,进程的最大需求 - 已经分配给进程的数目 = 进程仍然需要的资源数目
银行家算法通过对进程的需求、占有和系统拥有资源的实时统计,确保系统在分配给进程资源不会造成死锁才会对其分配;
死锁的解除
如果利用死锁检测算法已经检测出系统出现了死锁,那么就需要采取相应的措施来解除死锁状态:
方法 | 解释 |
---|---|
抢占资源 | 从一个或多个进程中抢占足够数量的资源分配给死锁进程,直至死锁状态解除 |
终止进程 | 终止或撤销系统中一个或多个死锁进程,直至打破死锁状态 |
终止进程的判断条件:
1.进程的优先级;
2.进程已经运行的时间以及运行完成还需要的时间;
3.进程占用的系统资源;
4.进程运行完成还需要的系统资源;
5.终止进程数目;
6.进程是交互的还是批处理的;