SyntaxPilot
Courses/CS Fundamentals for Placements/Lesson 31
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 31 of 90

Paging and the TLB with numericals

pagingpageframepage tablepage number and page offsetlogical-to-physical address translationpage table size numericalspage table entry bits (valid, dirty, reference, protection)page size trade-offsshared pagespage-table base registerTLBTLB hit and misseffective access time with TLB numericals

These are the notes for CS Fundamentals for Placements, episode 31. Last episode, giving every program one unbroken stretch of RAM (contiguous allocation) ended in external fragmentation: 400 K free, yet a 350 K program could not run. Today we fix that for good with paging: pages, frames, the page table, the page number and page offset, logical-to-physical address translation, page table entry bits (valid, protection, dirty, reference), the page-table base register (PTBR), page table size numericals, page size trade-offs and shared pages. Then we make paging fast with the TLB: TLB hits and misses, the hit ratio, effective access time (EAT) numericals, the TLB flush and the ASID. 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. All outputs are deterministic.

The problem: memory in pieces

From episode 30: 1000 K of RAM held programs A (300 K), B (200 K), C (300 K) and D (200 K). B and D finished:

| A 300K | hole 200K | C 300K | hole 200K |
  • 400 K is free in total, but a 350 K program fails: no single hole (free gap) is big enough. Free memory chopped into pieces between processes is external fragmentation.
  • Compaction (sliding programs together so the holes join) works, but copying hundreds of megabytes stops everything.

The root cause is the rule "one program = one unbroken stretch". What if a program could live in pieces, scattered anywhere?

The idea: paging

The story: a big family on a train

Railway booking Paging
A family of 14 can't get 14 berths side by side, so it is split into groups of 8 (group 0, group 1) The OS cuts a program's logical memory into equal fixed-size pieces: pages
Every coach has exactly 8 berths; a group goes into any coach with space RAM is cut into slots exactly one page big: frames; any page goes into any free frame
A reservation chart: group 0 → coach S4, group 1 → coach S9 A page table per process: page 0 → frame 5, page 1 → frame 2
Berth 5 stays berth 5 in whichever coach you land The offset (position inside the page) stays the same inside the frame

Definitions

  • Page: a fixed-size block of a process's logical address space (the addresses the program sees, from episode 30).
  • Frame (page frame): a fixed-size block of physical memory (real RAM), exactly the same size as a page.
  • Page table: a table, one per process, with one entry per page, giving the frame number that holds that page.
  • Paging: the memory-management scheme that lets a process's physical memory be non-contiguous: its pages sit in any free frames.
logical memory        page table          physical memory (frames)
page 0  ───────►  0 │ 5 │  ───────►  frame 5
page 1  ───────►  1 │ 2 │  ───────►  frame 2
page 2  ───────►  2 │ 7 │  ───────►  frame 7

What paging fixes and what it costs:

Contiguous allocation (ep 30) Paging
External fragmentation Yes: holes between processes None: any free frame can be used
Internal fragmentation With fixed partitions Only in the last page of each process: less than one page (on average about half a page)
Compaction needed Sometimes Never
Extra cost Relocation + limit registers A page table per process, and a lookup on every access (fixed by the TLB)

Pages on a real machine

#include <stdio.h>
#include <unistd.h>
int main(void) {
    long page = sysconf(_SC_PAGESIZE);          // ask the OS: page size?
    printf("page size on this machine: %ld bytes\n", page);
    int program = 10000;                        // a 10,000-byte program
    long pages = (program + page - 1) / page;   // round UP
    printf("a %d-byte program needs %ld pages\n", program, pages);
    printf("wasted in the last page: %ld bytes\n", pages*page - program);
}
page size on this machine: 4096 bytes
a 10000-byte program needs 3 pages
wasted in the last page: 2288 bytes
  • sysconf (from <unistd.h>) asks the operating system for a system setting; _SC_PAGESIZE is the page size.
  • 4096 bytes = 4 KiB. A KiB (kibibyte) is 1024 bytes; a MiB (mebibyte) is 1024 KiB; a GiB (gibibyte) is 1024 MiB. (KB, MB, GB strictly mean powers of 1000, episode 1.)
  • The program needs ⌈10000 / 4096⌉ = 3 pages = 12,288 bytes, so the last page wastes 12,288 - 10,000 = 2288 bytes of internal fragmentation.
  • (program + page - 1) / page is the integer way of rounding up a division.
  • 4096 = 2^12. Page sizes are always a power of two, which makes splitting an address trivial (next section).

Page number and offset

Every logical address is split into two parts:

  • Page number (p): which page the byte is in. It is the index into the page table.
  • Page offset (d): where the byte is inside that page, from 0 to page size - 1.
logical address 20000, page size 4096
page   = 20000 / 4096 = 4      (4 x 4096 = 16384)
offset = 20000 % 4096 = 3616
check:  4 x 4096 + 3616 = 20000

Because the page size is 2^n, the offset is the low n bits and the page number is all the bits above them:

         m-bit logical address
|<-- page number p: m - n bits -->|<-- offset d: n bits -->|

With m = 32 and 4 KiB pages (n = 12): 20 bits of page number, 12 bits of offset. No division is needed: the hardware just takes the wires.

The obvious mask fails (live)

A bitwise AND (&, episode 3) keeps only the bits that are 1 in both numbers. The number we AND with to keep some bits is called a mask. The obvious mask is the page size:

#include <stdio.h>
int main(void) {
    unsigned a = 20000;               // a logical address
    unsigned p = a >> 12;             // 4096 = 2^12: drop the low 12 bits
    unsigned d = a & 4096;            // keep the low 12 bits?
    printf("address %u -> page %u, offset %u\n", a, p, d);
    printf("check: %u * 4096 + %u = %u\n", p, d, p * 4096 + d);
}
address 20000 -> page 4, offset 0
check: 4 * 4096 + 0 = 16384

Wrong! 4096 in binary is 1 0000 0000 0000: a single 1-bit (bit 12) followed by twelve zeros. 20000 & 4096 keeps only bit 12, which is exactly the bit we wanted to drop, and 20000 has a 0 there. To keep the low 12 bits we need twelve 1-bits: 4096 - 1 = 4095 = 0xFFF = 1111 1111 1111.

#include <stdio.h>
int main(void) {
    unsigned a = 20000;               // a logical address
    unsigned p = a >> 12;             // 4096 = 2^12: drop the low 12 bits
    unsigned d = a & 4095;            // 4095 = 0xFFF: twelve 1-bits
    printf("address %u -> page %u, offset %u\n", a, p, d);
    printf("check: %u * 4096 + %u = %u\n", p, d, p * 4096 + d);
    printf("with / and %%: page %u, offset %u\n", a / 4096, a % 4096);
}
address 20000 -> page 4, offset 3616
check: 4 * 4096 + 3616 = 20000
with / and %: page 4, offset 3616

Rule: page number = addr >> n (or addr / size), offset = addr & (size - 1) (or addr % size). >> shifts the bits right, dropping the low n bits.

Address translation

The MMU (memory management unit, episode 30) translates every logical address:

  1. Split the logical address into page number p and offset d.
  2. Look up entry p of the page table to get the frame number f.
  3. Physical address = f × page size + d. In bits: the frame number simply replaces the page number; the offset is copied unchanged.
logical [  p  |  d  ]  ──page table: p → f──►  physical [  f  |  d  ]

Where is the page table? The PTBR

The page table is itself in RAM (it is far too big for registers). A CPU register, the page-table base register (PTBR), holds the physical address where the current process's page table starts. On a context switch (the CPU moving from one process to another, episode 17), the OS saves the old process's state and loads the new process's PTBR, which switches the whole memory map in one step. (On x86 this register is called CR3.) Some systems also keep a page-table length register (PTLR) with the table's size, so page numbers beyond it trap.

What's inside a page table entry (PTE)

A page table entry (PTE) is one row of the page table:

| frame number | valid | protection (R/W/X) | dirty | reference |
Bit Meaning Example
Valid (present) bit 1 = this page belongs to the process and is in RAM; 0 = not, so the MMU traps to the OS (an invalid access, or a page fault, episode 33) page 3 below
Protection bits What is allowed on the page: read, write, execute code pages are read + execute, not write
Dirty (modified) bit Set by hardware when the page is written; the OS must save a dirty page to disk before reusing its frame after x = 5 on that page
Reference (accessed) bit Set by hardware whenever the page is read or written; tells the OS which pages are in active use used by page replacement, episode 34

A trap is an interrupt caused by the running program itself, handing control to the OS.

The MMU, simulated (live)

#include <stdio.h>
// One process, page size 4096. Page table: page -> frame + bits
int frame[4] = {5, 2, 7, 0};       // where each page sits in RAM
int valid[4] = {1, 1, 1, 0};       // page 3 is not in memory
int rw[4]    = {0, 1, 1, 1};       // page 0 is code: read-only
void translate(unsigned addr, int is_write) {
    unsigned p = addr / 4096, d = addr % 4096;
    printf("%s %5u: page %u offset %4u -> ",
           is_write ? "write" : "read ", addr, p, d);
    if (p >= 4 || !valid[p]) { printf("TRAP: invalid page\n"); return; }
    if (is_write && !rw[p]) { printf("TRAP: read-only\n"); return; }
    printf("frame %d, physical %u\n", frame[p], frame[p] * 4096 + d);
}
int main(void) {
    translate(100, 0);  translate(5000, 1);  translate(9000, 0);
    translate(13000, 0);  translate(200, 1);
}
read    100: page 0 offset  100 -> frame 5, physical 20580
write  5000: page 1 offset  904 -> frame 2, physical 9096
read   9000: page 2 offset  808 -> frame 7, physical 29480
read  13000: page 3 offset  712 -> TRAP: invalid page
write   200: page 0 offset  200 -> TRAP: read-only
  • frame[] is the page table. valid[] and rw[] are the valid and write-permission bits.
  • read 100: page 0, offset 100 → frame 5 → 5 × 4096 + 100 = 20580.
  • write 5000: page 1 (4096..8191), offset 904 → frame 2 → 8192 + 904 = 9096.
  • read 9000: page 2, offset 808 → frame 7 → 28672 + 808 = 29480.
  • read 13000: page 3, valid bit 0 → trap.
  • write 200: page 0 is read-only code → trap. This is exactly how a real Segmentation fault is caught: the hardware checks the PTE and traps; the OS stops the program.

Worked example (the in-video "Try it")

Page size 1024 bytes; page table 0 → 3, 1 → 8, 2 → 1. Logical address 2100:

  • p = 2100 / 1024 = 2, d = 2100 % 1024 = 52.
  • Page 2 → frame 1. Physical = 1 × 1024 + 52 = 1076.

How big is the page table?

Recipe:

  1. Offset bits n = log2(page size).
  2. Page-number bits = logical address bits - n.
  3. Number of entries = 2^(page-number bits) (one entry per page, not per frame).
  4. Page table size = entries × bytes per entry.

Physical side:

  1. Frames = physical memory size / page size.
  2. Frame-number bits = log2(frames).
  3. A PTE needs the frame-number bits plus the flag bits, rounded up to whole bytes (usually 4 or 8).

Example: 32-bit logical addresses, 4 KiB pages, 64 MiB RAM.

offset bits    = 12
page bits      = 32 - 12 = 20  → 2^20 = 1,048,576 entries
frames         = 2^26 / 2^12 = 2^14 = 16,384 → frame number = 14 bits
PTE            = 14 bits + flags → 4 bytes
page table     = 2^20 x 4 B = 4 MiB, for EVERY process

Calculator (live)

#include <stdio.h>
// Page table size = number of pages x bytes per entry
void table(int addr_bits, int offset_bits, int entry_bytes) {
    int page_bits = addr_bits - offset_bits;
    unsigned long long entries = 1ULL << page_bits;
    unsigned long long kib = entries * entry_bytes / 1024;
    printf("%d-bit, %2d offset bits: 2^%d entries x %d B = ",
           addr_bits, offset_bits, page_bits, entry_bytes);
    if (kib >= 1048576) printf("%llu GiB\n", kib / 1048576);
    else if (kib >= 1024) printf("%llu MiB\n", kib / 1024);
    else printf("%llu KiB\n", kib);
}
int main(void) {
    table(32, 12, 4);       // 32-bit address, 4 KiB pages
    table(32, 22, 4);       // 32-bit address, 4 MiB pages
    table(48, 12, 8);       // 48-bit address, 4 KiB pages
}
32-bit, 12 offset bits: 2^20 entries x 4 B = 4 MiB
32-bit, 22 offset bits: 2^10 entries x 4 B = 4 KiB
48-bit, 12 offset bits: 2^36 entries x 8 B = 512 GiB
  • 1ULL << page_bits is 2^page_bits (shifting 1 left by k places multiplies it by 2^k); ULL makes it a 64-bit unsigned number so 2^36 does not overflow.
  • 32-bit with 4 KiB pages: 4 MiB per process. With 4 MiB pages: only 10 page bits, a 4 KiB table.
  • 48-bit addresses (x86-64 with 4-level paging "supports 48 virtual address bits", sandpile.org) with 4 KiB pages and 8-byte entries: 512 GiB per process, far bigger than the RAM. A flat (single-level) page table is impossible there; episode 32 fixes it with multilevel paging.

Page size trade-offs

Small pages (e.g. 4 KiB) Big pages (e.g. 2 MiB, 4 MiB)
Internal fragmentation Little (less than one small page per process) Up to a whole big page
Page table size Large (more pages) Small
TLB coverage (memory one TLB entry covers) Small → more TLB misses Large → fewer misses
Disk transfers Many small ones Fewer, bigger ones (more efficient per byte)
Loading only what's used Fine-grained Coarse

There is no single winner; real systems use a small default page and allow big pages for programs that need lots of memory (huge pages, episode 32).

Average internal fragmentation with paging is about half a page per process (the last page is, on average, half full).

Shared pages

40 students run the same text editor on one server. The editor's code is 150 KB, each student's data is 50 KB.

no sharing:   40 x (150 + 50) = 8000 KB
shared code:  150 + 40 x 50   = 2150 KB

With paging, each student's page table points its code pages at the same frames: one physical copy, many page tables. These are shared pages. Sharing is only safe for reentrant code (also called pure code): code that never modifies itself, so it is read-only and no process can disturb another. The protection bits mark these pages read + execute only. This is how shared libraries (episode 30) are kept in RAM only once.

The new problem: two trips per access

The page table is in RAM. So every load or store now needs:

  1. one RAM access to read the PTE, then
  2. one RAM access to read or write the actual data.

If one RAM access takes 100 ns (nanoseconds, billionths of a second), every access now takes 200 ns: twice as slow. Unacceptable.

The TLB

The story: the delivery boy's memory

Delivery at a big society TLB
A huge residents' register at the gate: slow to search The page table in RAM
A tiny notebook of regular customers: "Mehta → flat 1204" The TLB: recent page → frame translations
Name in the notebook? Go straight up TLB hit: frame found in about a clock cycle
Not there? Check the register, write it in the notebook, cross out an old note TLB miss: read the page table from RAM, save the translation, replace an old entry

Definitions

  • TLB (translation lookaside buffer): a small, very fast cache inside the MMU that stores recent page-number → frame-number translations.
  • Associative memory: memory in which every entry is compared with the search key at the same time (in parallel), instead of one by one. This makes the TLB fast, and expensive, so it is small.
  • TLB hit: the page number is found in the TLB; the frame number comes out immediately and RAM is accessed once (for the data).
  • TLB miss: the page number is not in the TLB; the page table is read from RAM, the translation is put into the TLB, then the data is accessed.
  • Hit ratio (h): the fraction of lookups that hit. Miss ratio = 1 - h.
  • When the TLB is full, an entry is replaced, often the least recently used (LRU) one (episode 10).

Typical figures (Wikipedia, "Translation lookaside buffer"): size 12 to 4,096 entries, hit time 0.5 to 1 clock cycle, miss penalty 10 to 100 clock cycles, miss rate 0.01 to 1%. On x86 the hardware walks the page tables itself on a miss (starting from CR3); MIPS uses a software-managed TLB: a miss raises an exception and the OS fills the TLB.

logical [p | d] ──► TLB? ──hit──► f ──► physical [f | d]
                     │
                    miss
                     ▼
              page table (RAM, via PTBR) ──► f, and put (p, f) into the TLB

TLB simulation (live)

#include <stdio.h>
int tlb[4], used[4], now, hits, misses;   // a 4-entry TLB, LRU
void touch(int page) {
    int lru = 0; now++;
    for (int i = 0; i < 4; i++) {
        if (tlb[i] == page) { hits++; used[i] = now; return; }
        if (used[i] < used[lru]) lru = i;
    }
    misses++; tlb[lru] = page; used[lru] = now;  // walk the page table
}
void test(const char *name, int step) {      // step = bytes between reads
    for (int i = 0; i < 4; i++) tlb[i] = -1, used[i] = 0;
    hits = misses = 0;
    for (int r = 0; r < 4; r++)                  // read 64 KiB, 4 times
        for (int a = 0; a < 65536; a += step) touch(a / 4096);
    printf("%-10s hits %5d  misses %3d  hit ratio %.2f%%\n",
           name, hits, misses, 100.0 * hits / (hits + misses));
}
int main(void) { test("in order", 4); test("jumping", 4096); }
in order   hits 65472  misses  64  hit ratio 99.90%
jumping    hits     0  misses  64  hit ratio 0.00%
  • A 4-entry TLB with LRU replacement. touch(page) is one lookup: a hit updates the entry's last-used time; a miss replaces the least recently used entry.
  • test reads 64 KiB (16 pages of 4 KiB) four times: either in order, 4 bytes at a time (16,384 reads per pass), or jumping 4096 bytes each time (16 reads per pass).
  • In order: 65,536 lookups, 64 misses (each of the 16 pages misses once per pass, because 16 pages don't fit in 4 entries), 99.90% hit ratio: each translation is reused 1023 more times.
  • Jumping: 64 lookups, all misses: the 16 pages cycle through a 4-entry LRU TLB, so every page has been evicted by the time it comes back.
  • This is locality (episode 8): programs keep using memory near what they just used, which is why a tiny TLB works so well, and why walking arrays in order is faster.

Effective access time (EAT)

Let m = time of one RAM access, t = time to search the TLB, h = TLB hit ratio.

hit:   t + m          (TLB, then the data)
miss:  t + m + m      (TLB, the page table, then the data)
EAT  = h(t + m) + (1 - h)(t + 2m)

If the question doesn't give a TLB time, take t = 0: EAT = h·m + (1 - h)·2m = (2 - h)·m.

Some questions say the TLB search overlaps the memory access or is negligible; then use EAT = h·m + (1 - h)·2m. Always write the formula you use.

Numerical

m = 100 ns, t = 20 ns, h = 0.80:

EAT = 0.8 x (20 + 100) + 0.2 x (20 + 200) = 96 + 44 = 140 ns

EAT calculator (live)

#include <stdio.h>
// Effective access time (EAT) with a TLB
int main(void) {
    double m = 100, t = 20;     // ns: one RAM access, one TLB search
    double ratio[4] = {0.80, 0.90, 0.98, 0.99};
    printf("no TLB at all: %.0f ns (page table + data)\n", 2 * m);
    for (int i = 0; i < 4; i++) {
        double h = ratio[i];
        double eat = h * (t + m) + (1 - h) * (t + 2 * m);
        printf("hit ratio %.0f%%: EAT = %.1f ns, slowdown %.0f%%\n",
               100 * h, eat, 100 * (eat - m) / m);
    }
}
no TLB at all: 200 ns (page table + data)
hit ratio 80%: EAT = 140.0 ns, slowdown 40%
hit ratio 90%: EAT = 130.0 ns, slowdown 30%
hit ratio 98%: EAT = 122.0 ns, slowdown 22%
hit ratio 99%: EAT = 121.0 ns, slowdown 21%

Without a TLB every access costs 200 ns. With 99% hits it costs 121 ns, only 21% slower than plain memory. Raising the hit ratio matters far more than shaving the TLB time.

Finding the hit ratio you need

m = 100 ns, t = 0. For EAT ≤ 110 ns: (2 - h) × 100 ≤ 110 → h ≥ 0.90.

Context switches: TLB flush and ASID

The TLB is shared by all processes, but page numbers are not: process A's page 4 is in frame 9, process B's page 4 is in frame 2. After a context switch from A to B, a TLB hit on page 4 would give B A's frame: wrong, and a security hole.

  1. TLB flush: mark every TLB entry invalid on each context switch. Simple and safe, and the only option on some older hardware (Wikipedia names the Intel 80386), but the new process starts cold: every lookup misses until the TLB refills.
  2. ASID (address-space identifier): tag each TLB entry with a small number naming the process (address space) it belongs to. A hit needs both the page number and the ASID to match the current process, so entries of many processes coexist and no flush is needed. The OS flushes only when it reuses an ASID.
TLB:  ASID | page | frame
       A   |  4   |  9
       B   |  4   |  2

On x86 the ASID is called the PCID (process-context identifier). From the Linux kernel patch that started using it: "PCID is a "process context ID" -- it's what other architectures call an address space ID", "x86's PCID is 12 bits" (4096 values), and "Every non-global TLB entry is tagged with a PCID". (Global entries, such as kernel pages that every process maps the same way, are marked so they survive switches.)

The whole chain

Step Obvious attempt What broke Fix
1 One unbroken stretch per program External fragmentation: 350 K fails with 400 K free Paging: pages in any frames
2 Divide addresses Slow, and the mask & 4096 gave offset 0 Page size = 2^n: offset = low n bits, mask = size - 1
3 Pages anywhere Where is each page? Page table (via the PTBR): p → f
4 Let every access through Bad pages, writes to code Valid and protection bits trap
5 One flat table 4 MiB (32-bit) to 512 GiB (48-bit) per process Next: multilevel tables, huge pages
6 Page table in RAM Every access = 2 RAM trips TLB (99.9% hits with locality)
7 TLB shared by processes Wrong frame after a switch TLB flush or ASID (x86 PCID)

Common mistakes

Mistake What you see Why Fix
offset = addr & 4096 offset 0 and check: 4 * 4096 + 0 = 16384 (wrong output, live) 4096 is a single 1-bit addr & 4095 (mask = page size - 1)
Translating the offset too Wrong physical address Only p becomes f Physical = f × size + d
Miss costs t + m Wrong EAT A miss reads the page table and the data Miss = t + 2m
Page table entries = RAM / page size Wrong numerical That's the number of frames Entries = 2^(logical bits - offset bits)
Forgetting to round up pages 2 pages for 10,000 bytes A partial page still needs a whole frame ⌈size / page size⌉
Using 1 << 36 with int warning: left shift count >= width of type [-Wshift-count-overflow], and the value prints 0 1 is a 32-bit int 1ULL << 36
Sharing writable pages One process changes another's data Sharing is safe only for read-only (reentrant) code Share code, give each process its own data
Forgetting the flush / ASID Wrong frame after a context switch TLB entries belong to a process Flush on switch, or tag with an ASID

Mini project: a paging + TLB simulator

Write a C program that reads, from stdin, a page size, a page table (frame number, valid bit, write bit per page) and a list of accesses like r 20000 or w 5000. Simulate an 8-entry TLB with LRU replacement in front of the page table. For each access print the page, offset, whether it was a TLB hit or miss, and the physical address or the trap. At the end, print the hit ratio and the EAT for m = 100 ns, t = 10 ns. Then add ASIDs: accept switch A / switch B lines and compare the hit ratio with "flush on every switch" against "tag with ASID".

Practice

1. Page size 2 KiB: split logical address 7000.

Solution

2 KiB = 2048 = 2^11. p = 7000 / 2048 = 3 (3 × 2048 = 6144), d = 7000 - 6144 = 856. In bits: p = 7000 >> 11, d = 7000 & 2047.

2. 36-bit logical address, 4 KiB pages, 4-byte entries. Page table size?

Solution

Offset 12 bits, page number 24 bits → 2^24 = 16,777,216 entries × 4 B = 2^26 B = 64 MiB.

3. m = 80 ns, t = 0, h = 95%. EAT?

Solution

EAT = 0.95 × 80 + 0.05 × 160 = 76 + 8 = 84 ns.

4. Why can only read-only pages be shared?

Solution

If a writable page were shared, one process's writes would change the other processes' data, breaking the isolation between them. Read-only (reentrant) code never changes, so every process can safely use the same frames. (Writable pages can be shared until the first write with copy-on-write, episode 33.)

5. A process of 72,766 bytes, page size 2048 bytes. How many pages, and how much internal fragmentation?

Solution

72,766 / 2048 = 35.53 → 36 pages (73,728 bytes). Internal fragmentation = 73,728 - 72,766 = 962 bytes.

6. 32-bit logical addresses, 1 GiB of physical memory, 4 KiB pages, and each PTE holds the frame number plus valid, dirty, reference and 3 protection bits. Find the frame-number bits, the PTE size and the page table size.

Solution

Frames = 2^30 / 2^12 = 2^18 → 18-bit frame number. PTE = 18 + 1 + 1 + 1 + 3 = 24 bits = 3 bytes (in practice rounded to 4). Entries = 2^(32 - 12) = 2^20. Table = 2^20 × 3 B = 3 MiB (or 4 MiB with 4-byte entries).

7. m = 100 ns, t = 0. What hit ratio keeps EAT within 110 ns?

Solution

EAT = h × 100 + (1 - h) × 200 = 200 - 100h ≤ 110 → h ≥ 0.90.

8. Page size 1 KiB, page table 0 → 6, 1 → 4, 2 → 9, 3 → invalid. Translate logical 3000 and 3500.

Solution

3000: p = 2, d = 3000 - 2048 = 952 → frame 9 → 9 × 1024 + 952 = 10,168. 3500: p = 3 → valid bit 0 → trap.

Quick quiz

RAM access m = 50 ns
TLB search t = 10 ns
TLB hit ratio h = 90%
// effective access time?

A. 60 ns B. 65 ns C. 110 ns D. 55 ns

Answer

B. EAT = 0.9 × (10 + 50) + 0.1 × (10 + 100) = 54 + 11 = 65 ns.

Interview questions

  1. What is paging, and what problem does it solve? Splitting logical memory into fixed-size pages and physical memory into same-size frames, so a process can occupy any free frames. It removes external fragmentation and the need for compaction.
  2. Page vs frame? A page is a block of logical (virtual) memory; a frame is a block of physical memory of the same size.
  3. How is a logical address translated? Split into page number and offset; the page table gives the frame number; physical = frame × page size + offset.
  4. Why are page sizes powers of two? So the offset is just the low bits and the page number the high bits: no division.
  5. Does paging have fragmentation? No external; internal only in the last page of each process (about half a page on average).
  6. What does a page table entry contain? Frame number plus valid, protection (R/W/X), dirty and reference bits.
  7. What is the PTBR? A register holding the address of the current process's page table; changed on every context switch (CR3 on x86).
  8. How big is a page table for 32-bit addresses and 4 KiB pages? 2^20 entries × 4 B = 4 MiB per process.
  9. Small vs large pages? Small: less internal fragmentation, bigger tables, more TLB misses. Large: the reverse.
  10. What are shared pages? Frames of read-only (reentrant) code mapped into many processes' page tables, so only one copy is in RAM.
  11. What is a TLB and why is it needed? A small, fast, associative cache of page → frame translations; without it every access would need an extra RAM access for the page table.
  12. What is the EAT formula? EAT = h(t + m) + (1 - h)(t + 2m).
  13. What happens to the TLB on a context switch? It is flushed, or entries are tagged with an ASID (PCID on x86) so no flush is needed.
  14. Who handles a TLB miss? On x86, the hardware page walker; on MIPS, the OS (software-managed TLB).

Glossary

Term Meaning in plain words Example
Contiguous allocation Each process gets one unbroken stretch of RAM episode 30
External fragmentation Free memory split into holes between processes, none big enough 400 K free, 350 K fails
Internal fragmentation Wasted space inside an allocated block 2288 bytes in the last page
Hole A free gap in memory 200 K between A and C
Compaction Sliding processes together so holes join slow
Logical (virtual) address Address generated by the program 20000
Logical address space All logical addresses a process can use 0 .. 2^32 - 1
Physical address Real address in RAM 20580
Paging Memory scheme where a process's pages sit in any free frames
Page Fixed-size block of logical memory 4 KiB
Frame (page frame) Fixed-size block of physical memory, same size as a page frame 5
Page table Per-process table: page number → frame number 0 → 5, 1 → 2
Page number (p) Which page an address is in; index into the page table 20000 → 4
Page offset (d) Position of the byte inside its page 20000 → 3616
Address translation Turning a logical address into a physical one (p, d) → f × size + d
MMU Hardware that translates addresses on every access
sysconf(_SC_PAGESIZE) C call asking the OS for its page size 4096
KiB / MiB / GiB 1024 bytes / 1024 KiB / 1024 MiB 4 KiB page
Power of two 2 multiplied by itself n times 4096 = 2^12
>> (right shift) Moves bits right, dropping the low ones 20000 >> 12 = 4
<< (left shift) Moves bits left; 1 << k = 2^k 1ULL << 36
Bitwise AND (&) Keeps bits that are 1 in both numbers 20000 & 4095 = 3616
Mask A number used with AND to keep chosen bits 4095 = 0xFFF
PTBR (page-table base register) Register with the address of the current page table CR3 on x86
PTLR (page-table length register) Register with the page table's size
Context switch CPU moving from one process to another load new PTBR
PTE (page table entry) One row of the page table: frame number + bits
Valid (present) bit 1 = page belongs to the process and is in RAM; 0 → trap page 3
Protection bits Read / write / execute permissions of a page code: read-only
Dirty (modified) bit Set when the page is written; must be saved before reuse
Reference (accessed) bit Set when the page is used page replacement
Trap Interrupt caused by the running program, handing control to the OS invalid page
Page fault Trap on access to a page that is not in RAM (episode 33)
Segmentation fault OS stopping a program after an invalid memory access write to read-only page
Page table size Entries × bytes per entry 4 MiB for 32-bit, 4 KiB pages
Flat (single-level) page table One table with an entry for every page 512 GiB for 48-bit
Page size trade-off Small pages: less waste, bigger tables; big pages: the reverse
TLB coverage (reach) Memory covered by all TLB entries together entries × page size
Shared pages The same frames mapped in many processes' page tables one editor copy
Reentrant (pure) code Code that never modifies itself, safe to share editor code
TLB (translation lookaside buffer) Small fast cache of recent page → frame translations 4 entries in our demo
Associative memory All entries compared with the key at once the TLB
TLB hit Translation found in the TLB 65,472 hits
TLB miss Translation not in the TLB; read the page table 64 misses
Hit ratio (h) Fraction of lookups that hit 99.90%
Miss penalty Extra time a miss costs 10-100 cycles
LRU Replace the least recently used entry our TLB
Locality Programs keep using memory near what they just used in-order reads
Hardware-managed TLB CPU walks the page table itself on a miss x86
Software-managed TLB A miss raises an exception and the OS fills the TLB MIPS
EAT (effective access time) Average time of one memory access 140 ns
ns (nanosecond) One billionth of a second 100 ns
TLB flush Invalidating all TLB entries on a context switch
ASID (address-space identifier) Tag on each TLB entry naming its process A, B
PCID x86's ASID, 12 bits 4096 values
Global TLB entry Entry shared by all processes, not flushed kernel pages

Summary

  • Paging cuts logical memory into pages and RAM into same-size frames; a per-process page table (found through the PTBR) maps page → frame. No external fragmentation; internal only in the last page (live: 3 pages for 10,000 bytes, 2288 bytes wasted).
  • An address splits into page number (high bits) and offset (low bits); the mask is page size - 1 (live: & 4096 gave offset 0, & 4095 gave 3616).
  • Physical = frame × page size + offset. PTEs carry valid, protection, dirty and reference bits; invalid pages and illegal writes trap (live).
  • Page table size = 2^(page-number bits) × entry size: 4 MiB for 32-bit, 512 GiB for 48-bit (live) → next episode. Small vs big pages is a trade-off; shared pages keep one copy of read-only code.
  • Paging makes every access two RAM trips; the TLB caches translations (live: 99.90% hits in order, 0% jumping). EAT = h(t + m) + (1 - h)(t + 2m) (live: 140, 130, 122, 121 ns).
  • On a context switch, flush the TLB or tag entries with an ASID (x86: 12-bit PCID).

Next episode: Page table structures and segmentation: multilevel paging, hashed and inverted page tables, huge pages, segmentation and segmented paging.