本文是对王道计算机408操作系统+王道2025操作系统考研复习指导部分的提炼总结，个人心得，包含视频内容和课后习题的提炼.
本人是26届考研考生,本文属于考研复习的笔记,会持续更新~
建议搭配视频和指导书食用~ ~ 视频课请看王道计算机考研408操作系统
本文是操作系统第二章 第二节内容
总目录2026考研408 操作系统
第二节：CPU调度
2.2.1 调度的基本概念,层次,对比
- 高级调度(作业调度)
作业:一个具体的任务- 用户向操作系统提交一个作业=用户让操作系统启动一个程序(来处理具体的任务)
- 高级调度是操作系统按照某种规则从外存处于后备队列的作业中选一个或多个给他们分配系统资源并建立对应进程,使他们获得竞争CPU的权利
- 每个作业在一个生命周期内只会调入一次，调入时建立
PCB调出撤销PCB
- 中级调度(内存调度)
- 按照某种策略将挂起的进程重新调入内存
- 低级调度(进程调度/处理机调度)
- 按照某种策略从就绪队列中选取一个进程将处理机分配给它
- 当内存不够的时候,可以将某些数据调出内存,暂时调入外存等待的进程状态为挂起状态,被挂起的进程
PCB会组织成挂起队列 - 一个进程可能会被多次调出调入内存,所以中级调度发生的频率要高于高级调度
- 低级调度(进程调度)是最基本的调度,在各种操作系统都必须配备,进程调度的频率很高一般几十毫秒一次
- 作业调度为进程活动做准备,进程调度使进程正常活动起来
- 中级调度将暂时不用的进程挂起,中级调度处于作业调度和进程调度之间
- 作业调度次数最少,中级调度次数略多,进程调度频率最高
补充知识: 进程的挂起态与七状态模型
- 暂时调出内存的进程称为挂起状态
- 挂起状态细分为就绪挂起,阻塞挂起
- 七状态模型
2.2.2 调度的实现
进程调度的时机
-
需要进程切换的情况
- 当前运行的进程主动放弃
CPU- 进程正常结束
- 运行过程中发生异常
- 进程主动请求堵塞(如等待
IO)
- 当前运行的程序被动放弃
CPU- 分给进程的时间片用完
- 有更紧急的事情需要处理(
IO中断) - 有更高优先级的进程进入就绪队列
- 当前运行的进程主动放弃
-
创建新进程后由于父进程和子进程都处于就绪状态,调度程序会合法的决定其中一个先运行
-
当IO设备完成后会发出IO中断,原先等带IO完成的程序会从阻塞态变到就绪态,此时调度程序需要决定是让新的就绪进程投入运行还是发生中断时的进程继续执行
-
并不是什么时候都可以进程调度的
- 在处理中断的过程中,中断处理过程复杂,与硬件密切相关无法在中断处理的过程中进行进程切换
- 进程在操作系统内核临界区中
- 在原子操作的过程中
-
临界资源:一个时间段内只允许一个进程使用的资源,各进程需要互斥的访问临界资源
-
临界区:访问临界资源的代码;所以也只能互斥的执行临界区代码
-
内核程序临界区:一般是访问某种内核数据结构的,比如进程的就绪队列
-
当进程在内核程序临界区访问内核数据结构(比如就绪队列)的时候,进程调度的程序也需要访问内核数据结构如就绪队列,但是此时被当前进程上锁,所以不能进行调度
-
当进程访问的是普通的临界资源的时候比如(
IO设备打印机),打印机属于慢速设备,进程迟迟不结束不退出普通临界区,会使CPU大量时间空闲,况且普通临界区访问的临界资源不会直接影响操作系统内核的管理,所以在访问普通临界区的临界资源的时候是可以CPU调度的
进程调度的方式
- 非剥夺调度方式(非抢占式),只允许进程主动放弃
CPU,在运行的过程中即便有更紧迫的进程到达也只能等当前使用CPU的进程释放CPU - 剥夺调度方式(抢占式),则与上面相反
- 第一种实现简单,系统开销小,无法及时响应紧急任务,适用于早期批处理系统
- 第二种可以优先处理更紧急任务,也可以实现让各个进程按时间片轮流执行的功能,适用于分时系统,实时系统
进程的切换与过程
- 对原来运行的进程各种数据保存
- 对新的进程各种数据恢复
- 注意进程切换是有代价的,过于频繁的切换进程必然会使整个系统效率下降
调度器(调度程序)
- 用于调度和分派
CPU的组件称为调度程序,它通常分为三部分- 排队器
- 顾名思义就是将系统所有的就绪队列按一定的策略排成一个或多个队列以便于调度程序选择,每当有一个进程变成就绪状态排队器就将它插入相应的就绪队列;
- 分派器
- 分派器专门分配
CPU,依据调度程序选出来的进程,将CPU分配给这个程序
- 分派器专门分配
- 上下文切换器
- 上下文切换指的是切换到另一个进程需要保存当前进程状态并恢复另一个进程的状态这个任务称为上下文切换
- 模式切换指的是用户进程最开始运行在用户态,若进程因中断等原因进入内核态,执行完中断处理程序回到原来进程运行,在同一进程下发生用户态和核心态转换称为模式转换
- 上下文切换会改变当前进程,上下文切换只能发生在内核态,他是多任务操作系统一个必须的特性
- 在对
CPU进行切换的时候会发生两对上下文切换操作- 将当前进程的上下文保存到其
PCB当中,再装入分派程序的上下文,以便于分派程序运行 - 移除分派程序上下文,将新选择的进程的
CPU现场信息装入CPU各个寄存器中
- 将当前进程的上下文保存到其
- 排队器
- 闲逛进程指的是在进程切换的时候如果系统中没有就绪进程,就会调度闲逛进程运行
- 闲逛进程不需要
CPU之外的资源,他不会被阻塞 - 两种线程的调度
- 用户级线程调度
- 内核并不知道用户级线程的存在,对于内核来说还是和以前一样,选择一个进程给他
CPU,给一个时间片,进程内部决定哪个用户级线程运行
- 内核并不知道用户级线程的存在,对于内核来说还是和以前一样,选择一个进程给他
- 内核级线程调度
- 内核选择一个特定线程运行,通常不考虑该线程属于哪个线程,对被选择的线程赋予时间片,时间片到了就会强制挂起该线程
- 用户级线程调度
2.2.3 调度的目标
CPU利用率
CPU的利用率 =
C
P
U
有效工作时间
总时间
(
C
P
U
有效工作时间
+
C
P
U
空闲等待时间
)
\frac {CPU有效工作时间}{总时间(CPU有效工作时间+CPU空闲等待时间)}
总时间(CPU有效工作时间+CPU空闲等待时间)CPU有效工作时间
- 系统吞吐量
- 表示单位时间内
CPU完成的作业数量 - 系统吞吐量 = 完成作业数量 总共花了多少时间 \frac {完成作业数量}{总共花了多少时间} 总共花了多少时间完成作业数量
- 表示单位时间内
- 周转时间
- 指的是从作业提交到作业完成所经历的时间,时作业等待,在就绪队列,在CPU上运行以及
IO操作等所花费时间的总和 - 周转时间 = 作业完成时间-作业提交时间
- 平均周转时间 = 所有周转时间之和 作业数量 \frac {所有周转时间之和}{作业数量} 作业数量所有周转时间之和
- 带权周转时间 =
作业的周转时间
作业理论需要的的周转时间
\frac {作业的周转时间}{作业理论需要的的周转时间}
作业理论需要的的周转时间作业的周转时间 =
作业完成时间
−
作业提交时间
作业理论需要的的周转时间
\frac {作业完成时间-作业提交时间}{作业理论需要的的周转时间}
作业理论需要的的周转时间作业完成时间−作业提交时间
- 对于周转时间相同的两个作业带权周转时间越小越好
- 对于实际需求时间相同的两个作业带权周转时间越小越好
- 平均带权时间 = 所有带权周转时间之和 作业数量 \frac {所有带权周转时间之和}{作业数量} 作业数量所有带权周转时间之和
- 指的是从作业提交到作业完成所经历的时间,时作业等待,在就绪队列,在CPU上运行以及
- 等待时间
- 指的是进程处于等待
CPU时间之和,调度算法实际上不影响作业执行和IO操作时间,只影响作业在就绪队列中等待所花的时间
- 指的是进程处于等待
- 响应时间
- 指的是用户提交请求到系统首次产生响应所用的时间
2.2.4 调度算法
先来先服务(FCFS)
- 思想
- 从公平的角度看待所有进程/作业
- 在作业调度中,调度算法每次从后备作业队列中选择最先来的作业分配资源,创建进程放到就绪队列中
- 在进程调度中,每次从就绪队列选出最先来的进分配
CPU直到运行完成或者因为某种原因阻塞才释放CPU
- 规则
- 按照作业/进程到达的先后顺序进行服务
- 非抢占式算法
- 优缺点
- 优点
- 公平,算法实现简单
- 缺点
- 排在长作业(进程)后面的短作业等待时间长,带权周转时间大
- 总结
- 对长作业有利,对短作业不利
- 优点
- 算法不会导致饥饿
- 饥饿指的是某进程长时间得不到服务
短作业优先(SJF)
- 思想
- 追去最少的平均等待时间,最少的平均周转时间,最少的平均带权周转时间
- 最短的作业/进程先服务
- 最短指的是所需服务的时间
- 算法可以用作作业调度也可用作进程调度,用在进程调度的时候叫短进程优先算法(
SPF) - 非抢占式算法,也有抢占式版本–最短剩余时间优先算法(
STRN)- 未特别说明默认非抢占式
- 抢占式指的是当一个新进程到达就绪队列,若其估计执行时间比当前进程的剩余时间小,则立即暂停当前进程,将
CPU分配给新进程 - 所有进程如果几乎同时到达,采用SJF算的平均等待时间,平均周转时间时最短的
- 其余情况最短的应该是SJF的抢占式算法(
STRN)
- 优缺点
- 优点
- "最短的"平均等待时间,平均响应时间
- 缺点
- 对短作业有利,对长作业不利,可能会导致饥饿现象
- 优点
- 会导致饥饿
- 饥饿指的是,如果源源不断的进来短作业/短进程,
CPU一直调度短作业,长作业就饿死了
- 饥饿指的是,如果源源不断的进来短作业/短进程,
- 该算法未考虑作业的紧迫程度,不能保证紧迫性的作业会被及时处理
- 该算法是基于用户所提供的估计时间而定,而用户可能会有意或者无意缩短其作业的估计运行时间,导致算法不一定真的能做到短作业优先
高响应比优先算法
- 思想
- 综合考虑进程/作业的等待时间和要求服务的时间
- 规则
- 调度的时候会计算各个进程的响应比,选择响应比最高的作业/进程服务
- 响应比 = 等待时间 + 要求服务时间 要求服务时间 \frac {等待时间+要求服务时间}{要求服务时间} 要求服务时间等待时间+要求服务时间
- 算法进程/作业都可以用
- 非抢占式算法
- 只有当前运行的进程/作业放弃
CPU才需要调度,才需要计算响应比
- 只有当前运行的进程/作业放弃
- 优缺点
- 综合考虑等待时间和运行时间
- 等待时间相同选择运行时间低的(
SJF优点) - 运行时间相同选择已经等待很久的(
FCFS优点) - 对于长作业,避免饿死,只要等的时间够久早晚会被调度的
注意
- 前三种算法主要关心公平性,平均周转时间,平均等待时间等评价系统整体性能的指标,并不关心响应时间,不区分任务紧急程度,对于用户的交互很糟糕
- 这三种算法一般适用于早期批处理系统
时间片轮转(RR)
- 思想
- 公平的轮流的为各个进程服务,让进程在一定时间内都能响应
- 规则
- 按照进程到达顺序排序轮流让每个进程执行一个时间片
- 算法用于进程调度
- 只有作业放入内存建立相应进程之后才可以被分配时间片
- 抢占式算法
- 由时钟装置发出中断通知
CPU时间片已到
- 由时钟装置发出中断通知
- 优缺点
- 公平,响应快适用于分时操作系统
- 由于高频率的进程切换有一定的开销,并且不能区分任务的紧急程度
- 该算法不会导致饥饿
- 如果时间片太大,使得每一个进程都可以在一个时间片里完成则退化成先来先服务(
FCFS)调度算法,并且会增大进程响应时间,因此时间片不能太大 - 如果时间片太小,进程切换过于频繁,系统开销大,系统会花费大量时间切换进程,时间片不能太小
- 时间片的长短通常由以下因素确定:
- 系统的响应时间
- 就绪队列里的进程数目
- 系统的处理能力
优先级调度算法
- 思想
- 实时操作系统的出现,很多应用场景需要根据人物的紧急程度来决定处理顺序
- 规则
- 每个进程/作业都有优先级,调度的时候选择高优先级进程/作业
- 可以用于作业也可以用于进程调度,甚至还可以用于
IO调度 - 该算法既有抢占式版本也有非抢占式版本
- 优缺点
- 用优先级区分紧急程度,适用于实时操作系统,可以灵活调整作业/进程的偏好程度
- 若有源源不断高优先级的进程进入,则可能会导致饥饿
- 根据优先级是否可变分为静态优先级和动态优先级
- 静态优先级
- 创建进程的时候就确定了,并且不会改变
- 动态优先级
- 创建进程的时候有一个初始值,但是之后会根据情况改变优先级
- 如何合理设置优先级?
- 通常
- 系统优先级高于用于优先级
- 前台进程高于后台进程
- 操作系统会更偏好
IO型进程(IO繁忙型)- 与
IO繁忙型进程相对应的就是计算型进程(CPU繁忙型进程) IO设备和CPU可以并行运行,如果让IO繁忙型进程优先运行,可以让IO设备尽早投入使用,则系统资源利用率,系统吞吐量都会提高
- 与
- 通常
- 如果采用动态优先级,那什么时候调整进程的优先级呢
- 可以通过追求公平和提升资源利用率等角度改变优先级
- 如果某个进程在就绪队列等待时间很久,则可以适当提升其优先级
- 相反,如果某个进程占用
CPU时间过长,可以适当降低其优先级 - 如果发现一个进程频繁的使用
IO操作可以提升其优先级
- 静态优先级
多级反馈队列调度算法
- 思想
- 融合前几种算法的优点,对其他算法的折中平衡
- 规则
- 设置多种就绪队列,优先级从高到低,时间片大小从小到大
- 新进程到达时会先进入第一级优先级队列,按照
FCFS原则分配时间片 - 若时间片用完进程未结束则将该进程放入下一级队列末尾
- 如果此时已经在最低级优先级队列,则将该进程放入该队列末尾
- 只有上一层队列为空的时候
CPU才会开始调度下一级的就绪队列
- 用于进程调度
- 是一种抢占式算法,在k级队列运行的过程中,若更上级的队列(优先级更高的队列)进入新的进程,由于新进程处于优先级更高的队列中则会抢占
CPU,原来运行的进程会放入k级队列末尾 - 优缺点
- 对各种类型的进程都相对公平(
FCFS优点) - 每个新进来的进程都可以很快就得到响应(
RR优点) - 对于短进程来说在执行几次高优先级的对立之后就完成了,用较少的时间就可以完成(
SPF优点) - 不必估计进程运行时间,隔绝用户自定义因素
- 可以灵活的调整对各种进程的偏好程度
- 对各种类型的进程都相对公平(
- 但是该算法会导致饥饿
多级队列调度算法
- 系统按照进程的类型设置多个队列,进程创建成功后插入某个队列,不同进程优先级不同
- 系统进程优先级最高,交互式进程其次,批处理进程优先级较低
- 队列之间可以采取固定优先级,时间片划分
- 固定优先级
- 只有高优先级队列为空才能调度低优先级队列
- 时间片划分
- 给不同的优先级队列划分不同的时间片如(50% 40% 10%)
- 各队列又可以采用不同的进程调度策略
- 比如系统进程采用优先级调度
- 比如交互式队列采用(
RR) - 比如批处理进程采用(
FCFS)
习题提炼
- 中级调度(内存调度)的主要目的是节省内存,将内存中处于阻塞态或者长期不运行的进程挂起到外存,从而腾出空间给其他进程使用
- 当这些挂起的进程重新具备条件的时候,再从外存调入内存
CPU繁忙型指的是该类作业需要占据很长时间CPU,而很少请求IO操作,所以CPU繁忙型作业是长作业FCFS调度算法比较利于长作业,而不利于短作业,所以FCFS比较适合CPU繁忙型进程/作业- 采用
SJF适合短作业,所以比较适合IO频繁型作业 - 时间片轮转调度算法是绝对可抢占的
- 时间片轮转算法是按照固定的时间运行,时间一到不论是否都会切换进程
- 作业是用户提交,进程是由操作系统自动生成,前者是以用户任务为单位,后者是以操作系统控制为单位
- 本节核心是计算题,本文主要展示背诵部分,计算题暂不总结