Page Replacement - FIFO, LRU, Optimal Algorithm

▶

Steps

setup

Initialize FIFO Page Replacement

Start with an empty queue and empty set to track pages in memory. Page fault count is zero.

💡 Initialization sets up the data structures needed to track pages and detect faults efficiently.

Line:

queue = []  # Queue to store pages in FIFO order
page_set = set()  # Set for O(1) lookup
page_faults = 0

💡 The queue will maintain insertion order, crucial for FIFO eviction.

insert

Process page 7 - Page Fault

Page 7 is not in memory, causing a page fault. It is added to the queue and set.

💡 Adding a new page when memory is not full causes a fault and increases the fault count.

Line:

if page not in page_set:
    page_faults += 1
    queue.append(page)
    page_set.add(page)

💡 Page fault occurs when a page is first referenced and not in memory.

insert

Process page 0 - Page Fault

Page 0 is not in memory, causing a page fault. It is added to the queue and set.

💡 Memory still has space, so page 0 is simply added, increasing faults.

Line:

if page not in page_set:
    page_faults += 1
    queue.append(page)
    page_set.add(page)

💡 Pages are added in arrival order until capacity is reached.

insert

Process page 1 - Page Fault

Page 1 is not in memory, causing a page fault. It is added to the queue and set.

💡 Memory still has space for one more page before eviction is needed.

Line:

if page not in page_set:
    page_faults += 1
    queue.append(page)
    page_set.add(page)

💡 Pages fill memory until capacity is reached.

delete

Process page 2 - Evict page 7, Page Fault

Page 2 is not in memory and capacity is full. Evict oldest page 7, then add page 2.

💡 FIFO evicts the oldest page to make room for the new page, causing a fault.

Line:

if len(queue) == capacity:
    removed = queue.pop(0)  # Remove oldest page
    page_set.remove(removed)
queue.append(page)
page_set.add(page)

💡 FIFO strictly removes the earliest loaded page regardless of future use.

compare

Process page 0 - No Page Fault

Page 0 is already in memory, so no page fault occurs.

💡 If the page is already in memory, no eviction or fault is needed.

Line:

if page not in page_set:
    # fault handling
else:
    # no fault

💡 Page hits do not increase fault count or change memory state.

delete

Process page 3 - Evict page 0, Page Fault

Page 3 is not in memory and capacity is full. Evict oldest page 0, then add page 3.

💡 FIFO evicts the oldest page in queue order to handle new page fault.

Line:

if len(queue) == capacity:
    removed = queue.pop(0)
    page_set.remove(removed)
queue.append(page)
page_set.add(page)

💡 FIFO does not consider page usage, only arrival order.

delete

Process page 0 - Evict page 1, Page Fault

Page 0 is not in memory. Evict oldest page 1, then add page 0.

💡 FIFO continues evicting oldest pages to handle faults.

Line:

if len(queue) == capacity:
    removed = queue.pop(0)
    page_set.remove(removed)
queue.append(page)
page_set.add(page)

💡 FIFO strictly follows insertion order for eviction.

delete

Process page 4 - Evict page 2, Page Fault

Page 4 is not in memory. Evict oldest page 2, then add page 4.

💡 FIFO evicts the oldest page to make room for the new page.

Line:

if len(queue) == capacity:
    removed = queue.pop(0)
    page_set.remove(removed)
queue.append(page)
page_set.add(page)

💡 FIFO eviction order is predictable and simple.

reconstruct

FIFO Algorithm Complete - Total Page Faults

All pages processed. Total page faults counted as 6.

💡 The final fault count summarizes the algorithm's performance on this input.

Line:

return page_faults

💡 FIFO caused 6 page faults for this sequence and capacity.

def fifo_page_replacement(pages, capacity):
    queue = []  # STEP 1: Initialize queue
    page_set = set()  # STEP 1: Initialize set
    page_faults = 0  # STEP 1: Initialize fault count
    for page in pages:
        if page not in page_set:  # STEP 2-9: Check if page fault
            page_faults += 1  # STEP 2-9: Increment fault
            if len(queue) == capacity:  # STEP 5,7,8,9: Evict if full
                removed = queue.pop(0)  # STEP 5,7,8,9: Remove oldest
                page_set.remove(removed)  # STEP 5,7,8,9: Remove from set
            queue.append(page)  # STEP 2-9: Add new page
            page_set.add(page)  # STEP 2-9: Add to set
    return page_faults  # STEP 10: Return total faults

📊

Page Replacement - FIFO, LRU, Optimal Algorithm - Watch the Algorithm Execute, Step by Step

Watching the algorithm step-by-step reveals the dynamic decisions behind page replacement, which are hard to grasp from code alone.

Transition new → ready pid:fifo - Initialization complete

fifo

ready

Ready Queue

fifo

Waiting Queue

empty

🖥CPUidlet=0

Transition ready → running pid:fifo - Processing page 7

fifo

running

Ready Queue

empty

Waiting Queue

empty

🖥CPUfifot=1

fifo

Transition running → running pid:fifo - Processing page 0

fifo

running

Ready Queue

empty

Waiting Queue

empty

🖥CPUfifot=2

fifo

Transition running → running pid:fifo - Processing page 1

fifo

running

Ready Queue

empty

Waiting Queue

empty

🖥CPUfifot=3

fifo

Transition running → running pid:fifo - Evicted page 7 to add page 2

fifo

running

Ready Queue

empty

Waiting Queue

empty

🖥CPUfifot=4

fifo

Transition running → running pid:fifo - Page 0 hit in memory

fifo

running

Ready Queue

empty

Waiting Queue

empty

🖥CPUfifot=5

fifo

Transition running → running pid:fifo - Evicted page 0 to add page 3

fifo

running

Ready Queue

empty

Waiting Queue

empty

🖥CPUfifot=6

fifo

Transition running → running pid:fifo - Evicted page 1 to add page 0

fifo

running

Ready Queue

empty

Waiting Queue

empty

🖥CPUfifot=7

fifo

Transition running → running pid:fifo - Evicted page 2 to add page 4

fifo

running

Ready Queue

empty

Waiting Queue

empty

🖥CPUfifot=8

fifo

Transition running → terminated pid:fifo - Algorithm completed

fifo

terminated

burst: 0

Ready Queue

empty

Waiting Queue

empty

🖥CPUidlet=8

fifo

Key Takeaways

✓ FIFO evicts the oldest page regardless of future use.

This insight is hard to see from code alone because the eviction is implicit in the queue structure.

✓ Page faults occur only when a page is not in memory.

Visualizing each page check clarifies when faults happen and when pages are hits.

✓ The queue order directly controls eviction order in FIFO.

Seeing the queue update step-by-step reveals how insertion order drives eviction.

Practice

1. Which of the following statements best describes a limitation of FCFS scheduling related to waiting time and system responsiveness?

medium

A. FCFS can cause long waiting times for short processes due to the convoy effect

B. FCFS guarantees the shortest average waiting time among all scheduling algorithms

C. FCFS allows preemption to improve responsiveness for interactive processes

D. FCFS scheduling complexity grows exponentially with the number of processes

Solution

1. Step 1: Evaluate each statement

   A is correct because FCFS can cause long waiting times for short processes due to the convoy effect.
   B is incorrect because FCFS does not guarantee the shortest average waiting time; algorithms like SJF do.
   C is incorrect because FCFS is non-preemptive and does not allow preemption.
   D is incorrect because FCFS scheduling complexity is O(n), simple queue processing.

2. Step 2: Identify the limitation

   The convoy effect causing long waiting times for short processes is a key limitation.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   FCFS is simple but can cause poor responsiveness due to the convoy effect.

Hint: FCFS = simple but convoy effect hurts short jobs

Common Mistakes:

• Believing FCFS minimizes average waiting time
• Confusing FCFS with preemptive algorithms
• Overestimating FCFS scheduling complexity

2. Why might a file system designer limit the number of indirect pointers in an inode rather than allowing unlimited indirect pointers for very large files?

medium

A. Because indirect pointers increase the inode size exponentially, making inodes too large to store efficiently.

B. Because indirect pointers consume more inode space, reducing the number of files the system can track.

C. Because increasing indirect pointers indefinitely would cause excessive disk seek times and degrade performance.

D. Because indirect pointers require complex encryption, increasing CPU overhead.

Solution

1. Step 1: Understand performance impact of indirect pointers

   Each level of indirection adds extra disk reads, increasing seek times and latency.

2. Step 2: Analyze inode size constraints

   Indirect pointers are stored in data blocks, not inodes, so inode size is fixed and not directly affected.

3. Step 3: Clarify inode size growth

   Inode size does not grow exponentially with indirect pointers; pointer blocks are separate.

4. Step 4: Dispel encryption misconception

   Indirect pointers do not inherently require encryption or extra CPU overhead.

5. Final Answer:

   Option C -> Option C

6. Quick Check:

   Performance degradation due to multiple disk seeks is the main limitation [OK]

Hint: More indirection -> more disk seeks -> slower access

Common Mistakes:

• Confusing inode size with pointer block size
• Assuming inode size grows with indirect pointers
• Believing indirect pointers require encryption overhead

3. What is the primary trade-off when choosing a very small time quantum in Round Robin scheduling?

medium

A. Processes with longer CPU bursts get more CPU time per cycle

B. Longer average turnaround time due to processes waiting longer in the queue

C. Reduced fairness among processes with different burst lengths

D. Increased context switching overhead leading to reduced CPU efficiency

Solution

1. Step 1: Understand impact of small quantum

   A very small quantum causes frequent context switches, which consume CPU cycles and reduce efficiency.

2. Step 2: Analyze other options

   Longer average turnaround time due to processes waiting longer in the queue is incorrect because smaller quantum generally reduces waiting time for short processes. Processes with longer CPU bursts get more CPU time per cycle is false; small quantum limits CPU time per cycle for long bursts. Reduced fairness among processes with different burst lengths is incorrect because smaller quantum improves fairness.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Small quantum -> more context switches -> overhead ↑ -> efficiency ↓.

Hint: Small quantum -> high context switch overhead

Common Mistakes:

• Assuming smaller quantum always improves turnaround time
• Believing small quantum favors longer processes
• Confusing fairness impact with quantum size

4. Which of the following is a significant drawback of preemptive SJF scheduling compared to non-preemptive SJF?

medium

A. It reduces CPU utilization due to frequent context switches

B. It can cause starvation of longer processes if short jobs keep arriving

C. It always results in higher average turnaround time

D. It cannot handle processes arriving at different times

Solution

1. Step 1: Understand starvation in preemptive SJF

   Shorter jobs can continuously preempt longer ones, causing longer processes to wait indefinitely.

2. Step 2: Analyze other options

   A: While context switches increase, CPU utilization remains high; overhead is a concern but not utilization.
   B: Preemptive SJF generally reduces average turnaround time, not increases it.
   D: Preemptive SJF is designed to handle processes arriving at different times.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Starvation is a classic drawback of preemptive SJF.

Hint: Preemptive SJF risks starving long jobs if short jobs keep arriving [OK]

Common Mistakes:

• Confusing turnaround time impact
• Assuming preemptive SJF cannot handle dynamic arrivals

5. Why is it generally inefficient to implement all OS services as system calls requiring mode switches?

medium

A. Because mode switches cause significant CPU overhead and latency

B. Because system calls cannot access hardware devices

C. Because user mode has unrestricted access to kernel data structures

D. Because system calls bypass the CPU privilege checks

Solution

1. Step 1: Understand mode switch cost

   Switching from user to kernel mode involves saving/restoring CPU state and flushing pipelines, which is expensive.

2. Step 2: Why not all services as system calls

   Excessive mode switches degrade performance, so only critical OS services use system calls.

3. Step 3: Why other options are incorrect

   Because system calls cannot access hardware devices is false; system calls are the mechanism to access hardware safely. Because user mode has unrestricted access to kernel data structures is false; user mode is restricted from kernel data. Because system calls bypass the CPU privilege checks is false; system calls enforce privilege checks via mode switch.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Mode switch overhead limits system call usage [OK]

Hint: Mode switches are costly, so minimize system calls

Common Mistakes:

• Believing system calls cannot access hardware
• Thinking user mode has full kernel access
• Assuming system calls skip privilege checks