Thrashing, Locality of Reference & Cache Memory in Operating System

OPERATING SYSTEM - CHAPTER 26

Thrashing, Locality of Reference and Cache Memory in Operating System

These three topics look separate at first, but they are actually connected by one important idea: keep frequently needed data close to the CPU and avoid expensive memory transfers.

Locality of Reference explains why a program repeatedly uses a small region of memory. Cache Memory takes advantage of that behavior. Virtual-memory systems also depend on locality. When a process does not have enough frames for the pages it is actively using, page faults can become extremely frequent and the system can enter Thrashing.

Quick Answer:

Locality of Reference means programs tend to access recently used or nearby memory locations repeatedly.

Cache Memory is a small and very fast memory located close to the CPU that stores recently or frequently needed data and instructions.

Thrashing happens in virtual memory when excessive page faults cause the system to spend too much time moving pages between RAM and storage instead of performing useful computation.

Jump to a Topic

Big Connection Locality Cache Memory Cache Performance Thrashing Working Set Page Fault Frequency Prevention Differences Exam Revision FAQ

The Big Connection: Locality, Cache and Thrashing

Modern computer systems contain several levels of memory. The fastest memory is small and expensive. Larger memory is slower.

The complete memory system therefore works efficiently only when the computer keeps the most useful data in the faster levels.

CPU SIDE Cache Stores very frequently needed data close to the CPU.

PROGRAM BEHAVIOR Locality Explains why recently used and nearby data is likely to be used again.

MAIN MEMORY RAM Holds active programs and pages required for execution.

VIRTUAL MEMORY RISK Thrashing Too many missing pages can create excessive paging activity.

Easy Memory Trick:

Good Locality → Useful data stays close → More Cache Hits and fewer unnecessary page transfers

Poor memory availability for active pages → More Page Faults → Possible Thrashing

Memory Hierarchy Before Understanding Cache and Thrashing

Computer memory is arranged in levels. Faster memory is generally smaller, while larger memory is usually slower.

L1 Cache - Very Small and Very Fast

L2 Cache

L3 Cache

Main Memory - RAM

Secondary Storage - SSD / Disk

Cache Memory reduces the speed gap between CPU and RAM. Virtual Memory deals with the relationship between virtual address spaces, RAM and backing storage. These are related performance topics, but they are not the same mechanism.

What Is Locality of Reference?

Programs usually do not access random memory locations equally. During a short period, they tend to repeatedly access a relatively small region of memory.

Simple Definition:
Locality of Reference is the tendency of a program to repeatedly access recently used memory locations or locations close to recently accessed memory.

This property is extremely important because both cache systems and virtual memory can use it to keep useful data closer to the processor.

Visual Example of Locality

Imagine a process with many memory blocks, but only a small area is being accessed repeatedly.

Memory Access Heatmap

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

The darker active region represents memory locations used repeatedly. Keeping such frequently accessed data in faster memory can improve performance.

Types of Locality of Reference

T Temporal Locality If a memory location is accessed now, there is a good chance it will be accessed again soon.

Example: instructions inside a loop.

S Spatial Locality If one location is accessed, nearby memory locations are likely to be accessed soon.

Example: nearby elements of an array.

Q Sequential Locality A special and common access pattern where consecutive locations are accessed one after another.

Example: reading an array from beginning to end.

Temporal Locality Example

Consider this repeated sequence:

A → B → C → A → B → C → A → B → C

A, B and C are repeatedly reused. This is temporal locality.

Repeated Access Timeline

A

B

C

A

B

C

A

B

C

Keeping A, B and C in a fast cache can make repeated accesses much faster.

Spatial Locality Example

Suppose a program accesses array elements:

Array[0] Array[1] Array[2] Array[3] Array[4]

These values are stored near each other. Fetching a block containing nearby values allows future references to benefit from the data already brought closer to the CPU.

Why Is Locality Important?

CACHE More Hits Frequently reused data can remain in fast cache memory.

VIRTUAL MEMORY Fewer Faults Active pages can remain in RAM if enough frames are available.

CPU Less Waiting Fewer expensive memory transfers improve effective performance.

THRASHING Lower Risk A stable active working set reduces repeated page swapping.

What Is Cache Memory?

The CPU is much faster than main memory. If the processor had to wait for RAM on every memory access, a lot of CPU time would be wasted.

Simple Definition:
Cache Memory is a small and very fast memory located close to the CPU that stores copies of frequently or recently used instructions and data.

The processor checks the cache before going to slower memory levels.

How Cache Memory Works

CACHE ACCESS PIPELINE

1 CPU Requests Data Processor generates a memory request.

2 Check Cache Cache is searched for the required block.

3 Cache Hit Data is found and returned quickly.

4 Cache Miss If absent, lower memory must be accessed.

5 Fill Cache Requested block may be copied into cache for future reuse.

Cache Hit and Cache Miss

Cache Hit

The requested data is already available in the cache.

Cache Hit = Fast access

Cache Miss

The requested data is not present in the cache.

Cache Miss = Access slower memory level

Cache Hit Ratio, Miss Ratio and Average Memory Access Time

HIT RATIO Cache Hit Ratio

Hit Ratio = Cache Hits / Total Accesses

MISS RATIO Cache Miss Ratio

Miss Ratio = 1 - Hit Ratio

AMAT Average Memory Access Time

AMAT = Hit Time + Miss Rate × Miss Penalty

In this formula, Miss Penalty means the additional delay caused by a cache miss after the initial cache lookup. If a textbook defines miss time differently, follow the definition given in that numerical.

Cache Performance Solved Example

Given

Cache Hit Time = 1 ns Cache Hit Ratio = 95% Miss Penalty = 50 ns

Step 1: Find Miss Rate

Miss Rate = 1 - 0.95 = 0.05

Step 2: Apply AMAT Formula

AMAT = Hit Time + Miss Rate × Miss Penalty = 1 + 0.05 × 50 = 1 + 2.5 = 3.5 ns

Final Answer:
Average Memory Access Time = 3.5 ns

L1, L2 and L3 Cache

Cache Level	General Position	Typical Characteristic	Purpose
L1	Closest to CPU core	Smallest and fastest of common cache levels	Serve very frequent accesses quickly
L2	Near or within CPU core hierarchy	Larger than L1, usually slower than L1	Back up L1 misses
L3	Often shared by multiple cores	Larger but generally slower than L1 and L2	Reduce accesses to RAM

Exact cache organization varies by processor architecture. The operating system usually does not perform every individual L1/L2/L3 cache replacement decision. CPU hardware handles most cache lookup and replacement behavior automatically.

Basic Cache Mapping Techniques

When a memory block enters cache, the system needs a rule for deciding where that block can be stored.

D Direct Mapping Each memory block maps to one specific cache location. It is simple but can cause conflict misses.

F Fully Associative A block can be placed in any cache line. It is flexible but requires more complex lookup hardware.

S Set Associative Cache is divided into sets. A block maps to one set but may occupy different lines inside that set.

Main Types of Cache Misses

FIRST ACCESS Compulsory First access to a block can miss because the block has never been loaded.

LIMITED SIZE Capacity The working data set is too large for the available cache capacity.

MAPPING COLLISION Conflict Multiple blocks compete for the same allowed cache locations.

MULTICORE EFFECT Coherence In multiprocessor systems, coherence activity can also invalidate or update cached data.

Write-Through and Write-Back Cache

Write-Through

A write updates the cache and also propagates the change to the lower memory level according to the system design.

Easier consistency model, but can create more memory traffic.

Write-Back

A write updates the cached copy first. The modified block is written back later when required.

Can reduce write traffic, but modified data must be tracked carefully.

Does the Operating System Directly Control CPU Cache?

Not in the same way that it manages virtual-memory pages.

Modern CPU caches are largely controlled by processor hardware. Cache hits, cache-line fills and many replacement decisions happen automatically in hardware.

Important Difference:

CPU Cache = Mostly hardware-managed

Virtual Memory Pages = Hardware and Operating System cooperate closely

The operating system can still influence cache behavior indirectly through scheduling, memory placement, page mapping, process migration and architecture-specific cache or coherency operations.

CPU Cache vs Operating System Page Cache

The word "cache" can refer to more than one thing.

CPU Cache Small hardware memory near the processor, such as L1, L2 and L3.

OS Page Cache Main-memory area used by the operating system to keep recently accessed file data and reduce repeated storage reads.

Virtual Memory Address-space and page-management system that maps virtual pages to physical frames and backing storage.

These mechanisms can all improve performance, but they operate at different levels of the computer system.

What Is Thrashing in Operating System?

Virtual memory works well when the pages a process actively needs remain in RAM most of the time.

Problems begin when a process or group of processes receives too few frames. Pages are removed, then quickly needed again, causing another page fault.

Simple Definition:
Thrashing is a condition in which excessive page faults cause the operating system to spend a large amount of time moving pages between main memory and secondary storage instead of performing useful execution.

Page Fault Activity THRASHING RISK

How Thrashing Starts Step by Step

1 Too Few Frames A process cannot keep its active pages in RAM.

2 Page Faults Rise Frequently needed pages are repeatedly missing.

3 More Page I/O Pages are loaded from and removed to backing storage.

4 CPU Progress Falls Processes spend more time waiting for memory operations.

5 System Slows Paging activity can dominate useful computation.

Main Causes of Thrashing

CAUSE 1 Too Many Processes High multiprogramming can make many processes compete for limited frames.

CAUSE 2 Too Few Frames A process may not be able to hold its active working set.

CAUSE 3 Poor Locality If the process rapidly moves between many unrelated pages, its active set may become difficult to keep resident.

CAUSE 4 Replacement Pressure Recently evicted pages may be needed again immediately.

Symptoms of Thrashing

• Very high page-fault activity.
• Heavy storage input/output caused by paging.
• Low useful CPU progress.
• Processes frequently wait for pages.
• System responsiveness becomes poor.
• Adding more active processes can make performance worse.

Thrashing does not mean the CPU itself is slow. The main problem is that the system spends too much time satisfying memory demands instead of executing useful instructions.

Working Set and Thrashing

A process usually has a group of pages that it actively uses during a recent period of execution.

Simple Idea:
The Working Set is the collection of pages a process has been actively referencing during a recent execution window.

If enough of those pages stay in RAM, the process can continue with relatively few page faults.

If too many working-set pages are missing, the process repeatedly faults and performance drops.

Example Working Set

P0

P1

P2

P3

P4

P5

P6

In this example, Pages 1, 2 and 3 represent the currently active region.

Working Set and Locality Are Closely Related

A working set is useful because program execution usually shows locality.

During one phase, a process may execute one function and repeatedly access a specific group of data pages.

Later, the program can move to another phase and its working set can change.

Locality explains why a small active set often exists. Working-set management tries to keep that active set available in RAM.

Page Fault Frequency Method

Another way to control memory pressure is to observe how frequently page faults occur.

Page Fault Frequency:

PFF = Number of Page Faults / Number of Page References

Conceptual Page Fault Frequency

Low Fault Rate Monitor High Fault Rate

There is no single universal numeric threshold that means thrashing for every computer system. The operating system evaluates fault behavior relative to workload, available memory and system policy.

How Page Fault Frequency Can Guide Frame Allocation

Fault Rate Too High

The process may need more physical frames.

High PFF can indicate that the active page set does not fit well in the current frame allocation.

Fault Rate Very Low

The process may have more frames than it currently needs.

Some systems may be able to reassign memory while still maintaining acceptable performance.

Degree of Multiprogramming and Thrashing

Multiprogramming means keeping several processes active so that the CPU can work on another process when one process waits.

Increasing multiprogramming can improve resource use, but only up to a point.

Example

Suppose physical memory can comfortably hold the active working sets of four processes.

If many more memory-intensive processes are added without enough RAM, each process may receive fewer frames.

Page faults rise, storage traffic rises, and useful progress may fall.

More processes do not always mean better performance. Beyond the available-memory limit, higher multiprogramming can contribute to thrashing.

How to Prevent or Reduce Thrashing

METHOD 1 More Frames Give a process enough frames for its actively used pages.

METHOD 2 Working Set Estimate the active set and try to keep those pages resident.

METHOD 3 Control PFF Monitor page-fault behavior and adjust frame allocation.

METHOD 4 Reduce Load Lower the degree of multiprogramming when memory pressure is too high.

Local and Global Page Replacement During Memory Pressure

Local Replacement

A process selects a victim from its own allocated frames.

This can limit how directly one process affects another process's resident pages.

Global Replacement

A replacement decision can draw from a broader pool of frames, depending on the system policy.

This provides flexibility but can allow one workload's behavior to influence another workload more strongly.

Simple Thrashing Example

Suppose a process actively needs these pages:

Working Set: P1, P2, P3, P4

But it receives only two physical frames.

Frames Available: Frame 1 Frame 2

The process moves repeatedly among P1, P2, P3 and P4. Two pages cannot hold the complete four-page active set.

P1 → Load P2 → Load P3 → Replace one page P4 → Replace one page P1 → Needed again P2 → Needed again ...

If this pattern continues, recently removed pages are repeatedly demanded again. Page-fault activity becomes extremely high.

Cache Miss vs Page Fault

Basis	Cache Miss	Page Fault
Meaning	Requested data is not in the current cache level	Required virtual page is not currently resident in physical memory
Handled Mainly By	Processor hardware and cache hierarchy	Hardware detects condition, operating system handles fault
Next Level	Lower cache level or RAM	RAM must obtain page data from its backing source when necessary
Typical Cost	Usually much smaller than a page fault	Can be extremely expensive because storage I/O may be involved
Relation to Locality	Good locality improves hit rate	Good locality helps active pages stay useful in RAM

Cache Memory vs Virtual Memory vs Thrashing

Basis	Cache Memory	Virtual Memory	Thrashing
Type	Fast memory mechanism	Memory-management abstraction	Performance problem
Main Goal	Reduce average data-access time	Provide flexible virtual address spaces and page management	Not a goal; it is an undesirable condition
Main Location	Near or inside processor hierarchy	Uses page tables, RAM and backing storage	Occurs when paging activity becomes excessive
Main Event	Cache Hit / Cache Miss	Page translation / Page Fault	Very frequent page faults
Relation to Locality	Strongly benefits from locality	Demand paging benefits from locality	Poor frame availability for the active locality can cause it

Cache AMAT Calculator

Use this tool to calculate Average Memory Access Time.

Cache Performance Lab

Cache Hit Time (ns)

Hit Rate (%)

Miss Penalty (ns)

Page Fault Frequency Calculator

This calculator finds the observed page-fault ratio for a sequence of memory references.

Page Fault Frequency Lab

Number of Page Faults

Total Page References

Common Student Confusions

Is Cache Memory the Same as RAM?

No. Cache is much smaller and faster and sits closer to the CPU. RAM is larger main memory.

Is Cache Memory the Same as Virtual Memory?

No. CPU cache reduces access latency. Virtual memory provides address translation and allows pages to move between RAM and backing storage when needed.

Is a Cache Miss the Same as a Page Fault?

No. A cache miss usually means a lower cache level or RAM must be checked. A page fault means the required virtual page is not currently resident in physical memory.

Does Every High Page Fault Rate Mean Thrashing?

Not automatically. Thrashing refers to sustained excessive paging activity that seriously reduces useful system progress.

Does Good Locality Guarantee No Thrashing?

No. Good locality helps, but if a process still receives too few frames for its active working set, page faults can remain high.

Does the Operating System Manage L1 Cache Like It Manages Pages?

No. CPU caches are mainly hardware-managed, while virtual-memory page management requires much more direct operating-system involvement.

Is More Multiprogramming Always Better?

No. If memory pressure becomes too high, adding more processes can increase paging and reduce performance.

Locality, Cache and Thrashing in One View

Locality Describes program access behavior.

Cache Exploits locality to reduce average memory-access time.

Thrashing Appears when active pages cannot remain resident and faults become excessive.

Locality is a behavior.

Cache is a performance mechanism.

Thrashing is a virtual-memory performance failure condition.

One-Minute Revision

Locality of Reference Programs repeatedly use recently accessed or nearby memory locations.

Temporal Locality Recently used data is likely to be used again soon.

Spatial Locality Nearby memory locations are likely to be accessed soon.

Cache Memory Small fast memory near the CPU.

Cache Hit Requested data is already present in cache.

Cache Miss Lower memory level must be accessed.

Working Set Recently active group of virtual-memory pages.

PFF Page Faults divided by Total Page References.

Thrashing Excessive paging activity reduces useful computation.

Thrashing, Locality and Cache Memory Exam Preparation

2-Mark Locality Definition

Locality of Reference is the tendency of a program to repeatedly access recently used memory locations or memory locations close to recently accessed locations.

2-Mark Cache Definition

Cache Memory is a small and high-speed memory located close to the CPU that stores frequently or recently used instructions and data.

2-Mark Thrashing Definition

Thrashing is a condition in which excessive page faults cause a system to spend more time moving pages between RAM and storage than performing useful process execution.

Important Formulas

Cache Hit Ratio = Cache Hits / Total Accesses Cache Miss Ratio = 1 - Hit Ratio AMAT = Hit Time + Miss Rate × Miss Penalty Page Fault Frequency = Page Faults / Total Page References

For a 5-Mark Question

1. Define Locality of Reference.
2. Explain Temporal and Spatial Locality.
3. Define Cache Memory.
4. Explain Cache Hit and Cache Miss.
5. Define Thrashing and list its causes.

For a 10-Mark Question

1. Memory hierarchy.
2. Meaning of Locality of Reference.
3. Temporal Locality.
4. Spatial Locality.
5. Sequential Locality.
6. Working Set.
7. Cache Memory.
8. Cache Hit and Miss.
9. Hit Ratio and Miss Ratio.
10. Average Memory Access Time.
11. L1, L2 and L3 Cache.
12. Cache Mapping.
13. Cache Miss Types.
14. Thrashing.
15. Causes and Symptoms of Thrashing.
16. Page Fault Frequency.
17. Working Set Model.
18. Thrashing Prevention.

Frequently Asked Questions

What is Thrashing in Operating System?

Thrashing is a condition where excessive page faults cause a system to spend a large amount of time transferring pages between RAM and backing storage instead of performing useful computation.

What is Locality of Reference?

Locality of Reference is the tendency of a program to repeatedly access recently used memory locations or nearby locations.

What is Temporal Locality?

Temporal Locality means that a memory location used recently is likely to be used again soon.

What is Spatial Locality?

Spatial Locality means that memory locations near a recently accessed location are likely to be accessed soon.

What is Cache Memory?

Cache Memory is a small and very fast memory near the CPU that stores frequently or recently used instructions and data.

What is a Cache Hit?

A Cache Hit occurs when the requested data is found in the cache.

What is a Cache Miss?

A Cache Miss occurs when the requested data is not found in the cache and a lower memory level must be accessed.

What is the Working Set of a Process?

The Working Set is the group of virtual-memory pages actively referenced by a process during a recent execution period.

What is Page Fault Frequency?

Page Fault Frequency is the ratio of page faults to page references during an observed interval.

How Can Thrashing Be Reduced?

Thrashing can be reduced by allocating enough frames for active pages, using working-set or page-fault-frequency control, and reducing the degree of multiprogramming when memory pressure becomes too high.

Is Cache Memory the Same as Virtual Memory?

No. Cache Memory reduces access latency by keeping frequently used data close to the CPU, while Virtual Memory provides address translation and manages virtual pages across RAM and backing storage.

What is the Difference Between a Cache Miss and a Page Fault?

A Cache Miss means data is not present in the current cache level, while a Page Fault means the required virtual-memory page is not currently resident in physical RAM.

Conclusion

Locality of Reference explains one of the most important behaviors of real programs: programs repeatedly access a relatively small area of memory during a period of execution.

Cache Memory takes advantage of this behavior by keeping recently or frequently used data close to the CPU.

A high cache hit rate can significantly reduce average memory-access time.

Virtual memory also benefits from locality. If the actively used pages of a process remain in RAM, execution can continue with relatively few page faults.

But if too many active pages compete for too few physical frames, the operating system may continuously load and remove pages.

This excessive paging condition is called Thrashing.

Working-set analysis, Page Fault Frequency monitoring, suitable frame allocation and control of multiprogramming can help reduce the risk.

Final Memory Trick:

Temporal Locality = Use Again Soon

Spatial Locality = Use Nearby Location Soon

Cache Hit = Data Found in Cache

Cache Miss = Go to Lower Memory Level

Working Set = Active Pages

Too Few Frames + High Page Faults = Thrashing

Good Locality = Better Cache and Virtual-Memory Performance