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.
| Process | Thread | |
|---|---|---|
| Address space | its 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 cost | high (new address space, page tables) | lower (a stack and some bookkeeping) |
| Communication | needs IPC: pipes, sockets, shared memory | read and write the same memory (and need locks) |
| A crash | usually ends only that process, but see the limits below | can take down the whole process |
| Good for | isolation, security, use of several machines | parallelism 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:
- Resources the kernel shares. Files, directories, sockets, the CPU, the disk, the page cache, the network and the memory of the machine are shared. A process that fills the disk, opens every file descriptor the user is allowed, or consumes all the memory hurts its neighbours, which is the reason resource limits, quotas and cgroups exist.
- Memory shared on purpose. Processes that use shared memory or a shared
mmapsee each other's writes. A crash in the middle of an update can leave the shared data half-written, and a lock held by a process that died stays held unless the lock is designed to be robust (recoverable by the next owner). - Permissions. Processes of the same user can usually send each other signals and, depending on the system's settings, inspect and control each other with
ptrace. Isolation between users or between services is the work of permissions, namespaces and sandboxes, not of the address space alone. - The kernel itself. All processes on a host share one kernel, so a kernel bug, or a hardware flaw such as the speculative-execution leaks (Spectre-class), can cross process boundaries. This is the reason sensitive workloads use virtual machines or additional hardware isolation.
- Supervision. Processes live in a tree. A parent that dies may orphan its children, which are adopted by
init, or may take them along with it (when they share a process group or a service manager stops the whole unit). A supervisor such assystemd, a container runtime or an orchestrator may restart a crashed process, or may decide to stop and restart the whole group of related processes. In a container, if the main process (PID 1) exits, the container stops. A crash is "usually only that process" for the memory, and not necessarily for the service.
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:
- First-come, first-served: simple, but one long job makes all the short ones behind it wait (the convoy effect).
- Shortest job first: best average waiting time, but needs to know the job lengths and can starve long jobs.
- Round robin: each thread gets a time slice (quantum), then goes to the back of the queue. Fair and responsive.
- Priority queues and multi-level feedback: threads that use their whole slice are treated as CPU hogs and lose priority; threads that block often (interactive ones) keep it. Modern schedulers, such as Linux's, are descendants of this idea that track how much CPU each task has received and prefer those that received the least. The next section, "Scheduling on a modern Linux machine", says how far the textbook model goes.
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:
- Scheduling classes. Ordinary programs run in the fair class (
SCHED_OTHER, alsoSCHED_BATCHandSCHED_IDLE). Above it sit the real-time policies (SCHED_FIFO,SCHED_RR), where a runnable real-time task always beats a fair one, andSCHED_DEADLINE, where a task declares its runtime, deadline and period and the kernel admits only what it can guarantee. A real-time task that spins can starve the rest of the system, so these are used sparingly and with limits. - Weights, not fixed slices. In the fair class each task has a weight derived from its
nicevalue, and the CPU is shared in proportion to the weights. There is no fixed time slice of the textbook kind: how long a task runs depends on how many tasks are runnable and on their weights. Linux used the Completely Fair Scheduler (CFS), which always ran the task that had received the least weighted CPU time, until version 6.6 (2023), where it was replaced by EEVDF (earliest eligible virtual deadline first). EEVDF still tracks the share each task is owed, but also gives each task a deadline derived from its requested time slice, so a task that needs short slices (a latency-sensitive one) can be scheduled sooner without being given a larger share. The tuning knobs and the exact behaviour differ between kernel versions, so check yours before relying on a detail. - One run queue per CPU, with a load balancer that moves tasks between CPUs. The scheduler also takes cache affinity (a task is happier on the core where its data is) and, on large machines, NUMA topology and the cost of migrating between sockets into account. This is why pinning a thread to a core (as the ping-pong experiment does) changes timings.
- Groups share, as well as tasks. With cgroups the CPU is divided between groups first:
cpu.weight(a proportional share, only relevant under contention) andcpu.max(a hard quota per period that throttles a group once it has used it, even when the CPUs are otherwise idle). This is how container CPU limits work, and why a container with a quota can show latency spikes at a low average CPU use (containers and Kubernetes). - Preemption and ticks. Whether the kernel can preempt a task running in kernel mode depends on its configuration (voluntary, full or real-time preemption), and a timer tick is not always running (idle and "tickless" CPUs). A burst of interrupts, a CPU frequency change or another virtual machine on the same host (steal time) also delays tasks in ways the scheduler does not control.
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:
- mapped to a physical frame in RAM,
- not yet mapped (never touched),
- or swapped out or backed by a file on disk.
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:
| Step | Time | Page faults |
|---|---|---|
mmap of 256 MB | 0.02 ms | 0 |
| Write one byte to every page (65,536 pages) | 203 ms | 65,536 |
| Write to every page again | 14 ms | 4 |
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 to | Faults in the child | Time spent by the child |
|---|---|---|
| nothing | 13 | under 1 ms |
| 10% of the pages | 3,290 | 13 ms |
| all pages | 32,781 | 133 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:
- FIFO: evict the page that has been in memory the longest. Simple, but a page can be old and still heavily used.
- LRU (least recently used): evict the page not used for the longest time, on the bet that the past predicts the future (locality). Exact LRU is expensive in hardware, so real systems use approximations such as the clock algorithm with a "referenced" bit, and Linux keeps active and inactive lists.
- Optimal: evict the page that will be used furthest in the future. Impossible in practice, but a yardstick for the others.
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
- "Out of memory" is not always a leak. Look at resident memory, not virtual size, and at whether the page cache (file data the kernel keeps in otherwise free RAM, and gives back when needed) is counted.
- Containers limit memory with cgroups; what happens at the limit depends on the configuration. Three things are easy to confuse:
- The limit (
memory.maxin cgroup v2,memory.limit_in_bytesin v1; Kubernetes' memory limit) counts more than the heap: the process's resident memory plus the page cache it caused, kernel memory such as socket buffers, and its children. - Reclaim before kill. When the group reaches its limit the kernel first tries to reclaim memory inside the group: it drops clean page cache and, if swap is available to that group, swaps out anonymous pages. Only when it cannot reclaim enough does the OOM killer pick a process in that group and kill it (exit status 137,
OOMKilled). The cgroupmemory.highsetting is a softer limit that throttles the group before the hard one. It is separate from the whole machine running out of memory, when the host's OOM killer chooses a victim by its badness score (adjustable withoom_score_adj). - Swap is its own setting. Whether a container can swap depends on the host having swap, on the cgroup's swap limit (
memory.swap.max;--memory-swapin Docker), and on the orchestrator: Kubernetes has traditionally required nodes to run without swap, and swap support for containers is a newer, opt-in feature with its own rules. With no swap for the group, going over the limit leads straight to the OOM kill, as in my 50 MB experiment in containers and Kubernetes. With swap it can instead become slow, with the group swapping heavily before (or instead of) being killed.
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).
- Latency spikes can be page faults. A major fault in a hot path can cost from hundreds of microseconds to milliseconds or more, depending on the storage. Databases avoid it by keeping their working set in memory, by
mlock, or by disabling swap. - Thread-per-request has a ceiling. Each thread costs stack memory and scheduler work; that is the reason for event-driven servers and thread pools of limited size (see also resilience patterns for bounding concurrency).
- A system call costs more than a function call: it crosses into the kernel. Batching (
writev, buffered I/O) is the standard remedy; and see memory hierarchy and Big-O in practice for the next level of the story, the CPU caches. - Memory-mapped files (
mmap) let the kernel's paging machinery act as your file cache. Databases use them, and also avoid them for good reasons: you lose control of when I/O happens, and a fault in the wrong place stalls the thread.
7. Common mistakes
- Reading "virtual memory" as "swap". Virtual memory is the address translation; swap is one possible backing store.
- Using more threads than cores for CPU-bound work and expecting more throughput.
- Judging a process by virtual size, or by the first number of
topwithout the cache. - Forgetting that a forked child shares nothing logically but everything physically until it writes.
- Choosing a time slice or thread pool size by guessing instead of measuring.
- Assuming a process and a container are the same thing: a container is a process (or more) with limited views and resources, sharing the host's kernel.
- Assuming that separate processes cannot affect one another: they share the disk, the CPU, the network, the page cache and the kernel, may share memory on purpose, and are managed by supervisors.
- Treating "container memory limit", "OOM kill" and "swap" as one thing, or quoting a single figure for what a page fault costs.
8. Things to mention in an interview
- Process versus thread in terms of address space, cost, communication and failure, and the limits of process isolation (shared resources, shared memory, one kernel, supervisors).
- The states ready, running and blocked, and what a context switch costs directly and indirectly.
- Preemptive versus cooperative scheduling; round robin and the effect of the time slice; priority inversion and its fix; and how Linux really schedules (fair class with weights, real-time classes, EEVDF since 6.6, cgroup shares and quotas).
- Virtual memory as page tables plus a TLB, with page faults (minor and major), copy-on-write and why
forkis cheap. - Page replacement (FIFO, LRU, clock), locality, the working set, thrashing and Belady's anomaly.
- A concrete story: "the container was killed because its memory (resident set and page cache) hit the cgroup limit and reclaim was not enough, so the OOM killer ran; there was no swap for that group". And the three separate questions behind it: what the limit counts, what the kernel reclaims first, and whether swap is allowed.
Quick recap
- A process has its own address space; threads share one. Threads are cheaper (about 48 microseconds against 3.2 ms to create here) and need locks.
- The scheduler trades throughput, latency and fairness; a shorter round-robin slice means more switches (7 against 2 in the example) and a faster response.
- Virtual memory is lazy: mapping 256 MB cost 0.02 ms and touching it cost 65,536 page faults. A minor fault was about 3 microseconds here; a major fault depends on the storage, from tens of microseconds to milliseconds.
- Copy-on-write makes
forkfast; pages are copied only when written (33,000 faults when the child wrote everything). - Page replacement chooses victims by guessing the future: LRU beat FIFO (12 against 15 faults), FIFO can show Belady's anomaly (9 then 10), and a working set that does not fit means thrashing.
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
- Remzi and Andrea Arpaci-Dusseau, Operating Systems: Three Easy Pieces, the chapters on scheduling, address spaces, paging and page replacement.
- Silberschatz, Galvin and Gagne, Operating System Concepts (Wiley), for Belady's anomaly and the working-set model.
- Peter Denning, The Working Set Model for Program Behavior (Communications of the ACM, 1968), and Thrashing: Its Causes and Prevention (1968).
- Linux man pages: fork(2), mmap(2), clone(2).
- Linux kernel documentation, CFS scheduler, EEVDF scheduler, Real-time group scheduling and SCHED_DEADLINE and the cgroup v2 admin guide (
memory.max,memory.high,memory.swap.max,cpu.weight,cpu.max) and Concepts overview of memory management.
Practise this topic: CS Fundamentals