什么是死锁
各进程互相竞争对手里的资源,导致各进程都阻塞,都无法向前推进
死锁、饥饿、死循环的区别
死锁:各进程互相持有对方想要的资源且不释放,导致各进程阻塞,无法向前推进
饥饿:由于长期得不到想要的资源,某进程无法向前推进
死循环:某进程执行某个过程一直跳不出某个循环的现象
死锁产生的四个必要条件
- 互斥:不互斥不会死锁
- 不剥夺:进程所持有的资源不能被其他进程强行夺走
- 请求和保持:进程至少持有了一个资源,但同时申请新的资源,不释放已持有资源
- 循环等待:存在一个进程资源循环等待链,即每个进程申请的资源已被上一个进程持有,已持有资源被下一个进程申请
什么时候发生死锁
- 竞争不可剥夺资源
- 进程推进顺序非法,请求和释放资源的顺序不当
- 信号量使用不当,如互斥在同步之前
死锁处理策略
- 预防死锁:破坏四个条件其一或多个
- 避免死锁:银行家算法,避免死锁出现
- 死锁的检测和解除:允许死锁出现,但会检测死锁的发生并采取措施解除死锁
预防死锁
破坏互斥条件
互斥资源变为共享资源,如SPOOLing技术改造打印机,设置空闲缓冲区存储要打印的数据,并为用户申请并填写请求打印表,将此表挂到请求打印队列上,当打印机空闲则从队列中取表,开始打印
破坏不可剥夺条件
不剥夺条件:其他进程不能强行剥夺进程持有的资源
- 当某个进程请求资源得不到满足时,立即释放保持的所有资源,等需要时再重新申请
- 当某个进程需要的资源被其他进程所占有时,可通过操作系统强行剥夺想要的资源
缺点:实现复杂 ,释放持有资源会导致一部分工作失效,反复申请和释放资源会增加系统开销,降低系统吞吐量,有可能综测饥饿
破坏请求和保持条件
静态分配,一次性分配所需全部资源,不然不让他投入运行,运行期间一直归他所有
实现简单,但缺点明显
一部分资源可能只需要使用很短时间,但长期持有造成了浪费,资源利用率低和可能造成进程饥饿
破坏循环等待条件
顺序资源分配法:编号资源,规定每个进程必须按编号递增的顺序请求资源,即持有a号资源,则只能申请大于a的号的资源
缺点在新增设备困难, 编号不方便,实际使用顺序可能不按着递增来,编程困难
避免死锁
安全序列
按照这样的序列分配资源,不会死锁
几种状态间的联系
安全序列不会发生死锁,有安全序列就是安全状态,没有则是不安全状态
不安全状态可能发生死锁,安全序列可能有多个
死锁一定是发生在不安全状态
银行家算法
通过预分配找出安全序列
死锁的检测和解除
死锁的检测
如果这样的图能最后消除所有边,则称是可完全简化的,一定不会死锁,否则会发生死锁
通过图记录资源的请求和分配信息,通过算法检测是否处于死锁状态