Question

There are four page frames. Using the reference string listed, show the final contents of memory and the number of page faults for the page replacement strategies listed below. For the optimal strategy: if you have no way to make a choice otherwise, then use FIFO as a secondary strategy.

3 2 1 2 4 5 2 3 5 4 1 3 7 2 3
A. LRU
B. Optimal

Answer 1

The final contents of memory using the LRU strategy are provided along with the number of page faults. The optimal strategy is also explained, with the final contents of memory and the number of page faults.

Step-by-step explanation:

The final contents of memory using the LRU (Least Recently Used) page replacement strategy are as follows:

1. 3 - Page Fault
2. 3, 2
3. 3, 2, 1
4. 3, 2, 1, 4
5. 2, 1, 4, 5 - Page Fault
6. 1, 4, 5, 2 - Page Fault
7. 4, 5, 2, 3
8. 5, 2, 3, 1 - Page Fault
9. 2, 3, 1, 5
10. 3, 1, 5, 4
11. 1, 5, 4, 3
12. 5, 4, 3, 7 - Page Fault
13. 4, 3, 7, 2
14. 3, 7, 2, 1 - Page Fault

The total number of page faults using the LRU strategy is 8.

For the optimal page replacement strategy, we need to simulate the entire sequence of references and calculate the furthest future reference for each page in memory. If we have no way to make a choice otherwise, we will use the FIFO (First-In, First-Out) strategy. Here are the steps:

1. 3 - Page Fault (3)
2. 3, 2 - Page Fault (2)
3. 3, 2, 1 - Page Fault (1)
4. 3, 2, 1, 4 - Page Fault (4)
5. 5 - Page Fault (5)
6. 5, 2 - Page Fault (2)
7. 5, 2, 3 - Page Fault (3)
8. 5, 2, 3, 1 - Page Fault (1)
9. 5, 2, 3, 1, 4 - Page Fault (4)
10. 5, 2, 3, 1, 4, 7 - Page Fault (7)
11. 5, 2, 3 - Page Fault (3)
12. 5, 2, 3, 7 - Page Fault (7)
13. 5, 2, 3, 7, 2 - Page Fault (2)
14. 5, 2, 3, 7, 2, 1 - Page Fault (1)

The total number of page faults using the optimal strategy is 9.