OS-2-2-进程管理(处理机调度算法)
2021-08-12 09:30:30 0 举报AI智能生成
操作系统第二章 第二节 进程管理 处理机调度算法 知识点梳理
作者其他创作
大纲/内容
非交互式OS
进程调度算法
进程调度算法
先来先服务
FCFS
FCFS
目的
公平性
规则
按作业到达后备队列/进程到达就绪队列的先后顺序服务
用途
作业调度/进程调度均可
性能分析
优缺点
公平
实现简单
对长作业有利，对(排在长作业后的)短作业不利
不会导致饥饿
总会得到服务
非抢占式算法
短作业优先
SJF
短进程优先
SPF
SJF
短进程优先
SPF
目的
追求更短的平均等待时间、平均周转时间、平均带权周转时间
规则
当前已到达的，最短的作业/进程优先得到服务
用途
作业调度(SJF)，进程调度(SPF)均可
变种
抢占式：
最短剩余时间优先
SRTN
最短剩余时间优先
SRTN
每当有进程加入就绪队列、每当进程完成时需要调度
若新进程剩余时间更短，则新进程抢占处理机
当前进程回到就绪队列
当前进程回到就绪队列
性能分析
优缺点
比SJF性能更优秀
不会导致饥饿
性能分析
优缺点
在所有进程几乎同时到达时，SJF的
平均等待时间、平均周转时间最少
平均等待时间、平均周转时间最少
偶尔会出现不加前提的选项，除非
有更合适的选项，不然还是认为正确
有更合适的选项，不然还是认为正确
短作业有利，长作业不利
作业时间可以篡改
会导致(长作业)饥饿
甚至导致长作业饿死
非抢占式算法
高响应比优先
HRRN
HRRN
目的
综合考虑作业/进程等待时间和要求服务的时间
响应比=(等待时间+要求服务时间)/要求服务时间
≥1
随时间发展响应比增加
规则
在就绪队列中选择响应比最高的
只有主动放弃CPU才会进行调度
用途
作业调度/进程调度均可
性能分析
优缺点
综合考虑作业/进程等待时间和要求服务的时间
综合SJF和FCFS的优点
不导致饥饿
非抢占式
交互式OS
进程调度算法
进程调度算法
时间片轮转算法
RR(Round-Robin)
RR(Round-Robin)
目的
公平轮流的为进程服务
关心响应时间，其余指标次要
规则
轮流让进程执行一个时间片
时间片到就剥夺进程的处理机
并将进程放到就绪队列尾
并将进程放到就绪队列尾
利用时钟硬件发出时钟中断
一般情况下，对于新进程和下处理机
进程同时发生，按新进程先到处理
进程同时发生，按新进程先到处理
对于运行时间小于时间片的，不用
把时间片用完，主动放弃也要调度
把时间片用完，主动放弃也要调度
只有主动放弃和时间片到时需调度
用途
仅进程调度
性能分析
优缺点
公平轮流的为进程服务，响应时间很短，适合分时OS
不区分紧急程度
时间片太长，就会退化为FCFS算法
时间片太小，系统开销太大，效率很低
不导致饥饿
抢占式
优先级调度算法
目的
实时OS要求根据紧急程度决定处理顺序
规则
在就绪队列中选择优先级最高的作业/进程
仅抢占式：当队列中存在优先级更高的任务时，当前进程下处理机
只有作业/进程结束才会进行调度（非抢占式）
作业/进程结束和队列新到时进行调度（抢占式）
注：就绪队列可能有多个，部分OS按优先级组织就绪队列
优先级
动态优先级
进程在就绪队列中等待过久，可适当提升其优先级
进程占用处理机时间过长，可适当降低其优先级
静态优先级
优先级不变
系统进程>用户进程
前台进程>后台进程
I/O进程(I/O繁忙型进程)>运算型进程(CPU繁忙型进程)
用途
作业调度/进程调度均可
性能分析
优缺点
可区分任务紧急程度
可能导致饥饿
会导致饥饿
多级反馈队列调度
目的
综合所有以上算法的优势
规则
设置多级就绪队列，各队列优先级从高到低。时间片由小到大
新进程达到时先进入最高级队列，按FCFS原则等待被分配时间片
若时间片到未执行完，下处理机并进入下一级就绪队列队尾
若已在最低级队列，则放回该级队尾
若时间片到未执行完，下处理机并进入下一级就绪队列队尾
若已在最低级队列，则放回该级队尾
只为非空的队列中优先级最高者分配时间片
用途
仅进程调度
性能分析
对各类型进程相对公平(FCFS)
子主题
新到进程响应快(RR)
短进程只用较少时间完成(SPF)
无需预估进程运行时间(解决优先级的痛点)
可以灵活调整堆各类型进程的偏好程度
如IO阻塞时不降优先级
抢占式算法
部分教材也可实现为非抢占式
会导致饥饿
处理机调度基本概念
调度的三个层次
作业调度
(高级调度)
(高级调度)
按一定的原则从外存的作业后备队列
挑选一个调入内存，并创建进程
挑选一个调入内存，并创建进程
调入时创建PCB，调出时撤销PCB
例：启动程序
内存调度
(中级调度)
(中级调度)
内存不足时，将某些进程调出
等内存空闲时再调入内存
等内存空闲时再调入内存
暂时调出的进程状态称为“挂起状态”
其PCB组织为挂起队列
其PCB组织为挂起队列
挂起也分为“就绪挂起”和“阻塞挂起”
调入的过程称为中级调度
进程调度
(低级调度)
(低级调度)
按策略从就绪队列中选取一个
将处理机分配给它
将处理机分配给它
进程调度的策略
时机
何时需要调度
当前进程主动放弃处理机
正常终止
异常终止
阻塞
当前进程被动放弃处理机
时间片耗尽
有更紧急的事要处理(IO中断)
更高优先级进程进入队列
何时不可调度
处理中断的过程中
进程在OS内核程序临界区中
临界区是访问临界资源的代码
普通临界区一直等待就会造
成处理机算力资源的浪费
成处理机算力资源的浪费
原语执行过程中
方式
非剥夺调度
(非抢占方式)
(非抢占方式)
只允许进程主动放弃处理机
简单，系统开销小
无法及时处理紧急任务
一般适合早期批处理OS
剥夺调度
(抢占方式)
(抢占方式)
当更紧迫的任务出现时，立即暂停
当前进程，将处理机分配给紧迫者
当前进程，将处理机分配给紧迫者
适合分时OS和实时OS
切换与过程
辨析
(狭义的)进程调度
从就绪队列选择一
个要运行的进程
个要运行的进程
进程切换
一个进程让出处理机，另
一个进程占用处理机的过程
一个进程占用处理机的过程
过程
保存当前进程的各种数据
恢复新进程的运行环境
进程调度和切换是有代价的，过于频繁的调度、切换反而降低系统并发度
调度算法性能指标
CPU利用率
CPU忙碌时间占总时间比例
其他设备利用率亦如此计算
系统吞吐量
利用尽可能少的时间处理尽量多的作业
系统吞吐量=作业完成量/完成时间
周转时间
周转时间=完成时间点-到达时间点
平均周转时间=周转时间和/作业数
带权周转时间=周转时间/作业实际运行时间
≥1
越小体验越好
平均带权周转时间=带权周转时间和/作业数
从作业被提交给系统到作业完成经历的时间
高级调度等待时间
低级调度等待时间
作业在CPU上执行时间
作业阻塞时间
等待时间
等待处理机时间之和
越长体验越差
作业还要考虑等待高级调度的时间，进程不用
等待IO完成时间不计入等待时间
等待时间=周转时间-运行时间(-IO时间)
响应时间
从提交请求(命令)到产生首次响应的时间
饥饿
进程/作业长期得不到服务，称之为“饥饿”
一直得不到服务，称为进程/作业“饿死”
职业：暂无
0 条评论
下一页
