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