GATE CS Mastery
Cheat sheets

GATE CS 2012 · Operating Systems

Question 42

MCQPrinted as CS Q.422 marksWrong answer: −2/3Medium (estimate)

Question

Consider the virtual page reference string

1,2,3,2,4,1,3,2,4,11, 2, 3, 2, 4, 1, 3, 2, 4, 1

on a demand paged virtual memory system running on a computer system that has main memory size of 3 page frames which are initially empty. Let LRU, FIFO and OPTIMAL denote the number of page faults under the corresponding page replacement policy. Then

Choose one option
Official answer and solution
Official answer
B
From
Official GATE 2012 answer key

Solution

Simulate page replacement on the given 10-reference string using 3 initially empty page frames for OPTIMAL, FIFO, and LRU algorithms.

  1. Page reference sequence: 1, 2, 3, 2, 4, 1, 3, 2, 4, 1, with 3 frames.

  2. OPTIMAL Simulation:

  • Ref 1: Fault, frames: [1] (Fault 1)
  • Ref 2: Fault, frames: [1, 2] (Fault 2)
  • Ref 3: Fault, frames: [1, 2, 3] (Fault 3)
  • Ref 2: Hit, frames: [1, 2, 3]
  • Ref 4: Fault. Next uses: 1 at pos 6, 3 at pos 7, 2 at pos 8. Replace 2: frames: [1, 4, 3] (Fault 4)
  • Ref 1: Hit, frames: [1, 4, 3]
  • Ref 3: Hit, frames: [1, 4, 3]
  • Ref 2: Fault. Next uses: 4 at pos 9, 1 at pos 10, 3 never. Replace 3: frames: [1, 4, 2] (Fault 5)
  • Ref 4: Hit, frames: [1, 4, 2]
  • Ref 1: Hit, frames: [1, 4, 2]
  • Total OPTIMAL faults = 5.
  1. FIFO Simulation:
  • Ref 1, 2, 3: Faults 1, 2, 3. Queue: [1, 2, 3]
  • Ref 2: Hit. Queue: [1, 2, 3]
  • Ref 4: Fault 4. Replace 1. Queue: [2, 3, 4]
  • Ref 1: Fault 5. Replace 2. Queue: [3, 4, 1]
  • Ref 3: Hit. Queue: [3, 4, 1]
  • Ref 2: Fault 6. Replace 3. Queue: [4, 1, 2]
  • Ref 4: Hit. Queue: [4, 1, 2]
  • Ref 1: Hit. Queue: [4, 1, 2]
  • Total FIFO faults = 6.
  1. LRU Simulation:
  • Ref 1, 2, 3: Faults 1, 2, 3. Recency: 1, 2, 3
  • Ref 2: Hit. Recency: 1, 3, 2
  • Ref 4: Fault 4. Replace LRU 1. Recency: 3, 2, 4
  • Ref 1: Fault 5. Replace LRU 3. Recency: 2, 4, 1
  • Ref 3: Fault 6. Replace LRU 2. Recency: 4, 1, 3
  • Ref 2: Fault 7. Replace LRU 4. Recency: 1, 3, 2
  • Ref 4: Fault 8. Replace LRU 1. Recency: 3, 2, 4
  • Ref 1: Fault 9. Replace LRU 3. Recency: 2, 4, 1
  • Total LRU faults = 9.
  1. Comparing fault counts:
OPTIMAL(5)<FIFO(6)<LRU(9)\text{OPTIMAL} (5) < \text{FIFO} (6) < \text{LRU} (9)
  1. Hence, Option (B) is correct.
Final answer

B

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper
GATE 2012 Computer Science and Information Technology (CS)
Question
42 of 65, printed as CS Q.42
Section
Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.