This set of Data Structures & Algorithms Multiple Choice Questions on “Optimal Page Replacement Algorithm”.
1. __________ has the lowest fault rate of all the page replacement algorithms. Answer: a 2. Optimal page replacement algorithm is also called as __________ Answer: c 3. In a optimal page replacement algorithm, when a page is to be replaced, which of the following pages is chosen? 4. A page that is not going to be used for the next 7 seconds will be swapped out over a page that is going to be used within the next 0.7 seconds. 5. Analysis of the optimal paging problem has been done through___________ Answer: b 6. Optimal page replacement algorithm is implemented in __________ Answer: b 7. Optimal page replacement algorithm is said to satisfy __________ Answer: b 8. In a stack algorithm, the set of pages in a k-frame memory is always a subset of pages in a __________ frame memory. Answer: c 9. When all software that runs on a system is known beforehand, optimal page replacement algorithm can be used in a general-purpose operating system. Answer: a 10. Consider a reference string 7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1 of frame size 3. Calculate the number of page faults using optimal page replacement algorithm. 11. Consider a reference string 7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1 of frame size 4. Calculate the number of page faults using optimal page replacement algorithm. Answer: c 12. Consider a reference string 1,2,3,2,1,5,2,1,6,2,5,6,3,1,3,6,1,2,4,3 of frame size 3. Calculate the number of page faults using optimal page replacement algorithm. Answer: c
a) Optimal page replacement algorithm
b) LRU replacement algorithm
c) FIFO
d) Counting based
Clarification: Optimal page replacement algorithm has the lowest fault rate as it has the knowledge of all the pages beforehand.
a) LIFO
b) NRU
c) Clairvoyant replacement algorithm
d) Page buffering
Clarification: Optimal page replacement algorithm is also called a Clairvoyant replacement algorithm or Belady’s optimal replacement algorithm.
a) Oldest page
b) Newest page
c) Frequently occurred page in the future
d) Not frequently occurred page in the future
Answer: d
Clarification: The page which doesn’t occur more frequently in the future is chosen to be replaced with the page in the frame.
a) True
b) False
Answer: a
Clarification: In an optimal page replacement algorithm, the page that is to be used later in the future is swapped out over a page that is to be used immediately.
a) Deterministic algorithm
b) Online algorithm
c) Euclid algorithm
d) Optimal algorithm
Clarification: Analysis of the optimal paging algorithm is done through an online algorithm. Efficiency is calculated through amortized analysis.
a) General-purpose operating system
b) Special-purpose operating system
c) In any kind of operating system
d) In Windows only
Clarification: Optimal page replacement algorithm is used in special-purpose operating system because it is impossible to compute time before which a page is used.
a) Online algorithm
b) Stack algorithm
c) Queue algorithm
d) Array algorithm
Clarification: Optimal page replacement algorithm is said to satisfy the stack algorithm. It is also called as inclusion property.
a) k-1
b) k
c) k+1
d) k(k+1)
Clarification: Stack algorithm is satisfied if the set of pages in a k-frame memory is always a subset of pages in a k+1 frame memory.
a) True
b) False
Clarification: The algorithm can be implemented in a general-purpose algorithm if the software is known beforehand and if it is amenable to the static analysis of the memory.
a) 10
b) 9
c) 8
d) 7
Answer: b
Clarification: For the given string, the number of page faults using optimal page replacement algorithm is 9. It is solved in the given diagram.
a) 7
b) 9
c) 8
d) 6
Clarification: For the given reference string, the number of page faults using optimal page replacement algorithm is said to be 8. It is solved in the given diagram.
a) 12
b) 16
c) 14
d) 15
Clarification: For the given reference string, the number of page faults using optimal page replacement algorithm is said to be 14.