专题进阶 · 操作系统算法推荐总顺序 · 第 141 / 148 课

按到达顺序画出甘特图,分别计算响应时间、等待时间和周转时间。

先学会这些,再进入本课 队列
还有 1 节先修课未标记掌握;已具备基础时可以直接学习,遇到障碍再沿链接补课。
专题详解 · 操作系统算法

先来先服务FCFS

按到达顺序非抢占执行,容易产生长任务阻塞短任务的护航效应。

建议 40 分钟 · 含手算、代码与三层练习

本课要建立的能力

按到达顺序画出甘特图,分别计算响应时间、等待时间和周转时间。

先手算,再对照代码;理解为什么成立,最后用改变条件的练习检查迁移能力。

01先把问题说具体

三个任务先后进入单核 CPU,若谁先到谁先执行,会得到怎样的等待体验?

02一步步得到方法

先明确调度模型

本课假定单 CPU、每个任务只有一个 CPU burst、不发生 IO、上下文切换成本为 0。FCFS 采用非抢占策略:一旦开始运行,就一直执行到本次任务结束,后到任务只能排队。

任务按到达时间进入 FIFO 队列,到达时间相同则保持输入顺序。若 CPU 空闲,要把当前时间推进到下一个任务到达,而不是让尚未到达的任务提前执行。

三种时间指标不要混用

响应时间=首次运行时刻−到达时刻;周转时间=完成时刻−到达时刻;等待时间=周转时间−CPU 运行时长。在本课无 IO、单次非抢占模型中,响应时间恰等于等待时间。

对抢占或多次 IO 的系统,这两者通常不同。解释一个调度结果时,要先写清任务模型,再比较同一组指标。

队头长任务造成车队效应

短任务若排在长任务后面,会长时间等待。FCFS 实现简单、顺序可预期,但不根据任务长度改善平均等待。后续 SJF 会尝试先处理短任务,Round Robin 则用时间片改善首次响应。

不同策略服务不同目标;吞吐、平均等待、交互响应和公平性不能只用一个数字概括。真实系统还面对多核、优先级和 IO 行为。

03把一个小例子完全算清楚

任务 A=(到达0,时长5),B=(1,1),C=(2,2)。

步骤计算与状态为什么这样做
执行 A0→5,等待0B、C 到达后排队
执行 B5→6,等待45−1=4
执行 C6→8,等待46−2=4

窄屏可左右滑动表格,阅读完整计算与理由。

平均等待为 (0+4+4)/3=8/3;周转分别为 5、5、6。

04为什么这个方法成立

  1. 队列按到达时间稳定排序,执行时不会跳过更早到达的任务,符合 FCFS 定义。
  2. start=max(当前时间,到达时间) 保证无重叠运行且不会提前执行。
  3. finish=start+duration,代入指标定义即可逐项核对结果。

05把推导翻译成代码

Python · 可独立运行的教学实现

def fcfs(jobs):
    if any(arrival<0 or duration<=0 for name,arrival,duration in jobs):
        raise ValueError("invalid job")
    time = 0
    result = []
    for name,arrival,duration in sorted(jobs,key=lambda job:job[1]):
        start = max(time,arrival)
        time = start+duration
        result.append({"name":name,"start":start,"finish":time,
                       "waiting":start-arrival,"turnaround":time-arrival})
    return result

print(fcfs([("A",0,5),("B",1,1),("C",2,2)]))

逐个理解关键决定

sorted(jobs,key=lambda job:job[1])
Python 稳定排序保留同时到达任务的输入顺序。
max(time,arrival)
正确处理没有任务可运行的空闲区间。
turnaround
包含等待和运行时长,不等于单纯 CPU 时间。

06时间、空间与实现范围

离线输入排序 O(n log n),扫描调度 O(n),结果空间 O(n)。

若任务已经按到达顺序在线入队,FIFO 操作可做到每次 O(1)。

07改变条件,检查哪里会出错

直接把 start 设为当前 time

若任务尚未到达,会产生不可能的提前运行。

长任务先执行也一定公平

它遵守到达次序,但短交互任务可能经历很差的响应时间。

08从手算到独立迁移

先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。

练习 1 · 复现与理解

若第一个任务到达 5,CPU 从几时开始它?

需要一点提示

此前无就绪任务。

查看解析与答案

时刻 5,0 到 5 是空闲时间。

练习 2 · 边界与辨析

B 的周转为何是 5 而不是 1?

需要一点提示

完成时刻 6,到达时刻 1。

查看解析与答案

周转包含等待4和运行1,总计5。

练习 3 · 变式与迁移

把 A 改成时长100,B、C 的等待怎样变化?

需要一点提示

后续任务被队头阻塞。

查看解析与答案

B 等待99,C 等待99,体现车队效应。

继续深入这个专题

本站例子、推导与教学代码独立编写。以下是相关教材、作者论文或官方文档,可继续核对定义、证明与更完整的工程实现。

Arpaci-Dusseau · Operating Systems: Three Easy Pieces

理解之后,继续递进

能解释手算中的每一步,并独立完成迁移题后,再标记掌握。