xv6 schedulers

Lab created with ❤️ by:嘉宏 Alvin又歆 Yuhsin佳晉 Johnny

Part 0Start here

The lab has five tasks. Each task is on its own branch of the lab repository, with its own spec. In every task you write a scheduling policy in kernel/sched.c and connect it to the timer in kernel/trap.c. Do the tasks in order: Task 5 uses the pickers that you write in Tasks 1–4.

Deadline: 2026/11/10 23:59 (UTC+8). Upload your zip to the eLearn assignment by then (Part 10).

Set up the container

Every command in this lab runs in the course container. It has the RISC-V compiler, QEMU, gdb and the grading script. The TAs grade in the same container.

1. Install Docker (Docker Desktop on macOS and Windows).
2. Clone the repository and go into its folder:

   git clone https://github.com/GaGa55555LaLa/os-xv6-lab-student.git
   cd os-xv6-lab-student

3. Build the image. You do this once:

   docker build -t xv6-lab .devcontainer

4. Start the container in the repository folder. On macOS and Linux:

   docker run -it --rm --name xv6 \
       -u "$(id -u):$(id -g)" \
       -v "$PWD":/xv6 -w /xv6 \
       xv6-lab bash

   On Windows, in PowerShell:

   docker run -it --rm --name xv6 `
       -v "${PWD}:/xv6" -w /xv6 `
       xv6-lab bash

• Shortcut: ./lab shell builds the image if needed and starts the container. ./lab grade and ./lab make qemu run one command in it. These work on Linux, macOS, and in Git Bash or WSL on Windows.
• VS Code: open the folder and run "Dev Containers: Reopen in Container".
• Leave the container with exit. Your files stay in the repository folder on your computer.
• Windows: if ./grade prints env: $'python3\r': No such file or directory, commit your changes first, then run:

  git config core.autocrlf false
  git rm -r -q --cached .
  git reset -q --hard

Build, run and test

make qemu              # build and boot xv6 on one CPU; quit with Ctrl-a, then x
$ schedcheck           # in xv6: run every small test (mlfqcheck in Task 5)
$ schedcheck late      # run one test
$ schedtest 42         # a larger workload with seed 42, drawn as a Gantt chart

./grade                # in the container shell: build, run every test, compare
./grade late wake      # only some tests

One branch per task

git checkout q0                    # switch to Task 1
git commit -am "q0: round robin"   # commit your work on this branch
git show q0:kernel/sched.c         # read a file of another branch without switching
git show origin/q1:kernel/sched.c  # the same, for a branch you have not checked out yet

The prompt in the container shows the current branch, for example /xv6 (q0) $. Commit your work before you switch branches. The TAs grade the last commit on each branch; uncommitted changes are not graded.

Rules for every task

• Do not change these files; they are overwritten when grading: 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.
• Do not add kernel source files.
• Do not change, add or remove any schedlog() or logat() call. These calls record the events that the tests compare (Part 8).
• You may use generative AI tools. 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, and do not push it to a public repository.

Part 1Processes and their states

xv6 keeps every process in a fixed array, proc[NPROC], in kernel/proc.c. Each entry is a struct proc (kernel/proc.h). The field p->state holds the state of the process. An entry whose state is UNUSED is free. allocproc() finds a free entry and gives it the next pid, so a process created later has a larger pid.

The xv6 states have different names from the ones in the lecture:

Each transition is caused by a few kernel functions and records an event in the test log (Part 8). These six paths are the Trace Code paths that the lab quiz covers.

The ready queue

The specs talk about a "ready queue", but xv6 has no queue data structure. The ready queue is the set of entries in proc[] whose state is RUNNABLE. In q4, queue Qk is the set of RUNNABLE entries whose level is k.

The order of a queue is not stored either. It comes from fields of struct proc, for example enter_tick (the tick at which the process joined the ready queue) and pid. A picker such as pick_rr() returns the process at the head of a queue. It calls pick_by() in kernel/sched.c, which loops over proc[] and keeps the best entry so far. Part 8 shows a queue changing tick by tick.

The lab runs xv6 on one CPU: the Makefile fixes CPUS to 1. So at most one process is RUNNING at a time.

Part 2The timer interrupt

A trap stops the instructions that the CPU is running and jumps to a handler in the kernel. A system call, an exception (such as a page fault) and a device interrupt are all traps. The timer is a device that raises interrupts at times the kernel chooses.

Every timer interrupt reaches clockintr(), which adds 1 to the global counter ticks. One tick, the time between two timer interrupts, is the unit of time in this lab. Every count in the specs, such as a time slice, an allotment or a waiting time, is a number of ticks.

The register stvec holds the address of the trap handler. xv6 changes it when the CPU moves between user mode and kernel mode. So a timer interrupt reaches clockintr() by one of two paths, depending on what the CPU was doing. A test job burns CPU time by calling the system call cputicks() in a loop, so the interrupt can find it in user mode or in the kernel.

Two hooks: accounting, then the preemption check

The lab connects the timer to the scheduler with two functions in kernel/sched.c. You add the calls to them in kernel/trap.c (TODO (trap)).

• sched_tick() does the accounting for the tick that has just ended. It charges the tick to the running process, adds 1 to the waiting time of every RUNNABLE process, and wakes up every pause() that is due. It is called in clockintr(), right after ticks++.
• sched_timer() does the preemption check. It calls should_preempt(). If should_preempt() returns 0, the running process continues. Otherwise the process gives up the CPU. It is called in usertrap() and kerneltrap(), after devintr() has returned 2 (a timer interrupt).

Since clockintr() runs inside devintr(), the accounting always happens before the preemption check. Until sched_tick() is connected, ticks still grows but no pause() ever wakes up, so every test hangs. When the interrupt finds the CPU in the scheduler loop, myproc() returns 0: there is no process to check.

Part 3Locks

Kernel code often reads and changes data that other kernel code also uses, such as the fields of a process. Two pieces of code must not change the same data at the same time, or one of them may see it half updated. On a computer with several CPUs, two CPUs can run kernel code at once. Even on one CPU, a timer interrupt can stop kernel code in the middle of an update and run other kernel code. A lock makes such code take turns.

xv6 uses spin locks (struct spinlock, kernel/spinlock.c). acquire(&lk) waits until no other CPU holds lk, and then holds it. release(&lk) gives it back. The code between the two calls is a critical section: while one CPU is in it, no other CPU can enter a critical section of the same lock. For example, kfork() in kernel/proc.c makes a new process runnable like this:

acquire(&np->lock);
np->state = RUNNABLE;
np->enter_tick = ticks;
release(&np->lock);

Code that reads these fields also holds np->lock. So it sees either the old values or the new ones, never a RUNNABLE process with an old enter_tick.

The locks in this lab

The comments in struct proc (kernel/proc.h) say which lock protects each field.

Locks and interrupts

acquire() also turns interrupts off on the CPU, and they stay off until the CPU has released every lock it holds. So code that holds a spin lock cannot be interrupted by the timer. Without this, the timer handler could try to acquire a lock that the interrupted code already holds, and wait for it forever. For example, clockintr() acquires tickslock, which sys_pause() also holds while it reads ticks.

This lab runs on one CPU, but the locks still matter: the kernel checks how they are used and panics when a rule is broken. Part 5 shows the checks in sched(). Three rules follow:

• A spin lock cannot be acquired twice. If the CPU already holds a lock, acquire() of the same lock panics with acquire. The pickers and top_level() acquire the lock of every process in turn. So do not call them while you hold any p->lock.
• Release only a lock you hold. Otherwise release() panics with release.
• Read and write the fields of a process while you hold its lock.

Part 4Sleep, wakeup and exit

A process that must wait for an event sleeps: it sets its state to SLEEPING and gives up the CPU. A process gives up the CPU by calling sched(); Part 5 shows what happens inside it. When the event happens, other kernel code calls wakeup(chan). The channel chan is an address that names the event.

Sleeping takes two steps:

1. sleep_prepare(chan) stores chan in p->chan.
2. sleep() sets the state to SLEEPING and calls sched(), but only if p->chan is still set.

wakeup(chan) clears p->chan in every process that waits on chan, and calls sched_wakeup() for each one that is already SLEEPING. The two steps prevent a lost wakeup: if the event happens between the two steps, p->chan is already cleared, so sleep() returns at once instead of sleeping forever.

pause()

pause(n) (sys_pause() in kernel/sysproc.c) sets p->wake_tick to the current tick plus n and sleeps on the channel &p->wake_tick. At every tick, sched_tick() wakes up each process whose wake_tick has come. So a process in pause(n) sleeps for n ticks and wakes up once. The test programs use pause() to stand for I/O.

The scheduler hooks in sleep and wakeup

• sleep() calls sched_sleep(p) just before sched(). For the scheduler, this is the end of a CPU burst: the time a process runs until it blocks.
• sched_wakeup(p) sets the state to RUNNABLE, records the tick at which the process joins the ready queue, and resets its waiting time.
• Each test job starts with the system call schedstart(), which sleeps until the start tick of the job. When that sleep ends, sched_wakeup() records a new event instead of a wake event.

Exit

kexit() closes the files of the process, gives its children to init, wakes up its parent, sets its state to ZOMBIE, and calls sched(). It never returns. The parent's wait() later finds the ZOMBIE child and frees its entry in proc[].

Part 5The context switch

Each process has a kernel thread: a kernel stack (p->kstack) and a set of saved registers (p->context). When a process makes a system call or is interrupted, the kernel code runs on the kernel stack of that process. The CPU also has a scheduler thread, which runs scheduler() on its own stack. Its saved registers are in cpu->context.

swtch(old, new) in kernel/swtch.S saves the current registers in old and loads the registers in new, including the stack pointer sp and the return address ra. So the ret at the end of swtch returns into the other thread, at the point where that thread last called swtch.

xv6 never switches directly from one process to another. A process calls sched(), which switches to the scheduler thread. The scheduler thread selects the next process and switches to it. In the example below, process A calls pause() and goes to sleep, and process B, which slept earlier and has been woken up, runs next.

The loop in scheduler() (kernel/proc.c) is short:

for (;;) {
  intr_on();                       // a pending interrupt is taken here,
  intr_off();                      // then interrupts are off again
  if ((p = sched_pick()) != 0) {   // returns p locked and RUNNABLE
    p->state = RUNNING;
    p->slice_used = 0;
    p->wait_ticks = 0;
    schedlog(p, SEV_RUN);
    c->proc = p;
    swtch(&c->context, &p->context);
    c->proc = 0;                     // p has left the CPU
    release(&p->lock);
  } else {
    asm volatile("wfi");            // nothing to run: wait until an interrupt is pending
  }
}

Simplified from kernel/proc.c: the variable found, the line mycpu()->intena = 0; and the comments are left out.

A process that has never run has no earlier call to sched(). allocproc() sets its context.ra to forkret, so the first swtch() to it starts forkret(), which releases p->lock and returns to user space.

What sched() checks

sched() checks four conditions before it calls swtch(), and panics if one of them fails. These panics are the most common crashes in this lab.

Why is p->lock held during the switch? p->state and p->context must change together. If the lock were released before swtch(), the process would be RUNNABLE while its registers are only half saved, and another CPU could start to run it. So the lock is acquired in one thread and released in another, as the stepper shows.

Part 6Scheduler hooks and fields

The scheduling policy is in kernel/sched.c. The rest of the kernel calls it through a few functions, the hooks. The TODO comments in kernel/sched.c and kernel/trap.c on each branch mark exactly what to change. In every task you also add the calls to sched_tick() and sched_timer() in kernel/trap.c (TODO (trap)).

A picker returns its result without the lock. Before it uses the result, the caller must lock the process and check that its state is still RUNNABLE, as sched_pick() does.

The lab adds these fields to struct proc. All of them are protected by p->lock.

Part 7Your tasks

Before you write code for a task, answer its Think first questions. Open Where to look if you are stuck.

Part 8Reading the test output

schedcheck (mlfqcheck in q4) runs small fixed tests. Each test starts a few jobs, named A, B, C, … in the order of the test, and prints one line per scheduler event:

ev <tick> <job> <event> L<level>

<tick> counts from the start of the test. <level> is the queue of the job after the event; for a tick event, it is the queue the job ran in. The jobs are created in the order A, B, C, so A has the smallest pid. ./grade compares these lines with the expected ones.

One test, tick by tick

This is the expected log of the q0 test late, one timer interrupt at a time. The rule is round robin with a time slice of 2 ticks (Task 1). Jobs A and B arrive at tick 0 and need 6 ticks of CPU each. Job C arrives at tick 3 and needs 2 ticks.

Two details of the log are easy to misread:

• A tick event carries the tick that has just ended. sched_tick() records it at the next interrupt, as ticks - 1. Other events carry the tick in which they happen. So the lines from one interrupt can carry two different numbers, and a later line can show a smaller tick. For example, a q2 test prints ev 5 A new before ev 4 C tick. Both come from the interrupt that starts tick 5.
• The events that sched_tick() records at one interrupt follow the order of proc[]. sched_tick() visits the entries of proc[] from first to last. A requeue or preempt line, and the run line that follows it, always come after them. At tick 3 in the stepper, B's entry comes before C's, so B's tick line comes before C's new line.

A job whose last tick of work ends at an interrupt still needs a little CPU time to return to user space and call exit(). This takes much less than one tick, so no tick event comes before its exit event. If the job gave up the CPU at that interrupt, it must be picked again first. Its run and exit events then carry the same tick, as for C at tick 12.

schedtest draws a larger workload as a Gantt chart with one row per queue. The section schedtest output of q4-spec.md explains its format.

When a test fails

When a test fails, ./grade prints the first line where your log differs from the expected log, with the three expected lines before it. For example, with a bug in TODO (yield):

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

Events are counted from 0, so event 6 is the seventh ev line of the test. The whole output of the last run is in the file grade.out. The expected lines are in the EXPECTED block near the top of grade.

The viewer draws a log as a chart. Paste your output into the first box and, to compare, the expected lines from grade into the second; the quotes and commas are fine. It starts with the output of the buggy kernel above: A gets the CPU back right after each requeue, and B waits until A has exited.

Write your own test

The public tests are small. The hidden seeds use larger workloads with more ties and more blocking. To check a case that the public tests do not cover, add your own test to user/schedcheck.c (user/mlfqcheck.c in Task 5). Each test is one entry in the table tests[]:

An entry has a name, a description, the number of jobs (at most 4), and the jobs. Each job is { profile, arrive, level, priority, burst_est, nops, ops }:

• profile is a name for the job. The log calls the jobs A, B, C, D in the order of the entry.
• arrive is the tick, counted from the start of the test, at which the job leaves schedstart() and joins the ready queue.
• level, priority and burst_est are the starting values of these fields. level must be 0 in Tasks 1–4.
• ops lists what the job does, and nops is the length of the list. B(n) runs on the CPU for n ticks; P(n) calls pause(n).

Run it in xv6 with schedcheck and its name, and check the events against the rules by hand. Files in user/ are overwritten when grading, so your tests do not affect your grade.

Part 9Debugging

Symptoms

Print from the kernel

In the kernel, the print function is printk(). It takes a format string like printf(), and its output goes to the console. Remove your printk() calls before you run ./grade: kernel output mixes with the event lines that ./grade reads. Press Ctrl-p in the xv6 console to print the list of processes with their pids and states.

gdb: set up two terminals

gdb lets you stop the kernel at any function, look at the call chain and the fields of every process, and stop when a field changes. In the container, start gdb with gdb-multiarch, not gdb. The command gdb there debugs only programs for the CPU of your own computer (x86 or ARM) and cannot read the RISC-V kernel, although make qemu-gdb tells you to run gdb.

You need two terminals in the same container, one for xv6 and one for gdb. How to open the second one depends on how you started the container:

tmux splits one terminal into panes. Run tmux, then press Ctrl-b and then % to split the window into a left and a right pane. Press Ctrl-b and then an arrow key to move between panes. Press Ctrl-b and then [ to scroll back with the arrow keys, and q to stop scrolling. Type exit in a pane to close it.

gdb: a first session

1. In the first pane, run make qemu-gdb. QEMU starts xv6 and stops it before the first instruction. It waits for gdb.
2. In the second pane, in the same folder, run gdb-multiarch. gdb reads the file .gdbinit that make qemu-gdb has written, loads the kernel symbols and connects to QEMU. It stops at address 0x1000, the first instruction.
3. Type continue in gdb. xv6 boots in the first pane.
4. Run a test in the first pane, for example schedcheck late. Press Ctrl-c in gdb to stop xv6 at any time, and type continue to go on.

A session on q0 with a working solution (your line numbers will differ):

(gdb) break sched_timer
Breakpoint 1 at 0x80002760: file kernel/sched.c, line 232.
(gdb) continue
Continuing.

Breakpoint 1, sched_timer () at kernel/sched.c:232
232 {
(gdb) bt                                  # the call chain: the newest call first
#0  sched_timer () at kernel/sched.c:232
#1  0x0000000080002c2e in kerneltrap () at kernel/trap.c:156
#2  0x0000000080005b58 in kernelvec () at kernel/kernelvec.S:38
Backtrace stopped: frame did not save the PC
(gdb) p p
$1 = <optimized out>
(gdb) p cpus[0].proc->name                # the running process
$2 = "schedcheck\000\000\000\000\000"
(gdb) p cpus[0].proc->slice_used
$3 = 1
(gdb) p ticks
$4 = 65
(gdb) delete                              # remove all breakpoints
(gdb) continue

The interrupt came from kerneltrap(): the job was inside the system call cputicks(). The backtrace ends at kernelvec, where the trap entered the kernel; "Backtrace stopped" is normal there. The kernel is compiled with optimization, so gdb cannot show some local variables, such as p here. With one CPU, cpus[0].proc is always the running process (0 when no process runs).

gdb: list the processes

Save the lines below as procs.gdb in the repository folder. In gdb, type source procs.gdb once; after that, the command procs prints every process with its state and scheduling fields. Add other fields, such as priority or allot_used, in the same way.

# procs: print every process in use, with the scheduling fields.
define procs
  set $i = 0
  while $i < 64
    if proc[$i].state != UNUSED
      printf "%3d %-10s ", proc[$i].pid, proc[$i].name
      output proc[$i].state
      printf "  level=%d enter_tick=%d slice_used=%d wait_ticks=%d\n", proc[$i].level, proc[$i].enter_tick, proc[$i].slice_used, proc[$i].wait_ticks
    end
    set $i = $i + 1
  end
end

All the jobs of a test are named schedcheck (mlfqcheck in q4). Their pids are in the order A, B, C, …, so in the sessions below (the first test after boot) pid 4 is A, pid 5 is B and pid 6 is C. Use procs to find the pids in your own run.

gdb: recipes

A test hangs. Press Ctrl-c in gdb, then look at where the CPU is and at the processes. Here the kernel does not call sched_tick():

^C
Program received signal SIGINT, Interrupt.
scheduler () at kernel/proc.c:457
457     intr_on();
(gdb) p ticks
$1 = 109
(gdb) procs
  1 init       SLEEPING  level=0 enter_tick=1 slice_used=0 wait_ticks=0
  2 sh         SLEEPING  level=0 enter_tick=59 slice_used=0 wait_ticks=0
  3 schedcheck SLEEPING  level=0 enter_tick=59 slice_used=0 wait_ticks=0
  4 schedcheck SLEEPING  level=0 enter_tick=59 slice_used=0 wait_ticks=0
  5 schedcheck SLEEPING  level=0 enter_tick=59 slice_used=0 wait_ticks=0
  6 schedcheck SLEEPING  level=0 enter_tick=59 slice_used=0 wait_ticks=0
(gdb) continue
^C
(gdb) p ticks
$2 = 139

ticks grows, but every process is SLEEPING and the CPU waits in scheduler(). The jobs never leave schedstart(): nothing wakes them up at their start tick.

The kernel panics. Set a breakpoint on panic before you type continue. When the panic happens, bt shows the code that caused it. Here should_preempt() still holds p->lock when it calls pick_rr(). pick_by() then tries to acquire the lock of every process, including p:

(gdb) break panic
(gdb) continue
Breakpoint 1, panic (s=s@entry=0x80008048 "acquire") at kernel/printk.c:139
(gdb) bt
#0  panic (s=s@entry=0x80008048 "acquire") at kernel/printk.c:139
#1  0x0000000080000c28 in acquire (lk=lk@entry=0x80014020 <proc+1248>) at kernel/spinlock.c:26
#2  0x00000000800025d8 in pick_by (level=0, before=<optimized out>) at kernel/sched.c:99
#3  pick_rr (level=level@entry=0) at kernel/sched.c:121
#4  0x0000000080002782 in should_preempt (p=0x80014020 <proc+1248>) at kernel/sched.c:222
#5  sched_timer () at kernel/sched.c:236
#6  0x0000000080002b98 in usertrap () at kernel/trap.c:85
#7  0x0000003ffffff09c in ?? ()

Which code changes a field? watch -l stops whenever a memory location changes, and shows the old and the new value. Here it watches the time slice of the process that is running when you set the watchpoint. -l fixes the address, so it keeps watching that process after a switch:

(gdb) watch -l cpus[0].proc->slice_used
Hardware watchpoint 2: -location cpus[0].proc->slice_used
(gdb) continue
Hardware watchpoint 2: -location cpus[0].proc->slice_used

Old value = 1
New value = 2
charge (p=0x80014030 <proc+1248>) at kernel/sched.c:181
(gdb) bt
#0  charge (p=0x80014030 <proc+1248>) at kernel/sched.c:181
#1  sched_tick () at kernel/sched.c:194
#2  0x0000000080002a1e in clockintr () at kernel/trap.c:172
#3  0x0000000080002a92 in devintr () at kernel/trap.c:214
#4  0x0000000080002bcc in kerneltrap () at kernel/trap.c:148
#5  0x0000000080005b58 in kernelvec () at kernel/kernelvec.S:38

Which process does the picker return? Stop in sched_pick() and type finish. gdb runs to the end of the function and prints the return value. $ is the last value that gdb printed, and $$ the one before it.

(gdb) break sched_pick
(gdb) continue
Breakpoint 2, sched_pick () at kernel/sched.c:127
(gdb) finish
Run till exit from #0  sched_pick () at kernel/sched.c:127
0x0000000080001e24 in scheduler () at kernel/proc.c:461
461     if ((p = sched_pick()) != 0) {
Value returned is $3 = (struct proc *) 0x80014030 <proc+1248>
(gdb) p $->pid
$4 = 4
(gdb) p *$$                               # every field of that process
$5 = {lock = {locked = 1, ...}, state = RUNNABLE, ..., pid = 4, level = 0, priority = 5,
  burst_est = 2, cur_burst = 2, slice_used = 2, allot_used = 0, wait_ticks = 2,
  enter_tick = 66, ...}

Stop for one process only. Add a condition to a breakpoint. Here gdb stops only when job C (pid 6) wakes up:

(gdb) break sched_wakeup if p->pid == 6
(gdb) continue
Breakpoint 1, sched_wakeup (p=p@entry=0x80014370 <proc+2080>) at kernel/sched.c:158
(gdb) bt
#0  sched_wakeup (p=p@entry=0x80014370 <proc+2080>) at kernel/sched.c:158
#1  0x0000000080002746 in sched_tick () at kernel/sched.c:202
#2  0x0000000080002a1e in clockintr () at kernel/trap.c:172
...

gdb: commands for this lab

• A breakpoint in a function that runs at every tick, such as sched_tick(), stops at every tick. Add a condition, or remove the breakpoint when you are done with it.
• To stop, type quit in gdb. xv6 then keeps running; press Ctrl-a and then x in the first pane to stop QEMU.
• Run ./grade without gdb. It starts its own QEMU.

Part 10Grading and submission

This lab is worth 7 points of the course grade: 3 for the implementation and 4 for the lab quiz.

Implementation (3 points)

The five tasks add up to 100 points, scaled to 3. In each task, the public tests give 40% of the points and 10 hidden seeds give 60%.

• The TAs grade the last commit on each branch in your zip. Uncommitted changes are not graded.
• The TAs use their own copies of ./grade and of the files you must not change (Part 0).
• A build failure gives 0 for that task. A kernel panic or a hang gives 0 for that test or seed.
• Each hidden seed may run for up to 60 s. 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. Write your own tests, try schedtest with other seeds (for example 7 and 42), and check the Gantt charts against the rules by hand.

Lab quiz (4 points)

How to prepare for the quiz?

• Understand each policy. For every task, be ready to explain which process runs next, when the running process gives up the CPU, and why. Dry-run your scheduler on a small workload: take a test from schedcheck (or mlfqcheck), write down the events you expect tick by tick, and compare them with the real output in the log viewer of Part 8.
• Follow a timer interrupt all the way to sched(). Start from the hardware that raises the interrupt and go step by step until the CPU switches to the scheduler thread. At each step, know which function runs, what it does, and which locks are held.
• Trace the code yourself. For every item in the Trace Code section of q4-spec.md, open the files and follow the calls. This page explains the paths, but the quiz asks about the code.
• Compare the policies. Review the strengths and weaknesses of each scheduling algorithm from the lecture, then look for them in your own lab. schedtest builds the same workload from the same seed on every branch, so run schedtest 42 on q0 to q4 and compare the Gantt charts and the turnaround tables. Which jobs wait longest under each policy? How soon does a short job that arrives late finish? Which policy switches between jobs most often?

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.

AttributionCredits

• The scheduling lab (its specs, starting code, tests and grading) was created by the TAs 嘉宏 Alvin、又歆 Yuhsin、佳晉 Johnny.
• The lab code is a modified version of xv6-riscv (MIT PDOS, MIT license). All logs and gdb sessions on this page are real output from the lab code in the course container.
• 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.