Consider the following page reference string: in Operating systems

Question

7, 2, 3, 1, 2, 5, 3, 4, 6, 7, 7, 1, 0, 5, 4, 6, 2, 3, 0 , 1.
Assuming demand paging with three frames, how many page faults would occur for the
following replacement algorithms?
A, LRU replacement
B. FIFO replacement
C. Optimal replacement

Answer 1

To calculate the number of page faults for the three replacement algorithms (LRU, FIFO, and Optimal) in a demand paging scenario with three frames, we need to track the state of the pages in the frames after each reference.

Given Page Reference String:

7, 2, 3, 1, 2, 5, 3, 4, 6, 7, 7, 1, 0, 5, 4, 6, 2, 3, 0, 1

A. LRU Replacement (Least Recently Used)

1. Reference 7: Page fault (frames: [7])
2. Reference 2: Page fault (frames: [7, 2])
3. Reference 3: Page fault (frames: [7, 2, 3])
4. Reference 1: Page fault (replace 7 with 1, frames: [1, 2, 3])
5. Reference 2: No page fault (frames: [1, 2, 3])
6. Reference 5: Page fault (replace 3 with 5, frames: [1, 2, 5])
7. Reference 3: Page fault (replace 2 with 3, frames: [1, 5, 3])
8. Reference 4: Page fault (replace 1 with 4, frames: [4, 5, 3])
9. Reference 6: Page fault (replace 5 with 6, frames: [4, 6, 3])
10. Reference 7: Page fault (replace 3 with 7, frames: [4, 6, 7])
11. Reference 7: No page fault (frames: [4, 6, 7])
12. Reference 1: Page fault (replace 4 with 1, frames: [1, 6, 7])
13. Reference 0: Page fault (replace 6 with 0, frames: [1, 0, 7])
14. Reference 5: Page fault (replace 7 with 5, frames: [1, 0, 5])
15. Reference 4: Page fault (replace 1 with 4, frames: [4, 0, 5])
16. Reference 6: Page fault (replace 0 with 6, frames: [4, 6, 5])
17. Reference 2: Page fault (replace 5 with 2, frames: [4, 6, 2])
18. Reference 3: Page fault (replace 4 with 3, frames: [3, 6, 2])
19. Reference 0: Page fault (replace 6 with 0, frames: [3, 0, 2])
20. Reference 1: Page fault (replace 2 with 1, frames: [3, 0, 1])

Total page faults for LRU: 14

B. FIFO Replacement (First-In, First-Out)

1. Reference 7: Page fault (frames: [7])
2. Reference 2: Page fault (frames: [7, 2])
3. Reference 3: Page fault (frames: [7, 2, 3])
4. Reference 1: Page fault (replace 7 with 1, frames: [1, 2, 3])
5. Reference 2: No page fault (frames: [1, 2, 3])
6. Reference 5: Page fault (replace 2 with 5, frames: [1, 3, 5])
7. Reference 3: No page fault (frames: [1, 3, 5])
8. Reference 4: Page fault (replace 1 with 4, frames: [4, 3, 5])
9. Reference 6: Page fault (replace 3 with 6, frames: [4, 6, 5])
10. Reference 7: Page fault (replace 5 with 7, frames: [4, 6, 7])
11. Reference 7: No page fault (frames: [4, 6, 7])
12. Reference 1: Page fault (replace 4 with 1, frames: [1, 6, 7])
13. Reference 0: Page fault (replace 6 with 0, frames: [1, 0, 7])
14. Reference 5: Page fault (replace 7 with 5, frames: [1, 0, 5])
15. Reference 4: Page fault (replace 1 with 4, frames: [4, 0, 5])
16. Reference 6: Page fault (replace 0 with 6, frames: [4, 6, 5])
17. Reference 2: Page fault (replace 5 with 2, frames: [4, 6, 2])
18. Reference 3: Page fault (replace 4 with 3, frames: [3, 6, 2])
19. Reference 0: Page fault (replace 6 with 0, frames: [3, 0, 2])
20. Reference 1: Page fault (replace 2 with 1, frames: [3, 0, 1])

Total page faults for FIFO: 15

C. Optimal Replacement

1. Reference 7: Page fault (frames: [7])
2. Reference 2: Page fault (frames: [7, 2])
3. Reference 3: Page fault (frames: [7, 2, 3])
4. Reference 1: Page fault (replace 7 with 1, frames: [1, 2, 3])
5. Reference 2: No page fault (frames: [1, 2, 3])
6. Reference 5: Page fault (replace 3 with 5, frames: [1, 2, 5])
7. Reference 3: Page fault (replace 2 with 3, frames: [1, 5, 3])
8. Reference 4: Page fault (replace 1 with 4, frames: [4, 5, 3])
9. Reference 6: Page fault (replace 5 with 6, frames: [4, 6, 3])
10. Reference 7: Page fault (replace 3 with 7, frames: [4, 6, 7])
11. Reference 7: No page fault (frames: [4, 6, 7])
12. Reference 1: Page fault (replace 4 with 1, frames: [1, 6, 7])
13. Reference 0: Page fault (replace 6 with 0, frames: [1, 0, 7])
14. Reference 5: Page fault (replace 7 with 5, frames: [1, 0, 5])
15. Reference 4: Page fault (replace 1 with 4, frames: [4, 0, 5])
16. Reference 6: Page fault (replace 0 with 6, frames: [4, 6, 5])
17. Reference 2: Page fault (replace 5 with 2, frames: [4, 6, 2])
18. Reference 3: Page fault (replace 4 with 3, frames: [3, 6, 2])
19. Reference 0: Page fault (replace 6 with 0, frames: [3, 0, 2])
20. Reference 1: Page fault (replace 2 with 1, frames: [3, 0, 1])

Total page faults for Optimal: 13

Summary of Page Faults:

• LRU: 14 page faults
• FIFO: 15 page faults
• Optimal: 13 page faults