Gyanrush
Start freeOpen Gyanrush
Start freeOpen Gyanrush
  1. LPU MCA Semester 1
  2. CAP366
  3. Unit 7

CAP366 · Unit 7: Memory management

Page replacement algorithms

10 practice questions · in the ETE syllabus

Practise this topicPractise this topic

Key points

  • FIFO, LRU and optimal differ in the victim they choose
  • Optimal is a benchmark, not implementable
  • LRU is a stack algorithm and has no Belady's anomaly
  • EAT = (1-p) x memory time + p x fault time

When a page fault occurs and no frame is free, the OS picks a victim page to replace. Algorithms are compared by the number of page faults on a reference string.

AlgorithmVictim
FIFOOldest page in memory
OptimalPage not used for the longest time in the future
LRUPage not used for the longest time in the past

Optimal gives the minimum faults but needs knowledge of the future, so it is a yardstick. LRU is a stack algorithm, so it never shows Belady's anomaly; FIFO can. A dirty bit tells the OS whether a victim must be written back to disk.

Worked example: on 7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1 with 3 frames, FIFO gives 15 faults, LRU 12 and optimal 9. On 1,2,3,4,1,2,5,1,2,3,4,5, FIFO gives 9 faults with 3 frames but 10 with 4 frames, which is Belady's anomaly.

Effective access time with fault rate p is (1 - p) x memory time + p x fault service time, so even a tiny p matters when the fault takes milliseconds.

Exam trap: more frames do not always mean fewer faults under FIFO.

Try two questions

Question 1 · Tier 3, Apply

Use FIFO replacement and three frames on the reference string 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1. How many page faults occur?

  1. 12
  2. 15
  3. 9
  4. 18
Show the answer

B. Simulating FIFO with three frames gives 15 faults for this string.

Why not A: 12 is the LRU count for this string.

Why not C: 9 is the optimal count for this string.

Why not D: 18 overcounts and is not the FIFO figure.

Question 2 · Tier 2, Understand

Which page replacement algorithm is free of Belady's anomaly?

  1. FIFO, because it replaces the oldest page
  2. Second chance, because it uses a reference bit
  3. Random replacement, because it has no pattern
  4. LRU, because it is a stack algorithm
Show the answer

D. In a stack algorithm the set of pages with n frames is a subset of the set with n + 1 frames, which rules out the anomaly.

Why not A: FIFO is the classic example of the anomaly.

Why not B: Second chance reduces to FIFO in the worst case and can show the anomaly.

Why not C: Random replacement has no stack property, so a guarantee does not hold.