先来先服务调度算法 (FCFS)

---

在多道程序设计中，需要对CPU进行调度，以便能够在更短的时间内或同时执行多个任务。通过CPU调度，决定就绪队列中哪个进程应该分配到CPU。因此，存在许多CPU调度算法来调度CPU。先来先服务 (FCFS) 调度是其中一种CPU调度算法。

先来先服务 (FCFS) 调度算法 (FIRST-COME, FIRST-SERVED)

FCFS被认为是最简单的CPU调度算法。在FCFS算法中，最先请求CPU的进程最先获得CPU资源。FCFS算法的实现是通过FIFO (先进先出) 队列来管理的。FCFS调度是非抢占式的。非抢占式意味着，一旦CPU被分配给一个进程，该进程就会一直占用CPU，直到它执行完工作或任务并释放CPU，或者请求I/O操作。

FCFS 调度的现实生活例子

作为FCFS调度的现实生活例子，可以观察到购物中心的收银台系统。排队中的第一个人先结账，然后下一个人有机会结账付款，依此类推。如果没有优先考虑VIP客户，则计费系统将按此方式进行（这意味着排队中的第一个人（第一个任务）将首先获得账单，在完成（执行）第一个客户的付款后，收银员（CPU）将关注其他客户（单独的任务），因为他们都在排队）。由于FCFS是非抢占式的，因此不会优先处理随机的重要任务。

FCFS 调度数学示例

在CPU调度问题中，解决问题时会用到一些术语，因此出于概念目的，将讨论这些术语如下：

• 到达时间 (AT) - 到达时间是指进程到达就绪队列的时间。

• 突发时间 (BT) 或进程的CPU时间 - 突发时间是特定进程完成执行所需的时间单位。

• 完成时间 (CT) - 完成时间是指进程终止的时间。

• 周转时间 (TAT) - 从到达时间到完成时间的总时间称为周转时间。TAT可以写成：

周转时间 (TAT) = 完成时间 (CT) – 到达时间 (AT) 或 TAT = 突发时间 (BT) + 等待时间 (WT)

• 等待时间 (WT) - 等待时间是指进程在等待分配CPU时，前一个进程正在CPU上执行的时间。WT可以写成：

等待时间 (WT) = 周转时间 (TAT) – 突发时间 (BT)

• 响应时间 (RT) - 响应时间是指CPU第一次分配给特定进程的时间。

  在非抢占式调度中，等待时间和响应时间通常相同。

• 甘特图 - 甘特图是一种可视化工具，有助于在项目中调度和管理特定任务。它在解决调度问题时使用，用于概念化进程如何在不同算法中被分配。

问题 1

考虑下表，求出完成时间 (CT)、周转时间 (TAT)、等待时间 (WT)、响应时间 (RT)、平均周转时间和平均等待时间。

进程 ID	到达时间	突发时间
P1	2	2
P2	5	6
P3	0	4
P4	0	7
P5	7	4

解答

甘特图

对于这个问题，CT、TAT、WT、RT显示在下表中：

进程 ID	到达时间	突发时间	CT	TAT=CT-AT	WT=TAT-BT	RT
P1	2	2	13	13-2= 11	11-2= 9	9
P2	5	6	19	19-5= 14	14-6= 8	8
P3	0	4	4	4-0= 4	4-4= 0	0
P4	0	7	11	11-0= 11	11-7= 4	4
P5	7	4	23	23-7= 16	16-4= 12	12

平均等待时间 = (9+8+0+4+12)/5 = 33/5 = 6.6 时间单位（时间单位可以认为是毫秒）

平均周转时间 = (11+14+4+11+16)/5 = 56/5 = 11.2 时间单位（时间单位可以认为是毫秒）

问题 2

考虑下表，求出完成时间 (CT)、周转时间 (TAT)、等待时间 (WT)、响应时间 (RT)、平均周转时间和平均等待时间。

进程 ID	到达时间	突发时间
P1	2	2
P2	0	1
P3	2	3
P4	3	5
P5	4	5

解答

甘特图：

对于这个问题，CT、TAT、WT、RT显示在下表中：

进程 ID	到达时间	突发时间	CT	TAT=CT-AT	WT=TAT-BT	RT
P1	2	2	4	4-2= 2	2-2= 0	0
P2	0	1	1	1-0= 1	1-1= 0	0
P3	2	3	7	7-2= 5	5-3= 2	2
P4	3	5	12	12-3= 9	9-5= 4	4
P5	4	5	17	17-4= 13	13-5= 8	8

平均等待时间 = (0+0+2+4+8)/5 = 14/5 = 2.8 时间单位（时间单位可以认为是毫秒）

平均周转时间 = (2+1+5+9+13)/5 = 30/5 = 6 时间单位（时间单位可以认为是毫秒）

*在CPU空闲（非活动）期间，没有进程被调度终止，因此在此期间它会保持空闲一小段时间。

FCFS 调度的优点

• 它是一种易于实现的算法，因为它不包含任何复杂的方法。

• 每个任务都应同时执行，因为它遵循FIFO队列。

• FCFS不会优先处理任何随机的重要任务，因此它是一个公平的调度算法。

FCFS 调度的缺点

• FCFS会导致车队效应，这意味着如果具有较长突发时间的进程首先出现在就绪队列中，则具有较短突发时间的进程可能会被阻塞，并且如果较长突发时间的任务永远占用时间，则较短突发时间的进程可能无法获得CPU。

• 如果一个具有较长突发时间的进程首先排队，那么其他具有较短突发时间的进程必须等待很长时间，因此它不太适合分时系统。

• 由于它是不可抢占式的，它不会在完成任务执行之前释放CPU。

*车队效应和饥饿现象听起来相似，但略有不同，因此建议不要将这两个术语视为相同的词。

结论

尽管FCFS易于实现和理解，但FCFS不适合交互式系统，并且不用于现代操作系统。可以使用其他CPU抢占式调度算法（例如“轮询调度”）来防止FCFS中的车队效应。