Assume that a main memory with only 4 pages, each of 16 bytes, is initially…

2008

Assume that a main memory with only 4 pages, each of 16 bytes, is initially empty. The CPU generates the following sequence of virtual addresses and uses the Least Recently Used (LRU) page replacement policy.
0, 4, 8, 20, 24, 36, 44, 12, 68, 72, 80, 84, 28, 32, 88, 92
How many page faults does this sequence cause? What are the page numbers of the pages present in the main memory at the end of the sequence?

  1. A.

    6 and 1, 2, 3, 4

  2. B.

    7 and 1, 2, 4, 5

  3. C.

    8 and 1, 2, 4, 5

  4. D.

    9 and 1, 2, 3, 5

Attempted by 120 students.

Show answer & explanation

Correct answer: B

Answer: There are 7 page faults. The pages present in main memory at the end are 1, 2, 4, and 5.

Step 1 — compute page numbers (page size = 16 bytes):

  • Addresses: 0, 4, 8, 20, 24, 36, 44, 12, 68, 72, 80, 84, 28, 32, 88, 92

  • Page numbers (address // 16): 0, 0, 0, 1, 1, 2, 2, 0, 4, 4, 5, 5, 1, 2, 5, 5

Step 2 — simulate LRU with four frames:

  1. Access page 0 → frames: [0] → page fault (count = 1)

  2. Access page 0 → hit → frames: [0] (count = 1)

  3. Access page 0 → hit → frames: [0] (count = 1)

  4. Access page 1 → frames: [0, 1] → page fault (count = 2)

  5. Access page 1 → hit → frames: [0, 1] (count = 2)

  6. Access page 2 → frames: [0, 1, 2] → page fault (count = 3)

  7. Access page 2 → hit → frames: [0, 1, 2] (count = 3)

  8. Access page 0 → hit (updates recency) → frames: [0, 1, 2] (count = 3)

  9. Access page 4 → frames: [0, 1, 2, 4] → page fault (count = 4)

  10. Access page 4 → hit → frames: [0, 1, 2, 4] (count = 4)

  11. Access page 5 → page fault. Evict the least recently used page (which is page 1) → frames: [0, 2, 4, 5] (count = 5)

  12. Access page 5 → hit → frames: [0, 2, 4, 5] (count = 5)

  13. Access page 1 → page fault. Evict least recently used page (page 2) → frames: [0, 4, 5, 1] (count = 6)

  14. Access page 2 → page fault. Evict least recently used page (page 0) → frames: [4, 5, 1, 2] (count = 7)

  15. Access page 5 → hit → frames: [4, 5, 1, 2] (count = 7)

  16. Access page 5 → hit → frames remain [4, 5, 1, 2] (count = 7)

Summary:

  • Total page faults = 7.

  • Pages in main memory at the end = 1, 2, 4, 5.

Explore the full course: Gate Guidance By Sanchit Sir