Memory Organization

Seven topics explained step by step, with pictures, flowcharts, tables and solved examples.

1Memory Hierarchy

No single memory is fast, big and cheap at the same time. So a computer uses several kinds of memory in layers, like a pyramid. The top is tiny and very fast. The bottom is huge and slow.

Registers0.3 ns, under 1 KB Cache (L1, L2, L3), SRAM1 to 12 ns, 32 KB to 32 MB Main memory, DRAM50 to 100 ns, 4 to 64 GB Secondary: SSD and hard disk0.1 to 10 ms, up to several TB Tertiary: optical disc and tapeseconds or more, TBs and up fastercheaper
Going down: bigger, cheaper per bit, but about 10 times slower or more at each step.

Volatile memory loses data when power is off: registers, cache and RAM. Non-volatile memory keeps data: SSD, hard disk, optical disc and tape.

Why does the pyramid work? Locality of reference

Temporal localityAn item used recently will probably be used again soon. Example: a loop counter.
Spatial localityItems near a used address will probably be used next. Example: array elements.

2Main Memory

Main memory holds the programs and data the CPU is using right now. The CPU can address it directly. It is made of RAM (read and write, loses data without power) and ROM (mostly read-only, keeps data).

FeatureSRAMDRAM
Cell6 transistors (a latch)1 transistor + 1 capacitor
RefreshNot neededAbout every 64 ms
SpeedFasterSlower
Cost and densityCostly, low densityCheap, high density
Used forCache, registersMain memory

DDR SDRAM sends data on both clock edges, so one clock moves two words. DRAM sends the row address first (RAS) and then the column address (CAS), which halves the address pins.

ROM types

TypeProgrammedErased
Mask ROMAt the factoryNever
PROMOnce, by the userNever
EPROMBy the userUV light, whole chip
EEPROMBy the userElectrically, byte by byte
FlashBy the userElectrically, in blocks (USB, SSD)
Solved exampleMake 64K × 8 memory from 16K × 8 chips. Chips needed = (64K × 8) ÷ (16K × 8) = 4. The address has 16 bits. A15 and A14 go to a 2-to-4 decoder that picks the chip. A13 to A0 go to every chip.
Chip 00000 – 3FFF
Chip 14000 – 7FFF
Chip 28000 – BFFF
Chip 3C000 – FFFF

Address 0x9A3C has A15 A14 = 10, so it is in chip 2.

InterleavingWith 4 banks, address mod 4 picks the bank, so neighbouring words come from different banks at the same time. If each bank needs 4 cycles, 16 words take about 4 + 15 = 19 cycles instead of 64.

3Secondary Memory

Secondary memory is permanent bulk storage. The CPU does not run programs straight from it. Data is copied in blocks into main memory.

Magnetic disk

Track (a ring) Sector (a slice of a track) Same track on every platter = cylinder
  1. Platters spin on a spindle (5400 or 7200 rpm). Each surface has a head on a shared arm.
  2. A track is split into sectors (512 bytes or 4 KB).
  3. Access time = seek time + rotational latency + transfer time.

Average rotational latency = 0.5 × 60 ÷ rpm. Transfer time = rotation time ÷ sectors per track.

Solved example8 surfaces, 10,000 tracks, 400 sectors, 512 B, 7200 rpm, seek 9 ms. Capacity = 8 × 10,000 × 400 × 512 ≈ 16.4 GB. One rotation = 8.33 ms, latency = 4.17 ms, transfer = 0.02 ms. Access time ≈ 9 + 4.17 + 0.02 ≈ 13.2 ms.

Other devices

Magnetic tapeSequential access, 9 tracks (8 data + 1 parity), blocks split by gaps (IRG). Good for backup.
SSDNAND flash, no moving parts, about 0.1 ms. Flash blocks wear out after many erases.
Optical discA laser reads pits and lands on a spiral track. ROM (pressed), R (write once), RW (rewritable).
DiscLaserCapacity (one layer)
CD780 nm infraredabout 700 MB
DVD650 nm red4.7 GB
Blu-ray405 nm blue-violet25 GB
Tape example2400 ft = 28,800 in, 1600 bytes/in, blocks of 4000 bytes, gap 0.6 in. Block + gap = 2.5 + 0.6 = 3.1 in. Blocks = 28,800 ÷ 3.1 ≈ 9290, so capacity ≈ 37.2 MB (46.08 MB without gaps).

4Cache Memory

A cache is a small, very fast SRAM between the CPU and main memory. It keeps copies of recently used blocks. If the word is found, it is a hit. If not, it is a miss and the whole block is fetched from memory. Think of it as notes kept on your desk instead of walking to the library each time.

Each cache line stores a valid bit, a tag, the data block (and a dirty bit in write-back caches). The address is split into three parts:

Tag
compared with stored tag
Index (or set)
picks the line
Offset
picks the word

Cache read flowchart

CPU sends address
↓
Split into tag, index, offset
↓
Read the line at that index
↓
Valid bit on and tag matches?
Yes (hit)
Word goes to the CPU at once
No (miss)
Fetch block from main memory
↓
Evict a victim, write back if dirty
↓
Load block, set valid bit and tag
↓
Word goes to the CPU
Average memory access time (AMAT)AMAT = hit time + miss rate × miss penalty. With hit time 1 ns, penalty 100 ns, hit ratio 95%: AMAT = 1 + 0.05 × 100 = 6 ns. At 99%: 2 ns.
Write policyWhat happensTrade-off
Write-throughWrite cache and memory togetherSimple, memory always current, slower
Write-backWrite cache only, set dirty bit, write memory on evictionLess bus traffic, needs dirty bits

Mapping: where can a block go?

Example: 64K-word memory (16-bit address), 1K-word cache, 16-word blocks, so 1024 ÷ 16 = 64 lines.

SchemeBlock can go toAddress splitConflict misses
Direct1 line (block mod 64)tag 6, index 6, offset 4Highest
Fully associativeAny linetag 12, offset 4None
4-way set associativeAny of 4 lines in one set (16 sets)tag 8, set 4, offset 4Medium
Solved examplesDecode 0x2B7C with the direct split: offset = 12, index = 55, tag = 10. For the block sequence 0, 8, 0, 6, 8 on 4 lines: direct mapping has 5 misses, 2-way (LRU) has 4, fully associative has 3.

Replacement and speed-ups

LRUEvicts the least recently used line. Best in practice.
FIFOEvicts the oldest line. Simple, may remove a busy line.
LFUEvicts the least frequently used line. Needs counters.
RandomEvicts any line. Almost no hardware.

Ways to improve a cache: multi-level cache (L2 answers L1 misses), bigger cache (fewer capacity misses), bigger blocks (use spatial locality), more associativity (fewer conflict misses), victim cache, prefetching, write buffer and non-blocking cache. Direct mapping needs no replacement policy.

Two-level exampleL1 hit 1 ns, L1 miss 5%, L2 hit 10 ns, L2 local miss 20%, memory 100 ns. AMAT = 1 + 0.05 × (10 + 0.2 × 100) = 2.5 ns, against 6 ns without L2.

5Virtual Memory

Virtual memory gives each program its own large, private address space, even when RAM is small and shared. Only the pages in use stay in RAM. The rest wait in the swap area on disk.

Paging

Virtual memory is cut into equal pages. RAM is cut into frames of the same size (often 4 KB). The page table maps each virtual page number (VPN) to a frame number. Each entry has a valid bit, protection bits, and dirty and reference bits.

FormulaPhysical address = frame number × page size + offset
Solved examplesPage size 1 KB, virtual address 3000, page 2 is in frame 5. Page = 3000 ÷ 1024 = 2, offset = 952, physical = 5 × 1024 + 952 = 6072.
Page table size: 32-bit address, 4 KB pages, 4-byte entries. VPN = 20 bits, so 220 entries × 4 B = 4 MB per process. Multi-level and inverted page tables reduce this.

TLB: a cache for translations

The translation lookaside buffer (TLB) is a small, fast cache of recent VPN-to-frame translations. Without it, every access needs two memory reads.

Virtual address (page number + offset)
↓
Page number in TLB?
Yes (TLB hit)
Frame number comes from the TLB
↓
Physical address = frame × page size + offset
No (TLB miss)
Read the page table from memory
↓
Valid bit = 1?
↓
Yes: update the TLB, make the physical address
No: page fault, OS loads the page
TLB exampleTLB 10 ns, memory 100 ns, hit ratio 95%. Hit = 110 ns, miss = 210 ns. EAT = 0.95 × 110 + 0.05 × 210 = 115 ns.

Page fault handling

  1. The MMU sees valid = 0 and traps to the OS.
  2. The OS checks the reference is legal, otherwise it ends the process.
  3. The OS finds a free frame, or picks a victim (saved to disk first if dirty).
  4. The OS reads the needed page from disk into the frame.
  5. The OS updates the page table and TLB (valid = 1).
  6. The faulting instruction restarts.
ExampleMemory 200 ns, fault service 8 ms, fault rate 0.001. EAT = 0.999 × 200 + 0.001 × 8,000,000 ≈ 8200 ns, about 40 times slower.

Page replacement

FIFORemoves the oldest page. Simple. Belady’s anomaly: more frames can cause more faults.
OptimalRemoves the page used furthest in the future. Fewest faults, but needs the future, so it is a benchmark.
LRURemoves the page unused for the longest time. Close to optimal.
ClockRemoves the first page with reference bit 0. A cheap LRU approximation.
ExampleReference string 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 with 3 frames: FIFO = 15 faults, LRU = 12, Optimal = 9.
ThrashingA process with too few frames keeps faulting and does almost no useful work. Fix it with more frames or fewer running processes.

6Memory Management Hardware

The MMU sits between the CPU and memory. It translates every address in hardware and protects memory, so one process cannot touch another process or the OS. An illegal access becomes a trap to the OS.

Base and limit registersBase = start address, limit = size. Check address < limit, then base + address, else trap.
Base 30000, limit 12000: logical 500 gives 30500. Logical 13000 traps.
Paging hardwareThe page-table base register (PTBR) points to the page table, and a TLB caches translations. No external fragmentation, but the last page wastes space.
72,766 B, 2048-byte pages: 36 pages, waste = 2048 − 1086 = 962 B.
Segmentation hardwareAddress = (segment s, offset d). Check d < limit[s], then base[s] + d.
Segment 2: base 4300, limit 400. (2, 53) gives 4353. (2, 500) traps.

Contiguous allocation (base and limit) suffers from external fragmentation. Segmented paging splits each segment into pages to keep a logical structure without external fragmentation.

PointPagingSegmentation
UnitFixed-size pageVariable-size segment
AddressPage number + offsetSegment number + offset
FragmentationInternalExternal
Protection and sharingPer pagePer segment, more natural
Visible to programmerNoYes

Other hardware helpers

Protection bitsRead, write, execute, user or supervisor, kept in each table entry.
Dirty and reference bitsSet by hardware for write-back and LRU-like replacement.
Cache controllerDoes tag compare, replacement and write policy in hardware.
DMA controllerMoves blocks between disk and memory without using the CPU.
MPUA simple MMU in microcontrollers: protects regions, no translation.

7Formula Sheet and Exam Questions

TopicFormula or fact
Address lines2n locations need n address bits. Chips = total capacity ÷ chip capacity
Disk capacitysurfaces × tracks × sectors per track × bytes per sector
Disk access timeseek + 0.5 × (60 ÷ rpm) + (60 ÷ rpm) ÷ sectors per track
Cache linescache size ÷ block size
Cache address bitsoffset = log2(block size), index = log2(lines or sets), tag = the rest
Setslines ÷ ways (direct: 1 way, fully associative: 1 set)
AMAThit time + miss rate × miss penalty
Two-level AMATH1 + M1 × (H2 + M2 × memory)
Page translationframe × page size + offset
Page table size2(VPN bits) × entry size
TLB EATh × (tTLB + tmem) + (1 − h) × (tTLB + 2 × tmem)
Page-fault EAT(1 − p) × tmem + p × tfault
Base and limitaddress < limit, then base + address, else trap
Segmentationd < limit[s], then base[s] + d, else trap

Likely exam questions

  1. Compare SRAM and DRAM, and list the ROM types with their erase methods.
  2. Draw the memory hierarchy and explain why it works (locality).
  3. Calculate disk capacity and average access time from the given geometry.
  4. Explain direct, associative and set-associative mapping with the address split, and find hits and misses for a block sequence.
  5. Compare LRU, FIFO and Optimal on a reference string and count the page faults.
  6. Explain how a virtual address becomes a physical address, including the TLB and a page fault.
  7. Compare paging and segmentation, and explain base and limit protection.