本系列文章为408考研操作系统知识点整理仅涉及到一些重要的考研知识点并不是完全系统全面的知识，参考书目和视频资料：汤小丹 计算机操作系统（第四版），操作系统考研复习指导，B站王道考研操作系统视频课。

2.2.1 调度的概念

处理机调度：多道程序系统中，进程数量往往大于处理机的个数，因此进程争用处理机的情况在所难免。所谓调度是指以满足系统目标(如响应时间、吞吐率、处理器效率)的方式通过一定算法（公平、高效），把进程分配到一个或多个处理机上执行，以实现进程并发执行。

高级调度（作业调度）


高级调度（作业调度）：按照一定的原则从外存处于后备状态的作业中挑选一个（或多个）作业，给它（们）分配内存、输入输出设备等必要资源，并创建进程，使其获得竞争处理机的权利
每个作业只调入一次，调出一次。调入时会建立PCB,调出时会撤销PCB
高级调度主要是指调入的问题，因为只有调度的时机需要操作系统决定，调出的时机必然是作业运行结束
简单理解：好多个程序需要启动，到底应该先启动哪个

中级调度（内存调度）


中级调度（内存调度）：在引入虚拟存储技术后，可以将暂时不能运行的进程调至外存等待（挂起），等它重新具备了运行条件且内存又有空闲时，再重新调入内存，这样做可以提高内存利用率和系统吞吐量。所以中级调度会按照某种策略决定将哪个处于挂起状态的进程重新调回内存
暂时调到外存等待的进程状态为挂起状态（注意PCB一般不会一起调到外存，而是会常驻内存，被挂起的PCB会被放到挂起队列中)
一个进程可能会被多次调出、调入内存，因此中级调度发生的频率要高于高级调度

低级调度(进程调度)


低级调度（进程调度）：按照某种策略从就绪队列中选取一个进程，将处理机分配给它
进程调度是操作系统最基本的一种调度
频率非常高，一般几十毫秒一次。这样才可以保证进程在宏观上并行运行

2.2.2 调度算法评价指标

调度算法评价指标：不同的调度算法具有不同的特性，在选择调度算法时，必须考虑算法的特性。为了比较处理机调度算法的性能，人们提出了很多评价准则，下面介绍其中主要的几种

①：CPU利用率：指CPU处于忙碌状态的时间占比。因此CPU的利用率要尽可能的高
②：系统吞吐量：表示单位时间内内CPU完成作业的数量。尽可能要用少的时间处理更多作业。长时间需要消耗较长的处理机时间，因此会降低系统的吞吐量；对于短作业，他们所需要消耗的处理时间较短，因此比能提高系统的吞吐量

③：周转时间：是指作业提交到作业完成所经历的时间，是作业等待、在就绪队列中排队、在处理机上运行以及输入输出操作所费时间总和
周转时间 = 作业完成时间-作业提交时间
平均周转时间是多个作业周转时间的平均值；即平均周转时间=(作业1+作业2++作业n)/n
带权周转时间是作业周转时间与作业实际运行时间的比值；
平均带权周转时间是指多个作业带权周转时间的平均值

④：等待时间：是指进程处于等处理机状态的时间之和，等待时间越长，用户满意度越低
处理机调度算法实际上并不影响作业执行或喻入喻出操作的时间，只影响作业在就绪队列中等待所花的时间。因此，衡量一个调度算法的优劣，常常只需简单地考察等待时间
⑤：响应时间：是指从用户提交请求到系统首次产生响应所用的时间
在交互式系统中，周转时间不可能是最好的评价准则，一般采用响应时间作为衡量调度算法的重要准则之一。从用户角度来看，调度策略应尽量降低响应时间，使响应时间处在用户能接受的范围之内

2.2.3 进程调度的时机、切换与过程、调度器和闲逛进程

进程调度的时机、切换与过程

(1)需要进行进程调度与切换的情况
①当前运行的进程主动放弃处理机
进程正常终止
运行过程中发生异常而终止
进程主动请求阻塞
②当前运行的进程被动放弃处理机
分配给进程的时间片用完
有更紧急的事情需要处理
有更高优先级的进程进入就绪队列

(2)不能进行进程调度与切换的情况
在处理中断的过程中，由于中断处理过程复杂，与硬件密切相关，很难做到在中断处理过程中进行进程切换
进程在操作系统内核程序临界区中
在原子操作过程中，原则操作不可中断，需要一气呵成

进程切换的过程主要完成了
对原来运行进程的各种数据进行保存
对新的进程的各种数据进行恢复

狭义和广义的进程调度
·狭义的进程调度：从就绪队列中选择一个要运行的进程（此进程可以是刚刚被暂停执行的进程，也可能是另外一个进程，其中后者便是进程切换)
广义的进程调度：包含了选择一个进程和进程切换两个步骤

进程切换

对于通常的进程而言，其创建、撤销及要求由系统设备完成的I/O操作，都是利用系统调用而进入内核，再由内核中的相应处理程序予以完成的。进程切换同样是在内核的支持下实现的，因此可以说，任何进程都是在操作系统内核的支持下运行的，是与内核紧密相关的。

切换CPU到另一个进程需要保存当前进程状态并恢复另一个进程的状态，这个任务称为上下文切换。上下文是指某一时刻CPU寄存器和程序计数器的内容。进行上下文切换时，内核会将旧进程状态保存在其PCB中，然后加载经调度而要执行的新进程的上下文。
上下文切换实质上是指处理机从一个进程的运行转到另一个进程上运行，在这个过程中，进程的运行环境产生了实质性的变化。上下文切换的流程如下：

1)挂起一个进程，保存CPU上下文，包括程序计数器和其他寄存器。
2)更新PCB信息。
3)把进程的PCB移入相应的队列，如就绪、在某事件阻塞等队列。
4)选择另一个进程执行，并更新其PCB。
5)跳转到新进程PCB中的程序计数器所指向的位置执行。
6)恢复处理机上下文。

模式切换与上下文切换是不同的，模式切换时，CPU逻辑上可能还在执行同一进程。用户进程最开始都运行在用户态，若进程因中断或异常进入核心态运行，执行完后又回到用户态刚被中断的进程运行。用户态和内核态之间的切换称为模式切换，而不是上下文切换，因为没有改变当前的进程。上下文切换只能发生在内核态，它是多任务操作系统中的一个必需的特性。

调度器

调度器（调度程序）：进程的就绪和运行状态的切换由调度程序引起，它主要决定以下两件事情
调度算法
时间片大小
以下事件会触发调度程序

  • 创建新进程
  • 进程退出
  • 运行进程阻塞
  • I/O中断发生

对于非抢占式调度策略，只有运行进程阻塞或退出时才会触发调度程序工作
对于抢占式调度策略，每个时钟中断或k个时钟中断会触发调度程序工作

闲逛进程

闲逛进程：它是调度程序永远的备胎，没有其他就绪进程时，会运行闲逛进程。其特性如下

  • 优先级最低
  • 可以是0地址指令，占一个完整的指令周期
  • 能耗低，不需要CPU以外的资源，不会被阻塞

2.2.4 经典调度算法

先来先服务调度算法(FCFS)

先来先服务调度算法(FCFS):先来后到，每次从就绪队列选择最优先进入队列的进程，然后一直运行，直到进程退出或被阻塞，才会继续在队列中选择下一个进程，属于非抢占式
作业调度：考虑的是哪个作业先到达后备队列
进程队列：考虑的是哪个进程先到达就绪队列

优缺点
优点：公平、算法实现简单
缺点：如果带权周转时间很大，表明该进程只需很短的时间能被处理，却还要花费很长时间处理。
适用情况：FCFS对长作业有利，对短作业不利。适用于CPU繁忙型作业的系统，不适用于I/O繁忙型作业的系统
是否会导致饥饿现象：不会

最短作业优先调度算法(SJF)

最短作业优先调度算法(SJF):最短（要求服务时间最短）的作业进程优先得到服务，既可以用于作业调度，也可以用于进程调度
如果用于进程调度，又称为“短进程优先算法(SPF)”
SPF和SJF都是非抢占式算法（默认）。但也有对应的抢占式版本，称之为最短剩余时间优先算法(SRTN)

优缺点
优点：“最短的”平均等待时间，平均周转时间
缺点：不公平。而且有时作业进程的运行时间是由用户提供的，并不一定真实，不一定能够做到真正的短作业优先
适用情况：SJF对短作业有利，对长作业不利
是否会导致饥饿现象：会
如果短作业进程源源不断到来，可能使长作业进程长时间得不到服务，产生“饥饿“”现象，如果一直得不到服务则称之为“饿死”

高响应比优先调度算法(HRRN)

高响应比优先调度算法(HRRN):该算法综合考虑作业进程的等待时间和要求服务的时间。在每次调度时先计算各个作业进程的响应比，选择响应比最高的作业进程为其进行服务，属于非抢占式
如果两个进程的等待时间相同，要求服务时间越短，那么响应比就会越高，这样短作业就容易被选中运行
如果两个进程的要求服务时间相同，等待时间越长，响应比就越高，这样长作业就容易被选中运行

是否会导致饥饿现象：不会

上面这几种算法着重点主要在公平性、平均周转时间、平均等待时间等评价系统整体性能的指标，但是不关心响应时间，也不区分任务的紧急程度，因此交互性很差。

时间片轮转调度算法(RR)

时间片轮转调度算法(RR)：公平地、轮流地为各个进程服务，让每个进程在一定时间间隔内都可以得到响应。按照各进程到达就绪队列的顺序，轮流让各个进程执行一个时间片(Quantum),若进程未在一个时间片内执行完毕，则剥夺处理机，然后将其放入就绪队列重新排队
用于进程调度（因为只有作业放入内存建立了相应进程后，才能被分配处理机时间片）
·若进程未能在时间片内运行完毕，则会被强行剥夺，属于抢占式算法，由时钟装置发出时钟中断通知CPU时间片已到

时间片大小的影响
时间片太大：使得每个进程都可以在一个时间片内完成，此时RR算法就退化为了FCFS算法，并且会增大进程响应时间
时间片太小：由于进程调度、切换是有时间代价的，因此如果时间片太小，会导致进程切换过于频繁，系统会花大量时间来处理进程切换
优缺点
优点：公平、响应快
缺点：由于高频率的进程切换，因此会有一定开销，且不能区分任务的紧急程度
是否会导致饥饿现象：不会

优先级调度算法(HPF)

随着计算机的发展，特别是实时操作系统的出现，越来越多的应用场景需要根据任务的紧急程度（优先级）来决定处理顺序。进程的优先级可以被划分为
静态优先级：创建进程的时候，就已经确定好了优先级，整个运行过程优先级都不会发生变化
动态优先级：根据进程的动态变化调整优先级（比如当进程的运行时间增加侧降低其优先级、进程等待时间增加则提高其优先级等等)

优先级调度算法(HPF)：每个作业进程都有各自的优先级，调度时选择优先级最高的作业进程
可用于作业调度、进程调度，甚至I/O调度
有抢占式（当就绪队列中出现优先级高的进程，当前进程被挂起，调度优先级高的进程）和非抢占（当就绪队列中出现优先级高的进程，运行完当前进程，再选择优先级高的进程)两种

进程优先级的设置原侧
系统进程大于用户进程：系统进程作为系统的管理者，理应拥有更高的优先级
交互型进程大于非交互型进程（前台进程大于后台进程）：类比使用手机时的前台应用程序和后台应用程序
I/O密集型进程大于计算密集型进程：I/O密集型进程是指那些会频繁使用I/O设备的进程；计算密集型进程是指那些频繁使用CPU的进程。如果将I/O密集型进程设置得更高，就更有可能让I/O设备尽早开始投入工作，进而提升系统的整体效率
优缺点
优点：使用优先级区分紧急程度、重要程度、适用于实时操作系统，可以灵活调整对各种作业进程的偏好程度
缺点：有可能导致低优先级进程得不到运行
是否会导致饥饿：会

多级反馈队列调度算法(MFQ)

多级反馈队列调度算法(MFQ)：MFQ算法其实是RR算法和HPF算法的综合和发展
多级：表示有多个队列，每个队列优先级从高到低，同时优先级越高时间片越短
反馈：表示如果有新的进程加入优先级高的队列时，立刻停止当前正在运行的进程，转而去运行优先级高的队列
算法具体规则
设置了多个队列，赋予每个队列不同的优先级，每个队列优先级从高到低，同时优先级越高时间片越短
新的进程会被放入到第一级队列的末尾，按FCFS算法的原则排队等待被调度，如果在第一级队列规定的时间片内没有运行完毕，则将其转入第二级队列的末尾，依次类推，直至完成
当较高优先级的队列为空时，才调度较低优先级队列中的进程。如果进程运行时，有新的进程进入较高优先级队列时，则停止当前运行的进程并将其移入原队列的末尾，接着让较高优先级的进程运行

从以上的叙述中大家可以感受到：
短作业可能可以在第一级队列很快地被处理完
长作业如果第一级处理不完，可以移入下一级等待。等待时间虽然变长了，但是运行时间也会变长
多级反馈队列的优点
终端型作业用户：短作业优先（例如命令行输入命令）
短批处理作业用户：周转时间较短
长批处理作业用户：经过前面几个队列得到部分执行，不会长期得不到处理
是否会导致饥饿：会

对比总结