Main-Memory Management

Introduction

Main-memory management is the operating system function responsible for organizing, allocating, protecting, and translating the memory used by processes. Although secondary storage provides persistence, the CPU normally executes instructions and accesses data only when they are present in main memory. Effective memory management therefore affects performance, security, multiprogramming, and system reliability.

A modern operating system must answer several questions: Where is a process located in memory? How are logical addresses translated into physical addresses? How can several processes share memory safely? What happens when available memory is insufficient? How can memory be allocated with minimal waste? The principal mechanisms used to answer these questions are address binding, contiguous allocation, swapping, paging, segmentation, translation lookaside buffers, and hardware-supported protection.

Learning Objectives

After studying this chapter, students should be able to:

1. Explain logical and physical addresses and the stages of address binding.

2. Describe contiguous allocation, fragmentation, relocation, and swapping.

3. Explain paging, page tables, multilevel translation, and TLBs.

4. Compare paging and segmentation.

5. Explain how hardware supports relocation and memory protection.

6. Analyze memory-management choices in practical systems.

1. Address Spaces and Address Binding

A process is associated with an address space: the set of addresses that it may use during execution. A logical address, also called a virtual address, is generated by the CPU. A physical address identifies a location in main memory. In a simple system these addresses may be identical, but in a protected multiprogrammed system they are normally different.

Address binding is the mapping of program instructions and data references to actual memory locations. It may occur at three stages:

• Compile-time binding: If the final memory location is known in advance, the compiler can generate absolute addresses. Moving the program later requires recompilation.
• Load-time binding: The compiler produces relocatable code. The loader chooses a starting location and adjusts addresses when the program is loaded.
• Execution-time binding: Address translation occurs while the program runs. A process can be moved during execution, and its pages or segments may be located in different physical regions. Hardware support is required.

Execution-time binding is fundamental to virtual memory. It enables relocation, process isolation, shared libraries, and the use of physical memory that is not contiguous.

A typical address-translation path is:

CPU-generated virtual address → memory-management unit (MMU) → physical address → cache or main memory.

The operating system establishes translation structures, while hardware performs frequent translations efficiently. This division is essential because translating every address through software would impose unacceptable overhead.

2. Contiguous Memory Allocation

In contiguous allocation, each process occupies one continuous region of physical memory. Early systems often divided memory into an operating-system region and a user-process region. In multiprogrammed systems, several partitions may contain several processes.

Fixed and Variable Partitions

With fixed partitions, memory is divided into predetermined regions. A process is placed into a partition large enough to contain it. Fixed partitions are simple but may waste space inside partitions. This waste is called internal fragmentation.

With variable partitions, the operating system creates a region of approximately the required size for each process. Unallocated regions between processes are called holes. As processes enter and leave memory, holes may become separated into many small areas. This is external fragmentation.

Common placement strategies include:

• First fit: Allocate the first hole large enough for the request.
• Best fit: Allocate the smallest hole that is large enough.
• Worst fit: Allocate the largest available hole.
• Next fit: Continue searching from the location of the previous allocation.

First fit is often efficient in practice. Best fit can create many tiny unusable holes, while worst fit attempts to preserve moderately sized holes but often performs poorly. No strategy eliminates fragmentation in all workloads.

Fragmentation

Internal fragmentation occurs inside an allocated unit. For example, if a 10-MB partition is assigned to a process requiring 8 MB, 2 MB is internally unused. External fragmentation occurs between allocated units. The total free memory may be sufficient for a request, but it may not exist as one contiguous hole.

Compaction moves allocated regions together to combine scattered holes. It requires relocation support and consumes processor and memory-bandwidth resources. Compaction is practical only when addresses can be dynamically relocated and when its cost is justified.

3. Relocation and Memory-Protection Hardware

A basic relocation mechanism uses two registers:

• The base register contains the lowest physical address assigned to a process.
• The limit register contains the size of the valid address range.

For a logical address L, the hardware checks whether

0 ≤ L < limit.

If the check succeeds, the physical address is

physical address = base + L.

If the check fails, the hardware raises a protection fault. The operating system then handles the fault, commonly by terminating the process or reporting an illegal memory access.

Only privileged operating-system code may load or modify base and limit registers. Otherwise, a process could change its own base or limit and access the operating system or another process.

This mechanism provides both relocation and protection. It does not, however, support noncontiguous allocation by itself. Paging and segmentation extend the basic idea by using multiple translation entries.

Worked Example: Base and Limit Translation

Suppose a process has base register 40,000 and limit register 12,000. A logical address of 7,500 is valid because 7,500 < 12,000. Its physical address is:

40,000 + 7,500 = 47,500.

A logical address of 12,000 is invalid because valid offsets range from 0 through 11,999. The MMU therefore generates a protection fault.

4. Swapping

Swapping temporarily moves a process, or parts of a process, between main memory and backing storage. The objective is to free physical memory so that other processes can execute.

In traditional swapping, the entire process is moved out and later brought back. Execution-time binding is needed because the process may return to a different physical location. Modern virtual-memory systems usually swap pages rather than complete processes, although the general term “swapping” is still widely used.

Swapping time depends strongly on the amount of data transferred and the speed of the storage device. If a process of size S bytes is transferred over a device with effective bandwidth B bytes per second, the transfer time, ignoring latency and other overheads, is approximately:

T = S / B.

For a 200-MB process transferred at 100 MB/s, one-way transfer takes approximately 2 seconds. Moving it out and later bringing it back requires approximately 4 seconds, excluding seek, latency, scheduling, and processing overhead. This illustrates why excessive swapping, known as thrashing when associated with paging, severely reduces performance.

Swapping also raises scheduling issues. A process that is swapped out cannot run until it is resident again. The operating system must coordinate memory pressure, process priorities, I/O activity, and fairness.

5. Paging

Paging divides a process's virtual address space into fixed-size pages and physical memory into equal-size frames. Any page can be loaded into any available frame. Consequently, a process need not occupy contiguous physical memory.

A virtual address is divided into:

• a page number, p; and
• a page offset, d.

The page number indexes a page table. The corresponding page-table entry identifies the physical frame. The offset remains unchanged. If the page size is 2^n bytes, the lowest n address bits represent the offset. The remaining bits represent the page number.

If the page-table entry maps page p to frame f, and the page size is P bytes, then:

physical address = f × P + d.

The equation assumes that the page is present in main memory and that the page-table entry is valid.

Worked Example: Paging Translation

Assume a 16-bit virtual address, a page size of 1,024 bytes, and a page-table entry mapping page 5 to frame 12. Since 1,024 = 2^10, the offset uses 10 bits. Consider virtual address 5,300.

Page number = floor(5,300 / 1,024) = 5.

Offset = 5,300 − (5 × 1,024) = 180.

The physical address is:

12 × 1,024 + 180 = 12,468.

The page table must contain a valid mapping for page 5. If it does not, the access causes a page fault or another translation exception.

Page Tables

A page table may be stored in main memory. A page-table base register identifies the table for the current process. A context switch changes this register, ensuring that the new process uses its own mappings.

Large virtual address spaces can require large page tables. Several designs reduce this cost:

• Hierarchical page tables: Divide the page table into levels and allocate lower-level tables only for used regions.
• Hashed page tables: Hash virtual page numbers to entries, useful for large address spaces.
• Inverted page tables: Maintain one entry per physical frame rather than one entry per virtual page.

Paging eliminates external fragmentation because any free frame can hold any page. It can still produce internal fragmentation, especially in the final page of a process. With page size P and a uniformly distributed final-page occupancy, average internal waste is approximately P/2, although actual waste depends on allocation patterns.

Larger pages reduce page-table size and may improve sequential transfer efficiency, but they increase internal fragmentation and may bring unused data into memory. Smaller pages reduce such waste but increase translation-structure overhead.

6. Translation Lookaside Buffers

A translation lookaside buffer (TLB) is a small, fast associative cache of recent virtual-page-to-physical-frame translations. It prevents the MMU from accessing the page table in main memory for every reference.

On a TLB hit, the frame number is obtained rapidly and combined with the offset. On a TLB miss, the page table is consulted; the resulting translation may then be inserted into the TLB. If the page is not present, a page fault occurs and the operating system must obtain it from secondary storage.

Let h be the TLB hit ratio, ε the TLB lookup time, and m the main-memory access time. In a simplified model, assuming a TLB hit requires one memory access after lookup and a miss requires an additional page-table memory access, the effective access time is:

EAT = h(ε + m) + (1 − h)(ε + 2m).

This expression excludes page-fault service time and assumes the page table is in main memory. It also assumes the TLB lookup is performed before the memory access.

Worked Example: TLB Performance

Let h = 0.98, ε = 10 ns, and m = 100 ns.

EAT = 0.98(10 + 100) + 0.02(10 + 200)

= 0.98(110) + 0.02(210)

= 107.8 + 4.2 = 112 ns.

Thus, a high TLB hit ratio keeps the average access time close to the ordinary memory-access time. Real processors may use multiple TLB levels, speculative translation, page-walk caches, and parallel cache access, so actual behavior can differ from this simplified model.

TLB entries may be tagged with an address-space identifier (ASID). This permits entries from multiple processes to coexist and reduces the need to flush the TLB on every context switch.

7. Memory Protection in Paged Systems

Each page-table entry commonly contains more than a frame number. Typical control information includes:

• Valid or present bit: Indicates whether the mapping may be used.
• Read/write permission: Controls whether the page may be modified.
• Execute permission: Supports non-executable data regions.
• User/supervisor permission: Separates application access from kernel-only memory.
• Reference or accessed bit: Indicates recent use.
• Dirty or modified bit: Indicates that the page has changed and may need to be written back.
• Caching attributes: Specify whether and how the region may be cached.

A write to a read-only page, execution from a non-executable page, or user access to a supervisor page causes a protection exception. These mechanisms support process isolation and help defend against common classes of software attack, including code injection and unauthorized kernel access.

Protection is not equivalent to complete security. Correct permission settings must be combined with secure operating-system code, safe drivers, isolation of devices, careful sharing policies, and appropriate handling of side channels.

8. Segmentation

Segmentation divides a process according to logical units such as code, data, stack, symbol tables, or dynamically growing arrays. A logical address consists of a segment number and an offset. A segment table entry contains a base and a limit, along with protection attributes.

For segment s and offset d, the hardware checks whether d < limit[s]. If valid:

physical address = base[s] + d.

Segmentation reflects the programmer's logical view more directly than paging. Different segments can have different permissions, and sharing a code segment between processes can be natural. However, variable-sized segments cause external fragmentation. Compaction may be required, and allocation is more complex.

Paging and segmentation can be combined. A segment may be divided into pages, allowing logical protection and sharing at the segment level while avoiding the external fragmentation of variable-sized physical allocation. Many contemporary architectures expose a primarily paged model, even when historical designs supported segmentation prominently.

Paging versus Segmentation

Paging is primarily a physical-memory management technique. It uses fixed-size blocks, eliminates external fragmentation, and supports efficient virtual memory. Its logical units may not correspond to program structures.

Segmentation is primarily a logical-memory and protection model. It supports meaningful regions with different sizes and permissions but can suffer external fragmentation. Paging generally simplifies allocation; segmentation can express programmer-visible structure more naturally. The choice depends on hardware architecture, operating-system goals, compatibility, and performance requirements.

9. Virtual Memory and Demand Paging

Virtual memory allows a process to have an address space larger than the currently available physical memory. In demand paging, a page is loaded only when referenced. A reference to a nonresident page causes a page fault.

A typical page-fault sequence is:

1. The CPU references a virtual address.

2. The MMU detects that the page is not present.

3. Hardware traps to the operating system.

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

5. A free frame is found, or a victim page is selected.

6. If the victim is dirty, it is written to storage.

7. The required page is read into the frame.

8. The page table and TLB are updated.

9. The interrupted instruction is restarted.

Page replacement algorithms include FIFO, optimal replacement, and LRU. The optimal algorithm provides the theoretical minimum number of page faults but requires knowledge of future references and is therefore not implementable in general. LRU approximations use reference bits, aging, or clock algorithms. FIFO is simple but can exhibit Belady's anomaly, in which increasing the number of frames increases page faults for some reference strings.

If the system spends most of its time servicing page faults rather than executing instructions, it is thrashing. Causes include insufficient frames, excessive multiprogramming, poor locality, or an unsuitable replacement policy. Working-set and page-fault-frequency approaches attempt to control this problem.

10. A Detailed Applied Scenario: Memory Isolation in an AI Inference Service

This is an illustrative case.

Background

A cloud service runs several AI inference workers on one server. Each worker loads model code, input buffers, temporary tensors, and shared read-only libraries. Some workers process untrusted customer input.

Problem

The service experiences high latency during peak demand. In addition, a programming error in one worker occasionally causes an invalid write. The operator must improve utilization without allowing one worker to corrupt another worker or the operating system.

Analysis

A contiguous-allocation design would make relocation and growth difficult. Model data and temporary tensors vary substantially in size, producing external fragmentation. Full-process swapping would also be too slow for latency-sensitive requests.

A paged virtual-memory design allows each worker to use a private virtual address space. Read-only model pages and libraries may be shared physically, while writable buffers remain private. Page permissions can mark code non-writable and data non-executable. The MMU and TLB perform ordinary translations, while invalid or unauthorized accesses generate faults.

Approach and Solution

The operator uses demand paging, a multi-level page table, TLBs with address-space identifiers, and a replacement policy that considers the workers' active working sets. Frequently used model pages remain resident. Large pages are selectively used for stable, frequently accessed model regions, while ordinary pages are retained for small temporary allocations. Memory limits are imposed per worker to prevent one workload from consuming all frames.

Monitoring records page-fault rates, resident-set sizes, TLB misses, and latency. The system avoids indiscriminate swapping during peak inference and reduces concurrency when aggregate working sets exceed physical memory.

Outcome

Isolation prevents invalid writes from reaching other workers. Shared read-only pages reduce duplication. Working-set monitoring lowers thrashing, while selective page sizes balance translation overhead against internal fragmentation. The service becomes more predictable, although memory pressure still requires admission control.

Learning Points

1. Virtual memory is both a performance mechanism and a protection mechanism.

2. Sharing is safest when pages are read-only or controlled through copy-on-write.

3. TLB behavior can influence application performance even when total memory is sufficient.

4. AI workloads with large models benefit from careful page-size, locality, and residency decisions.

11. Contemporary Developments and Best Practices

Modern systems combine page tables, multi-level TLBs, hardware permission checks, copy-on-write, memory-mapped files, and hardware virtualization. Containers commonly rely on operating-system isolation, while virtual machines add another translation layer, such as nested paging. This can improve consolidation but may increase translation overhead and complicate accounting.

Best practices include:

• Use hardware-enforced address translation and privilege levels.
• Mark code and data with least-privilege permissions.
• Minimize unnecessary page-table and TLB misses.
• Monitor page-fault rate, working-set size, and memory pressure.
• Select page sizes according to locality, fragmentation, and translation overhead.
• Use copy-on-write for efficient process creation and safe sharing.
• Avoid uncontrolled overcommit when workloads are latency-sensitive.
• Treat memory contents as potentially sensitive; securely handle deallocation, encryption requirements, and crash dumps.

Memory management also has governance implications. Cloud providers must isolate tenants, account fairly for shared pages, protect confidential data, and disclose resource limits. Side-channel risks, including timing effects associated with caches and translation structures, require threat modeling and sometimes stronger isolation.

Challenges and Limitations

No memory-management policy is universally best. Paging removes external fragmentation but introduces page-table storage, TLB misses, and possible internal fragmentation. Segmentation expresses logical structure but is vulnerable to external fragmentation. Large pages improve translation efficiency for some workloads but waste memory for sparse access patterns. Swapping expands apparent capacity but can destroy responsiveness. Protection hardware prevents many invalid accesses but cannot correct flawed authorization logic within a valid address range.

Performance is also workload-dependent. Sequential programs may benefit from large pages and prefetching, whereas sparse data structures may suffer from them. AI models may have large, stable read-only regions but highly variable temporary allocations. Consequently, operating-system configuration should be evaluated using measurements rather than assumptions.

Chapter Summary

Main-memory management maps process address spaces to physical memory while providing relocation, protection, sharing, and efficient utilization. Address binding may occur at compile time, load time, or execution time; modern systems rely primarily on execution-time translation. Base and limit registers support simple relocation and protection.

Contiguous allocation is simple but suffers internal or external fragmentation. Swapping can release memory but is expensive. Paging divides virtual memory into pages and physical memory into frames, eliminating external fragmentation and supporting demand paging. Page tables perform translation, while TLBs cache recent translations. Segmentation organizes memory into logical variable-sized units and supports meaningful protection boundaries, but may cause external fragmentation.

Hardware permission bits, privilege levels, valid bits, dirty bits, and execution controls provide essential protection. Virtual memory enables processes to use address spaces larger than resident physical memory, but page faults and thrashing can severely reduce performance. Effective systems combine hardware support, suitable page sizes, replacement policies, monitoring, isolation, and workload-aware configuration.

Key Terms

Address binding: Mapping program addresses to memory locations.

Logical address: Address generated by the CPU and used by a process.

Physical address: Actual address in main memory.

MMU: Hardware unit that translates virtual addresses to physical addresses.

Relocation: Moving a program while preserving correct address references.

Base register: Register containing the starting physical address of a process region.

Limit register: Register specifying the valid size of a process region.

Internal fragmentation: Unused space inside an allocated region.

External fragmentation: Free space divided among separated holes.

Compaction: Moving allocations to combine free holes.

Swapping: Moving processes or pages between memory and backing storage.

Page: Fixed-size block of virtual memory.

Frame: Fixed-size block of physical memory.

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

TLB: Fast cache of recent address translations.

Segmentation: Division of an address space into logical variable-sized units.

Page fault: Exception caused when a referenced page is not resident or is unauthorized.

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

Copy-on-write: Sharing pages until a process attempts to modify one.

Review Questions

Short Answer Questions

1. Distinguish a logical address from a physical address.

2. What is the difference between internal and external fragmentation?

3. Why is a TLB used in a paged memory system?

4. State the purpose of the valid and dirty bits in a page-table entry.

5. What condition causes a page fault?

Long Answer Questions

1. Explain compile-time, load-time, and execution-time address binding and compare their flexibility.

2. Describe paging translation, including the roles of the page number, offset, page table, and frame.

3. Compare paging and segmentation in terms of organization, fragmentation, protection, and sharing.

4. Explain the complete sequence of events that occurs during a demand-page fault.

5. Discuss how memory-protection hardware supports process isolation.

Analytical / Application Questions

1. A system has a 4-KB page size. Explain how a virtual address is divided into page number and offset, and describe how the physical address is formed after a page-table lookup.

2. A server has a high TLB miss rate and frequent page faults. Analyze at least four possible causes and recommend measurements or design changes.

3. Design a memory-management approach for a multi-tenant AI inference server. Justify choices concerning page size, protection, sharing, replacement, monitoring, and admission control.

Multiple Choice Questions with Answers

Question 1

Which address is generated directly by the CPU in a virtual-memory system?

A. Physical address

B. Logical address

C. Disk-sector address

D. DMA channel address

Correct Answer: B. Logical address

Question 2

A process has base 40,000 and limit 12,000. What physical address results from logical address 7,500?

A. 7,500

B. 12,000

C. 40,000

D. 47,500

Correct Answer: D. 47,500

Question 3

Which allocation method selects the first sufficiently large free hole?

A. First fit

B. Best fit

C. Worst fit

D. Optimal replacement

Correct Answer: A. First fit

Question 4

In paging, which part of a virtual address remains unchanged during translation?

A. Page number

B. Frame number

C. Offset

D. Table index

Correct Answer: C. Offset

Question 5

A page size is 1,024 bytes, and page 5 maps to frame 12. What physical address corresponds to virtual address 5,300?

A. 5,420

B. 12,180

C. 12,468

D. 17,300

Correct Answer: C. 12,468

Question 6

What is the primary purpose of a TLB?

A. To store complete processes on disk

B. To cache recent address translations

C. To eliminate all page faults

D. To combine external holes

Correct Answer: B. To cache recent address translations

Question 7

Which page-table bit commonly indicates that a page has been modified?

A. Valid bit

B. Execute bit

C. Dirty bit

D. User bit

Correct Answer: C. Dirty bit

Question 8

What is a major disadvantage of variable-sized segmentation?

A. It cannot support protection

B. It causes external fragmentation

C. It requires fixed-size frames

D. It prevents logical organization

Correct Answer: B. It causes external fragmentation

Question 9

What event occurs when a referenced page is not currently in physical memory?

A. TLB hit

B. Page fault

C. Compaction

D. Context-free translation

Correct Answer: B. Page fault

Question 10

Which condition best describes thrashing?

A. The CPU spends most time executing application instructions

B. The system spends excessive time servicing page faults

C. All pages are permanently resident

D. The TLB has no entries

Correct Answer: B. The system spends excessive time servicing page faults