CFS and Signals

Why This Matters

Every real operating system must answer two questions that xv6 only partially addresses: How do we share the CPU fairly across many different kinds of processes? and How do we let the kernel notify a running process about an event without the process having to ask? Linux's Completely Fair Scheduler (CFS) solves the first; the Unix signal mechanism solves the second. Understanding both gives you the conceptual tools to reason about scheduling and asynchronous communication in any Unix-like system.

Quick Recap: The xv6 Scheduler

The xv6 scheduler is a simple round-robin loop in proc.c: scheduler(). It scans the process table, picks the next RUNNABLE process, and calls swtch() to swap CPU registers and stack. A running process eventually gives up the CPU through one of these paths:

All paths ultimately call sched() / swtch() to hand control back to the scheduler thread.

Time Slices and Their Tradeoffs

A time slice is the maximum period a process runs uninterrupted before the scheduler may preempt it. In xv6, the time slice is one tick (one timer interrupt period, configured in trap.c).

Choosing the right time slice is a classic tension:

A Concrete Example

Imagine two processes sharing the CPU:

• Text editor — mostly waiting for keystrokes (I/O-bound, latency-sensitive)
• Video encoder — churning through frames (CPU-bound, throughput-sensitive)

What we want:

• The text editor should preempt the encoder immediately when a key is pressed, so the user sees no lag.
• The encoder should run long stretches so it can keep its working set warm in the CPU cache.

A fixed time slice cannot satisfy both goals perfectly. This motivates a smarter scheduler.

Linux's Completely Fair Scheduler (CFS)

CFS was the default scheduler in Linux from kernel v2.6.23 through v6.6. Its core idea: at any moment, every runnable process of the same priority should have received exactly the same amount of CPU time.

Virtual Runtime (vruntime)

CFS tracks each process's virtual runtime — a weighted measure of how much CPU time it has consumed. Concretely:

• vruntime increases each time the scheduler runs the process.
• CFS always picks the process with the smallest vruntime to run next.
• A process that just woke up from I/O has a small vruntime and therefore gets scheduled quickly — achieving the goal of good interactive performance.

sched(p):  p->vruntime += elapsed_cpu_time
next = process with min(vruntime) among RUNNABLE processes

CFS uses a red-black tree (ordered by vruntime) so picking the minimum is O(log n).

Why This Solves the Text-Editor / Encoder Problem

• The text editor spends most of its time sleeping (waiting for input). Its vruntime barely grows.
• When a key is pressed and the editor becomes runnable, its vruntime is smaller than the encoder's, so CFS preempts the encoder immediately.
• The encoder runs long stretches when the editor is idle, keeping cache warm.

No fixed time slice needed — CFS dynamically adapts.

Unix / Linux Signals

What Is a Signal?

A signal is a software interrupt sent by the kernel (or by another process) to notify a process of an event asynchronously. The process doesn't need to poll; the kernel delivers the signal at the next opportunity.

Common signals:

Default vs. User-Defined Behavior

Each signal has a default action (terminate, stop, ignore, etc.). A process can override this with a custom signal handler — a function that runs when the signal arrives.

#include <signal.h>
#include <stdio.h>
#include <unistd.h>

void handler(int signal) {
    printf("Got signal %d\n", signal);
}

int main(int argc, char **argv) {
    signal(SIGTERM, handler);   // install handler for SIGTERM
    while (1) sleep(10);
}

Now sending SIGTERM prints a message instead of killing the process. Note: SIGKILL cannot be caught or ignored — the kernel always terminates the process.

Signals vs. Hardware Interrupts

Signals are sometimes called software interrupts because they share the asynchronous notification model, but they operate at the process level, not the hardware level.

xv6 Signal-Related System Calls

xv6 (as extended in homework 5) provides three signal-related syscalls:

int  kill(int pid, int signal);             // send signal to pid
void signal(int signum, void (*handler)(int)); // install a handler
void alarm(int secs);                        // schedule SIGALRM after secs seconds

kill marks the target process as having a pending signal; the signal is actually delivered the next time that process returns from the kernel to user space (at a trap return).

Key Takeaways

• The time slice length involves a fundamental tradeoff between interactivity and throughput; no fixed value is universally optimal.
• CFS tracks vruntime (virtual runtime) per process and always schedules the process with the smallest vruntime, achieving proportional fairness and excellent interactive performance without a fixed time slice.
• A signal is the kernel's mechanism for asynchronously notifying a process; the process can install custom handlers for most signals, but SIGKILL is always fatal.
• Signals are not hardware interrupts — they are managed by the kernel and delivered at process-level boundaries (kernel→user transitions).
• The three core signal syscalls are kill (send), signal (install handler), and alarm (delayed timer).