Memory Organization and Hierarchy

Introduction

A computer’s processor can execute instructions extremely quickly, but no practical memory technology provides unlimited capacity, very low cost, and processor-level speed at the same time. Computer systems therefore organize storage into a hierarchy. Small, fast, expensive storage is placed close to the processor, while large, slower, less expensive storage is placed farther away.

Memory organization concerns how data and instructions are arranged, accessed, protected, transferred, and translated. A sound understanding of memory is essential for system performance, operating-system operation, embedded-system design, server administration, and network-device engineering.

The hierarchy normally includes processor registers, cache memory, main memory, non-volatile firmware memory, secondary storage, and sometimes tertiary or cloud storage. The hierarchy works effectively because programs usually demonstrate locality: recently used data is likely to be used again, and data near recently used data is likely to be accessed soon.

Learning Objectives

After studying this chapter, the reader should be able to:

• distinguish registers, cache, RAM, ROM, and secondary storage;
• explain temporal and spatial locality;
• describe cache organization, mapping, and replacement policies;
• calculate basic cache performance measures;
• explain virtual memory, paging, address translation, and translation lookaside buffers;
• describe memory protection mechanisms;
• evaluate memory-performance trade-offs in practical systems.

1. The Memory Hierarchy

The principal levels of a conventional hierarchy are:

Moving downward generally increases capacity and decreases cost per bit, but access time increases. The hierarchy is not merely a collection of independent devices. Hardware and operating-system mechanisms transfer blocks of information between levels so that the processor can observe an apparently large and fast memory.

A memory access has several important characteristics:

• Capacity: the amount of information stored.
• Access time: the interval between requesting data and receiving it.
• Transfer rate: the amount of data transferred per unit time.
• Latency: the delay before useful transfer begins.
• Cost per bit: the economic cost of storage capacity.
• Volatility: whether data is lost when power is removed.

Registers

Registers are the smallest and fastest storage elements visible to the processor. General-purpose registers hold operands, addresses, and intermediate results. Special-purpose registers include the program counter, instruction register, stack pointer, status or flags register, and memory-address or memory-data registers in some architectures.

A register file may contain multiple read ports and write ports so that an instruction can obtain several operands and write a result in one cycle. Increasing the number of registers can reduce memory traffic, but registers occupy valuable processor area and require instruction formats capable of naming them.

Cache Memory

Cache memory is usually built from static RAM. It stores copies of recently or frequently accessed blocks from main memory. A cache is divided into lines or blocks. Each line contains a data block and metadata such as a tag, valid bit, and sometimes a dirty bit and replacement information.

A cache hit occurs when the requested block is present. A cache miss occurs when it is absent. On a miss, the required block is fetched from a lower level, often replacing another block.

RAM

Random-access memory permits approximately uniform access to any address, unlike sequential storage. Dynamic RAM stores each bit using a capacitor and transistor. Because charge leaks, DRAM requires periodic refreshing. DRAM is dense and relatively inexpensive, making it suitable for main memory.

Synchronous DRAM operates in coordination with a memory clock. Modern systems use multiple channels, ranks, banks, burst transfers, and sophisticated memory controllers to improve throughput. Main-memory latency is still much greater than register or cache latency, which is why cache effectiveness is important.

ROM and Non-Volatile Memory

Read-only memory originally referred to memory programmed permanently during manufacture. Modern systems commonly use programmable non-volatile technologies:

• PROM can be programmed once.
• EPROM can be erased using ultraviolet light and reprogrammed.
• EEPROM can be electrically erased and programmed.
• Flash memory is electrically erasable in blocks and is widely used for firmware and storage.

Firmware memory retains data without power. It stores boot firmware, device-controller code, and configuration data. Flash memory has finite write endurance, so controllers use wear levelling and error correction.

Secondary Storage

Secondary storage includes solid-state drives, hard-disk drives, memory cards, and optical media. It is persistent and has much greater capacity than RAM. SSDs have low mechanical latency because they contain no moving heads, but flash pages are written and erased in different-sized units. SSD controllers therefore perform garbage collection, wear levelling, bad-block management, and error correction.

Hard-disk performance depends on seek time, rotational latency, and transfer time. A simplified access-time model is:

Here, T_access is total access time; T_seek is head-positioning time; T_rotation is rotational waiting time; T_transfer is data-transfer time; and T_controller is controller and interface overhead. This model applies mainly to magnetic disks and is not appropriate for SSDs, which have no seek or rotational terms.

2. Locality of Reference

The hierarchy depends on the observation that program references are not random.

Temporal locality means that an item accessed recently is likely to be accessed again soon. Loop counters, frequently used variables, and instructions inside loops demonstrate temporal locality.

Spatial locality means that addresses near a recently accessed address are likely to be accessed soon. Sequential instruction execution, arrays, and records demonstrate spatial locality.

A third useful concept is sequential locality, a strong form of spatial locality in which addresses are accessed in increasing or decreasing order.

For example, the following loop has both kinds of locality:

for i = 0 to 999:
    total = total + array[i]

The variable total has temporal locality because it is repeatedly used. Consecutive elements of array have spatial locality. A cache line containing several adjacent elements can therefore satisfy many requests after one memory fetch.

Locality is influenced by program structure, data layout, compiler optimization, access stride, working-set size, and multithreading. Poor locality can reduce performance even when the processor itself is powerful.

3. Cache Organization

A memory address is commonly divided into three logical fields:

1. Block offset: identifies a byte or word within a cache block.
2. Index or set field: identifies a cache line or set.
3. Tag: identifies which memory block currently occupies that location.

If a cache has C bytes of data capacity, block size B bytes, and associativity A, then the number of sets is:

If the physical or virtual address width is m bits, the block offset requires:

bits, assuming B is a power of two. The set-index field requires:

bits, assuming S is a power of two. The remaining tag width is:

These equations describe a conventional power-of-two cache and assume byte-addressable memory.

Direct-Mapped Cache

In a direct-mapped cache, each memory block can occupy exactly one cache line. The set index selects that line, and the tag determines whether the line contains the requested block. Direct mapping is simple and fast, but two heavily used blocks that map to the same line can repeatedly evict each other. This is called a conflict miss.

Fully Associative Cache

In a fully associative cache, a memory block may occupy any cache line. The cache compares the requested tag with all valid tags, usually in parallel. This greatly reduces conflict misses but requires more comparison hardware and replacement logic. Fully associative organization is common for small structures such as translation lookaside buffers.

Set-Associative Cache

A set-associative cache divides lines into sets. A block maps to one set but may occupy any of the lines, or ways, in that set. An A-way cache permits A possible locations within each set. Set associativity provides a practical balance between speed, hardware cost, and miss rate.

Cache Miss Types

• Compulsory miss: the first access to a block.
• Capacity miss: the cache cannot hold the program’s active working set.
• Conflict miss: blocks compete for the same location in a non-fully-associative cache.
• Coherence miss: in a multiprocessor, another processor’s write invalidates a cached copy.

Replacement Policies

When all candidate locations are occupied, the cache must choose a victim line.

• Least recently used (LRU): replaces the line unused for the longest time. It can be effective but becomes expensive at high associativity.
• First-in, first-out (FIFO): replaces the oldest line, regardless of recent use.
• Random: selects a line pseudo-randomly; it is simple and can avoid some pathological patterns.
• Pseudo-LRU: approximates LRU with less hardware.

A write policy determines how stores update the hierarchy. Write-through immediately sends a write to the next level and may use a write buffer. Write-back updates only the cache initially and marks the line dirty; the line is written to lower memory when evicted. Write-back reduces traffic but requires dirty-bit management and coherence control.

For a write miss, write-allocate first loads the block into the cache, while no-write-allocate writes directly to the lower level. The best combination depends on workload and architecture.

4. Measuring Cache Performance

The average memory access time can be expressed as:

where AMAT is average memory access time, T_hit is the cache-hit time, MR is the miss rate, and P_miss is the miss penalty. The miss rate is the fraction of accesses that miss, and the miss penalty is the additional time required after a miss. This equation assumes one cache level and a constant average penalty.

For multiple cache levels, a two-level form is:

Here, T_L1 and T_L2 are hit times at the first and second caches; MR_L1 and MR_L2 are local miss rates; and P_L2 is the penalty after an L2 miss. The definition of miss rate must be stated carefully: local L2 miss rate is measured among L2 accesses, not among all processor accesses.

Worked Example

Suppose a cache has a hit time of 2 ns, a miss rate of 5%, and a miss penalty of 40 ns. Then:

Thus, the average access takes 4 ns under the stated assumptions. Reducing the miss rate to 2% while leaving other values unchanged gives:

This illustrates why locality and cache capacity can be more valuable than a small reduction in hit time.

5. Virtual Memory

Virtual memory allows each process to use a virtual address space that is larger, more flexible, and more isolated than its directly assigned physical memory. The operating system and memory-management unit translate virtual addresses into physical addresses.

Virtual memory provides:

• process isolation;
• controlled sharing of code and data;
• relocation of programs in physical memory;
• demand loading of pages;
• support for memory-mapped files;
• a larger apparent address space than installed RAM.

Virtual memory does not make storage faster. If a page must be fetched from secondary storage, the delay is many orders of magnitude greater than a cache miss. Effective systems avoid frequent paging through adequate RAM, good workload management, and appropriate page-replacement policies.

Paging

In paging, virtual memory is divided into fixed-size pages and physical memory into same-sized frames. A page table maps virtual page numbers to physical frame numbers. The page offset remains unchanged during translation.

For a virtual address with v bits and page size 2^p bytes, the offset uses p bits and the virtual page number uses v − p bits. The physical address is formed by replacing the virtual page number with the physical frame number.

A page-table entry may contain:

• frame number;
• present or valid bit;
• read, write, and execute permissions;
• accessed/reference bit;
• dirty/modified bit;
• user/supervisor privilege information;
• caching or memory-type attributes.

A page fault occurs when a referenced page is not currently in physical memory. The operating system must obtain a free frame or select a victim page, write it to storage if dirty, load the required page, update the page table, and restart the interrupted instruction.

Translation Lookaside Buffer

A translation lookaside buffer (TLB) is a small, fast cache of recent virtual-to-physical translations. On a TLB hit, translation is obtained without a page-table memory walk. On a TLB miss, hardware or software performs a page-table walk, unless the page is invalid, in which case a page fault may occur.

A TLB therefore improves address-translation performance but introduces another cache whose entries require replacement and invalidation. Context switches may require flushing TLB entries or using address-space identifiers to distinguish processes.

Page-Replacement Policies

When no free frame exists, the operating system chooses a victim page. Common policies include FIFO, LRU or its approximations, and the clock or second-chance algorithm. A good policy attempts to retain the working set—the pages actively needed by a process during a period of execution.

Excessive page faults cause thrashing, in which the system spends more time moving pages than executing programs. Thrashing may result from insufficient RAM, too many concurrent processes, or poor locality.

6. Address Translation and Protection

Address translation is both a performance function and a security boundary. A typical access proceeds as follows:

1. The processor generates a virtual address.
2. The TLB is searched using the virtual page number and process identity.
3. If the translation is found, permissions are checked.
4. The physical frame number is combined with the page offset.
5. The cache and memory system access the physical or appropriately tagged address.
6. If translation is absent, a page-table walk is attempted.
7. If the page is not present or permission is violated, an exception occurs.

Memory protection prevents a user process from reading or modifying another process’s memory or privileged operating-system regions. Read, write, and execute permissions support the principle of least privilege. A page marked non-executable helps reduce certain code-injection attacks, while guard pages can detect stack overflow.

Protection is not perfect by itself. Hardware, operating systems, compilers, and applications must cooperate. Side-channel attacks such as cache-timing attacks exploit information revealed by shared microarchitectural resources even when ordinary page permissions are correctly configured. Mitigations may include isolation, constant-time algorithms, cache partitioning, speculative-execution controls, and timely security updates.

7. Performance Trade-offs and Design Decisions

Memory design involves competing objectives:

• Larger caches reduce capacity misses but may increase hit time, power, and chip area.
• Larger blocks exploit spatial locality but waste bandwidth when locality is poor.
• Higher associativity reduces conflict misses but increases tag-comparison cost.
• Write-back caching reduces traffic but complicates consistency and recovery.
• More RAM reduces paging but increases cost and energy consumption.
• SSDs provide low latency and high I/O operations per second, but flash has endurance limits.
• Magnetic disks offer economical capacity but have mechanical latency.
• Strong protection and isolation improve security but can increase translation and context-switch overhead.

System designers should measure a representative workload rather than optimize a single synthetic benchmark. Important metrics include cache hit rate, miss penalty, memory bandwidth, page-fault rate, TLB miss rate, storage latency, queue depth, energy use, and cost per capacity.

Applied Case: Improving a Database Server’s Memory Performance

Background

An illustrative database server has a multi-level CPU cache, 64 GB of RAM, and solid-state storage. Administrators observe high CPU utilization, increasing query latency, and frequent storage reads.

Problem

Performance monitoring shows that the database index is larger than available RAM. Queries scan records in an inefficient order, producing poor spatial locality. The system also experiences TLB misses because the workload uses a very large memory region with scattered access patterns.

Analysis

The server’s problem is not simply processor speed. A high cache-miss rate increases average memory access time, while insufficient RAM causes page reclamation and storage traffic. Random index access also limits the benefit of fetching large blocks.

Approach and Solution

The administrators:

1. add RAM so the active database working set remains resident;
2. reorganize indexes and query plans to encourage sequential access;
3. align frequently accessed records with useful cache-line boundaries;
4. monitor cache, TLB, and page-fault statistics;
5. reserve sufficient memory for the operating system and other services;
6. configure storage and database write policies consistently;
7. retain backups because caching and redundancy do not replace persistence.

Outcome

The larger resident working set reduces page faults. Improved access order increases spatial locality, and query changes reduce unnecessary data movement. Latency becomes more predictable even though the processor clock frequency is unchanged.

Learning Points

Memory performance is a system property. Cache organization, data structures, operating-system paging, database algorithms, and storage configuration interact. A local optimization can be harmful if it increases memory traffic elsewhere.

Contemporary Developments

Modern processors commonly use several cache levels, out-of-order execution, hardware prefetching, non-uniform memory access, and simultaneous multithreading. Hardware prefetchers predict future accesses and fetch data before it is requested, but inaccurate predictions consume bandwidth and cache capacity.

High-performance servers may use NUMA architectures, in which access time depends on the processor socket and memory location. Operating systems and applications should place threads and data carefully.

Persistent memory and storage-class memory seek to combine some properties of memory and storage, although questions of endurance, consistency, software support, and cost remain important. AI workloads have increased demand for high-bandwidth memory and specialized accelerator memory. Such systems often trade capacity, bandwidth, precision, and energy efficiency.

Best Practices

• Keep frequently used data compact and contiguous where possible.
• Use data structures that match access patterns rather than choosing solely for programming convenience.
• Measure cache misses, TLB misses, page faults, and storage latency.
• Avoid unnecessary copying between buffers and protection domains.
• Select page sizes with awareness of TLB reach and fragmentation.
• Use memory permissions deliberately: writable data need not be executable.
• Plan RAM capacity around the active working set, not merely total installed software.
• Treat SSD endurance, backup, encryption, and secure deletion as operational concerns.
• Consider locality and bandwidth as well as nominal processor frequency.

Chapter Summary

Computer memory is organized as a hierarchy because no single technology simultaneously offers maximum speed, capacity, persistence, and low cost. Registers provide immediate processor storage; caches exploit locality; DRAM holds active programs; non-volatile memory stores firmware; and secondary storage provides persistent capacity.

Cache performance depends on block size, capacity, associativity, mapping, replacement, and write policy. Direct-mapped, fully associative, and set-associative caches offer different trade-offs. Average memory access time combines hit time, miss rate, and miss penalty.

Virtual memory separates a process’s virtual address space from physical memory. Paging maps virtual pages to physical frames, while the TLB accelerates repeated translations. Page faults, replacement policies, and working-set behavior determine whether virtual memory supports performance or causes thrashing.

Memory protection uses permissions, privilege levels, page tables, and hardware checks to enforce isolation. Practical memory engineering requires balancing speed, capacity, cost, energy, security, reliability, and workload locality.

Key Terms

Register: Small, high-speed storage location inside the processor.

Cache: Fast memory that stores copies of recently or frequently used blocks.

Cache line: The unit of data transferred between a cache and a lower memory level.

Hit: An access satisfied by the searched memory level.

Miss: An access for which the required block is absent.

Temporal locality: The tendency to reuse recently accessed items.

Spatial locality: The tendency to access addresses near a recently accessed address.

DRAM: Dense dynamic memory requiring periodic refresh.

SRAM: Fast static memory commonly used for caches.

ROM: Non-volatile memory traditionally intended primarily for reading.

Flash memory: Electrically programmable and erasable non-volatile memory.

Virtual memory: An abstraction that maps process addresses to physical memory.

Page: Fixed-size unit of virtual memory.

Frame: Fixed-size unit of physical memory holding a page.

Page table: Data structure mapping virtual pages to physical frames.

TLB: Cache of recent virtual-to-physical address translations.

Page fault: Exception generated when a required page is not resident or access is invalid.

Thrashing: Excessive paging that leaves little time for useful execution.

Write-back: Cache policy that delays lower-level updates until a modified line is evicted.

NUMA: Architecture in which memory access time depends on processor and memory location.

Review Questions

Short Answer Questions

1. Why is a memory hierarchy necessary in computer systems?
2. Distinguish temporal locality from spatial locality.
3. What information is stored in a typical cache-line tag structure?
4. What is the purpose of a translation lookaside buffer?
5. Define a page fault and state one possible cause.

Long Answer Questions

1. Compare direct-mapped, fully associative, and set-associative caches.
2. Explain how write-through and write-back cache policies differ.
3. Describe the steps involved in translating a virtual address into a physical address.
4. Explain how paging provides both flexibility and process isolation.
5. Discuss the major performance and cost trade-offs in designing a memory hierarchy.

Analytical / Application Questions

1. A cache has a 3 ns hit time, a 4% miss rate, and a 50 ns miss penalty. Calculate its AMAT using the single-level formula and explain the result.
2. A program accesses a large array sequentially and then accesses a linked list whose nodes are scattered throughout memory. Compare the likely cache behavior of the two phases.
3. A server experiences frequent page faults despite having a fast processor. Propose a diagnostic procedure and at least three corrective actions.

Multiple Choice Questions with Answers

Question 1

Which storage level is normally fastest and smallest?

A. Secondary storage

B. Main memory

C. Processor registers

D. Firmware flash

Correct Answer: C. Processor registers

Question 2

Which situation best demonstrates temporal locality?

A. Reading consecutive array elements

B. Repeatedly updating the same loop counter

C. Accessing randomly distributed records

D. Loading a program from an SSD

Correct Answer: B. Repeatedly updating the same loop counter

Question 3

In a set-associative cache, a memory block maps to:

A. Any line in the entire cache

B. Exactly one set but one of several lines within that set

C. Every set simultaneously

D. Only main memory and never the cache

Correct Answer: B. Exactly one set but one of several lines within that set

Question 4

A cache has a 2 ns hit time, a 5% miss rate, and a 40 ns miss penalty. What is its AMAT?

A. 2 ns

B. 2.4 ns

C. 4 ns

D. 42 ns

Correct Answer: C. 4 ns

Question 5

Which cache miss occurs when two frequently used blocks compete for the same direct-mapped line?

A. Compulsory miss

B. Capacity miss

C. Conflict miss

D. Protection miss

Correct Answer: C. Conflict miss

Question 6

What is the principal purpose of a page table?

A. To store cache replacement counters

B. To map virtual pages to physical frames

C. To increase SSD write endurance

D. To store processor instructions permanently

Correct Answer: B. To map virtual pages to physical frames

Question 7

What happens to the page offset during ordinary paging translation?

A. It is discarded

B. It is encrypted by the TLB

C. It remains unchanged

D. It becomes the frame number

Correct Answer: C. It remains unchanged

Question 8

Which event normally causes a page fault?

A. A required page is not currently resident in physical memory

B. A cache hit occurs

C. A register contains zero

D. A write-through cache is used

Correct Answer: A. A required page is not currently resident in physical memory

Question 9

Which policy delays writing a modified cache line to lower memory until eviction?

A. Write-through

B. Write-back

C. No-write-allocate

D. FIFO

Correct Answer: B. Write-back

Question 10

Which feature directly helps prevent a user process from executing data stored on a protected page?

A. An execute-permission control

B. A larger disk capacity

C. A higher cache associativity

D. A rotational-latency reduction

Correct Answer: A. An execute-permission control