# 调度算法

# 先来先服务 (FCFS) 调度算法（作业调度 + 进程调度）

周转时间 = 完成时间 - 到达时间

带权周转时间 = 周转时间 / 服务时间

FCFS 算法对长作业（CPU 时间长的作业）有利，对短作业不利。

# 最短作业 (SJF) 调度算法（作业调度 + 进程调度）

对这个情况而言，SJF 比 FCFS 更好，尤其是 C。

SJF 调度算法也存在不容忽视的缺点：

• 该算法对长作业不利，更严重的是，如果有一长作业（进程）进入系统的后备队列（就绪队列），由于调度程序总是优先调度那些（即使是后进来的）短作业（进程），将导致长作业（进程）长期不被调度。
• 该算法完全未考虑作业的紧迫程度，因而不能保证紧迫性作业（进程）会被及时处理。
• 由于作业（进程）的长短只是根据用户所提供的估计执行时间而定的，而用户又可能会有意或无意地缩短其作业的估计运行时间，致使该算法不一定能真正做到短作业优先调度。

# 高响应比优先 (HRRN) 调度算法（作业调度 + 进程调度）

HRRN (Highest Response Ratio Next) = HRRF (Highest Response Ratio First)

NUIST 老师习惯用 HRRF，我觉得 HRRN 更合适

FCFS 与 SJF 是片面的调度算法。FCFS 只考虑作业等候时间而忽视了作业的计算时间问题；SJF 只考虑用户估计的作业计算时间而忽视了作业等待时间。

HRRN 是介乎这两者之间的非剥夺式算法，既考虑作业等待时间，又考虑作业的运行时间，既照顾短作业又不使长作业的等待时间过长，改进了调度性能。

响应比（带权周转时间） = 作业周转时间 / 作业处理时间 = （作业等待时间 + 作业处理时间） / 作业处理时间 = 1 + 作业等待时间 / 作业处理时间

• 短作业容易得到较高响应比（分母小）
• 长作业等待时间足够长后，也将获得足够高的响应比（分子足够大）
• 饥饿现象不会发生

# 例题 1

首先调度 J1，然后计算响应比：

J2 1+15/15=2
J3 1+10/5=3
J4 1+5/10=1.5

J3 的响应比最大，调度 J3。随后计算 J3 完成后的响应比：

t=20+5
J2 1+20/15=2.3
J4 1+10/10=2

所以调用 J2，最后调用 J4。

# 例题 2

FCFS J1 2 3 4
8 10 2 1
10 10.5 1.5+1/6 (1.5+1/6)/0.5=3.3
10.5 10.6 1.6 1.6/0.1=16
10.6 10.8 0.8+2/3 (0.8+2/3)/0.2=7.3
(2+1.5+1/6+1.6+0.8+2/3)/4=1.68
(1+(1.5+1/6)/0.5+1.6/0.1+(0.8+2/3)/0.2)/4=6.92
SJF J1 3 4 2
8 10 2 1
10.3 10.8 1.8+1/6 (1.8+1/6)/0.5=3.93
10 10.1 1.1 1.1/0.1=11
10.1 10.3 0.3+2/3 (0.3+2/3)/0.2=4.83
(2+1.8+1/6+1.1+0.3+2/3)/4=1.51
(1+(1.8+1/6)/0.5+1.1/0.1+(0.3+2/3)/0.2)/4=5.19
HRRF J1 
8 10 2 1
(10) J2 未完成

# 高优先权 (FPF) 调度算法（作业调度 + 进程调度）

# 非抢占式优先权算法

和 HRRN 算法很像，进程会正常运行，直到结束之后才发生调度，在调度的时候会选择队列中优先级最高的进程。

# 抢占式优先权算法

除了正常运行结束会发生调度之外，每次就绪队列有新的进程到达时还会做一次检查，如果新到达进程优先级高于正在运行进程的优先级，那么新到达进程会抢占处理机。

# 静态优先权

静态优先级，指的是进程的优先级在它创建的时候就确定了，此后一直不会改变。一般认为系统进程优先级要高于用户进程优先级；前台进程优先级高于后台进程优先级；I/O 型进程优先级会比较高。

# 动态优先权

动态优先级，会尽量遵循公平的原则。也就是说，如果某个进程实在等得太久，那么不妨提高它的优先级，让他有机会被调度；反之，如果某个进程占用处理机时间过长，那么就要考虑降低它的优先级，不要让他一直 “霸占” 处理机了。另外，之前说过 I/O 型进程的优先级会很高，所以如果某个进程频繁进行 I/O 操作，也可以考虑提高它的优先级。

优先级算法的优点在于区分了各个进程的紧急程度，比较紧急重要的进程会优先得到处理，因此它适用于实时操作系统。另外，由于动态优先级的存在，使得它对进程的调度相对灵活很多。缺点则是，如果源源不断进来了一些高优先级的进程，那么优先级相对较低的进程可能一直无法执行，进而导致饥饿现象的发生。这点和 HRRN 算法也是很像的。（其实也可以把 HRRN 算法看作优先级算法的一种特殊情况，将响应比作为优先级评判的标准）

# 例题 1

可剥夺：

开始执行时间:进程 0:P1 3:P2 5:P3 10:P4 20:P3 21:P1 23:DONE
进程 周转时间 带权周转时间
P1 23-0=23 23/5=4.6
P2 5-3=2 2/2=1
P3 21-5=16 16/6=2.67
P4 20-10=10 10/10=1
平均周转时间：12.75
带权周转时间：2.32

# 时间片轮转 (RR) 调度算法（进程调度）

RR 算法的特点则在于 “公平分配”，按照进程到达就绪队列的顺序，轮流让每个进程执行一个相等长度的时间片，若在自己的时间片内没有执行完，则进程自动进入就绪队列队尾，并调度队头进程运行。整体呈现出 “交替” 的特点。因为进程即使没运行完也会发生调度，所以这是一个抢占式的算法。

答题需表格 + 执行顺序时间线

# 例题 1

开始执行时间:进程(剩余时间)：0:P1(33) 20:P2(0) 37:P3(48) 57:P4(4) 77:P1(13) 97:P3(28) 117:P4(0) 121:P1(0)  134:P3(8) 154:P3(0) 162:DONE
P1 134 134/50
P2 17 17/17
P3 162 162/68
P4 121 121/24
平均周转时间：108.5
带权平均周转时间：2.78

# 多级反馈调度算法（进程调度）

• 有多个级别的就绪队列，各级队列优先级从高到低，时间片从小到大
• 每次有新进程到达，都会首先进入第一级队列，并按 FCFS 算法被分配时间片。如果时间片用完了而进程还没执行完，那么该进程将被送到下一级队列队尾。如果当前已经是最后一级，则重新放回当前队列队尾
• 当且仅当上层级别的队列为空时，下一级队列的进程才有机会被调度
• 关于抢占：如果某个进程运行的时候，比它所在队列级别更高的队列中有新进程到达，则那个新进程会抢占处理机，而当前正在运行的进程会被送到当前队列队尾

优点：

• 对各类型进程相对公平（FCFS 的优点）：谁先进来，谁就会处于高级队列，优先得到服务
• 每个新到达的进程都可以很快就得到响应（RR 的优点）：新到达的进程首先在高级队列，可以很快得到响应
• 短进程只用较少的时间就可完成（SPF 的优点）：不需要经历过多的队列
• 可灵活地调整对各类进程的偏好程度，比如 CPU 密集型进程、I/O 密集型进程（拓展：可以将因 I/O 而阻塞的进程重新放回原队列，这样 I/O 型进程就可以保持较高优先级）
• 对各类型用户友好。对于终端型用户来说，他们提交的大多属于较小的交互型作业，系统只要能使这些作业在第一队列所规定的时间片内完成，便可使终端型作业用户都感到满意；对短批处理作业用户来说，只需在第一队列中执行一个时间片，或至多在第二和第三队列中各执行一个时间片即可完成；对长批处理作业用户来说，只要让作业依次在第 1, 2，… n 个队列中运行，然后再按轮转方式运行，用户不必担心其作业长期得不到处理。

缺点：

• 可能会导致饥饿。若有源源不断的短进程到达第一队列，那么这些进程会持续被调度，使得下面一级的那些进程一直得不到调度，导致饥饿现象的发生。

# 例题 1

D 就绪队列 2 有误

# 例题 2（只有 3 个就绪队列的例题 1）

A 2-0=2 2/2
B 22-2=20 20/6
C 58-4=54 54/10
D 66-6=60 60/14
E 110-8=102 102/18
F 118-10=108 108/22
G 146-12=134 134/26
H 154-14=140 140/30
I 166-16=150 150/34
平均周转时间：85.56
带权平均周转时间：4.31

平均周转时间 = 结束时间 - 开始时间 ×，平均周转时间 = 结束时间 - 到达时间 √。若没有给到达时间，则默认所有任务一开始就同时到达。