Unit 4 · Memory Management

Lecture 8: Page replacement & thrashing

Learning outcomes

Evaluate page replacement algorithms and explain the phenomenon of thrashing.

Lecture Notes

Main content

Performance of Demand Paging, Page Replacement Algorithms, Thrashing, Cache Memory Organization, and Locality of Reference

These notes explain how demand paging affects performance, how the operating system chooses a page to replace, why a system may enter thrashing, how cache memory is organized, and why locality of reference is the key idea behind both caching and virtual memory.

Demand Paging EAT Page Replacement Thrashing Cache Memory Locality

1. Performance of Demand Paging

1.1 Why performance matters

Demand paging allows a process to run without loading all its pages into RAM at the beginning. This is memory-efficient, but it creates a new cost: when a required page is not in memory, the system must handle a page fault.

A page fault is expensive because the missing page has to be brought from disk into memory. RAM access is extremely fast, while disk access is extremely slow in comparison. So a small page-fault rate can still hurt performance badly.

Main point: Demand paging is efficient only when the page-fault rate remains low.

1.2 Main components of page-fault service time

The total time required to service a page fault usually includes:

servicing the page-fault interrupt,
reading the required page from backing store,
restarting the interrupted process.

Among these, disk I/O dominates the total delay.

Figure 1: Main time-consuming steps in page-fault servicing.

1.3 Effective Access Time (EAT)

The impact of page faults is measured using Effective Access Time (EAT).

Effective Access Time = (1 − p) × Memory Access Time + p × Page Fault Service Time

where:

p = page-fault rate
Memory Access Time = normal RAM access time
Page Fault Service Time = total time to handle a page fault

Worked Example: EAT

Suppose:

Memory access time = 200 ns
Page-fault service time = 8 ms = 8,000,000 ns
Page-fault rate = p

EAT = (1 − p) × 200 + p × 8,000,000

If p = 0.001 (that is, 1 fault per 1000 accesses), then:

EAT = 0.999 × 200 + 0.001 × 8,000,000
EAT = 199.8 + 8000
EAT ≈ 8199.8 ns ≈ 8.2 μs

So one tiny-looking page-fault probability causes a massive slowdown. That is classic OS mischief.

1.4 Factors affecting demand-paging performance

Page-fault rate
Speed of backing store
Number of free frames available
Page replacement policy
Program locality
Cache and TLB effectiveness

Important: Demand paging is practical only when most memory references hit pages already present in RAM.

2. Page Replacement Algorithms

2.1 Why page replacement is needed

When a page fault occurs and there is no free frame available, the operating system must choose some page currently in memory to remove. This decision is made by a page replacement algorithm.

The objective is simple: choose a page whose removal causes the fewest future page faults. That objective is simple on paper; the machine, naturally, makes it annoying.

2.2 Desirable properties

Low page-fault rate
Simple implementation
Low overhead
Good behavior under changing workloads

2.3 FIFO (First-In, First-Out)

FIFO replaces the page that has been in memory the longest. The oldest page leaves first.

Algorithm	Rule	Strength	Weakness
FIFO	Replace the page that entered memory first.	Very simple to implement.	May replace a heavily used page; can suffer from Belady’s anomaly.

Figure 2: FIFO removes the oldest page in memory.

2.4 Optimal Page Replacement (OPT)

OPT replaces the page that will not be used for the longest time in the future. It gives the minimum possible page-fault rate for a fixed number of frames.

Algorithm	Rule	Strength	Weakness
Optimal (OPT)	Replace the page whose next use is farthest in the future.	Best possible page-fault performance.	Needs future knowledge, so impractical in real systems.

2.5 LRU (Least Recently Used)

LRU replaces the page that has not been used for the longest time in the past. The idea is based on locality: pages used recently are likely to be used again soon.

Algorithm	Rule	Strength	Weakness
LRU	Replace the least recently used page.	Usually performs well and approximates OPT.	Pure LRU is costly to implement exactly.

Figure 3: LRU chooses the page with the oldest recent-use history.

2.6 Belady’s anomaly

Some algorithms, especially FIFO, can show Belady’s anomaly, where increasing the number of frames actually increases the number of page faults. That sounds wrong because it is wrong in spirit, but it happens.

Belady’s anomaly: More memory does not always mean fewer page faults for FIFO.

2.7 Comparison snapshot

Algorithm	Nature	Belady’s Anomaly	Practical Use
FIFO	Simple queue-based	Yes	Educational / basic implementation
OPT	Theoretical best	No	Benchmark / comparison only
LRU	Locality-based	No	Conceptually strong; often approximated in practice

3. Thrashing

3.1 Meaning

Thrashing is a condition in which a process or the whole system spends more time paging than executing useful instructions.

It happens when the system does not have enough frames to support the current working sets of active processes. The CPU waits while pages are constantly swapped in and out.

Definition: Thrashing means excessive paging with very little productive execution.

3.2 Why thrashing occurs

Degree of multiprogramming becomes too high
Too many processes compete for too few frames
Each process gets fewer frames than its current working set needs
Page-fault rate rises sharply

Figure 4: Beyond a point, increasing multiprogramming can decrease CPU utilization due to thrashing.

3.3 Symptoms of thrashing

Very high page-fault rate
Low CPU utilization
Heavy disk activity
Little actual progress in program execution

3.4 Preventing thrashing

Common approaches include:

Reduce the degree of multiprogramming
Allocate more frames to processes that need them
Use the working-set model
Use page-fault frequency control

3.5 Working set idea

A working set is the set of pages actively used by a process during a recent interval. If the process does not get enough frames to hold its working set, page faults rise and thrashing may begin.

Thrashing and locality are linked: if a process has frames for its current locality, it runs well; if not, it keeps faulting and thrashing starts.

4. Cache Memory Organization

4.1 Why cache memory is needed

CPU speed is much higher than main-memory speed. To reduce this speed gap, systems use cache memory, which is smaller but much faster than RAM.

Frequently used instructions and data are copied into cache so the CPU can access them quickly.

4.2 Memory hierarchy

Computer storage is organized as a hierarchy:

Figure 5: Cache sits between CPU and main memory in the storage hierarchy.

4.3 Typical cache organization

L1 Cache: Smallest and fastest, closest to the CPU core
L2 Cache: Larger than L1, slightly slower
L3 Cache: Larger and often shared among cores

4.4 Basic terms

Term	Meaning
Cache hit	Required data is found in cache.
Cache miss	Required data is not in cache and must be fetched from lower memory level.
Hit ratio	Fraction of accesses that are cache hits.
Miss penalty	Extra time required when a miss occurs.

4.5 Cache organization methods

Method	Idea	Characteristic
Direct Mapping	Each memory block maps to exactly one cache line.	Simple and fast, but conflict misses can occur.
Associative Mapping	A memory block can go to any cache line.	Flexible but expensive hardware.
Set-Associative Mapping	A memory block maps to one set, but within that set it can occupy any line.	Good compromise between flexibility and cost.

Simple intuition

Direct mapping is like having one fixed chair per student. Associative mapping is like letting the student sit anywhere. Set-associative mapping is like giving the student one row, but freedom inside that row.

4.6 Write policies

Write-through: update cache and main memory together
Write-back: update cache first and write to main memory later

5. Locality of Reference

5.1 Meaning

Locality of reference means that a program tends to access a relatively small set of memory locations repeatedly for some period of time.

This is the key reason why both caching and virtual memory work well.

Core insight: Programs usually do not use all of memory uniformly. They focus on nearby or recently used locations.

5.2 Types of locality

Type	Meaning	Example
Temporal Locality	If a location is used now, it is likely to be used again soon.	Loop counter reused every iteration
Spatial Locality	If a location is used now, nearby locations are likely to be used soon.	Sequential array traversal
Sequential Locality	Instructions or data are often accessed in sequence.	Executing program instructions one after another

Figure 6: Spatial locality favors nearby addresses; temporal locality favors recently used items.

5.3 Locality and paging

In virtual memory, locality means that a process usually needs only a small group of pages at one time. That group is often called a locality or part of its working set.

If those pages stay in memory, page faults remain low. If they do not, the process begins faulting frequently and may thrash.

5.4 Locality and cache memory

Cache memory works because recently used and nearby data are likely to be accessed again. A good cache exploits locality and gives a high hit ratio.

Big picture: Cache memory uses locality to reduce RAM accesses, and virtual memory uses locality to keep only currently important pages in RAM.

6. Final Comparison Snapshot

Topic	Main idea	What to remember
Performance of Demand Paging	EAT depends heavily on page-fault rate.	Even a small page-fault rate can cause large slowdown.
Page Replacement	Choose a victim page when no free frame exists.	FIFO is simple, OPT is best but impractical, LRU is strong but costly.
Thrashing	System spends more time paging than executing.	Usually caused by too few frames for current working sets.
Cache Organization	Fast small memory between CPU and RAM.	Hit/miss behavior and mapping policy matter.
Locality of Reference	Programs reuse recent and nearby memory locations.	This is why cache and virtual memory work.

7. One-Page Summary

Demand-paging performance depends mainly on the page-fault rate. Since servicing a page fault is far slower than normal memory access, the operating system must keep faults rare.

Page replacement algorithms decide which page to remove when memory is full. FIFO is simple, OPT is ideal but theoretical, and LRU follows locality and performs well conceptually.

Thrashing occurs when the system spends too much time moving pages between disk and RAM and too little time doing useful work.

Cache memory organization places a small fast storage area between CPU and RAM. It depends on hit rate, miss penalty, and mapping policy.

Locality of reference is the principle that programs repeatedly use recent and nearby memory locations. It is the foundation of both caching and virtual memory.

8. Likely University Questions

Explain the performance of demand paging using effective access time.
What is page replacement? Explain FIFO, Optimal, and LRU.
What is Belady’s anomaly?
What is thrashing? Explain its causes and prevention.
Explain cache memory organization and cache hit / miss.
What is locality of reference? Explain its types.
How is locality of reference related to virtual memory?
Differentiate between FIFO, Optimal, and LRU page replacement algorithms.

Worked Example

2.4 Optimal Page Replacement (OPT)

The Optimal Page Replacement algorithm (OPT) replaces the page whose next use lies farthest in the future. In other words, when a page fault occurs and no free frame is available, the operating system looks ahead in the reference string and removes the page that will not be needed for the longest time.

The basic intuition is straightforward: if one page will be used very soon, it should be kept in memory, whereas a page that will not be required for a long time is the best candidate for replacement. Because of this decision rule, OPT produces the minimum possible number of page faults for a given page-reference string and a fixed number of page frames.

Key idea: Replace the page that is safest to remove now because it will be needed last in the future.

Algorithm	Rule	Strength	Weakness
Optimal (OPT)	Replace the page whose next use is farthest in the future.	Gives the lowest possible page-fault rate for a fixed number of frames.	Requires exact knowledge of future page references, so it cannot be implemented perfectly in real systems.

Why OPT is considered ideal

OPT is called an ideal or theoretical benchmark algorithm because no other page-replacement algorithm can perform better on the same reference string with the same number of frames. For this reason, OPT is often used as a standard for comparison when evaluating practical algorithms such as FIFO and LRU.

How OPT works

A page reference occurs.
If the page is already in memory, it is a hit; no replacement is needed.
If the page is not in memory, a page fault occurs.
If a free frame is available, the page is simply loaded.
If all frames are full, the OS examines the future reference string.
The page whose next use is farthest away in the future is selected as the victim page.
The new page is loaded into that frame.

Figure: OPT examines future page references and replaces the page needed farthest in the future.

Worked Example

Consider the reference string:

7, 0, 1, 2, 0, 3, 0, 4

Let the number of page frames be 3.

Load 7 → page fault
Load 0 → page fault
Load 1 → page fault
Reference 2 → page fault, memory is full

Current frames contain:

[7, 0, 1]

Now look ahead in the future reference string:

0, 3, 0, 4

Page 0 will be used soon.
Page 1 will not be used again.
Page 7 will not be used again.

Either 1 or 7 may be replaced, since neither is needed again. Suppose 7 is replaced.

[2, 0, 1]

OPT always makes the best replacement decision because it uses complete future knowledge.

Important properties of OPT

It gives the minimum page-fault count for a given reference string.
It is mainly used for comparison and analysis, not direct implementation.
It helps in evaluating how close practical algorithms come to the theoretical best.
It does not suffer from Belady’s anomaly.

Limitation: OPT is not practical in real operating systems because the OS cannot know exact future memory references in advance.

Why it still matters in OS study

Even though OPT cannot be implemented exactly in real systems, it remains extremely important in Operating Systems because it provides a benchmark. When we compare FIFO, LRU, or any approximation algorithm, we often compare their page-fault count with OPT to judge how efficient they are.

Summary: Optimal Page Replacement replaces the page whose next use is farthest in the future. It is the best possible page-replacement strategy in theory, but it is impractical in real systems because future references are not known exactly.