Scheduling

This homework covers how xv6 decides which process runs next.

You can go through the following files:

• kernel/proc.c (scheduler(), sched(), yield())
• kernel/proc.h (struct proc, enum procstate)

Chapter 8 of the book (Scheduling) will help, especially sections 8.1–8.4.

xv6 uses a round-robin style scheduler. scheduler() runs in an infinite loop on each CPU: it scans the process table (proc[]), acquiring each process’s lock to check if its state is RUNNABLE. When it finds one, it switches to it. That process keeps running until it blocks, exits, or gets interrupted by a timer tick (which calls yield() to set state back to RUNNABLE and yield the CPU).

Questions

1. In scheduler(), what has to happen (which locks are acquired/released, and which state changes occur) between finding a runnable process and actually switching to it? What happens when that process gives up the CPU before the scheduler can pick another process?

2. If two processes are both runnable and one has been waiting much longer than the other, does xv6’s default scheduler take wait time into account? Why or why not? (Hint: Think about how process slots in proc[] are reused as processes exit).

DIY: your very own scheduler

Round-robin treats every runnable process similarly regardless of when it was created. First-Come-First-Served (FCFS) instead prioritizes whichever runnable process arrived earliest.

xv6 assigns each process a pid in increasing order as it is created (see allocproc() and nextpid in kernel/proc.c), so a lower pid means the process arrived earlier.

Task:

Modify scheduler() in kernel/proc.c so that, instead of running the first RUNNABLE process encountered during the array scan, it selects the RUNNABLE process with the smallest pid.

Set CPUS=1 in your Makefile to be able to observe the scheduling changes properly.

Testing Your Change:

1. Create a user program user/testfcfs.c that forks 3–4 child processes. Have each child print its pid multiple times (e.g., in a loop) and then exit.
2. Add $U/_testfcfs to UPROGS in Makefile.
3. Run your test program in QEMU:

   make qemu