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. In which scenario is segmentation preferred over paging for memory management?

easy

A. When fixed-size memory blocks are needed to simplify allocation

B. When hardware support for address translation is limited

C. When minimizing internal fragmentation is the primary goal

D. When the program requires logical division of memory into variable-sized segments

Solution

1. Step 1: Understand segmentation's purpose

   Segmentation divides memory into logical units like code, stack, and data, which can vary in size.

2. Step 2: Analyze When fixed-size memory blocks are needed to simplify allocation

   Paging uses fixed-size pages, not segmentation, so this is incorrect.

3. Step 3: Analyze When minimizing internal fragmentation is the primary goal

   Paging reduces internal fragmentation better than segmentation; segmentation can have external fragmentation.

4. Step 4: Analyze When hardware support for address translation is limited

   Both paging and segmentation require hardware support; limited hardware support is not a reason to prefer segmentation.

5. Final Answer:

   Option D -> Option D

6. Quick Check:

   Segmentation fits variable-sized logical divisions, matching the scenario described in When the program requires logical division of memory into variable-sized segments.

Hint: Segmentation = logical variable-sized chunks; Paging = fixed-size blocks

Common Mistakes:

• Confusing segmentation with fixed-size allocation
• Assuming segmentation eliminates fragmentation
• Believing segmentation is chosen due to hardware limits

2. In which scenario is the Process Control Block (PCB) primarily used during the process state transitions in the five-state model?

easy

A. When a process moves from New to Ready state to store initial process information

B. When a process is terminated to delete all its data from memory

C. When a process is in the Ready state to execute instructions directly

D. When a process moves from Running to Waiting state to save CPU registers and state

Solution

1. Step 1: Understand the role of PCB during state transitions

   The PCB stores the process state, CPU registers, and scheduling information during context switches.

2. Step 2: Analyze each option

   A: PCB is created at process creation but its primary use is during context switches, not just at New to Ready.
   B: PCB is involved in termination but mainly to release resources; it is not primarily used to delete data.
   C: Processes in Ready state do not execute instructions directly; they wait for CPU allocation.
   D: Correct. When a process moves from Running to Waiting, the PCB saves CPU registers and state for resumption.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   PCB is essential for saving CPU state during Running to Waiting transitions [OK]

Hint: PCB saves CPU state during Running to Waiting transitions [OK]

Common Mistakes:

• Thinking PCB is only used at process creation
• Assuming Ready state processes execute instructions
• Believing PCB is deleted immediately at termination

3. Why is it generally inefficient to keep a process in the Ready state for a long time without scheduling it to Running, especially in a multi-core system?

medium

A. Because the process wastes CPU cache locality and increases context switch overhead when scheduled later

B. Because the process holds resources like memory and I/O devices exclusively while Ready

C. Because the process consumes CPU cycles even in Ready state, reducing overall throughput

D. Because the process cannot perform I/O operations while in Ready state, causing system deadlocks

Solution

1. Step 1: Understand Ready state resource usage

   Processes in Ready state do not consume CPU cycles but occupy scheduling queues.

2. Step 2: Analyze each option

   A: Correct. Long Ready times cause loss of CPU cache locality and increase context switch overhead when finally scheduled.
   B: Incorrect. Processes do not hold exclusive I/O or memory resources just by being Ready.
   C: Incorrect. Ready processes do not consume CPU cycles.
   D: Incorrect. Ready processes do not cause deadlocks by not performing I/O.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Ready state delays hurt cache locality and increase context switch costs [OK]

Hint: Ready state processes wait without CPU but lose cache locality and increase context switch overhead [OK]

Common Mistakes:

• Believing Ready processes consume CPU cycles
• Assuming Ready processes hold exclusive resources
• Confusing Ready state with Waiting state regarding I/O

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. What is a key limitation of the working set model in preventing thrashing that candidates often overlook?

medium

A. It requires tracking all page references, which can be expensive and complex

B. It guarantees zero page faults once the working set is allocated

C. It works best when all processes have identical working set sizes

D. It eliminates the need for load control mechanisms

Solution

1. Step 1: Understand working set model overhead

   The model requires monitoring page references over time windows, which can be costly.

2. Step 2: Analyze options

   A is correct because tracking page references precisely is resource-intensive.
   B is incorrect because even with working set allocation, some page faults can occur.
   C is incorrect because working set sizes vary widely among processes.
   D is incorrect because load control is still needed when total working sets exceed memory.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Working set tracking overhead is a practical limitation often underestimated.

Hint: Working set tracking = overhead cost

Common Mistakes:

• Assuming working set eliminates all page faults
• Believing all processes have similar working sets
• Ignoring the need for load control