CSCI3150 L08 Scheduling: The Multi-Level Feedback Queue

课程：CSCI3150 Introduction to Operating Systems · 2022未核本讲：L08 Scheduling: The Multi-Level Feedback Queue，第 2 部分 / 共 4 部分 · 原件 L08-CPU调度-2022未核.pptx（本地课件） · PDF页码副本（本地课件） p.19–33 定位：把MLFQ从初版规则推到防饥饿、抗钻空子的最终版本，并学会跟踪每级累计CPU配额。前后：上一份 Part I · 下一份 Part III

p.19 Part II分节页。

在不知道作业长度时推测它的需求

目标、队列与优先级（p.20–22）【新】

p.20 A Scheduler that learns from the past to predict the future.

Objective:

Optimize turnaround time  Run shorter jobs first

Minimize response time without a priori knowledge of job length.

p.21 MLFQ has a number of distinct queues.

Each queues is assigned a different priority level.

A job that is ready to run is on a single queue.

A job on a higher queue is chosen to run.

Use round-robin scheduling among jobs in the same queue

p.21 Rule 1: If Priority(A) > Priority(B), A runs (B doesn’t).

Rule 2: If Priority(A) = Priority(B), A & B run in RR.

p.22 MLFQ varies the priority of a job based on its observed behavior.

Example:

A job repeatedly relinquishes the CPU while waiting IOs  Keep its priority high

A job uses the CPU intensively for long periods of time  Reduce its priority.

p.20希望兼顾短任务的周转与交互任务的响应，但不预先知道运行长度。p.21设置多个优先级队列：只选最高非空就绪队列，同级内部RR。p.22再用过去行为调整优先级：长时间消耗CPU者向下，常很快让出CPU等待I/O者暂留高位。

这里的“反馈”是行为改变队列位置，不是把队列名当任务永久身份。补充：优先级高仍须处于ready才参与选择；阻塞中的高优先级任务不会占着CPU不让低级就绪者跑。

八级图与第一版降级规则（p.23–24）

p.24 MLFQ priority adjustment algorithm:

Rule 3: When a job enters the system, it is placed at the highest priority

Rule 4a: If a job uses up an entire time slice while running, its priority is reduced (i.e., it moves down on queue).

Rule 4b: If a job gives up the CPU before the time slice is up, it stays at the same priority level

图（p.23）：八级MLFQ 元素：Q8内A、B，Q4内C，Q1内D，其余为空，Q8最高。看什么：A/B在Q8轮转时C/D暂不运行；只有更高的就绪队列都空，才轮到低级。

p.24初版规则是新任务进入最高级；一次用完整片就降一级；提前主动让出则保留级别。它试图用“是否迅速让出”推测交互性。补充算例（数字是我为演示取的，讲义没给）：片长10ms，任务连续用满10后降级；若运行2ms便阻塞则本版保留级别。注意这是初版，p.30会替换其计费规则，不能把两版混成一套。

长任务、短任务与I/O任务（p.25–27）

p.26 Assumption:

Job A: A long-running CPU-intensive job

Job B: A short-running interactive job (20ms runtime)

A has been running for some time, and then B arrives at time T=100.

p.27 Assumption:

Job A: A long-running CPU-intensive job

Job B: An interactive job that need the CPU only for 1ms before performing an I/O

p.27 A Mixed I/O-intensive and CPU-intensive Workload (msec)

p.27 The MLFQ approach keeps an interactive job at the highest priority

题面（同原件 · Example 1 · p.25）

p.25 A three-queue scheduler with time slice 10ms

p.25图中一个长任务先在Q2跑0–10，再在Q1跑10–20，随后落到Q0。它被降级不是因出错，而是系统观察到它已消耗完整时间片，优先留高队列给短任务。

题面（同原件 · Example 2 · p.26）

p.26 Job A: A long-running CPU-intensive job

p.26 Job B: A short-running interactive job (20ms runtime)

p.26 A has been running for some time, and then B arrives at time T=100.

p.26 B在100进入Q2，跑10ms降Q1，再跑10ms完成，结束120；B响应0、周转20。A在低级暂让路，120后继续。图体现本讲的严格高优先级选择，不能自动换成Tutorial特定的片内不抢占规则。

p.27的B每次只用CPU1ms便I/O，所以初版规则让它维持高优先级；A填补B等待区间。图没有给每次I/O的精确时长，因此不能捏造唯一完成时刻。若I/O时长为d且重复k次，忽略抢占开销，前k轮的一个周期为1+d，B的CPU需求为k毫秒；实际最后一次是否还需I/O要按任务终止定义决定。

初版的三种失败与周期提升（p.28–29）

p.28 Starvation

If there are “too many” interactive jobs in the system.

Long-running jobs will never receive any CPU time.

Game the scheduler

After running 99% of a time slice, issue an I/O operation.

The job gains a higher percentage of CPU time.

A program may change its behavior over time.

CPU bound process  I/O bound process

p.29 Rule 5: After some time period S, move all the jobs in the system to the topmost queue.

Example:

A long-running job(A) with two short-running interactive job(B, C)

p.28列出饥饿、钻计费空子、程序行为变化。若高队列一直有任务，低队列可能长期得不到CPU；若每次快到片尾才让出，任务可以消耗很多CPU却不降级；原来CPU密集的程序后来转交互，也可能被旧低优先级困住。

p.29每隔S把任务提升到最高队列，让历史判断定期重新开始。图左A长期留Q0而B/C占高位；图右周期提升让A再次得到高优先级机会。补充：这提供重新竞争的机会，具体最长等待上界还需要就绪任务数、时间片等参数，不能只从S推出每个任务恰好多久运行一次。

累计计费才是最终规则（p.30）

p.30 How to prevent gaming of our scheduler?

Solution:

Rule 4 (Rewrite Rules 4a and 4b): Once a job uses up its time allotment at a given level (regardless of how many times it has given up the CPU), its priority is reduced(i.e., it moves down on queue).

p.30 Without(Left) and With(Right) Gaming Tolerance

新规则记累计CPU用量，不因I/O或主动让出而把已用预算清零。算一遍（补充；数字是我为演示取的，讲义没给）：本级配额10ms，先用9ms后阻塞，回来只剩1ms，再用1ms就耗尽并降级。旧规则会把两次都视作“没用满一整片”而放过；新规则累计9+1=10，堵住漏洞。这里区分quantum（一次最多运行多久）与allotment（本级累计可用多久），实现可以让配额包含多片。

补充：预算像余额，不像每次重新领的票。 用 p.30 的累计规则做一段完整状态追踪：最高级配额10ms，某任务先运行4ms，再I/O，回来运行3ms，再I/O，最后运行3ms。这些数字是演示取的；每次 I/O 多久不参与 CPU 配额扣费。

事件	本级累计CPU用量	剩余额度	下一步含义
初次入队	0	10	可竞争最高级CPU
运行4后阻塞	4	6	不在ready队列，别的任务可运行
I/O完成	4	6	回ready，不自动清零预算
再运行3后阻塞	7	3	仍未耗尽
最后再运行3	10	0	按最终规则降级

墙钟可能走了很久，但这里合计服务恰为10；把阻塞时长也扣掉会错误惩罚等待设备的任务。相反，每次返回都恢复到10会重现 p.28 的钻空子问题。周期提升是另一个事件，是否重置本级计数应按所用版本明示，不能偷偷借用 Tutorial 的约定补全讲义缺项。

自测：高优先级任务阻塞时，低优先级任务运行是否违反“最高优先级优先”？

不违反。选择集合是就绪任务；阻塞者此刻不能执行。它 I/O 完成后变为就绪，才重新参加比较。若题设允许高优先级到达时立刻抢占，低级任务会被打断；若题目另给片内不抢占，则到边界再处理。两个题目可用不同规则，不能只靠“MLFQ”三个字补猜。

参数调节与完整规则（p.31–33）

p.31 The high-priority queues  Short time slices

E.g., 10 or fewer milliseconds

The Low-priority queue  Longer time slices

E.g., 100 milliseconds

p.31 Example) 10ms for the highest queue, 20ms for the middle,

40ms for the lowest

p.32 For the Time-Sharing scheduling class (TS)

60 Queues

Slowly increasing time-slice length

The highest priority: 20msec

The lowest priority: A few hundred milliseconds

Priorities boosted around every 1 second or so.

p.33 The refined set of MLFQ rules:

Rule 1: If Priority(A) > Priority(B), A runs (B doesn’t).

Rule 2: If Priority(A) = Priority(B), A & B run in RR.

Rule 3: When a job enters the system, it is placed at the highest priority.

Rule 4: Once a job uses up its time allotment at a given level (regardless of how many times it has given up the CPU), its priority is reduced(i.e., it moves down on queue).

Rule 5: After some time period S, move all the jobs in the system to the topmost queue.

p.31给高/中/低10、20、40ms时间片。一个持续CPU任务若每级配额恰为一片，先运行10，再20，30ms后到最低级；低级长片减少切换，高级短片改善响应。p.32用Solaris历史实现说明参数是设计选择：60级、最高约20ms、低级数百毫秒、约1秒提升。这是课件实例，不是所有MLFQ或当前系统的固定配置。

p.33的最终算法依次为：最高非空级优先；同级RR；新任务最高级；本级累计配额用尽则降级；周期S统一提升。执行手算时，每个任务至少记录到达时刻、剩余服务、级别、本级已用配额及就绪/阻塞状态。一次事件后先更新状态，再选择队列，不能只画最终甘特图却不记配额。

考试角度：（C 级通识）常见考法是给出到达、I/O、配额和S，逐事件更新队列；最易混淆的是I/O是否重置配额，以及题目是否另设片内不抢占约定。

补充：在同一个时刻有多件事发生，先处理状态，才有可选队列。 例如一次运行恰好同时碰到片尾和任务完成，已经完成的任务不能再被放到降级队列；若任务先阻塞，选择时应把它排除在就绪集合之外；若周期提升与新任务到达重合，则两者都可能影响最高队列的内容，而同级先后还需要题目给出规则。没有写明的平局规则不能靠“答案看起来好看”倒推。

手算一行至少保留五个量：本段起止时刻、运行者、剩余服务、本级累计已用量、结束原因。下一行的队头必须能从结束原因推出来。只有画运行者色块，往往会在配额未满却片到期、配额用尽却任务也完成这两种情况中混淆。后面的 T07 给出自己的事件约定，应先抄清约定，再代入本讲的状态量。

本讲核心考点

最高非空就绪队列优先，同级RR（p.21，C 级通识考法）。
新任务从最高级开始，行为反馈改变级别（p.22–27，C 级通识考法）。
周期提升缓解饥饿及旧行为判断（p.28–29，C 级通识考法）。
最终版本按本级累计CPU配额降级（p.30、33，C 级通识考法）。

附录

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

来源与证据

原件：L08-CPU调度-2022未核.pptx（本地课件）；PDF副本（本地课件） p.19–33。本文页码均为 PDF 页号。
考试证据：读了课程大纲-2026T1.pdf、教学计划-2026T1.pdf、T08-期中参考-2025T2-题目-解答.pdf、T07-多级反馈队列-2025T2.pdf（p.13–15内嵌历史试题）；未识别用途的 PDF：无
2026-10-13 内容补全：保留原页顺序与版本，补入对应页的程序、接口、字段、条件和演算；原程序片段保留课件行号、拼写与省略处，不能据此视为经过编译的完整软件。本文已有运行记录属于其标注日期，本次未重新运行课程容器或提交作业。