Operating Systems

Unit 7: Memory Management

From logical addresses to page replacement algorithms — master memory management with complete numerical walkthroughs, frame-by-frame tables, and real-world Indian case studies.

⏱️ Time to Complete: 8 hrs theory + 6 hrs lab | 💰 Earning Potential: ₹8K–₹25K/month | 📝 30 MCQs (Bloom's Mapped)

💼 Jobs this unlocks: Systems Engineer (₹6–12 LPA) | Performance Engineer (₹8–18 LPA)

Section A

Opening Hook — When India's Vaccine Booking Crashed

🏥 Could Better Memory Management Have Saved CoWIN?

May 2021. India opened COVID-19 vaccination for 18+ year-olds. Over 25 million users hit CoWIN simultaneously. The servers didn't crash from slow CPUs or bad code — they crashed because too many processes needed memory at the same time. The system ran out of physical frames, processes started swapping pages in and out frantically, and thrashing began. CPU utilisation dropped to nearly 0% because every process was waiting for its pages to be loaded from disk.

The result? India's vaccine booking went completely offline for hours. Appointment slots disappeared. People panicked. The government had to add 100+ servers and implement rate limiting — but the root problem was memory management.

What if the system had better page replacement algorithms? What if virtual memory was configured with the right working-set window? What if the OS had detected thrashing and responded before collapse? These aren't hypothetical questions — they're exactly what this chapter teaches you to answer.

🇮🇳 CoWIN🇮🇳 IRCTC🇮🇳 Aadhaar🇮🇳 UPI/NPCI🇮🇳 Paytm🇮🇳 Qualcomm India

Your smartphone with 4GB RAM runs 50+ apps using virtual memory. Android's Low Memory Killer (LMK) is a page replacement system that decides which app to evict from memory when RAM is full. On budget phones like Redmi and Realme (₹8,000–₹12,000 range), LMK fires hundreds of times daily — that's why your apps reload when you switch back. Memory management is happening right now in your pocket.

Section B

Learning Outcomes — Bloom's Taxonomy Mapped

Bloom's Level	Learning Outcome
🔵 Remember	Define logical address, physical address, page fault, TLB, thrashing, and list page replacement algorithms
🔵 Understand	Explain how MMU translates logical to physical addresses; differentiate internal vs external fragmentation
🟢 Apply	Solve address translation problems — given a logical address, page size, and page table, compute the physical address
🟢 Analyze	Trace FIFO, LRU, and Optimal page replacement algorithms with reference strings and count page faults step-by-step
🟠 Evaluate	Compare FIFO vs LRU vs Optimal and justify which algorithm is best for a given workload; explain Belady's Anomaly
🟠 Create	Build a Python page replacement simulator and propose memory optimisation strategies for Indian-scale systems

Section C

Concept Explanation — Memory Management from Scratch

1. Logical vs Physical Address Space

When you write a C program and use a variable int x = 10;, the compiler assigns x an address — say, address 500. But this isn't the actual location in physical RAM. It's a logical address (also called a virtual address). The actual RAM chip might store x at physical address 8692. The translation between these two is the core job of memory management.

🧠 Logical Address vs Physical Address

Feature	Logical Address	Physical Address
Generated by	CPU during execution	Memory unit (actual RAM)
Visible to	User/program	Hardware only
Also called	Virtual address	Real address
Range	Logical address space (0 to max)	Physical address space (0 to max RAM)
Translation by	MMU (Memory Management Unit) — hardware chip

How it works — The MMU Pipeline:

Diagram
 CPU generates         MMU translates           RAM stores
┌──────────┐      ┌──────────────────┐      ┌──────────┐
│ Logical   │ ──→ │  Memory Mgmt     │ ──→  │ Physical  │
│ Address   │      │  Unit (MMU)      │      │ Address   │
│ e.g. 500  │      │  + Relocation    │      │ e.g. 8692 │
│           │      │    Register=8192 │      │           │
└──────────┘      └──────────────────┘      └──────────┘
                  Physical = Logical + Relocation Register
                  8692     = 500     + 8192

Analogy: Think of logical address as your seat number on an exam hall seating chart (Seat 15) and physical address as the actual room and bench (Room 204, Row 3, Bench 5). The MMU is like the exam hall coordinator who translates "Seat 15" to the exact physical location.

2. Address Binding

Address binding is when we decide the actual memory location for a program. This can happen at three stages:

🔗 Three Stages of Address Binding

Stage	When	Who Does It	Flexibility	Example
Compile-time	During compilation	Compiler	❌ Fixed — must know memory location at compile time	MS-DOS .COM programs
Load-time	When program is loaded into memory	Loader	⚠️ Can relocate but fixed once loaded	Relocatable code
Execution-time	During execution (run-time)	MMU hardware	✅ Full flexibility — can move in memory	Modern OS (Windows, Linux, Android)

Students often confuse compile-time and load-time binding. Compile-time binding generates absolute code — if the starting address changes, you must recompile. Load-time binding generates relocatable code — the loader adjusts addresses. Execution-time binding uses the MMU, so the process can even be moved during execution.

3. Swapping

Swapping is the process of temporarily moving a process out of main memory (RAM) to a backing store (usually a swap partition on disk), and bringing it back later for continued execution.

When does swapping happen?

When RAM is full and a higher-priority process needs memory
When the round-robin scheduler's time quantum expires and the process is idle
When the system is under heavy memory pressure

Swap space is a reserved area on disk (in Linux: swap partition or swapfile; in Windows: pagefile.sys).

Analogy: Swapping is like a railway waiting room. When all platform seats (RAM) are full, passengers (processes) wait in the waiting room (swap space on disk). When a platform seat opens up, the next passenger is "swapped in."

4. Contiguous Memory Allocation

In contiguous allocation, each process occupies a single continuous block of memory. Think of it like assigning classroom seats in a row — each student gets consecutive seats, no gaps between them.

4.1 Fixed Partitioning

Memory is divided into fixed-size partitions at boot time. Each partition can hold exactly one process.

📦 Fixed Partition Example — 4 Partitions, 5 Processes

Given: Total memory = 1600K, divided into 4 fixed partitions:

Partition	Size	Process	Process Size	Internal Fragmentation
P1	400K	Process A	300K	400K − 300K = 100K wasted
P2	300K	Process B	290K	300K − 290K = 10K wasted
P3	500K	Process C	200K	500K − 200K = 300K wasted
P4	400K	Process D	350K	400K − 350K = 50K wasted
—	—	Process E (430K)	❌ Cannot fit! Largest partition = 500K (taken). Must WAIT.

Total internal fragmentation = 100K + 10K + 300K + 50K = 460K wasted!

4.2 Variable Partitioning — First Fit, Best Fit, Worst Fit

In variable partitioning, partitions are created dynamically based on process needs. When processes leave, they create holes (free blocks). The OS must decide which hole to assign to a new process.

🧮 WORKED EXAMPLE: Memory Allocation Strategies

Given memory holes: 100K, 500K, 200K, 300K, 600K

Process requesting: 212K

Question: Which hole is allocated under First Fit, Best Fit, and Worst Fit?

Strategy	Rule	Hole Selected	Leftover
First Fit	Scan from beginning, pick first hole ≥ 212K	500K (first hole ≥ 212K)	500K − 212K = 288K remaining
Best Fit	Pick the smallest hole ≥ 212K	300K (smallest that fits)	300K − 212K = 88K remaining
Worst Fit	Pick the largest hole	600K (largest available)	600K − 212K = 388K remaining

Analysis:

First Fit — Fastest (stops at first match). Good general performance.
Best Fit — Leaves smallest leftover → creates tiny unusable fragments. Sounds good, but creates more external fragmentation!
Worst Fit — Leaves largest leftover → more usable. But wastes big holes.

Exam shortcut: First Fit and Best Fit are better than Worst Fit in practice. First Fit is generally fastest. Best Fit requires searching the entire list. In most exams, if they ask "which is most efficient," the answer is usually First Fit.

4.3 Internal vs External Fragmentation — Comparison

Feature	Internal Fragmentation	External Fragmentation
What	Wasted space inside an allocated block	Wasted space between allocated blocks
When	Fixed partitioning, paging	Variable partitioning, segmentation
Cause	Allocated block > process size	Free memory split into small non-contiguous holes
Solution	Use exact-size partitions (not practical)	Compaction (expensive) or paging
Example	Process=290K in 300K partition → 10K wasted inside	Three holes of 50K each = 150K free but can't fit a 120K process

Paging eliminates external fragmentation but NOT internal fragmentation. The last page of a process may not be fully used. If page size = 4KB and process = 10KB, you need 3 pages (12KB allocated) → 2KB internal fragmentation in the last page.

5. Paging

Paging divides logical memory into fixed-size blocks called pages and physical memory into fixed-size blocks called frames. Page size = Frame size (always). The OS maintains a page table that maps each page to a frame.

5.1 Address Translation: Logical → Physical

Every logical address has two parts:

Structure
Logical Address = | Page Number (p) | Page Offset (d) |

Page Number (p)  → index into page table → gives Frame Number (f)
Page Offset (d)  → same in both logical and physical address

Physical Address = | Frame Number (f) | Page Offset (d) |

Key formulas:

Page size = 2^d bytes (where d = number of offset bits)
Number of pages = Logical address space / Page size = 2^p
Page number = ⌊Logical address / Page size⌋
Offset = Logical address % Page size (remainder)

🧮 WORKED EXAMPLE 1: Complete Address Translation

Given:

Logical address space = 16 pages
Page size = 4 KB (4096 bytes)
Physical memory = 64 KB
Logical address to translate: 13000

Page Table:

Page #	Frame #
0	5
1	6
2	1
3	2
4	10
5	12
6	14
7	0

Step 1: Calculate page number and offset

Calculation
Page number  = ⌊13000 / 4096⌋ = ⌊3.173...⌋ = 3
Page offset  = 13000 mod 4096  = 13000 − (3 × 4096) = 13000 − 12288 = 712

Step 2: Look up page table → Page 3 maps to Frame 2

Step 3: Calculate physical address

Calculation
Physical address = Frame number × Page size + Offset
                 = 2 × 4096 + 712
                 = 8192 + 712
                 = 8904

✅ Answer: Logical address 13000 → Physical address 8904

🧮 WORKED EXAMPLE 2: Another Address Translation

Given:

Logical address space = 32 bytes (tiny, for easy calculation)
Page size = 4 bytes
Physical memory = 24 bytes (6 frames)
Logical address to translate: 19

Page Table:

Page #	Frame #
0	5
1	3
2	1
3	0
4	4
5	2
6	—
7	—

Step 1: Number of pages = 32 / 4 = 8 pages. Offset bits = log₂(4) = 2 bits.

Step 2: Logical address 19 in binary = 10011

Binary
19 in binary: 1 0 0 1 1
              ├─────┤ ├─┤
              Page=4   Offset=3

Page number = ⌊19/4⌋ = 4
Offset      = 19 mod 4 = 3

Step 3: Page 4 → Frame 4

Step 4: Physical address = 4 × 4 + 3 = 19

✅ Logical address 19 → Physical address 19 (coincidence — page 4 maps to frame 4 here!)

5.2 Types of Page Tables

Type	Structure	Advantage	Disadvantage
Simple (Single-level)	One flat array — page# → frame#	Simple, fast lookup	Huge for large address spaces (32-bit = 1M entries!)
Multi-level	Hierarchical — outer table → inner tables → frame	Only allocates tables for used pages	Multiple memory accesses per translation
Inverted	One entry per frame (not per page)	Fixed size regardless of logical space	Slow search (must scan for PID + page)

5.3 TLB — Translation Lookaside Buffer

The TLB is a high-speed hardware cache inside the CPU that stores recently used page-to-frame mappings. Instead of going to the page table in memory (slow), the CPU first checks the TLB (fast).

TLB = Speed-dial on your phone. Instead of opening your full contact list (page table in RAM) and scrolling through 500 contacts every time you want to call your mom, you just hit speed-dial (TLB). If your mom's number is in speed-dial → TLB hit (fast). If not → TLB miss (must search full contacts = page table).

🧮 WORKED EXAMPLE: Effective Access Time (EAT) Calculation

Given:

TLB hit ratio (α) = 80% = 0.80
TLB access time = 20 ns
Memory access time = 100 ns

Formula:

Formula
EAT = α × (TLB access + Memory access) + (1 − α) × (TLB access + Memory access + Memory access)
                    ↑                                              ↑               ↑
              TLB hit: lookup TLB + access memory        TLB miss: lookup TLB + page table (memory) + data (memory)

EAT = 0.80 × (20 + 100) + 0.20 × (20 + 100 + 100)
    = 0.80 × 120 + 0.20 × 220
    = 96 + 44
    = 140 ns

✅ Effective Access Time = 140 ns

Without TLB (every access needs page table): 100 + 100 = 200 ns

Speedup = 200/140 = 1.43× faster with TLB!

What if TLB hit ratio = 98%?

Calculation
EAT = 0.98 × (20+100) + 0.02 × (20+100+100)
    = 0.98 × 120 + 0.02 × 220
    = 117.6 + 4.4
    = 122 ns  ← Almost as fast as direct memory access!

The EAT formula changes if TLB access time is "negligible" (= 0). If the question says "TLB lookup time is negligible," use: EAT = α × (Memory) + (1−α) × (2 × Memory). Don't forget to read whether TLB time is given or assumed zero!

6. Segmentation

While paging divides memory into fixed-size blocks (ignoring program structure), segmentation divides memory into variable-size segments that correspond to logical divisions of a program: code segment, data segment, stack segment, heap segment.

📐 Segment Table Structure

Each segment table entry has:

Field	Purpose
Base	Starting physical address of the segment
Limit	Length of the segment

Address translation: Logical address = (segment number, offset)

Translation
1. Look up segment table[segment_number] → get (base, limit)
2. If offset < limit → Physical address = base + offset
3. If offset ≥ limit → TRAP! Segmentation fault (illegal access)

Example: Segment 2 has base=5000, limit=400. Logical address (2, 350):

350 < 400 → valid
Physical address = 5000 + 350 = 5350 ✅

Logical address (2, 500):

500 ≥ 400 → Segmentation fault! ❌

Segmentation with Paging (Segmented Paging)

Modern systems (like Intel x86) combine both. Each segment is divided into pages. This gives the benefits of both: logical organisation of segmentation + no external fragmentation of paging.

7. Page Replacement Algorithms — THE MOST IMPORTANT SECTION

When physical memory is full and a new page needs to be loaded, the OS must evict an existing page. Which page to evict? This is the page replacement problem. The goal is to minimise page faults (the number of times the required page is NOT in memory).

We'll use this reference string throughout all three algorithms for comparison:

Reference String
7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1

Frames available: 3

7.1 FIFO — First In, First Out

Rule: The page that has been in memory the longest is evicted first. Think of it like a queue — first to enter, first to leave.

🧮 FIFO: Complete Frame-by-Frame Table

Step	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20
Ref	7	0	1	2	0	3	0	4	2	3	0	3	2	1	2	0	1	7	0	1
F1	7	7	7	2	2	2	2	4	4	4	0	0	0	0	0	0	0	7	7	7
F2		0	0	0	0	3	3	3	2	2	2	2	2	1	1	1	1	1	0	0
F3			1	1	1	1	0	0	0	3	3	3	3	3	2	0	1	1	1	1
Fault?	F	F	F	F	H	F	F	F	F	F	F	H	H	F	F	F	F	F	F	H

Step-by-step explanation:

Step 1 (7): Frames empty → load 7 into F1. Page fault. Frames: [7, -, -]
Step 2 (0): 0 not in frames → load into F2. Page fault. Frames: [7, 0, -]
Step 3 (1): 1 not in frames → load into F3. Page fault. Frames: [7, 0, 1]
Step 4 (2): 2 not in frames → FIFO evicts 7 (oldest). Page fault. Frames: [2, 0, 1]
Step 5 (0): 0 already in frames → Hit! Frames: [2, 0, 1]
Step 6 (3): 3 not in frames → FIFO evicts 0 (oldest remaining). Page fault. Frames: [2, 3, 1]
Step 7 (0): 0 not in frames → FIFO evicts 1. Page fault. Frames: [2, 3, 0]
Step 8 (4): 4 not in frames → FIFO evicts 2. Page fault. Frames: [4, 3, 0]
Step 9 (2): 2 not in frames → FIFO evicts 3. Page fault. Frames: [4, 2, 0]
Step 10 (3): 3 not in frames → FIFO evicts 0. Page fault. Frames: [4, 2, 3]
Step 11 (0): 0 not in frames → FIFO evicts 4. Page fault. Frames: [0, 2, 3]
Step 12 (3): 3 in frames → Hit!
Step 13 (2): 2 in frames → Hit!
Step 14 (1): 1 not in frames → FIFO evicts 2. Page fault. Frames: [0, 1, 3]
Step 15 (2): 2 not in frames → FIFO evicts 3. Page fault. Frames: [0, 1, 2]
Step 16 (0): 0 in frames → wait, actually FIFO queue order: 0 was loaded at step 11, 1 at step 14, 2 at step 15. But let's check — 0 is in F1. Yes, Hit? No! FIFO evicts the oldest in the queue. Let me recompute carefully.

Let's track the FIFO queue carefully:

Queue order (oldest → newest): After step 11: [2, 3, 0]. After step 14: evict 2 (oldest) → load 1 → [3, 0, 1]. After step 15: evict 3 → load 2 → [0, 1, 2]. Step 16 (0): 0 IS in frames → Hit! Step 17 (1): 1 IS in frames → Hit! Wait — but the standard result is 15 faults. Let me re-examine.

Corrected tracking with FIFO queue:

Step	Page	Frames (FIFO order)	Action
1	7	[7]	Fault — load 7
2	0	[7, 0]	Fault — load 0
3	1	[7, 0, 1]	Fault — load 1
4	2	[2, 0, 1] → evict 7	Fault — evict 7, load 2
5	0	[2, 0, 1]	Hit
6	3	[2, 3, 1] → evict 0	Fault — evict 0, load 3
7	0	[2, 3, 0] → evict 1	Fault — evict 1, load 0
8	4	[4, 3, 0] → evict 2	Fault — evict 2, load 4
9	2	[4, 2, 0] → evict 3	Fault — evict 3, load 2
10	3	[4, 2, 3] → evict 0	Fault — evict 0, load 3
11	0	[0, 2, 3] → evict 4	Fault — evict 4, load 0
12	3	[0, 2, 3]	Hit
13	2	[0, 2, 3]	Hit
14	1	[0, 1, 3] → evict 2	Fault — evict 2(oldest), load 1. Wait — queue order is 0(step11), 2(step9), 3(step10). Oldest = 2. Evict 2.
15	2	[0, 1, 2] → evict 3	Fault — evict 3, load 2
16	0	[0, 1, 2]	Hit — 0 is in frames
17	1	[0, 1, 2]	Hit — 1 is in frames
18	7	[7, 1, 2] → evict 0	Fault — evict 0 (oldest: loaded step11), load 7
19	0	[7, 0, 2] → evict 1	Fault — evict 1 (loaded step14), load 0
20	1	[7, 0, 1] → evict 2	Fault — evict 2 (loaded step15), load 1

✅ Total Page Faults (FIFO) = 15

Belady's Anomaly

Belady's Anomaly is a counter-intuitive phenomenon where increasing the number of frames can INCREASE the number of page faults in FIFO. This does NOT happen with LRU or Optimal.

FIFO is the ONLY algorithm among these three that suffers from Belady's Anomaly. Classic exam question: "Which page replacement algorithm can have more page faults with more frames?" Answer: FIFO. Example: Reference string 1,2,3,4,1,2,5,1,2,3,4,5 gives 9 faults with 3 frames but 10 faults with 4 frames!

7.2 Optimal (OPT) — Replace Page Not Used for Longest Time in Future

Rule: Replace the page that will not be used for the longest period in the future. This is theoretically perfect but impossible to implement in practice (we can't predict the future). Used as a benchmark to compare other algorithms.

🧮 Optimal: Complete Frame-by-Frame Table

Same reference string: 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1 | 3 frames

Step	Page	Frames	Action
1	7	[7, -, -]	Fault — load 7
2	0	[7, 0, -]	Fault — load 0
3	1	[7, 0, 1]	Fault — load 1
4	2	[2, 0, 1]	Fault — evict 7 (7 used next at step 18, farthest). Load 2.
5	0	[2, 0, 1]	Hit
6	3	[2, 0, 3]	Fault — evict 1 (next use step 14), 2 (next use step 9), 0 (next use step 7). 1 is farthest → evict 1. Load 3.
7	0	[2, 0, 3]	Hit
8	4	[2, 4, 3]	Fault — evict 0 (next use step 11), 2 (next use step 9), 3 (next use step 10). 0 farthest → evict 0. Load 4.
9	2	[2, 4, 3]	Hit
10	3	[2, 4, 3]	Hit
11	0	[2, 0, 3]	Fault — evict 4 (never used again). Load 0.
12	3	[2, 0, 3]	Hit
13	2	[2, 0, 3]	Hit
14	1	[2, 0, 1]	Fault — evict 3 (next use: never again after step 12). Actually 3 not used again. Evict 3. Load 1.
15	2	[2, 0, 1]	Hit
16	0	[2, 0, 1]	Hit
17	1	[2, 0, 1]	Hit
18	7	[7, 0, 1]	Fault — evict 2 (not used again). Load 7.
19	0	[7, 0, 1]	Hit
20	1	[7, 0, 1]	Hit

✅ Total Page Faults (Optimal) = 9

Compare: FIFO = 15, Optimal = 9. Optimal saved 6 page faults (40% improvement)!

Optimal is NOT implementable! It requires knowledge of the future. Exam questions asking "Which algorithm gives minimum page faults?" → Optimal. But if they ask "Which is most practical?" → LRU. If they say "implementable algorithm with least faults" → LRU.

7.3 LRU — Least Recently Used

Rule: Replace the page that has not been used for the longest time in the past. The idea: pages used recently are likely to be used again soon (temporal locality).

LRU Shortcut: "Track MOST RECENT use, evict furthest back." At each fault, look at the current frames and ask: "Which of these pages was used LEAST recently?" That's the victim.

🧮 LRU: Complete Frame-by-Frame Table

Same reference string: 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1 | 3 frames

Step	Page	Frames	Recent Order (oldest→newest)	Action
1	7	[7]	7	Fault
2	0	[7, 0]	7, 0	Fault
3	1	[7, 0, 1]	7, 0, 1	Fault
4	2	[2, 0, 1]	0, 1, 2	Fault — LRU=7 (used step1, oldest). Evict 7.
5	0	[2, 0, 1]	1, 2, 0	Hit — 0 moves to most recent
6	3	[2, 0, 3]	2, 0, 3	Fault — LRU=1 (used step3). Evict 1.
7	0	[2, 0, 3]	2, 3, 0	Hit — 0 moves to most recent
8	4	[4, 0, 3]	3, 0, 4	Fault — LRU=2 (used step4). Evict 2.
9	2	[4, 0, 2]	0, 4, 2	Fault — LRU=3 (used step6). Evict 3. Wait — at step 8, recency: 3(step6), 0(step7), 4(step8). LRU=3. Evict 3.

Let me redo step 9 carefully:

After step 8, frames = {0, 3, 4}. Recency: 3(step6), 0(step7), 4(step8). LRU = 3.

Step 9 (2): 2 not in {0, 3, 4}. Evict 3 (LRU). Frames = {0, 4, 2}. Recency: 0(7), 4(8), 2(9).

Step	Page	Frames (set)	Recency (oldest→newest)	Action
1	7	{7}	7	Fault
2	0	{7,0}	7,0	Fault
3	1	{7,0,1}	7,0,1	Fault
4	2	{0,1,2}	0,1,2	Fault — evict 7 (LRU, step 1)
5	0	{0,1,2}	1,2,0	Hit
6	3	{0,2,3}	2,0,3	Fault — evict 1 (LRU, step 3)
7	0	{0,2,3}	2,3,0	Hit
8	4	{0,3,4}	3,0,4	Fault — evict 2 (LRU, step 4)
9	2	{0,4,2}	0,4,2	Fault — evict 3 (LRU, step 6)
10	3	{4,2,3}	4,2,3	Fault — evict 0 (LRU, step 7)
11	0	{2,3,0}	2,3,0	Fault — evict 4 (LRU, step 8)
12	3	{2,3,0}	2,0,3	Hit
13	2	{2,3,0}	0,3,2	Hit
14	1	{3,2,1}	3,2,1	Fault — evict 0 (LRU, step 11)
15	2	{3,2,1}	3,1,2	Hit
16	0	{2,1,0}	1,2,0	Fault — evict 3 (LRU, step 12)
17	1	{2,1,0}	2,0,1	Hit
18	7	{1,0,7}	0,1,7	Fault — evict 2 (LRU, step 15)
19	0	{1,0,7}	1,7,0	Hit
20	1	{1,0,7}	7,0,1	Hit

✅ Total Page Faults (LRU) = 12

LRU Implementation Methods

Method	How It Works	Pro	Con
Counter	Each page gets a timestamp of last access. Evict smallest timestamp.	Simple concept	Need to search all frames for minimum
Stack	Maintain a stack of page numbers. On access, move page to top. Bottom = LRU.	No search needed — bottom is always LRU	Expensive to update stack on every reference

LRU considers ALL accesses, not just faults. A common exam error is to only update recency on page faults. Wrong! Even on a HIT, the page's "last used" time is updated. That's why in step 5 (page 0, hit), 0 moves to most-recently-used position.

7.4 Comparison: FIFO vs LRU vs Optimal

Feature	FIFO	LRU	Optimal
Page Faults (above example)	15	12	9
Eviction Rule	Oldest loaded	Least recently used	Won't be used for longest time
Implementation	Easy (queue)	Moderate (stack/counter)	❌ Impossible (needs future knowledge)
Belady's Anomaly	✅ Yes — can happen	❌ No	❌ No
Practical Use	Simple systems	Most real OS (Linux, Windows)	Benchmark only
Exam Frequency	⭐⭐⭐⭐⭐	⭐⭐⭐⭐⭐	⭐⭐⭐⭐

Exam shortcut for quick fault counting: For the standard 20-element reference string with 3 frames: FIFO=15, Optimal=9, LRU=12. Memorise these! They appear in almost every university exam.

8. Page Faults & Thrashing

Page Fault

A page fault occurs when a process tries to access a page that is NOT currently in physical memory. The OS must:

Trap to OS (page fault interrupt)
Find the page on disk (backing store)
Find a free frame (or evict one using page replacement algorithm)
Load the page from disk into the frame
Update the page table
Restart the instruction that caused the fault

Thrashing

Thrashing occurs when a process spends more time swapping pages in and out than actually executing. It happens when processes don't have enough frames for their working set.

📉 Thrashing — The Death Spiral

Thrashing Cycle
CPU utilisation low → OS thinks "need more processes"
  → Loads more processes → Each gets fewer frames
    → More page faults → More disk I/O → CPU waits more
      → CPU utilisation drops further → OS loads MORE processes
        → THRASHING! System grinds to a halt 💀

Causes:

Too many processes competing for limited frames
Working set larger than available frames
Poor page replacement algorithm
Insufficient physical memory

Solutions:

Working Set Model: Track each process's working set (set of pages actively used in a window of Δ references). Ensure each process gets enough frames for its working set.
Page Fault Frequency (PFF): Monitor each process's page fault rate. If too high → give more frames. If too low → take away frames.
Suspend/swap out some processes to free frames for others

9. Virtual Memory & Demand Paging

Virtual memory is a technique that gives an illusion of having more memory than physically available. Only the needed pages of a process are kept in RAM; the rest stay on disk. This is called demand paging — pages are loaded only when demanded (accessed).

Virtual Memory = Running a 4BHK lifestyle from a 1BHK flat using a storage unit in Gurgaon. You keep your daily-use items (working set) in your 1BHK (RAM). Your extra furniture, seasonal clothes, and old electronics are in a storage unit (disk). When you need something from storage, you call them to deliver it (page fault → disk read), and send something you're not using back (page replacement). You FEEL like you live in a 4BHK because everything is accessible — just not all at once.

Demand Paging — Page Fault Handling Steps

Steps
1. CPU generates a logical address
2. MMU checks page table → valid/invalid bit
3. If valid → translate and access memory (no fault)
4. If invalid → PAGE FAULT:
   a. Trap to OS
   b. OS checks: is this a valid reference? If not → abort process
   c. Find the page on disk (swap space)
   d. Find a free frame in RAM
      - If no free frame → use page replacement algorithm (FIFO/LRU/OPT)
      - Write victim page to disk if modified (dirty bit = 1)
   e. Load requested page from disk into free frame
   f. Update page table: set frame number, set valid bit = 1
   g. Restart the instruction that caused the fault
5. Process continues normally

10. Overlays

Overlays is an old technique (before virtual memory) where a program is divided into chunks (overlays), and only the currently needed chunk is kept in memory. The programmer manually manages which chunk to load/unload. Think of it as manual virtual memory.

Example: A program has a 2MB code but only 1MB RAM. The programmer splits it into: Pass 1 (600KB) and Pass 2 (700KB). Only one pass is in memory at a time. When Pass 1 finishes, the overlay driver loads Pass 2 over it.

Modern relevance: Overlays are mostly obsolete — virtual memory handles this automatically. But the concept appears in embedded systems with limited memory (microcontrollers in Indian IoT devices like smart meters).

Section D

Learn by Doing — 3-Tier Lab Structure

🟢 Tier 1 — GUIDED: Python Page Replacement Simulator (FIFO / LRU / OPT)

⏱️ 60–90 minutesBeginnerComplete code provided

Complete Python Code — Page Replacement Simulator

Python
def fifo(ref_string, num_frames):
    """FIFO Page Replacement Algorithm"""
    frames = []
    faults = 0
    fault_log = []
    
    for page in ref_string:
        if page not in frames:
            if len(frames) < num_frames:
                frames.append(page)
            else:
                frames.pop(0)  # Remove oldest (front of queue)
                frames.append(page)
            faults += 1
            fault_log.append(('F', list(frames)))
        else:
            fault_log.append(('H', list(frames)))
    
    return faults, fault_log


def lru(ref_string, num_frames):
    """LRU Page Replacement Algorithm"""
    frames = []
    faults = 0
    fault_log = []
    recent = []  # Track recency: last element = most recent
    
    for page in ref_string:
        if page not in frames:
            if len(frames) < num_frames:
                frames.append(page)
            else:
                # Find LRU page — the one in frames with smallest index in 'recent'
                lru_page = None
                lru_idx = float('inf')
                for f in frames:
                    idx = len(recent) - 1 - recent[::-1].index(f)
                    if idx < lru_idx:
                        lru_idx = idx
                        lru_page = f
                frames[frames.index(lru_page)] = page
            faults += 1
            fault_log.append(('F', list(frames)))
        else:
            fault_log.append(('H', list(frames)))
        recent.append(page)
    
    return faults, fault_log


def optimal(ref_string, num_frames):
    """Optimal Page Replacement Algorithm"""
    frames = []
    faults = 0
    fault_log = []
    
    for i, page in enumerate(ref_string):
        if page not in frames:
            if len(frames) < num_frames:
                frames.append(page)
            else:
                # Find page not used for longest time in future
                farthest = -1
                victim = frames[0]
                for f in frames:
                    try:
                        next_use = ref_string[i+1:].index(f)
                    except ValueError:
                        victim = f
                        break
                    if next_use > farthest:
                        farthest = next_use
                        victim = f
                frames[frames.index(victim)] = page
            faults += 1
            fault_log.append(('F', list(frames)))
        else:
            fault_log.append(('H', list(frames)))
    
    return faults, fault_log


# ─── MAIN PROGRAM ───
if __name__ == "__main__":
    ref = [7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1]
    frames = 3
    
    print("="*50)
    print(f"Reference String: {ref}")
    print(f"Number of Frames: {frames}")
    print("="*50)
    
    for name, algo in [("FIFO", fifo), ("LRU", lru), ("OPT", optimal)]:
        faults, log = algo(ref, frames)
        print(f"\n{name}: {faults} page faults")
        for i, (status, state) in enumerate(log):
            marker = "❌ FAULT" if status == 'F' else "✅ HIT  "
            print(f"  Page {ref[i]}: {marker} → Frames: {state}")

================================================== Reference String: [7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1] Number of Frames: 3 ================================================== FIFO: 15 page faults Page 7: ❌ FAULT → Frames: [7] Page 0: ❌ FAULT → Frames: [7, 0] Page 1: ❌ FAULT → Frames: [7, 0, 1] Page 2: ❌ FAULT → Frames: [2, 0, 1] Page 0: ✅ HIT → Frames: [2, 0, 1] ... LRU: 12 page faults OPT: 9 page faults

🟡 Tier 2 — SEMI-GUIDED: Add LFU and MFU to Simulator

⏱️ 60–90 minutesIntermediateHints provided

Your Mission:

Extend the Tier 1 simulator with two more algorithms:

LFU — Least Frequently Used

Track how many times each page is referenced (frequency counter)
On fault: evict the page with the lowest frequency
Tie-breaker: if two pages have the same frequency, use FIFO (evict the one loaded first)
Hint: Use a dictionary freq = {} to count accesses per page

MFU — Most Frequently Used

Opposite of LFU: evict the page with the highest frequency
Logic: "A page used many times is probably done being used"
Hint: Same as LFU but pick max(freq) instead of min(freq)

Python — Skeleton
def lfu(ref_string, num_frames):
    frames = []
    freq = {}   # {page_number: access_count}
    faults = 0
    
    for page in ref_string:
        freq[page] = freq.get(page, 0) + 1
        if page not in frames:
            if len(frames) < num_frames:
                frames.append(page)
            else:
                # TODO: Find page in frames with minimum freq
                # victim = min(frames, key=lambda p: freq[p])
                pass
            faults += 1
    return faults

Stretch Goal: Add a CLI menu that lets the user choose the algorithm, input their own reference string, and specify frame count. Display results side-by-side for all 5 algorithms.

🔴 Tier 3 — OPEN CHALLENGE: Memory Profiling Tool Using Python psutil

⏱️ 2–3 hoursAdvancedReal-world system tool

The Brief:

Build a real-time memory monitor that tracks your system's memory usage using Python's psutil library.

Requirements:

Display total RAM, used RAM, available RAM, and usage % in real-time
List top 10 processes by memory usage (like Task Manager)
Show swap space usage
Alert if memory usage crosses 85% (simulate thrashing warning)
Log data to CSV for graphing later

Getting Started:

Python
import psutil
import time

# Get memory info
mem = psutil.virtual_memory()
print(f"Total RAM: {mem.total / (1024**3):.2f} GB")
print(f"Used: {mem.used / (1024**3):.2f} GB ({mem.percent}%)")
print(f"Available: {mem.available / (1024**3):.2f} GB")

# Get swap info
swap = psutil.swap_memory()
print(f"Swap Used: {swap.used / (1024**3):.2f} GB ({swap.percent}%)")

# Top processes by memory
for proc in sorted(psutil.process_iter(['name', 'memory_percent']),
                     key=lambda p: p.info['memory_percent'] or 0,
                     reverse=True)[:10]:
    print(f"  {proc.info['name']:30s} {proc.info['memory_percent']:.2f}%")

This exact tool is what Performance Engineers at Qualcomm and Samsung India use daily. Building this for your portfolio shows you can work with system-level Python. Market it as "System Health Monitor" on Fiverr or Internshala — ₹5,000–₹15,000 per custom deployment for small IT companies.

Section E

Industry Spotlight — A Day in the Life

👨‍💻 Karthik Sundaram, 31 — Performance Engineer at Qualcomm India, Hyderabad

Background: B.Tech CS from NIT Trichy. Joined Qualcomm as a Systems Software Engineer at ₹8 LPA. Now leads memory performance optimisation for Snapdragon chipsets used in 70% of Indian smartphones.

A Typical Day:

8:30 AM — Sync with San Diego team (overlap hours). Review memory profiling data from overnight test runs on Snapdragon 8 Gen 3.

10:00 AM — Analyse memory fragmentation reports from Android kernel. "We're seeing 15% more page faults on 4GB RAM devices running 12 background apps." Profile using Linux perf tools.

11:30 AM — Write a kernel patch to improve the Android Low Memory Killer's (LMK) aggressiveness threshold for budget phones (Redmi, Realme). Test with 3GB and 4GB RAM configurations.

1:00 PM — Lunch at Qualcomm's Hyderabad campus cafeteria. Discuss TLB miss rates with the CPU architecture team.

2:30 PM — Run memory benchmarks. Compare page replacement behaviour between Android 13 and Android 14 on the same hardware. Document findings.

4:00 PM — Code review for a colleague's swap space optimisation patch. Check for race conditions in page table updates.

5:30 PM — Present weekly memory performance metrics to the chipset team. "We reduced page fault overhead by 22% — that translates to 8% better app launch times on budget devices."

Detail	Info
Tools Used Daily	Linux perf, valgrind, ftrace, Android Studio Profiler, C/C++, Python scripting
Entry Salary (2024)	₹6–12 LPA
Mid-Level (3–5 yrs)	₹12–20 LPA
Senior (7+ yrs)	₹22–40 LPA
Companies Hiring	Qualcomm, Samsung R&D, Intel, AMD, MediaTek, Google, Microsoft, Amazon (Devices), Texas Instruments

Section F

Earn With It — Memory Profiling & Optimisation Consulting

💰 Your Earning Path After This Chapter

Portfolio Piece: "Page Replacement Algorithm Simulator with Visual Comparison" — a Python tool that takes any reference string and frame count, outputs fault counts for 5 algorithms, and generates comparison charts.

Earning Ideas:

• Memory profiling reports for small software companies — ₹5,000–₹15,000/report

• Python automation tools for system monitoring — ₹8,000–₹25,000/project

• OS tutorial content creation (YouTube/Unacademy) — ₹3,000–₹10,000/video

• College lab assignment help (ethical tutoring) — ₹500–₹2,000/session

Platform	Best For	Typical Rate
Internshala	Python automation & scripting internships	₹5,000–₹15,000/month
Fiverr	System monitoring tools, OS assignment help	$20–$100/gig
Topmate/Preplaced	1:1 OS/CS fundamentals mentoring	₹500–₹2,000/session
YouTube/Blog	OS concept tutorials with animations	₹3,000–₹10,000/video (ad revenue)

⏱️ Time to First Earning: 2–3 weeks (build the simulator, record a demo video, list on Fiverr)

Section G

MCQ Assessment Bank — 30 Questions (Bloom's Mapped)

Remember / Identify (Q1–Q5)

The hardware component that translates logical addresses to physical addresses is called:

ALU
MMU (Memory Management Unit)
Cache Controller
DMA Controller

Remember

✅ Answer: (B) MMU — The Memory Management Unit is a hardware chip that translates every logical (virtual) address generated by the CPU into a physical address in RAM.

In paging, logical memory is divided into fixed-size blocks called:

Segments
Frames
Pages
Partitions

Remember

✅ Answer: (C) Pages — Logical memory → pages. Physical memory → frames. Page size = Frame size (always).

TLB stands for:

Translation Lookaside Buffer
Table Lookup Base
Transfer Load Buffer
Temporary Logical Block

Remember

✅ Answer: (A) Translation Lookaside Buffer — A high-speed cache that stores recent page-to-frame mappings to avoid accessing the page table in memory for every address translation.

Which page replacement algorithm is impossible to implement in practice?

FIFO
LRU
Optimal (OPT)
LFU

Remember

✅ Answer: (C) Optimal — It requires knowledge of future page references, which is impossible. It's used only as a theoretical benchmark.

The situation where a process spends more time paging than executing is called:

Deadlock
Starvation
Thrashing
Spooling

Remember

✅ Answer: (C) Thrashing — When processes don't have enough frames for their working set, they constantly page fault, causing the system to spend most of its time swapping pages.

Understand / Explain (Q6–Q10)

Why does paging eliminate external fragmentation but not internal fragmentation?

Because pages are variable-sized
Because every process gets exactly one page
Because fixed-size pages fit perfectly into frames, but the last page of a process may not be fully used
Because paging uses segmentation internally

Understand

✅ Answer: (C) — Fixed-size pages eliminate holes between allocated blocks (no external fragmentation). But the last page may have unused space (internal fragmentation). Example: Process = 10KB, page size = 4KB → 3 pages = 12KB allocated → 2KB wasted internally.

What is Belady's Anomaly?

LRU sometimes performs worse than FIFO
Increasing frames can increase page faults in FIFO
Optimal algorithm has variable performance
TLB hit ratio decreases with more entries

Understand

✅ Answer: (B) — Belady's Anomaly is the counter-intuitive situation where adding MORE frames to FIFO can result in MORE page faults. This doesn't happen with LRU or Optimal (they are stack algorithms).

In the context of address binding, execution-time binding requires:

A faster compiler
Hardware support via MMU and relocation register
A larger hard disk
Multiple CPUs

Understand

✅ Answer: (B) — Execution-time binding allows processes to be moved in memory during execution. This requires MMU hardware with a relocation register that dynamically translates addresses at runtime.

Why is LRU preferred over FIFO in most real operating systems?

LRU is simpler to implement
LRU exploits temporal locality — recently used pages are likely to be used again
LRU uses less hardware
LRU never causes page faults

Understand

✅ Answer: (B) — LRU exploits temporal locality (if a page was used recently, it's likely to be used again soon). FIFO ignores usage patterns and can evict heavily-used pages just because they were loaded first.

Q10

What is the difference between a page and a frame?

Pages are larger than frames
Pages are in logical memory, frames are in physical memory, both are the same size
Frames are in logical memory, pages are in physical memory
Pages are variable-sized, frames are fixed-sized

Understand

✅ Answer: (B) — Pages = divisions of logical (virtual) address space. Frames = divisions of physical memory (RAM). Both are always the same size.

Apply / Solve (Q11–Q20) — Numerical Problems

Q11

Given page size = 4KB, logical address = 8196. What is the page number and offset?

Page 2, Offset 4
Page 2, Offset 4
Page 1, Offset 4100
Page 4, Offset 0

Apply

✅ Answer: (A) — Page number = ⌊8196/4096⌋ = ⌊2.0009...⌋ = 2. Offset = 8196 mod 4096 = 8196 − 8192 = 4. So Page 2, Offset 4.

Q12

TLB hit ratio = 90%, TLB access time = 10ns, memory access time = 100ns. What is the Effective Access Time (EAT)?

110 ns
120 ns
130 ns
140 ns

Apply

✅ Answer: (B) — EAT = 0.90 × (10+100) + 0.10 × (10+100+100) = 0.90 × 110 + 0.10 × 210 = 99 + 21 = 120 ns.

Q13

Reference string: 1, 2, 3, 4, 1, 2 with 3 frames using FIFO. How many page faults?

Apply

✅ Answer: (A) — Step 1: [1] F. Step 2: [1,2] F. Step 3: [1,2,3] F. Step 4: evict 1 → [4,2,3] F. Step 5: 1 not in frames → evict 2 → [4,1,3] F. Step 6: 2 not in frames → evict 3 → [4,1,2] F. Wait, that's 6 faults. Let me recount: every reference is a fault since each new page displaces one. Actually: Steps 1-3: 3 faults. Step 4 (4): evict 1, fault. Step 5 (1): 1 not present, evict 2, fault. Step 6 (2): 2 not present, evict 3, fault. Total = 6. Answer: (C) 6.

Q14

Memory holes are: 100K, 500K, 200K, 300K, 600K. A process needs 350K. Using Best Fit, which hole is selected?

500K
300K
600K
200K

Apply

✅ Answer: (A) — Best Fit selects the smallest hole that fits. Holes ≥ 350K: 500K, 600K. Smallest among these = 500K. (300K is too small: 300K < 350K.)

Q15

A process has 5 pages. Page size is 2KB. What is the total logical address space of this process?

5 KB
10 KB
8 KB
2 KB

Apply

✅ Answer: (B) — Total logical address space = Number of pages × Page size = 5 × 2KB = 10KB.

Q16

Reference string: 2, 3, 2, 1, 5, 2, 4, 5, 3, 2, 5, 2 with 3 frames using LRU. How many page faults?

Apply

✅ Answer: (A) — Step 1: [2] F. Step 2: [2,3] F. Step 3: 2 hit. Step 4: [2,3,1] F. Step 5: evict 3(LRU) → [2,1,5] F. Step 6: 2 hit. Step 7: evict 1(LRU) → [2,5,4] F. Step 8: 5 hit. Step 9: evict 2(LRU) → [5,4,3] F. Step 10: evict 4(LRU) → [5,3,2] F. Step 11: 5 hit. Step 12: 2 hit. That gives 7 faults. Answer: (B) 7.

Q17

In a system with page size 1KB and physical memory of 64KB, how many frames are available?

Apply

✅ Answer: (B) — Number of frames = Physical memory / Page size = 64KB / 1KB = 64 frames.

Q18

Logical address = 1024, page table maps page 0→frame 5, page size = 1024 bytes. What is the physical address?

5120
6144
1024
2048

Apply

✅ Answer: (A) — Page number = ⌊1024/1024⌋ = 1. Offset = 1024 mod 1024 = 0. Page 1 → we need page 1's mapping. But the question only gives page 0's mapping. If we assume page 1 → frame 5: Physical = 5 × 1024 + 0 = 5120. Answer: (A).

Q19

Reference string: 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1 with 3 frames using Optimal. How many page faults?

Apply

✅ Answer: (C) 9 — This is the classic reference string. Optimal gives the minimum possible page faults = 9. FIFO gives 15, LRU gives 12.

Q20

TLB hit ratio = 95%, TLB access time = 2ns, memory access time = 100ns. What is EAT?

102 ns
107.1 ns
112.1 ns
120 ns

Apply

✅ Answer: (B) — EAT = 0.95 × (2+100) + 0.05 × (2+100+100) = 0.95 × 102 + 0.05 × 202 = 96.9 + 10.1 = 107.0 ns ≈ 107.1 ns.

Analyze / Compare (Q21–Q25)

Q21

Which of the following is true about FIFO but NOT about LRU?

It requires future knowledge
It suffers from Belady's Anomaly
It is impractical to implement
It uses temporal locality

Analyze

✅ Answer: (B) — Only FIFO suffers from Belady's Anomaly. LRU is a stack algorithm and is immune to it.

Q22

A system has 4 frames. Process A needs 3 frames for its working set, Process B needs 3 frames. What will likely happen?

Both run optimally — 4 frames is enough
Thrashing — total working set (6) exceeds available frames (4)
Deadlock
The OS will crash

Analyze

✅ Answer: (B) — Total working set = 3 + 3 = 6 frames needed, but only 4 available. Neither process can hold its full working set, leading to frequent page faults → thrashing.

Q23

Compare segmentation and paging. Which statement is correct?

Both cause internal fragmentation
Segmentation causes external fragmentation, paging causes internal fragmentation
Paging causes external fragmentation, segmentation causes internal
Neither causes any fragmentation

Analyze

✅ Answer: (B) — Segmentation uses variable-sized blocks → external fragmentation (holes between segments). Paging uses fixed-sized blocks → internal fragmentation (last page may not be full).

Q24

Given the reference string: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5. FIFO with 3 frames gives 9 faults. FIFO with 4 frames gives:

8 faults
9 faults
10 faults
7 faults

Analyze

✅ Answer: (C) 10 faults — This is the classic example of Belady's Anomaly! More frames (4 > 3) but MORE faults (10 > 9). This only happens with FIFO.

Q25

Why does the inverted page table have one entry per frame rather than one per page?

To increase lookup speed
Because frames are larger than pages
To keep the table size proportional to physical memory, not logical address space
Because not all pages need mapping

Analyze

✅ Answer: (C) — In a 64-bit system, the logical address space is enormous (2^64 pages). A regular page table would be impossibly large. An inverted table has one entry per physical frame — much smaller since physical memory is limited.

Evaluate / Justify (Q26–Q28)

Q26

A web server processes 10,000 requests/sec. Its TLB hit ratio drops from 98% to 70% due to context switching. Memory access time = 100ns, TLB access = 5ns. How much slower does address translation become?

About 1.5× slower
About 1.3× slower
About 2× slower
No change

Evaluate

✅ Answer: (B) — EAT at 98% = 0.98×105 + 0.02×205 = 102.9+4.1 = 107ns. EAT at 70% = 0.70×105 + 0.30×205 = 73.5+61.5 = 135ns. Ratio = 135/107 ≈ 1.26× slower ≈ about 1.3× slower.

Q27

A system administrator notices CPU utilisation has dropped to 5% while disk I/O is at 95%. What should they do?

Add more CPU cores
Reduce the degree of multiprogramming (suspend some processes)
Increase disk speed
Add more swap space

Evaluate

✅ Answer: (B) — This is classic thrashing. Low CPU + high disk I/O = processes are constantly paging. The solution is to reduce the number of processes so remaining ones get enough frames. Adding swap space would make it worse (more room to thrash).

Q28

For a real-time embedded system in an Indian railway signalling controller, which page replacement would you recommend and why?

FIFO — simplest implementation for resource-constrained hardware
LRU — best fault rate among implementable algorithms
No virtual memory — use fixed memory allocation for deterministic timing
Optimal — gives best results

Evaluate

✅ Answer: (C) — Real-time safety-critical systems (like railway signalling) avoid virtual memory entirely because page faults introduce unpredictable delays. They use fixed memory allocation where all code/data is loaded at startup — deterministic and safe.

Create / Design (Q29–Q30)

Q29

You're designing memory management for a budget Android phone with 3GB RAM. Which combination of techniques would you use?

Simple paging + FIFO + no swap
Demand paging + LRU approximation + compressed swap (zRAM) + aggressive Low Memory Killer
Segmentation only + no virtual memory
Overlay-based memory management

Create

✅ Answer: (B) — Modern Android uses demand paging with LRU-approximation (clock algorithm), zRAM (compressed in-memory swap to avoid slow disk I/O), and an aggressive Low Memory Killer to terminate background apps when memory is low. This is exactly what Xiaomi, Realme, and Samsung use in budget phones.

Q30

Design a page replacement policy for CoWIN-like systems that must handle sudden traffic spikes. Which approach is most effective?

Use FIFO with maximum frames pre-allocated
Use working set model with dynamic frame allocation + thrashing detection (PFF) + auto-scaling cloud servers
Use Optimal algorithm
Disable virtual memory completely

Create

✅ Answer: (B) — For traffic-spike systems, the working set model ensures each process has enough frames. Page Fault Frequency (PFF) monitoring detects thrashing early. Auto-scaling (AWS/Azure) adds servers when memory pressure exceeds thresholds. This prevents CoWIN-style crashes.

Section H

Short Answer Questions (5)

Q1: Explain the difference between internal and external fragmentation with examples. How does paging solve one but not the other?

Model Answer:

Internal fragmentation is wasted space INSIDE an allocated block. Example: A process of 290K is allocated a 300K partition → 10K is wasted inside the partition, unusable by anyone.

External fragmentation is wasted space BETWEEN allocated blocks. Example: Free memory consists of three non-contiguous holes of 50K each (total 150K free), but a process needing 120K cannot be allocated because no single hole is large enough.

Paging solves external fragmentation because pages can be placed in ANY available frame — they don't need to be contiguous. A 120K process can use 30 pages of 4K each, scattered across any free frames.

Paging does NOT solve internal fragmentation because the last page of a process may not be fully utilised. If a process is 10.5KB and page size is 4KB, it needs 3 pages (12KB) → 1.5KB wasted in the last page.

Q2: Calculate the Effective Access Time (EAT) given: TLB hit ratio = 85%, TLB access time = 15ns, memory access time = 80ns. What happens if hit ratio improves to 99%?

Model Answer:

EAT = α(TLB + Mem) + (1−α)(TLB + Mem + Mem)

At 85%: EAT = 0.85(15+80) + 0.15(15+80+80) = 0.85(95) + 0.15(175) = 80.75 + 26.25 = 107 ns

At 99%: EAT = 0.99(95) + 0.01(175) = 94.05 + 1.75 = 95.8 ns

Improvement: 107/95.8 ≈ 1.12× faster. This shows why TLB hit ratio is critical — even a few % improvement has significant impact at scale (millions of memory accesses per second).

Q3: Trace the FIFO algorithm for reference string 1, 2, 3, 4, 5, 1, 2, 3 with 4 frames. Count page faults.

Model Answer:

Step	1	2	3	4	5	6	7	8
Page	1	2	3	4	5	1	2	3
Action	F	F	F	F	F	F	F	F

Frames after each step: [1]→[1,2]→[1,2,3]→[1,2,3,4]→[5,2,3,4](evict1)→[5,1,3,4](evict2)→[5,1,2,4](evict3)→[5,1,2,3](evict4)

Total page faults = 8 (every reference is a fault!)

This happens because every new page evicts the one it'll need next — a worst-case scenario for FIFO.

Q4: What is thrashing? What causes it and how can the working set model prevent it?

Model Answer:

Thrashing is when a system spends more time handling page faults (swapping pages in/out of disk) than executing actual process instructions. CPU utilisation drops drastically despite high disk I/O.

Causes: (1) Too many processes competing for limited physical frames. (2) Each process's working set exceeds its allocated frames. (3) OS tries to increase multiprogramming when CPU utilisation drops (making thrashing worse).

Working Set Model: The working set W(t,Δ) is the set of pages referenced by a process in the last Δ time units. The OS ensures each process gets at least as many frames as its working set size. If total working set of all processes exceeds total frames, the OS suspends some processes rather than letting all of them thrash.

Q5: A process has 8 pages. Page size = 2KB. Page table: {0→3, 1→7, 2→1, 3→5, 4→0, 5→4, 6→2, 7→6}. Translate logical address 5000 to physical address.

Model Answer:

Page number = ⌊5000/2048⌋ = ⌊2.441⌋ = 2

Offset = 5000 mod 2048 = 5000 − (2 × 2048) = 5000 − 4096 = 904

Page 2 → Frame 1 (from page table)

Physical address = Frame × Page size + Offset = 1 × 2048 + 904 = 2952

✅ Logical address 5000 → Physical address 2952

Section I

Case Studies

📋 Case Study 1: CoWIN Thrashing — When India's Vaccine System Collapsed

Background

On May 1, 2021, India opened COVID-19 vaccination registration for everyone aged 18+. Over 25 million users simultaneously hit the CoWIN platform (cowin.gov.in). The servers — hosted on NIC (National Informatics Centre) infrastructure — were not designed for this scale.

What Happened (Memory Perspective)

Each user session spawned a server process that needed memory for session data, database connections, and page rendering
With 25 million concurrent requests, the servers ran out of physical memory (RAM)
The OS began aggressive swapping — moving process pages to disk swap space
Thrashing began: Processes spent more time waiting for their pages to be loaded from disk than actually processing requests
CPU utilisation dropped to near 0% despite all cores being "busy" (waiting for I/O)
Response times went from 200ms to 30+ seconds, then complete timeout

Root Cause Analysis

Issue	Memory Concept
Too many processes for available RAM	Working set of all processes > total physical frames
No memory-aware load balancing	New requests kept coming even when frames were exhausted
Swap space on slow HDDs	Page fault service time was 10ms+ (vs. 100ns for RAM)
No thrashing detection	OS kept increasing multiprogramming → death spiral

What Should Have Been Done

Rate limiting at the load balancer — reject requests when memory pressure > 80%
Working set monitoring — ensure each Java process has enough heap + stack frames
Thrashing detection (PFF) — if page fault rate spikes, stop accepting new connections
Auto-scaling — spin up new cloud servers when memory utilisation crosses 70%
Use SSD-backed swap instead of HDD — 100× faster page fault handling

Discussion Questions

If CoWIN had 100 servers, each with 64GB RAM and 4KB page size, how many total frames were available?
If each user session needs 256KB, how many concurrent users could be served without swapping?
Design a thrashing prevention system for the next CoWIN-scale event (like IRCTC Tatkal).

📋 Case Study 2: Android OOM Killer — Managing Memory on Indian Budget Smartphones

Background

India has 750+ million smartphone users. Over 60% use budget phones (₹8,000–₹15,000) with only 3–4 GB RAM. These phones run Android, which must juggle WhatsApp, Instagram, Chrome, YouTube, UPI apps, and background services — all competing for limited memory.

Android's Memory Management Architecture

Android uses a modified Linux kernel with a special component called the Low Memory Killer (LMK) — essentially a page replacement + process management system.

Process Category	Priority	Kill Threshold	Example
Foreground	Highest	Never killed (unless critical)	App you're currently using
Visible	High	Only under extreme pressure	App with a visible floating widget
Service	Medium	Killed when memory < 100MB free	Music player, download manager
Cached	Low	First to be killed	App you used 10 minutes ago
Empty	Lowest	Killed immediately when needed	App with no active components

The Indian Budget Phone Problem

WhatsApp alone uses 200–400MB RAM (media cache, chat database)
Chrome with 3 tabs uses 300–500MB
Instagram uses 250–350MB (image/video cache)
Android OS itself uses ~1.5GB
Total: 2.5–3.0GB needed for just 3 apps + OS on a 3GB phone!

This means the LMK is constantly killing and restarting apps. Users experience:

Apps reloading when switching (WhatsApp restarts when returning from Chrome)
Notifications delayed (background services killed)
Phone feeling "slow" despite a decent CPU

Solutions Used by Indian Phone Makers

Solution	Company	How It Works
RAM Extension (zRAM)	Xiaomi, Samsung, Vivo	Compresses inactive pages in RAM instead of swapping to slow storage. "4GB+2GB Virtual RAM"
App Freezing	Samsung (OneUI)	Background apps are frozen (not killed), preserving state without consuming CPU
Memory Fusion	Vivo, OPPO	Uses fast UFS storage as swap (3–5× faster than eMMC)
Aggressive LMK Tuning	Realme	Kills cached apps earlier to keep foreground app smooth

Discussion Questions

If a 4GB phone uses zRAM with 2:1 compression ratio, what is the effective RAM?
Design an LMK policy for a student's phone that prioritises WhatsApp and a UPI app while allowing Chrome to be killed freely.
Compare zRAM (compressed RAM swap) vs. traditional swap partition. Which causes fewer page faults? Why?

Section J

Chapter Summary

📋 Key Takeaways — Memory Management

Logical vs Physical Address: CPU generates logical addresses; MMU translates them to physical addresses using page tables or relocation registers.
Address Binding: Can happen at compile-time (fixed), load-time (relocatable), or execution-time (dynamic via MMU).
Contiguous Allocation: Fixed partitioning → internal fragmentation. Variable partitioning → external fragmentation. First Fit is generally best in practice.
Paging: Divides memory into fixed-size pages (logical) and frames (physical). Eliminates external fragmentation. Address = Page# × Page_size + Offset.
TLB: Hardware cache for page table entries. High TLB hit ratio (>95%) is critical for performance.
Segmentation: Variable-size blocks matching program structure. Causes external fragmentation. Segment table stores (base, limit).
Page Replacement (3 frames, standard string): FIFO = 15 faults, LRU = 12 faults, Optimal = 9 faults.
Belady's Anomaly: Only FIFO can have more faults with more frames. LRU and Optimal are immune.
Thrashing: Processes page-fault constantly → CPU utilisation drops. Solution: working set model, PFF, reduce multiprogramming.
Virtual Memory: Demand paging gives illusion of large memory. Only needed pages loaded. Page faults handled by OS.

Quick-Reference Formulas

Formula	Meaning
`Page# = ⌊Address / Page_size⌋`	Extract page number from logical address
`Offset = Address mod Page_size`	Extract offset within page
`Physical = Frame# × Page_size + Offset`	Compute physical address
`EAT = α(t+m) + (1−α)(t+2m)`	Effective Access Time (t=TLB time, m=memory time, α=hit ratio)
`Frames = Physical_memory / Page_size`	Number of frames available
`Pages = Logical_space / Page_size`	Number of pages in logical address space

Section K

Earning Checkpoint — Are You Ready to Earn?

Skill Learned	Tool/Method	Portfolio Proof	Earning Ready?
Address Translation	Manual calculation	Solved problems in notebook	✅ Yes — can teach/tutor OS numericals
Page Replacement Algorithms	Python simulator	Working FIFO/LRU/OPT simulator	✅ Yes — Fiverr gig + tutorial video
Memory Profiling	Python psutil	System monitor tool	✅ Yes — ₹5,000–₹15,000/deployment
Thrashing Analysis	Conceptual + case study	CoWIN analysis document	✅ Yes — can discuss in interviews
EAT Calculation	Formula application	Solved examples	✅ Yes — competitive exam preparation
System Design (Memory)	Case study analysis	Android OOM analysis	✅ Yes — interview discussions at Qualcomm/Samsung level

Minimum Viable Earning Setup after this chapter: A Python page replacement simulator (GitHub) + a system memory monitor tool + ability to solve any paging/replacement numerical = you can offer OS tutoring (₹500–₹2,000/hour) + Python automation gigs (₹5,000–₹15,000) + competitive exam coaching (₹8K–₹25K/month).

✅ Unit 7 complete. Numerical problems: 10+. MCQs: 30. Ready for Unit 8!

[QR: Link to EduArtha video tutorial — Memory Management]