进程调度算法

调度算法的评价指标

先来先服务（FCFS）

先来先服务是非抢占式的算法

一个🌰

例题：各进程到达就绪队列的时间、需要的运行时间如下表所示。使用先来先服务调度算法，计算各进程的等待时间、平均等待时间、周转时间、平均周转时间、带权周转时间、平均带权周转时间。

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

解释：

先来先服务调度算法：按照到达的先后顺序调度，事实上就是等待时间越久的越优先得到服务。
因此，调度顺序为：P1->P2->P3->P4

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

短作业优先（SJF）

短作业优先算法分为抢占式和非抢占式

一个🌰：非抢占式

例题：各进程到达就绪队列的时间、需要的运行时间如下表所示。使用非抢占式的短作业优先调度算法，计算各进程的等待时间、平均等待时间、周转时间、平均周转时间、带权周转时间、平均带权周转时间。

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

解释：

短作业/进程优先调度算法：每次调度时选择当前已到达且运行时间最短的作业/进程。
因此，调度顺序为：P1->P3->P2->P4

刚开始只有p1到达，所以执行p1，然后当p1执行完毕后，此时是时刻7，剩余三个进程均已到达，所以按照运行时间最短的，执行p3

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

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

高响应比优先算法（HRRN）

高响应比优先算法是非抢占式的算法

响应比 = 等待时间+要求服务时间 / 要求服务时间

一个🌰

例题：各进程到达就绪队列的时间、需要的运行时间如下表所示。使用高响应比优先调度算法，计算各进程的等待时间、平均等待时间、周转时间、平均周转时间、带权周转时间、平均带权周转时间。

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

解释：

• 0时刻：只有P1 到达就绪队列，P1上处理机

• 7时刻（P1主动放弃CPU）：就绪队列中有P2 (响应比=(5+4)/4=2.25)、P3((3+1)/1=4)、P4((2+4)/4=1.5)，

• 8时刻（P3完成）： P2(2.5)、P4(1.75)

• 12时刻（P2完成）：就绪队列中只剩下P4

时间片轮转调度算法（RR）

时间片轮转调度算法属于抢占式

如果在一个时间片内，某个进程执行完毕，就会主动放弃处理机，发生调度

如果在一个时间片内，某个进程还未处理完毕，当时间片运行结束后，强行放弃处理机

一个🌰

优先级调度算法

优先级调度分为抢占式和非抢占式

• 非抢占式：当就绪队列中出现优先级高的进程，运行完当前进程，再选择优先级高的进程。
• 抢占式：当就绪队列中出现优先级高的进程，当前进程挂起，调度优先级高的进程运行。

但是依然有缺点，可能会导致低优先级的进程永远不会运行。

一个🌰：非抢占式

一个🌰：抢占式

多级反馈队列（Multilevel Feedback Queue）调度算法

是「时间片轮转算法」和「优先级算法」的综合和发展。

• 「多级」表示有多个队列，每个队列优先级从高到低，同时优先级越高时间片越短。
• 「反馈」表示如果有新的进程加入优先级高的队列时，立刻停止当前正在运行的进程，转而去运行优先级高的队列