文章目录
- 死锁的基本概念
- 死锁的四个必要条件
- 避免死锁
- 避免死锁的算法
- 死锁检测算法
死锁的基本概念
死锁是指在一组进程中的各个进程均占有不会释放的资源,但因互相申请被其他进程所站用不会释放的资源而处于的一种永久等待状态。当然,线程之间同样也有死锁问题。
死锁的四个必要条件
- 互斥条件:资源不能被多个线程同时使用,同一时刻最多只有一个线程占有
- 占有并等待条件:一个进程已经获得了某些资源,同时还在等待被其他线程获取的资源。也称为请求与保持条件,即一个线程因为申请资源而阻塞,但是对自己的获得的资源不释放。
- 不可剥夺条件:一个已经获得资源的线程不能被强行地剥夺,只能由占有该线程自行释放。
- 循环等待条件:描述了一种资源分配的闭环,进程之间形成了一个循环等待链。比如A等待B,B等待C,C又等待A。
为什么这四个条件同时满足就一定会造成死锁问题呢?
思考这样一个场景:
假设苹果和梨都是互斥资源
A有一个苹果,B有一个梨,但是A想要的是梨,B想要苹果。于是A在请求B把梨给他,但是A要收到梨才肯交出自己的苹果,对于B也是这样,如果没有外部干预,AB就进入了一直等待的情况即一直等着对方先释放资源。如果允许有外部干预,比如把其中某个人的资源强行释放给对方,比如强行把A的苹果拿给B,B收到苹果就把梨释放了,A也就拿到了梨。这样就AB就脱离了死锁状态。但是如果外部干预也没用,那就彻底没办法了,也就是死锁了。
通过上面的例子,首先苹果和梨同一时间只能时是A或者B拥有,这就满足了互斥条件。A等梨,但是又不释放苹果,这就是占有并等待条件。AB相互等待,这就满足了循环等待条件。如果AB还无论如何都不可能被外部强行释放资源,这也就满足了不可剥夺条件。
那如果上面的四个条件有一个不满足,我们来看看会不会死锁呢?
- 破坏互斥条件,即A拿了苹果,B再拿回来就是了。
- 破坏占有并等待条件,也就是说A拿到苹果之后就马上把苹果释放掉,B拿到梨之后也马上释放掉
- 破坏不可剥夺条件,也就是说A可以被其它人强行把苹果释放掉,无论A愿不愿意,比如B想要苹果,那就强行从A那里把苹果抢过来
- 破坏循环等待条件:A释放苹果,不以B先给他梨为先决条件
上面任意一种情况都不会导致死锁。
那么脱离样例,从线程角度来说,该如何避免死锁呢?
避免死锁
- 破坏死锁的四个条件
- 加锁顺序一致,本质是破坏循环等待的条件。
- 避免锁未释放的场景
- 资源一次性分配,也就是没有线程交叉访问临界资源的情况,每个线程只访问属于自己的资源
避免死锁的算法
死锁检测算法
死锁检测算法用于在系统允许死锁发生的情况下,定期或在特定情况下检测系统是否处于死锁状态,并采取措施恢复。那如何检测呢?
首先要使用到资源分配图:
- 使用图形模型表示资源和进程的分配与请求关系
- 节点分为两类:一种是线程或者是进程节点,另一种是资源节点
- 边分为两类:一种表示申请资源,另一种表示持有资源
例如:
检测思路:检查资源分配图是否出现环,很明显上面图中存在环。
其实还有银行家算法,这里就不做介绍了。