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