7. Memory Management and Virtual Memory

Introduction and Context

Memory management is the operating system function that gives processes the illusion of a private, large, continuous memory space while using finite and shared physical memory. It decides where programs and data are placed, how addresses are translated, which pages remain in main memory, and how access is protected. These decisions affect performance, reliability, security, energy consumption, and the number of processes that can execute concurrently.

A modern process does not normally use physical addresses directly. It generates virtual addresses, which the memory-management unit (MMU) translates into physical addresses. The operating system establishes the translation structures and handles exceptional events such as page faults. This separation allows a process to be relocated, isolated from other processes, and given an address space larger than available RAM. It also makes possible shared libraries, memory-mapped files, copy-on-write processes, and controlled sharing between protection domains.

The central challenge is to balance three objectives: efficient utilization of memory, fast address translation, and strong protection. A policy that maximizes utilization may increase translation overhead; a policy that provides aggressive isolation may reduce sharing; and a policy that keeps many processes active may cause thrashing if their working sets do not fit in memory.

Learning Objectives

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

1. Explain logical, virtual, linear, and physical addresses and the role of the MMU.

2. Compare contiguous allocation, paging, segmentation, and hybrid schemes.

3. Describe page-table organization, translation lookaside buffers, and address-translation paths.

4. Analyze page-replacement algorithms, working sets, locality, and thrashing.

5. Explain copy-on-write, memory mapping, shared memory, and demand paging.

6. Discuss NUMA, huge pages, memory protection, and contemporary allocation issues.

7. Select suitable memory-management strategies for operating-system and application scenarios.

From Allocation to Address Translation

Early systems often used contiguous allocation. Each process occupied one continuous region of physical memory. Relocation registers allowed the operating system to load a process at different physical locations, while a limit register prevented references outside the process’s region. Although simple, contiguous allocation suffers from external fragmentation: free memory becomes divided into holes that may collectively be large enough but not individually suitable for a request.

Allocation policies such as first fit, next fit, best fit, and worst fit choose a hole for a new allocation. First fit generally provides a practical balance between search cost and fragmentation. Best fit may leave many small unusable holes, while worst fit attempts to preserve medium-sized holes but often wastes large regions. Compaction can combine free holes, but it requires relocating allocated blocks and is expensive for large systems.

Paging removes the requirement that a process occupy contiguous physical memory. A virtual address is divided into a page number and an offset. Physical memory is divided into equally sized frames. A page table maps virtual page numbers to physical frame numbers; the offset is copied unchanged. If the page size is 2^d bytes, the lower d address bits are the offset and the remaining bits identify the virtual page.

For example, with a 32-bit virtual address and 4 KiB pages, the offset contains 12 bits and the virtual page number contains 20 bits. A process can therefore have up to 2^20 pages in its virtual address space. If page 37 maps to frame 912, an address within page 37 is translated by replacing the page number with 912 while preserving the 12-bit offset.

Paging introduces internal fragmentation because the final page of a region may be only partially used. It eliminates external fragmentation for page allocation, but page tables consume memory. Large address spaces therefore require hierarchical, hashed, or inverted page-table designs. In a multilevel page table, only portions corresponding to used regions need to be allocated. A virtual address is divided into several indexes and an offset; each index selects an entry at one level.

A translation lookaside buffer (TLB) is a small, fast associative cache of recent virtual-to-physical translations. On a TLB hit, translation can proceed without walking the page table. On a miss, hardware or the operating system performs a page-table walk and generally inserts the result into the TLB. TLB reach—the amount of memory addressable by TLB entries—is approximately the number of entries multiplied by page size. Increasing page size or using multiple page sizes can improve reach, although it may increase internal fragmentation.

A typical translation path is therefore: the processor generates a virtual address; the TLB is searched; on a hit, the frame number is combined with the offset; on a miss, the page table is consulted; if the page is present, the translation is cached; if it is absent, a page fault transfers control to the operating system. A valid page-table entry is not sufficient by itself: permission bits must also allow the requested operation.

Segmentation and Hybrid Address Spaces

Segmentation reflects the programmer’s logical view of memory. A program may be divided into segments such as code, read-only data, writable data, stack, and dynamically allocated objects. A logical address identifies a segment and an offset. A segment table supplies the segment’s base, limit, and access permissions. Segmentation supports meaningful protection and sharing—for example, a code segment can be shared read-only among processes.

Its weakness is external fragmentation because segments vary in size. Paging and segmentation can be combined: segments define logical regions, while each segment is paged into fixed-size units. Several contemporary architectures retain segmentation-related mechanisms, although general-purpose operating systems often use a largely flat virtual address model and rely on paging for practical memory management.

Demand Paging and the Cost of Absence

Demand paging loads a page only when it is referenced. At process start, many pages may be marked not present. A reference to such a page causes a page-fault exception. The operating system checks whether the reference is legal, locates the page in a backing store or file, obtains a free frame or selects a victim page, writes the victim if it is dirty, reads the required page, updates the page table, and restarts the interrupted instruction.

A page fault is much more expensive than a TLB miss because it may involve storage I/O and scheduling. Consequently, virtual memory is beneficial only when the fault rate remains acceptably low. The effective access time can be expressed conceptually as:

EAT = (1 − p) × memory-access time + p × page-fault service time,

where p is the probability of a page fault. Even a small p can dominate the result when page-fault service time is millions of processor cycles relative to an ordinary memory access.

Demand paging also supports file-backed pages. The first access to a mapped file region may bring data into memory; clean pages can later be discarded and reread from the file. Anonymous memory, such as heap and stack pages, has no ordinary file representation and may be backed by swap when necessary.

Replacement, Locality, and Working Sets

When no free frame exists, the operating system must select a page for eviction. The optimal algorithm replaces the page whose next reference is farthest in the future. It is not implementable in a general running system, but it provides a benchmark for other algorithms. First-in, first-out (FIFO) is simple but can display Belady’s anomaly, in which adding frames increases page faults.

Least recently used (LRU) replaces the page that has not been referenced for the longest time. It follows temporal locality: recently used pages are likely to be used again. Exact LRU is expensive, so systems use approximations based on reference or accessed bits, clock algorithms, aging counters, and multi-queue policies. A second-chance or clock algorithm gives recently referenced pages an opportunity to remain in memory while avoiding a complete ordering of all pages.

The working set of a process is the set of pages referenced during a recent window of execution. If the window is too small, the working set omits useful pages; if too large, it includes pages no longer relevant. The working-set model connects memory allocation with program behavior: a process should receive enough frames to contain its current working set, otherwise it will fault repeatedly while making little progress.

Thrashing occurs when the system spends more time servicing page faults than executing useful instructions. It commonly results from excessive multiprogramming, insufficient frames, poor locality, or an inappropriate replacement policy. Increasing the number of runnable processes may initially improve CPU utilization, but once the aggregate working sets exceed available frames, performance collapses. Operating systems can respond by reducing the degree of multiprogramming, suspending processes, reserving memory for critical workloads, or using working-set and page-fault-frequency controls.

Global replacement allows a process to take frames from another process and can improve overall utilization, but it may make one process’s performance unpredictable. Local replacement restricts victims to the process’s own allocation and provides stronger isolation. The choice is a policy decision involving fairness, throughput, latency, and workload requirements.

Copy-on-Write, Mapping, and Sharing

Copy-on-write (COW) allows multiple address spaces to refer initially to the same physical page. The pages are marked read-only. If a process attempts to write, the operating system handles a protection fault, allocates a new frame, copies the page, updates the writer’s page table, and permits the write. The technique is especially useful when a process creates a child and the child immediately executes another program: copying every page eagerly would waste time and memory.

Memory mapping associates a virtual address range with a file or an anonymous memory object. A mapped file can be accessed through ordinary loads and stores rather than explicit read and write system calls. Mapping is useful for shared libraries, persistent data structures, large files, interprocess communication, and zero-copy data paths. However, applications must understand consistency, synchronization, file-size changes, eviction, and the distinction between private and shared mappings. A private mapping commonly uses COW, whereas a shared mapping makes modifications visible through the shared object subject to system semantics.

Shared memory can provide high-throughput communication because processes exchange data through pages rather than copying messages through the kernel. It also introduces synchronization and security responsibilities. Data races, stale protocols, insufficient bounds checks, and unintended inheritance of mappings can produce serious defects.

Memory Protection and Isolation

Protection begins with the distinction between user mode and kernel mode. User processes cannot normally modify page tables, access kernel-only pages, or execute privileged instructions. Page-table entries commonly include present, writable, user-accessible, accessed, dirty, and execute-disable or no-execute attributes. These bits allow a system to implement read-only code, non-executable data, guard pages, and isolated kernel regions.

A guard page is an unmapped or protected page placed beside a stack or sensitive region. An access beyond the valid boundary generates a fault rather than silently corrupting another object. Address-space layout randomization (ASLR) varies the locations of stacks, libraries, heaps, and executables, making exploitation less predictable. Non-executable memory, often called W^X in policy form, attempts to ensure that a page is writable or executable but not both at the same time, subject to legitimate runtime requirements such as managed-language compilation.

Protection must cover more than ordinary page permissions. DMA-capable devices require an IOMMU so that device-generated addresses are also constrained. Kernel interfaces must validate user-provided addresses and lengths. Speculative-execution vulnerabilities demonstrate that architectural permission checks do not automatically eliminate microarchitectural information leakage; mitigations may require hardware features, isolation, or changes to kernel mappings.

NUMA and Huge Pages

In a non-uniform memory access (NUMA) system, processors have different access costs depending on the location of memory. A thread running on one socket usually accesses its local memory more quickly than memory attached to another socket. NUMA-aware allocation attempts to place data near the processors that use it. First-touch policies allocate a page on the node where it is first written, while explicit placement and migration policies allow applications or the operating system to refine locality.

NUMA creates a tension between locality and load balancing. Moving a thread to its data may be better than moving large data structures to the thread, but a workload with changing access patterns may require migration. Poor placement can cause remote-memory traffic, queue contention, and unpredictable latency. Performance analysis should therefore examine locality, bandwidth, page migration, and thread affinity rather than CPU utilization alone.

Huge pages increase the amount of memory covered by one page-table entry and TLB entry. They can reduce page-table memory, TLB misses, and page-walk overhead, which is valuable for databases, virtual machines, scientific workloads, and large in-memory services. Their disadvantages include internal fragmentation, allocation difficulty, longer fault or zeroing operations, and reduced flexibility when only a small portion is active. Transparent huge-page mechanisms automate selection but may introduce latency through promotion, splitting, or compaction. Explicit huge-page pools provide predictability at the cost of administrative complexity.

An Applied Case: Stabilizing a Memory-Intensive Analytics Service

Background

Consider an illustrative online analytics service running on a multi-socket server. Each worker process maintains a large in-memory index and maps several data files. The service initially performs well with a small number of workers but becomes erratic after a deployment increases concurrency.

Situation and Problem

Monitoring shows high page-fault activity, falling throughput, and large variation in request latency. CPU utilization is moderate rather than saturated. Some workers are frequently descheduled while waiting for storage. The machine has sufficient total virtual address space, but physical memory is smaller than the combined active indexes and mapped regions.

Analysis

The performance symptoms indicate memory pressure and possible thrashing rather than a CPU bottleneck. Profiling reveals that each worker receives too few frames for its active index. A global replacement policy allows pages belonging to one worker to displace pages heavily used by another. The service also uses a page size that produces substantial TLB activity. On a NUMA machine, several workers are scheduled on remote sockets relative to their most frequently accessed data.

Approach and Strategy

The operations team first reduces concurrency to keep the aggregate working sets within physical memory. It then measures page-fault frequency, resident-set sizes, dirty-page rates, and NUMA-local versus remote accesses. Workers are pinned more carefully, and data initialization is arranged to support first-touch placement. Large, stable index regions are evaluated for huge-page use, while small irregular allocations remain on ordinary pages.

The service changes its file-mapping policy so that private mappings are used only where COW semantics are intended. Shared mappings are protected by explicit synchronization. Memory limits are configured per service group to prevent one workload from consuming all reclaimable memory. Finally, dashboards alert on major faults, reclaim activity, swap behavior, TLB-related performance counters, and allocation failures rather than relying on free-memory values alone.

Outcome

The revised configuration reduces fault frequency and latency variance. Throughput improves not because the processors became faster, but because workers spend more time executing useful instructions. NUMA placement reduces remote traffic, while selective huge pages improve translation efficiency without imposing them on every allocation.

Learning Points

The case illustrates that “available memory” is not a sufficient diagnostic measure. The relevant questions are whether active working sets fit, whether pages are placed near their users, whether translation structures are effective, and whether reclamation is disrupting locality. Memory management is therefore both an operating-system concern and an application-architecture concern.

Professional Practices, Risks, and Governance

Engineers should measure before changing page size, replacement settings, or swapping policy. A low free-memory value may be normal because the kernel uses memory for cache; conversely, apparently free memory may not prevent latency if allocation requires expensive compaction. Capacity planning should consider peak resident sets, mapped files, kernel memory, page tables, device buffers, and NUMA distribution.

Common mistakes include confusing virtual size with resident memory, assuming a mapped file is always resident, treating a TLB miss as a page fault, using huge pages indiscriminately, and disabling swapping without understanding its effect on workload isolation. Applications should release unused mappings, avoid accidental retention of large object graphs, control allocation sizes, and use access patterns that respect locality.

Memory handling also has governance implications. Sensitive data may remain in RAM, swap, crash dumps, or mapped files after logical deletion. Systems handling credentials or regulated information may require zeroization, restricted core dumps, encrypted swap or storage, secure page sharing policies, and audited access controls. Isolation boundaries must be validated in containers and virtual machines because page tables, shared kernels, deduplication, and speculative hardware behavior can affect confidentiality.

Current Developments and Best Practices

Contemporary systems increasingly combine hardware page-table support, multiple page sizes, memory control groups, tiered memory, compression, and remote-memory fabrics. Memory compression can postpone storage I/O but consumes CPU and may introduce latency. Persistent or byte-addressable memory technologies raise questions about durability, ordering, recovery, and whether conventional paging assumptions remain appropriate. Virtual machines add another translation layer, so nested page tables and TLB behavior become important to performance.

Effective practice follows several principles:

• Separate virtual address size, committed memory, resident memory, and physical capacity during analysis.
• Use locality-aware allocation and scheduling on NUMA systems.
• Choose huge pages selectively after measuring TLB and fragmentation effects.
• Protect code, data, stacks, and kernel regions with least-privilege permissions.
• Monitor page-fault frequency, reclaim, swap, TLB behavior, fragmentation, and remote accesses.
• Treat memory mapping and shared memory as synchronization and security interfaces, not merely performance features.
• Use working-set or admission-control reasoning when increasing concurrency.

Chapter Summary

Memory management provides allocation, relocation, translation, sharing, and protection for processes. Contiguous allocation is simple but suffers from fragmentation; paging provides fixed-size allocation and virtual-to-physical translation; segmentation expresses logical regions but may create external fragmentation. TLBs accelerate translation, while multilevel page tables make large address spaces practical. Demand paging extends apparent memory capacity but makes page-fault behavior central to performance.

Replacement policies approximate locality-based choices, and the working-set model explains why insufficient frames produce thrashing. Copy-on-write and memory mapping enable efficient process creation, shared libraries, file access, and interprocess communication. Protection uses privilege levels, page permissions, guard pages, address randomization, and device-address controls. NUMA requires placement decisions, while huge pages trade translation efficiency against fragmentation and flexibility. Sound practice combines operating-system mechanisms with measurement, workload-aware configuration, security controls, and careful capacity planning.

Key Terms

Virtual address: An address generated by a process before translation to physical memory.

Physical address: The address used to locate a byte or word in hardware memory.

Memory-management unit (MMU): Hardware that translates addresses and enforces memory permissions.

Page: A fixed-size block of virtual memory.

Frame: A fixed-size block of physical memory that can contain a page.

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

Translation lookaside buffer (TLB): A cache of recent address translations.

Page fault: An exception raised when a referenced page is absent or access is prohibited.

Demand paging: Loading pages into memory only when they are referenced.

Internal fragmentation: Allocated space within a unit that is not used by the requesting object.

External fragmentation: Free memory divided into separated holes.

Segmentation: Address management based on logically defined variable-sized regions.

Working set: Pages actively referenced during a defined recent execution window.

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

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

Memory mapping: Associating a virtual region with a file or memory object.

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

Huge page: A page larger than the system’s ordinary base page size.

ASLR: A technique that randomizes address-space locations to reduce exploit predictability.

Guard page: A protected or unmapped page used to detect boundary violations.

Review Questions

Short Answer Questions

1. What is the difference between a virtual address and a physical address?

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

3. Define a working set and explain its relevance to page replacement.

4. What event triggers copy-on-write handling?

5. Why can huge pages reduce TLB overhead?

Long Answer Questions

1. Explain the complete address-translation process for a paged virtual-memory system, including TLB hits, TLB misses, and page faults.

2. Compare FIFO, optimal, LRU, and clock page-replacement approaches, including their practical trade-offs.

3. Explain thrashing using the working-set model and discuss operating-system responses.

4. Discuss memory mapping, shared memory, and copy-on-write as mechanisms for efficient data sharing.

5. Analyze the effects of NUMA and huge pages on performance, allocation, and system design.

Analytical / Application Questions

1. A server’s CPU utilization falls while major page faults and storage latency rise after the number of worker processes is doubled. Diagnose the likely memory behavior and propose a measurement-based remedy.

2. A database has a large, stable index but also many small, short-lived allocations. Decide which regions, if any, should use huge pages and justify the decision.

3. Two processes share a read-only library through the same physical pages. Describe the page-table permissions and events required if one process attempts to modify a shared page.

22. Multiple Choice Questions with Answers

Question 1

A 32-bit virtual address uses 4 KiB pages. How many bits identify the virtual page number?

A. 8

B. 12

C. 20

D. 24

Correct Answer: C. 20

Question 2

What is the primary function of a TLB?

A. To store evicted pages permanently

B. To cache recent virtual-to-physical translations

C. To increase the size of physical memory

D. To detect all illegal program instructions

Correct Answer: B. To cache recent virtual-to-physical translations

Question 3

Which condition most directly indicates thrashing?

A. High CPU utilization with no page faults

B. Low page-fault frequency and abundant free frames

C. Excessive paging with little useful process execution

D. A single TLB miss during process startup

Correct Answer: C. Excessive paging with little useful process execution

Question 4

Why can FIFO page replacement exhibit Belady’s anomaly?

A. Adding frames can sometimes increase its page-fault count

B. It always requires future reference information

C. It never evicts dirty pages

D. It uses exact least-recently-used ordering

Correct Answer: A. Adding frames can sometimes increase its page-fault count

Question 5

What happens during a copy-on-write write fault?

A. The writing process is terminated immediately

B. The shared page is made writable for every process

C. A private copy is created for the writing process

D. The page is permanently removed from physical memory

Correct Answer: C. A private copy is created for the writing process

Question 6

Which statement best describes a NUMA system?

A. All processors access every memory location at identical cost

B. Memory access cost depends on the location of memory relative to the processor

C. Only one process can use memory at a time

D. Virtual addresses are not required

Correct Answer: B. Memory access cost depends on the location of memory relative to the processor

Question 7

A page marked non-executable primarily helps prevent which class of misuse?

A. Execution of injected code in a data region

B. External fragmentation

C. TLB replacement

D. NUMA migration

Correct Answer: A. Execution of injected code in a data region

Question 8

A major disadvantage of using huge pages indiscriminately is:

A. They eliminate all page-table entries

B. They can increase internal fragmentation and reduce allocation flexibility

C. They make physical addresses unavailable

D. They prevent file mapping

Correct Answer: B. They can increase internal fragmentation and reduce allocation flexibility

Question 9

Which situation most strongly favors demand paging?

A. A workload whose entire address space must be resident before execution

B. A workload with locality that references only portions of a large address space at a time

C. A system with no backing storage and no page tables

D. A process requiring all pages to be physically contiguous

Correct Answer: B. A workload with locality that references only portions of a large address space at a time

Question 10

A mapped file is marked private and two processes initially share its pages. What normally happens when one process writes to a shared page?

A. The write changes the file for all processes immediately

B. A copy-on-write private page is created for the writer

C. The page becomes a kernel-only page

D. The entire file is copied into physical memory

Correct Answer: B. A copy-on-write private page is created for the writer