This set of Data Structures & Algorithms Multiple Choice Questions & Answers (MCQs) focuses on “Random Page Replacement Algorithm”.
1. Which among the following algorithms can be used to decide which page should be replaced when the new page comes in?
a) Karatsuba algorithm
b) DSW algorithm
c) Page replacement algorithm
d) Aging algorithm
View Answer
Explanation: The page replacement algorithm in operating systems, is used to decide which page should be evicted when the new page comes in. The basic idea of these algorithms is to reduce the number of page faults that occur.
2. The random page replacement algorithm may suffer from Belady’s anomaly.
a) True
b) False
View Answer
Explanation: Belady’s anomaly depicts that with the increase in the number of page frames, the number of page faults also increases. It is in context with the FIFO page replacement policy. Since random page replacement algorithm replaces the page randomly, it may behave like FIFO and thus it may suffer from belady’s anomaly.
3. The random page replacement algorithm fares better than which of the following algorithm?
a) Optimal page replacement algorithm
b) LIFO
c) FIFO
d) Not frequently used algorithm
View Answer
Explanation: The random page replaces a page randomly from the frame. Here, we cannot predict the future at all. The best case, worst case and average case are all same for this algorithm. It is also easy to implement. Hence, it fares better than FIFO.
4. Consider the given page reference string 0, 1, 3, 7, 1, 7, 0, 3, 6, 8. How many page faults will occur if the program has 4-page frames available to it and it uses the random page replacement algorithm?
a) 6
b) 7
c) 8
d) 9
View Answer
Explanation: All the slots are empty initially, 0 1 3 7 are allocated → 4 page faults. 1 is already present → 0 page fault. 7 is already present → 0 page fault. 0 is already present → 0 page fault. 3 is already present → 0 page fault. When 6 came, randomly replace it with any of the page → 1 page fault. When 8 came, randomly replace it with any of the page → 1 page fault. Hence, total 6 page faults.
5. In the random page replacement algorithm, if the current page doesn’t exist in the frame then it is replaced with which of the following page?
a) Recently used page
b) Least recently used page
c) Any random page
d) The first page of the frame
View Answer
Explanation: In the random page replacement algorithm, as the name suggests replaces any random page from the set. Hence, if the current page doesn’t exist in the set, then it is replaced with any random page.
6. Consider the following pseudocode for the random page replacement algorithm. Which of the following best suits the blank?
Start traversing the pages
if pages < capacity
{
insert the pages until the size of the set reaches capacity or all the pages are processed
maintain the pages in a queue
increment page fault
}
else if
{
current page is present in the set
do nothing
}
else
{
replace the current page with __________
store current page in the queue
increment page fault
}
return page faultsa) any random page
b) recently used page
c) least recently used page
d) the first page of the frame
View Answer
Explanation: In the random page replacement algorithm, while traversing the pages, if the pages are less than the capacity, keep adding the pages until the set reaches the capacity. Increment the page fault. If the current page is present in the set, gives 0 page fault. Hence, do nothing, else replace the page randomly with any page of the set and increment the page fault.
7. Random page replacement algorithm may behave like any other page replacement algorithms.
a) True
b) False
View Answer
Explanation: In the random page replacement algorithm, if the page doesn’t exist in the set then it is replaced by any of the pages from the set. Hence, it may behave like FIFO, LIFO, LRU, Optimal, etc. any of the page replacement algorithm.
8. Which of the following is a characteristic of random page replacement algorithm?
a) It replaces the page that has been present in the main memory for the longest
b) It uses a queue data structure for implementation
c) It eliminates the overhead cost of tracking page reference
d) It cannot be implemented
View Answer
Explanation: In FIFO page replacement algorithm, the page that has been in the memory for the longest amount of time is replaced and it uses queue data structure for implementation. Optimal page replacement algorithm cannot be implemented because the future cannot be predicted. In random page replacement algorithm, the memory page is replaced randomly and hence we do not need to track the page reference.
Sanfoundry Global Education & Learning Series – Data Structures & Algorithms.
To practice all areas of Data Structures & Algorithms, here is complete set of 1000+ Multiple Choice Questions and Answers.
If you find a mistake in question / option / answer, kindly take a screenshot and email to [email protected]
- Practice Data Structure MCQ
- Check Computer Science Books
- Apply for Computer Science Internship
- Practice Computer Science MCQs
- Check Design and Analysis of Algorithms Books
