Consider the page reference string: 1, 0, 7,1,0, 2,1,2,3, 2, 4, 0, 3, 6, 2, 1 for a memory with 3 frames. Determine the number of page faults using FIFO. optimal and LRU
Given page reference string: 1, 0, 7,1,0, 2,1,2,3, 2, 4, 0, 3, 6, 2, 1
Number of memory frames (frames): 3
ii) FIFO Algorithm: In the FIFO algorithm, we replace the page that has fist in to frame.
| String | 1 | 0 | 7 | 1 | 0 | 2 | 1 | 2 | 3 | 2 | 4 | 0 | 3 | 6 | 2 | 1 |
| Frame -1 | 1 | 1 | 1 | 1 | 1 | 2 | 2 | 2 | 2 | 2 | 4 | 4 | 4 | 4 | 2 | 2 |
| Frame -2 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 1 | |
| Frame -3 | 7 | 7 | 7 | 7 | 7 | 7 | 3 | 3 | 3 | 3 | 3 | 6 | 6 | 6 | ||
| Fault (F) / Hit (H) | F | F | F | H | H | F | F | H | F | H | F | F | H | F | F | F |
The total number of page faults using the FIFO algorithm is 11.
The total number of page Hits using the FIFO algorithm is 5.
ii) LRU Algorithm: In the LRU algorithm, we replace the page that has not been used for the longest time.
| String | 1 | 0 | 7 | 1 | 0 | 2 | 1 | 2 | 3 | 2 | 4 | 0 | 3 | 6 | 2 | 1 |
| Frame -1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 4 | 4 | 4 | 6 | 6 | 6 |
| Frame -2 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 3 | 3 | 3 | 0 | 0 | 0 | 2 | 2 | |
| Frame -3 | 7 | 7 | 7 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 3 | 3 | 3 | 1 | ||
| Fault (F) / Hit (H) | F | F | F | H | H | F | H | H | F | H | F | F | F | F | F | F |
The total number of page faults using the LRU algorithm is 11.
The total number of page Hits using the LRU algorithm is 5.
iii) 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 | 1 | 0 | 7 | 1 | 0 | 2 | 1 | 2 | 3 | 2 | 4 | 0 | 3 | 6 | 2 | 1 |
| Frame -1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 1 |
| Frame -2 | | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| Frame -3 | | | 7 | 7 | 7 | 2 | 2 | 2 | 2 | 2 | 4 | 4 | 4 | 6 | 2 | 2 |
| Fault (F) / Hit (H) | F | F | F | H | H | F | H | H | F | H | F | H | H | F | F | F |
The total number of page faults using the Optimal algorithm is 9.
The total number of page Hits using the Optimal algorithm is 7.