OS-2-5-死锁
2021-08-18 19:37:23 14 举报
AI智能生成
操作系统 第二章 第5节 死锁 知识点梳理
作者其他创作
大纲/内容
避免死锁
安全序列
存在一个或多个序列,使得系统如果按照该序列分配资源,每个进程都能顺利完成。
存在安全序列的状态称为安全状态
安全状态必然不会死锁
系统不安全状态
如果完成一次分配后,系统中找不到任何一个安全序列,称此时系统进入了不安全状态
即可能所有进程都不能顺利执行
若部分进程归还了一些资源,系统可能回到安全状态
死锁时系统必然处于不安全状态
银行家算法
分析当前的分配是否会导致系统进入不安全状态
若会,则拒绝此次分配
将系统的资源组织为向量,有多少种资源,向量就是多少维
尝试找到一个安全序列
检查剩余可用资源是否可以满足某个进程的最大需求
若不可,则进入了不安全状态
若可,则将该进程加入安全序列,
已分配资源加入可用资源,回到第一步
直到所有进程均加入安全序列
已分配资源加入可用资源,回到第一步
直到所有进程均加入安全序列
实际做题时,若多个进程都可以满足,则可以直接将其全部纳入安全序列,并回收资源
代码实现
检测和解除
检测
定义一种图结构
资源分配图
资源分配图
具有两种结点
进程结点
资源节点:一个结点代表一种资源,其存量由值表示
具有两种边
进程→资源:请求边
资源→进程:分配边
死锁检测算法
以此消除与不阻塞进程相连的边,直到无边可消
不阻塞进程指申请资源可以满足的进程
死锁定理:若图不可完全简化,则形成的回路包含的进程就是死锁进程
可完全简化的图不会死锁
解除
资源剥夺
撤销进程
进程回退
处理原则
优先级低者被处理
执行时间短者被处理
剩余时间长者被处理
使用资源多者被处理
批处理者被处理(相对于交互式)
基本概念
各个进程因等待其他进程占有的资源,而导致全体阻塞,无法执行的现象
死锁不能自行解除,必须外部干涉
Cmp
饥饿 vs 死锁
死循环 vs 死锁
死锁的必要条件(4)
必须同时满足
必须同时满足
互斥条件:进程争抢互斥资源
不可剥夺:资源只能由进程自身释放,不可剥夺
请求和保持:至少已经占有了一个资源,又请求了一个已被占有的资源
循环等待:存在资源的循环等待链,即进程已获得的资源被下一个进程请求
循环等待只在每种资源只有一个时成为死锁的充分条件
仅循环等待不一定死锁,死锁必然循环等待
产生死锁环境
各进程对不可剥夺资源的竞争
CPU是可剥夺的,不会导致死锁
进程执行顺序非法、请求/释放资源顺序不当
信号量使用不当
将信号量也可看做系统资源
死锁的处理策略
不允许死锁发生
预防死锁(静态策略)
破坏一个或几个条件
避免死锁(动态策略)
用特定方法防止系统进入不安全状态
银行家算法
允许死锁发生
死锁检测和接触
系统负责检测并解除死锁
预防死锁
破坏互斥条件
取消互斥资源的互斥限制
OS可以用SPOOLing技术把互斥设备在逻辑上改为共享设备
适用范围窄,很多时候不适用
破坏不可剥夺条件
进程请求不到新资源时释放已获得的资源,留到以后重新申请
在优先级情况下,可由OS剥夺其他进程占有的正被请求的资源
实现复杂,可能造成工作失效,降低系统吞吐量、(第一种方法)可能导致饥饿
破坏请求和保持
静态分配方法:进程要么不被分配资源,要么获得请求的全部资源
获得资源后直到运行结束都不会释放
获得资源后直到运行结束都不会释放
可能造成饥饿
对于部分使用率低的资源,造成极大的浪费
破坏循环等待
顺序资源分配法:对资源编号,规定进程必须按编号
递增顺序请求资源,同类资源(编号相同)一次申请完
递增顺序请求资源,同类资源(编号相同)一次申请完
占有小编号资源时,才有资格申请大编号资源
占有大编号资源时,无权申请小编号资源
占有大编号资源时,无权申请小编号资源
不便于增设新资源,或需全部重分配编号
进程实际使用资源的顺序和编号或不同
导致浪费
导致浪费
用户编程困难
0 条评论
下一页
为你推荐
查看更多