Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

Notes › Operating Systems

Memory Management, Paging and Virtual Memory

The OS decides which part of RAM each process gets, keeps processes from touching each other's memory, and makes programs bigger than RAM possible.

Logical vs physical address

Contiguous allocation and fragmentation

Early systems gave each process one continuous block.

Strategy Pick the hole that is… Notes
First fit first one big enough fast
Best fit smallest one big enough leaves tiny useless holes
Worst fit largest leaves big holes

Fragmentation:

Paging

Split logical memory into pages and physical memory into frames of the same size (e.g. 4 KB). Any page can go into any free frame → no external fragmentation (a little internal fragmentation in the last page).

Address translation

Logical address = page number (p) + offset (d).

Worked example: page size = 1 KB (2¹⁰), logical address = 5000.

Page table size example

32-bit logical addresses, 4 KB pages (2¹²) → 2³²/2¹² = 2²⁰ pages (~1 million). With 4-byte entries → 4 MB page table per process — too big to keep whole, hence multilevel paging.

TLB — Translation Lookaside Buffer

Every memory access would need two RAM accesses (page table + data). The TLB is a small, fast cache of recent page → frame translations.

Effective access time (EAT): EAT = h × (TLB + memory) + (1 − h) × (TLB + 2 × memory) Example: TLB = 20 ns, memory = 100 ns, hit ratio h = 0.8 → 0.8 × 120 + 0.2 × 220 = 96 + 44 = 140 ns (vs 200 ns without a TLB).

Multilevel paging and other page tables

Segmentation

Divide memory by logical units of the program — code, stack, heap, functions — each a variable-size segment with a base and limit.

Paging Segmentation
Unit size fixed (pages) variable (segments)
Seen by the programmer no yes (logical view)
Fragmentation internal external
Table page table segment table (base, limit)

Many systems combined them (segmented paging).

Virtual memory

Run programs larger than physical RAM by keeping only the needed pages in RAM and the rest on disk (swap space). The program sees a big, continuous address space.

Demand paging

Load a page only when it's first used. Each page-table entry has a valid bit. Page fault (accessing a page not in RAM):

  1. The MMU traps to the OS.
  2. The OS checks the access is legal (else: segmentation fault).
  3. Finds a free frame (or replaces one — see Page Replacement Algorithms).
  4. Reads the page from disk into the frame.
  5. Updates the page table, then restarts the instruction.

Page faults are expensive (milliseconds vs nanoseconds), so even a tiny fault rate slows everything — see the effective access time formula in the page replacement note.

Copy-on-write

After fork(), parent and child share pages until one of them writes — then only that page is copied. Makes fork() fast.

Thrashing

When processes don't have enough frames, they page-fault constantly and the CPU does almost no work. Fix with the working-set model, fewer processes or more RAM.

Interview one-liners

More Operating Systems notes