ECE344 Fall 2026 (Sec 1) Lec 12 - Basic Scheduling

Overview

Jon Eyolfson connects xv6’s process memory layout and RISC-V trap handling to the mechanics of scheduling: interrupts save state, context switches restore another process, and the scheduler chooses what runs next. He compares FCFS, shortest job first, shortest remaining time first, and round robin, showing how waiting time, response time, fairness, and context-switch overhead trade off; in the round-robin example, a quantum of 3 produces 7 context switches.

Key takeaways

A RISC-V xv6 system call crosses from user to kernel mode through ecall and the trampoline: uservec saves registers in a trap frame, SATP switches to the kernel page table, and userret restores user state before sret.
Preemptive multitasking depends on timer interrupts: xv6 on QEMU uses roughly 10 interrupts per second, while typical systems may use about 250–1,000.
FCFS waiting time depends heavily on arrival order; the example with burst times 7, 4, 1, and 4 has an average of 7.5 time units in the 1-2-3-4 order.
SJF gives the lowest average waiting time when burst lengths are known, but actual future CPU demand is unavailable and repeated short arrivals can starve long jobs.
Round robin’s quantum controls the balance between responsiveness and overhead: a very short slice creates many context switches, while a slice longer than every job’s burst reduces the policy to FCFS.
A context switch is not free: saving and restoring process state and changing page tables can disturb the TLB and caches, so scheduling policies must account for switching overhead.

Chapters

0:00 Page-Table Permissions and xv6’s Address-Space Layout

The opening discussion distinguishes page-table validity checks from the permissions associated with the final translation.
xv6 maps a process’s program code starting at virtual address zero, followed by data, a guard page, a one-page stack, and a growing heap.

2:40 Guard Pages, Kernel-Mapped Pages, and Linux vDSO

xv6 uses an unmapped guard page below the stack so a stack overflow normally triggers a page fault; a sufficiently large overflow can jump past it.
xv6 maps the trampoline and trap frame at the top of every process address space; unlike Linux, xv6 also maps virtual address zero.
Linux keeps page zero unmapped and provides a vDSO mapping that can let libc implement calls such as clock_gettime without a full system call.

8:20 RISC-V System Calls, the Trampoline, and Trap Frames

An xv6 system-call stub places the call number in RISC-V register A7 and executes ecall; the CPU enters supervisor mode and saves the program counter in SEPC.
The trampoline’s uservec assembly saves user registers to the trap frame before switching SATP to the kernel page table.
The kernel handles the system call, places its return value in the saved A0 register, and returns through userret, which restores the user page table and registers before sret.

13:20 Timer Interrupts, Yielding, and Preemptive Multitasking

Timer interrupts use the same trap-entry path as system calls; xv6 on QEMU requests roughly 10 timer interrupts per second, compared with about 250–1,000 per second in typical systems.
A process can call yield to give up the CPU voluntarily, while a timer interrupt lets the kernel preempt it without its consent.
The switch routine saves kernel registers in a context structure so the process can resume later; the trap frame separately holds the user registers.

18:20 Context Switching, xv6’s Scheduler, and Scheduling Trade-Offs

A context switch from process A to B saves A’s state, selects a runnable process, restores B’s kernel context, and returns B to user mode.
xv6’s basic scheduler loops over processes and runs the next runnable one; the lecture distinguishes this scheduling policy from the dispatcher mechanism that performs a switch.
Context switches are overhead: changing page tables can disrupt the TLB and caches, and Linux reports voluntary and nonvoluntary switches in /proc/<pid>/status.
Scheduling can be evaluated by waiting time, response time, CPU utilization, throughput, and fairness; these goals can conflict.

27:30 FCFS Scheduling and Waiting-Time Calculations

First Come, First Served (FCFS) runs jobs in arrival order without preemption; for P1–P4 with burst times 7, 4, 1, and 4 arriving together, waiting times are 0, 7, 11, and 12.
That FCFS ordering gives an average waiting time of 7.5 time units; changing the tie-breaking arrival order can substantially reduce it.
Burst time means the CPU time a process needs to finish, and waiting time counts time spent runnable but not executing.

33:50 Shortest Job First and the Risk of Starvation

Nonpreemptive Shortest Job First (SJF) selects the runnable process with the smallest burst whenever the CPU becomes free.
In the example, P1 runs first because it is the only job at time zero; then the one-unit P3 runs before the four-unit P2 and P4.
SJF minimizes average waiting time when burst lengths are known, but real systems cannot know future execution times reliably.
A continuing stream of short jobs can starve a long job by repeatedly keeping it from being selected.

38:10 Shortest Remaining Time First Adds Preemption

Shortest Remaining Time First (SRTF) is preemptive SJF: when a job arrives, the scheduler compares its burst with the remaining time of the running job.
In the worked example, P1 has 5 units left when P2 arrives with 4, so P2 preempts it; P3 then preempts P2 because it needs only 1 unit.
For the example, the waiting times are P1 = 9, P2 = 1, P3 = 0, and P4 = 2, for a 3-unit average.

41:09 Round Robin Queues and a Three-Unit Quantum

Round robin gives each runnable process a fixed time slice, or quantum; a process that remains unfinished at the end goes to the back of the FIFO queue.
With a quantum of 3, newly arriving jobs join the queue, and an unfinished process returns to the back after its slice; a process that finishes early does not pass its unused time to another job.
In the example, the schedule has 7 process-to-process context switches, with response times of 0 for P1, 1 for P2, and 5 each for P3 and P4.

48:05 Choosing a Round-Robin Quantum and Reviewing the Algorithms

A quantum of 1 improves response time but causes many context switches; a quantum of 10 exceeds the example jobs’ burst times and effectively behaves like FCFS.
Round robin can provide fairness and good interactivity with a suitable quantum, but too many switches waste time and a large quantum weakens responsiveness.
Jon Eyolfson’s comparison: FCFS is simple, SJF can reduce average waiting but is impractical and can starve jobs, SRTF minimizes waiting with preemption, and round robin trades some waiting-time performance for responsiveness and fairness.

Summary, takeaways, and chapters were generated by AI from the video's transcript and may contain errors. The video belongs to its creator, Jon Eyolfson.