This set of Data Structures & Algorithms Multiple Choice Questions & Answers (MCQs) focuses on “Not Recently Used Algorithm (NRU)”.
1. Which page replacement strategy uses referenced bits and modified bits to replace the page?
a) First in first out
b) Least recently used algorithm
c) Not recently used algorithm
d) Optimal page replacement algorithm
View Answer
Explanation: The not recently used algorithm is one of the page replacement algorithms. Page replacement algorithms in operating systems are used to decide which page should be evicted to make room for the upcoming pages. Not recently used algorithm is a page replacement strategy that uses referenced bits and modified bits to replace the page.
2. Not recently used page replacement algorithm uses a counter.
a) True
b) False
View Answer
Explanation: The not frequently used algorithm is a page replacement algorithm that uses a counter to keep track of how frequently the page has been used. Here, the page which has the lowest count may be swapped out. The not recently used algorithm doesn’t use a counter, it uses only referenced bit and modified bit.
3. In the not recently used algorithm, what do the R bits and M bits refer to?
a) R – read/write, M – modified
b) R – not referenced, M – modified
c) R – read/write, M – not modified
d) R – referenced, M – not modified
View Answer
Explanation: After every memory reference, the bits are set by hardware but are cleared only by the software. The R bit is set when the page is referenced by performing read or write. M bit is set when the page is modified.
4. Consider the given page reference string 3, 1, 0, 2, 1, 5, 6, 2, 8, 6, 9, 1. How many page faults will occur if the program has 4-page frames available to it and it uses the not recently used algorithm?
a) 6
b) 7
c) 8
d) 9
View Answer
Explanation: All the slots are empty initially, 3 1 02 are allocated → 4 page faults. 1 is already present → 0 page fault. When 5 came, 3 wasn’t used recently, replace it → 1 page fault When 6 came, 0 wasn’t used recently, replace it → 1 page fault 2 is already present → 0 page fault When 8 came, 1 wasn’t used recently, replace it → 1 page fault 6 is already present → 0 page fault When 9 came, 5 wasn’t used recently, replace it → 1 page fault When 1 came, 2 wasn’t used recently, replace it → 1 page fault Hence, total 9 page faults.
5. In the not recently used algorithm, which page is to be replaced when the new page comes in?
a) Referenced, modified
b) Not referenced, not modified
c) Referenced, not modified
d) Not referenced, modified
View Answer
Explanation: Not recently used page replacement algorithm, as the name suggests, evicts the page that hasn’t been used recently. Whenever a page is referred, it is marked by setting a referenced bit. It randomly picks up the page from the lowest numbered nonempty class. Hence, the page which is not referenced and not modified will be replaced first.
6. Consider the given page reference string 2, 6, 1, 2, 0, 1, 5, 3. What will be the page fault rate, if the program has 3-page frames available to it and it uses the not recently used algorithm?
a) 1 / 2
b) 2 / 4
c) 3 / 4
d) 3 / 8
View Answer
Explanation: All the slots are empty initially, 2 6 1 are allocated →3 page faults. 2 is already present → 0 page fault. When 0 came, 6 wasn’t used recently, replace it → 1 page fault 1 is already present → 0 page fault When 5 came, 2 wasn’t used recently, replace it → 1 page fault When 3 came, 0 wasn’t used recently, replace it → 1 page fault Total 9 page faults. Now, page fault rate = page fault / total pages = 6 / 8 = 3 / 4.
7. The page which is referenced and not modified is less important than the page which is modified but not referenced.
a) True
b) False
View Answer
Explanation: In the not recently used algorithm, instead of removing the page that is recently used, we remove a modified page, which is not referenced in one clock tick. Hence, a page that is referenced and not modified is more important than the page which is modified but not referenced.
8. Which among the following is a disadvantage of the not recently used algorithm?
a) Implementation is complex
b) It uses a queue data structure for implementation
c) Time consuming
d) It cannot be implemented
View Answer
Explanation: In the not recently used algorithm to decide which page is to be evicted when the new page comes in, we have to scan through the reference bits and modified bits. Hence, the performance is not that good, as it takes time to classify.
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.
- Check Programming Books
- Practice Data Structure MCQ
- Practice Programming MCQs
- Check Computer Science Books
- Check Design and Analysis of Algorithms Books
