死锁
死锁发生的原因
归根结底是对资源的竞争。大家都想要某种资源,但是却不能随心所欲的得到资源,在争夺的僵局中,谁都无法继续推进。
资源:一般一个程序工作时所需要的东西:磁盘驱动器,锁、信号量、数据表格等。既可以是软件资源也可以是硬件资源。
资源又可以分为:可抢占资源和不可抢占资源。
死锁的描述:如果有一组线程,每个线程都在等待一个事件的发生,而这个事件只能由该组线程里面的另一线程发出,称这组线程发生死锁。这里的事件通常指资源的释放。
死锁发生的四个必要条件
- 资源有限。(也称为资源互斥条件,即资源不能共享,在一个时刻只能由一个线程使用)
- 持有等待。(一个线程在请求新线程时,已经获得的资源不释放,而是继续持有。)
- 不能抢占。
- 循环等待条件。
死锁的经典问题-哲学家就餐问题
死锁处理
- 死锁预防
- 死锁避免
- 死锁检测和修复
- 处理死锁的综合方法
死锁预防
死锁预防就是防止死锁发生的可能性。
从萌芽状态杀死死锁发生的必要条件。
分为:间接方法和直接方法。
间接方法是防止产生死锁的前三个条件:资源有限(互斥),持有等待、非抢占
直接方法是防止第四个条件:循环等待
消除资源独占条件
- 增加资源(××)
- 资源共享
消除保持和请求条件
- 一个进程必须一次请求其所需要的所有资源,而不是一般情况下的请求一点资源,做一点事情。其拥有程序执行必须得资源,因此不用去竞争资源,所以不会发生死锁。
消除非抢占条件
- 允许对资源进行抢占
消除循环等待条件
循环等待的原因是因为进程请求资源的顺序是随机的,一个进程可以先请求资源A再请求B,也可以先请求B再请求A。所以如果将资源的使用顺序固定,则死锁将不会发生。
死锁避免
死锁避免使在进程申请资源时先判断这次分配是否安全,如果安全才实施分配。
死锁避免的两种方式
- 如果进程对资源的申请可能导致死锁,则不启动这个进程(从进程方面着手)
- 如果进程对资源的申请可能导致死锁,则不给进程分配该资源 (从资源方面着手)
死锁避免的缺点
- 进程预先申明资源的最大量需求
- 进程必须是独立的
- 资源和进程的数目必须固定
死锁检测
一种方法是画出资源占用和资源需求关系的有向图,然后查看是否有循环。如果有循环,则说明有死锁。
否则,无死锁。
但是这种方法实际操作难度较大。
故不采用。
另一种算法是利用矩阵。
用到的两个矩阵分别是:资源分配矩阵和资源等待矩阵。
NULL | 资源1 | 资源2 | 资源3 | 资源4 | 资源5 |
---|---|---|---|---|---|
进程1 | – | 2 | 1 | 3 | 2 |
进程2 | 7 | – | 3 | 2 | 5 |
进程3 | 4 | 6 | – | 3 | 2 |
进程4 | 3 | 2 | 1 | – | 1 |
进程5 | 3 | 5 | 4 | 3 | – |
NULL | 资源1 | 资源2 | 资源3 | 资源4 | 资源5 |
---|---|---|---|---|---|
进程1 | 3 | 2 | 2 | 1 | 0 |
进程2 | 0 | 6 | 1 | 0 | 0 |
进程3 | 0 | 0 | 3 | 1 | 1 |
进程4 | 1 | 1 | 0 | 2 | 1 |
进程5 | 0 | 0 | 0 | 0 | 2 |
NULL | 资源1 | 资源2 | 资源3 | 资源4 | 资源5 |
---|---|---|---|---|---|
系统资源总量 | 20 | 20 | 10 | 15 | 10 |
NULL | 资源1 | 资源2 | 资源3 | 资源4 | 资源5 |
---|---|---|---|---|---|
系统资源总量 | 3 | 5 | 1 | 4 | 0 |
判断算法:将可用资源拿来与资源等待矩阵的每一行进行比较,如果减出来,每一个进程都有负数,则有可能发生死锁
例如上述表格中,系统可用资源与等待矩阵的每一行相减,每一行都出现了负数值。则说明有可能发生死锁。
死锁恢复
死锁恢复的基本方法就是:剥夺
按复杂度增加次序排列
- 杀死所有进程
- 死锁进程回滚到已定义的监测点,重新执行他们
- 逐个杀死进程知道死锁消除
- 逐个抢占其他进程的资源知道死锁消失