常见调度算法

FCFS-先来先服务 (First Come First Server)

算法思想

主要从“公平”角度考虑，类似我们生活中的排队购物现象，先到先服务

算法规则

按照作业/进程到达的先后顺序进行服务

用于作业/进程调度

  • 用于作业调度时：考虑的是哪个作业先到达后备队列
  • 用于进程调度时：考虑的是哪个进程先到达就绪队列

是否可抢占？

非抢占式算法

示例

先来先服务例题

优缺点

  • 优点：公平，算法实现简单
  • 缺点：排在长作业/长进程后面的短作业需要等待很长时间，其带权周转时间很大，对短作业用户体验不好。

综上即FCFS算法对长作业有利，对短作业不利（例如上面例题种P3作业的带权周转时间达到了很大的8）

是否会导致饥饿

饥饿指某进/作业长时间得不到服务

FCFS算法不会导致饥饿，只要各个任务依序排队，总会轮到响应作业

SJF-短作业优先 (Shortest Job First)

算法思想

追求最少的平均等待时间，最少的平均周转时间，最少的平均带权周转时间

算法规则

最短的作业/进程有限得到服务（这里的最短指的是要求服务时间最短）

用于作业/进程调度

即可用于作业调度，也可用于进程调度，用于进程调度事被称为“短进程优先算法（SPF，Shortest Process First）”

是否可抢占

SJF和SPF是非抢占式算法，但是也存在抢占式的版本：最短剩余时间优先算法（SRTN，Shortest Remaining Time Next）

示例

非抢占式版本

抢占式版本

优缺点

  • 优点：拥有“最短的”平均等待时间，平均周转时间
  • 缺点：不公平，对短作业有利，对长作业不利。可能产生饥饿现象，另外，由于作业/进程运行时间是由用户提供，并不一定真实，可能产生为了抢夺资源故意使用短作业的现象发生

是否会导致饥饿

会，如果不断有短作业到来，可能使已到达的长作业长时间得不到服务，产生饥饿现象

注意

HRRN-高响应比优先 (Hignest Response Ration Next)

算法思想

要综合考虑作业/进程的等待时间和要求服务时间

算法规则

在每次调度时先计算各个作业/进程的响应比，选择响应比最高的作业/进程为其服务

$$响应比=\frac{等待时间+要求服务时间}{要求服务时间}$$

用于作业/进程调度

即可用于作业调度，也可用于进程调度

是否可抢占

非抢占式算法，只有当前运行的作业主动放弃处理机时，才会进行调度

示例

优缺点

  • 优点：
    • 综合考虑等待时间和运行时间
    • 等待时间相同时，要求服务时间短的优先（SJF优点）
    • 要求服务时间相同时，等待时间长的优先（FCFS优点）
    • 对于长作业来说，随着等待时间越来越久，其响应比会增大，从而避免长作业饥饿

是否会导致饥饿

不会

RR-时间片轮转 (Round-Robin)

算法思想

公平轮流为各个进程服务，让每个进程在一定时间间隔内都可以得到响应

算法思想

按照每个进程到达就绪队列的顺序，轮流让每个进程执行一个时间片（如100ms），若进程未在规定时间片内执行完则剥夺其处理机，重新将进程放入就绪队列的队尾重新排队

用于作业/进程调度

用于进程调度（作业只有在被放入内存建立进程后才可能涉及分配处理机时间片）

是否可抢占

若进程未在时间片内运行完，则会被强行剥夺处理及使用权，因此时间片轮转算法属于抢占式算法，由时钟装置发出时钟中断来通知CPU时间片已到

示例

时间片大小为2

时间片大小为5

  • 从上面的时间片为5的示例的运行队列可以看出，在时间片比较大的情况下，RR算法和FCFS算法的运行队列非常相近。如果时间片太大（上面示例超过6时），使得每个进程都可以在一个时间片内完成，则RR算法会退化为FCFS算法，并且会增大进程响应时间，因此时间片不能太大
  • 另一方面，进程调度是有时间代价（保存恢复运行环境），因此如果时间片太小，会导致进程切换过于频繁，系统花费大量时间处理进程切换，降低系统运行效率，因此时间片也不能太小
  • 综上，一般情况下，设计时间片时要让切换进程的开销占比不超过1%

优缺点：

  • 优点：公平，响应快，适用于分时操作系统
  • 缺点：由于高频率的进程切换，因此有一定的开销，不区分任务的紧急程度

是否会导致饥饿

不会

优先级调度算法

算法思想

随着计算机发展，特别是实时操作系统出现，越来越多的应用场景需要根据任务的紧急程度决定处理顺序

算法规则

调度时选择优先级最高的作业/进程

用于作业/进程调度

即可用于作业调度，也可用于进程调度，甚至可以用到I/O调度中

是否可抢占

抢占式，非抢占式都可以，区别在于非抢占式只能在进程主动放弃处理机资源时进行调度，抢占式则需要在就绪队列发生变化时进行检查，是否有优先级变化是否需要抢占

示例

非抢占式

抢占式

优缺点

  • 优点：用优先级区分紧急程度，适用于实时操作系统，可灵活调整对各种作业/进程的偏好承度
  • 缺点：若不断有高优先级进程到来，会导致低优先级进程发生饥饿

是否会发生饥饿

会

补充

多级反馈队列调度算法

算法思想

对其他调度算法的折中权衡

算法规则

  1. 设置多级就绪队列，各级队列的优先级从高到低，时间片从小到大
  2. 新进程到达时优先进入第一级队列，按FCFS原则排队等待被分配时间片，若用完时间片进程还未结束，则进程进入下一级队列队尾，如果此时该进程已经处于最低级队列，则重新放回该队列队尾
  3. 只有第k级队列为空时，第k+1级队列的首个进程才会被分配时间片（优先级高的永远抢占运行）

用于作业/进程调度

用于进程调度

是否可抢占

多级反馈队列调度算法是抢占式算法，在k级队列的进程运行过程中，若更高级的队列（1~k-1）中进入新进程，则由于新进程优先级更高，抢占处理机，原k级进程被放回k级队列队尾

示例


首先P1在0时刻到达，进入最高级队列（1级队列），此时没有进程运行，P1占用CPU运行




一级队列时间片大小只有1，在1时刻，P1在运行完一个时间片后，就需要中断运行进入2级就绪队列等待，此时P2进程恰好进入1级队列，由于优先级更高，所以P2进程占用CPU运行一个时间片，运行结束后同样进入2级就绪队列等待


在2时刻，此时没有更高级进程进入，所以位于2级队列队首的P1进程继续执行，2级队列拥有两个时间片，P1在4时刻中断运行，由于还没有运行结束，所以继续降级进入3级队列等待，4时刻没有新进程到来，所以P2继续占用CPU运行


在5时刻，P2只运行了一个时间片，但由于此时有新进程P3进入，P3处于更高优先级，所以P3抢占CPU运行，P2只能重新回到2级队列队尾等待

在6时刻，P3进程运行结束，离开队列，此时P2处于更高优先级，所以继续占用CPU运行两个时间片


在8时刻，P2运行结束，离开队列，此时P1才能继续占用CPU运行4个时间片，4个时间片后P1仍未运行技术，此时由于P1位于最底层队列，所以P1只能重新回到3级队列队尾进行等待，直到占用CPU运行结束

综上所述，进程的运行情况为：P1(1)->P2(1)->P1(2)->P2(1)->p3(1)->P2(2)->p1(4)->p1(1)

优缺点

  • 优点：对所有进程相对公平（FCFS优点），每个新到达的进程都可以很快得到响应（RR优点），短进程只用较少时间就可以完成（SPF优点），不需要事先考虑进程的运行时间（避免用户造假，避免了SPF的缺点），可以灵活调整对各类进程的偏好程度（CPU密集型，I/O密集型）
  • 缺点：可能会导致饥饿

是否会导致饥饿

是，若不断有新进程到来，则老进程由于进入低优先级队列无法得到执行，进入饥饿状态