1

[Link]
Professor, CSE, UEC

[Link], CSE 02-03-2026

 Swap space is a portion of secondary storage (hard disk or
SSD) reserved by the OS
 to temporarily store memory pages that are not currently in use
in physical memory (RAM).
 When RAM becomes full, the OS:
 Swaps out inactive pages from RAM to disk.
 Swaps in required pages from disk back to RAM.
 This mechanism is part of virtual memory management,
allowing the system to run programs larger than the available
physical memory.

[Link], CSE 02-03-2026 2

Why Swap Space is Needed
 Physical memory (RAM) is limited. But users may:
 Run multiple applications simultaneously.
 Execute large programs.
 Open many browser tabs.
 Perform memory-intensive tasks.

[Link], CSE 02-03-2026 3

How Swap Space Works
 Each process has multiple pages.
 Only some of these pages are kept in RAM.
 The remaining pages are stored in swap space.
 When a page not in RAM is needed → Page Fault occurs.
 OS loads that page from swap space into RAM.

[Link], CSE 02-03-2026 4

Example:
 Physical memory = 4 pages
 Swap space = 8 pages
 4 processes: P0, P1, P2, P3
 Possible situation:
 P0 → 1 page in RAM, rest in swap
 P1 → 1 page in RAM, rest in swap
 P2 → 1 page in RAM, rest in swap
 P3 → All pages in swap (not currently running)
 1 swap block still free

[Link], CSE 02-03-2026 5

 Even though RAM is small, the system behaves as if it has
more memory because inactive pages are stored on disk.
 This is how the OS creates the illusion of larger memory.
[Link], CSE 02-03-2026 6
 A page fault occurs when a process tries to access a virtual page
that is not currently present in physical memory (RAM).
 That page may:
 Be stored in swap space (disk)
 Not yet loaded into memory
 When this happens, the OS must fix the problem.
Who Handles the Page Fault?
 The hardware manages the TLB (or)
 The OS manages the TLB
 OS always handles the page fault using a special routine called
the Page Fault Handler.
[Link], CSE 02-03-2026 7
 A page fault occurs when:
 The page has been swapped out to disk
 The page has not yet been loaded (demand paging)
 The page was never allocated
 Invalid memory access (illegal reference)

[Link], CSE 02-03-2026 8

What Happens During a Page Fault?
Step 1: CPU Tries to Access Memory
 CPU generates a virtual address.
Step 2: Check Page Table
 If the page is not present in RAM, a page fault occurs.
Step 3: OS Takes Control
 The OS runs the page fault handler.
Step 4: Find the Page on Disk
 The OS checks the Page Table Entry (PTE). If the page was
swapped out, the PTE contains:
 The disk address where the page is stored.
[Link], CSE 02-03-2026 9
Step 5: Load Page from Disk
 The OS:
 Finds a free frame in RAM
 Sends a disk request
 Loads the page into memory
Step 6: Update Page Table
 After loading:
 Present bit = 1
 PFN (frame number) is updated

[Link], CSE 02-03-2026 10

Step 7: Restart the Instruction
 The CPU retries the same instruction.
 Now:
 Address translation works
 Program continues normally

What Happens to the Process During This Time?

 While the disk is loading the page:
 The process goes into Blocked state
 The OS runs another process
This improves
[Link], CSE CPU usage (multiprogramming). 02-03-2026 11
 When someone asks:
 “What happens when a program fetches some data from
memory?”,
 All the different possibilities.

1. Hardware Control Flow (During Address Translation)

 When CPU accesses memory:
Step 1: Check TLB
 The hardware first checks the TLB.

[Link], CSE 02-03-2026 12

 Case 1: TLB Hit
 Translation found in TLB.
 Physical address is formed.
 Memory access happens.
 Program continues normally.

 Case 2: TLB Miss + Page Present

 TLB does not contain the translation.
 Hardware checks the Page Table.
 Page is:
 Valid
 Present in RAM
[Link], CSE 02-03-2026 13
What happens?
 Hardware/OS loads PFN into TLB.
 Instruction is retried.
 This time → TLB Hit.
 Program continues.
 This is a normal TLB miss (no page fault).

 Case 3: TLB Miss + Page Not Present

 Page is valid (allowed to access).
 But not present in RAM.
 It is stored in disk (swap space).
 This causes a Page Fault.
 Now the OS must handle it.
[Link], CSE 02-03-2026 14
 Case 4: Invalid Page
 Page is not valid.
 Example:
 Accessing memory outside program range
 Bug in program
 Null pointer access
 Hardware traps to OS.
 The OS usually:
 Terminates the process
 Shows segmentation fault error
[Link], CSE 02-03-2026 15
2. Software Control Flow (During Page Fault)
 Now let’s see what the OS does when a page fault occurs.
Step 1: Find a Free Frame
 OS checks:
 Is there a free frame in RAM?
 If YES → Use it
 If NO → Run page replacement algorithm (LRU, FIFO, etc.)
 Remove some other page
 Free that frame

[Link], CSE 02-03-2026 16

Step 2: Load Page from Disk
 OS issues disk I/O request.
 Page is read from swap space.
 This is slow.
 During this time:
 The process goes into Blocked state
 OS runs another process

[Link], CSE 02-03-2026 17

Step 3: Update Page Table
 After disk read completes:
 Mark page as Present = 1
 Update PFN with new frame number

Step 4: Restart Instruction

 Instruction is retried.
 First retry → TLB Miss
 TLB gets updated
 Second retry → TLB Hit
 Memory access succeeds
[Link], CSE 02-03-2026 18
 When a page fault occurs and there is no free frame in RAM,
 the OS must decide:
 Which page should be removed from memory?
 The rule used to select a page for removal is called a Page
Replacement Policy (Algorithm).

Why Page Replacement is Needed?

 RAM is limited. When it becomes full:
 One page must be removed.
 The new required page is loaded.
 This is called page replacement.
[Link], CSE 02-03-2026 19
 FIFO is one of the earliest and simplest page replacement
policies.
 The page that entered memory first is removed first when
replacement is needed.
 It works like a queue:
 New pages are added at the rear.
 The oldest page (front of queue) is removed.

[Link], CSE 02-03-2026 20

 Page Reference:
01201303121

Total Count
Total Accesses = 11
Hits = 4
Misses = 7

[Link], CSE 02-03-2026 21

[Link], CSE 02-03-2026 22
Important Observation
 Even though: Page 0 was used many times. FIFO still removed it.
 Why?
 Because FIFO only cares about arrival time, not usage frequency or
recency.

Why FIFO Performs Poorly?

 FIFO does not consider:
 How frequently a page is used
 How recently it was used
 Future usage
 It blindly removes the oldest page.
 This may remove a very important page.
[Link], CSE 02-03-2026 23
Comparison with Optimal
 The Optimal algorithm removes the page that will not be
used for the longest time in the future.
 FIFO cannot predict importance, so:
 FIFO → Lower hit rate
 Optimal → Minimum page faults
 In the example mentioned:
 FIFO hit rate ≈ 36.4%
 Optimal performs significantly better.

[Link], CSE 02-03-2026 24

 It is a page replacement algorithm that replaces the page whose
next use will occur farthest in the future,
 thereby producing the minimum possible number of page faults.

Basic Principle
 When a replacement is required:
 Look at all pages currently in memory.
 Check their next future use.
 Remove the page that will be used last (or not used again).
 This ensures the least number of page faults.

[Link], CSE 02-03-2026 25

Example
 Reference string:
0, 1, 2, 0, 1, 3, 0, 3, 1, 2, 1
 Number of frames = 3
 Total Accesses = 11
 Total Hits = 6
Total Misses = 5
 Hit Rate = 6 / 11 =
54.6%
[Link], CSE 02-03-2026 26
Advantages
 Produces minimum number of page faults.
 Used as a benchmark for comparing other algorithms.
 Does not suffer from Belady’s anomaly.

Disadvantages
 Cannot be implemented in real systems.
 Requires knowledge of future memory references.

[Link], CSE 02-03-2026 27

 When a page fault occurs and memory is full:
 The system randomly selects any one page in memory and
evicts it.
 Unlike FIFO, it does not follow order.
 Unlike LRU or Optimal, it does not use past or future
information.
 Reference String 0 1 2 0 1 3 0 3 1 2 1
 Number of Frames = 3

[Link], CSE 02-03-2026 28

Example
 Reference string:
0, 1, 2, 0, 1, 3, 0, 3, 1, 2, 1
 Number of frames = 3
 Total Accesses = 11
 Total Hits = 5
 Total Misses = 6

[Link], CSE 02-03-2026 29

Why Results Change Every Time?
 Because eviction is random:
 Sometimes it removes a “good” page → more misses later
 Sometimes it removes a “bad” page → better performance
 That’s why:
 Some runs get 6 hits (same as Optimal)
 Some runs get only 2 or 3 hits

[Link], CSE 02-03-2026 30

 When a page fault occurs,
 replace the page that was least recently used (i.e., the page
that has not been used for the longest time).

 Simple rule: Evict the page with the oldest recent access.
 It is based on the principle of locality, which states that
recently used pages are likely to be used again.

[Link], CSE 02-03-2026 31

Example:
 Reference string:
0, 1, 2, 0, 1, 3, 0, 3, 1, 2, 1
 Number of frames = 3
 Total Accesses = 11
 Hits = 6
 Misses = 5
 LRU matches Optimal

[Link], CSE 02-03-2026 32

 When page 3 arrives:
 0 and 1 were used recently
 2 was least recently used
 So LRU evicts 2 (correct decision)
 When page 2 arrives later:
 0 was least recently used
 So LRU evicts 0
 In both cases, LRU makes the right prediction using history.
 LRU performs better than FIFO and Random and may
match Optimal performance.
[Link], CSE 02-03-2026 33
 When a page fault occurs:
 Replace the page that was used most recently.
 Opposite of LRU
 Assumes the most recently used page is less likely to be
used again soon

[Link], CSE 02-03-2026 34

Example
 Reference string: 0, 1, 2, 0, 1, 3, 0, 3, 1, 2, 1
 Number of frames = 3
 Total Accesses = 11 Total Hits = 5 Total Misses = 6
[Link], CSE 02-03-2026 35
Step 6 (Access 3)
 Before access: 0,1,2
 Most recently used page = 1
 So MRU evicts 1

Step 9 (Access 1)
 Before access: 0,2,3
 Most recently used page = 3
 So MRU evicts 3

[Link], CSE 02-03-2026 36

 Thrashing is a condition in which:
 Operating system spends most of its time swapping
(paging) pages in and out of memory instead of
executing processes.
 It occurs when:
 The total memory demand of running processes
 Exceeds available physical memory
 As described by Peter J. Denning.

[Link], CSE 02-03-2026 37

Causes of Thrashing
1. Excessive Multiprogramming
 When too many processes are loaded into memory at the
same time:
 Each process gets fewer frames
 Working sets cannot fit into memory
 Page faults increase rapidly
 This is the most common cause of thrashing.

[Link], CSE 02-03-2026 38

2. Insufficient Physical Memory
 If the total demand for memory is greater than available
RAM:
 Total working sets of processes > Physical memory
 The system continuously swaps pages in and out.

3. Poor Page Replacement Policy

 Inefficient policies (like FIFO in some cases)
 May remove frequently used pages
 Increase page faults
 Worsen memory pressure
[Link], CSE 02-03-2026 39
Methods to Control Thrashing
(a) Admission Control: Limit the number of processes in
memory so their working sets fit into physical memory.

(b) Working Set Model: Ensure each process gets enough

frames to hold its working set.

(c) Out-of-Memory Handling: Some versions of Linux use

an OOM (Out-of-Memory) Killer, which terminates memory-
intensive processes when memory is exhausted.

[Link], CSE 02-03-2026 40

[Link], CSE 02-03-2026 41