Consider a main memory with five-page frames and the following sequence of page references: . Which one of the following is true with respect to page replacement policies First In First Out (FIFO) and Least Recently Used (LRU)?
View worked solution
Answer: A
To find the correct option, we trace the given page reference sequence with 5 page frames for both FIFO and LRU replacement policies.
Reference string: 3, 8, 2, 3, 9, 1, 6, 3, 8, 9, 3, 6, 2, 1, 3
1. First In First Out (FIFO)
FIFO replaces the page that has been in memory the longest.
| Ref | 3 | 8 | 2 | 3 | 9 | 1 | 6 | 3 | 8 | 9 | 3 | 6 | 2 | 1 | 3 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| F1 | 3 | 3 | 3 | 3 | 3 | 3 | 6 | 6 | 6 | 6 | 6 | 6 | 6 | 6 | 6 |
| F2 | 8 | 8 | 8 | 8 | 8 | 8 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | |
| F3 | 2 | 2 | 2 | 2 | 2 | 2 | 8 | 8 | 8 | 8 | 8 | 8 | 8 | ||
| F4 | 9 | 9 | 9 | 9 | 9 | 9 | 9 | 9 | 2 | 2 | 2 | ||||
| F5 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | |||||
| Fault | F | F | F | H | F | F | F | F | F | H | H | H | F | H | H |
Total FIFO Page Faults = 9
2. Least Recently Used (LRU)
LRU replaces the page that has not been used for the longest period of time.
| Ref | 3 | 8 | 2 | 3 | 9 | 1 | 6 | 3 | 8 | 9 | 3 | 6 | 2 | 1 | 3 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| F1 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 3 |
| F2 | 8 | 8 | 8 | 8 | 8 | 6 | 6 | 6 | 6 | 6 | 6 | 6 | 1 | 1 | |
| F3 | 2 | 2 | 2 | 2 | 2 | 2 | 8 | 8 | 8 | 8 | 8 | 8 | 8 | ||
| F4 | 9 | 9 | 9 | 9 | 9 | 9 | 9 | 9 | 2 | 2 | 2 | ||||
| F5 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | |||||
| Fault | F | F | F | H | F | F | F | H | F | H | H | H | F | F | H |
Total LRU Page Faults = 9
Both FIFO and LRU algorithms incur exactly 9 page faults for the given reference string.
Free practice · Your answers on this page are not saved.