CSCI3150 T07 MLFQ逐步演算
课程：CSCI3150 Introduction to Operating Systems · 2025T2 本讲：T07 MLFQ逐步演算 · 原件 T07-多级反馈队列-2025T2.pptx（本地课件） · PDF页码副本（本地课件） p.1–45 定位：按本题非抢占时间片规则，逐项维护剩余工作量、队列预算与周期提升。 前后：对应 L08 MLFQ；后接 T08期中题。
逐页伴读
p.1–3：这份练习来自历史Spring2026
p.1 Multilevel Feedback Queue
CSCI3150 Introduction to Operating Systems, Spring 2026
p.2 Assignment 2
Due at 23:59:59 p.m., Sunday, March 1stask as soon as possible.
Please accept the task ASAP.
Invitation URL: https://classroom.github.com/a/RKvPmvxf
Submission: Github classroom (refer to the Assignment 1 guide: https://piazza.com/class/mjxsr09gf91dw/post/11)
p.3 Assignment 2
For students who have already accepted asg2, please run git pull to update
封面2月26日，作业2截止3月1日。更新提示仅说明该历史作业材料曾调整，本次不执行git pull或提交操作。
p.4–6：自动反馈也有延迟
p.4 Assignment 2
If you can't access asg2 via this URL, please try the solution also mentioned in asg1:
p.5 Assignment 2as possible.
Autograding: https://piazza.com/class/mjxsr09gf91dw/post/57\#
p.5 New update: Considering GitHub's permission security issues, we have made some adjustments to how you can view the autograding feedback:
You can continue to check the basic test results (e.g., whether the compilation passes, whether files are missing, etc.) in the Actions tab of your personal repo after pushing asg2.
Detailed results will be pushed to the Issues tab of your personal repo with a delay. However, due to the instability of GitHub's schedule triggers for automated testing (which may be dropped or delayed), it may take 10 minutes or even longer to actually receive the feedback. It is recommended to test as early as possible.
p.6 Assignment 2as possible.
课件把基础检查放Actions，详细结果延迟到Issues，说明没有即时报告不等于程序没有运行。截图是当时工作流记录，不能作为当期作业平台承诺。
p.7–9：本题最关键的额外假设
p.9 All examples used in this tutorial:
https://github.com/henryhxu/CSCI3150/tree/2026-Spring/tutorial/T07
p.7 FAQ说明空闲区间不用填表、周期到来要排序，极长任务耗尽所有级预算不计该次作业；同一时刻周期排序与新到达先后允许两种。p.8补充新任务入最高队尾，同刻片到期的旧任务先于新任务入队。
p.8 图中文字 For simplicity in this assignment, a running process will NOT be preempted by a newly arrived higher-priority process until it finishes its current time slice or allotment.
因此本题高优先级新到达不会立即打断正在运行的时间片；周期提升仍按后面的演示在300发生。不能直接套L08一般抢占式MLFQ来填同一张表。p.9说明本次目标是填调度表。
p.7–8 的 FAQ 条件补齐。 原页还有两个不可省略的回答：该次作业的 reader/writer 临界操作不被抢占；README 中“每到 Period_S 且 time slice 长度为 10 时排序”是笔误，改为每到 Period_S 都排序。这里描述的是这份历史模拟作业的约定，不能据此认定真实操作系统在读写锁内禁用抢占。周期提升遇到同刻新到达，原 FAQ 允许先排序或让新任务参加排序，均不影响当次作业评分；手算一道确定的题仍须固定一种规则，不能中途切换。
p.10–12：时间片与allotment不是同一个计数
p.10 We have process A and process B.
Rule 1: If Priority(A) > Priority(B), A runs (B doesn’t).
Rule 2: If Priority(A) = Priority(B), A & B run in round-robin fashion using the time slice (quantum length) of the given queue.
Rule 3: When a job enters the system, it is placed at the highest priority (the topmost queue). For the jobs arriving at the same time, schedule the job with largest(or smallest) pid first.
p.11 We have process A and process B.
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 one queue and will be at the tail of the target queue, which means it will be scheduled last).
Rule 5: After some time period S, move all the jobs in the system to the topmost queue, and sort all the jobs by pid. The job with the largest(or smallest) pid will be scheduled first.
p.12 This is a common question that often appears in final exams.
In recent 3 years, it appeared in the final exams of
First term of 2023-2024
First term of 2022-2023
First term of 2021-2022
Second term of 2021-2022
高队优先，同队RR，新任务先入最高队；在某级累计用尽allotment才降级，主动让出也不清零。p.12声称历年多次考过，只能说明本Tutorial引用过历史试题，不能推出2026T1一定再考。
p.13–15：完整读题再落笔
p.13 This question will give you the MLFQ rules. For example, Question 3 in Course Examination 1st Term, 2023-2024
Pay attention to the details.
p.14 Next, this question will give you the related information, such as
p.15 Finally, you are required to fill the MLFQ table.
截图引用2023–24 T1 Q3：同刻到达取较大PID先，降级放目标队尾；每S将任务提升，先按原到达时间早者，平局再较大PID。p.15给部分已填行，40–80整段运行PID45也与p.8的时间片内不抢占一致。
p.16–18：完整题面与第一行
p.16 Arriving at the same time → Largest pid first
After period S → Earliest, Largest pid first
五任务为下表，初始无任务，未说明I/O，按纯CPU执行；Q3/Q2/Q1从高到低，周期S=300。
| PID | 到达时间 | 总执行时间 |
|---|---|---|
| 45 | 10 | 130 |
| 323 | 50 | 28 |
| 2023 | 50 | 20 |
| 122 | 80 | 90 |
| 1242 | 80 | 100 |
| 队列 | 时间片 | 本级累计预算 |
|---|---|---|
| Q3 | 10 | 30 |
| Q2 | 40 | 80 |
| Q1 | 60 | 120 |
t=0–10空闲不填；p.17在10把45放Q3预算30，p.18执行10–20，剩工作120、预算20。这两个剩余量从此一直分别记。
p.19–21：45先降Q2，50到达者等当前片结束
20–30、30–40继续45，工作依次110、100；累计30耗尽Q3预算，降Q2预算80。40–80运行40，工作剩60、Q2预算剩40。虽然50有2023与323到达，按本题假设等到80才抢占选队。80又到1242、122，新队顺序2023、323、1242、122；45留在Q2等待。
p.22–24：Q3第一轮前三个
80–90跑2023，剩10，预算20，移队尾；90–100跑323，剩18，预算20；100–110跑1242，剩90，预算20。每段都从工作量和本级预算各扣10。
p.25–27：短任务先完成
110–120跑122，剩80；120–130跑2023，剩0而完成，不用等待其预算耗尽；130–140跑323，剩8。完成、片到期、预算耗尽是不同事件，不能固定每次都跑满10。
p.28–30：最后8单位不补到整片
140–150跑1242，剩80；150–160跑122，剩70；160–168跑323只需8即完成。这个8也从预算扣，下一任务从168开始，不等到170。
p.31–33：降级任务排在已有45后面
168–178跑1242，剩70，Q3累计30耗尽，入Q2尾；178–188跑122，剩60，也降级。Q2此时45、1242、122。188–228再跑45的40，工作剩20且Q2预算耗尽，降Q1；图中各框左右次序已逐一核对，文本抽取的顺序可能错乱。
p.34–36：300的提升会截短时间片
228–268跑1242，剩30、Q2预算40；268起122原可跑40至308，但300触发提升，实际运行32，剩工作28、Q2预算48。提升后所有未完成者进Q3并重置预算30：45到达10最早，其后80同时到达的1242、122按PID降序。
补充：为什么268这一行只跑32。 不要先画40格再硬把300挤进中间；先列出会终止当前运行段的事件。122在268时剩60服务，本级预算80，时间片40，因此若没有周期事件，最早是片在308到期。但下一次周期提升是300，距离当前32，所以本段只消耗32。随后剩工作60−32=28、原级预算80−32=48，与原图相符。
这一步同时说明新到达不抢占与周期提升可截断并不矛盾：题目对不同事件给了不同处理方式。把“片内不抢占”扩成“任何事件都不处理”会把122跑到308，后面所有行都偏移。
记账可分三个层次：全任务剩余服务跨队列保留；本级预算在级别/提升事件按题设重置；单次时间片在每次派发时重新开始。它们恰好都用时间单位，但不是同一个变量。
p.37–39：提升后第一轮
300–310跑45剩10；310–320跑1242剩20；320–330跑122剩18。重置的是层级预算，不是任务剩余工作；45不会重新变130。
p.40–42：45结束，另两人轮转
330–340跑45完成；340–350跑1242剩10；350–360跑122剩8。各任务累计获得的CPU时间仍必须与题设总工作一致。
p.43–45：收尾与总量反算
360–370跑1242完成；370–378跑122完成；p.45为Q&A。总CPU需求130+28+20+90+100=368，开始于10且此后无空闲，最后378，和逐行表一致。完整26行在本节下表。
补充指标：完成时刻45/323/2023/122/1242分别340/168/130/378/370，周转330/118/80/298/290，平均223.2；首次运行10/90/80/110/100，响应0/40/30/30/20，平均24。这里沿用本题非抢占到达规则，换规则应整表重算。
不看附表自检：为什么最后时刻378可以反查，但不能独自证明26行都对？
总服务368，第一次开始10，期间无空闲，故最后为378。这能排除丢失或多算CPU时间，却不能排除把同样总量错误分给不同任务。还应逐PID合计运行区间，分别核130、28、20、90、100；再检查每次选的是当时最高非空队列，且同级顺序符合到达、轮转和提升规则。总量守恒是必要检查，不是完整调度证明。
原例26行完整结果
| 行 | 执行区间 | PID | 到达 | 执行后剩余 |
|---|---|---|---|---|
| 1 | 10–20 | 45 | 10 | 120 |
| 2 | 20–30 | 45 | 10 | 110 |
| 3 | 30–40 | 45 | 10 | 100 |
| 4 | 40–80 | 45 | 10 | 60 |
| 5 | 80–90 | 2023 | 50 | 10 |
| 6 | 90–100 | 323 | 50 | 18 |
| 7 | 100–110 | 1242 | 80 | 90 |
| 8 | 110–120 | 122 | 80 | 80 |
| 9 | 120–130 | 2023 | 50 | 0 |
| 10 | 130–140 | 323 | 50 | 8 |
| 11 | 140–150 | 1242 | 80 | 80 |
| 12 | 150–160 | 122 | 80 | 70 |
| 13 | 160–168 | 323 | 50 | 0 |
| 14 | 168–178 | 1242 | 80 | 70 |
| 15 | 178–188 | 122 | 80 | 60 |
| 16 | 188–228 | 45 | 10 | 20 |
| 17 | 228–268 | 1242 | 80 | 30 |
| 18 | 268–300 | 122 | 80 | 28 |
| 19 | 300–310 | 45 | 10 | 10 |
| 20 | 310–320 | 1242 | 80 | 20 |
| 21 | 320–330 | 122 | 80 | 18 |
| 22 | 330–340 | 45 | 10 | 0 |
| 23 | 340–350 | 1242 | 80 | 10 |
| 24 | 350–360 | 122 | 80 | 8 |
| 25 | 360–370 | 1242 | 80 | 0 |
| 26 | 370–378 | 122 | 80 | 0 |
总执行368，所有任务剩余归零。回逐页推导。
补充：用原表做两种独立验算，分别抓不同错误。 服务守恒检查每个 PID 所有运行段长度之和是否等于题目需求：45 为 130，2023 为 20，323 为 28，1242 为 100，122 为 90，总和 368。时间线从 10 到 378，跨度也为 368；在这个无空闲、无切换成本的原表中两者应相等。若不等，必有服务漏算、重复或额外空洞。
但总量相等仍不能证明选择顺序正确。第二种检查在每个段起点重建队列：哪些任务已到达，哪些已完成，谁处于更高级别，当前片是否允许被该事件截断，平局按什么顺序。比如把某两个同长度段交换，总服务仍然相等，却可能违反优先级。先用守恒找算术错，再用事件规则找调度错，才能解释原 26 行为什么不只是一个凑对最终时刻的表。
本讲核心考点
- [A-历史题截图] 2023–24 T1 Q3的MLFQ填表；证据是本Tutorial p.13–15所嵌题面，并非已取得该期完整试卷。
- [C] 分别扣减工作量、时间片和本级累计预算。
- [C] 处理同刻到达、完成、降级入尾和周期提升。
- [C] 用CPU总量与完成时间反算调度表。
附录
完整演算已放回相应页的正文，原链接锚点继续保留。
来源与证据
-
原件：T07-多级反馈队列-2025T2.pptx（本地课件）；PDF副本（本地课件） p.1–45。本文页码均为 PDF 页号。
-
考试证据：读了 课程大纲-2026T1.pdf、教学计划-2026T1.pdf、T08-期中参考-2025T2-题目-解答.pdf、T07-多级反馈队列-2025T2.pdf（p.13–15内嵌历史试题）；未识别用途的 PDF：无
-
2026-10-13 内容补全：保留原页顺序与版本，补入对应页的程序、接口、字段、条件和演算；原程序片段保留课件行号、拼写与省略处，不能据此视为经过编译的完整软件。本文已有运行记录属于其标注日期，本次未重新运行课程容器或提交作业。