Operating Systems #7 — Putting an MLFQ Scheduler into xv6

The first project was replacing xv6's scheduler with an MLFQ — the same MLFQ from lecture, covered in #4.

Reading the existing xv6 scheduler

Before changing anything, you have to read what's there. xv6 uses Round Robin. A process that exceeds its time quantum goes to the back of the ready queue; if it issues I/O before the quantum expires it goes to the waiting queue and the next process is scheduled.

The implementation:

• There's a job queue called ptable, holding up to 64 (NPROC) processes at once. Inside it are a lock and proc[NPROC].
• Allocating a process means finding an UNUSED slot in the ptable and turning it into EMBRYO (the NEW state from lecture). Then fork() or userinit() makes it RUNNABLE (READY).
• On a timer interrupt, or when a process changes state, the CPU is handed over.

The handover path:

• yield() — marks the running process RUNNABLE and calls sched().
• sched() — runs a series of sanity checks and context-switches into scheduler().
• scheduler() — finds a RUNNABLE process in the ptable and context-switches into it. It loops forever and never returns.

xv6 uses ticks as its time quantum and walks the ptable in index order looking for RUNNABLE processes, which makes it Round Robin. (Though if a process created earlier dies and becomes UNUSED, the ordering probably isn't perfectly preserved.)

The states are UNUSED (no process here), EMBRYO (new), SLEEPING (not eligible for scheduling, like waiting), RUNNABLE (ready), RUNNING, and ZOMBIE.

xv6's original struct proc — the thing we start bolting fields onto.

Dropping in cprintf calls made the flow visible. After userinit there's one RUNNABLE process; mpmain() prints cpu %d: starting and the scheduler runs for the first time. Once the $ prompt appears — the moment the shell starts reading input — the scheduler spins forever. Nothing has been launched yet so there are no RUNNABLE processes, which is the normal state of affairs.

The scheduler right after boot; once the prompt appears it spins on an empty loop.

The MLFQ to build

Three queues: L0, L1, L2.

• Lower number means higher priority. Every process starts in L0.
• Queue Ln's time quantum is 2n + 4 ticks — how long a process may stay in that queue.
• L0 and L1 use Round Robin; L2 uses priority scheduling.
  • L2 runs the process with the lower priority number (i.e. higher priority) first.
  • Ties are broken by FCFS.

So if A, B, C, D arrive in order, they all go into L0 and get scheduled every tick (the timer interrupt interval, about 10ms by default in xv6). A, B, C, D, A, B, C, D, A, B, C, D, A (down to L1), B (down to L1), C (down to L1), D (down to L1).

Implementation

New fields on struct proc

• priority — used for comparison in L2.
• time — this process's time quantum (accumulated ticks).
• level — which queue it's in. To mark the schedulerLock state, a locked process gets -1.
• enterL2 — records the order in which it entered L2, needed for FCFS when priorities tie.

The fields added to struct proc.

System calls

• yield() — called on a timer interrupt. Increments time and checks whether the queue's quantum has passed. If so, it moves the process to another queue (L0, L1) or changes its priority (L2). When moving into L2 it initializes enterL2 for FCFS, taking the value from a global counter that tracks order.
• getLevel() — returns the level of the queue the process is in.
• setPriority(int pid, int priority) — sets the priority of that pid.
• schedulerLock(int password) — makes this process scheduled first. On the correct password it resets the global tick to 0 with no priority boosting. On the wrong one it prints the pid, time quantum, and queue level.
• schedulerUnlock(int password) — stops the preferential scheduling. Only the process that called schedulerLock may call it — only whoever set the lock may release it. On the correct password it restores level, time quantum, and priority to their initial values; on the wrong one it prints process information the same way.

yield() — checks the quantum and moves the process between queues.

schedulerLock().

schedulerUnlock() — only the process that set the lock may release it.

Locking through an interrupt

schedulerLock and schedulerUnlock are also callable through interrupts 129 and 130. I added gates in tvinit with the DPL opened so they're reachable from user mode, and added the matching cases in the trap function.

Gates for interrupts 129 and 130 added in tvinit.

The matching cases in trap().

In #6 I'd noted that you can create a new interrupt in an empty IDT slot; this is where that gets used. That's when it clicked that adding a system call and opening another gate in the IDT are essentially the same act.

allocproc

Turn an UNUSED process into EMBRYO and initialize the new fields; priority is initialized through setPriority. This is used by userinit() and fork().

scheduler

This is the heart of it.

• for(;;) loops forever and never returns.
• Inside, for(p = ptable.proc; p < &ptable.proc[NPROC]; p++) gives Round Robin.
• Each time a new running candidate is needed, targetLevel() finds the level to target — the minimum queue level among RUNNABLE processes.

scheduler() — walking the ptable for the next candidate.

targetLevel() — the minimum queue level among RUNNABLE processes.

Then it branches on that level.

• Target level -1 — meaning some process holds schedulerLock and is RUNNABLE. Find it in the ptable. Doing p-- here so the same slot is re-examined keeps it the running candidate until the lock is released. And even after the lock is released, the p-- means it runs first when priority boosting or the unlock happens — the effect is that it goes to the very front of L0.
• Target level 0 or 1 — search among the processes in that queue. On a timer interrupt or when the running process terminates, the next candidate is found in order, which is Round Robin.
• Target level 2 — different, since it's priority-based. targetID() gives the target pid and the loop checks p->pid == targetID(). targetID() finds the minimum priority first, then among those the earliest arrival, and returns its pid.

targetID() — lowest priority number, ties broken by arrival order.

Priority boosting

When the global tick hits 100, allReset performs priority boosting, restoring the values that allocproc set.

allReset() — priority boosting at global tick 100.

Results

I checked by creating several processes with fork.

RUNNABLE processes take turns on each timer interrupt. With pid 3 at level 1 the processes in L0 run first, and in L2 only the process with the lower priority number (higher priority) runs.

RUNNABLE processes taking turns on each timer interrupt.

At global tick 100, priority boosting fires and the values reset.

Priority boosting returning level and time to their initial values.

With schedulerLock set, only the locking process runs and the others don't.

The schedulerLock test — only the locking process runs.

When the locking process sleeps, though, another RUNNABLE process runs. I confirmed pid 4 at level 1 running while pid 3 at level -1 was sleeping.

A level 1 process running while the level -1 process sleeps.

After schedulerUnlock, level goes back to 0 and time to 0, and the child process runs again.

The unlock lands around i = 50, resetting level and time.

Calling through int 129 and int 130 hits the cprintf as expected.

Trouble shooting

I had the time quantum wrong

This is what cost me the most time. A time quantum is the maximum time a process runs in one go — except that the timer interrupt changes the story.

"Time quanta of 4, 6, 8 ticks" in the spec means 4, 6, 8 × 10ms. But timer interrupts keep firing during that window, and each one picks the next process by that queue's policy. Without timer interrupts, not finishing within 8ms would mean dropping to the next queue. With them, each interrupt hands the CPU to the next process, and if the quantum hasn't expired the handed-off process is still in the queue. Only when its accumulated time in the queue reaches the quantum does it drop down.

How the quantum relates to the timer interrupt: only accumulated time in the queue pushes a process down.

Sleeping processes become runnable on a timer interrupt

I noticed processes that were sleeping turning runnable after a timer interrupt. It's because sleeping sets the tick as chan, and the timer interrupt wakes every process whose chan is the tick. Since sleeping itself only counts while the process runs, I decided this is natural enough.

There is a wrinkle: a timer interrupt can fire while a process is being marked sleeping, incrementing time. Level -1 doesn't use time so it doesn't matter there, but the other levels need care.

myproc() can be null

Calling myproc() under case T_IRQ0 + IRQ_TIMER panicked. At startup, and whenever there's no RUNNABLE process, myproc() returns 0 (null), and myproc()-> then reaches into a process that isn't there. Guarding with if (myproc() != 0) fixed it.

This was the most expensive bug of the project. I'd originally been building a separate Queue struct, kept writing without checking as I went, hit a kernel panic at some point, and couldn't find the cause — so I reimplemented it the way described above. Only later did I learn the cause was calling myproc in the timer interrupt path in trap.c. I still want to go back and do the separate queue version.

A panic from where I put cprintf

Putting a cprintf under struct proc to check the sleeping state produced panic: acquire. Suspecting a lock problem, I moved it, and that fixed it.

Things I picked up along the way

• Calling a system call from user mode invokes a registered wrapper function, which switches mode and then calls the function you actually wanted. Called from kernel mode, the wrapper is skipped and the function is called directly.
• sleep() calls sched() directly without going through yield. That is, it doesn't wait for a timer interrupt before finding the next process to run.