These are the notes for CS Fundamentals for Placements, episode 33. In episodes 31 and 32 we cut memory into pages and frames and built page tables of every shape. But we still assumed that every page of a process is in RAM before it runs. Today we drop that assumption and invent virtual memory: demand paging and lazy loading, the page fault and its handling steps, pure demand paging, effective access time (EAT) with page faults (numericals), copy-on-write, memory-mapped files, the locality model, thrashing, the working set model, page fault frequency (PFF), and frame allocation (equal, proportional, global vs local replacement). Every term is explained in plain words the first time it appears, and there is a full glossary at the end.
All program outputs below are real: every C program was compiled with gcc 13.3 -O2 (the SyntaxPilot compiler's flags: gcc -O2 -Wno-unused-result main.c -o main -lm) and run on Linux x86-64 on 5 November 2026.
Quick recap: pages, frames, valid bit, swap space
- A page is a fixed-size piece of a process's (logical) memory, usually 4 KB. A frame is a page-sized slot in RAM.
- The page table maps page number → frame number. Each entry has a valid bit: 1 = this page is in RAM in that frame; 0 = it is not.
- Swap space (also called the backing store) is an area on the disk that holds pages that are not in RAM.
The problem: load every page first?
The story: streaming a film
A two-hour film is about 4 GB. The obvious way is to download all of it, then press play: a long wait, and a phone with little space can't play it at all. Streaming fetches only the next few minutes, so playback starts at once. Jump to 1:30:00 and there's a short pause while that part is fetched. Parts you've watched are thrown away. The phone never holds the whole film.
The same problem with programs
RAM: 8 GB
12 programs open, each up to 2 GB
load all pages first → needs 24 GB ✗
And most of that is waste: help menus, error-handling paths and features you never click are loaded but never run.
Virtual memory
Virtual memory separates the memory a process sees (its logical, or virtual, address space) from the RAM that really exists. Each process sees one big, private memory, which can be bigger than the RAM. Only the pages in use are in RAM; the rest wait on disk. The process can't tell the difference.
Virtual memory was invented for the Atlas computer, designed and built by Tom Kilburn and a joint team of the University of Manchester and Ferranti Ltd. (1957 to 1962). The IEEE milestone plaque calls the invention of virtual memory "the most significant new feature of Atlas".
Benefits:
- A program can be larger than physical memory.
- More programs fit in RAM at once (a higher degree of multiprogramming, so better CPU use).
- Less I/O to load or swap a program, so programs start faster.
- Easy sharing of pages (shared libraries, copy-on-write).
Demand paging and lazy loading
Demand paging: a page is brought into RAM only when the program touches it (on demand), exactly like streaming. Lazy loading is the general idea: do the work only at the moment it is needed. The part of the OS that brings pages in is sometimes called the pager (a "lazy swapper" that never swaps in a page that won't be used).
The valid bit does the bookkeeping:
page frame valid
0 5 1
1 - 0 ← still on disk
2 9 1
Live: ask for 1 GB, use almost none
#include <stdio.h>
#include <stdlib.h>
long ram_mb(void) { // how much of us is really in RAM
long pages, resident;
FILE *f = fopen("/proc/self/statm", "r");
fscanf(f, "%ld %ld", &pages, &resident); fclose(f);
return (resident * 4096 / 1048576 + 50) / 100 * 100; // round
}
int main(void) {
long MB = 1048576;
char *big = malloc(1024 * MB); // ask for 1 GB
printf("asked for 1024 MB, in RAM: about %ld MB\n", ram_mb());
for (long i = 0; i < 200 * MB; i += 4096) big[i] = 1; // touch 200 MB
printf("touched 200 MB, in RAM: about %ld MB\n", ram_mb());
for (long i = 0; i < 600 * MB; i += 4096) big[i] = 1; // touch 600 MB
printf("touched 600 MB, in RAM: about %ld MB\n", ram_mb());
free(big);
}
asked for 1024 MB, in RAM: about 0 MB
touched 200 MB, in RAM: about 200 MB
touched 600 MB, in RAM: about 600 MB
malloc(1024 * MB)only reserves addresses; no page is loaded, so the resident set (the pages of the process really in RAM, the second number in/proc/self/statm, counted in pages) is about 0 MB.- Writing one byte into every 4 KB page of the first 200 MB brings exactly those pages in: about 200 MB resident. After 600 MB, about 600 MB. The other 424 MB never used any RAM.
- We round to the nearest 100 MB because the program's own code and libraries also take a little RAM; the rounded numbers are the same on every run.
Page fault
A page fault is a trap (an interrupt caused by the running program, handing control to the OS) that happens when the CPU touches a page whose valid bit is 0. Despite the name, it is not an error: it is the normal way demand paging loads a page. Only a fault on an illegal address is an error.
Page fault handling steps (exam favourite)
- The CPU touches a page; the MMU finds valid bit = 0 in the page table.
- The hardware traps to the OS: a page fault.
- The OS checks its own records (kept in the process's PCB): is this address legal for the process? If not, the process is killed (on Linux:
Segmentation fault). - If legal, the OS finds a free frame (from its free-frame list; if there is none, it must first pick a victim page to throw out: page replacement, next episode).
- The OS asks the disk to read the page into that frame. This takes milliseconds, so the process goes to the waiting state and another process gets the CPU.
- When the read completes, the OS updates the page table: the frame number and valid bit = 1.
- The OS restarts the instruction that faulted. Now the page is there, and the program carries on as if nothing happened.
The instruction is restarted from the beginning, so the hardware must be able to undo a half-done instruction (for example one that moves a block of bytes that crosses a page boundary).
Minor vs major fault (extra): a major fault needs a disk read; a minor fault finds the page already in RAM (for example in the file cache, or a fresh zero page) and only fixes the page table. Our 1 GB demo mostly caused minor faults: new pages of a malloc block are filled with zeros, not read from disk.
Pure demand paging
Pure demand paging: start a process with zero pages in RAM. The very first instruction faults; after that, each page faults exactly once, the first time it is needed. Never bring in a page until it is needed.
One instruction could touch several new pages (the instruction's own page and two data pages: three faults). In practice this is rare because programs show locality (below): they keep reusing the same few pages for a while.
Effective access time with page faults
Let p be the page fault rate: the fraction of memory accesses that cause a page fault, 0 ≤ p ≤ 1.
EAT = (1 - p) × memory access time + p × page fault service time
The page fault service time includes the trap, finding a frame, the disk read, updating the table and restarting: it is dominated by the disk.
Example numbers (textbook style): memory access = 200 ns, page fault service = 8 ms = 8,000,000 ns. One fault costs as much as 40,000 normal accesses.
Live: the EAT calculator
#include <stdio.h>
// Example numbers: RAM access 200 ns, page fault service 8 ms
int main(void) {
double ma = 200, fault = 8000000; // both in ns
double p[3] = {0, 1.0 / 1000, 1.0 / 400000}; // fault rate
for (int i = 0; i < 3; i++) {
double eat = (1 - p[i]) * ma + p[i] * fault;
printf("p = %.7f EAT = %8.1f ns (%.1fx slower)\n",
p[i], eat, eat / ma);
}
double limit = ma * 1.10; // allow 10% slowdown
double pmax = (limit - ma) / (fault - ma);
printf("for <= 10%% slowdown: at most 1 fault in %.0f accesses\n",
1 / pmax);
}
p = 0.0000000 EAT = 200.0 ns (1.0x slower)
p = 0.0010000 EAT = 8199.8 ns (41.0x slower)
p = 0.0000025 EAT = 220.0 ns (1.1x slower)
for <= 10% slowdown: at most 1 fault in 399990 accesses
- One fault in 1000 accesses:
0.999 × 200 + 0.001 × 8,000,000 = 199.8 + 8000 = 8199.8 ns: 41 times slower. - For at most 10% slowdown (EAT ≤ 220 ns):
220 > 200 + 7,999,800 × p→p < 0.0000025: at most one fault in 399,990 accesses.
So the page fault rate must be kept tiny. That is why locality, the working set and frame allocation matter.
Numerical by hand
Memory 100 ns, fault service 20 ms, p = 0.0001:
EAT = 0.9999 × 100 + 0.0001 × 20,000,000
= 99.99 + 2000 = 2099.99 ns (about 21x slower)
Exam traps
- Convert everything to the same unit first:
1 ms = 1,000 µs = 1,000,000 ns. - If RAM is full, a victim page must be thrown out. If the victim is dirty (modified while in RAM; its dirty bit, or modify bit, is 1), it must be written to disk first, so that fault costs two disk transfers. A clean victim can simply be overwritten, since the disk copy is still correct.
Numerical with dirty pages. Memory 100 ns; servicing a fault takes 8 ms if the victim is clean and 20 ms if it is dirty; 70% of victims are dirty. What is the largest acceptable fault rate for EAT ≤ 200 ns?
average fault time = 0.3 × 8 ms + 0.7 × 20 ms = 16.4 ms = 16,400,000 ns
200 = (1 - p) × 100 + p × 16,400,000
100 = p × 16,399,900 → p ≈ 0.0000061 (about 1 fault in 164,000 accesses)
Copy-on-write
The story: two students, one set of notes
Two students share one set of notes. Nobody photocopies the whole notebook; both read the same pages. Only when one wants to write on page 4 do they photocopy page 4. The other's notes stay clean.
The problem it solves
fork() (episode 18) creates a child that is a copy of its parent. Copying hundreds of MB of pages on every fork is slow, and the child very often calls exec() straight away and throws the copy away.
Copy-on-write (COW): after fork(), parent and child share the same frames, all marked read-only. When either one writes to a shared page, the write traps; the OS copies just that page into a new frame for the writer and makes it writable. Pages that are never written are never copied.
Live: same address, different values
#include <stdio.h>
#include <unistd.h>
#include <sys/wait.h>
int marks = 100; // one page, shared after fork
int main(void) {
int fd[2]; pipe(fd);
fflush(stdout);
if (fork() == 0) { // child
marks = 200; // first WRITE: OS copies the page
printf("child : marks = %d\n", marks);
int *where = &marks;
write(fd[1], &where, sizeof where); // send our address
return 0;
}
wait(NULL); // parent waits for the child
int *theirs; read(fd[0], &theirs, sizeof theirs);
printf("parent: marks = %d\n", marks);
printf("same virtual address in both? %s\n",
theirs == &marks ? "yes" : "no");
}
child : marks = 200
parent: marks = 100
same virtual address in both? yes
- The child writes 200, the parent still reads 100, at the same virtual address (the child sends its
&marksthrough a pipe, a one-way channel between processes from episode 19, and the parent compares it with its own). - Possible only because these are virtual addresses: until the write, both page tables pointed at one frame; the write faulted and the OS gave the child its own frame. Same page number, two frames.
fflush(stdout)beforefork()empties the output buffer so it isn't printed twice (episode 18).
vfork (extra): an older call where the child borrows the parent's memory without even COW, and the parent is suspended until the child calls exec or _exit. COW made it mostly unnecessary.
Memory-mapped files
Normal file I/O calls read()/write() (or fread/fwrite) again and again; each is a system call into the kernel. For big files that is slow.
A memory-mapped file maps a file's blocks into the process's pages. Then:
- Reading
p[0]is an ordinary memory read. The first touch causes a page fault, and demand paging loads that part of the file. - Writing
p[0] = 'T'makes the page dirty; the OS writes it back to the file (at the latest when the mapping is removed or the program ends). - Several processes that map the same file with
MAP_SHAREDshare the same frames: a form of shared memory (episode 19).
char *p = mmap(NULL, n, PROT_READ | PROT_WRITE, MAP_SHARED, fd, 0);
n = how many bytes, PROT_READ | PROT_WRITE = the protection (readable and writable), MAP_SHARED = changes go to the file (MAP_PRIVATE would give a copy-on-write private copy instead), fd = the file descriptor (the small number open() returns for an open file), 0 = the offset in the file.
Live: change a file with an array assignment
#include <stdio.h>
#include <string.h>
#include <fcntl.h>
#include <unistd.h>
#include <sys/mman.h>
int main(void) {
const char *text = "tea 10, coffee 20, juice 30\n";
FILE *f = fopen("menu.txt", "w"); fputs(text, f); fclose(f);
int fd = open("menu.txt", O_RDWR), n = strlen(text);
char *p = mmap(NULL, n, PROT_READ | PROT_WRITE, MAP_SHARED, fd, 0);
printf("p[0] read through memory: %c\n", p[0]); // a plain read
p[0] = 'T'; p[8] = 'C'; // a plain write, no fwrite
munmap(p, n); close(fd); // changes go to the file
char line[64]; f = fopen("menu.txt", "r");
fgets(line, sizeof line, f); fclose(f);
printf("file now says: %s", line);
}
p[0] read through memory: t
file now says: Tea 10, Coffee 20, juice 30
No fwrite anywhere: the two letters were changed by plain assignments, and they reached the file on disk. Linux loads every program this way: the program's code and its shared libraries are memory-mapped, and only the parts that run are paged in.
The locality model
The story: a cook's kitchen counter
Making tea, a cook uses the kettle, tea, sugar and milk, again and again. Then for dinner a new set comes out: rice, a pan, spices, and the tea things go back in the cupboard. The counter only has to hold what the current dish needs.
Locality of reference: programs tend to reuse the same small set of pages for a while.
- Temporal locality: a page used now is likely to be used again soon (a loop's code, a counter variable).
- Spatial locality: pages near a used one are likely to be used soon (walking through an array).
The locality model: a process moves from one locality (a set of pages actively used together) to another. Calling a function enters a new locality: its code, its local variables, the data it touches. If RAM holds the current locality, faults happen only when the locality changes. That is why demand paging works.
Thrashing
Live: one frame too few
A loop keeps using pages 0, 1, 2, 3, 4, 0, 1, ... for 100 accesses. Its locality is 5 pages. When RAM is full, the simulator throws out the page that came in first (choosing which page to throw out is page replacement; this rule is FIFO, next episode).
#include <stdio.h>
// A loop that keeps using pages 0,1,2,3,4 over and over (100 accesses)
int faults(int frames) {
int ram[8], used = 0, oldest = 0, count = 0;
for (int t = 0; t < 100; t++) {
int page = t % 5, hit = 0;
for (int i = 0; i < used; i++) if (ram[i] == page) hit = 1;
if (hit) continue;
count++; // page fault
if (used < frames) ram[used++] = page; // a free frame
else { ram[oldest] = page; oldest = (oldest + 1) % frames; }
} // full: evict oldest
return count;
}
int main(void) {
for (int f = 6; f >= 3; f--)
printf("%d frames: %3d faults in 100 accesses\n", f, faults(f));
}
6 frames: 5 faults in 100 accesses
5 frames: 5 faults in 100 accesses
4 frames: 100 faults in 100 accesses
3 frames: 100 faults in 100 accesses
- With 5 or more frames: 5 faults, one per page the first time it is used.
- With 4 frames: every access faults: the page we need next is always the one we just threw out.
Thrashing: a process spends more time paging (moving pages between disk and RAM) than executing. It happens when a process has fewer frames than its current locality needs.
Thrashing across the whole system
CPU use │ ●●●
│ ● ●
│ ● ● ← thrashing
└──────────────────── processes in RAM
As the degree of multiprogramming (the number of processes in memory) grows, CPU use first rises. Past a point, each process has too few frames, they all fault and wait for the disk, and CPU use falls off a cliff. The trap: a scheduler that sees the idle CPU and admits more processes makes it worse.
Cures: give each process enough frames for its current locality (working set, PFF), use local replacement so one thrashing process can't steal frames from others, or run fewer processes (suspend and swap one out).
The working set model
- Δ (delta), the working set window: a number of recent page references.
- Working set
WS(t, Δ): the set of distinct pages referenced in the last Δ references up to time t. - WSS (working set size): the number of pages in the working set.
- A reference string is the list of pages a process touches, in order.
Peter J. Denning, "The Working Set Model for Program Behaviour", Communications of the ACM, 1968.
Live: working set with Δ = 4
#include <stdio.h>
// Working set: the pages used in the last D references
int main(void) {
int ref[14] = {1,2,1,3,1,2, 7,8,7,9,8,7, 7,8};
int D = 4; // the window
for (int t = D - 1; t < 14; t++) {
int in[10] = {0}, size = 0;
printf("t=%2d page %d WS = {", t + 1, ref[t]);
for (int k = t - D + 1; k <= t; k++)
if (!in[ref[k]]) { in[ref[k]] = 1; size++; }
for (int p = 0; p < 10; p++) if (in[p]) printf(" %d", p);
printf(" } size %d\n", size);
}
}
t= 4 page 3 WS = { 1 2 3 } size 3
t= 5 page 1 WS = { 1 2 3 } size 3
t= 6 page 2 WS = { 1 2 3 } size 3
t= 7 page 7 WS = { 1 2 3 7 } size 4
t= 8 page 8 WS = { 1 2 7 8 } size 4
t= 9 page 7 WS = { 2 7 8 } size 3
t=10 page 9 WS = { 7 8 9 } size 3
t=11 page 8 WS = { 7 8 9 } size 3
t=12 page 7 WS = { 7 8 9 } size 3
t=13 page 7 WS = { 7 8 9 } size 3
t=14 page 8 WS = { 7 8 } size 2
At first the process uses pages 1, 2 and 3 (WSS 3). At t = 7 it jumps to a new locality: for a moment the window holds old and new pages (WSS 4). Then the old pages drop out and it settles on {7, 8, 9}. The working set follows the locality automatically.
Using the working set against thrashing
D = WSS1 + WSS2 + ... + WSSn (total frames demanded)
m = frames in RAM
D ≤ m: every process has its locality; the OS may even start another process.D > m: thrashing ahead; the OS suspends a process (swaps it out) and gives its frames to the others.- Choosing Δ: too small misses part of the locality; too large spans several localities. Exact tracking is expensive, so real systems approximate it with a timer and the reference bit (a bit the hardware sets when a page is used).
Page fault frequency (PFF)
fault rate │ ─ ─ ─ ─ ─ upper bound → give a frame
│ ok
│ ─ ─ ─ ─ ─ lower bound → take a frame
└──────────────────── frames given
Page fault frequency controls frames by watching the symptom directly. The OS measures each process's fault rate:
- above the upper bound: the process needs more frames → give it one;
- below the lower bound: it has more than it needs → take one away;
- if frames are needed and none are free → suspend a process.
Frame allocation
Minimum frames: every process needs at least enough frames for all the pages a single instruction can touch, or that instruction would fault forever. The CPU's instruction set decides this number.
Equal allocation: m frames, n processes → m / n each (any leftover frames go to a free-frame pool).
Proportional allocation: frames in proportion to size. With process sizes s_i and total S = Σ s_i:
a_i = (s_i / S) × m
Example numbers: m = 62 frames, P1 = 10 pages, P2 = 127 pages (S = 137).
equal: 31 and 31 (P1 wastes 21 frames)
proportional: 10/137 × 62 ≈ 4, 127/137 × 62 ≈ 57
Allocation can also be by priority: higher-priority processes get more frames.
Global vs local replacement
| Global replacement | Local replacement | |
|---|---|---|
| The victim can be | any process's frame | only one of the faulting process's own frames |
| Good | better overall use of memory, higher throughput | predictable; a process controls its own fault rate |
| Bad | a process's speed depends on the others; thrashing can spread | frames another process isn't using stay idle |
Throughput = the number of processes finished per unit time.
The whole chain
| Step | Obvious attempt | What broke | Fix |
|---|---|---|---|
| 1 | Load every page first | 24 GB needed, 8 GB RAM; most code never runs | Virtual memory, demand paging |
| 2 | Assume the page is in RAM | It isn't (valid bit 0) | Page fault, 7 handling steps, restart |
| 3 | Fault whenever | 1 in 1000 = 41x slower | Keep p tiny (≤ 1 in 400,000 for 10%) |
| 4 | Copy all pages on fork | Slow, often wasted by exec | Copy-on-write |
| 5 | System call per file read | Slow | Memory-mapped files |
| 6 | Too few frames | 100 faults in 100 accesses | Locality, working set, PFF, frame allocation |
Common mistakes
| Mistake | What you see | Why | Fix |
|---|---|---|---|
Writing to a page mapped PROT_READ |
Segmentation fault |
The page is read-only; the MMU traps the write | Map with both PROT_READ and PROT_WRITE |
PROT_WRITE + MAP_SHARED on a file opened O_RDONLY |
mmap: Permission denied (from perror) |
A mapping can't allow more than the file was opened for | Open with O_RDWR |
Forgetting #include <sys/mman.h> |
warning: implicit declaration of function 'mmap' |
The compiler doesn't know mmap returns a pointer | Include the header |
Not checking mmap's result |
crash later | On failure mmap returns MAP_FAILED, not NULL |
if (p == MAP_FAILED) perror("mmap"); |
| Mixing ms and ns in EAT | answer off by 10^6 | 1 ms = 1,000,000 ns |
Convert first |
| Forgetting the dirty victim | EAT too small | A dirty page is written out first | Fault time = write + read |
| "A page fault is an error" | wrong theory answer | It is how demand paging loads pages | Only an illegal address is an error |
| "Idle CPU → add processes" | thrashing gets worse | Each process gets even fewer frames | Reduce multiprogramming |
The first two messages were produced by these programs:
// Segmentation fault: writing to a read-only mapping
int fd = open("menu.txt", O_RDONLY);
char *p = mmap(NULL, 7, PROT_READ, MAP_SHARED, fd, 0);
printf("read: %c\n", p[0]); fflush(stdout); // prints "read: t"
p[0] = 'T'; // Segmentation fault
// mmap: Permission denied
int fd = open("menu.txt", O_RDONLY);
char *p = mmap(NULL, 7, PROT_READ | PROT_WRITE, MAP_SHARED, fd, 0);
if (p == MAP_FAILED) { perror("mmap"); return 1; }
Mini project: a demand-paging simulator
Write a C program that reads a reference string and a number of frames, simulates demand paging with FIFO replacement, and prints, for every reference: the page, hit or fault, and the frames' contents. Then add:
- a dirty bit per frame (mark a reference with
wfor a write) and count how many faults needed a write-back; - the EAT for given memory and fault times (clean and dirty);
- a working set column for a chosen Δ, and a warning line when the working set size exceeds the number of frames ("thrashing risk").
Try the loop 0 1 2 3 4 repeated 20 times with 4, 5 and 6 frames.
Practice
1. EAT: memory 150 ns, fault service 5 ms, p = 1/2000.
Solution
5 ms = 5,000,000 ns; p = 0.0005. EAT = 0.9995 × 150 + 0.0005 × 5,000,000 = 149.925 + 2500 = 2649.925 ns (about 17.7 times slower).
2. Working set with Δ = 3 for the reference string 2 3 2 1 5 2 4 5 3 2.
Solution
Run today's working-set program with this string and D = 3 (real output):
t= 3 page 2 WS = { 2 3 } size 2
t= 4 page 1 WS = { 1 2 3 } size 3
t= 5 page 5 WS = { 1 2 5 } size 3
t= 6 page 2 WS = { 1 2 5 } size 3
t= 7 page 4 WS = { 2 4 5 } size 3
t= 8 page 5 WS = { 2 4 5 } size 3
t= 9 page 3 WS = { 3 4 5 } size 3
t=10 page 2 WS = { 2 3 5 } size 3
At t = 3 the window (2, 3, 2) has only two distinct pages.
3. Proportional allocation: 100 frames, processes of 20, 30 and 150 pages.
Solution
S = 200. a1 = 20/200 × 100 = 10, a2 = 30/200 × 100 = 15, a3 = 150/200 × 100 = 75. Equal allocation would give 33 each (1 frame left over), wasting frames on the small processes and starving the big one.
4. Why does fork() followed by exec() gain so much from copy-on-write?
Solution
exec() replaces the child's whole memory with a new program. Without COW, fork would copy every page of the parent only for exec to throw the copies away. With COW, fork copies only the page table; the few pages the child writes before exec (its stack, a variable or two) are the only ones copied.
5. Put the page fault handling steps in order: (a) restart the instruction, (b) read the page from disk, (c) trap to the OS, (d) update the page table, (e) check the address is legal, (f) find a free frame.
Solution
c → e → f → b → d → a.
6. Memory 100 ns; fault service 8 ms (clean victim) or 20 ms (dirty victim); 70% of victims are dirty. Largest p for EAT ≤ 200 ns?
Solution
Average fault time = 0.3 × 8 + 0.7 × 20 = 16.4 ms = 16,400,000 ns. 200 = (1 - p) × 100 + p × 16,400,000 → p = 100 / 16,399,900 ≈ 0.0000061, about one fault in 164,000 accesses.
7. 93 frames, 5 processes, equal allocation. How many each, and how many are left?
Solution
93 / 5 = 18 each (90 frames); 3 frames are left in the free-frame pool.
Quick quiz
memory access time = 100 ns
page fault service = 10 ms
page fault rate p = 1 / 10,000
// what is the effective access time?
A. 100 ns B. about 1100 ns C. about 10,100 ns D. 1000 ns
Answer
B. 10 ms = 10,000,000 ns. EAT = 0.9999 × 100 + 0.0001 × 10,000,000 = 99.99 + 1000 = 1099.99 ns, about 1100 ns (11 times slower).
Interview questions
- What is virtual memory? Separating the logical memory a process sees from physical RAM, so a process can be larger than RAM and only the pages in use are kept in RAM; the rest are on disk.
- What is demand paging? Loading a page only when it is first accessed; a missing page causes a page fault.
- What is a page fault? Is it an error? A trap raised when a process touches a page that isn't in RAM (valid bit 0). Not an error: the OS loads the page and restarts the instruction. Only an illegal address is an error (segmentation fault).
- List the steps to handle a page fault. Trap → check legality → find a free frame (or a victim) → read the page from disk (process waits) → update the page table → restart the instruction.
- What is pure demand paging? Starting a process with no pages in memory and bringing in each page only on its first access.
- Write the EAT formula with page faults. EAT = (1 - p) × memory access time + p × page fault service time.
- What is copy-on-write? After fork, parent and child share pages read-only; a page is copied only when one of them writes to it.
- What is a memory-mapped file? Advantage? A file mapped into the address space so it is read and written with ordinary memory accesses; avoids a system call per read/write and lets processes share the file's pages.
- What is thrashing? How do you detect and prevent it? A process spends more time paging than executing; signs: high fault rate, low CPU use, busy disk. Prevent with the working set model, PFF, local replacement, or by reducing the degree of multiprogramming.
- What is the working set? The set of distinct pages referenced in the last Δ references; if the sum of working set sizes exceeds the frames available, suspend a process.
- What is locality of reference? Programs reuse a small set of pages for a while (temporal) and nearby pages (spatial); it is why demand paging and caches work.
- Equal vs proportional allocation? Global vs local replacement? Equal: m/n frames each; proportional: (s_i/S) × m. Global: victim from any process; local: only from the faulting process.
- Why does malloc of 1 GB not use 1 GB of RAM? It only reserves virtual addresses; pages are given frames on first touch (demand paging).
Glossary
| Term | Meaning in plain words | Example |
|---|---|---|
| Page | A fixed-size piece of a process's logical memory | 4 KB |
| Frame | A page-sized slot in RAM | frame 5 |
| Page table | Table mapping page numbers to frame numbers | page 0 → frame 5 |
| Valid bit | Page-table bit: 1 = page in RAM, 0 = not | page 1 valid = 0 |
| Swap space / backing store | Disk area holding pages that are not in RAM | Linux swap partition |
| Virtual memory | Logical memory separated from RAM; can be bigger than RAM; only pages in use are in RAM | 12 × 2 GB programs on 8 GB |
| Logical (virtual) address space | All addresses a process can use | what the program sees |
| Degree of multiprogramming | How many processes are in memory at once | 12 programs |
| Demand paging | Load a page only when it's first touched | malloc 1 GB → ~0 MB used |
| Lazy loading | Doing work only when it's needed | streaming a film |
| Pager | The OS part that brings pages in and out | "lazy swapper" |
| Resident set | The pages of a process that are really in RAM | /proc/self/statm |
| Page fault | Trap when touching a page that isn't in RAM | first write to a new page |
| Trap | An interrupt caused by the running program, giving control to the OS | page fault |
| Page fault handling steps | Trap → legal? → free frame → disk read → update table → restart | 7 steps |
| Minor / major fault | Fault without / with a disk read | zero page / page from disk |
| Pure demand paging | Start with zero pages; load each on first use | first instruction faults |
| Page fault rate (p) | Fraction of accesses that fault | 1 in 1000 = 0.001 |
| Page fault service time | Time to handle one fault (mostly the disk) | 8 ms (example) |
| Effective access time (EAT) | Average time of one memory access | (1 - p) × 200 + p × 8,000,000 |
| Victim | The page thrown out to free a frame | the oldest page (FIFO) |
| Page replacement | Choosing a victim when RAM is full | FIFO, LRU (next episode) |
| Dirty (modify) bit | Set when a page is changed in RAM; dirty pages must be written back | after p[0] = 'T' |
fork() |
System call that creates a child copy of the process | episode 18 |
exec() |
Replaces the process's program with a new one | execvp |
| Copy-on-write (COW) | Share pages after fork; copy a page only when written | child writes 200 |
| Pipe | One-way channel between processes | pipe(fd) |
| vfork | Old fork variant that shares memory without copying | parent waits |
| System call | A request from a program to the kernel | read, mmap |
| Memory-mapped file | A file mapped into pages and used like an array | mmap |
mmap / munmap |
Map / unmap a file (or memory) into the address space | mmap(NULL, n, ...) |
PROT_READ / PROT_WRITE |
Page protection: readable / writable | PROT_READ plus PROT_WRITE |
MAP_SHARED / MAP_PRIVATE |
Changes go to the file / private copy-on-write copy | |
| File descriptor (fd) | Small number that open() returns for an open file |
fd = 3 |
MAP_FAILED |
What mmap returns on failure |
perror("mmap") |
| Locality of reference | Programs reuse a small set of pages for a while | a loop |
| Temporal locality | Used now → likely used again soon | a counter variable |
| Spatial locality | Nearby addresses likely used soon | walking an array |
| Locality model | A process moves from one locality to the next | calling a function |
| Locality | A set of pages actively used together | tea things on the counter |
| Thrashing | More time paging than executing | 4 frames, 100 faults in 100 |
| FIFO replacement | Throw out the page that came in first | our thrashing demo |
| Reference string | The pages a process touches, in order | 1 2 1 3 1 2 7 ... |
| Working set window (Δ) | How many recent references to look at | Δ = 4 |
| Working set | Distinct pages in the last Δ references | {7, 8, 9} |
| Working set size (WSS) | Number of pages in the working set | 3 |
| D | Sum of all working set sizes (frames demanded) | D > m → suspend |
| Reference bit | Hardware sets it when a page is used | approximating the working set |
| Page fault frequency (PFF) | Give/take frames to keep the fault rate between bounds | above upper bound → +1 frame |
| Minimum frames | Frames one instruction may need at once | set by the instruction set |
| Equal allocation | m / n frames each | 62 / 2 = 31 |
| Proportional allocation | (s_i / S) × m frames | 4 and 57 |
| Priority allocation | More frames to higher-priority processes | |
| Global replacement | Victim may be any process's frame | better throughput |
| Local replacement | Victim must be the process's own frame | thrashing can't spread |
| Throughput | Processes finished per unit time | |
| Atlas | Manchester/Ferranti computer (1957-1962) where virtual memory was invented |
Summary
- Virtual memory lets a process be bigger than RAM: only the pages in use are in RAM (invented for the Atlas computer, Manchester and Ferranti, 1957-1962).
- Demand paging / lazy loading brings a page in on first touch (live:
malloc1 GB → about 0 MB in RAM, 200 MB touched → about 200 MB). - A page fault is the trap for a missing page; the OS checks the address, finds a frame, reads the page, updates the table and restarts the instruction. Pure demand paging starts with zero pages.
- EAT = (1 - p) × memory + p × fault time (live: one fault in 1000 → 41x slower; 10% slowdown allows only 1 in 399,990).
- Copy-on-write shares pages after fork until a write (live: child 200, parent 100, same virtual address). Memory-mapped files turn file I/O into memory accesses (live:
p[0] = 'T'changed the file). - The locality model explains why it works; too few frames causes thrashing (live: 5 frames → 5 faults, 4 frames → 100 faults).
- The working set (live, Δ = 4) and page fault frequency keep each process supplied; frames are allocated equally or proportionally, with global or local replacement.
Next episode: Page replacement algorithms with numericals: FIFO, Belady's anomaly, Optimal, LRU, the clock algorithm and counting page faults.