E ExamMaster

Operating Systems · Operating Systems

Memory management

Paging, address translation, the TLB, demand paging and segmentation.

maya's editor is 12 KB. RAM is cut into 4 KB frames, so she occupies 3 pages. This lesson is that map: pages and frames, how a logical address splits into page number and offset, the TLB that makes the walk cheap (EAT 140 ns at h = 0.80), demand paging when a page is not yet in RAM, and why segments fragment the other way. Which page to evict is the next lesson.

  • Operating Systems
  • Hard level
  • 5 concepts
  • 5 practice questions

1Pages, frames, page table

maya's editor occupies 12 KB of logical memory — the addresses she thinks she has. Physical memory is RAM, cut into frames of 4 KB. Paging cuts maya's 12 KB into pages of the same 4 KB. 12 / 4 = 3 pages. Each page may sit in any free frame. The page table is the map: page 0 → some frame, page 1 → another, page 2 → another.

Because every page is the same size, free frames are interchangeable. That kills external fragmentation — the leftover holes between unequal chunks. The last page may not fill a frame; those unused bytes inside the frame are internal fragmentation.

Figure. Logical pages stay contiguous in the process's view. Physical frames need not be contiguous — the page table alone carries the map (P0→F2, P1→F0, P2→F1).

How it works

  1. Split logicalLogical address space → equal pages of size 2^k bytes.
  2. Split physicalRAM → equal frames of that same size.
  3. MapPage table: page number → frame number. Any free frame will do.

How many pages?

A process is 12 KB and the page size is 4 KB. How many pages does it need?

  • Number of pages = ceil(process size / page size)ceil(12 / 4)
  • 12 / 43 pages

Pro tip. A remainder still needs a whole frame — round up. A 13 KB process with 4 KB pages needs 4 pages, not 3.

Paging is preferred over contiguous allocation mainly because it
  1. Removes internal fragmentation entirely
  2. Eliminates external fragmentation by mapping equal pages into any free frames
  3. Makes the page table unnecessary

Equal-sized pages fit any free frame, so holes between allocations disappear. Internal fragmentation remains in the last (partial) page; the page table is required, not optional.

2Page number and offset

A logical address is a number maya uses. The hardware splits it into a page number and an offset. The page number indexes the page table to find the frame. The offset is the byte inside that page and is copied unchanged into the physical address.

On a machine with 16-bit logical addresses and a 1 KB page, 1 KB = 2^{10} bytes, so the offset is 10 bits. The page-number field is 16 − 10 = 6 bits, which names 2^6 = 64 pages. maya's 12 KB / 4 KB walk used a different page size; the split rule is the same: offset bits = \log_2(\text{page size}).

Figure. The low k bits never go through the page table — they ride along as the offset. Only the high page-number field is rewritten to a frame number.

How it works

  1. Offset bitsOffset width = \log_2(\text{page size}) — fixed by page/frame size.
  2. Page bitsPage-number bits = address bits − offset bits.
  3. TranslateLookup frame for that page; concatenate frame bits with the same offset.

Address split

A system uses 16-bit logical addresses and a page size of 1 KB. How many bits are for the page number?

  • Page size = 1 KB = 2^{10} bytesoffset = 10 bits
  • Page-number bits = 16 − 106 bits
  • Number of pages = 2^{6}64 pages

Pro tip. Offset bits come only from page size. Double the page size and you steal one bit from the page-number field — the total address width does not grow.

With 32-bit logical addresses and 4 KB pages, the page-number field is
  1. 12 bits
  2. 20 bits
  3. 32 bits

4 KB = 2^{12}, so offset = 12 bits and page number = 32 − 12 = 20 bits.

3TLB and effective access time

Every load would otherwise walk the page table in RAM and then walk the data — two memory accesses. The TLB (translation lookaside buffer) is a small cache of recent page-table entries. A hit gives the frame without reading the page table. A miss still pays the table walk.

Effective access time weights the two paths by the hit ratio h. With TLB access 20 ns, memory 100 ns, and h = 0.80: hit path 20+100 = 120 ns, miss path 20+200 = 220 ns, EAT = 0.80×120 + 0.20×220 = 140 ns. No page faults in that walk — faults belong to demand paging.

Figure. A TLB hit goes CPU → TLB → data memory only. The dashed miss path is the extra page-table read before the data access — that is the second t_{\mathrm{mem}} in the EAT miss term.

How it works

  1. Probe TLBLook up the page number in the associative TLB.
  2. Hit pathFrame known → one data memory access. Cost ≈ t_{\mathrm{TLB}} + t_{\mathrm{mem}}.
  3. Miss pathFetch PTE from memory, then data. Cost ≈ t_{\mathrm{TLB}} + 2t_{\mathrm{mem}}.

Effective access time

TLB access = 20 ns, memory access = 100 ns, hit ratio h = 0.80. Find EAT (page table held in memory; no page faults).

  • Hit path = t_{\mathrm{TLB}} + t_{\mathrm{mem}}20 + 100 = 120 ns
  • Miss path = t_{\mathrm{TLB}} + 2t_{\mathrm{mem}}20 + 200 = 220 ns
  • EAT = 0.80 \times 120 + 0.20 \times 22096 + 44 = 140 ns

Pro tip. Always split into hit case and miss case, then weight by h and 1-h. If a question folds TLB time into the given "memory access", treat t_{\mathrm{TLB}} = 0 and the same split still applies.

Raising the TLB hit ratio from 0.8 to 0.9, with t_{\mathrm{TLB}}=20 ns and t_{\mathrm{mem}}=100 ns, changes EAT from 140 ns to
  1. 130 ns
  2. 120 ns
  3. 110 ns

New EAT = 0.9 \times 120 + 0.1 \times 220 = 108 + 22 = 130 ns. Only the weights change; the two path costs stay 120 and 220.

4Demand paging, faults, thrashing

Demand paging loads a page into a frame only when maya first touches it. A reference to a page that is not resident is a page fault: the OS finds a free frame (or makes one), reads the page from disk, updates the page table, and restarts the instruction. Disk is orders of magnitude slower than RAM, so a fault is expensive.

Thrashing is what happens when maya's working set — the pages she is actively using — is larger than the frames she is allowed. The machine pages in and out and little user work completes. Replacement, the choice of which resident page to evict, is the next lesson.

Figure. A reference walks TLB then page table; an invalid entry traps to the pager to bring the page from disk.

On a page fault

  1. TrapMMU finds invalid/not-present PTE → kernel page-fault handler.
  2. PlaceIf no free frame, run replacement; then read the page from disk into a frame.
  3. ResumeMark present, update TLB/PTE, restart the faulting instruction.
Thrashing is best described as
  1. A TLB miss that still finds the page in RAM
  2. High page-fault activity because the resident set is too small for the working set
  3. Internal fragmentation inside the last page of a process

Thrashing is excessive swapping when frames cannot hold the pages a process keeps touching. A TLB miss with a present page is still a hit in RAM; internal fragmentation is unused space inside a frame.

5Segmentation versus paging

Segmentation cuts memory by logical units maya already names — code, stack, data — each a segment of variable size, addressed as (segment number, offset). Variable sizes match the programmer's view and can leave unusable holes between segments: external fragmentation.

Paging uses fixed frames and instead leaves unused bytes inside the last page of a process: internal fragmentation. Many machines do both: segments whose contents are paged. The exam cut is which leftover you are being asked about.

Figure. Segments match program parts but external-fragment; pages waste a partial last page but pack frames tightly.

How to tell them apart

  1. UnitSegment = variable logical piece. Page = fixed-size block.
  2. AddressSegmentation: (segment #, offset). Paging: (page #, offset).
  3. FragmentationSegments → external holes. Pages → internal waste in the last frame.
Paging vs segmentation
PagingSegmentation
Piece sizeFixed (page = frame)Variable (logical unit)
ViewPhysical convenienceProgrammer's modules
Main fragmentationInternalExternal
Table mapsPage → frameSegment → base + limit
External fragmentation is characteristic of
  1. Pure paging with fixed frame size
  2. Pure segmentation with variable-length segments
  3. A TLB miss on a present page

Variable segment lengths leave holes that may not fit the next segment. Pure paging's leftover space is internal to a frame. A TLB miss is a translation-cache event, not a fragmentation mode.

Notes

  • Paging divides logical memory into fixed-size pages and physical memory into equal frames; the page table maps page numbers to frame numbers.
  • A logical address splits into (page number, offset); the page number indexes the page table and the offset is added to the frame's base.
  • The TLB is a small associative cache of recent page-table entries; a TLB hit avoids an extra memory access to the page table.
  • Page replacement algorithms: FIFO (oldest out, suffers Belady's anomaly), Optimal (replace the page used farthest in future), and LRU (least recently used).
  • Segmentation divides memory by logical units (code, stack, data) of variable size and can cause external fragmentation; paging causes internal fragmentation.

Formulas

  • Number of pages = logical address space / page size; offset bits = \log_2(\text{page size}).
  • Effective Access Time (EAT) with TLB = h*(TLB + mem) + (1-h)*(TLB + 2*mem), where h = hit ratio.
  • For a page size of 2^k bytes, the low k bits of an address form the offset.
  • Page fault rate = (page faults) / (total memory references).
  • Physical address = frame_number * frame_size + offset.

Exam traps & shortcuts

  • Belady's anomaly (more frames -> more faults) occurs in FIFO but never in LRU or Optimal (stack algorithms).
  • Offset bits come from page/frame size; the rest of the address bits give the page/frame number.
  • Optimal is a theoretical lower bound for faults; LRU is the best practical approximation.

Reference tables

Every numerical in this topic is one of these lines.

Formulas to keep
QuantityFormula
Offset bitsk = \log_2(\text{page size}); page bits = address width − k
Number of pagesceil(logical size / page size)
Physical addressframe_number × frame_size + offset
EAT (TLB, no fault)h(t_{\mathrm{TLB}} + t_{\mathrm{mem}}) + (1-h)(t_{\mathrm{TLB}} + 2t_{\mathrm{mem}})
Page-fault ratefaults / total memory references

Name the algorithm or the hole type before you compute.

Replacement and fragmentation cues
CueAnswer
Evict oldest arrivalFIFO — Belady possible
Evict least recently usedLRU — stack, no Belady
Evict farthest next useOptimal — lower-bound benchmark
Holes between variable chunksExternal fragmentation (segmentation)
Unused bytes inside a frameInternal fragmentation (paging)

Recap

12 KB / 4 KB = 3 pages. Offset bits = log2(page size). EAT = 140 ns at h = 0.80.

Paging
Equal pages → any free frame. Kills external fragmentation.
Split
Offset = \log_2(\text{page size}); the rest is the page number.
TLB
Hit: TLB + one mem. Miss: TLB + table + data. Weight by h.
Demand
Fault = disk fetch. Thrashing = working set larger than frames.
Segments
Variable logical units → external fragmentation. Paging → internal.

Practise Memory management

Reading is free and needs no account. Practice, mocks and progress live in the app.

  • 5 exam-style questions on this topic, with explanations
  • A 5-question practice set that ends the chapter
  • Timed mocks scored with the real marking scheme
  • Readiness tracked per topic, kept on your device
Continue with Google — freeNo card, no trial. Works offline once installed.