Page-Replacement-algorithm
Question 1 |
Recall that Belady’s anomaly is that the page-fault rate may increase as the number of allocated frames increases. Now, consider the following statements:
-
S1: Random page replacement algorithm (where a page chosen at random is replaced) suffers from Belady’s anomaly
S2: LRU page replacement algorithm suffers from Belady’s anomaly
Which of the following is CORRECT?
S1 is true, S2 is true | |
S1 is true, S2 is false | |
S1 is false, S2 is true | |
S1 is false, S2 is false |
Page replacement algorithm suffers from Belady's anomaly when it is not a stack algorithm.
S1: Random page replacement algorithm is not a stack algorithm. So, S1 is true.
S2: LRU is a stack algorithm. Therefore, it doesn't suffer from Belady's anomaly. S2 is false.
Question 2 |
Consider a computer system with ten physical page frames. The system is provided with an access sequence (a1,a2,…,a20,a1,a2,…,a20), where each ai is a distinct virtual page number. The difference in the number of page faults between the last-in-first-out page replacement policy and the optimal page replacement policy is ___________.
1 | |
2 | |
3 | |
4 |
First we can consider LIFO (Last In First Out) →
a1 to a10 will result in page faults = 10 page faults,
Then a11 will replace a10 (last in is a10), a12 replace a11 and ...till a20 = 10 page faults and a20 will be top of stack and a9…a1 are remained as such.
Then a1 to a9 are already there.
So, 0 page faults from a1 to a9.
a10 will replace a20, a11 will replace a10 and so on = So 11 page faults.
So total faults will be 10+10+11 = 31.
Second Optimal Page Replacement Policy →
a1 to a10 = 10 page faults,
a11 will replace a10 because among a1 to a10, a10 will be used later, a12 will replace a11 and so on = 10 page faults.
a20 will be top of stack and a9…a1 are remained as such.
a1 to a9 = 0 page fault. a10 will replace a1 because it will not be used afterwards and so on, a10 to a19 will have 10 page faults.
So no page fault for a20.
Total = 10+ 10 +10 = 30.
So the difference between LIFO - Optimal = 1
Question 3 |
In which one of the following page replacement algorithms it is possible for the page fault rate to increase even when the number of allocated frames increases?
LRU (Least Recently Used) | |
OPT (Optimal Page Replacement) | |
MRU (Most Recently Used) | |
FIFO (First In First Out) |
In Belady’s anomaly is the phenomenon in which increasing the number of page frames results in an increase in the number of page faults for certain memory access patterns proves that it is possible to have more page faults when increasing the number of page frames while using the First in First Out (FIFO) page replacement algorithm.
In some situations, FIFO page replacement gives more page faults when increasing the number of page frames.
Question 4 |
Consider a main memory with five page frames and the following sequence of page references: 3, 8, 2, 3, 9, 1, 6, 3, 8, 9, 3, 6, 2, 1, 3. Which one of the following is true with respect to page replacement policies First-In-First Out (FIFO) and Least Recently Used (LRU)?
Both incur the same number of page faults
| |
FIFO incurs 2 more page faults than LRU | |
LRU incurs 2 more page faults than FIFO | |
FIFO incurs 1 more page faults than LRU |

∴ Number of page faults = 9

∴ Number of page faults = 9
Question 5 |
Assume that there are 3 page frames which are initially empty. If the page reference string is 1, 2, 3, 4, 2, 1, 5, 3, 2, 4, 6, the number of page faults using the optimal replacement policy is__________.
7 | |
8 | |
9 | |
10 |

Total 7 faults are there.
Question 6 |
A computer has twenty physical page frames which contain pages numbered 101 through 120. Now a program accesses the pages numbered 1, 2, …, 100 in that order, and repeats the access sequence THRICE. Which one of the following page replacement policies experiences the same number of page faults as the optimal page replacement policy for this program?
Least-recently-used | |
First-in-first-out | |
Last-in-first-out | |
Most-recently-used |

So, there would be 300 page faults in total (each access 100 page faults). Also it is visible that every time a replacement is done for the page which is most recently referred as it will be least recently referred in future. So, for the given page reference string optimal page replacement policy is working same as most recently used policy and thus number of page faults will be same in both of them.
Question 7 |
A system uses 3 page frames for storing process pages in main memory. It uses the Least Recently Used (LRU) page replacement policy. Assume that all the page frames are initially empty. What is the total number of page faults that will occur while processing the page reference string given below?
4, 7, 6, 1, 7, 6, 1, 2, 7, 2
6 | |
7 | |
8 | |
9 |
Question 8 |
Which of the following page replacement algorithms suffers from Belady’s anamoly?
Optimal replacement | |
LRU | |
FIFO | |
Both (A) and (C) |
Question 9 |
The address sequence generated by tracing a particular program executing in a pure demand paging system with 100 records per page with 1 free main memory frame is recorded as follows. What is the number of page faults?
0100, 0200, 0430, 0499, 0510, 0530, 0560, 0120, 0220, 0240, 0260, 0320, 0370
13 | |
8 | |
7 | |
10 |
01, 02, 04, 04, 05, 05, 05, 01, 02, 02, 02, 03, 03.
Clearly 7 page faults.
Question 10 |
A memory page containing a heavily used variable that was initialized very early and is in constant use is removed when
LRU page replacement algorithm is used | |
FIFO page replacement algorithm is used | |
LFU page replacement algorithm is used | |
None of the above |
In LRU which can eliminate (or) removed which is least recently used.
In LFU the frequency of the page is more. So it is in constant use so cannot be replaced.
Question 11 |
Consider the following heap (figure) in which blank regions are not in use and hatched region are in use.

The sequence of requests for blocks of size 300, 25, 125, 50 can be satisfied if we use
either first fit or best fit policy (any one) | |
first fit but not best fit policy | |
best fit but first fit policy | |
None of the above |
So, request for 300 will be satisfied by 350 size block reducing the free size to 50.
Request for 25, satisfied by 125 size block, reducing it to 125.
Request for 125 satisfied by the 125 size block.
And request for 50 satisfied by 50 size block.
So, all requests can be satisfied.
In best fit strategy, a block request is satisfied by the smallest block in which can fit it. So, request for 300 will be satisfied by 350 size block reducing the free size to 50.
Request for 25, satisfied by 50 size block as its the smallest size that fits 25, reducing it to 25.
Request for 125, satisfied by 150 size block, reducing it to 25.
Now, request for 50 cannot be satisfied as the two 25 size blocks are not contiguous.
Question 12 |
Which page replacement policy sometimes leads to more page faults when size of memory is increased?
FIFO |
Question 13 |
Consider a fully associative cache with 8 cache blocks (numbered 0-7) and the following sequence of memory block requests:
4, 3, 25, 8, 19, 6, 25, 8, 16, 35, 45, 22, 8, 3, 16, 25, 7
If LRU replacement policy is used, which cache block will have memory block 7?
4 | |
5 | |
6 | |
7 |
4, 3, 25, 8, 19, 6, 16, 35
CPU array (first element being least recently used)
[4, 3, 19, 6, 25, 8, 16, 35]
So, 45 replaces 4.
45, 3, 25, 8, 19, 6, 16, 35 [3, 19, 6, 25, 8, 16, 35, 45]
Similarly, 22 replaces 3 to give,
45, 22, 25, 8, 19, 6, 16, 35 [19, 6, 25, 8, 16, 35, 45, 22]
8 hits in cache.
45, 22, 25, 8, 19, 6, 16, 35 [19, 6, 25, 16, 35, 45, 22, 8]
3 replaces 19,
45, 22, 25, 8, 3, 6, 16, 35 [6, 25, 16, 35, 45, 22, 8, 3]
16 and 25 hits in cache,
45, 22, 25, 8, 3, 6, 16, 35 [6, 35, 45, 22, 8, 3, 16, 25]
Finally, 7 replaces 6, which is in block 5.
Question 14 |
3 | |
4 | |
5 | |
None of these |

Question 15 |
7 | |
8 | |
9 | |
None of these |

Note: Total 7-page faults will occur.
Question 16 |
LRU | |
FIFO | |
Optimal page replacement | |
Second chance algorithm |
Question 17 |
3 | |
5 | |
4 | |
None of these |

Here, total 6 page faults but in question, they are clearly mentioned that the main memory already has the pages 1 and 2, with page one having brought earlier than page 2. It means 6-2=4.
Question 18 |
FIFO | |
Optimal | |
LRU | |
MRU |
→ This phenomenon is commonly experienced when using the first-in first-out (FIFO) page replacement algorithm.
→ In FIFO, the page fault may or may not increase as the page frames increase, but in Optimal and stack-based algorithms like LRU, as the page frames increase the page fault decreases.
Question 19 |
Consider the list of page references in the timeline as below:
9 6 2 3 4 4 4 4 3 4 4 2 5 8 6 8 5 5 3 2 3 3 9 6 2 7
What is the working set at the penultimate page reference if ∆ is 5?
{8,5,3,2,9,6} | |
{4,3,6,2,5} | |
{3,9,6,2,7} | |
{3,9,6,2,7} |
The set of pages that a process is currently using is called its working set. If the entire working set is in memory, the process will run without causing many faults until it moves into another execution phase (e.g., the next pass of the compiler).
Many paging systems try to keep track of each process' working set and make sure that it is in memory before letting the process run. This approach is called the working set model.. It is designed to greatly reduce the page fault rate.
Working sets are as below:
9 - {9}
6 - {9,6}
2 - {9,6,2}
3 - {9,6,2,3}
4 - {9,6,2,3,4}
4 - {6,2,3,4}
4 - {2,3,4}
4 - {3,4}
3 - {3,4}
4 - {3,4}
4 - {3,4}
2 - {3,4,2}
5 - {3,4,2,5}
8 - {2,4,5,8}
6 - {2,4,5,8,6}
8 - {2,5,8,6}
5 - {5,8,6}
5 - {5,8,6}
3 - {3,5,8,6}
2 - {2,3,5,8}
3 - {2,3,5}
9 - {2,3,9}
6 - {2,3,9,6}
2 - {3,9,6,2}
7 - {3,9,6,2,7}
Question 20 |
3 | |
5 | |
7 | |
8 |
when a page fault occurs, throw out the page that has been unused for the longest time.

Question 21 |
causes variation in its address number | |
adds to the contents of the location | |
is called a readout operation | |
is destructive of previous contents |
Question 22 |
3 | |
5 | |
4 | |
none of these |

Here, total 6 page faults but in question, they are clearly mentioned that the main memory already has the pages 1 and 2, with page one having brought earlier than page 2. It means 6-2=4.
Question 23 |
The set of k future references that the operating system will make | |
The set of future references that the operating system will make in the next 'k' time units | |
The set of k references with high frequency | |
The set of pages that have been referenced in the last k time units |
→ It defines “the working set of information W(t,τ) of a process at time t to be the collection of information referenced by the process during the process time interval (t−τ,t)”.
→ Typically the units of information in question are considered to be memory pages. This is suggested to be an approximation of the set of pages that the process will access in the future (say during the next τ time units), and more specifically is suggested to be an indication of what pages ought to be kept in main memory to allow most progress to be made in the execution of that process.
Question 24 |
Suppose for a process P, reference to pages in order are 1, 2, 4, 5, 2, 1, 2, 4. Assume that main memory can accommodate 3 pages and the main memory has already pages 1 and 2 in the order 1 - first, 2- second. At this moment, assume FIFO Page Replacement Algorithm is used then the number of page faults that occur to complete the execution of process P is
6 | |
4 | |
3 | |
5 |

In this problem, they are mentioned that “main memory has already pages 1 and 2 in the order 1 - first, 2- second”. So, total page faults are 7-already 2 available.
= 7 - 2
= 5
Question 25 |
FIFO | |
LRU | |
Optimal | |
MRU |
● This phenomenon is commonly experienced when using the first-in first-out (FIFO) page replacement algorithm.
● In FIFO, the page fault may or may not increase as the page frames increase, but in Optimal and stack-based algorithms like LRU, as the page frames increase the page fault decreases.
Question 26 |
15,4 | |
6,4 | |
7,2 | |
4,6 |
01, 02, 04, 04, 05, 05, 05, 01, 02, 02, 02, 03, 03.
Clearly 7 page faults.
Question 27 |
7,0,1,2,0,3,4,2,3,0,3,2,1,2,0,1
6 | |
8 | |
7 | |
9 |

Question 28 |
15,4 | |
6,4 | |
7,2 | |
4,6 |
The page number is 1 from the record numbers 1-100,
The page number is 2 from the record numbers 101 -200
The page number is 3 from the record numbers 201 -300
The page number is 4 from the record numbers 301 -400
The page number is 5 from the record numbers 401 -500
The page number is 6 from the record numbers 501 -600
The page number is 7 from the record numbers 601 -700
For a given address sequence 0100, 0200, 0430, 0499, 0510, 0530, 0560, 0120, 0220, 0240,0260, 0320, 0370
The page number numbers sequence is 1,2,5,5,6,6,6,2,3,3,3,4,4
The number of available frame is 1, So we need to use only one frame for executing demand page process.

So total number of page faults are 7.
Question 29 |
In page replacement, ‘adding more frames may cause more page faults’ is referred to as:
Thrashing
| |
Belady’s anomaly
| |
Banker’s anomaly
| |
Ageing |
Question 30 |
F5, F2, F1, F3, F6, F4 | |
F4, F6, F3, F1, F2, F5 | |
F1, F2, F3, F4, F5, F6 | |
F6, F5, F4, F3, F2, F1 |
Note: Merging files required m+n-1 comprisions
Question 31 |
11 | |
12 | |
10 | |
9 | |
None of the above |

Total number of page frames are 13.
None: Actually they given options are wrong. Excluded for evaluation.
Question 32 |
0 1 2 3 0 1 4 0 1 2 3 4
If FIFO page replacement algorithm is used, then the number of page faults with three page frames and four page frames are _______ and ______ respectively.
10, 9 | |
9, 9 | |
10, 10 | |
9,10 |

FIFO page replacement algorithm with 3 page frames

Question 33 |
6 | |
7 | |
8 | |
5 |

Question 34 |
6 | |
4 | |
3 | |
5 |

In this problem, they are mentioned that “main memory has already pages 1 and 2 in the order 1 - first, 2- second”. So total page faults are 7-already 2 available.
=7-2
=5
Question 35 |
5 | |
7 | |
9 | |
10 |

So total number of page faults are 7.
Question 36 |
4,3, 2, 1, 4, 3, 5, 4, 3, 2, 1, 5
Percentage of page fault that would occur if FIFO page replacement algorithm is used with number of frames for the JOB m = 4 will be
8 | |
9 | |
10 | |
12 |

Total 10 page faults will happen.
Question 37 |
3 | |
5 | |
4 | |
none of the above |
Question 38 |
LRV | |
LFU | |
FIFO | |
OPTIMAL |
Question 39 |
FIFO | |
LIFO | |
LRU | |
Optimal |


Question 40 |
10, 14, 8 | |
8, 10, 7 | |
7, 10, 8 | |
7, 10, 7 |


Question 41 |
What shall be the difference i page faults for the above string using the algorithm of LRU and Optimal page replacement for referencing the string?
2 | |
0 | |
1 | |
3 |

Question 42 |
1 2 3 4 2 1 5 6 2 1 2 3 7 6 3 2 1 2 3 6
What are the minimum number of frames required to get a single page fault for the above sequence assuming LRU replacement strategy?
7 | |
4 | |
6 | |
5 |
Question 43 |
LRU page replacement | |
FIFO page replacement | |
Optimal page replacement | |
Enhanced second chance algorithm |
Question 44 |
What is the number of page faults by least recently used page replacement for a memory with 4 frames for the page reference string 2, 0, 1, 2, 4, 0, 5, 1, 4, 6, 4, 2, 1, 3, 0?
9 | |
7 | |
8 | |
10 |
2, 0, 1, 2, 4, 0, 5, 1, 4, 6, 4, 2, 1, 3, 0
In the least recently used page replacement algorithm, whenever there is page fault then the least recently used page will be replaced.

So, 10 page faults are there.
Question 45 |
Which one from the following is a false statement about page replacement algorithm?
LRU page replacement algorithm uses the principle of locality of reference. | |
LRU page replacement algorithm does not posses the stack property.
| |
Optimal page replacement algorithm is infeasible.
| |
FIFO page replacement algorithm does not posses the stack property. |
S2 is false,because LRU page replacement algorithm possess the stack property.
S3 is true because Optimal page replacement is infeasible because the virtual memory handler does not have knowledge of the future reference. It is just used to evaluate the performance with other algorithms for comparison.
S4 is true thats why FIFO suffers from anomaly called belady's anamoly.