常见调度算法
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)
算法思想
要综合考虑作业/进程的等待时间和要求服务时间
算法规则
在每次调度时先计算各个作业/进程的响应比，选择响应比最高的作业/进程为其服务
用于作业/进程调度
即可用于作业调度，也可用于进程调度
是否可抢占
非抢占式算法，只有当前运行的作业主动放弃处理机时，才会进行调度
示例
优缺点
- 优点：
- 综合考虑等待时间和运行时间
- 等待时间相同时，要求服务时间短的优先（SJF优点）
- 要求服务时间相同时，等待时间长的优先（FCFS优点）
- 对于长作业来说，随着等待时间越来越久，其响应比会增大，从而避免长作业饥饿
是否会导致饥饿
不会
RR-时间片轮转 (Round-Robin)
算法思想
公平轮流为各个进程服务，让每个进程在一定时间间隔内都可以得到响应
算法思想
按照每个进程到达就绪队列的顺序，轮流让每个进程执行一个时间片（如100ms），若进程未在规定时间片内执行完则剥夺其处理机，重新将进程放入就绪队列的队尾重新排队
用于作业/进程调度
用于进程调度（作业只有在被放入内存建立进程后才可能涉及分配处理机时间片）
是否可抢占
若进程未在时间片内运行完，则会被强行剥夺处理及使用权，因此时间片轮转算法属于抢占式算法，由时钟装置发出时钟中断来通知CPU时间片已到
示例
时间片大小为2
时间片大小为5
- 从上面的时间片为5的示例的运行队列可以看出，在时间片比较大的情况下，RR算法和FCFS算法的运行队列非常相近。如果时间片太大（上面示例超过6时），使得每个进程都可以在一个时间片内完成，则RR算法会退化为FCFS算法，并且会增大进程响应时间，因此时间片不能太大
- 另一方面，进程调度是有时间代价（保存恢复运行环境），因此如果时间片太小，会导致进程切换过于频繁，系统花费大量时间处理进程切换，降低系统运行效率，因此时间片也不能太小
- 综上，一般情况下，设计时间片时要让切换进程的开销占比不超过1%
优缺点：
- 优点：公平，响应快，适用于分时操作系统
- 缺点：由于高频率的进程切换，因此有一定的开销，不区分任务的紧急程度
是否会导致饥饿
不会
优先级调度算法
算法思想
随着计算机发展，特别是实时操作系统出现，越来越多的应用场景需要根据任务的紧急程度决定处理顺序
算法规则
调度时选择优先级最高的作业/进程
用于作业/进程调度
即可用于作业调度，也可用于进程调度，甚至可以用到I/O调度中
是否可抢占
抢占式，非抢占式都可以，区别在于非抢占式只能在进程主动放弃处理机资源时进行调度，抢占式则需要在就绪队列发生变化时进行检查，是否有优先级变化是否需要抢占
示例
非抢占式
抢占式
优缺点
- 优点：用优先级区分紧急程度，适用于实时操作系统，可灵活调整对各种作业/进程的偏好承度
- 缺点：若不断有高优先级进程到来，会导致低优先级进程发生饥饿
是否会发生饥饿
会
补充
多级反馈队列调度算法
算法思想
对其他调度算法的折中权衡
算法规则
- 设置多级就绪队列，各级队列的优先级从高到低，时间片从小到大
- 新进程到达时优先进入第一级队列，按FCFS原则排队等待被分配时间片，若用完时间片进程还未结束，则进程进入下一级队列队尾，如果此时该进程已经处于最低级队列，则重新放回该队列队尾
- 只有第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密集型）
- 缺点：可能会导致饥饿
是否会导致饥饿
是，若不断有新进程到来，则老进程由于进入低优先级队列无法得到执行，进入饥饿状态
