Lab 1 Guide
Dear friends,
Worksheet 9 is very difficult to understand 🥲. Here I have rewritten it with Claude's help, in the hope that you can successfully complete this lab. Furthermore, we visualize all the public test cases and even offer you a visual debugger in the Oops! What's Wrong? section.
Please step through the tests below using the ⬅️ ➡️ keys on your keyboard.
Please enjoy! Best wishes!
- 💡 Learn more about how to use gdb.
- 💡 Learn more about how to prepare for the quiz.
- 📖 Go back to the old worksheet 9.
Start here
xv6 runs on one CPU in this lab, so only one job runs at a time. A hardware timer interrupts the CPU again and again. The time between two timer interrupts is one tick, about 0.1 s.
At every timer interrupt the kernel first counts the tick (provided), then asks whether the running job must stop. Whenever the CPU is free, it asks who runs next. You write the purple parts:
The lab has five tasks, one branch each. In q0–q3 you change the same two functions in kernel/sched.c: a picker (who runs next) and should_preempt() (must the running job stop now?). q4 combines the four pickers and adds rules for moving jobs between queues.
| Task | Branch | Policy | Who runs next | Stops at a timer interrupt when… | Points |
|---|---|---|---|---|---|
| 1 | q0 | Round robin | joined the ready queue first | its 2-tick slice is used up and another job is ready | 10 |
| 2 | q1 | Shortest estimated time left | least time left | never | 10 |
| 3 | q2 | Priority with aging | best priority, improved by waiting | a ready job comes before it | 10 |
| 4 | q3 | First come, first served | joined the ready queue first | never | 10 |
| 5 | q4 | Multilevel feedback queue | highest non-empty of 4 queues | a table of rules | 60 |
Do the tasks in order: q4 copies your pickers from q0–q3. The deadline is 2026/11/10 23:59 (UTC+8).
Set up and run the tests
The code is on GitHub: os-xv6-lab-student. Everything runs in the course container, which has the compiler, QEMU and the grading script. Install Docker, then, once:
git clone https://github.com/GaGa55555LaLa/os-xv6-lab-student.git
cd os-xv6-lab-student
docker build -t xv6-lab .devcontainer
Each time you work, start the container in the repository folder (macOS and Linux):
docker run -it --rm --name xv6 -u "$(id -u):$(id -g)" -v "$PWD":/xv6 -w /xv6 xv6-lab bash
Windows
In PowerShell:
docker run -it --rm --name xv6 -v "${PWD}:/xv6" -w /xv6 xv6-lab bash
If ./grade prints env: $'python3\r': No such file or directory, commit your work, then run git config core.autocrlf false, git rm -r -q --cached . and git reset -q --hard.
Shortcuts: ./lab shell starts the container, and ./lab grade runs the tests in it (Git Bash or WSL). In VS Code, "Dev Containers: Reopen in Container" also works.
Inside the container:
git checkout q0 # the branch of Task 1
./grade # build, run every public test, compare with the expected output
./grade late # run one test
make qemu # boot xv6 yourself; quit with Ctrl-a, then x
$ schedcheck late # (inside xv6) run one test and print its log
Commit on each branch before you switch: git commit -am "q0: round robin". The TAs grade the last commit on each branch.
How a Test Runs and What It Prints
A test is a small program, such as schedcheck late, that starts a few jobs named A, B, C. Each job follows a script of two kinds of steps:
- run n: use the CPU for n ticks. A job that is not on the CPU makes no progress.
- pause(n): sleep for n ticks, standing in for waiting on a disk or the network.
At any moment a job is in one of three states. The colours stay the same on the whole page:
- RUNNING: on the CPU. Only one job at a time.
- RUNNABLE, or ready: wants the CPU and waits for it. All ready jobs together form the ready queue.
- SLEEPING: in
pause(). It does not want the CPU until it wakes up.
We number the timer interrupts like the ticks: interrupt k ends tick k−1 and starts tick k, and interrupt 0 is when the test starts. Every decision happens at an interrupt, or when the running job sleeps or exits.
Each job also has a process id, its pid. A has the smallest, then B, then C. When two jobs tie, the smaller pid goes first.
Here is a public test of q0, round robin, one interrupt at a time. In round robin every job gets the CPU for at most 2 ticks, its time slice, and then goes to the end of the ready queue. Press Next (or the → key) to move one interrupt forward.
Every public test in this guide has a step-by-step view like the one below. The timeline at the top shows who held the CPU in each tick. The three boxes below it show the moment right after the current interrupt: On the CPU, the Ready queue in the order the next pick will take them, and the Log lines the kernel printed, with the new ones in yellow. Steps marked ★ are worth a closer look.
exit(): ev 12 C run, then ev 12 C exit, with no tick in between.
How to interpret one log line
The kernel records every scheduling decision as one line. ./grade compares your lines with the expected ones, line by line and in order. One wrong line fails the whole test.
ev 2 A requeue L0
│ │ │ └─ queue level after the event (always L0 until q4)
│ │ └───────── what happened
│ └─────────── which job
└───────────── tick
| Event | Meaning |
|---|---|
new | The job arrives and joins the ready queue. |
run | The job your picker chose gets the CPU. |
tick | The tick that just ended is charged to the running job. |
requeue | The running job gives up the CPU and goes to the end of the ready queue. |
sleep | The running job calls pause(). |
wake | The job's pause is over, and it joins the ready queue. |
exit | The job is done. |
You never print a log line yourself. Your code decides which job runs and when the running job stops, and the provided code prints the lines. q4 adds three more events, explained there.
⚠️ Be careful!! ⚠️
Your scheduler can be right and still print lines in an order you did not expect. These three facts explain every surprising order in the public tests:
- A tick line looks back. The line for tick 0 is printed at interrupt 1, when tick 0 has ended:
ev 0 A tickappears afterev 0 A run. - Within one interrupt, jobs come in table order. The kernel walks its process table A, B, C, …, charging the running job and waking sleepers as it goes. Only then does the running job stop, and only then does the next job run. In test
wake, interrupt 3 printsev 3 A wakebeforeev 2 B tick, because A comes before B in the table. - A finished job needs the CPU once more to exit. A job counts its own ticks, and it can only notice that it is done while it is on the CPU. If it keeps the CPU at the interrupt that ends its last tick,
exitfollows at once: in testalone,ev 4 A tickthenev 5 A exit. If it was stopped at that interrupt, it has to be picked once more:run, thenexit, as C at interrupt 12 above.
Details How a job counts its ticks
run n calls burn(n), which loops on the system call cputicks() until the job has been charged n more ticks. A job waiting in the ready queue is not charged, so its count simply pauses. This is also why a job needs the CPU once more after its last tick: only then can its loop see that the count has reached n.
The Ready Queue and Your Picker
xv6 keeps every process in one fixed array, proc[]. There is no separate queue to add to or remove from. The ready queue is simply every entry whose state is RUNNABLE, and its order comes from fields in each entry.
For a queue in arrival order, the field is enter_tick: the tick at which the job joined the ready queue. The provided code sets it when a job arrives or wakes up. A job that has waited longest has the smallest enter_tick. "Go to the end of the queue" just means setting enter_tick to the current tick, ticks. When two jobs joined at the same tick, the one with the smaller pid goes first. Jobs A, B, C, … have increasing pids.
Here is proc[] in test late right after interrupt 4:
| Entry | state | enter_tick | Place in the ready queue |
|---|
Read from the real log. At interrupt 4, B used up its slice and rejoined at tick 4, after C, which joined at tick 3.
How a picker works
A picker returns the ready job that should run next. You never write the loop over proc[] yourself. The provided pick_by() does the scanning and the locking. You give it a comparison function before(a, b) that returns non-zero when job a should run before job b:
| 91 | // The best RUNNABLE process in queue level, where before(a, b) says |
| 92 | // whether a should run before b. |
| 93 | static __attribute__((unused)) struct proc * |
| 94 | pick_by(int level, int (*before)(struct proc *, struct proc *)) |
| 95 | { |
| 96 | struct proc *p, *best = 0; |
| 97 | |
| 98 | for (p = proc; p < &proc[NPROC]; p++) { |
| 99 | acquire(&p->lock); |
| 100 | if (p->state == RUNNABLE && p->level == level && |
| 101 | (best == 0 || before(p, best))) |
| 102 | best = p; |
| 103 | release(&p->lock); |
| 104 | } |
| 105 | return best; |
| 106 | } |
So writing a picker comes down to one question: when should a run before b? Each scheduling policy has a different choice. For example:
- Round robin (
q0) and first come, first served (q3) run the job that joined the ready queue first, the one with the earliestenter_tick. - Shortest estimated time left (
q1) runs the job with the least time left in its CPU burst. - Priority with aging (
q2) runs the job with the best priority, after waiting has improved it.
Every policy breaks ties the same way: the smaller pid wins.
The level argument matters only in q4, where there are four queues. In q0–q3 every job is in queue 0.
Reference All the fields your code uses
Each entry of proc[] holds many fields. Your code reads and writes only these. Each task section introduces the ones it needs.
| Field | Meaning | Set by | Branches |
|---|---|---|---|
state | RUNNING, RUNNABLE, SLEEPING, … | provided code, and you when a job gives up the CPU | all |
pid | process id, used to break ties | provided | all |
enter_tick | when it joined the ready queue | provided code when a job arrives or wakes, and you when it goes to the end | q0, q3, q4 |
slice_used | ticks run since it was last picked | provided code (+1 per tick, 0 when picked), and you when a new slice starts | q0, q4 |
burst_est, cur_burst | the estimated length of its CPU burst, and the ticks it has run in this burst | see q1 | q1, q4 |
priority, wait_ticks | its priority (0 is the best), and the ticks it has spent ready since it last ran | see q2 | q2, q4 |
level, allot_used, demoted | its queue in q4, and two counters for moving between queues | see q4 | q4 |
The Code That All Scheduling Policies Will Need
Whatever the policy, two pieces of code are the same on every branch: TODO (trap) connects the timer to the scheduler, and TODO (yield) makes a stopped job give up the CPU. You write them on q0 and copy them to the other branches. The lock rules at the end of this section also hold for every policy.
TODO (trap): connect the timer
Every timer interrupt reaches clockintr() first. It adds 1 to ticks. Your line there tells the scheduler that a tick has passed:
| 165 | void |
| 166 | clockintr() |
| 167 | { |
| 168 | if (cpuid() == 0) { |
| 169 | acquire(&tickslock); |
| 170 | ticks++; |
| 171 | wakeup(&ticks); |
| 172 | release(&tickslock); |
| 173 | // TODO (trap): tell the scheduler that a tick has passed. |
| 174 | } |
| 175 | |
| 176 | // ask for the next timer interrupt. this also clears |
| 177 | // the interrupt request. 1000000 is about a tenth |
| 178 | // of a second. |
| 179 | w_stimecmp(r_time() + 1000000); |
| 180 | } |
Then the interrupt returns to one of two handlers: usertrap() if the job was running its own code, or kerneltrap() if the CPU was inside the kernel. Both handlers get a number, which_dev, that says which device caused the interrupt. For the timer, which_dev is 2. Your line in each lets the scheduler decide whether the running job must stop:
| 81 | if (killed(p)) |
| 82 | kexit(-1); |
| 83 | |
| 84 | // TODO (trap): on a timer interrupt (which_dev == 2), let the |
| 85 | // scheduler decide whether to give up the CPU. |
| 86 | |
| 87 | prepare_return(); |
| 88 |
| 151 | r_stval()); |
| 152 | panic("kerneltrap"); |
| 153 | } |
| 154 | |
| 155 | // TODO (trap): on a timer interrupt (which_dev == 2), let the |
| 156 | // scheduler decide whether to give up the CPU. There may be no |
| 157 | // current process: the CPU can be in the scheduler loop. |
| 158 | |
| 159 | // the scheduler may have caused some traps to occur, |
| Situation | What should happen |
|---|---|
clockintr(): a tick has passed | call sched_tick() (provided: charges the tick, counts waiting, wakes sleepers) |
usertrap(): which_dev is 2 | call sched_timer() (provided: asks your should_preempt()) |
kerneltrap(): which_dev is 2 and a job is running | call sched_timer() |
kerneltrap(): which_dev is 2 but no job is running | nothing: there is no job to stop |
myproc() returns 0. sched_timer() uses myproc(), so calling it then crashes the kernel. This already happens while xv6 boots, so ./grade reports that xv6 did not reach the shell../grade reports that it did not finish.TODO (yield): give up the CPU
sched_timer() calls your should_preempt(p) for the running job p. It returns 0 (keep running) or PREEMPT_REQUEUE (stop and go to the end of the ready queue). On a stop, sched_timer() takes p->lock, and your yield code runs:
| 212 | // Called from usertrap() and kerneltrap() on a timer interrupt. |
| 213 | void |
| 214 | sched_timer(void) |
| 215 | { |
| 216 | struct proc *p = myproc(); |
| 217 | int r = should_preempt(p); |
| 218 | |
| 219 | if (r == 0) |
| 220 | return; |
| 221 | acquire(&p->lock); |
| 222 | // TODO (yield): p gives up the CPU. Put it back in the ready queue, |
| 223 | // at the end of the queue. |
| 224 | schedlog(p, r == PREEMPT_REQUEUE ? SEV_REQUEUE : SEV_PREEMPT); |
| 225 | // TODO (yield): switch to the scheduler. |
| 226 | release(&p->lock); |
| 227 | } |
| Situation | What should happen |
|---|---|
should_preempt() returned PREEMPT_REQUEUE | p becomes ready again, joins the end of the ready queue, and then switches to the scheduler with sched() |
p->statep->enter_ticktickssched()sched() is provided. Think of it as "switch to the scheduler": it returns only when the picker chooses p again. The requeue line between your two TODOs is printed for you.
q1 and q3 never stop a job, so their tests never reach this code. q2 reaches it, but its tests cannot tell where in the queue the job went. q0 is where "the end of the queue" is checked. q4 adds a second kind of stop, explained there.
Please use the lock carefully
Each entry of proc[] has a lock, p->lock, that protects its fields. Please follow these three rules.
| Rule | Where it applies | If you break it |
|---|---|---|
1. Release every lock before you call a picker. A picker, pick_by() and top_level() lock every process themselves, and a lock cannot be taken twice. Inside your before(a, b), do not take a lock either: pick_by() already handles it. | your pickers, and should_preempt() when it asks a picker | panic: acquire |
2. In should_preempt(), hold p->lock while you use p's fields. It is called without the lock, so you take it and release it yourself, and release it before rule 1 applies. To compare p with the job a picker returned, holding p->lock alone is enough. | should_preempt() | no crash on our one CPU, but the rules require it |
3. Where the lock is already held, do not take it again. In the yield code, sched_timer() holds p->lock: keep holding exactly that lock until sched(), and make p stop being RUNNING first. In q4, the hooks charge(), sched_tick(), sched_sleep() and sched_wakeup() also run with p->lock held. | TODO (yield) and the q4 hooks | panic: acquire, panic: sched RUNNING, panic: sched locks, panic: sched p->lock (released too early) |
A panic stops the kernel and scores 0 for that test. Because should_preempt() runs for every process, not only for test jobs, a lock mistake there often crashes xv6 while it boots. Oops! What's Wrong? shows what each panic looks like in ./grade.
q0 · Round robin
Round robin shares the CPU fairly: no job can hold it for long while others wait. It needs one new field. p->slice_used counts the ticks a job has run in its current time slice. The slice length is RR_SLICE, which is 2, in kernel/param.h. The provided code adds 1 to slice_used at every tick the job runs, and sets it to 0 when the picker chooses the job.
You also need the two TODOs from TODO (trap): connect the timer and TODO (yield): give up the CPU. Write them on this branch first.
Who runs next: pick_rr()
You write the before(a, b) that pick_by() needs, and call pick_by() from pick_rr():
| 108 | // In ready-queue order; the running process gives up the CPU when its |
| 109 | // time slice is used up (see should_preempt()). |
| 110 | struct proc * |
| 111 | pick_rr(int level) |
| 112 | { |
| 113 | // TODO (q0): the RUNNABLE process in queue level that runs next. |
| 114 | return 0; |
| 115 | } |
| Situation: two ready jobs a and b | What should happen |
|---|---|
| a joined the ready queue at an earlier tick than b | a runs before b |
| a and b joined at the same tick | the one with the smaller pid runs first |
| no job is ready at all | the picker returns 0 (pick_by() already does this) |
p->enter_tickp->pidpick_by()Locks: pick_by() does the locking for the picker. See the three lock rules.
Must it stop? should_preempt()
At every timer interrupt, after the tick has been charged, sched_timer() asks this function about the running job p. A slice is used up when the job has run at least RR_SLICE ticks in it.
| 203 | // Should the running process p give up the CPU at this timer interrupt? |
| 204 | static int |
| 205 | should_preempt(struct proc *p) |
| 206 | { |
| 207 | // TODO (q0): must p give up the CPU now? Return 0 to keep |
| 208 | // running, or PREEMPT_REQUEUE. |
| 209 | return 0; |
| 210 | } |
| Situation | What should happen |
|---|---|
| p has not used up its slice | keep running: return 0 |
| p has used up its slice, and another job is ready | stop: return PREEMPT_REQUEUE |
| p has used up its slice, and no other job is ready | keep running: return 0, and start a new slice (slice_used back to 0) |
p->slice_usedRR_SLICEpick_rr()p->lockTo learn whether another job is ready, you can ask your own picker. p is RUNNING, not RUNNABLE, so the picker never returns p itself.
Locks: this function is called without p->lock, so follow the three lock rules.
One test, step by step
In test slice, A is alone when its first slice is used up, and B arrives during A's new slice. Watch the slice counter next to the running job.
should_preempt() must start the new slice: A is not picked again, so the provided reset does not run.
B's arrival (ev 3 B new) does not stop A, because A's new slice has only 1 tick in it. A also runs tick 3. Without the reset at interrupt 2, A's slice would still look used up, and A would stop here.
Only now are both conditions true: the slice is used up and another job is ready. So ev 4 A requeue, then ev 4 B run.
All public tests
Pitfalls
- No new slice. In
slice, A must keep the CPU at interrupt 3 (ev 3 A tick). If your output hasev 3 A requeuethere, the third row of the table never resetslice_used. - Stopping a job that is alone. In
alone, A runs all 5 ticks, 0 to 4, without a break (ev 2 A tick).ev 2 A requeuefollowed byev 2 A runmeans you stopped A although no other job was ready. - Holding the lock while asking the picker. The first slice that is used up with another job ready is at interrupt 2 of
turns(ev 2 A requeue). If you callpick_rr()while holdingp->lock, the kernel panics before the test can print its log:./gradesaysdid not finish within 15s, thenFAIL (no output; see grade.out), andgrade.outends withpanic: acquire. Becauseshould_preempt()runs for every process, not only test jobs, this can happen already at boot (xv6 did not reach the shell). - Ties go to the smaller pid. In
wake, A woke up at tick 3 and B rejoined at tick 3. At interrupt 5 they tie, and A runs because its pid is smaller.ev 5 B runmeans your tie goes the wrong way.
When a test fails What each q0 test catches
| Test | What it checks | Likely cause when it fails |
|---|---|---|
turns | Three jobs take turns, 2 ticks each, A first (ev 0 A run). | A runs 4 ticks in a row: should_preempt() never stops. A runs again at interrupt 2: TODO (yield) does not move A to the end of the queue. No output and panic: acquire at the end of grade.out: lock held while calling the picker. |
alone | A job alone is never stopped. | should_preempt() stops when the slice is used up without asking whether another job is ready. |
late | A job that arrives joins the end: A, which rejoined at tick 2, runs before C, which arrived at tick 3. | before() compares pids only, or TODO (yield) does not set enter_tick to the current tick. |
wake | A job that wakes up joins the end, and a tie on the joining tick goes to the smaller pid (ev 5 A run). | The tie in before() is missing or reversed. |
slice | A job alone starts a new slice and keeps the CPU (ev 3 A tick). | The third row of the should_preempt() table does not reset slice_used. |
Every test hangs: pick_rr() still returns 0, or sched_tick() is not called (see TODO (trap): connect the timer).
q1 · Shortest estimated time left
Running short jobs first makes the average wait short. To know which job is short, the kernel needs a guess of how long each one will run.
A CPU burst is the time a job runs from when it gets the CPU until it sleeps in pause() or exits. Each job starts with an estimate of its burst, p->burst_est, set by the test (the "estimate" in each workload below). In q1 the estimate never changes. p->cur_burst counts the ticks the job has run in its current burst. The provided code adds 1 to it at every tick the job runs, and sets it to 0 when the job sleeps.
Time left is burst_est − cur_burst. A job that wakes up starts a new burst, so its time left is its whole estimate again. Write time left with both fields, burst_est − cur_burst, now. In q1 no job is stopped halfway, so the difference does not show yet, but q4 copies this comparison and its tests need cur_burst.
A policy that never stops a job at a timer interrupt is called non-preemptive. This one is.
Copy your two TODOs from TODO (trap): connect the timer and TODO (yield): give up the CPU to this branch. The tests here never reach the yield code.
Who runs next: pick_shortest()
As in round robin, you write a before(a, b) for pick_by(). Only the order changes:
| 108 | // The process with the least estimated time left in its CPU burst. |
| 109 | struct proc * |
| 110 | pick_shortest(int level) |
| 111 | { |
| 112 | // TODO (q1): the RUNNABLE process in queue level that runs next. |
| 113 | return 0; |
| 114 | } |
| Situation: two ready jobs a and b | What should happen |
|---|---|
| a has less time left than b | a runs before b |
| a and b have the same time left | the one with the smaller pid runs first, even if the other has waited longer |
| no job is ready at all | the picker returns 0 (pick_by() already does this) |
p->burst_estp->cur_burstp->pidpick_by()When a job joined the queue does not matter here, so enter_tick is not used. Locks: the same as for pick_rr(). See the three lock rules.
Must it stop? should_preempt()
| 202 | // Should the running process p give up the CPU at this timer interrupt? |
| 203 | static int |
| 204 | should_preempt(struct proc *p) |
| 205 | { |
| 206 | // TODO (q1): must p give up the CPU now? Return 0 to keep |
| 207 | // running, or PREEMPT_REQUEUE. |
| 208 | return 0; |
| 209 | } |
Leave the skeleton's return 0: q1 never stops a job at a timer interrupt. A job stops only when it sleeps or exits, and the provided code handles both.
One test, step by step
In test wake, a job sleeps and comes back. Watch the time left next to each job.
ev 1 A sleep) ends A's burst, so its cur_burst goes back to 0. B has the smaller pid, but the pid only breaks ties: C has 3 left and B has 4, so C runs.
A starts a new burst (ev 2 A wake), so its time left is its whole estimate again, 2. It still does not take the CPU from C: q1 never stops a job, so C also runs ticks 2 and 3.
B has waited since tick 0, but waiting does not count here. A has 2 left and B has 4, so A runs.
All public tests
The estimate is only a guess. In tie-arrival, A's estimate is 1 but A runs 3 ticks, up to tick 2, so the On the CPU box shows its time left falling below 0. A keeps the CPU anyway.
Pitfalls
- Ordering by arrival. In
wakeat interrupt 1, B and C both joined at tick 0, and C must run.ev 1 B runmeans yourbefore()still orders by when jobs joined, as in round robin. - Breaking ties by arrival. In
tie-arrivalat interrupt 3, B and C both have 3 left. C arrived first, but B runs because its pid is smaller.ev 3 C runmeans your tie usesenter_tick. - Stopping for a shorter job. In
no-preempt, B (estimate 1) arrives at tick 2 while A (estimate 6) runs. A keeps the CPU (ev 2 A tick).ev 2 A requeuemeansshould_preempt()stopped A. - Stopping when the estimate runs out. In
shortest, B's estimate is 2 but it also runs tick 2.ev 2 B requeuemeans you stopped B when its time left reached 0.
When a test fails What each q1 test catches
| Test | What it checks | Likely cause when it fails |
|---|---|---|
shortest | The least estimate runs first: B (2), then C (4), then A (6). | A runs first: before() orders by pid or by arrival. ev 2 B requeue: should_preempt() stops a job. |
no-preempt | A shorter job that arrives does not stop the running one (ev 4 B run). | should_preempt() returns something other than 0. |
tie | Equal estimates: the smaller pid runs first (ev 0 A run). | The tie in before() is missing or reversed. |
tie-arrival | Equal estimates: the smaller pid wins over the earlier arrival (ev 3 B run). | The tie uses enter_tick instead of the pid. |
wake | A job back from sleep is compared by its whole estimate (ev 4 A run). | before() orders by arrival, or computes time left from the wrong fields. |
q2 · Priority with aging
Always running the most important job could leave the others waiting forever. Aging fixes that: a job that waits long enough climbs to the top. Two new fields, both kept up to date for you:
priority: a number from 0 to 9 set by the test. 0 is the best. It never changes.wait_ticks: ticks spent ready since the job last ran. It is 0 when the job arrives, wakes up or is picked, and does not grow while the job runs.
effective priority = max(0, priority − wait_ticks ÷ PRIO_AGE_STEP)
The division rounds down. PRIO_AGE_STEP is 3, so every 3 ticks of waiting improve a job by one step.
| 20 | #define PRIO_AGE_STEP 3 // +1 priority per this many waiting ticks |
A job with priority 5, after waiting:
| Ticks waited | 0 | 2 | 3 | 6 | 20 |
|---|---|---|---|---|---|
| Steps gained | 0 | 0 | 1 | 2 | 6 |
| Effective priority | 5 | 5 | 4 | 3 | 0 (not −1) |
Job a comes before job b if a has the smaller effective priority, or the same one and the smaller pid. How long a job waited counts only through its effective priority, never as a tie-break.
The running job has wait_ticks 0, so it competes with its own priority.
Who runs next: pick_priority()
As in How a picker works, your picker hands pick_by() a comparison before(a, b).
| 108 | // The process with the highest priority after aging. |
| 109 | struct proc * |
| 110 | pick_priority(int level) |
| 111 | { |
| 112 | // TODO (q2): the RUNNABLE process in queue level that runs next. |
| 113 | return 0; |
| 114 | } |
| Situation | What should happen |
|---|---|
| a has the smaller effective priority | a goes first |
| Same effective priority, a has the smaller pid, even if b waited longer or arrived earlier | a goes first |
p->priorityp->wait_ticksPRIO_AGE_STEPp->pidLock rule: take no lock in your comparison (see the three lock rules).
Must it stop? should_preempt()
At every timer interrupt the question is: does some ready job come before the running job p? Only the job your picker would choose matters. If it does not, no ready job does.
| 202 | // Should the running process p give up the CPU at this timer interrupt? |
| 203 | static int |
| 204 | should_preempt(struct proc *p) |
| 205 | { |
| 206 | // TODO (q2): must p give up the CPU now? Return 0 to keep |
| 207 | // running, or PREEMPT_REQUEUE. |
| 208 | return 0; |
| 209 | } |
| Situation | What should happen |
|---|---|
| No other job is ready | keep running: return 0 |
The picker's job has a smaller effective priority than p's priority | p stops: return PREEMPT_REQUEUE |
The picker's job has the same effective priority and a smaller pid than p | p stops: return PREEMPT_REQUEUE |
| The picker's job has a larger effective priority, or the same one and a larger pid | keep running: return 0 |
pick_priority()p->priorityp->pidPREEMPT_REQUEUELock rule: release p->lock before you call pick_priority(), or the kernel stops with panic: acquire (see the three lock rules).
A stop runs your code from TODO (yield): give up the CPU.
One test, step by step
In test age-tie-preempt the CPU changes hands three times. The ready queue shows how long each job has waited and its effective priority.
ev 10 B requeue, and A gets tick 10.
Picking A set its wait_ticks to 0, so it is back to its own priority, 4. One tick on the CPU undoes all its aging, and A stops again.
All public tests
Test age-pid-not-wait is the other trap, shown from interrupt 6.
Pitfalls
- Stopping only for a strictly better job. In
age-tie-preempta tie must stop B at interrupt 10. Symptom:ev 10 B tickwhereev 10 B requeueis expected. - Stopping on every tie. In
aging, B ages to 1 at interrupt 6, tying the running A, which has the smaller pid. So A keeps tick 6, and B takes over only at interrupt 9. Symptom:ev 6 A requeue. - Breaking ties by waiting time or arrival. In
age-pid-not-waitA runs at interrupt 6, and intie-arrivalB runs at interrupt 2 before C, which arrived earlier. Symptom: the other job'srunline. - Writing the aged value into
priority. Inage-tie-preemptA must be back to 4 and stop at interrupt 11. Symptom: A keeps tick 11.
When a test fails Which bug each q2 test catches
| Test | What it catches | Likely bug |
|---|---|---|
any, with panic: acquire | the lock rule | pick_priority() called while holding p->lock, or a lock taken inside the comparison |
priority | the order of plain priorities | the comparison is reversed (larger number first), or the picker returns 0 |
preempt | stopping for a better job that arrives | should_preempt() still always returns 0 |
aging | waiting improves a job, and the running job wins a tie with the smaller pid | no aging, the division in the wrong place, or stopping on every tie |
tie | the smaller pid on a full tie | the comparison says yes when both jobs are equal, so the larger pid wins |
tie-arrival | pid, not arrival, breaks ties | ties broken by enter_tick |
age-tie-preempt | an aged tie stops the running job, which is then back to its own priority | stopping only for a strictly better job, or writing the aged value into priority |
age-pid-not-wait | pid, not waiting time, breaks ties | ties broken by wait_ticks |
q3 · First come, first served
Nothing here is new: the order of the ready queue from The Ready Queue and Your Picker, as in q0 but with no time slice, and no stop at a timer interrupt, as in q1.
Who runs next: pick_fifo()
| 108 | // The process that has been in the ready queue the longest. |
| 109 | struct proc * |
| 110 | pick_fifo(int level) |
| 111 | { |
| 112 | // TODO (q3): the RUNNABLE process in queue level that runs next. |
| 113 | return 0; |
| 114 | } |
| Situation | What should happen |
|---|---|
| a joined the ready queue earlier than b | a goes first |
| Both joined at the same tick, a has the smaller pid | a goes first |
p->enter_tickp->pidLock rule: take no lock in your comparison (see the three lock rules).
Must it stop? should_preempt()
| 202 | // Should the running process p give up the CPU at this timer interrupt? |
| 203 | static int |
| 204 | should_preempt(struct proc *p) |
| 205 | { |
| 206 | // TODO (q3): must p give up the CPU now? Return 0 to keep |
| 207 | // running, or PREEMPT_REQUEUE. |
| 208 | return 0; |
| 209 | } |
Leave the skeleton's return 0: q3 never stops a job at a timer interrupt, so it reads no field, takes no lock, and never reaches your yield code.
One test, step by step
Test wake shows the one thing to watch here: a job that wakes up waits behind every job already in the queue.
enter_tick 2, later than C's 0: it goes behind C, although it has the smaller pid.
No time slice: B kept the CPU for all 3 of its ticks while C and A waited, so C gets the CPU only now.
A, the smallest pid, has waited 5 ticks: waking up put it at the end, so it runs last.
All public tests
Pitfalls
- Keeping the time slice from q0. In
no-preempt, B is waiting, yet A keeps tick 2 and every tick until it exits. Symptom:ev 2 A requeue. - Ordering by pid alone. In
wake, A has the smallest pid but woke after C joined, so C gets tick 4. Symptom:ev 4 A run. - Getting the tie the wrong way round. In
arrival, B and C both arrive at tick 1, so B runs first at interrupt 3. Symptom:ev 3 C run.
When a test fails Which bug each q3 test catches
| Test | What it catches | Likely bug |
|---|---|---|
arrival | arrival order, and a tie between two arrivals | the comparison is reversed, ignores enter_tick, or lets the larger pid win a tie |
no-preempt | no stop at a timer interrupt | should_preempt() copied from q0 |
wake | a woken job goes to the end | ordering by pid, not by enter_tick |
tie | the smaller pid on a full tie | the comparison says yes when both jobs are equal, so the larger pid wins |
q4 · Multilevel feedback queue
q4Task 560 points20 public testsyou write: sched_pick(), should_preempt(), yield+ four hooks, four copied pickersJobs with short bursts stay high and run soon, but a job that holds the CPU for long sinks. The queue a job is in is its level, p->level: 0 (L0, the highest) to 3 (L3).
The four queues
Each queue reuses the picker of q0, q1, q2 or q3. The allotment is how many ticks one CPU burst may use in a queue before the job moves down. It starts over in every new queue.
Each test starts its jobs in chosen queues ("starts in L2" in the workload line) to test one rule alone. Your code does nothing for this.
Down arrows: charge(). Up arrows: sched_wakeup(). The L3 → L2 arrow: sched_tick(). Every move puts the job at the end of its new queue.
Unlike q1, L1 stops a running job as soon as a ready L1 job has less time left, or the same and a smaller pid. Time left keeps counting down across a move down and can go below 0 (the On the CPU box then shows, say, "-3 left"). It is just compared as a number. Unlike q2, L2 checks for a better job only when its 2-tick slice is used up, and ages one step per 2 waiting ticks, MLFQ_AGE_STEP. The provided top_level() returns the highest queue with a ready job, or 4 if none.
| 20 | #define MLFQ_NLEVEL 4 |
| 21 | #define MLFQ_SLICE0 1 // L0 time slice |
| 22 | #define MLFQ_SLICE2 2 // L2 re-checks priorities after this many ticks |
| 23 | #define MLFQ_ALLOT0 2 // CPU ticks one burst may use in L0 before demotion |
| 24 | #define MLFQ_ALLOT1 4 |
| 25 | #define MLFQ_ALLOT2 8 |
| 26 | #define MLFQ_AGE_STEP 2 // L2: +1 priority per this many waiting ticks |
| 27 | #define MLFQ_STARVE 20 // L3: promote to L2 after waiting this many ticks |
The last field of a log line is now the job's level after the event, and a tick line shows the queue the tick was charged in. Three events are new:
| Event | Meaning |
|---|---|
demote | The running job used up its allotment and moved one queue down. |
promote | A ready job waited 20 ticks in L3 and moved up to L2. |
preempt | The running job gave up the CPU but kept its place in its queue. requeue still means it went to the end. |
In one interrupt, demote and promote lines come in proc[] order with the tick, new and wake lines.
Who runs next: sched_pick()
First copy your four pickers and their comparison functions into the TODO (q0) to TODO (q3) places. pick_priority() now ages with MLFQ_AGE_STEP. Then sched_pick(), called whenever the CPU is free, must look past L0:
| 148 | // Choose the next process to run. Returns it locked and RUNNABLE, or 0. |
| 149 | struct proc * |
| 150 | sched_pick(void) |
| 151 | { |
| 152 | struct proc *p; |
| 153 | |
| 154 | for (;;) { |
| 155 | // TODO (MLFQ): look at the queues from Q0 to Q3 and take the first |
| 156 | // process found: pick_rr() for Q0, pick_shortest() for Q1, |
| 157 | // pick_priority() for Q2 and pick_fifo() for Q3. For now, only Q0. |
| 158 | p = pick_rr(0); |
| 159 | if (p == 0) |
| 160 | return 0; |
| 161 | acquire(&p->lock); |
| 162 | if (p->state == RUNNABLE) |
| 163 | return p; |
| 164 | release(&p->lock); |
| 165 | } |
| 166 | } |
| Situation | What should happen |
|---|---|
| L0 has a ready job | take the job pick_rr() returns for L0 |
| L0 is empty, L1 has a ready job | take pick_shortest()'s job for L1 |
| L0 and L1 are empty, L2 has one | take pick_priority()'s job for L2 |
| only L3 has ready jobs | take pick_fifo()'s job for L3 |
| no queue has a ready job | return 0, as now: the CPU waits |
top_level()pick_rr()pick_shortest()pick_priority()pick_fifo()Locks: see the three lock rules. The provided lines after your TODO lock the chosen job and check that it is still ready.
Moving between queues
Four provided hooks get one TODO each. All four run with p->lock already held (see the three lock rules). Leave their other lines as they are: they start the tests, record the log and end pause().
Moving down: charge()
sched_tick() calls charge() for the running job at every interrupt, after counting the tick in slice_used and cur_burst.
| 206 | // Charge the tick that just ended to a RUNNING process. |
| 207 | static void |
| 208 | charge(struct proc *p) |
| 209 | { |
| 210 | p->rticks++; |
| 211 | p->slice_used++; |
| 212 | p->cur_burst++; |
| 213 | logat(p, SEV_TICK, ticks - 1); |
| 214 | // TODO (MLFQ): count this tick against the allotment of p's queue. |
| 215 | if (0 /* TODO (MLFQ): p has used up its allotment and is not in Q3 */) { |
| 216 | // TODO (MLFQ): move p one queue down, to the end of that queue, and |
| 217 | // remember that p was just demoted. |
| 218 | schedlog(p, SEV_DEMOTE); |
| 219 | } |
| 220 | } |
| Situation | What should happen |
|---|---|
every tick charged to p | count it against p's allotment in its current queue |
| that allotment is now used up (2 ticks in L0, 4 in L1, 8 in L2) | p moves one queue down, to the end of it. Its used allotment starts over at 0, and it is marked as just demoted |
p is in L3 | it never moves down: L3 has no allotment |
p->allot_usedp->levelp->enter_tickp->demotedticksMLFQ_ALLOT0MLFQ_ALLOT1MLFQ_ALLOT2"Just demoted" tells should_preempt(), at the same interrupt, that p must go to the end of its new queue. In test demote, one job runs 16 ticks. Watch the allotment in the On the CPU box.
ev 1 A tick L0, the tick that used up the allotment, and already shows the new level: ev 2 A demote L1. The allotment counter starts over at 0 in L1.
A is still in its first burst: moving down does not end a burst. That is why its time left in L1 went below 0 before ev 6 A demote L2.
After 8 ticks in L2, ev 14 A demote L3. L3 has no allotment, so A stays there however long it runs. No other job is ready, so A never has to give up the CPU.
Moving up after waiting: sched_tick()
| 222 | // Called by clockintr() on CPU 0 right after ticks++. |
| 223 | void |
| 224 | sched_tick(void) |
| 225 | { |
| 226 | struct proc *p; |
| 227 | |
| 228 | for (p = proc; p < &proc[NPROC]; p++) { |
| 229 | acquire(&p->lock); |
| 230 | if (p->state == RUNNING) { |
| 231 | charge(p); |
| 232 | } else if (p->state == RUNNABLE) { |
| 233 | p->wait_ticks++; |
| 234 | if (0 /* TODO (MLFQ): p has waited too long in Q3 */) { |
| 235 | // TODO (MLFQ): move p up to the end of Q2. |
| 236 | schedlog(p, SEV_PROMOTE); |
| 237 | } |
| 238 | } |
| 239 | // wake up pause() and schedstart() sleepers whose time has come. |
| 240 | if (p->chan == &p->wake_tick && ticks >= p->wake_tick) { |
| 241 | p->chan = 0; |
| 242 | if (p->state == SLEEPING) |
| 243 | sched_wakeup(p); |
| 244 | } |
| 245 | release(&p->lock); |
| 246 | } |
| 247 | } |
| Situation | What should happen |
|---|---|
a ready job in L3 has now waited 20 ticks or more (MLFQ_STARVE) | it moves to the end of L2. Its waiting time goes back to 0 and its used allotment starts over |
| any other ready job | nothing: its waiting time was already counted |
p->levelp->wait_ticksp->enter_tickp->allot_usedticksMLFQ_STARVEMoving up after sleeping: sched_wakeup()
| 184 | // Make a SLEEPING process RUNNABLE. |
| 185 | void |
| 186 | sched_wakeup(struct proc *p) |
| 187 | { |
| 188 | p->state = RUNNABLE; |
| 189 | p->enter_tick = ticks; |
| 190 | p->wait_ticks = 0; |
| 191 | if (p->starting) { |
| 192 | p->starting = 0; |
| 193 | p->logenabled = 1; |
| 194 | schedlog(p, SEV_NEW); |
| 195 | return; |
| 196 | } |
| 197 | // TODO (MLFQ): coming back from sleep moves p up (see "Waking up" in |
| 198 | // the spec). |
| 199 | schedlog(p, SEV_WAKE); |
| 200 | } |
| Situation | What should happen |
|---|---|
p wakes up in L1, L2 or L3 | it moves up one queue |
p wakes up in L0 | it stays in L0 |
p->levelThe provided lines already put the woken job at the end of its queue.
The estimate after a burst: sched_sleep()
A burst ends only when the job calls pause(): not at a stop, not at a move down.
| 172 | // p is about to block: its CPU burst is over. |
| 173 | void |
| 174 | sched_sleep(struct proc *p) |
| 175 | { |
| 176 | if (p->starting) |
| 177 | return; |
| 178 | // TODO (MLFQ): update p->burst_est and reset the allotment p has used |
| 179 | // in its queue (see "Blocking" in the spec). |
| 180 | p->cur_burst = 0; |
| 181 | schedlog(p, SEV_SLEEP); |
| 182 | } |
| Situation | What should happen |
|---|---|
p's burst ends | new estimate = (ticks run in this burst + old estimate) / 2, rounded down. Its used allotment goes back to 0 |
p->burst_estp->cur_burstp->allot_usedYour lines run before the provided reset of cur_burst, so it still holds this burst's ticks. Test estimate:
ev 2 C wake L1), so it now competes in L1 with its new estimate, 4.
This is the step the test checks: C (4 left) runs before A (5 left). With the old estimate 8, A would run here.
Must it stop? should_preempt()
After the hooks, sched_timer() asks should_preempt(p) about the running job. It can now return a second kind of stop, PREEMPT_KEEP:
| 268 | // Should the running process p give up the CPU at this timer interrupt? |
| 269 | // Returns 0 (keep running), PREEMPT_KEEP or PREEMPT_REQUEUE. |
| 270 | static int |
| 271 | should_preempt(struct proc *p) |
| 272 | { |
| 273 | // TODO (MLFQ): follow the "Preemption" table in the spec. Also start a |
| 274 | // new time slice when p's slice is used up but p keeps running, and |
| 275 | // forget that p was just demoted. Hold p->lock while you use p's fields, but not |
| 276 | // while you call top_level() or a picker: they lock every process. |
| 277 | return 0; |
| 278 | } |
Use the first row that matches. "Comes before" means the queue's picking rule, ties included: an equal job with a smaller pid comes before p. "Slice used up" means p has run at least its current queue's slice since it was picked. L0 has a 1-tick slice and L2 a 2-tick slice. L1 and L3 have none. A move down does not reset slice_used, so a job can land in L2 already past its slice.
| Situation | What should happen |
|---|---|
a higher queue than p's has a ready job, and p is not just demoted | stop, keep its place: PREEMPT_KEEP |
a higher queue has a ready job, and p is just demoted | stop, go to the end: PREEMPT_REQUEUE |
p is just demoted and its new queue already has a ready job | PREEMPT_REQUEUE |
p is in L0, its 1-tick slice is used up, and another L0 job is ready | PREEMPT_REQUEUE |
p is in L1 and a ready L1 job comes before it (less time left, or the same and a smaller pid) | PREEMPT_REQUEUE |
p is in L2, its 2-tick slice is used up, and a ready L2 job comes before it (better effective priority, or the same and a smaller pid) | PREEMPT_REQUEUE |
| anything else, including every case in L3 | 0: keep running |
p keeps running and its slice is used up | also start a new slice |
| every case, whatever the result | p no longer counts as just demoted |
p->levelp->demotedp->slice_usedMLFQ_SLICE0MLFQ_SLICE2top_level()pick_shortest()pick_priority()Locks: should_preempt() is called without p->lock, so follow the three lock rules.
Hint Finding a job that comes before p
The best ready job in p's queue is what that queue's picker returns. It is never p, which is not ready. Compare it with p using your comparison function. A running job has waited 0 ticks, so its effective priority is its priority.
The yield change: PREEMPT_KEEP
| 280 | // Called from usertrap() and kerneltrap() on a timer interrupt. |
| 281 | void |
| 282 | sched_timer(void) |
| 283 | { |
| 284 | struct proc *p = myproc(); |
| 285 | int r = should_preempt(p); |
| 286 | |
| 287 | if (r == 0) |
| 288 | return; |
| 289 | acquire(&p->lock); |
| 290 | // TODO (yield): p gives up the CPU. Put it back in the ready queue: |
| 291 | // at the end of its queue for PREEMPT_REQUEUE, keeping its place for |
| 292 | // PREEMPT_KEEP. |
| 293 | schedlog(p, r == PREEMPT_REQUEUE ? SEV_REQUEUE : SEV_PREEMPT); |
| 294 | // TODO (yield): switch to the scheduler. |
| 295 | release(&p->lock); |
| 296 | } |
| Situation | What should happen |
|---|---|
PREEMPT_REQUEUE | as in q0–q3: p becomes ready, goes to the end of its queue, then sched(). The log shows requeue |
PREEMPT_KEEP | p becomes ready but keeps its old enter_tick, so it keeps its place, then sched(). The log shows preempt |
p->statep->enter_ticktickssched()sched_timer() already holds p->lock, as before. The difference shows only in L3: nothing is above L0, and L1 and L2 do not order by joining time. Test fifo:
should_preempt() table applies: PREEMPT_KEEP, logged as ev 2 A preempt L3. Your yield code leaves its enter_tick at 0.
A still counts as joined at tick 0, because it kept its place, so A runs before B. Had your yield sent A to the end (joined at tick 2), B would run here.
All public tests
Run one with ./grade demote, or mlfqcheck demote in xv6. The other 17, by rule:
All jobs in one queue: each test checks one picker and its pid tie-break.
Waking up lifts a job one queue, and waiting 20 ticks in L3 lifts it to L2.
Both count only the current burst, and a stop does not end it.
L1 stops at once for a shorter job, L2 at the end of its slice, any queue for a higher one.
The hidden seeds are larger: when all 20 pass, check a few columns of schedtest 7's chart by hand.
Pitfalls
- Treating
PREEMPT_KEEPlike a requeue. Infifo, expectedev 3 A run L3, but you seeev 3 B run L3. - Forgetting "just demoted". In
rr, A moves to L1 while L0 still has jobs, so it must go to the end:ev 4 A requeue L1. Without the flag, the first row of theshould_preempt()table matches and you printev 4 A preempt L1. - Counting all CPU ticks, not this burst. In
remaining-historyyou seeev 8 A run L1instead ofev 8 B run L1. - Aging with step 3. In
priority, B (priority 3) has waited 6 ticks: with step 2 it reaches 0 and beats A (priority 1),ev 6 A requeue L2. With step 3 it only ties A, and A keeps the CPU. - Calling
top_level()or a picker while holdingp->lock. No test prints a log:./gradesaysdid not finish, thenFAIL (no output; see grade.out), or alreadyxv6 did not reach the shellat boot, andgrade.outends withpanic: acquire.
When a test fails Each q4 test and its most likely bug
| Test | Likely cause |
|---|---|
demote | The allotment is not counted, uses the wrong limit for the queue, or does not start over after moving down. |
rr | L0 uses a 2-tick slice instead of 1, or a just-demoted job is not sent to the end. |
shortest | sched_pick() does not reach L1, or pick_shortest() was not copied. |
shortest-tie, priority-tie | A tie is broken by arrival instead of by pid. |
priority-pid-not-wait | A tie in effective priority is broken by waiting time instead of by pid. |
priority | Aging uses PRIO_AGE_STEP, or L2 checks for a better job before its slice is used up. |
slice | A job alone in L2 does not start a new slice, so it stops a tick early when B arrives. |
priority-age-tie | "Comes before" ignores the pid on equal effective priority. |
shortest-preempt | L1 never stops the running job, as in q1. |
estimate | The estimate is not updated on sleep, or the wake-up move is missing. |
estimate-history | The new estimate uses all ticks the job has run, not this burst. |
remaining-history | Time left subtracts all ticks the job has run, not this burst. |
progress | A stop resets the burst, or the preempted job loses its time already run. |
preempt-estimate | The estimate is updated when the job is stopped, not only when it sleeps. |
fifo | PREEMPT_KEEP moves the job to the end. |
preempt | A higher queue does not stop the running job, or PREEMPT_KEEP is handled wrong. |
starve | No promotion from L3, or the promoted job keeps its waiting time or used allotment. |
wake | The wake-up move is missing, or it moves more than one queue. |
wake-tail | The woken job does not join the end of its queue. |
Oops! What's Wrong?
./grade prints OK for each test that passes and a short report for each test that fails. Here is a real report from q0 with one bug: a job that gives up the CPU keeps its old place in the ready queue instead of going to the end.
$ ./grade late
late: FAIL (0/20) -- a job that arrives later joins the end of the queue
first difference at event 6:
ev 0 A tick L0
ev 1 A tick L0
ev 2 A requeue L0
expected: ev 2 B run L0
got: ev 2 A run L0
score: 0/20
A failed test reports only its first difference. Every line before it matched. Events are counted from 0, so event 6 is the seventh ev line. expected: is what the rules produce, got: is what your kernel printed, and above them are the three expected lines before the difference. The whole output of the last run, with any panic message, is in the file grade.out.
Example The whole run: one bug, four failed tests
The same bug fails every test in which a job gives up the CPU while another job is ready. Fix the first difference of one test, then run ./grade again.
$ ./grade
turns: FAIL (0/20) -- jobs in the ready queue take turns, RR_SLICE ticks each
first difference at event 7:
ev 0 A tick L0
ev 1 A tick L0
ev 2 A requeue L0
expected: ev 2 B run L0
got: ev 2 A run L0
alone: OK (20/20)
late: FAIL (0/20) -- a job that arrives later joins the end of the queue
first difference at event 6:
ev 0 A tick L0
ev 1 A tick L0
ev 2 A requeue L0
expected: ev 2 B run L0
got: ev 2 A run L0
wake: FAIL (0/20) -- a job that wakes up joins the end of the queue
first difference at event 11:
ev 3 A wake L0
ev 2 B tick L0
ev 3 B requeue L0
expected: ev 3 C run L0
got: ev 3 B run L0
slice: FAIL (0/20) -- a job alone starts a new time slice when its slice is used up
first difference at event 8:
ev 3 B new L0
ev 3 A tick L0
ev 4 A requeue L0
expected: ev 4 B run L0
got: ev 4 A run L0
score: 20/100
How to find my bug?
- Find the interrupt. A line
ev t …is printed at interrupt t, except atickline, which is printed at interrupt t+1. Inlate, the expected lineev 2 B run L0is at interrupt 2. - Go to that test's step-by-step view and move to that interrupt. Every public test has one in its task section, under "All public tests". The view of
lateis in How a Test Runs and What It Prints. - Read the boxes below the timeline and ask what your code did differently. At interrupt 2 of
late, the Ready box shows B first and A behind it, because A has just rejoined. The kernel that printedev 2 A runran A instead, so A kept its old place. Its yield code did not send A to the end of the queue (TODO (yield)).
The tool below does step 1 for you. Paste your output, and it finds the first difference and draws your timeline under the expected one.
Compare your output here
Run the test inside xv6 (make qemu, then schedcheck late, or mlfqcheck late on q4) and paste what it prints. Or paste the whole grade.out. The tool finds each test in your paste and compares it with that test's expected log, line by line, exactly as ./grade does, so it reports the same "first difference at event N". It works out the branch from the output: mlfqcheck means q4, and on q0–q3 the test names and descriptions tell the branches apart. If they cannot, it asks you to choose. It then draws your timeline under the expected one, with the first difference marked.
Symptoms and likely causes
A panic or a hang shows as did not finish within 15s, restarting xv6, then FAIL (no output; see grade.out). The end of grade.out says which.
| What you see | Likely cause |
|---|---|
Did not finish, and no panic in grade.out | sched_tick() is not called, so no job ever arrives (TODO (trap)). |
xv6 did not reach the shell within 60s, and grade.out ends with panic: kerneltrap | kerneltrap() calls sched_timer() when no job is running (TODO (trap)). |
xv6 did not reach the shell within 60s, no panic | Your picker never returns a job, so not even the shell can run. |
panic: acquire, in a test or already at boot (xv6 did not reach the shell) | A lock taken twice: a picker, pick_by() or top_level() called while holding p->lock, or the yield code acquiring p->lock again (the three lock rules). should_preempt() runs for every process, the shell included, so this can crash before any test starts. |
panic: sched RUNNING | The yield code calls sched() before p is RUNNABLE. |
panic: sched p->lock | The yield code released p->lock before sched(). sched_timer() releases it after sched() returns. |
panic: sched locks | More than one lock is held at sched(): some acquire in your code has no matching release. |
Compiler errors, then a Python Traceback | The kernel does not build. Fix the first compiler error. |
Failing tests differ at their first run line | The picker's order is wrong from the start, often a tie: when the task's rule rates two jobs the same, the smaller pid runs first. |
| A job that just gave up the CPU runs again at once | It did not go to the end of the queue: its enter_tick did not become ticks (the bug above). |
| The right lines, in a different order within one interrupt | Read ⚠️ Be careful!! ⚠️ (three facts about the order of log lines) first. If yours still differs, check where you call sched_tick() and sched_timer() (TODO (trap)). |
./grade compares only the lines that start with ev, so a debug line on its own is ignored. But a debug line printed while the test prints its log can land in the middle of an ev line and fail the test. Remove your printk() calls before you trust a score.Hidden seeds All public tests pass: what next?
The hidden seeds use larger workloads, with more ties and more blocking. Add your own test to tests[] in user/schedcheck.c (user/mlfqcheck.c on q4), run it by name, and check each decision against the rules by hand. Also run schedtest 7 and schedtest 42 and check the chart of which job ran in each tick. Files in user/ are replaced when grading, so your tests cannot change your score.
To stop the kernel and look at every process, see Using gdb.
Submit and Grading
This lab is worth 7 points of the course grade: 3 for the implementation and 4 for the lab quiz.
How the implementation is graded
The points per branch are in the table in Start here. Together they make 100, scaled to 3. On each branch:
- the public tests of
./gradegive 40%, and 10 hidden seeds give 60%. - a kernel panic or a hang gives 0 for that test or seed, and a build failure gives 0 for the whole branch.
- the TAs grade the last commit. Uncommitted changes are not graded.
Details Hidden seeds and time limits
Each hidden seed may run for up to 60 s, and a correct run takes about 15 s. Passing ./grade does not guarantee the hidden seeds: they may include larger workloads, ties and blocking that the public tests do not cover.
Files you must not change
The TAs use their own copies of ./grade and of these files, so your changes to them are lost:
user/(you may add your own tests there),mkfs/,Makefile,kernel/param.h,kernel/syscall.h,kernel/schedlog.hgrade,test-xv6.py,.devcontainer/,laband.gitattributes.
Also, do not add kernel source files, and do not change, add or remove any schedlog() or logat() call. These calls record the log lines that the tests compare.
Submit
- Commit your work on every branch. To check, run:
for b in q0 q1 q2 q3 q4; do git log -1 --oneline $b; done - Run
make cleanin the container to keep the zip small. - Zip the whole
os-xv6-lab-studentfolder, including the hidden.gitfolder (it holds all your branches), as<student_id>.zip. Run this in the folder that containsos-xv6-lab-student:zip -r <student_id>.zip os-xv6-lab-student # macOS / Linux tar -a -c -f <student_id>.zip os-xv6-lab-student # Windows (PowerShell) - Upload
<student_id>.zipto the eLearn assignment by 2026/11/10 23:59 (UTC+8).
Do not push your work to a public repository, for example a fork of the lab repository: everyone could see your code.
Generative AI
You may use generative AI tools (ChatGPT, Claude, Copilot, …) for this lab. You are responsible for every line you submit: the lab quiz asks you to trace the scheduler and explain your implementation. Do not share your code with other students.
Lab quiz (4 points)
The quiz asks you to trace a timer interrupt and the process states through the kernel code and to explain your own implementation: see Preparing for the Lab Quiz.
Credits
- The scheduling lab (its specs, starting code, tests and grading) was created by the TAs 嘉宏 Alvin, 又歆 Yuhsin and 佳晉 Johnny.
- The lab code is a modified version of xv6-riscv (MIT PDOS, MIT license).
- Every schedule on this page is drawn from the expected logs in each branch's
gradescript, and every decision in them is checked against the task's rules when the page is built. - The course illustrations of Nini and Niko are NTHU CS Operating Systems course material (Tony Chen / Yun-Chih Chen), licensed under CC BY 4.0.