SyntaxPilot
Courses/CS Fundamentals for Placements/Lesson 33
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

CS Fundamentals for Placements · Lesson 33 of 90

Virtual memory and demand paging

virtual memorydemand paginglazy loadingpage faultpage fault handling stepspure demand pagingeffective access time with page faults numericalscopy-on-writememory-mapped fileslocality modelthrashingworking set modelpage fault frequencyframe allocation (equal, proportional, global vs local replacement)

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)

  1. The CPU touches a page; the MMU finds valid bit = 0 in the page table.
  2. The hardware traps to the OS: a page fault.
  3. 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).
  4. 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).
  5. 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.
  6. When the read completes, the OS updates the page table: the frame number and valid bit = 1.
  7. 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 &marks through 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) before fork() 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_SHARED share 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:

  1. a dirty bit per frame (mark a reference with w for a write) and count how many faults needed a write-back;
  2. the EAT for given memory and fault times (clean and dirty);
  3. 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

  1. 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.
  2. What is demand paging? Loading a page only when it is first accessed; a missing page causes a page fault.
  3. 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).
  4. 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.
  5. What is pure demand paging? Starting a process with no pages in memory and bringing in each page only on its first access.
  6. Write the EAT formula with page faults. EAT = (1 - p) × memory access time + p × page fault service time.
  7. 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.
  8. 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.
  9. 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.
  10. 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.
  11. 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.
  12. 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.
  13. 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: malloc 1 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.