Lab 1 Guide

Animation: Dogdog in a chef hat rolls Capoo flat like dough with a rolling pin

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!

Photo of Prof. Yun-Chih ChenProf. Yun-Chih Chen

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.

TaskBranchPolicyWho runs nextStops at a timer interrupt when…Points
1q0Round robinjoined the ready queue firstits 2-tick slice is used up and another job is ready10
2q1Shortest estimated time leftleast time leftnever10
3q2Priority with agingbest priority, improved by waitinga ready job comes before it10
4q3First come, first servedjoined the ready queue firstnever10
5q4Multilevel feedback queuehighest non-empty of 4 queuesa table of rules60

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.

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
EventMeaning
newThe job arrives and joins the ready queue.
runThe job your picker chose gets the CPU.
tickThe tick that just ended is charged to the running job.
requeueThe running job gives up the CPU and goes to the end of the ready queue.
sleepThe running job calls pause().
wakeThe job's pause is over, and it joins the ready queue.
exitThe 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:

  1. A tick line looks back. The line for tick 0 is printed at interrupt 1, when tick 0 has ended: ev 0 A tick appears after ev 0 A run.
  2. 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 prints ev 3 A wake before ev 2 B tick, because A comes before B in the table.
  3. 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, exit follows at once: in test alone, ev 4 A tick then ev 5 A exit. If it was stopped at that interrupt, it has to be picked once more: run, then exit, 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:

Entrystateenter_tickPlace 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:

kernel/sched.cLines 91 to 106 in q0 · pick_by()
91// The best RUNNABLE process in queue level, where before(a, b) says
92// whether a should run before b.
93static __attribute__((unused)) struct proc *
94pick_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 earliest enter_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.

FieldMeaningSet byBranches
stateRUNNING, RUNNABLE, SLEEPING, …provided code, and you when a job gives up the CPUall
pidprocess id, used to break tiesprovidedall
enter_tickwhen it joined the ready queueprovided code when a job arrives or wakes, and you when it goes to the endq0, q3, q4
slice_usedticks run since it was last pickedprovided code (+1 per tick, 0 when picked), and you when a new slice startsq0, q4
burst_est, cur_burstthe estimated length of its CPU burst, and the ticks it has run in this burstsee q1q1, q4
priority, wait_ticksits priority (0 is the best), and the ticks it has spent ready since it last ransee q2q2, q4
level, allot_used, demotedits queue in q4, and two counters for moving between queuessee q4q4

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:

kernel/trap.cLines 165 to 180 in q0 · clockintr()purple = TODO
165void
166clockintr()
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:

kernel/trap.cLines 81 to 88 in q0 · usertrap()purple = TODO
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
kernel/trap.cLines 151 to 159 in q0 · kerneltrap()purple = TODO
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,
SituationWhat should happen
clockintr(): a tick has passedcall sched_tick() (provided: charges the tick, counts waiting, wakes sleepers)
usertrap(): which_dev is 2call sched_timer() (provided: asks your should_preempt())
kerneltrap(): which_dev is 2 and a job is runningcall sched_timer()
kerneltrap(): which_dev is 2 but no job is runningnothing: there is no job to stop
Why "no job is running" happensWhen no job is ready, the CPU waits inside the kernel with no current process, and a timer interrupt arrives there too. Then 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.
If you forget sched_tick()No tick is ever charged and no job ever arrives, so every test hangs, and ./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:

kernel/sched.cLines 212 to 227 in q0 · sched_timer()purple = TODO
212// Called from usertrap() and kerneltrap() on a timer interrupt.
213void
214sched_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}
SituationWhat should happen
should_preempt() returned PREEMPT_REQUEUEp 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.

RuleWhere it appliesIf 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 pickerpanic: 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 hookspanic: 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

q0Task 110 points5 public testsyou write: pick_rr(), should_preempt()
The job that joined the ready queue first runs next. It keeps the CPU for at most a 2-tick time slice, then goes to the end of the queue if another job is ready.

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():

kernel/sched.cLines 108 to 115 in q0 · pick_rr()purple = TODO
108// In ready-queue order; the running process gives up the CPU when its
109// time slice is used up (see should_preempt()).
110struct proc *
111pick_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 bWhat should happen
a joined the ready queue at an earlier tick than ba runs before b
a and b joined at the same tickthe one with the smaller pid runs first
no job is ready at allthe 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.

kernel/sched.cLines 203 to 210 in q0 · should_preempt()purple = TODO
203// Should the running process p give up the CPU at this timer interrupt?
204static int
205should_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}
SituationWhat should happen
p has not used up its slicekeep running: return 0
p has used up its slice, and another job is readystop: return PREEMPT_REQUEUE
p has used up its slice, and no other job is readykeep running: return 0, and start a new slice (slice_used back to 0)
p->slice_usedRR_SLICEpick_rr()p->lock

To learn whether another job is ready, you can ask your own picker. p is RUNNING, not RUNNABLE, so the picker never returns p itself.

Why the third row mattersThe provided code starts a new slice only when the picker chooses a job. A job that keeps the CPU is not picked again, so nothing else resets its slice.

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.

All public tests

Pitfalls

  • No new slice. In slice, A must keep the CPU at interrupt 3 (ev 3 A tick). If your output has ev 3 A requeue there, the third row of the table never reset slice_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 requeue followed by ev 2 A run means 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 call pick_rr() while holding p->lock, the kernel panics before the test can print its log: ./grade says did not finish within 15s, then FAIL (no output; see grade.out), and grade.out ends with panic: acquire. Because should_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 run means your tie goes the wrong way.
When a test fails What each q0 test catches
TestWhat it checksLikely cause when it fails
turnsThree 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.
aloneA job alone is never stopped.should_preempt() stops when the slice is used up without asking whether another job is ready.
lateA 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.
wakeA 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.
sliceA 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

q1Task 210 points5 public testsyou write: pick_shortest(), should_preempt()
The ready job with the least estimated time left runs next. Once it runs, it keeps the CPU until it sleeps or exits.

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:

kernel/sched.cLines 108 to 114 in q1 · pick_shortest()purple = TODO
108// The process with the least estimated time left in its CPU burst.
109struct proc *
110pick_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 bWhat should happen
a has less time left than ba runs before b
a and b have the same time leftthe one with the smaller pid runs first, even if the other has waited longer
no job is ready at allthe 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()

kernel/sched.cLines 202 to 209 in q1 · should_preempt()purple = TODO
202// Should the running process p give up the CPU at this timer interrupt?
203static int
204should_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.

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 wake at interrupt 1, B and C both joined at tick 0, and C must run. ev 1 B run means your before() still orders by when jobs joined, as in round robin.
  • Breaking ties by arrival. In tie-arrival at interrupt 3, B and C both have 3 left. C arrived first, but B runs because its pid is smaller. ev 3 C run means your tie uses enter_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 requeue means should_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 requeue means you stopped B when its time left reached 0.
When a test fails What each q1 test catches
TestWhat it checksLikely cause when it fails
shortestThe 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-preemptA shorter job that arrives does not stop the running one (ev 4 B run).should_preempt() returns something other than 0.
tieEqual estimates: the smaller pid runs first (ev 0 A run).The tie in before() is missing or reversed.
tie-arrivalEqual estimates: the smaller pid wins over the earlier arrival (ev 3 B run).The tie uses enter_tick instead of the pid.
wakeA 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

q2Task 310 points7 public testsyou write: pick_priority(), should_preempt()
The ready job with the best effective priority runs, and waiting improves a job's effective priority. The running job stops as soon as a ready job comes before it.

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

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.

kernel/param.hLines 20 to 20 in q2
20#define PRIO_AGE_STEP 3 // +1 priority per this many waiting ticks

A job with priority 5, after waiting:

Ticks waited023620
Steps gained00126
Effective priority55430 (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).

kernel/sched.cLines 108 to 114 in q2 · pick_priority()purple = TODO
108// The process with the highest priority after aging.
109struct proc *
110pick_priority(int level)
111{
112 // TODO (q2): the RUNNABLE process in queue level that runs next.
113 return 0;
114}
SituationWhat should happen
a has the smaller effective prioritya goes first
Same effective priority, a has the smaller pid, even if b waited longer or arrived earliera goes first
p->priorityp->wait_ticksPRIO_AGE_STEPp->pid

Lock 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.

kernel/sched.cLines 202 to 209 in q2 · should_preempt()purple = TODO
202// Should the running process p give up the CPU at this timer interrupt?
203static int
204should_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}
SituationWhat should happen
No other job is readykeep running: return 0
The picker's job has a smaller effective priority than p's priorityp stops: return PREEMPT_REQUEUE
The picker's job has the same effective priority and a smaller pid than pp stops: return PREEMPT_REQUEUE
The picker's job has a larger effective priority, or the same one and a larger pidkeep running: return 0
pick_priority()p->priorityp->pidPREEMPT_REQUEUE

Lock 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.

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-preempt a tie must stop B at interrupt 10. Symptom: ev 10 B tick where ev 10 B requeue is 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-wait A runs at interrupt 6, and in tie-arrival B runs at interrupt 2 before C, which arrived earlier. Symptom: the other job's run line.
  • Writing the aged value into priority. In age-tie-preempt A 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
TestWhat it catchesLikely bug
any, with panic: acquirethe lock rulepick_priority() called while holding p->lock, or a lock taken inside the comparison
prioritythe order of plain prioritiesthe comparison is reversed (larger number first), or the picker returns 0
preemptstopping for a better job that arrivesshould_preempt() still always returns 0
agingwaiting improves a job, and the running job wins a tie with the smaller pidno aging, the division in the wrong place, or stopping on every tie
tiethe smaller pid on a full tiethe comparison says yes when both jobs are equal, so the larger pid wins
tie-arrivalpid, not arrival, breaks tiesties broken by enter_tick
age-tie-preemptan aged tie stops the running job, which is then back to its own prioritystopping only for a strictly better job, or writing the aged value into priority
age-pid-not-waitpid, not waiting time, breaks tiesties broken by wait_ticks

q3 · First come, first served

q3Task 410 points4 public testsyou write: pick_fifo(), should_preempt()
The job that joined the ready queue first runs next, and ties go to the smaller pid. The running job keeps the CPU until it sleeps or exits.

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()

kernel/sched.cLines 108 to 114 in q3 · pick_fifo()purple = TODO
108// The process that has been in the ready queue the longest.
109struct proc *
110pick_fifo(int level)
111{
112 // TODO (q3): the RUNNABLE process in queue level that runs next.
113 return 0;
114}
SituationWhat should happen
a joined the ready queue earlier than ba goes first
Both joined at the same tick, a has the smaller pida goes first
p->enter_tickp->pid

Lock rule: take no lock in your comparison (see the three lock rules).

Must it stop? should_preempt()

kernel/sched.cLines 202 to 209 in q3 · should_preempt()purple = TODO
202// Should the running process p give up the CPU at this timer interrupt?
203static int
204should_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.

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
TestWhat it catchesLikely bug
arrivalarrival order, and a tie between two arrivalsthe comparison is reversed, ignores enter_tick, or lets the larger pid win a tie
no-preemptno stop at a timer interruptshould_preempt() copied from q0
wakea woken job goes to the endordering by pid, not by enter_tick
tiethe smaller pid on a full tiethe 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 pickers
Four queues, each with its own picker. The highest queue with a ready job always runs first. A job moves down when it uses up its allotment in a queue, and up when it wakes from sleep or has waited 20 ticks in L3.

Jobs 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.

kernel/param.hLines 20 to 27 in q4
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:

EventMeaning
demoteThe running job used up its allotment and moved one queue down.
promoteA ready job waited 20 ticks in L3 and moved up to L2.
preemptThe 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:

kernel/sched.cLines 148 to 166 in q4 · sched_pick()purple = TODO
148// Choose the next process to run. Returns it locked and RUNNABLE, or 0.
149struct proc *
150sched_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}
SituationWhat should happen
L0 has a ready jobtake the job pick_rr() returns for L0
L0 is empty, L1 has a ready jobtake pick_shortest()'s job for L1
L0 and L1 are empty, L2 has onetake pick_priority()'s job for L2
only L3 has ready jobstake pick_fifo()'s job for L3
no queue has a ready jobreturn 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.

kernel/sched.cLines 206 to 220 in q4 · charge()purple = TODO
206// Charge the tick that just ended to a RUNNING process.
207static void
208charge(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}
SituationWhat should happen
every tick charged to pcount 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 L3it 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.

Moving up after waiting: sched_tick()

kernel/sched.cLines 222 to 247 in q4 · sched_tick()purple = TODO
222// Called by clockintr() on CPU 0 right after ticks++.
223void
224sched_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}
SituationWhat 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 jobnothing: its waiting time was already counted
p->levelp->wait_ticksp->enter_tickp->allot_usedticksMLFQ_STARVE

Moving up after sleeping: sched_wakeup()

kernel/sched.cLines 184 to 200 in q4 · sched_wakeup()purple = TODO
184// Make a SLEEPING process RUNNABLE.
185void
186sched_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}
SituationWhat should happen
p wakes up in L1, L2 or L3it moves up one queue
p wakes up in L0it stays in L0
p->level

The 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.

kernel/sched.cLines 172 to 182 in q4 · sched_sleep()purple = TODO
172// p is about to block: its CPU burst is over.
173void
174sched_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}
SituationWhat should happen
p's burst endsnew estimate = (ticks run in this burst + old estimate) / 2, rounded down. Its used allotment goes back to 0
p->burst_estp->cur_burstp->allot_used

Your lines run before the provided reset of cur_burst, so it still holds this burst's ticks. Test estimate:

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:

kernel/sched.cLines 268 to 278 in q4 · should_preempt()purple = TODO
268// Should the running process p give up the CPU at this timer interrupt?
269// Returns 0 (keep running), PREEMPT_KEEP or PREEMPT_REQUEUE.
270static int
271should_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.

SituationWhat should happen
a higher queue than p's has a ready job, and p is not just demotedstop, keep its place: PREEMPT_KEEP
a higher queue has a ready job, and p is just demotedstop, go to the end: PREEMPT_REQUEUE
p is just demoted and its new queue already has a ready jobPREEMPT_REQUEUE
p is in L0, its 1-tick slice is used up, and another L0 job is readyPREEMPT_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 L30: keep running
p keeps running and its slice is used upalso start a new slice
every case, whatever the resultp 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

kernel/sched.cLines 280 to 296 in q4 · sched_timer()purple = TODO
280// Called from usertrap() and kerneltrap() on a timer interrupt.
281void
282sched_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}
SituationWhat should happen
PREEMPT_REQUEUEas in q0–q3: p becomes ready, goes to the end of its queue, then sched(). The log shows requeue
PREEMPT_KEEPp 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:

All public tests

Run one with ./grade demote, or mlfqcheck demote in xv6. The other 17, by rule:

One queue at a time: the copied pickers

All jobs in one queue: each test checks one picker and its pid tie-break.

Moving up

Waking up lifts a job one queue, and waiting 20 ticks in L3 lifts it to L2.

The estimate and time left

Both count only the current burst, and a stop does not end it.

Stopping the running job

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_KEEP like a requeue. In fifo, expected ev 3 A run L3, but you see ev 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 the should_preempt() table matches and you print ev 4 A preempt L1.
  • Counting all CPU ticks, not this burst. In remaining-history you see ev 8 A run L1 instead of ev 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 holding p->lock. No test prints a log: ./grade says did not finish, then FAIL (no output; see grade.out), or already xv6 did not reach the shell at boot, and grade.out ends with panic: acquire.
When a test fails Each q4 test and its most likely bug
TestLikely cause
demoteThe allotment is not counted, uses the wrong limit for the queue, or does not start over after moving down.
rrL0 uses a 2-tick slice instead of 1, or a just-demoted job is not sent to the end.
shortestsched_pick() does not reach L1, or pick_shortest() was not copied.
shortest-tie, priority-tieA tie is broken by arrival instead of by pid.
priority-pid-not-waitA tie in effective priority is broken by waiting time instead of by pid.
priorityAging uses PRIO_AGE_STEP, or L2 checks for a better job before its slice is used up.
sliceA 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-preemptL1 never stops the running job, as in q1.
estimateThe estimate is not updated on sleep, or the wake-up move is missing.
estimate-historyThe new estimate uses all ticks the job has run, not this burst.
remaining-historyTime left subtracts all ticks the job has run, not this burst.
progressA stop resets the burst, or the preempted job loses its time already run.
preempt-estimateThe estimate is updated when the job is stopped, not only when it sleeps.
fifoPREEMPT_KEEP moves the job to the end.
preemptA higher queue does not stop the running job, or PREEMPT_KEEP is handled wrong.
starveNo promotion from L3, or the promoted job keeps its waiting time or used allotment.
wakeThe wake-up move is missing, or it moves more than one queue.
wake-tailThe 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?

  1. Find the interrupt. A line ev t … is printed at interrupt t, except a tick line, which is printed at interrupt t+1. In late, the expected line ev 2 B run L0 is at interrupt 2.
  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 late is in How a Test Runs and What It Prints.
  3. 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 printed ev 2 A run ran 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.

No output yet? Try a real failing run first.

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 seeLikely cause
Did not finish, and no panic in grade.outsched_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: kerneltrapkerneltrap() calls sched_timer() when no job is running (TODO (trap)).
xv6 did not reach the shell within 60s, no panicYour 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 RUNNINGThe yield code calls sched() before p is RUNNABLE.
panic: sched p->lockThe yield code released p->lock before sched(). sched_timer() releases it after sched() returns.
panic: sched locksMore than one lock is held at sched(): some acquire in your code has no matching release.
Compiler errors, then a Python TracebackThe kernel does not build. Fix the first compiler error.
Failing tests differ at their first run lineThe 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 onceIt 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 interruptRead ⚠️ 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)).
Remove debug output./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 ./grade give 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.h
  • grade, test-xv6.py, .devcontainer/, lab and .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

  1. Commit your work on every branch. To check, run:
    for b in q0 q1 q2 q3 q4; do git log -1 --oneline $b; done
  2. Run make clean in the container to keep the zip small.
  3. Zip the whole os-xv6-lab-student folder, including the hidden .git folder (it holds all your branches), as <student_id>.zip. Run this in the folder that contains os-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)
  4. Upload <student_id>.zip to 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 grade script, 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.