CSCI3150 L08 Scheduling: Introduction

课程：CSCI3150 Introduction to Operating Systems · 2022未核 本讲：L08 Scheduling: Introduction，第 1 部分 / 共 4 部分 · 原件 L08-CPU调度-2022未核.pptx（本地课件） · PDF页码副本（本地课件） p.1–18 定位：能从到达、首次运行与完成时刻计算调度指标，并解释FIFO、SJF、STCF、RR及I/O重叠的取舍。 前后：下一份 Part II 承接：#L06-03 中断与阻塞

整讲按原件分节页分成四份：

• Part I 调度入门：p.1–18。
• Part II 多级反馈队列：p.19–33。
• Part III 比例份额：p.34–44。
• Part IV 多处理器调度：p.45–64。

p.1标题页；p.2课程位置图将本讲放在CPU虚拟化；p.3 Part I分节页。

先固定假设，再比较调度结果

工作负载与周转时间（p.4–5）【新】

p.4 Workload assumptions:

Each job runs for the same amount of time.

All jobs arrive at the same time.

All jobs only use the CPU (i.e., they perform no I/O).

The run-time of each job is known.

p.5 Performance metric: Turnaround time

The time at which the job completes minus the time at which the job arrived in the system.

Another metric is fairness.

Performance and fairness are often at odds in scheduling.

p.4先假设作业等长、同时到达、只用CPU、运行时间已知，随后逐项放松。算法好坏依赖这些前提，不能把一组例子的最优顺序推广到不知道未来长度的真实负载。

p.5的周转时间是完成时刻减到达时刻，即从进入系统到全部完成的总等待长度。设到达a、完成c，则$T=c-a$。补充算例（数字是我为演示取的，讲义没给）：到达3、完成11，周转8；其中CPU实际执行可能只有2，另外6是等待，因此周转不是纯CPU服务时间。公平性是另一评价目标，平均完成快不代表每个任务都获得公平待遇。

FIFO与护航效应（p.6–7）

p.6 First Come, First Served (FCFS)

Very simple and easy to implement

Example:

A arrived just before B which arrived just before C.

Each job runs for 10 seconds.

p.7 Let’s relax assumption 1: Each job no longer runs for the same amount of time.

Example:

A arrived just before B which arrived just before C.

A runs for 100 seconds, B and C run for 10 each.

题面（L08-CPU调度-2022未核.pdf · FIFO两例 · p.6–7）

p.6 A arrived just before B which arrived just before C.

p.6 Each job runs for 10 seconds.

p.7 A runs for 100 seconds, B and C run for 10 each.

FIFO/FCFS按到达顺序运行，不因后来出现短任务而打断当前任务。p.6按讲义近似同时到达的模型，A在0–10、B在10–20、C在20–30，完成时刻10/20/30，平均周转(10+20+30)/3=20秒。

p.7只把A加长到100：A在0–100、B在100–110、C在110–120，平均周转110秒。B/C明明各只需10秒却在长A后面等待，这叫护航效应。三个任务总CPU工作量120秒不变，但如何排序影响每个任务等待多久。

SJF为何在晚到达时仍被长任务挡住（p.8–9）

p.8 Run the shortest job first, then the next shortest, and so on

Non-preemptive scheduler

Example:

A arrived just before B which arrived just before C.

A runs for 100 seconds, B and C run for 10 each.

p.9 Let’s relax assumption 2: Jobs can arrive at any time.

Example:

A arrives at t=0 and needs to run for 100 seconds.

B and C arrive at t=10 and each need to run for 10 seconds

p.8的SJF是非抢占算法。沿用p.7数据、同时可运行时选择B→C→A，完成10、20、120，平均(10+20+120)/3=50秒。短任务放前面后，长任务多等20秒，两个短任务各少等100秒，平均因而下降。

题面（同原件 · SJF晚到达 · p.9）

p.9 A arrives at t=0 and needs to run for 100 seconds.

p.9 B and C arrive at t=10 and each need to run for 10 seconds

t=0只有A，所以A一旦开始便运行到100；B/C在10到达，分别于110/120结束。周转不是100/110/120，而是100、110−10=100、120−10=110，平均310/3≈103.33秒。错误常发生在忘减新到达时间。

STCF按剩余时间重新选择（p.10–11）

p.10 Add preemption to SJF

Also knows as Preemptive Shortest Job First (PSJF)

A new job enters the system:

Determine of the remaining jobs and new job

Schedule the job which has the least time left

p.11 Example:

A arrives at t=0 and needs to run for 100 seconds.

B and C arrive at t=10 and each need to run for 10 seconds

p.10加入抢占：新任务到达后，把它的运行需求与现有任务的剩余量比较。p.11使用p.9的完整题面数据，A先跑0–10，此时剩90；B/C各10，所以抢占A。B跑10–20、C跑20–30，A跑30–120。周转A=120，B=10，C=20，平均150/3=50秒。

图（p.9、11）：非抢占与抢占的区别 元素：p.9 A连跑到100；p.11 A在10被切开，B/C插入后A再继续。 看什么：比较的是“剩下多久”，不是A原始的100；总完成时刻仍120，但短任务提早完成。

补充：先用交换相邻任务理解 SJF，再记名字。 假设两个任务同时到达，服务长度分别为 x 和 y，且 x 大于 y。忽略切换开销，先长后短的两个完成时刻为 x、x+y，总和 2x+y；先短后长则为 y、y+x，总和 2y+x。前者比后者多 x−y，所以交换后平均周转下降。这解释同时到达、运行时长已知、单 CPU 的模型中为什么应让短任务在前；它没有证明未知运行时长、带 I/O 或任意目标下 SJF 都最好。

沿 p.9 的晚到达例子，t=10 时应在账本写 A 已服务10、剩余90，B/C刚到达各需10。SJF 不重选是因为它“不抢占”的定义；STCF 重选则比较剩余量。算法名只决定选择规则，不能取代时间账本。画出的 CPU 总服务应仍为100+10+10=120，不可因为抢占多画出或少画掉 A 的10。

周转快不等于第一次响应快

响应时间与RR（p.12–13）【新】

p.12 The time from when the job arrives to the first time it is scheduled.

STCF and related disciplines are not particularly good for response time.

p.13 Time slicing Scheduling

Run a job for a time slice and then switch to the next job in the run queue until the jobs are finished.

Time slice is sometimes called a scheduling quantum.

It repeatedly does so until the jobs are finished.

The length of a time slice must be a multiple of the timer-interrupt period.

p.13 RR is fair, but performs poorly on metrics

such as turnaround time

响应时间只量到第一次运行。令首次运行f，则$R=f-a$；之后多次等待不会再次增加这个“首次”指标。p.13的RR按时间片轮转，运行一片后未结束者回到就绪队列，让其他任务有机会先获得一次CPU。时间片长度受定时中断粒度约束。

补充：任务一旦阻塞就暂时不在可运行队列中；RR不是强迫每个任务都占满一片。短片改善首次响应，同时增加切换频率，不能只看一个指标下结论。

补充：为什么时间片越小也不是越好。 响应时间只看第一次开始执行，不能用“很快运行了一小下”推出“很快完成”。如果每片后切换都消耗固定时间，缩短片长会让切换次数增加，真正用于作业的比例下降。

算一遍（数字是我为演示取的，讲义没给）：假定持续有任务可运行，每次切换耗时 1ms，每片有效服务 9ms，则每个服务加切换周期占 10ms，有效服务占 9/10=90%；改成 1ms 服务加 1ms 切换，占比变为 1/2=50%。这里算的是稳态的 CPU 时间分配，并未把第一片前或最后一片后的开销硬塞进原题。原课件忽略切换成本的甘特图仍按原模型计算；这个补充说明为什么把原模型的片长无限缩小，会超出它可用的假设。

三个5秒作业的完整比较（p.14–15）

p.14 RR with a time-slice of 1sec (Good for Response Time)

p.15 The shorter time slice

Better response time

The cost of context switching will dominate overall performance.

The longer time slice

Amortize the cost of switching

Worse response time

p.15 Deciding on the length of the time slice presents

a trade-off to a system designer

题面（同原件 · RR Scheduling Example · p.14）

p.14 A, B and C arrive at the same time.

p.14 They each wish to run for 5 seconds.

图（p.14）：SJF与1秒RR 元素：上图A/B/C各连续5秒；下图按ABC重复5轮，每格1秒。 看什么：第一次获得CPU的时刻与最终完成时刻是两组不同的数。

算一遍：SJF先后运行A0–5、B5–10、C10–15，响应0/5/10，平均5；周转5/10/15，平均10。RR首次时刻0/1/2，平均响应1；第5轮A于13完成，B于14完成，C于15完成，平均周转14。响应改善而平均周转变差，正是两目标的冲突。

p.15把切换成本加入考虑。补充算例（数字是我为演示取的，讲义没给）：若每片q=1毫秒，切换s=0.1毫秒，反复切换时开销占s/(q+s)=0.1/1.1≈9.09%；q=10时为0.1/10.1≈0.99%。这只是稳态简化比例，不包括初次启动等边界。

I/O期间让另一个任务运行

阻塞与重叠（p.16–18）【延伸 L06 p.9–11】

p.16 Let’s relax assumption 3: All programs perform I/O

Example:

A and B need 50ms of CPU time each.

A runs for 10ms and then issues an I/O request

I/Os each take 10ms

B simply uses the CPU for 50ms and performs no I/O

The scheduler runs A first, then B after

p.18 When a job initiates an I/O request.

The job is blocked waiting for I/O completion.

The scheduler should schedule another job on the CPU.

When the I/O completes

An interrupt is raised.

The OS moves the process from blocked back to the ready state.

题面（同原件 · Incorporating I/O · p.16）

p.16 A and B need 50ms of CPU time each.

p.16 A runs for 10ms and then issues an I/O request

p.16 I/Os each take 10ms

p.16 B simply uses the CPU for 50ms and performs no I/O

p.16 The scheduler runs A first, then B after

p.17上图让A跑五段10ms，中间四次I/O各10ms，A在90结束，B再跑50，整体140ms。有效CPU工作共100ms，利用率100/140≈71.43%。下图把B的五段10ms放进A的四段等待以及A结束后的最后10ms，整体100ms，图中CPU无空闲。

图（p.17）：两条时间线的重叠 元素：A的CPU段与下方I/O段交替；下图把B插入等待区间，上图留下CPU空洞。 看什么：总工作100ms没有减少，减少的是未利用的等待空隙。

p.18明确请求I/O后任务变blocked；I/O完成的中断使它回到ready，而不是保证立刻running。调度器仍要在所有就绪者之间选择。这里承接#L06-03的中断模型。

把 p.17 下图拆成 CPU 与设备的并行账本。 以下每格 10ms，沿用原图五段 A、五段 B、四段 I/O，不增加最后一次 I/O。

这张图不能读成 A 的 I/O 也消耗了 CPU 上的一格：10–20ms 中设备为 A 工作，同时 CPU 为 B 工作。横向总时长只走过 10ms，两种资源却各做了 10ms 的事。A 的完成时刻仍是 90ms；改善的是 B 从等 A 全做完才开始，变为利用四个空档，整个工作负载从 140ms 缩短到 100ms。

本讲核心考点

• 周转=完成−到达，响应=首次运行−到达（p.5、12，C 级通识考法）。
• SJF非抢占，STCF按剩余时间抢占（p.8–11，C 级通识考法）。
• RR短片改善响应但有切换成本（p.13–15，C 级通识考法）。
• I/O完成使blocked转ready（p.16–18，C 级通识考法）。

附录

本份没有需要移至附录的长推导；计算过程已在对应页正文写全。

来源与证据

• 原件：L08-CPU调度-2022未核.pptx（本地课件）；PDF副本（本地课件） p.1–18。本文页码均为 PDF 页号。

• 考试证据：读了 课程大纲-2026T1.pdf、教学计划-2026T1.pdf、T08-期中参考-2025T2-题目-解答.pdf、T07-多级反馈队列-2025T2.pdf（p.13–15内嵌历史试题）；未识别用途的 PDF：无

• 2026-10-13 内容补全：保留原页顺序与版本，补入对应页的程序、接口、字段、条件和演算；原程序片段保留课件行号、拼写与省略处，不能据此视为经过编译的完整软件。本文已有运行记录属于其标注日期，本次未重新运行课程容器或提交作业。