CS Fundamentals Trainer · Guides

Operating systems: processes, threads, virtual memory and scheduling

Processes against threads, context switches, round-robin scheduling, virtual memory, page faults, copy-on-write, page replacement and thrashing, with measurements on Linux and two step-by-step animations.

26 min read

Every program you write runs on top of an operating system, and many puzzling behaviours (a process that is "using 8 GB" but the machine has 4, a server that gets slower when you add threads, a pause of a few milliseconds that no code explains) are the operating system doing its job. The kernel has three main jobs: it decides who runs on the CPU (scheduling), it gives every program the illusion of its own private memory (virtual memory), and it mediates access to hardware (files, network, devices) through system calls. This guide covers the first two in depth, plus the vocabulary an interviewer expects: process, thread, context switch, page fault.

I ran small experiments on Linux for the numbers below; the code is in the appendix. The machine was a small virtual machine with two cores, so treat the ratios as the lesson and the absolute times as examples.

1. Processes and threads

A process is a running program together with its resources: its own virtual address space, open files, and at least one thread. A thread is a path of execution inside a process: it has its own stack and registers but shares the address space (and so the heap and global variables) with the other threads of the same process.

ProcessThread
Address spaceits own; isolated from other processes unless memory is deliberately shared (shared memory, mmap of a shared file)shared with the other threads of the process
Creation costhigh (new address space, page tables)lower (a stack and some bookkeeping)
Communicationneeds IPC: pipes, sockets, shared memoryread and write the same memory (and need locks)
A crashusually ends only that process, but see the limits belowcan take down the whole process
Good forisolation, security, use of several machinesparallelism and concurrency inside one program

In the experiment, creating and joining a thread took about 48 microseconds, while forking a process took about 3.2 milliseconds (the forking process had a 128 MB heap, so there were page tables to copy: the cost depends on the size of the process). Threads are cheaper, but the price is the shared memory, which is where the races and deadlocks of the concurrency guide come from. In the experiment, a thread that added 1 to a variable changed the parent's value; a child process that added 100 did not, because after fork it had its own copy.

How far process isolation goes

Separate address spaces stop one process from reading or overwriting another's memory by accident. That is a narrower promise than "processes cannot affect each other". Several things are shared, or can be reached, between processes:

So treat a process boundary as fault containment for memory errors, and add what the situation needs for the rest: limits, permissions, supervision and, for untrusted code, stronger sandboxes.

On Linux both are "tasks" created by the same system call family (clone) with different flags about what is shared. Language runtimes add their own layers on top: Go's goroutines and Node's event loop are not kernel threads, although they run on top of some. The kernel schedules only its own threads.

The life of a process

Diagram: The states of a process or thread

Only as many threads as there are CPU cores can be running at once. The others are ready (waiting for a core) or blocked (waiting for something else, using no CPU at all). Most servers' threads are blocked most of the time, waiting for the network or the disk, which is why a server can have thousands of threads on a few cores. When people say a system is CPU-bound they mean many threads are ready and few are blocked; I/O-bound is the opposite.

2. The context switch

To run another thread on a core, the kernel saves the registers of the current one, picks another, and restores that one's registers. If the new thread belongs to a different process it must also switch the address space. This is a context switch. The direct cost is small; I measured two processes passing one byte back and forth through pipes on a single core and got about 3.5 microseconds per round trip, which includes two switches and four system calls. The indirect cost is larger and harder to see: the new thread finds the CPU caches and the address-translation cache (TLB) full of the previous thread's data, so it starts slowly.

This is why more threads is not always faster. For CPU-bound work, more runnable threads than cores adds switching and cache misses and no throughput. For I/O-bound work, more threads help until the machine spends its time switching or running out of memory (each thread has a stack, typically 1 MB or more of address space and some of it real memory). That is also what motivates event loops, goroutines and async/await: a very large number of cheap tasks multiplexed on a few kernel threads.

3. Scheduling

The scheduler decides which ready thread runs next. Its goals conflict: high throughput (total work done), low latency (how quickly interactive work responds), and fairness (nobody starves). Classical algorithms are worth knowing as vocabulary:

Step through round robin with three processes needing 5, 3 and 8 units of CPU. Use the switch to compare a slice of 2 with a slice of 6.

Interactive animation: round robin

The trade-off is visible in the numbers. With a time slice of 2 there are 7 context switches and the average waiting time is 7.0; with a slice of 6 there are only 2 switches and the average wait is 4.3. A shorter slice makes the system more responsive (a process waits at most a few units before it gets to run) but spends more time switching; a longer slice approaches first-come-first-served. In the first case, the short process P2 finishes at time 9; in the second at time 8. A real kernel does not use a fixed slice like this (see "Scheduling on a modern Linux machine" below): it computes how long a task runs from the number of runnable tasks, their weights and the kernel's own settings, typically in the order of milliseconds, and the cost per switch is tiny compared with a millisecond, so for real systems the question is more about fairness and latency than about overhead.

Scheduling on a modern Linux machine

Round robin with a fixed slice is a model for learning. A real Linux scheduler differs in ways that matter when you reason about latency:

The lesson of the textbook model holds: time slices trade responsiveness against switching cost, and fairness competes with throughput. But "how long will my thread wait?" on a real system depends on the kernel version, the policy, the weights, the cgroup settings and the load on that CPU, and is best answered by measuring (perf sched, run-queue latency from tracing tools, /proc/pressure/cpu).

Two more terms. Preemptive scheduling means the kernel can take the CPU away from a thread (by a timer interrupt) without its cooperation; cooperative scheduling relies on tasks yielding, as in a single-threaded event loop where one long synchronous function blocks everything. And priority inversion is when a low-priority thread holds a lock that a high-priority thread needs, while a medium-priority thread keeps the low one from running; the usual fix is priority inheritance, a temporary boost of the lock holder.

4. Virtual memory

Every process sees a large, private, contiguous address space. The hardware and kernel translate each virtual address into a physical address using a page table, in units of fixed-size pages (4 KB on most systems). The translation is cached in the TLB. A virtual page may be:

Diagram: Translating a virtual address

Virtual memory gives you isolation (one process cannot read another's memory), simplicity (each program is linked as if it owned the machine), overcommit (the sum of all address spaces can exceed RAM) and sharing (the same physical pages of a library, or of a file, can appear in many processes).

Memory is lazy: a page fault is normal

I mapped 256 MB with mmap and measured:

StepTimePage faults
mmap of 256 MB0.02 ms0
Write one byte to every page (65,536 pages)203 ms65,536
Write to every page again14 ms4

Mapping memory costs nothing; the kernel only records that the range is valid. Each first touch causes a minor page fault: the CPU traps into the kernel, which finds a free frame, zeroes it and maps it. That cost about 3 microseconds per page here, and 14 times more than the second pass, when the pages were already there. (These figures are from one small virtual machine; the cost of a minor fault varies with the kernel, the CPU, the page size and whether huge pages are in use.) This is why "the process uses 8 GB" can be misleading: virtual size is what was mapped, resident size (RSS) is what is really in RAM. A major page fault has to bring the page from storage (a swapped-out page, or a file page that is not in the cache). Its cost depends on where the page comes from: a few tens to hundreds of microseconds from a fast NVMe drive, milliseconds from a spinning disk or a busy network volume, much less from compressed memory (zswap or zram, which trade CPU for disk access), and it grows when the device is busy, the queue is long or the volume is throttled (as on cloud disks with I/O limits). It is therefore anywhere from tens to thousands of times the cost of a minor fault, and the tail (the worst few faults) is far worse than the average. Measure it on your own hardware (perf, /proc/<pid>/stat, vmstat) before deciding how much a fault matters.

fork and copy-on-write

fork creates a copy of a process. Copying a 128 MB heap literally would take a long time, and the child often calls exec straight away and throws the copy away. So the kernel copies only the page tables and marks all pages copy-on-write: both processes share the physical pages, read-only, and a page is copied only when someone writes to it. I forked a process with a 128 MB heap and had the child write to a share of its pages:

Child writes toFaults in the childTime spent by the child
nothing13under 1 ms
10% of the pages3,29013 ms
all pages32,781133 ms

The fork call itself took 1 to 2 ms in each case. Each page written costs one fault and one 4 KB copy. This is why Redis, which uses fork to take a snapshot, can need extra memory in proportion to how many pages the parent modifies while the snapshot runs, and why a write-heavy workload during a fork shows latency spikes.

5. When memory runs out: page replacement

If there is no free frame when a page is needed, the kernel must evict one. Which one? A good choice is a page that will not be needed soon; a poor choice means the page is read back immediately. The kernel cannot see the future, so algorithms approximate it:

Step through a reference string with three frames, switching between FIFO and LRU. The classic string produces 15 faults with FIFO and 12 with LRU, out of 20 references.

Interactive animation: page replacement

More memory can mean more faults: Belady's anomaly

With FIFO, giving a process more frames can increase its faults. For the reference string 1 2 3 4 1 2 5 1 2 3 4 5, FIFO gives 9 faults with 3 frames and 10 with 4 (my script confirms both). The oldest page is not necessarily the least useful, so the extra frame changes the eviction order in an unlucky way. LRU does not have this problem (10 faults with 3 frames and 8 with 4): it belongs to a family of "stack algorithms" whose contents with n frames are always a subset of the contents with n+1 frames.

Locality and the working set

Programs with locality need far less memory than their size. In a test with 5,000 references where 90% go to 10 "hot" pages out of 100, LRU faulted 3,023 times with 5 frames, 1,247 with 10, 432 with 20 and 286 with 50. The first few frames matter a great deal, and then returns diminish. The set of pages a process needs over a short time is its working set. If the sum of the working sets of the running processes exceeds RAM, the system is thrashing: it spends its time swapping pages in and out and does little useful work. The sequential loop over 10 pages is the worst case for LRU: with 9 frames every one of 200 references faults, while with 10 frames only the first 10 do. This looks like a cliff in performance, and it is what you see when a database's working set no longer fits in memory, or when a process or container whose limit allows swapping runs short of memory and the machine starts to swap. (A container with no swap allowance does not thrash in this way; it is killed instead, see section 6.)

6. Putting it to use

Know the limit, the swap setting and the memory settings of your runtime (for example, a JVM or Node heap larger than the container's limit, or a heap that fits but leaves nothing for stacks, buffers and the page cache).

7. Common mistakes

8. Things to mention in an interview

Quick recap

Appendix: the experiment code

The timings come from the first script (Python 3 on Linux, standard library only; run on a small virtual machine, so absolute times will differ on yours (with the kernel version, the CPU, the page size and the hypervisor) and vary from run to run, while the fault counts are exact). The scripts show the principles; they do not model the real Linux scheduler or page-replacement code. The second script is deterministic: the same page-replacement and scheduling models drive the animations above.

Page faults, copy-on-write, context switches and thread creation

import os, mmap, resource, time, threading, sys

PAGE = os.sysconf("SC_PAGE_SIZE")
def faults(): 
    r = resource.getrusage(resource.RUSAGE_SELF); return r.ru_minflt, r.ru_majflt

# ---- 1. virtual memory is lazy: mapping 256 MB costs nothing until the pages are touched
size = 256 * 1024 * 1024
f0 = faults(); t0 = time.perf_counter()
m = mmap.mmap(-1, size)
t1 = time.perf_counter(); f1 = faults()
for off in range(0, size, PAGE): m[off] = 1
t2 = time.perf_counter(); f2 = faults()
print(f"page size {PAGE}; mmap of {size>>20} MB: {1000*(t1-t0):.2f} ms, {f1[0]-f0[0]} minor faults")
print(f"touching every page: {1000*(t2-t1):.0f} ms, {f2[0]-f1[0]} minor faults (pages: {size//PAGE})")
t3 = time.perf_counter()
for off in range(0, size, PAGE): m[off] = 2
t4 = time.perf_counter(); f4 = faults()
print(f"touching them again: {1000*(t4-t3):.0f} ms, {f4[0]-f2[0]} faults")
m.close()

# ---- 2. fork is copy-on-write: the child shares pages until it writes
buf = bytearray(b"x" * (128 * 1024 * 1024)); n = len(buf)//PAGE
def child_writes(fraction):
    r, w = os.pipe(); t = time.perf_counter()
    pid = os.fork()
    if pid == 0:
        a = faults()[0]; s = time.perf_counter()
        for i in range(int(n * fraction)): buf[i * PAGE] = 7
        os.write(w, f"{faults()[0]-a} {1000*(time.perf_counter()-s):.0f}".encode()); os._exit(0)
    forkms = 1000 * (time.perf_counter() - t)
    os.waitpid(pid, 0); fl, ms = os.read(r, 100).decode().split()
    return forkms, fl, ms
for frac in (0.0, 0.1, 1.0):
    fm, fl, ms = child_writes(frac)
    print(f"fork of a {n*PAGE>>20} MB process took {fm:.1f} ms; child wrote {int(frac*100)}% of pages: {fl} faults, {ms} ms")

# ---- 3. what a context switch costs: two processes ping-pong one byte through pipes
def pingpong(rounds=20000):
    a_r, a_w = os.pipe(); b_r, b_w = os.pipe()
    pid = os.fork()
    if pid == 0:
        os.sched_setaffinity(0, {0})
        for _ in range(rounds): os.read(a_r, 1); os.write(b_w, b"x")
        os._exit(0)
    os.sched_setaffinity(0, {0})
    t = time.perf_counter()
    for _ in range(rounds): os.write(a_w, b"x"); os.read(b_r, 1)
    dt = time.perf_counter() - t; os.waitpid(pid, 0)
    return dt / rounds * 1e6
print(f"process ping-pong on one core: {pingpong():.1f} microseconds per round trip (2 switches)")

# ---- 4. thread vs process creation
def spawn_thread(k=2000):
    t = time.perf_counter()
    for _ in range(k):
        th = threading.Thread(target=lambda: None); th.start(); th.join()
    return (time.perf_counter() - t) / k * 1e6
def spawn_proc(k=300):
    t = time.perf_counter()
    for _ in range(k):
        pid = os.fork()
        if pid == 0: os._exit(0)
        os.waitpid(pid, 0)
    return (time.perf_counter() - t) / k * 1e6
print(f"create+join a thread: {spawn_thread():.0f} us; fork+wait a process (here with a 128 MB heap): {spawn_proc():.0f} us")

# ---- 5. threads share memory, processes do not
shared = [0]
def bump(): shared[0] += 1
th = threading.Thread(target=bump); th.start(); th.join()
pid = os.fork()
if pid == 0: shared[0] += 100; os._exit(0)
os.waitpid(pid, 0)
print("after a thread added 1 and a child process added 100:", shared[0])

Page replacement and round-robin scheduling

from collections import deque, OrderedDict

def paging(refs, frames, policy):
    mem = OrderedDict(); faults = 0
    for p in refs:
        if p in mem:
            if policy == "lru": mem.move_to_end(p)     # FIFO ignores hits
        else:
            faults += 1
            if len(mem) == frames: mem.popitem(last=False)   # oldest (FIFO) or least recently used (LRU)
            mem[p] = True
    return faults

REFS = [7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1]
print("textbook string, 3 frames: FIFO", paging(REFS,3,"fifo"), "LRU", paging(REFS,3,"lru"))
B = [1,2,3,4,1,2,5,1,2,3,4,5]
print("Belady string, FIFO:", {f: paging(B,f,"fifo") for f in (3,4)}, " LRU:", {f: paging(B,f,"lru") for f in (3,4)})
# a loop over 10 pages: LRU with 9 frames is the worst case, with 10 it never faults again
loop = list(range(10)) * 20
print("loop over 10 pages, 200 refs, LRU:", {f: paging(loop,f,"lru") for f in (8,9,10)})
# locality: 90% of references go to 10 hot pages out of 100
import random
rnd = random.Random(3); hot = [rnd.randrange(10) if rnd.random() < .9 else rnd.randrange(10,100) for _ in range(5000)]
print("5000 refs, 90% to 10 hot pages of 100, LRU faults by frames:", {f: paging(hot,f,"lru") for f in (5,10,20,50,100)})

def round_robin(bursts, q):
    t = 0; ready = deque(bursts); left = dict(bursts); first = {}; finish = {}; last = None; switches = 0
    ready = deque(n for n,_ in bursts)
    while ready:
        n = ready.popleft(); run = min(q, left[n])
        if last is not None and last != n: switches += 1
        last = n; t += run; left[n] -= run
        if left[n]: ready.append(n)
        else: finish[n] = t
    wait = {n: finish[n] - b for n,b in bursts}
    return switches, finish, wait, sum(wait.values())/len(wait), sum(finish.values())/len(finish)
BURSTS = [("P1",5),("P2",3),("P3",8)]
for q in (1,2,6): 
    s,fin,w,aw,at = round_robin(BURSTS,q); print(f"quantum {q}: {s} switches, finish {fin}, avg wait {aw:.1f}, avg turnaround {at:.1f}")

Sources

Practise this topic: CS Fundamentals

More guides