Memory Management in Operating Systems

Introduction and Context

Memory management is the operating system function responsible for controlling how main memory is allocated, used, protected, and reclaimed. It provides a bridge between application requirements and the physical limitations of computer hardware. A running program requires instructions and data to be placed in memory, but several programs may need memory simultaneously. The operating system must therefore decide where programs are placed, how much memory they receive, how addresses are translated, and how one program is prevented from corrupting another.

Memory management directly affects system performance. Poor allocation can waste memory through fragmentation; excessive swapping can make a system appear unresponsive; and ineffective page replacement can cause frequent page faults. Conversely, well-designed memory management allows large applications to run safely even when their total logical memory requirements exceed available physical RAM.

Learning Objectives

After studying this chapter, a learner should be able to:

• explain contiguous and non-contiguous memory allocation;
• distinguish internal and external fragmentation;
• describe paging, segmentation, swapping, and virtual memory;
• calculate address translations and effective access time in simple cases;
• compare page-replacement algorithms;
• explain memory protection and address-space isolation;
• relate memory-management choices to performance and application requirements.

1. Address Spaces and Memory Allocation

A process is an executing program together with its current state, instructions, data, stack, and dynamically allocated objects. The addresses used by a process are normally logical or virtual addresses. Physical addresses identify actual locations in RAM. The memory-management unit (MMU), with assistance from the operating system, translates virtual addresses into physical addresses.

A process commonly views memory as a private address space. This abstraction has two important benefits. First, programmers can develop applications without knowing the exact physical location of their data. Second, the operating system can isolate processes and relocate them when necessary.

1.1 Contiguous allocation

In contiguous allocation, each process occupies one continuous region of physical memory. A simple system may divide memory into a region for the operating system and a region for one user process. Multiprogrammed systems can use fixed or variable partitions.

With fixed partitions, memory is divided into predetermined blocks. A process is assigned a partition large enough to contain it. This arrangement is simple but inflexible: a large partition may be unavailable even when the total unused space is sufficient, and a small process may leave unused space inside its partition.

With variable partitions, the operating system creates a memory block approximately equal to each process’s requirement. When a process terminates, its block becomes a hole. Allocation 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.

These strategies differ in speed and the pattern of holes they create. No strategy completely eliminates fragmentation.

1.2 Non-contiguous allocation

Paging and segmentation allow a process to occupy several separated physical regions. Non-contiguous allocation uses memory more flexibly and supports virtual memory, although it requires address-translation data structures and hardware support.

2. Fragmentation

Fragmentation is memory waste caused by the way free and allocated regions are arranged.

Internal fragmentation

Internal fragmentation occurs when allocated space is larger than the request. The unused area lies inside an allocated block and cannot normally be assigned to another process. Fixed-size pages may produce internal fragmentation because the final page of a process is often only partly used.

If a process requires 10,250 bytes and pages are 4,096 bytes, it needs three pages, providing 12,288 bytes. Internal waste is:

The amount varies from nearly zero to almost one page per process; the average waste for random process sizes is approximately half a page, although actual workloads may differ.

External fragmentation

External fragmentation occurs when free memory is divided into holes that are individually too small for a request. The total free memory may be adequate, but it is not available as one suitable region. Variable-size contiguous allocation is especially vulnerable to external fragmentation.

Compaction moves allocated blocks together to create a larger free region. It requires relocation support and consumes processor and memory bandwidth. Paging largely avoids external fragmentation because any free frame can hold any page, but paging may still cause internal fragmentation.

3. Paging

Paging divides a process’s virtual address space into fixed-size pages and physical memory into equal-size frames. A page can be loaded into any free frame. A page table records the relationship between virtual page numbers and physical frame numbers.

A virtual address consists of:

• a page number, identifying the page;
• an offset, identifying the byte within that page.

If the page size is 2^p bytes, the offset occupies p bits. For an address of n bits, the page number occupies n − p bits. The physical address is formed by combining the frame number with the unchanged offset.

Worked example: paging translation

Assume a 16-bit virtual address, a page size of 1,024 bytes, and a page table entry showing that virtual page 6 is stored in frame 14. Since 1,024 = 2¹⁰, the offset is 10 bits. The virtual address 6,500 can be divided as follows:

Thus, the page number is 6 and the offset is 356. Frame 14 begins at physical address:

The physical address is:

This calculation assumes byte-addressable memory and a valid page-table entry.

Page-table organization

A page table may contain the frame number, a valid or present bit, protection bits, a reference bit, and a modified or dirty bit. Large address spaces require large page tables, so systems use techniques such as multilevel page tables, inverted page tables, or hashed page tables.

The translation lookaside buffer (TLB) is a small, fast cache of recent page-table entries. If the desired translation is in the TLB, translation is faster. If not, the processor must consult the page table and may then update the TLB.

If TLB lookup takes ε, a memory access takes m, and the TLB hit ratio is h, a simplified effective access time is:

This assumes that a TLB miss requires one additional memory access to read the page-table entry, ignores page faults, and treats the TLB lookup time as occurring before the memory access.

Large pages and small pages

Small pages reduce internal fragmentation and can provide fine-grained protection, but they increase the number of page-table entries and may increase translation overhead. Large pages reduce page-table and TLB pressure and may benefit large databases or scientific workloads, but they can waste memory when only a small portion of a page is used. Operating systems therefore select page sizes according to hardware design and application behavior.

4. Segmentation

Segmentation divides a program according to logical units such as code, global data, a stack, a symbol table, or a dynamically created object area. A logical address contains a segment number and an offset. A segment table entry generally stores a base address, a limit, and protection information.

For a segment with base b and limit l, an offset d is valid when:

If valid, the physical address is:

If d ≥ l, the hardware raises a protection exception. This provides a direct way to express logical protection, such as read-only code or a non-executable data segment.

Segmentation supports sharing meaningful program units. For example, several processes may share one read-only library segment. Its main disadvantage is external fragmentation because variable-sized segments require variable-sized physical regions. Some systems combine segmentation with paging: each segment is divided into pages, retaining logical organization while reducing external fragmentation.

Paging and segmentation compared

5. Swapping and Virtual Memory

Swapping is the movement of a process, or portions of its memory, between RAM and secondary storage. Traditional swapping moves an entire process out of memory and later brings it back. Modern systems more commonly swap individual pages, although the term “swapping” is often used broadly for paging activity involving disk or solid-state storage.

Swapping allows more processes to be maintained than can fit entirely in RAM. However, secondary storage is much slower than RAM. Moving data between them consumes I/O bandwidth and increases response time. The operating system should therefore avoid unnecessary movement and prefer inactive or less frequently used pages as victims.

Virtual memory separates a process’s logical address space from the amount of physical memory currently assigned to it. A process can execute while only some of its pages are resident in RAM. If it references a nonresident page, a page fault occurs. The operating system then:

1. verifies that the reference is legal;
2. locates the required page on storage;
3. obtains a free frame, or selects a victim page;
4. writes the victim to storage if it is dirty;
5. reads the required page into the frame;
6. updates the page table and TLB;
7. restarts the interrupted instruction.

Virtual memory supports programs whose address spaces are larger than physical RAM, but it does not create unlimited fast memory. Its success depends on locality of reference. Temporal locality means recently used instructions or data are likely to be used again. Spatial locality means addresses near a recently used address are likely to be referenced soon.

Demand paging

In demand paging, a page is loaded only when it is referenced. This reduces initial loading and permits more processes to be active. Its cost is the page-fault penalty. A useful simplified model for average memory access time is:

where p is the page-fault probability, m is the ordinary memory-access time, and F is the average page-fault service time, including operating-system processing and storage I/O. This model assumes that a page fault replaces the normal access cost by approximately F and ignores additional cache or TLB effects. Because F is usually many orders of magnitude larger than m, even a small fault probability can significantly reduce performance.

6. Page Replacement

When a page fault occurs and no free frame exists, the operating system must choose a page to remove. The choice is made by a page-replacement algorithm. A good algorithm reduces page faults while keeping implementation cost reasonable.

First-In, First-Out (FIFO)

FIFO replaces the page that has been in memory the longest. It is simple and requires a queue. However, the oldest page may still be frequently used. FIFO can exhibit Belady’s anomaly, in which increasing the number of frames increases the number of page faults for some reference strings.

Optimal replacement

The optimal algorithm replaces the page whose next reference is farthest in the future. It produces the minimum possible number of faults for a known reference string, but the future is not available to a real operating system. It is therefore mainly a benchmark for evaluating practical algorithms.

Least Recently Used (LRU)

LRU replaces the page that has not been used for the longest time. It approximates locality and generally performs well, but exact implementation requires costly timestamps, counters, or hardware support.

Clock or second-chance replacement

Clock maintains pages in a circular list and uses a reference bit. A page with reference bit 0 is selected; a page with bit 1 is given a second chance and its bit is cleared. Clock approximates LRU with lower overhead.

Worked comparison

Consider the reference string 1, 2, 3, 1, 4 with three initially empty frames. Under FIFO, references 1, 2, and 3 cause three faults. The second reference to 1 is a hit. Reference 4 causes a fault and replaces 1, the oldest page. Thus FIFO produces four faults. Under LRU, the page-use order before reference 4 is 2, 3, 1, so LRU replaces 2 and also produces four faults. This small example does not establish that the algorithms are equally effective generally; a longer reference string may produce different results.

Replacement policy must also consider dirty pages. A clean victim can be discarded because its stored copy is unchanged; a dirty victim must first be written to storage, increasing fault service time.

7. Memory Protection and Sharing

Memory protection ensures that a process can access only the addresses and operations authorized for it. Common mechanisms include:

• Base and limit protection: an address is valid only within a specified range.
• Page-level protection: each page has read, write, and execute permissions.
• Segment-level protection: logical regions have separate limits and permissions.
• User and kernel modes: privileged instructions and protected memory are restricted to the operating system.
• No-execute protection: data pages are prevented from executing instructions, reducing some buffer-overflow attacks.
• Address-space isolation: each process receives a separate mapping of virtual addresses.

Protection is not identical to security, but it is a foundational security control. Shared memory can improve performance because processes exchange data without repeated copying. It must be carefully synchronized and permission-controlled, since an error in shared writable memory can affect multiple processes. Read-only sharing of common libraries is generally safer and conserves RAM.

8. Performance and Application Requirements

Memory-management design should reflect workload characteristics rather than rely on a single universally best method.

The working set is the collection of pages actively used by a process during a period. If the total working sets of active processes exceed available frames, the system may enter thrashing. Thrashing is characterized by very high page-fault and storage activity and little useful processor work.

Operating systems can control thrashing by reducing the degree of multiprogramming, allocating more frames to affected processes, or using working-set and page-fault-frequency policies. Increasing the number of processes is not always beneficial: beyond a point, competition for frames lowers total throughput.

Useful performance indicators include page-fault rate, TLB hit ratio, swap or paging I/O, memory utilization, response time, throughput, and CPU utilization. These measures should be interpreted together. High RAM utilization can be healthy if faults are low, whereas high paging I/O and low CPU utilization often indicate memory pressure.

9. Applied Case: Online Retail Analytics Service

Background

An illustrative online retailer runs a web application, a product-search service, and a demand-forecasting process on one server. During normal periods, each process fits comfortably in RAM. During a promotional event, thousands of product images, search indexes, and forecasting data structures become active.

Problem

Users report long response times. Monitoring shows high storage activity, a rising page-fault rate, and reduced CPU utilization. The server has sufficient total virtual memory, but its active working sets exceed available RAM.

Analysis

The problem is not simply that the system has “too little disk space.” Virtual memory allows the processes to address large spaces, but storage is far slower than RAM. The combined working sets are competing for frames. If the page-replacement algorithm repeatedly removes pages that will soon be needed, the system thrashes. Large image buffers also create pressure, while the forecasting process may contain a large but temporarily inactive data region.

Approach and solution

The operations team first measures working-set sizes and identifies inactive processes. It then separates the forecasting workload onto another server, limits the image-service cache, and increases RAM. The team also reviews page sizes and uses large pages only for data structures that benefit from them. It monitors dirty-page write activity and ensures that frequently used libraries are shared read-only. Application developers restructure the search index to improve locality rather than relying solely on hardware expansion.

Outcome

Paging I/O declines, page-fault frequency returns to a manageable level, and CPU utilization rises because processors spend more time executing useful work. User response time improves without changing the application’s logical address space.

Learning points

The case demonstrates that virtual memory is an abstraction, not a substitute for adequate RAM. Performance depends on locality, working-set size, replacement decisions, and application behavior. Diagnosis should use measurements rather than assuming that high memory utilization alone represents failure.

10. Challenges, Governance, and Best Practices

Memory-management failures can cause crashes, data corruption, information disclosure, or denial of service. Systems should enforce least privilege, validate page permissions, clear sensitive memory before reuse where appropriate, and maintain reliable audit and patching practices. Cloud and virtualized environments add concerns about overcommitment, memory ballooning, deduplication, and possible cross-tenant leakage.

Important best practices include:

1. use hardware-supported address translation and protection;
2. monitor page-fault rate and paging I/O, not merely free memory;
3. design applications for locality and bounded working sets;
4. avoid indiscriminate use of large pages;
5. protect executable and sensitive data with suitable permissions;
6. test workloads under peak demand;
7. distinguish a capacity problem from a replacement-policy problem;
8. use predictable allocation strategies in real-time applications;
9. document memory ownership when shared memory is used;
10. treat swap space as an emergency capacity mechanism, not equivalent to RAM.

Chapter Summary

Memory management allocates and protects memory while translating virtual addresses into physical locations. Contiguous allocation is simple but suffers from external fragmentation; paging uses fixed-size pages and frames, reducing external fragmentation but potentially causing internal fragmentation. Segmentation reflects logical program units and supports meaningful protection, although variable-sized segments can create external fragmentation.

Swapping transfers processes or pages between RAM and secondary storage. Virtual memory allows a process to use a large logical address space while only part of it is resident. Demand paging relies on locality of reference, but page faults are expensive. FIFO, optimal, LRU, and Clock are important replacement approaches, each balancing performance, predictability, and implementation cost. Protection mechanisms isolate processes and control read, write, and execute access.

System performance depends on TLB behavior, page-fault rate, working-set size, replacement policy, storage speed, and application locality. When working sets exceed available frames, thrashing may occur. Effective memory management therefore requires both operating-system policies and application-aware workload design.

Key Terms

Address space: The range of addresses available to a process.

Page: A fixed-size block of virtual memory.

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

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

MMU: Hardware that translates virtual addresses into physical addresses.

TLB: A fast cache of recent address translations.

Internal fragmentation: Unused space within an allocated block.

External fragmentation: Free space separated into holes that cannot satisfy a request.

Paging: Division of virtual memory into pages and physical memory into frames.

Segmentation: Division of memory into logical, variable-sized segments.

Swapping: Moving memory contents between RAM and secondary storage.

Virtual memory: An abstraction allowing logical memory to exceed currently available RAM.

Page fault: An exception caused when a referenced page is not resident.

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

Locality of reference: The tendency of programs to reuse nearby or recently used data and instructions.

Working set: Pages actively used by a process during a specified interval.

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

Memory protection: Controls that restrict processes to authorized memory operations.

Review Questions

Short Answer Questions

1. What is the difference between internal and external fragmentation?
2. Why does a virtual address contain a page number and an offset?
3. What is the purpose of a TLB?
4. Define a page fault and identify its main handling steps.
5. Why can thrashing reduce CPU utilization?

Long Answer Questions

1. Explain contiguous, paging-based, and segmentation-based allocation, including their advantages and limitations.
2. Describe demand paging and explain how locality of reference supports virtual memory.
3. Compare FIFO, optimal, LRU, and Clock page-replacement algorithms.
4. Explain the major mechanisms used to protect process memory.
5. Discuss how memory-management decisions affect interactive, database, real-time, and mobile applications.

Analytical / Application Questions

1. A system uses 4,096-byte pages. Translate virtual address 13,000 when the corresponding page is stored in frame 9. Show the page number, offset, and physical address.
2. A workload has a high TLB hit ratio but also a high page-fault rate. Explain how both observations can occur and recommend two diagnostic actions.
3. An organization must choose between increasing RAM and changing a replacement policy. Identify the measurements needed to make the decision and explain how their results would guide the choice.

Multiple Choice Questions with Answers

Question 1

Which condition produces external fragmentation?

A. Unused space inside an allocated fixed-size block

B. Free memory divided into separated holes

C. A page table containing invalid entries

D. A process using a read-only page

Correct Answer: B. Free memory divided into separated holes

Question 2

A system has a page size of 1,024 bytes. What is the offset for virtual address 6,500?

A. 6 bytes

B. 356 bytes

C. 1,024 bytes

D. 6,500 bytes

Correct Answer: B. 356 bytes

Question 3

Which structure caches recent virtual-to-physical address translations?

A. Stack

B. Segment table

C. TLB

D. Swap queue

Correct Answer: C. TLB

Question 4

Which page-replacement algorithm is theoretical because it requires knowledge of future references?

A. FIFO

B. Clock

C. LRU

D. Optimal

Correct Answer: D. Optimal

Question 5

What normally happens when a process references a nonresident page?

A. A page fault occurs

B. The page is executed directly from the TLB

C. The process automatically gains kernel privileges

D. The page table is deleted

Correct Answer: A. A page fault occurs

Question 6

Which statement best describes virtual memory?

A. It guarantees that storage is as fast as RAM

B. It allows logical memory to exceed currently resident physical memory

C. It eliminates all fragmentation

D. It removes the need for address translation

Correct Answer: B. It allows logical memory to exceed currently resident physical memory

Question 7

What is a principal danger when the combined working sets exceed available frames?

A. Thrashing

B. Compaction

C. Static linking

D. Instruction pipelining

Correct Answer: A. Thrashing

Question 8

In segmentation, what determines whether an offset is valid?

A. Whether the offset is smaller than the segment limit

B. Whether the offset equals the base address

C. Whether the segment is exactly one page

D. Whether the TLB is empty

Correct Answer: A. Whether the offset is smaller than the segment limit

Question 9

Why might a dirty page cost more to replace than a clean page?

A. It must be written to storage before reuse

B. It always has a larger page size

C. It cannot be mapped by an MMU

D. It must be converted into a segment

Correct Answer: A. It must be written to storage before reuse

Question 10

Which measure is most directly associated with excessive demand paging?

A. High paging I/O and page-fault frequency

B. Low logical address-space size

C. A large number of source-code comments

D. A high keyboard polling rate

Correct Answer: A. High paging I/O and page-fault frequency