CPU 调度算法

操作系统中存在多种调度算法，有的适用于作业调度，有的适用于进程调度，也有的两者均可适用。

调度计算的中心是一条真实可行的时间线。每到一个决策时刻，只比较已经到达且就绪的任务；运行后减少它的剩余服务量，完成时记录结束时间。

先固定题目规则

调度计算约定：单CPU、无I/O、无切换开销，优先级数值越大越高；同一时刻到达按表中顺序；并列时先到者优先；最短剩余时间或优先级相同时保留当前任务。

新任务尚未到达时，不能因为预先看见它很短就提前运行它。没有就绪任务则CPU空闲，除非题目明确采用另一种允许主动等待的策略。

根据是否抢占可以对调度算法进行如下分类：

• 非抢占型调度算法：先来先服务、最短任务优先、最高响应比优先
• 抢占型调度算法：时间片轮转、多级反馈队列

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

FCFS 调度算法是一种最简单的调度算法，既可用于作业调度，也可用于进程调度。

在作业调度中，FCFS 算法每次从后备作业队列中选择最早进入该队列的一个或多个作业，将它们调入内存，分配必要的资源，创建相应的进程，并放入就绪队列。

在进程调度中，FCFS 算法每次从就绪队列中选择最早进入该队列的进程，将CPU 分配给它，使其投入运行，直到该进程运行完成，或因某种原因而进入阻塞态，此时才会交出CPU。

先来先服务（First-Come, First-Served，FCFS）按照进程到达的顺序 分配依次执行。先到达的进程先执行，后续进程等待直到前一个进程执行才能进一步执行。

假设系统中有4个作业，它们的提交时间分别是 8.0、8.4、8.8和9.0，运行时间依次为2、1、0.5和0.2。若系统采用FCFS 算法，则这组作业的平均等待时间、平均周转时间和平均带权周转时间如表2.2所示。

FCFS 算法属于非抢占式算法。从表面上看，它对所有作业都是公平的；但若一个长作业先到达系统，则会导致后续的许多短作业长时间等待，因此它不适合作为分时系统和实时系统的主要调度策略。不过，FCFS 算法常被结合到其他调度策略中使用。例如，在采用优先级调度的系统中，对于多个具有相同优先级的进程，通常按照FCFS 的原则进行调度。

FCFS 算法的特点是实现简单，但效率较低。它对长作业较为有利，而对短作业相对不利（与 SJF 或高响应比优先调度算法相比）。此外，它更有利于CPU 繁忙型作业；而对于I/O 繁忙型作业，由于其运行过程中会频繁发起I/O 请求并进入阻塞状态，本可及时让出CPU 以提高系统并发性，但在FCFS 调度下，若排在长作业之后，则仍需长时间等待，难以发挥其优势。

表2.2　FCFS 调度算法的性能：

平均等待时间=1.575；平均周转时间=2.5；平均带权周转时间≈5.625。

非抢占地按进入就绪队列的先后选择，运行到本段完成或阻塞。公共例子的时间线是：

0—7 A | 7—11 B | 11—12 C | 12—16 D

周转为7、9、8、11，平均35/4；等待为0、5、7、7，平均19/4。短任务C到达后仍要等A、B，体现长任务阻挡后续短任务的现象。

短作业优先 (SJF)调度算法

短作业优先(SJF)调度算法是一种按照作业或进程的预计运行时间进行调度的策略。

在作业调度中，SJF 算法从后备作业队列中选择一个或多个估计运行时间最短的作业，将它们调入内存，分配资源并创建进程。

在进程调度中，该策略称为短进程优先(SPF)，即从就绪队列中选择估计运行时间最短的进程，将 CPU 分配给它，使其立即执行，直至完成，或因某种事件而阻塞时才释放CPU。

最短作业优先（Shortest Job First，SJF）算法在从就绪队列中选择进程时，会 选择运行时间最短 的进程进行执行。

在题目中进程的运行时间一般都是给定的，所以 SJF 算法比较容易实现。但是在真实的系统中进程的运行时间是不确定的，所以在使用该算法时操作系统需要对进程的运行时间进行预估。

例如，考虑与表2.2中示例相同的一组作业，若系统采用SJF 调度算法，则这组作业的平均等待时间、平均周转时间和平均带权周转时间如表2.3所示。

表2.3　SJF 调度算法的性能：

平均等待时间=1.175；平均周转时间=2.1；平均带权周转时间=3.525。

尽管SJF 算法在某些指标上表现优异，但它也存在不容忽视的缺点：

1)对长作业不利。由表2.2与表2.3可知，在 SJF 调度下，长作业的周转时间明显增加。更严重的是，若一个长作业进入系统的后备队列，而此后不断有新的短作业到达，调度程序将总是优先调度这些短作业，导致长作业长期得不到服务，从而产生饥饿现象（注意：饥饿是由于调度策略导致的无限期等待，与死锁中的环形等待有本质区别）。

2)未考虑作业的紧迫程度。该算法仅依据运行时间长短进行调度，完全忽略了作业的截止时间或紧急性，因此无法保证紧迫性作业被及时处理。

3)作业的“长短”由用户提交的估计值决定，而用户可能有意或无意地低估其作业的实际运行时间，以获取调度优势，从而使算法难以真正实现“短作业优先”的目标。

SPF 算法既可以是非抢占式的（默认情况），也可以是抢占式的。在抢占式版本中，当一个新进程到达就绪队列时，若其估计运行时间比当前进程的剩余执行时间更短，则立即暂停当前进程，将 CPU 分配给新进程。这种抢占式策略也称最短剩余时间优先调度算法。

注意当所有作业同时到达且运行时间已知时，SJF 算法的平均等待时间和平均周转时间是最优的。

短作业优先 SJF 与最短剩余时间 SRTF

非抢占SJF每次重新分配时选择已就绪任务中服务时间最短的。0时只有A，它会运行到7；随后选C，再选同为4但较早到达的B，最后D：

0—7 A | 7—8 C | 8—12 B | 12—16 D

SRTF允许新到达的更短剩余任务抢占。2时A还剩5，B需4；4时B还剩2，C需1，因此：

0—2 A | 2—4 B | 4—5 C | 5—7 B | 7—11 D | 11—16 A

A、B、C、D的完成时刻为16、7、5、11，周转16、5、1、6，平均7。5时C结束，B还剩2，比D的4和A的5都短。

SJF在所有任务同时到达、服务量已知且采用相应非抢占模型时，可以最小化平均等待和平均周转。不同到达时刻、截止期或带权指标会改变比较条件；“短者优先”不意味着优化所有指标。持续到达短任务还可能让长任务饥饿。

高响应比优先调度算法

高响应比优先调度算法主要用于作业调度，是对FCFS 算法和SJF 算法的一种综合平衡。它在调度决策时同时考虑每个作业的等待时间和估计运行时间。在每次进行作业调度时，系统首先计算后备作业队列中每个作业的响应比，然后选择响应比最高的作业调入内存并执行。

响应比的计算公式为响应比=（等待时间+估计运行时间）/估计运行时间由该公式可知：①当作业的等待时间相同时，估计运行时间越短，响应比越高，因此有利于短作业，这与 SJF 算法的特性相似。②当估计运行时间相同时，响应比由等待时间决定，等待时间越长，响应比越高，这体现了FCFS 调度的公平性。③对于长作业，其响应比会随着等待时间的增加而不断提高。当等待时间足够长时，即使估计运行时间较长，其响应比也可能超过其他作业，从而被调度执行。这一机制有效避免了长作业因长期得不到服务而产生的饥饿现象。

最高响应比优先（Highest Response Ratio Next，HRRN）算法从就绪队列中选择 响应比 最高的进程进行执行。

其中 响应比 （Response Ratio）的计算公式如下：

Response Ratio=BTWT+BT=BTTAT

其中 W （Waiting Time）为进程的等待时间， B （Burst Time）为进程的要求服务时间（从执行开始到结束所需时间）。

这种计算策略可以有效地避免饥饿现象，即一个进程等待了很长时间但仍没有得到执行。一个进程的等待时间越长，其 响应比 就会更大，进而优先得到执行机会。一个进程的执行时间很长，其 响应比 就会越小，会优先调度其他进程。

• 时刻 0：只有 P1 到达，执行 P1。
• 时刻 5：P1 执行完成。P2 的 响应比 为 $4 + 3$ / 3 ≈ 2.33，P3 的 响应比 为 $3 + 8$ / 8 = 1.375，P4 的 响应比 为 $2 + 6$ / 6 ≈ 1.33，此时 P2 的 响应比 最大，执行 P2。
• 时刻 8：P2 执行完成。P3 的 响应比 为 $6 + 8$ / 8 = 1.75，P4 的 响应比 为 $5 + 6$ / 6 ≈ 1.83。此时 P4 的 响应比 更大，执行 P4。
• 时刻 14：P4 执行完成，只剩下 P3 了，最后执行 P3。

所以进程的执行顺序为 P1、P2、P4、P3，每个进程的时间指标如下表所示：

响应比为 1+等待时间/预计服务时间，在每次非抢占选择时重新计算。等待相同偏向短任务；服务相同偏向等得久的任务。

公共例子7时：B响应比9/4，C为4，D为6/4，先选C；8时B为10/4，D为7/4，再选B。结果这次与SJF相同，不表示两个算法总相同。

另一个状态：当前时刻10，X到达0需10，Y到达8需3。X响应比2，Y为5/3，HRRN选X，SJF则选Y。不能把响应比中的等待时间替换成已完成之后才能知道的真实周转。

优先级调度算法

优先级调度算法通过为每个作业或进程分配一个优先级，以反映其紧迫程度。

在作业调度中，优先级调度算法每次从后备作业队列中选择优先级最高的一个或多个作业，将它们调入内存，分配资源并创建进程。

在进程调度中，该算法每次从就绪队列中选择优先级最高的进程，将 CPU 分配给它，使其投入运行。

根据是否允许抢占，优先级调度算法可分为以下两类：

1)非抢占式优先级调度算法。当一个进程正在CPU 上运行时，即使有更高优先级的进程进入就绪队列，系统仍允许当前进程继续执行，直到其因自身原因（如任务完成或等待事件）而让出CPU 时，此时将CPU 分配给就绪队列中优先级最高的进程。

2)抢占式优先级调度算法。当一个进程正在CPU 上运行时，若有更高优先级的进程进入就绪队列，系统将立即暂停当前进程，将CPU 分配给优先级更高的进程。

此外，根据进程创建后其优先级是否可变，优先级又可分为静态与动态两类：

1)静态优先级。优先级在进程创建时确定，并在其整个运行期间保持不变。确定静态优先级的主要依据包括：进程类型、对资源的需求、用户指定的优先级等。优点是实现简单，系统开销小；缺点是不够灵活，可能出现低优先级进程长期得不到调度的饥饿现象。

2)动态优先级。进程创建时赋予一个初始优先级，但该优先级会随着进程的推进或等待时间的增加而动态调整，以获得更好的调度效果。例如，规定优先级随等待时间的增加而提高，这样，即使初始优先级较低的进程，在等待足够长时间后也能获得CPU 调度。

在实际系统中，进程优先级的设置通常遵循以下原则：

1)系统进程>用户进程。系统进程负责管理核心资源和服务，通常被赋予更高的优先级。

2)交互型进程>非交互型进程（或前台进程>后台进程）。交互型进程需要快速响应用户输入，因此应优先调度，以保证良好的用户体验。

3. I/O 型进程>计算型进程。 I/O 型进程指频繁进行I/O 操作的进程，而计算型进程主要消耗 CPU 时间，很少使用I/O 设备。I/O 设备（如打印机）的处理速度远低于 CPU，因此若将I/O 型进程的优先级设置得更高，就能让它尽快获得 CPU 并启动 I/O 操作，使I/O 设备尽早开始工作，进而提高系统整体吞吐量。

优先级调度是一种基于进程优先级的调度算法，广泛应用于操作系统中。根据是否允许中断当前正在执行的进程，优先级调度可分为 非抢占式优先级调度 和 抢占式优先级调度 两种形式。

在 非抢占式优先级调度 中，调度器总是从就绪队列（等待队列）中选择优先级最高的进程执行。一旦某个进程开始执行，它将持续运行直到完成（或主动释放 CPU，例如进入等待 I/O 状态）。在此期间，即使有更高优先级的进程到达并加入就绪队列，当前进程也不会被中断，而是继续执行直到结束。

注意

在常见的操作系统和调度算法中，优先级的值越小，优先级越高。

例如对于 Unix 系统，使用 nice 值来表示优先级：

• nice 值越低，进程获得 CPU 时间的机会越多。

抢占式优先级调度 旨在确保系统中任何时刻运行的进程始终是优先级最高的。当一个更高优先级的进程到达时，调度器会立即暂停当前运行的低优先级进程（将其挂起并加入就绪队列），然后将 CPU 分配给新到达的高优先级进程。

下图给出了两种优先级调度方式的实例对比，其中绿色的进程表示执行态，黄色表示就绪态：

先确认数值方向，再确认是否抢占。非抢占版本只在当前任务让出时重新选择；抢占版本在更高优先级者就绪时可以中断当前任务。

项目2023年第29题给出P1(到达0、服务60、优先级1)、P2(20、42、10)、P3(30、13、100)：

0—20 P1 | 20—30 P2 | 30—43 P3 | 43—75 P2 | 75—115 P1

周转分别115、55、13，平均61ms。被抢占后恢复的是剩余量，P2在30时已用10，只剩32，不能再次运行完整42。

等待越久逐渐提高优先级的老化策略可缓解饥饿。优先级数值本身不具备通用的“越小越高”规则，题干已定义时直接服从题干。

时间片轮转 (RR)调度算法

时间片轮转 (RR)调度算法主要适用于分时系统，其最大特点是公平性。系统将所有就绪进程按FCFS 的原则组织成一个就绪队列。每隔固定的时间间隔（称为时间片，例如30 ms）,系统会产生一次时钟中断，激活调度程序，将 CPU 分配给就绪队列的队首进程，并允许其执行一个时间片。当该进程执行完一个时间片后，即使尚未运行完毕，也必须被剥夺CPU，并重新放入就绪队列的末尾，等待下一次调度；而下一个队首进程则获得 CPU 的使用权。

RR 算法的调度时机：①若当前进程在时间片结束前已运行完成，则调度程序会立即被激活，进行进程切换；②若时间片用尽，则由时钟中断处理程序触发调度程序，完成上下文切换。

在RR 算法中，时间片的大小对系统性能有显著影响。时间片过大，大到足以让每个进程在一个时间片内完成运行时，RR 算法将退化为FCFS 算法，无法满足短作业和交互式用户对快速响应的需求；时间片过小时，虽然部分短作业可能在一个时间片内完成，但会导致系统频繁进行进程调度和上下文切换，大幅增加系统开销，真正用于执行用户程序的CPU 时间反而减少。

因此，时间片的长度应合理设置，在响应速度与运行效率之间取得平衡。通常，其取值需综合考虑以下因素：系统的期望响应时间、就绪队列中的进程数量以及系统的处理能力。特别地，在交互式系统中，常以“典型交互”作为参考基准，例如，用户在文本编辑器中输入一个字符，或在终端中按下回车键，这类操作通常只需几十至上百毫秒即可完成。一个较为合理的时间片大小，应略长于一次典型交互所需的时间，这样既能确保大多数交互式进程在单个时间片内完成处理、获得流畅的响应体验，又能有效控制上下文切换频率，避免不必要的系统开销。

时间片轮转（Round Robin，RR）这是一种基于 时间片 的算法，每个进程被分配一个固定的时间片，当时间片用完时，进程被放回队列尾部，下一个进程开始执行。这样可以实现公平的 CPU 时间分配。

Process (Arrival Time, Burst Time)

上图中给出了每个进程的到达时间和要求服务时间，调度器按照轮询的方式依次遍历进程，每个进程只有执行时间片内的时间，之后便进入等待状态。

公共例子片额2，在片尾先把此时新到达的任务入队，再把尚未完成的当前任务放回尾部：

0—2 A | 2—4 B | 4—6 A | 6—7 C | 7—9 B
9—11 D | 11—13 A | 13—15 D | 15—16 A

2时B到达，与A片额用尽同刻；约定 B 先排入，所以接下来执行B。题目采用另一同刻顺序时，必须重新排队，不能一边用一种约定、一边抄另一种时间线。

A、B、C、D周转为16、7、3、10，等待9、3、2、6；平均周转9、平均等待5。首次响应等待为0、0、2、4，平均1.5。

时间片大到每段都能一次完成时，轮转近似FCFS。时间片极短时，响应机会更密，但开销增大。只剩一个任务时，它可以连续取得CPU，图上相邻同名段可合并，但统计调度开销时仍要遵循题设。

七种算法的同例对照

各项结果均基于同一组任务和相同的并列处理规则，不能据此断定各调度算法在所有负载下的优劣。

多级队列调度算法

前述的各种调度算法通常只设置一个就绪队列，采用固定且单一的调度策略，难以满足系统中不同类型进程对调度的不同需求。例如，交互型进程要求快速响应，而批处理进程更关注吞吐量和资源利用率。为兼顾这些差异，多级队列调度算法被提出。

该算法将系统中的就绪进程划分为多个独立的就绪队列，每个队列对应一类具有相似特性的进程（如系统进程、交互型进程、批处理进程等）。每个队列可独立采用适合其特性的调度算法：例如，交互型队列常使用RR 算法以保证响应性，而批处理队列可采用 FCFS 算法或SJF 算法以提高吞吐量。更重要的是，各队列本身具有不同的优先级。调度时，系统总是优先调度高优先级队列中的进程；只有当所有高优先级队列均为空时，才会调度低优先级队列中的进程。这种机制确保了关键任务（如系统服务或用户交互）能够及时获得CPU 资源。

多级反馈队列调度算法（融合了前几种算法的优点）

多级反馈队列调度算法是时间片轮转调度算法与优先级调度算法的综合与发展（见图2.10）。

通过动态调整进程所处的队列（优先级）和对应的时间片大小，该算法能够兼顾系统的多种目标：既有利于短进程，可提高吞吐量并缩短平均周转时间，又有利于I/O 型进程以提升设备利用率和响应速度，同时无须事先知道进程的运行时间。

多级反馈队列调度算法的实现机制如下。

1)设置多个就绪队列。为每个队列赋予不同的优先级，第1级队列优先级最高，第2级次之，其余队列优先级依次降低。该算法为各级队列分配不同的时间片，优先级越高的队列，时间片越小。例如，第i+1 级队列的时间片长度通常是第i 级的2倍。

2)每个队列内部采用时间片轮转(RR)调度。新进程创建后，首先被放入第1级队列的末尾。当轮到该进程执行时：若其在当前时间片内完成，则终止并退出系统；若时间片用完仍未完成，则被移至下一级（优先级更低）队列的末尾，等待后续调度。这一过程持续进行，直至进程在某一级队列中完成。通常，最低优先级队列（如第 n 级）的时间片较长，其行为接近FCFS，但仍采用时间片轮转以保证公平性。

3)按队列优先级调度。调度程序总是优先调度最高优先级队列中的进程执行。具体而言：仅当第1级队列为空时，才调度第2级队列中的进程；仅当第1～i-1 级队列均为空时，才会调度第i 级队列中的进程。此外，由于新进程总是首先进入第1级队列，因此若当前正在执行的是低优先级队列中的进程，而有新进程进入系统，则系统将立即抢占当前进程，将其放回原队列末尾，同时将 CPU 分配给新的高优先级进程。

多级反馈队列调度算法的优势主要体现在以下场景中：

1)交互型（终端型）用户：进程通常较短且频繁进行I/O，能在高优先级队列中快速完成。

2)短批处理作业用户：因优先级高、时间片小，可迅速执行完毕，周转时间较短。

3)长批处理作业用户：虽最终降至低优先级队列，但已在高优先级队列中获得部分CPU 时间，不会因长期得不到调度而产生饥饿现象，最终仍能完成。

多级反馈队列（Multilevel Feedback Queue）这是一种混合算法，将进程分为 多个队列，每个队列有不同的优先级和时间片大小。

高优先级队列优先调度，时间片较短，适合交互型进程；低优先级队列时间片较长，适合计算密集型任务。新进程通常进入最高优先级队列，若在时间片内未完成，则移到下一级队列；若因 I/O 等待阻塞，完成后可能返回较高优先级队列。

多级反馈队列根据进程行为调整其优先级。例如，占用 CPU 过多的进程会被降级，而频繁等待 I/O 的进程可能被提升。这种设计兼顾了快速响应、公平性和资源利用率。

多级反馈队列综合优先级和时间片；具体时序由给定的队列降级与抢占规则决定。

多级队列把不同类型任务分开，每队可采用不同算法；多级反馈还允许任务根据行为改变所属队列。新任务通常先进入高队列，用完整片额仍未完成则下移，低队列有较长片额。

题目可能规定最低队列RR、FCFS或SJF，不能只凭“反馈”一词决定。项目2019年第27题明确Q1的RR片额10ms，Q2采用短进程优先。两任务同在开始前进入Q1，分别需30、20ms：

0—10 P1(Q1) | 10—20 P2(Q1) | 20—30 P2(Q2) | 30—50 P1(Q2)

等待时间分别20、10，平均15ms。进入低队列时比较剩余CPU时间，而不是最初服务总量。

被高队列抢占以后

低队列任务被新高队列任务抢占时，需要记录它的层级、剩余服务、剩余片额，以及返回队首还是队尾。这些是算法参数，不可混用。

配套 feedback() 明确采用“原级队尾、保留未用片额、耗尽才降级、最低级仍RR”。例如A(0,9)、B(1,2)、C(4,1)，各级片额2、4、8：A先用2，B用2，C用1；A随后先在第二级用4，再在第三级用3。时间线中A的5—12可以连在一起，但层级记录仍保存两个阶段。

严格高队列优先且没有提升机制时，源源不断的高优先级任务可能让低层任务等不到CPU。周期性提升、老化等是额外防饥饿规则，不能仅凭“低层以前运行过”保证以后一定完成。

基于公平原则的调度算法

前面介绍的调度算法主要关注响应时间、吞吐量或周转时间等性能指标，但通常未将调度公平性作为主要设计目标。以下介绍两种以调度公平性为核心目标的算法。

保证调度算法

保证调度算法并不以“优先运行”为目标，而是为每个进程提供可量化的CPU 时间分配保证。例如，在包含n 个并发进程的系统中，每个进程应获得约1/n 的 CPU 时间。调度器通过动态跟踪各进程的实际 CPU 使用情况，并据此调整调度顺序，以逐步逼近这一公平目标。

为实现这一目标，系统需具备以下功能：

1)跟踪每个进程自创建以来已获得的CPU 时间。

2)计算每个进程应获得的CPU 时间，即自进程创建以来的时间除以n。

3)计算每个进程的公平比率，即实际获得的 CPU 时间与应获得的CPU 时间之比。若比率小于1，则表示未达应得份额；若比率大于1，则表示超额占用。

4)调度程序应选择当前比率最小的进程，将CPU 分配给它，并让它一直运行，直到它的比率超过最接近它的进程的比率为止。

公平分享调度算法

保证调度算法对进程公平，但未必对用户公平。假设各用户拥有的进程数不同，如用户1启动4个进程，而用户2仅启动1个进程，采用RR 调度，那么对每个进程而言很公平，但用户1 将获得80%的CPU 时间，而用户2仅获得20%的CPU 时间，显然对用户2有失公平。

公平分享调度算法则保证每个用户获得相同的 CPU 时间，或按所要求的比例分配。在这种方式下，不论用户启动多少进程，都能确保其获得应得的CPU 份额。例如，系统中有两个用户，用户1拥有4个进程A、B、C 和 D，用户2仅拥有1个进程E，若采用RR 调度，为保证两个用户获得相同的CPU 时间，可采用如下调度序列：

AEBECEDEAEBECEDE …若用户1应获得的CPU 时间是用户2的两倍，则可采用如下调度序列：

ABECDEABECDE …这类调度策略通过按用户权重分配调度机会，从而在用户层面实现公平性。

公平对象也要说明

若用户甲有4个等权进程、乙有1个，按进程等片轮转可给甲约4/5的CPU份额。若目标是两用户各1/2，则应先按用户分配，再在用户内部安排进程。公平是对谁公平，需要写清楚。

先列时间线再算指标

A在0到达需4单位CPU，B在1到达需1单位，忽略切换开销。非抢占FCFS顺序为A:0..4、B:4..5；抢占最短剩余时间为A:0..1、B:1..2、A:2..5。SJF非抢占版不能在1时刻打断A。

HRRN的响应比=(等待时间+服务时间)/服务时间，等待会提高优先程度。时间片轮转还须规定同一时刻新到进程和用完时间片进程的入队次序，否则某些边界时间线可能不唯一。

做题时的工作表

至少保留“当前时间、就绪队列、各任务剩余量、当前事件、选择结果”五栏。最后从完成时刻逐个计算指标，并检查CPU服务总量与时间线上的有效片段总量一致。

计算时只需依据题目给出的到达时间、服务时间和调度规则逐步绘制时间线；模型化计算不等同于调用真实系统的调度器。

随堂练习

公共例子使用SRTF，5时C刚完成，为什么先执行B而不是最早到达的A？A最终等待多少？

参考解答

此时B剩2、D剩4、A剩5，SRTF选择B。A完成于16、到达0、服务7，所以等待16−0−7=9。

对应训练

相关练习RR退化为FCFS的条件

相关练习多级反馈队列

相关练习二级反馈队列

相关练习抢占优先级的时间线