Chapter 9

Virtual Memory – Making Programs Feel Like They Have More Memory

What Is Virtual Memory?

Virtual memory is a technique that lets the system pretend there is more memory than there
actually is.

It separates:

• The logical address space (what the program thinks it has)

• From the physical memory (what's actually available in RAM)

Key Idea

Only the parts of a program that are needed right now are loaded into RAM.
The rest can stay on the disk and be loaded later when needed.

Why Is This Useful?

1. You don’t need to load the whole program into RAM to start running it

2. Programs can be larger than physical memory

3. Multiple processes can run at the same time and share memory

4. Makes process creation faster (less data needs to be loaded up front)

Example:

• Physical memory (RAM): 4 GB

• Program's logical address space: 16 GB

With virtual memory, the OS can pretend the program has 16 GB of memory and swap parts in
and out of RAM as needed.

How Is Virtual Memory Implemented?

There are two main methods:

1. Demand Paging

• Memory is divided into pages.

• Only the pages that are actually used are loaded into RAM.

• If a program tries to access a page that's not in RAM → causes a page fault

o The OS then loads the page from disk into memory.

This is the most common way to implement virtual memory.

2. Demand Segmentation

• Similar idea, but memory is divided into segments (e.g., code, stack, data).

• Only the segments that are needed are loaded into RAM.

• Less common today; mostly replaced by demand paging in modern OSes.

Real-Life Analogy

Think of a big book (your program):

• You’re reading just one chapter at a time (pages in RAM).

• The rest stays on the bookshelf (disk).

• If you need a chapter that isn’t in your hand, you go and get it (page fault).

Summary Table
Feature Explanation

Virtual Memory Allows using more logical memory than physical memory

Logical ≠ Physical Memory Logical space appears larger than actual RAM

On-Demand Loading Only load needed parts of program

Shared Memory Multiple processes can share memory areas

Faster Startup Program can begin before all of it is loaded

Implemented Using Demand Paging (most common), Demand Segmentation

 Demand Paging – Only Load What You Use

What Is Demand Paging?

Demand paging is a way to implement virtual memory where:

A page is only loaded into memory (RAM) when it is actually needed by the program.

This is different from older systems where the entire program had to be loaded into RAM
before it could start.

Why Use Demand Paging?

Less I/O

• Only transfer needed pages from disk → faster and saves disk/memory traffic.

Less Memory Needed

• Since not all pages are loaded at once, the system can run larger programs or more
programs at the same time.

Faster Program Start

• The program can begin running immediately, even if only part of it is in memory.

More Users Supported

• The system can support more processes at once, since each one only takes a small
amount of RAM at any time.

How It Works

When a process tries to use a page:

1. If the page is already in memory → use it immediately.

2. If the page is not in memory (but valid) → this triggers a page fault

o The OS loads the page from disk into a free frame in RAM.

3. If the reference is invalid (e.g., pointing to unallocated memory) → the OS aborts the
process.
 Lazy Swapper

• A lazy swapper doesn't bring pages into memory until they are actually needed.

• This saves time and resources.

• When applied to pages, this swapper is called a pager.

Terms to Remember

Term Meaning

Demand Paging Load pages into RAM only when needed

Page Fault Happens when a program requests a page that is not currently in memory

Lazy Swapper Only brings a page into memory if it's definitely going to be used

Pager The part of the OS responsible for handling page transfers

Invalid Reference Refers to memory the program doesn't legally own → causes a crash

Real-Life Analogy

Think of your program as a TV series with 100 episodes:

• You don’t download all 100 episodes at once.

• You stream each episode only when you watch it.

• If you try to play an episode that doesn't exist → you get an error (invalid reference).

• This is exactly how demand paging works.

Summary

Benefit Explanation

Less I/O Only transfer pages when needed

Benefit Explanation

Less Memory Usage Only active pages are in RAM

Faster Startup Program starts before all pages are loaded

More Users Supported System can support more processes at the same time

Page Fault Handling Load missing page; abort on illegal memory access
 Valid–Invalid Bit – Controlling Page Access

What Is the Valid–Invalid Bit?

Each entry in the page table has a special bit called the valid-invalid bit.

It tells the system whether a page is:

• Valid (v) → The page is currently in memory (RAM), and it's safe to access.

• Invalid (i) → The page is not in memory or not part of the process’s legal memory
space.

How It Works

When a process accesses a page:

1. The CPU looks up the page table entry.

2. It checks the valid-invalid bit:

o If the bit is valid (v) → access is allowed

o If the bit is invalid (i) → a page fault occurs

What Happens on Page Fault?

If the bit is invalid (i):

• This means the page is not currently in RAM.

• The OS handles the page fault by:

o Checking if the access was legal

o If it was:

▪ It loads the page from disk into RAM

▪ Updates the page table entry to valid (v)

o If it wasn’t legal:

▪ The OS terminates the process (illegal memory access)

 Initial State

• When a process starts, all valid-invalid bits are set to invalid (i).

• Pages are brought into memory only when needed (demand paging).

• Bits are updated to valid (v) once the page is loaded.

Real-Life Analogy

Think of the valid-invalid bit like a pass card system at a library:

• If your card is valid, you can enter the reading room (page in RAM).

• If it’s invalid, you can’t enter (page not in RAM → page fault).

• If you have a legal request, the librarian brings the book (loads the page).

• If your request is illegal, you’re kicked out of the library (process aborts).

Summary Table

Bit Value Meaning Result

v Page is valid (in memory) Memory access allowed

i Page is invalid (not in memory or illegal) Page fault → OS takes action

 Page Fault – What Happens When a Page Is Missing

What Is a Page Fault?

A page fault happens when a program tries to access a page that is not currently in RAM.

This is common in systems using demand paging.

How Does a Page Fault Occur?

1. The CPU generates a logical address.

2. The OS checks the page table entry.

3. If the valid-invalid bit is i (invalid) → this triggers a page fault.

What Happens During a Page Fault?

The operating system follows these steps:

Step-by-Step Page Fault Handling:

Step Action

Trap to the OS – The CPU pauses and passes control

to the OS.

OS checks another internal table to see if:

- The access is invalid → abort the

program

- The page is just not in memory →

continue

If the page is valid but not in memory:

→ Find a free frame in physical memory

Step Action

Read the page from disk (backing store) into that

frame

Update the page table:

• Set the frame number

• Set valid-invalid bit = v |

| | Restart the instruction that caused the page fault — the CPU tries again, and this
time the page is ready in RAM |

Visual Flow

Page Not in RAM → Page Fault → OS Checks Validity

Invalid → Abort

Valid → Load Page → Update Table →

Restart

Real-Life Analogy

Think of a page fault like looking for a book in your backpack:

• You try to read a book (page).

• It’s not there (page not in memory) → page fault.

• You ask the librarian (OS) to get it from the archive (disk).

• The librarian brings it back, updates your list, and lets you continue reading.

Summary Table

Term Description

Page Fault Happens when a process accesses a page not in RAM

Term Description

Page Table Says whether the page is valid (v) or invalid (i)

OS Action If valid but not in RAM → load it from disk

Frame A free space in physical memory to load the missing page

Final Step Restart the instruction now that the page is in memory
 Page Replacement – Making Room for New Pages

What Is Page Replacement?

Page replacement happens when:

A program needs a page that is not in memory, and there’s no free space left in RAM to load it.

So, the operating system must:

1. Choose a page that’s already in memory, but not currently being used

2. Swap it out (write it back to disk if needed)

3. Load the new page into the freed-up space

Why Is It Needed?

Page replacement is part of demand paging and is necessary when:

• All frames are full

• A new page needs to be brought in (due to a page fault)

• We need to make room for the new page in memory

Goals of Page Replacement

Minimize page faults — fewer interruptions = faster performance

Efficient use of memory — don’t keep pages that aren’t being used

What Happens in Page Replacement?

1. Page fault occurs

2. No free frame is available

3. Page replacement algorithm is used to choose a victim page

4. If the victim page is modified, write it to disk (this takes time)

o OS uses a modify (dirty) bit to track this

 5. Load the new page into the freed frame

6. Update the page table

7. Restart the instruction

Modify (Dirty) Bit

Each page has a dirty bit that tells if it has been modified:

• If dirty = 1 → page has been changed → must be written back to disk

• If dirty = 0 → no need to write it → just discard it

This saves time and I/O overhead when replacing pages.

Important Benefit

Page replacement fully separates logical memory from physical memory.

• Logical address space (what the program sees) can be much bigger

• Physical memory can stay small — OS just swaps pages in and out as needed

This is the core idea behind virtual memory:

Run large programs with limited RAM.

Real-Life Analogy

Imagine your desk (RAM) is full of open books (pages).

You now need a new book, but there's no space.

• You look for a book you're not using right now

• If you’ve written notes inside it (dirty), you copy them to storage (disk)

• Then you replace it with the new book

That’s page replacement.

Summary Table
Term Meaning

Page Replacement Replaces a page in RAM when no free frames are available

Dirty Bit Tracks if a page has been modified (1 = needs to be saved to disk)

Page Fault Triggers replacement when the page isn’t in memory

Replacement Algorithm Decides which page to remove (explained in next topic)

Benefit Allows virtual memory > physical memory

Reference string: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5

We’ll use this string to explain how each algorithm works, and we’ll assume the system has 3
page frames (slots in memory).

Goal of Page Replacement Algorithms

Choose which page to remove from memory when a new page must be loaded, aiming to
cause the fewest page faults.

FIFO – First-In, First-Out

Idea:

Remove the oldest page in memory (the one that came in first).

How It Works:

• Pages are stored like a queue.

• When memory is full and a new page comes in → kick out the one at the front.

Simple but can be bad in some cases (e.g., Belady’s anomaly).

Optimal – Best Case (Used for Comparison Only)

Idea:

Replace the page that will not be used for the longest time in the future.

How It Works:

• Look ahead in the reference string.

• Choose the page whose next use is farthest away (or never used again).

Has the lowest possible number of page faults.

Can’t be implemented in practice (we can’t see the future), but used to compare other
algorithms.
 LRU – Least Recently Used

Idea:

Remove the page that hasn’t been used for the longest time in the past.

How It Works:

• Keep track of when each page was last used.

• Replace the page that was used least recently.

Good approximation of optimal

Requires extra tracking (e.g., time stamps or a stack)

Counting Algorithms – Based on Usage Frequency

These algorithms keep a counter of how often a page is used.

LFU – Least Frequently Used

• Replace the page that has been used the fewest number of times.

• Idea: rarely used pages are less likely to be used again.

Problem: A page that was used heavily in the beginning but not recently may still stay in
memory.

MFU – Most Frequently Used

• Replace the page that has been used the most times.

• Based on the idea: “If a page was used a lot, maybe it won’t be needed anymore.”

Rarely used, mostly theoretical.

Example Run (with FIFO)

Using 3 frames and reference string:

1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5

FIFO Steps:

Step Memory Page Fault?

1 1 Yes

2 12 Yes

3 123 Yes

4 234 Yes (1 removed)

1 341 Yes (2 removed)

2 412 Yes (3 removed)

5 125 Yes (4 removed)

1 125 No

2 125 No

3 253 Yes (1 removed)

4 534 Yes (2 removed)

5 345 Yes (5 stays, 2 removed again)

Total page faults with FIFO = 9

Summary Comparison

Algorithm Strategy Strength Weakness

Can remove frequently used

FIFO Remove oldest page Simple
pages

Remove farthest future

Optimal Lowest page faults (ideal) Not implementable
use
Algorithm Strategy Strength Weakness

Remove least recently Good real-world Needs tracking or hardware

LRU
used performance support

Good when usage is

LFU Remove least used May keep old but unused pages
uneven

MFU Remove most used Theoretical interest Often not useful in practice
 Thrashing – When the System Spends All Its Time Swapping

What Is Thrashing?

Thrashing happens when a process doesn't have enough pages in memory, so it keeps causing
page faults over and over.

As a result, the system spends more time:

• Swapping pages in and out

• And less time actually running processes

This leads to very poor performance.

What Causes Thrashing?

Let’s break down the chain of events:

1. A process doesn’t have enough pages → High page-fault rate

2. CPU sits idle waiting for pages → Low CPU utilization

3. OS thinks the system is underused → Increases multiprogramming

4. Adds more processes → More memory pressure

5. Even fewer pages per process → Even more page faults

6. This creates a vicious cycle → Thrashing

Thrashing Explained Simply

Thrashing = Too much swapping, not enough computing

The OS is "thrashing" between disk and memory, doing constant page replacements with
almost no useful work getting done.

Symptoms of Thrashing

• CPU usage goes down

 • Disk activity (paging) goes way up

• Programs slow down dramatically

• System becomes unresponsive

Example:

Imagine a process that needs 6 pages to run smoothly, but the OS only gives it 3 frames.

• The process keeps requesting pages not in memory.

• Every few instructions → page fault

• OS keeps swapping old pages out to load new ones.

• The process makes no progress.

Now multiply this by many processes → System-wide slowdown

Real-Life Analogy

Think of trying to write a paper with only one sheet of paper on your desk.

• You keep swapping pages from your folder.

• You waste time picking up and putting back papers.

• You barely write anything.

That’s thrashing.

Summary Table

Term Description

Thrashing Constant page faults due to not enough memory

Cause High degree of multiprogramming or not enough frames per process

Effect Low CPU usage, high disk I/O, poor performance

System Reaction OS may mistakenly add more processes, making the problem worse