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