Scheduling and virtual memory

Scheduling

The CPU can run only one thread per core at a time. Scheduling is the OS policy that decides which ready thread runs next. Three classic algorithms illustrate the design space:

First-In, First-Out (FIFO / FCFS) — run each process to completion before starting the next. Simple to implement but catastrophic when a long job arrives first: a 60-second batch job blocks all short interactive jobs behind it ("convoy effect").

Round-robin — give each process a fixed time slice (typically 1–10 ms), then preempt it and move to the next process in a circular queue. Every process makes progress; no single process can monopolise the CPU. The cost is context switching overhead: switching threads has a measurable price (flushing pipeline state, TLB entries, cache lines). Very short slices increase responsiveness but spend more time switching than running.

Priority scheduling — assign each process a priority level; always run the highest-priority ready process. Effective when some work (OS interrupt handlers, real-time tasks) genuinely must run first. The risk is starvation: low- priority processes may never run if high-priority ones keep arriving. Real schedulers add aging — slowly raising the priority of processes that have been waiting — to prevent this.

Modern OS schedulers (Linux CFS, Windows HPET scheduler) are sophisticated hybrids that blend priority, fairness, and interactivity heuristics. The principles above are their building blocks.

Virtual memory and page tables

Each process believes it has access to a large, contiguous address space — on a 64-bit system, up to 2⁴⁸ bytes (roughly 256 TB). Physical DRAM is far smaller. Virtual memory is the mechanism that creates this illusion.

The address space is divided into fixed-size pages (typically 4 KB). A page table maps each virtual page number to either a physical frame in DRAM or a marker saying "this page is not currently in RAM." The hardware Memory Management Unit (MMU) translates every virtual address to a physical address on the fly, using the page table as a lookup.

When a process accesses a virtual address whose page is not in DRAM, a page fault interrupt fires. The OS handles it by loading the missing page from disk (swap space), updating the page table, and resuming the process. From the process's perspective, nothing happened — but it paid a disk-latency penalty.

Virtual address  →  [MMU + page table]  →  Physical address
  0x00401000               |                  0x01F34000   (in DRAM)
  0x7FFC0000               |                  page fault → load from disk

Page tables also enforce protection: the OS marks pages as readable, writable, or executable, and the MMU enforces this. A stack overflow that writes past the last allocated stack page triggers a segmentation fault because the page beyond the stack is marked not-writable — or not mapped at all.