处理机调度与死锁
2021-05-07 07:13:19 16 举报AI智能生成
进程调度策略与进程死锁
作者其他创作
大纲/内容
处理机调度
处理机调度
基本概念
按某种算法选择一个进程将处理机分配给它
三个层次
高级调度（作业调度）
按照某种规则，从后备队列中选择合适的作业将其调入内存，给它（们）分配内存、输入输出设备等必要的设备，并为其创建进程
对于每个作业只调入一次、调出一次
中级调度（内存调度）
按照某种规则， 从挂起队列中，选择合适的进程将其数据调回内存
低级调度（进程调度）
按照某种规则，从就绪队列中选择一个进程为其分配处理机
操作系统最基本的一种调度
三层调度的联系、对比
高级调度
外存->内存（面向作业）
发生频率：最低
中级调度
外存->内存（面向进程）
发生频率：中等
低级调度
内存->CPU
发生频率:最高
补充知识
为减轻系统负载，提高资源利用率，暂时不执行的进程会被调到外存从而变为“挂起态"
七状态模型：在五状态模型的基础上加入了“就绪挂起”和“阻塞挂起"两种状态
处理机调度过程
时机
什么时候需要进程调度？
主动放弃
进程正常终止
运行过程中发生异常而终止
主动阻塞（如 等待I/O）
被动放弃
分给进程的时间片用完
有更紧急的事情需要处理（如 I/O中断）
有更高优先级的进程进入就绪队列
什么时候不能进行进程调度？
在处理中断的过程中
进程在操作系统内核程序临界区中，进程在普通程序临界区中是可以进程调度、切换的
原子操作过程中（原语）
切换与过程
狭义的"调度"和"切换"的区别
切换过程
对原来运行进程各种数据的保存
对新的进程各种数据的恢复
重要结论：进程调度、切换是有代价的，并不是调度越频繁，并发度就越高
方式
非剥夺调度方式 （非抢占式）
只能由当前运行的进程主动放弃CPU
实现简单、系统开销小，但不能用于分时系统和大多数实时系统
剥夺调度方式（抢占方式）
可由操作系统剥夺当前进程的CPU使用权
对提高系统吞吐率和响应效率都有明显的好处
抢占必须遵循一定的原则
优先权原则
短进程优先原则
时间片原则
调度算法
作业调度
先来先服务（FCFS）
作业调度/进程调度
短作业优先（SJF）
作业调度/进程调度
高响应比优先（HRRN）
作业调度
进程调度
时间片轮转调度算法
分时系统
多级反馈队列调度算法
调度算法的评价指标
CPU利用率
利用率 = 忙碌的时间 / 总时间
系统吞吐量
系统吞吐量 = 总共完成了多少道作业 / 总共花了多少时间
周转时间
周转时间 = 作业完成时间 - 作业提交时间
平均周转时间 = 各作业周转时间之和 / 作业数
带权周转时间 = 作业周转时间 / 作业实际运行的时间
平均带权周转时间 = 各作业带权周转时间之和 / 作业数
包括四部分时间：
1、作业在外村后备队列上等待（作业）调度的时间
2、进程在就绪队列上等待进程调度的时间
3、进程在CPU上执行的时间
4、进程等待I/O操作完成的时间
等待时间
进程/作业 等待被服务的时间之和
平均等待时间即各个 进程/作业 等待时间的平均值
响应时间
从用户提交请求到首次产生响应所用的时间
死锁
死锁的概念
什么是死锁
各进程相互等待对方手里的资源，导致各进程都阻塞，无法向前推进
死锁、饥饿、死循环的区别
死锁：至少是两个进程一起死锁，死锁进程处于阻塞态
饥饿：可以只有一个进程饥饿，饥饿进程可能阻塞也可能就绪
死循环：可能只有一个进程发生死循环，死循环的进程可上处理机
死锁和饥饿是操作系统要解决的问题，死循环是应用程序员要解决的
死锁产生的必要条件
互斥条件
对必须互斥使用的资源的争夺才会导致死锁
不剥夺条件
进程保持的资源只能主动释放，不可强行剥夺
请求和保持条件
保持着某些资源不放的同时，请求别的资源
循环等待条件
存在一种进程资源的循环等待链
循环等待未必死锁，死锁一定有循环等待
什么时候会发生死锁
竞争不可抢占性资源引起死锁
竞争可消耗资源引起死锁
进程推进顺序不当引起死锁
死锁的处理策略
预防死锁
破坏死锁产生的四个必要条件
避免死锁
避免系统进入不安全状态（银行家算法）
死锁的检测和解除
允许死锁发生，系统负责检测出死锁并解除
死锁的处理
不允许死锁发生
静态策略：预防死锁
破坏互斥条件
将临界资源改造为可共享使用的资源（如 SPOOLing技术）
缺点：可行性不高，很多时候无法破坏互斥条件
破坏不可剥夺条件
方案一，申请的资源得不到满足时，立即释放拥有的所有资源
方案二，申请的资源被其他进程占用时，由操作系统协助剥夺（考虑优先级）
缺点：实现复杂；剥夺资源可能导致部分工作失效；反复申请和释放导致系统开销大；可能导致饥饿
破坏请求和保持条件
第一种协议：预先静态分配法，运行前分配好所有需要的资源，之后一直保持
缺点：资源利用率低；可能导致饥饿
第二种协议：允许一个进程只获得运行初期所需的资源后，便开始运行。进程运行过程中再逐步释放已分配给自己的、且已用毕的全部资源，然后再请求新的所需资源。
破坏循环等待条件
资源有序分配策略：给资源编号，必须按编号从小到大的顺序申请资源
缺点：不方便增加新设备；会导致资源浪费；用户编程麻烦
动态策略：避免死锁
允许死锁发生
死锁检测和解除
如何检测
数据结构：资源分配图
两种结点
进程结点
资源结点
两种边
进程结点->资源结点（请求边）
资源结点->进程结点（分配边）
死锁检测算法
依次消除与不阻塞进程相连的边，直到无边可消
注：所谓不阻塞进程是指其申请的资源数还足够的进程
死锁定理：若资源分配图是不可完全简化的，说明发生了死锁
如何解除
资源剥夺法
挂起某些死锁进程并抢夺它的资源，以便让让他进程继续推进
撤销进程法（终止进程法）
强制撤销部分甚至全部死锁进程并剥夺这些进程的资源。
进程回退法
进程回退时自愿释放资源而非被剥夺
让一个或多个进程回退到足以回避死锁的地步
1、抢占资源
2、终止（撤销）进程
0 条评论
下一页
