In this post we are discussing Consider the following page reference string [ 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1,2,0,1,7,0,1 ] Assuming there are 3 memory frames, how many page faults would occur in case of assuming there are 3 memory frames, i)LRU ii)Optimal algorithm note that initially all frames are empty.
Given page reference string: 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1
Number of memory frames (frames): 3
i) LRU Algorithm: In the LRU algorithm, we replace the page that has not been used for the longest time.
| String | 7 | 0 | 1 | 2 | 0 | 3 | 0 | 4 | 2 | 3 | 0 | 3 | 2 | 1 | 2 | 0 | 1 | 7 | 0 | 1 |
| Frame -1 | 7 | 7 | 7 | 2 | 2 | 2 | 2 | 4 | 4 | 4 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| Frame -2 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 3 | 3 | 3 | 3 | 3 | 3 | 0 | 0 | 0 | 0 | 0 | |
| Frame -3 | 1 | 1 | 1 | 3 | 3 | 3 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 7 | 7 | 7 | ||
| Fault (F) / Hit (H) | F | F | F | F | H | F | H | F | F | F | F | H | H | F | H | F | H | F | H | H |
The total number of page faults using the LRU algorithm is 12.
The total number of page Hits using the LRU algorithm is 8.
ii) Optimal Algorithm: In the Optimal algorithm, we replace the page that will not be used for the longest time in the future. This algorithm requires looking ahead in the page reference string to make replacement decisions.
| String | 7 | 0 | 1 | 2 | 0 | 3 | 0 | 4 | 2 | 3 | 0 | 3 | 2 | 1 | 2 | 0 | 1 | 7 | 0 | 1 |
| Frame -1 | 7 | 7 | 7 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 7 | 7 | 7 |
| Frame -2 | | 0 | 0 | 0 | 0 | 0 | 0 | 4 | 4 | 4 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| Frame -3 | | | 1 | 1 | 1 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| Fault (F) / Hit (H) | F | F | F | F | H | F | H | F | H | H | F | H | H | F | H | H | H | F | H | H |
The total number of page faults using the Optimal algorithm is 9.
The total number of page Hits using the Optimal algorithm is 11.