0 进程调度算法的性能指标

• 周转时间 = 完成时刻 - 到达时刻
• 带权周转时间 = 周转时间 / 运行时间
• 等待时间 = 运行时刻 - 到达时刻
• 等待时间（计算型进程） = 周转时间 – 运行时间
• 等待时间（I/O 型进程） = 周转时间 - 运行时间 - I/O 操作时间
• 响应比 = (等待时间 + 要求服务时间) / 要求服务时间

【注】调度与切换的区别：

• 调度：决定资源分配给哪个进程的行为，是一种决策行为
• 切换：实际分配的行为，是执行行为（上下文切换）

1 【非抢占式】先来先服务（FCFS）调度算法

• 规则：考虑的是哪个进程先到达就绪队列，按照进程到达的先后顺序进行服务
• 优点：公平、算法实现简单
• 缺点：对长作业有利，对短作业不利
• 饥饿：不会导致饥饿
• 案例：

进程	到达时间	运行时间
P1	0	7
P2	2	4
P3	4	1
P4	5	4

关键时刻	就绪队列	备注
0	P1	P1 就绪
0	空	P1 运行
2	P2	P2 就绪
4	P3 --> P2	P3 就绪
5	P4 --> P3 --> P2	P3 就绪
7	P4 --> P3	P2 运行
11	P4	P3 运行
12	空	P4 运行

性能指标	进程P1	进程P2	进程P3	进程P4
周转时间 = 完成时刻 - 到达时刻	7-0=7	11-2=9	12-4=8	16-5=11
带权周转时间 = 周转时间 / 运行时间	7/7=1	9/4=2.25	8/1=8	11/4=2.75
等待时间 = 周转时间 – 运行时间	7-7=0	9-4=5	8-1=7	11-4=7

• 平均周转时间 = (7+9+8+11)/4 = 8.75
• 平均带权周转时间 = (1+2.25+8+2.75)/4 = 3.5
• 平均等待时间 = (0+5+7+7)/4 = 4.75

2 【非抢占式+抢占式】短进程优先（SPF）调度算法

2.1 【非抢占式】短进程优先（SPF）调度算法

• 规则：每次调度时选择当前已到达且运行时间最短的进程
• 优点：“最短的”平均等待时间、平均周转时间
• 缺点：对短作业有利，对长作业不利；另外，作业/进程的运行时间是由用户提供的，并不一定真实，不一定能做到真正的短作业优先
• 饥饿：会导致饥饿，如果源源不断地有短进程到来，可能使长进程长时间得不到服务，产生“饥饿”现象
• 案例：

进程	到达时间	运行时间
P1	0	7
P2	2	4
P3	4	1
P4	5	4

关键时刻	就绪队列（括号内为运行时间，按运行时间排序）	备注
0	P1	P1 就绪
0	空	P1 运行
2	P2(4)	P2 就绪
4	P2(4) --> P3(1)	P3 就绪
5	P4(4) --> P2(4) --> P3(1)	P4 就绪
7	P4(4) --> P2(4)	P3 运行
8	P4(4)	P2 运行
12	空	P4 运行

性能指标	进程P1	进程P2	进程P3	进程P4
周转时间 = 完成时刻 - 到达时刻	7-0=7	12-2=10	8-4=4	16-5=11
带权周转时间 = 周转时间 / 运行时间	7/7=1	10/4=2.5	4/1=4	11/4=2.75
等待时间 = 周转时间 – 运行时间	7-7=0	10-4=6	4-1=3	11-4=7

• 平均周转时间 = (7+4+10+11)/4 = 8
• 平均带权周转时间 = (1+4+2.5+2.75)/4 = 2.56
• 平均等待时间 = (0+3+6+7)/4 = 4

2.2 【抢占式】最短剩余时间（SRTN）优先算法

• 即：【抢占式】短进程优先（SPF）调度算法
• 规则：
  • 当有进程加入就绪队列时：需要调度，如果新到达的进程剩余时间比当前运行的进程剩余时间更短，则由新进程抢占处理机，当前运行进程重新回到就绪队列
  • 当一个进程完成时：需要调度，在就绪队列中选择剩余时间最短的进程运行
• 优点：“最短的”平均等待时间、平均周转时间
• 缺点：对短作业有利，对长作业不利；另外，作业/进程的运行时间是由用户提供的，并不一定真实，不一定能做到真正的短作业优先
• 饥饿：会导致饥饿，如果源源不断地有短进程到来，可能使长进程长时间得不到服务，产生“饥饿”现象
• 案例：

进程	到达时间	运行时间
P1	0	7
P2	2	4
P3	4	1
P4	5	4

关键时刻	就绪队列（括号内为剩余运行时间，按剩余时间排序）	备注
0	P1(7)	P1 就绪
0	空	P1 运行
2	P1(5) --> P2(4)	P2 和 P1 就绪
2	P1(5)	P2 运行
4	P1(5) --> P2(2) --> P3(1)	P3 和 P2 就绪
4	P1(5) --> P2(2)	P3 运行
5	P1(5) --> P4(4) --> P2(2)	P4 就绪
5	P1(5) --> P4(4)	P2 运行
7	P1(5)	P4 运行
11	空	P1 运行

性能指标	进程P1	进程P2	进程P3	进程P4
周转时间 = 完成时刻 - 到达时刻	16-0=16	7-2=5	5-4=1	11-5=6
带权周转时间 = 周转时间 / 运行时间	16/7=2.28	5/4=1.25	1/1=1	6/4=1.5
等待时间 = 周转时间 – 运行时间	16-7=9	5-4=1	1-1=0	6-4=2

• 平均周转时间 = (16+5+1+6)/4 = 7
• 平均带权周转时间 = (2.28+1.25+1+1.5)/4 = 1.50
• 平均等待时间 = (9+1+0+2)/4 = 3

3 【非抢占式】高响应比优先（HRRN）调度算法

• 响应比 = (等待时间 + 要求服务时间) / 要求服务时间
• 规则：调度时计算所有就绪进程的响应比，选响应比最高的进程上处理机
• 优点：综合考虑了等待时间和运行时间
  • 等待时间相同时，要求服务时间短的优先（SJF 的优点）
  • 运行时间相同时，等待时间长的优先（FCFS 的优点）
  • 对于长作业来说，随着等待时间越来越久，其响应比也会越来越大，从而避免了长作业饥饿的问题
• 饥饿：不会导致饥饿
• 案例：

进程	到达时间	运行时间
P1	0	7
P2	2	4
P3	4	1
P4	5	4

关键时刻	就绪队列（括号内为响应比，按响应比大小排序）	备注
0	P1	P1 就绪
0	空	P1 运行
7	P4【响应比(2+4)/4=1.5】–> P2【响应比=(5+4)/4=2.25】–> P3【响应比(3+1)/1=4】	P2、P3 和 P4 均已就绪
7	P4【响应比(2+4)/4=1.5】–> P2【响应比=(5+4)/4=2.25	P3 运行
8	P4【响应比(3+4)/4=1.75】–> P2【响应比=(6+4)/4=2.5	P2 和 P4 均已就绪
8	P4【响应比(3+4)/4=1.75】	P2 运行
12	P4【响应比(7+4)/4=2.75】	P4 已就绪
12	空	P4 运行

4 【抢占式】时间片轮转（RR）调度算法

• 规则：
  • 按照各进程到达就绪队列的顺序，轮流让各个进程执行一个时间片（由时钟装置发出时钟中断来通知 CPU 时间片已到）
  • 若进程未在一个时间片内执行完，则剥夺处理机，将进程重新放到就绪队列队尾重新排队
  • 进程运行完会主动放弃处理机，此时也需要按上述两条规则进行调度
• 优点：公平，响应快，适用于分时操作系统
• 缺点：由于高频率的进程切换，因此有一定开销；不区分任务的紧急程度
• 饥饿：不会导致饥饿
• 时间片太大或太小的影响：
  • 时间片太大：退化为先来先服务（FCFS）算法
  • 时间片太小：进程切换过于频繁，系统会花大量的时间来处理进程切换，从而导致实际用于进程执行的时间比例减少
• 注意：常用于分时操作系统，更注重“响应时间”，因而此处不计算周转时间

案例一：时间片为 2

进程	到达时间	运行时间
P1	0	5
P2	2	4
P3	4	1
P4	5	6

调度时只做两件事：（1）时间片未用完的进程放到队尾排队；（2）取队头进程上处理机

关键时刻	就绪队列（括号内为剩余运行时间）	备注
0	P1(5)	P1 就绪
0	空	P1 运行（取队头进程上处理机）
2	P1(3) --> P2(4)	P2 和 P1 就绪（时间片未用完的进程放到队尾排队）
2	P1(3)	P2 运行，P1 就绪（取队头进程上处理机）
4	P2(2) --> P3(1) --> P1(3)	P3 和 P2 就绪（时间片未用完的进程放到队尾排队）
4	P2(2) --> P3(1)	P1 运行（取队头进程上处理机）
5	P4(6) --> P2(2) --> P3(1)	P4 就绪（由于 P1 的时间片未用完，因此不调度）
6	P1(1) --> P4(6) --> P2(2) --> P3(1)	P1 就绪（时间片未用完的进程放到队尾排队）
6	P1(1) --> P4(6) --> P2(2)	P3 运行（取队头进程上处理机）
7	P1(1) --> P4(6)	P2 运行（取队头进程上处理机）
9	P1(1)	P4 运行（取队头进程上处理机）
11	P4(4) --> P1(1)	P4 就绪（时间片未用完的进程放到队尾排队）
11	P4(4)	P1 运行（取队头进程上处理机）
12	P4(4)	P4 运行（取队头进程上处理机）
14	P4(2)	P4 就绪（时间片未用完的进程放到队尾排队）
14	空	P4 执行（取队头进程上处理机）

案例二：时间片为 5（时间片过大）

进程	到达时间	运行时间
P1	0	5
P2	2	4
P3	4	1
P4	5	6

关键时刻	就绪队列（括号内为剩余运行时间）	备注
0	P1(5)	P1 就绪
0	空	P1 运行（取队头进程上处理机）
2	P2(4)	P2 就绪
4	P3(4) --> P2(4)	P3 就绪
5	P4(6) --> P3(4) --> P2(4)	P4 就绪
5	P4(6) --> P3(4)	P2 运行（取队头进程上处理机）
9	P4(6)	P3 运行（取队头进程上处理机）
10	空	P4 运行（取队头进程上处理机）
15	P4(1)	P4 就绪（时间片未用完的进程放到队尾排队）
15	空	P4 运行（取队头进程上处理机）

5 【非抢占式+抢占式】优先级调度算法

5.1 【非抢占式】优先级调度算法

• 规则：
  • 每次调度时选择当前已到达且优先级最高的进程
  • 当前进程主动放弃处理机时发生调度
• 优点：用优先级区分紧急程度、重要程度，适用于实时操作系统。可灵活地调整对各种进程的偏好程度
• 缺点：若源源不断地有高优先级进程到来，则可能导致饥饿
• 饥饿：会导致饥饿
• 案例：（优先数越大，优先级越高）

进程	到达时间	运行时间	优先级
P1	0	7	1
P2	2	4	2
P3	4	1	3
P4	5	4	2

关键时刻	就绪队列（括号内为优先级，按优先级排序）	备注
0	P1(1)	P1 就绪
0	空	P1 运行
2	P2(2)	P2 就绪
4	P2(2) --> P3(3)	P3 就绪
5	P4(2) --> P2(2) --> P3(3)	P4 就绪（优先级相同则默认排到后面）
7	P4(2) --> P2(2)	P3 运行
8	P4(2)	P2 运行
12	P4(2)	P4 运行

5.2 【抢占式】优先级调度算法

• 规则：
  • 每次调度时选择当前已到达且优先级最高的进程
  • 当前进程主动放弃处理机时发生调度
  • 当就绪队列发生改变时也需要检查是会发生抢占
• 优点：用优先级区分紧急程度、重要程度，适用于实时操作系统。可灵活地调整对各种进程的偏好程度
• 缺点：若源源不断地有高优先级进程到来，则可能导致饥饿
• 饥饿：会导致饥饿
• 案例：（优先数越大，优先级越高）

进程	到达时间	运行时间	优先级
P1	0	7	1
P2	2	4	2
P3	4	1	3
P4	5	4	2

关键时刻	就绪队列（括号内为优先级，按优先级排序）	备注
0	P1(1)	P1 就绪
0	空	P1 运行
2	P1(1) --> P2(2)	P2 和 P1 就绪
2	P1(1)	P2 运行
4	P1(1) --> P2(2) --> P3(3)	P3 和 P2 就绪
4	P1(1) --> P2(2)	P3 运行
5	P1(1) --> P4(2) --> P2(2)	P4 就绪
5	P1(1) --> P4(2)	P2 运行
7	P1(1)	P4 运行
11	空	P1 运行

5.3 优先级的设置

根据优先级是否可以动态改变，可将优先级分为静态优先级和动态优先级：

• 静态优先级：创建进程时确定，之后一直不变
• 动态优先级：创建进程时有一个初始值，之后会根据情况动态地调整优先级
  • 如果某进程在就绪队列中等待了很长时间，则可以适当提升其优先
  • 如果某进程占用处理机运行了很长时间，则可适当降低其优先级
  • 如果发现一个进程频繁地进行 I/O 操作，则可适当提升其优先级

优先级的设置一般遵守：

• 系统进程优先级 > 用户进程
• 前台进程优先级 > 后台进程
• I/O 型进程（频繁使用 I/O 设备的进程） > 计算型进程（频繁使用 CPU 的进程）

【注】I/O 设备和 CPU 可以并行工作。如果优先让 I/O 繁忙型进程优先运行的话，则越有可能让 I/O 设备尽早地投入工作，则资源利用率、系统吞吐量都会得到提升。

【例】（2016 统考真题）某进程调度程序采用基于优先数（priority）的调度策略，即选择优先数最小的进程运行，进程创建时由用户指定一个 nice 作为静态优先数。为了动态调整优先数，引入运行时间 cpuTime 和等待时间 waitTime，初值均为 0。进程处于执行态时，cpuTime 定时加 1，且 waitTime 置 0；进程处于就绪态时，cpuTime 置 0，waitTime 定时加 1。请回答下列问题。

（1）若调度程序只将 nice 的值作为进程的优先数，即 priority = nice，则可能会出现饥饿现象，为什么?

（2）使用 nice、cpuTime 和 waitTime 设计一种动态优先数计算方法，以避免产生饥饿现象，并说明 waitTime 的作用。

【解】（1）由于采用了静态优先数，当就绪队列中总有优先数较小的进程时，优先数较大的进程一直没有机会运行，因而会出现饥饿现象。

（2）优先数的计算公式为：priority = nice + k1 * cpuTime - k2 * waitTime，其中k1 > 0，k2 > 0。waitTime 可使长时间等待的进程的优先数减少。

6 【抢占式】多级反馈队列调度算法

• 规则：
  • 设置多级就绪队列，各级队列优先级从高到低，时间片从小到大
  • 新进程到达时先进入第 1 级队列，按 FCFS 原则排队等待被分配时间片，若用完时间片进程还未结束，则进程进入下一级队列队尾（如果此时已经是在最下级的队列，则重新放回该队列队尾）
  • 只有第 k 级队列为空时，才会为 k+1 级队头的进程分配时间片
  • 被抢占处理机的进程重新放回原队列队尾
• 优点：
  • 对各类型进程相对公平（FCFS 的优点）
  • 每个新到达的进程都可以很快就得到响应（RR 的优点）
  • 短进程只用较少的时间就可完成（SPF 的优点）
  • 不必实现估计进程的运行时间（避免用户作假）
  • 可灵活地调整对各类进程的偏好程度，比如 CPU 密集型进程、I/O 密集型进程（可以将因 I/O 阻塞的进程重新放回原队列，这样 I/O 型进程就可以保持较高优先级）
• 饥饿：会导致饥饿
• 案例：

进程	到达时间	运行时间
P1	0	8
P2	1	4
P3	5	1

• 0 时刻（括号内为进程剩余时间，下同）：P1 到达，插入第 1 级队列末尾；P1 开始运行

队列	优先级	时间片	就绪队列
第 1 级队列	最高	1	P1(8)
第 2 级队列	次高	2
第 3 级队列	最低	4

• 1 时刻：P1 运行完一个时间片未结束，插入第 2 级队列末尾；P2 到达，插入第 1 级队列末尾；P2 开始运行

队列	优先级	时间片	就绪队列
第 1 级队列	最高	1	P2(4)
第 2 级队列	次高	2	P1(7)
第 3 级队列	最低	4

• 2 时刻：P2 运行完一个时间片未结束，插入第 2 级队列末尾；P1 开始运行

队列	优先级	时间片	就绪队列
第 1 级队列	最高	1
第 2 级队列	次高	2	P2(3) --> P1(7)
第 3 级队列	最低	4

• 4 时刻：P1 运行完一个时间片未结束，插入第 3 级队列末尾；P2 开始运行

队列	优先级	时间片	就绪队列
第 1 级队列	最高	1
第 2 级队列	次高	2	P2(3)
第 3 级队列	最低	4	P1(5)

• 5 时刻：P3 到达，插入第 1 级队列末尾；P2 被抢占，放回第 2 级队列末尾；P3 运行

队列	优先级	时间片	就绪队列
第 1 级队列	最高	1	P3(1)
第 2 级队列	次高	2	P2(2)
第 3 级队列	最低	4	P1(5)

• 6 时刻：P3 运行完毕；P2 开始运行

队列	优先级	时间片	就绪队列
第 1 级队列	最高	1
第 2 级队列	次高	2	P2(2)
第 3 级队列	最低	4	P1(5)

• 8 时刻：P2 运行完毕；P1 开始运行

队列	优先级	时间片	就绪队列
第 1 级队列	最高	1
第 2 级队列	次高	2
第 3 级队列	最低	4	P1(5)

• 12 时刻：P1 运行完一个时间片未结束，插入第 3 级队列末尾；P1 开始运行

队列	优先级	时间片	就绪队列
第 1 级队列	最高	1
第 2 级队列	次高	2
第 3 级队列	最低	4	P1(1)

• 13 时刻：P1 运行完毕

队列	优先级	时间片	就绪队列
第 1 级队列	最高	1
第 2 级队列	次高	2
第 3 级队列	最低	4