Virtual Memory and Memory Performance

Introduction

Virtual memory is an operating-system abstraction that gives each process the appearance of a large, private, contiguous address space, even when physical memory is limited, fragmented, or shared. The abstraction is implemented by translating virtual addresses into physical addresses and by moving pages between main memory and secondary storage when necessary.

Virtual memory is not merely a method for extending memory capacity. It supports process isolation, controlled sharing, efficient program loading, sparse data structures, memory-mapped files, copy-on-write, and flexible allocation. Its costs include address-translation overhead, page faults, contention for memory bandwidth, and—in poorly managed systems—thrashing.

For AI and machine-learning workloads, memory behavior is especially important. Training and inference may involve large tensors, irregular embedding-table accesses, memory-mapped datasets, multiple worker processes, and non-uniform memory access (NUMA). Performance therefore depends not only on the number of bytes available but also on locality, placement, access patterns, and the cost of misses.

Learning Objectives

By the end of this chapter, students should be able to:

1. Explain demand paging, page tables, translation lookaside buffers, and page faults.

2. Analyze copy-on-write and memory-mapped files.

3. Compare page-replacement algorithms and evaluate their limitations.

4. Apply effective-access-time calculations correctly.

5. Explain frame allocation, locality, working sets, and thrashing.

6. Describe NUMA effects and memory-performance trade-offs.

7. Diagnose memory behavior in operating systems and AI applications.

1. Address Translation and Demand Paging

A virtual address is commonly divided into a virtual page number and a page offset. If the page size is \(2^p\) bytes, the lowest \(p\) bits form the offset. The remaining bits identify the virtual page. A page table maps the virtual page number to a physical frame number. The offset is unchanged during translation.

For example, with 32-bit virtual addresses and 4 KiB pages, the offset contains 12 bits because \(4\text{ KiB}=2^{12}\) bytes. The virtual page number contains 20 bits, so the address space has \(2^{20}\) virtual pages. A physical address is constructed by concatenating the selected frame number with the original 12-bit offset.

A page-table entry commonly contains:

• a frame number;
• a present or valid bit;
• protection bits such as read, write, and execute;
• a reference or accessed bit;
• a dirty bit indicating modification;
• sometimes caching, sharing, or copy-on-write state.

A translation lookaside buffer (TLB) caches recent page-table translations. On a TLB hit, translation is fast. On a TLB miss, the processor or operating system performs a page-table walk, after which the translation may be inserted into the TLB. A valid translation does not guarantee that the page is physically resident; a page-table entry can indicate that the page is absent, producing a page fault.

Demand paging

In demand paging, a page is loaded into a physical frame only when an access requires it. A page-fault sequence is typically:

1. The processor detects an invalid or nonresident page-table entry.

2. Hardware transfers control to the operating system.

3. The operating system verifies that the reference is legal.

4. It obtains a free frame or selects a victim page.

5. If the victim is dirty, it writes the page to storage.

6. It reads the required page from storage.

7. It updates the page table and TLB-related state.

8. It restarts the faulting instruction.

Page faults are extremely expensive relative to ordinary memory references because they may require a storage operation and scheduling activity. Demand paging is therefore beneficial when it avoids loading pages that will never be used, but harmful when an application repeatedly faults.

2. Effective Access Time

A useful simplified model is:

\[

EAT=(1-p)C+pF

\]

where \(p\) is the probability of a page fault per reference, \(C\) is the cost of a normal memory reference, and \(F\) is the total cost of a faulting reference, including trap handling, possible replacement, storage transfer, page-table updates, and restart. The formula assumes that these costs are represented by expected values and that the probabilities are stable over the measured interval.

TLB behavior can be modeled separately. Suppose a TLB lookup takes 5 ns, main-memory access takes 100 ns, and a TLB miss requires an additional page-table memory access. If the TLB hit ratio is 98%, then:

• TLB hit cost: \(5+100=105\) ns;
• TLB miss cost: \(5+100+100=205\) ns.

The expected translation-and-memory cost is:

\[

0.98(105)+0.02(205)=102.9+4.1=107\text{ ns}.

\]

Now assume that the page-fault probability is 0.0008 and that a fault adds approximately 10,000 ns beyond the ordinary reference cost. The additional expected cost is:

\[

0.0008(10{,}000)=8\text{ ns}.

\]

Thus the total expected access time is approximately:

\[

107+8=115\text{ ns}.

\]

This example illustrates two important points. First, arithmetic must distinguish the TLB-miss cost from the page-fault cost. Second, even a very small fault probability can materially affect performance because the penalty is large. Real systems have more complex costs: multi-level page tables, caches, out-of-order execution, parallel memory requests, storage type, and fault clustering all affect the measured result.

3. Copy-on-Write and Efficient Process Creation

Copy-on-write (COW) allows two or more processes to share physical pages until one attempts to modify a shared page. Initially, the operating system maps the same frame into multiple address spaces and marks the mapping read-only or COW-protected. A write causes a protection fault. The kernel then allocates a new frame, copies the old contents, updates the writer’s mapping, and resumes the instruction.

COW is particularly useful for the traditional `fork` operation. A parent and child can initially share most pages, avoiding an immediate full-memory copy. If the child soon executes a new program, much of the apparent duplication is unnecessary and is avoided.

COW has costs and design constraints:

• the first write to each shared page causes a fault and copy;
• reference counts must be maintained safely;
• kernel and hardware page-table behavior must prevent unauthorized writes;
• large pages may increase copying cost when only a small region changes;
• memory pressure can make COW copies compete with application pages.

COW is not the same as ordinary shared memory. Shared memory permits deliberate communication through writable shared pages; COW preserves private logical state after a write.

4. Page Replacement

When no free frame is available, the operating system must select a victim page. A good replacement policy aims to minimize future faults while controlling overhead and respecting protection and sharing constraints.

Major policies

Optimal replacement removes the page whose next use is farthest in the future. It provides a theoretical minimum fault count but requires knowledge of future references, so it is mainly a benchmark.

FIFO removes the page that has been resident longest. It is simple but can suffer from Belady’s anomaly: increasing the number of frames can sometimes increase the number of faults.

LRU removes the page least recently used. It is motivated by temporal locality and has the stack property, so adding frames cannot increase faults under the ideal LRU model. Exact LRU can be expensive because every reference may require metadata updates.

Clock or second-chance replacement approximates LRU using a circular list and a reference bit. A page with its reference bit set receives a second chance; the bit is cleared as the clock hand advances. Clock policies offer a practical balance between quality and overhead.

Aging and working-set variants maintain approximate histories of recent use. They can distinguish pages referenced frequently from pages that have become inactive.

The dirty bit is important. Evicting a clean page generally requires discarding it, whereas evicting a dirty page requires writing it to backing storage. Consequently, a policy may prefer a slightly less recently used clean page over a dirty page, depending on system objectives.

Example of replacement analysis

Consider the reference string 1, 2, 3, 1, 4, 2 with three initially empty frames. Under FIFO, the first three references fault and load 1, 2, and 3. Reference 1 hits. Reference 4 faults and replaces 1, leaving 4, 2, and 3. Reference 2 hits. The total is four faults. Under an algorithm that retained 1 instead of replacing it, the reference to 4 would require a different victim choice; replacement results depend on the policy and exact state, not merely on the number of distinct pages.

Replacement algorithms should be evaluated using fault rate, CPU overhead, scan cost, write-back traffic, fairness, and behavior under multiprogramming—not fault count alone.

5. Frame Allocation and Global Competition

A process needs enough frames to hold its actively reused pages. Common allocation approaches include:

• equal allocation: divide available frames equally among processes;
• proportional allocation: allocate in proportion to process size or declared demand;
• priority allocation: give more frames to higher-priority or latency-sensitive work;
• local replacement: a process replaces only its own pages;
• global replacement: a process may take frames from another process.

Local replacement provides more predictable isolation. Global replacement can improve overall utilization but may allow one process to damage another’s performance. Practical kernels often combine global reclaim with per-process protections, memory-control groups, or working-set targets.

Minimum frame allocation is constrained by architecture and instruction semantics. An instruction that accesses multiple pages may require enough frames for all pages involved in restartable execution. The exact minimum is architecture-dependent and should not be generalized as a fixed number.

6. Locality, Working Sets, and Thrashing

Temporal locality means that recently used data or instructions are likely to be used again soon. Spatial locality means that addresses near a recently used address are likely to be accessed. Sequential code, arrays, and instruction streams often exhibit both forms, while pointer chasing and random hash-table access may exhibit weak locality.

The working set of a process over a window \(\Delta\) is the set of distinct pages referenced during the most recent \(\Delta\) references or time interval. If \(W_i(\Delta)\) is the working-set size of process \(i\), a system can avoid severe paging when:

\[

\sum_i W_i(\Delta) \leq M,

\]

where \(M\) is the number of available frames for those processes. This is a model and not an exact guarantee: working sets change, page-fault service consumes resources, and shared pages may be counted differently.

Thrashing occurs when the system spends a substantial fraction of time servicing page faults rather than executing useful work. It can result from too many active processes, insufficient frames, poor locality, or an allocation policy that ignores changing demand. Symptoms include high page-fault and storage I/O rates, low CPU utilization, long application latency, and repeated eviction and reloading of the same pages.

Possible responses include reducing the degree of multiprogramming, suspending or swapping out a process, allocating frames according to working-set estimates, improving locality, increasing physical memory, or changing the data layout. Increasing concurrency is not always beneficial: beyond the memory-capacity threshold, throughput can decline sharply.

7. Memory-Mapped Files

A memory-mapped file associates file contents with a virtual address range. Accessing a mapped page can cause a page fault that brings file data into memory. Modified private mappings are written back only according to the mapping semantics, while shared writable mappings can provide file-backed communication between processes.

Advantages include demand loading, direct pointer-based access, sharing of physical file pages, and avoiding explicit read-copy-write sequences. Limitations include page-fault latency, alignment and consistency concerns, address-space pressure, and complex behavior when files are truncated or concurrently modified.

A private mapping commonly uses COW: processes initially share file-backed pages, and a write creates a private anonymous page. A shared mapping makes writes visible according to operating-system and filesystem guarantees, but memory mapping should not be treated as a replacement for a carefully designed synchronization protocol.

For large datasets, memory mapping can be effective when access is localized and reused. It can perform poorly for random access over a dataset much larger than RAM, because the workload may generate persistent faults and storage traffic.

8. NUMA and Placement-Aware Memory Management

In a non-uniform memory access (NUMA) system, a processor can access local memory faster or with greater bandwidth than memory attached to another processor or socket. The address space may remain logically shared, but latency and bandwidth depend on placement.

NUMA-aware operating systems attempt to place pages near the processors that use them. First-touch allocation is a common policy: a page is allocated on the NUMA node of the processor that first writes to it. Thread affinity, page migration, interleaving, and explicit placement interfaces can improve locality.

NUMA introduces several trade-offs:

• migrating a page costs bandwidth and CPU time;
• replication improves read locality but complicates coherence and consistency;
• interleaving balances bandwidth but may increase latency for any one processor;
• a single shared data structure may cause remote accesses and coherence contention;
• scheduling a thread away from the node containing its data can reduce performance.

AI workloads often expose NUMA effects through large model parameters, embedding tables, data-loader buffers, and accelerator-host transfers. Benchmarking should measure local and remote bandwidth, tail latency, page placement, and thread affinity rather than relying only on total memory capacity.

9. Memory Performance Trade-offs

Memory design involves competing objectives:

• Page size: large pages reduce page-table and TLB pressure but can increase internal fragmentation and fault granularity. Small pages reduce wasted space and permit finer protection but increase translation overhead.
• Prefetching: fetching likely-needed pages can hide latency, but incorrect predictions waste bandwidth and evict useful data.
• Caching and replacement: retaining data improves reuse, but metadata and scan costs consume resources.
• Compression: compressed memory can increase effective capacity, but compression and decompression consume CPU time.
• Overcommitment: promising more virtual memory than currently exists can improve utilization, but allocation failure or severe reclaim may occur later.
• Isolation versus sharing: private pages improve protection, while sharing reduces duplication and can improve cache use.
• Latency versus throughput: batching and sequential I/O may improve throughput but increase individual request latency.

Performance analysis should therefore use multiple metrics: page faults per second, major versus minor faults, TLB miss rate, memory bandwidth, cache-miss rate, CPU utilization, storage I/O, NUMA remote-access rate, and application-level latency or throughput.

10. Applied Case: Illustrative Recommendation-Service Deployment

Background

Consider an illustrative recommendation service using a large memory-mapped embedding table. Several worker processes serve requests on a two-socket NUMA server. The table is larger than local memory, and requests contain sparse, irregular embedding IDs.

Problem

During peak traffic, CPU utilization falls while major page faults and remote-memory traffic rise. Increasing the number of worker processes makes response time worse rather than better.

Analysis

The embedding accesses have weak spatial locality. Each worker touches a broad portion of the table, so the aggregate working set exceeds available RAM. Global replacement allows workers to evict one another’s useful pages. First-touch placement also places many pages on the node of an initialization thread rather than near the workers that use them. The resulting pattern combines thrashing with NUMA-remote accesses.

Approach

The engineering team can:

1. measure per-process fault rates, working-set estimates, and NUMA remote accesses;

2. reduce worker concurrency until the aggregate active set fits memory more often;

3. partition or shard embeddings according to request and thread locality;

4. initialize pages in parallel using the intended CPU placement;

5. use memory-control policies to prevent one worker group from consuming all reclaimable frames;

6. prefetch only demonstrably predictable batches;

7. retain frequently used or “hot” embeddings in a resident cache;

8. evaluate huge pages selectively, since large pages may waste memory for sparse access.

Outcome

The expected improvement is not obtained from a single replacement algorithm. It results from matching placement, concurrency, data layout, and admission policies to the workload’s locality. Evaluation should compare tail latency and throughput as well as average fault rate.

Learning points

Virtual memory performance is a system property. A workload can have sufficient nominal memory yet perform poorly because its working set is too large, its access pattern is random, or its pages are remote. AI engineers should profile locality and placement before simply adding threads or increasing batch size.

11. Challenges, Security, and Governance

Virtual memory supports isolation, but implementation errors can create security vulnerabilities. Page permissions must prevent writable and executable mappings from being combined unnecessarily. Sensitive pages should be cleared before reuse, and discarded or swapped pages may require encryption or secure handling. Shared pages, memory deduplication, speculative execution, and timing differences can create side channels.

Operational governance should define resource limits, denial-of-service protections, logging of memory pressure, and policies for sensitive data in swap or mapped files. In regulated applications, data retention and confidentiality requirements may apply to memory dumps, crash files, checkpoint data, and temporary storage.

12. Contemporary Developments and Best Practices

Modern systems increasingly use multi-level translation, huge pages, compressed memory, memory-tiering, persistent memory, container memory limits, and hardware-assisted virtualization. These features can improve capacity or reduce translation overhead, but each introduces workload-dependent trade-offs.

Best practices include:

• measure before tuning;
• distinguish minor faults from storage-backed major faults;
• monitor TLB, cache, bandwidth, and NUMA metrics together;
• preserve locality through data layout and thread affinity;
• limit concurrency when aggregate working sets exceed memory;
• use huge pages selectively and validate fragmentation effects;
• protect latency-sensitive workloads with explicit memory reservations;
• test under realistic load, including tail latency and fault bursts;
• treat memory mapping, COW, and shared memory as synchronization and security mechanisms, not merely performance features.

Chapter Summary

Virtual memory separates a process’s logical address space from physical memory and enables isolation, sharing, demand loading, and efficient process creation. Demand paging loads pages when referenced, but page faults are expensive; effective-access-time calculations must account for both translation behavior and fault probability. Copy-on-write postpones copying until modification. Page-replacement policies such as FIFO, LRU, and Clock make different trade-offs in fault rate, metadata cost, and predictability. Frame allocation determines how processes compete for memory.

Locality explains why a relatively small working set can support fast execution. When the aggregate working sets exceed available frames, thrashing may occur. Memory-mapped files provide convenient file-backed virtual memory but can fail under random, oversized access patterns. NUMA adds placement-dependent latency and bandwidth, making affinity and page placement important. Professional memory optimization requires joint analysis of faults, TLB behavior, cache locality, bandwidth, storage, concurrency, and application-level performance.

Key Terms

Virtual memory: An abstraction providing processes with logical address spaces larger or different from physical memory.

Virtual page: A fixed-size region of a virtual address space.

Physical frame: A fixed-size region of physical memory that can hold a page.

Page table: A data structure mapping virtual pages to physical frames.

TLB: A cache of recent virtual-to-physical address translations.

Demand paging: Loading a page only when an access requires it.

Page fault: An exception caused when a required page is not currently accessible or resident.

Copy-on-write: Sharing pages until a write requires a private copy.

Page replacement: Selecting a resident page to evict when a frame is needed.

FIFO: A replacement policy that removes the page resident longest.

LRU: A policy that removes the least recently used page.

Clock: An efficient approximation to LRU using reference bits.

Working set: The distinct pages actively referenced during a defined recent window.

Locality: The tendency of programs to reuse nearby or recently accessed data.

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

Memory-mapped file: A file associated with a process’s virtual address range.

NUMA: A system in which memory-access cost depends on processor and memory location.

Page migration: Moving a page between memory nodes or locations.

Dirty page: A modified page that differs from its backing copy.

Effective access time: Expected time per memory reference under specified costs and probabilities.

Review Questions

Short Answer Questions

1. What information is typically stored in a page-table entry?

2. Why does a TLB improve virtual-memory performance?

3. What event triggers a copy-on-write page fault?

4. Define a working set.

5. State two symptoms of thrashing.

Long Answer Questions

1. Explain the complete sequence of events in handling a demand-paging fault.

2. Compare FIFO, LRU, and Clock replacement in terms of assumptions, overhead, and performance.

3. Explain how frame-allocation policy affects multiprogrammed systems.

4. Discuss the advantages and limitations of memory-mapped files.

5. Explain why NUMA-aware placement is important for large AI workloads.

Analytical / Application Questions

1. A system has a 5 ns TLB lookup, 100 ns memory access, a 98% TLB hit ratio, and a page-fault probability of 0.0008. If a TLB miss costs two memory accesses after the lookup and a fault adds 10,000 ns, calculate the approximate expected access time and state your assumptions.

2. An application’s working set grows beyond available frames as the number of worker processes increases. Explain why throughput may decline and propose three interventions.

3. A memory-mapped embedding table produces random accesses across a NUMA server. Design an experiment to distinguish the effects of page faults, NUMA-remote accesses, and insufficient locality.

Multiple Choice Questions with Answers

Question 1

Which event normally causes a copy-on-write page fault?

A. A process reads a shared read-only page

B. A process writes to a shared COW-protected page

C. A TLB successfully translates a page

D. A clean page is accessed twice

Correct Answer: B. A process writes to a shared COW-protected page

Question 2

With a 98% TLB hit ratio, a 105 ns hit cost, and a 205 ns miss cost, what is the expected cost before page-fault effects?

A. 102 ns

B. 105 ns

C. 107 ns

D. 205 ns

Correct Answer: C. 107 ns

Question 3

Which replacement policy is primarily a theoretical benchmark because it requires future-reference knowledge?

A. FIFO

B. Clock

C. LRU

D. Optimal replacement

Correct Answer: D. Optimal replacement

Question 4

What is the principal purpose of a dirty bit?

A. To record whether a page has been modified

B. To identify the virtual page number

C. To indicate a TLB hit

D. To record CPU priority

Correct Answer: A. To record whether a page has been modified

Question 5

Thrashing occurs when a system:

A. Has no virtual address space

B. Spends excessive time servicing page faults

C. Uses only clean pages

D. Disables the TLB

Correct Answer: B. Spends excessive time servicing page faults

Question 6

Which condition is represented by the working-set model?

A. The sum of active page sets should be compatible with available frames

B. Every process must receive exactly the same number of frames

C. All pages must be resident before execution begins

D. A page must be larger than a frame

Correct Answer: A. The sum of active page sets should be compatible with available frames

Question 7

What is a major NUMA performance concern?

A. All memory accesses have identical latency

B. Remote-node accesses may have higher latency and lower bandwidth

C. NUMA eliminates page tables

D. NUMA prevents thread migration

Correct Answer: B. Remote-node accesses may have higher latency and lower bandwidth

Question 8

Which statement best describes a private writable memory-mapped file?

A. Every write must immediately modify all processes’ mappings

B. A write can use copy-on-write to create private changes

C. The mapping cannot cause page faults

D. The file is always copied fully into RAM

Correct Answer: B. A write can use copy-on-write to create private changes

Question 9

If a page-fault probability is 0.0008 and each fault adds 10,000 ns in a simplified model, what is the expected added cost?

A. 0.8 ns

B. 8 ns

C. 80 ns

D. 8,000 ns

Correct Answer: B. 8 ns

Question 10

Which policy approximates LRU using a circular scan and reference bits?

A. FIFO

B. Optimal

C. Clock

D. Random allocation

Correct Answer: C. Clock