Memory Systems

A memory hierarchy is a layered organization of storage according to access time, capacity, cost per bit, volatility and proximity to the CPU. No one technology is simultaneously fastest, largest, cheapest and non-volatile, so active information is copied into small fast levels while bulk information remains in larger slow levels.

The physical memory hierarchy. Virtual memory is a separate address-translation and protection mechanism that may use backing storage.

Level	Typical property	Main function
CPU registers	Fastest, only a few bytes or words, volatile	Hold the current instruction, addresses, operands and results
Cache (L1/L2/L3)	Very fast SRAM, small and volatile	Keep copies of recently or nearby used memory blocks
Main memory	DRAM, typically gigabytes, volatile	Hold active programs and data
Auxiliary storage	Large non-volatile SSD, HDD, optical disk or tape	Store programs, files and archives persistently

Levels of the memory hierarchy.

Virtual memory is not another physical storage tier between RAM and disk. It is an address-translation, isolation and protection mechanism: virtual pages map to RAM frames, and selected nonresident pages may have copies in backing storage. A system can use virtual addressing even when it does not page data to disk.

Moving downward in the figure increases capacity and access time while reducing cost per bit. Moving upward increases speed and cost per bit. Registers and caches are managed mainly by compiler and hardware, physical-memory allocation and virtual mappings by the memory-management unit (MMU) plus the operating system, and files by the operating system and applications.

Locality and Block Transfer

The hierarchy works because normal programs do not reference all addresses uniformly:

• Temporal locality: a recently referenced instruction or datum is likely to be referenced again soon, as in a loop variable.

• Spatial locality: addresses near a referenced item are likely to be used soon, as in sequential array traversal.

• Sequential access: instruction execution normally proceeds through neighboring addresses until a branch.

Information moves between adjacent levels in blocks: a cache line between cache and RAM, a page between RAM and backing storage, and a file-system block between secondary storage and memory. Larger blocks exploit spatial locality but increase transfer time and may fetch unused bytes.

Cache Memory

A cache is a small, fast semiconductor memory logically between the CPU and main memory. It stores copies of selected instruction and data blocks so that most references avoid the longer DRAM access time.

Typical systems use a small private L1 instruction cache and L1 data cache, a larger L2 cache and a still larger shared L3 cache. On a hit, a valid entry has a tag matching the requested address and the selected word is returned. On a miss, the next hierarchy level supplies a complete line; the requested word is forwarded and the line is installed for reuse.

Cache lookup, tag test, hit return and miss-refill paths. The address is split into tag, index and offset fields, and locality makes hits common.

As the figure shows, an address is interpreted as tag  index  offset. The index selects a line or set, the tag identifies which main-memory block occupies it, and the offset selects the byte or word within the line. A matching tag without a set valid bit is not a hit.

Placement or Mapping

Mapping	Placement rule	Main trade-off
Direct mapped	Each memory block has exactly one possible cache line	Fast, simple and inexpensive, but vulnerable to repeated conflicts
Fully associative	A block may occupy any cache line	Eliminates placement conflicts, but requires costly parallel tag search and replacement choice
Set associative	A block selects one set and may occupy any way in that set	Practical balance among hit time, hardware cost and conflict misses

Cache mapping methods.

Hit Ratio and Average Memory Access Time

If $H$ is hit ratio, $T_c$ is cache lookup time and $T_m$ is the additional main-memory time on a miss, then

$$\begin{aligned} H&=\frac{\text{number of cache hits}}{\text{total memory accesses}},\\ T_{avg}&=H T_c+(1-H)(T_c+T_m)\\ &=\boxed{T_c+(1-H)T_m}. \end{aligned}$$

Note

Example — Cache hit ratio and AMAT

For $H=0.95$, $T_c=2\,\text{ns}$ and $T_m=60\,\text{ns}$,

$$T_{avg}=0.95(2)+0.05(2+60)=\boxed{5\,\text{ns}}.$$

Compared with an idealized $60\,\text{ns}$ DRAM access for every reference, this is about a twelvefold reduction in average access time. The result assumes the stated miss penalty and does not include other stalls.

The equivalent general notation is

$$\boxed{\mathrm{AMAT}=T_{hit}+r_{miss}P_{miss}},$$

where $r_{miss}=1-H$ and $P_{miss}$ is the additional miss penalty. Thus, for $T_{hit}=1\,\text{ns}$, $r_{miss}=0.02$ and $P_{miss}=50\,\text{ns}$,

$$\mathrm{AMAT}=1+0.02(50)=\boxed{2\,\text{ns}}.$$

Miss Types

Miss	Cause	Typical mitigation
Compulsory (cold)	First access to a block; no prior copy can be present	Prefetching or a larger line when spatial locality is strong
Capacity	Active working set is larger than the cache	Larger cache or a smaller/reorganized working set
Conflict	Mapping forces simultaneously useful blocks into the same line or set despite free space elsewhere	More associativity or different placement

The three classical cache-miss causes.

Random access weakens spatial locality; a workload larger than the cache causes capacity misses. In multicore systems, coherence actions can invalidate a line and create additional coherence traffic or misses.

Write Policies

Policy	Operation	Consequence
Write-through	Update cache and next memory level on every hit	Simple memory consistency, but high write traffic; a write buffer is normally used
Write-back	Update cache only and mark the line dirty; write it to the next level when evicted	Lower traffic, but needs dirty bits and more complex replacement/coherence handling
Write-allocate	On a write miss, fetch the line then write in cache	Exploits future locality; commonly paired with write-back
No-write-allocate	On a write miss, send the write downward without filling the cache	Avoids filling with data unlikely to be reused; often paired with write-through

Cache write-policy choices.

Note

Key Point — Cache coherence

When processors cache the same memory block, a coherence protocol must ensure that a core does not continue using an obsolete copy after another core writes the block. A high hit ratio alone is therefore not the whole multicore performance story.

Memory Technologies

RAM and ROM

Random-access memory (RAM) permits direct read/write access to any address but is volatile. Read-only memory (ROM) and its programmable variants retain contents without power and are used for firmware or fixed data.

Type	Storage and refresh	Relative property	Main use
SRAM	Bistable cell; no periodic refresh while powered	Faster, costlier and lower density	Processor cache
DRAM	Capacitor charge; must be periodically refreshed	Slower, cheaper and higher density	Main memory

SRAM and DRAM comparison.

Variant	Defining feature
PROM	User-programmable once; it cannot normally be erased
EPROM	Erased by ultraviolet light and then reprogrammed
EEPROM	Electrically erased and rewritten, commonly at byte granularity
Flash memory	Electrically erased in blocks, giving high density for firmware and solid-state storage

ROM and non-volatile semiconductor variants.

Secondary and Offline Storage

Storage	Characteristics	Typical use
HDD	Magnetic rotating disk with mechanical seek and low cost per gigabyte	Large economical online storage
SSD	Flash based, with no moving parts and low random-access latency; cells have finite write endurance	Operating system, applications and active data
Optical disk	Laser-read or laser-written removable medium	CD, DVD and Blu-ray distribution or archive
Magnetic tape	Very high capacity and low cost, but primarily sequential access	Backup and long-term archive

Common secondary-storage technologies.

Property	Cache	Main memory	Auxiliary storage
Technology	SRAM	DRAM	Flash or magnetic/optical media
CPU access	Hardware tag lookup	Through memory controller	Through I/O and the operating system
Unit moved	Cache line	Byte/word at the interface	Block or file
Persistence	No	No	Yes
Main limit	Capacity, misses and coherence cost	Refresh and finite capacity	High latency, wear or mechanical delay

Cache, main memory and auxiliary storage.

Virtual Memory and Paging

Virtual memory is a hardware-and-operating-system mechanism that gives each process a large private logical address space independent of the amount and placement of physical RAM. With paging, virtual memory is divided into equal-size pages and RAM into frames of the same size.

A virtual address is divided into

$$\boxed{\text{virtual page number (VPN)}\mid\text{page offset}}.$$

The MMU looks for the VPN in a translation lookaside buffer (TLB), a small cache of recent address translations. On a TLB hit, its frame number is combined with the unchanged offset. On a TLB miss, hardware or operating-system software reads the process page table. A TLB miss is therefore not necessarily a page fault: the page-table entry may show that the page is already in RAM.

Field	Purpose
Frame number	Identifies the RAM frame containing a present page
Present/valid bit	Distinguishes a resident legal translation from an absent page; architectures may use separate bits for validity and presence
Protection bits	Permit or forbid read, write, execute and user-mode access
Referenced/accessed	Records recent use for page-replacement decisions
Dirty/modified bit	Records a write so an evicted page can be saved first
Backing-store slot	Identifies where an absent page can be reloaded

Essential page-table-entry fields.

For byte addressing and page size $S$ bytes, the physical address is

$$\boxed{\mathrm{PA}=(\text{frame number}\times S)+\text{offset}}.$$

Virtual-memory translation through the TLB and page table. An illegal or forbidden access raises a protection fault; a legal but nonresident VPN 1 causes a page-fault reload from disk slot S17 into physical frame 2.

Page-Fault Service

If a referenced legal page is absent, the page fault in the figure traps to the operating system:

1. Save enough process state to restart the faulting instruction and verify that the virtual address and requested access are legal.

2. Obtain a free frame or choose a victim using the replacement policy. If the victim is dirty, write it to backing storage before reuse.

3. Read the required page from SSD or disk into the selected frame. The process waits while another process may run.

4. Update the page table, repair or invalidate the affected TLB entry, and restart the faulting instruction so translation is retried.

An illegal address or a forbidden read/write/execute access causes a protection exception and normally a process signal or termination; it must not be treated as an ordinary demand-page reload. Storage service is millions of CPU cycles slower than a cache or RAM access, so even a low page-fault rate can dominate execution time.

Note

Example — Virtual-to-physical address translation

Let virtual addresses be 16 bits and the page size be $4\,\text{KiB}=2^{12}$ bytes. The offset is therefore 12 bits and the VPN is $16-12=4$ bits. For virtual address 0x3ABC,

$$\mathrm{VPN}=\texttt{0x3},\qquad \mathrm{offset}=\texttt{0xABC}.$$

If VPN 3 maps to physical frame 9, then

$$\mathrm{PA}=9(\texttt{0x1000})+\texttt{0xABC} =\boxed{\texttt{0x9ABC}}.$$

The page offset is copied, not translated.

Benefits, Costs and Thrashing

Paging allows a program to use an address space larger than currently assigned RAM, relocates pages without changing program addresses, isolates processes, supports multiprogramming, shares selected pages and applies per-page protection. Its costs include page-table memory, TLB/page-walk overhead, internal fragmentation in partly used final pages and extremely slow faults.

Thrashing occurs when the active working sets of running processes do not fit in available frames. The system repeatedly faults and replaces pages that are needed again almost immediately, so storage traffic rises and useful CPU work collapses. Remedies include allocating more frames, reducing the degree of multiprogramming, using locality-aware replacement and controlling each process by its working set.

Note

Key Point — Hierarchy limitation

The hierarchy lowers average access time; it cannot remove every delay. Large working sets cause cache capacity misses, random access defeats spatial locality, and insufficient RAM can cause page-fault thrashing. Sudden power loss also destroys all volatile levels.

Quick Review

• Hierarchy: registers $\rightarrow$ cache $\rightarrow$ RAM $\rightarrow$ secondary storage trades speed for capacity and cost.

• Cache: uses temporal and spatial locality; a hit returns a matching valid line, while a miss fetches and installs a block.

• AMAT: $T_{hit}+r_{miss}P_{miss}$; always identify whether the stated penalty is additional.

• Paging: maps VPNs to equal-size physical frames; the offset is unchanged.

• TLB miss versus page fault: a TLB miss requests a page-table lookup; a page fault means the legal page is absent from RAM.

Tip

Exam Focus — Memory-system answer

Draw the hierarchy and state its direction of speed, capacity and cost. For a cache problem write the AMAT formula before substitution. For paging, split the address into VPN and offset, find the frame, retain the offset, and describe the complete fault sequence including dirty-victim write-back and restart.