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?
A
S1 is true, S2 is true
B
S1 is true, S2 is false
C
S1 is false, S2 is true
D
S1 is false, S2 is false
       Operating-Systems       Page-Replacement-Algorithm       GATE 2017 [Set-1]       Video-Explanation
Question 1 Explanation: 
FIFO may suffer from Belady's anomaly not always FIFO suffer from Belady's anomaly.
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 ___________.

A
1
B
2
C
3
D
4
       Operating-Systems       Page-Replacement-Algorithm       GATE 2016 [Set-1]       Video-Explanation
Question 2 Explanation: 
We have to calculate the difference between the last-in-first-out page replacement policy and the optimal page replacement policy.
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?

A
LRU (Least Recently Used)
B
OPT (Optimal Page Replacement)
C
MRU (Most Recently Used)
D
FIFO (First In First Out)
       Operating-Systems       Page-Replacement-Algorithm       GATE 2016 [Set-2]       Video-Explanation
Question 3 Explanation: 
To answer the question you have to know about Belady’s anomaly.
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)?

A
Both incur the same number of page faults
B
FIFO incurs 2 more page faults than LRU
C
LRU incurs 2 more page faults than FIFO
D
FIFO incurs 1 more page faults than LRU
       Operating-Systems       Page-Replacement-Algorithm       GATE 2015 [Set-1]
Question 4 Explanation: 

∴ 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__________.

A
7
B
8
C
9
D
10
       Operating-Systems       Page-Replacement-Algorithm       GATE 2014 [Set-1]
Question 5 Explanation: 

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?

A
Least-recently-used
B
First-in-first-out
C
Last-in-first-out
D
Most-recently-used
       Operating-Systems       Page-Replacement-Algorithm       GATE 2014 [Set-2]
Question 6 Explanation: 
The current status of 20 frames shows page numbers from 101 to 120. Implementation of optimal page replacement policy for above given page reference string would be as follows:

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
A
6
B
7
C
8
D
9
       Compiler-Design       Page-Replacement-Algorithm       GATE 2014 [Set-3]
Question 7 Explanation: 
6 page faults will occur using LRU.
Question 8

Which of the following page replacement algorithms suffers from Belady’s anamoly?

A
Optimal replacement
B
LRU
C
FIFO
D
Both (A) and (C)
       Operating-Systems       Page-Replacement-Algorithm       GATE 1995
Question 8 Explanation: 
FIFO is suffers from Belady's Anamoly.
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 
A
13
B
8
C
7
D
10
       Operating-Systems       Page-Replacement-Algorithm       GATE 1995
Question 9 Explanation: 
Page are fitted in frames, so first we need to determine the pages but given request are just the record request in decimal. We can assume that first page to address from 0000 to 0099 and page 2 contains records from 0100 to 0199 and so on (it is given in question that each page contains 100 records) and so on. So page request string is
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

A
LRU page replacement algorithm is used
B
FIFO page replacement algorithm is used
C
LFU page replacement algorithm is used
D
None of the above
       Operating-Systems       Page-Replacement-Algorithm       GATE 1994
Question 10 Explanation: 
In FIFO, whichever comes first that can be removed first. If the variable was initialized very early, it is in set of first pages. So it was removed.
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

A
either first fit or best fit policy (any one)
B
first fit but not best fit policy
C
best fit but first fit policy
D
None of the above
       Operating-Systems       Page-Replacement-Algorithm       GATE 1994
Question 11 Explanation: 
In first fit, block request will be satisfied from the first free block that fits it.
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

The following page addresses, in the given sequence, were generated by a program:

  1 2 3 4 1 3 5 2 1 5 4 3 2 3 

This program is run on a demand paged virtual memory system, with main memory size equal to 4 pages. Indicate the page references for which page faults occurs for the following page replacement algorithms.

 (a) LRU
 (b) FIFO 

Assume that the main memory is empty initially.

A
Theory Explanation.
       Operating-Systems       Page-Replacement-algorithm        GATE 1993
Question 13

Which page replacement policy sometimes leads to more page faults when size of memory is increased?

A
FIFO
       Operating-Systems       Page-Replacement-Algorithm       GATE 1992
Question 13 Explanation: 
FIFO, because it sometimes leads to more page faults when size of memory is increased.
Question 14

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?

A
4
B
5
C
6
D
7
       Operating-Systems       Page-Replacement-Algorithm       GATE 2004-IT
Question 14 Explanation: 
When 45 comes, the cache contents are:
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 15
Consider a demand paging system with four page frames (initially empty) and LRU page replacement policy. For the following page reference string
7, 2, 7, 3, 2, 5,3, 4, 6, 7, 7,1, 5, 6,1
the page fault rate, defined as the ratio of number of page faults to the number of memory accesses (rounded off to one decimal place) is_________.
A
0.60
       Operating-Systems       Page-Replacement-algorithm        GATE 2022       Video-Explanation
Question 15 Explanation: 
We have a total of 9 page faults using LRU page replacement algorithm with on demand paging. Out of 15 references, 9 page faults implies the page fault rate is 9/16 = 0.60.
Question 16
Determine the number of page faults when references to pages occur in order – 1, 2, 4, 5, 2, 1, 2, 4. Assume that the main memory can accommodate 3 pages and the main memory already has the pages 1 and 2, with page 1 having brought earlier than page 2.(assume LRU algorithm is used)
A
3
B
4
C
5
D
None of these
       Operating-Systems       Page-Replacement-algorithm        ISRO-2018       Video-Explanation
Question 16 Explanation: 
Page fault table is

The main memory already has the pages 1 and 2, with page 1 having brought earlier than page 2. So, total 6 page faults. 6-2=4
Question 17
Given the reference to the following pages by a program 0, 9, 0, 1, 8, 1, 8, 7, 8, 7, 1, 2, 8, 2, 7, 8, 2, 3, 8, 3 How many page faults will occur if the program has three-page frames available to it and uses an optimal replacement?
A
7
B
8
C
9
D
None of these
       Operating-Systems       Page-Replacement-algorithm        ISRO-2017 May
Question 17 Explanation: 
Optimal page replacement: Replace the page that will not be used for the longest period of time.

Note: Total 7-page faults will occur.
Question 18
The page replacement algorithm which gives the lowest page fault rate is
A
LRU
B
FIFO
C
Optimal page replacement
D
Second chance algorithm
       Operating-Systems       Page-Replacement-algorithm        ISRO CS 2008
Question 18 Explanation: 
In Optimal Page replacement algorithm, pages are replaced which are not used for the longest duration of time in the future. This page replacement algorithm ensures the lowest page fault rate.
Question 19
Determine the number of page faults when references to pages occur in the following order: 1, 2, 4, 5, 2, 1, 2, 4 Assume that the main memory can accommodate 3 pages and the main memory already has the pages 1 and 2, with page one having brought earlier than page 2. (LRU page replacement algorithm is used)
A
3
B
5
C
4
D
None of these
       Operating-Systems       Page-Replacement-algorithm        ISRO-2016
Question 19 Explanation: 

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 20
In which one of the page replacement policies, Belady’s anomaly may occur?
A
FIFO
B
Optimal
C
LRU
D
MRU
       Operating-Systems       Page-Replacement-algorithm        ISRO-2016
Question 20 Explanation: 
→ 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.
→ 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 21

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?

A
{8,5,3,2,9,6}
B
{4,3,6,2,5}
C
{3,9,6,2,7}
D
{3,9,6,2,7}
       Operating-Systems       Page-Replacement-algorithm        ISRO CS 2013
Question 21 Explanation: 
Penultimate means in second last working set model.
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 22
A computer has 16 pages of virtual address space but the size of main memory is only four frames. Initially the memory is empty. A program references the virtual pages in the order 0, 2, 4, 5, 2, 4, 3, 11, 2, 10. How many page faults occur if LRU page replacement algorithm is used?
A
3
B
5
C
7
D
8
       Operating-Systems       Page-Replacement-algorithm        ISRO CS 2014
Question 22 Explanation: 
LRU Page Replacement Algorithm:
when a page fault occurs, throw out the page that has been unused for the longest time.
Question 23
The process of entering data into a storage location
A
causes variation in its address number
B
adds to the contents of the location
C
is called a readout operation
D
is destructive of previous contents
       Operating-Systems       Page-Replacement-algorithm       Nielit Scientist-C 2016 march
Question 23 Explanation: 
The process of entering data into a storage location is destructive of previous contents using memory management techniques. In paging we are using LRU for replacing existing data.
Question 24
Determine the number of page faults when references to pages occur in the following order:1,2,4,5,2,1,2,4. Assume that the main memory can accommodate 3 pages and the main memory already has the pages 1 and 2, with page 1 having been brought earlier than page 2.(LRU algorithm is used)
A
3
B
5
C
4
D
none of these
       Operating-Systems       Page-Replacement-algorithm        Nielit Scientist-B CS 2016 march
Question 24 Explanation: 

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 25
Working set(t,k) at an instant of time,t,is
A
The set of k future references that the operating system will make
B
The set of future references that the operating system will make in the next 'k' time units
C
The set of k references with high frequency
D
The set of pages that have been referenced in the last k time units
       Operating-Systems       Page-Replacement-algorithm        Nielit Scientist-B CS 2016 march
Question 25 Explanation: 
Working set defines the amount of memory that a process requires in a given time interval.
→ 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 26

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

A
6
B
4
C
3
D
5
       Operating-Systems       Page-Replacement-algorithm        UGC-NET CS 2018 DEC Paper-2
Question 26 Explanation: 

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 27
A virtual memory system uses FIFO page replacement policy and allocates a fixed number of frames to the process. Consider the following statements
M : Increasing the number of page frames allocated to a process sometimes increases the page fault rate
N : Some programs do not exhibit locality of reference
Which one of the following is true?
A
Both M and N are true and N is the reason for M
B
Both M and N are true and N is not the reason for M
C
Both M and N are false
D
M is false, but N is true
       Operating-Systems       Page-Replacement-algorithm        ISRO DEC 2017 22- Soon
Question 27 Explanation: 
→ FIFO suffers from Belady Anomaly.
→ Belady Anomaly states that when number of page frames. Increases then increase the page fault rate.
M is True:
→ Locality of reference states that it’s a phenomenon in which the same values of related storage locations are frequently accessed depending on the memory access pattern.
N is also True:
→ Q is not the reason for P, because Belady Anomaly not depends on the locality of reference.
Question 28
A system uses FIFO policy for page replacement. It has 4 page frames with no pages loaded to begin with. The system first accesses 50 distinct pages in some order and then accesses the same 50 pages in reverse order. How many page faults will occur?
A
96
B
100
C
97
D
92
       Operating-Systems       Page-Replacement-algorithm        ISRO DEC 2017 22- Soon
Question 28 Explanation: 
The first 100 accesses causes 100 page faults.
Page 1 …….. Page 100 causes 100 faults.
Now, when they are accesses in reverse order page 100, 99, 98, 97 are already present. So we get 96 page faults. So, total of 196 page faults.
Question 29
In which one of the following pages replacement policies, Belady's anomaly may occur?
A
FIFO
B
LRU
C
Optimal
D
MRU
       Operating-Systems       Page-Replacement-algorithm       Nielit Scientist-B CS 4-12-2016
Question 29 Explanation: 
● Bélády'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.
● 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 30
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 fram is recorded as follows. What is the number of page faults? 0100, 0200, 0430, 0499, 0510, 0530, 0560, 0120, 0220, 0240, 0260, 0320, 0370
A
15,4
B
6,4
C
7,2
D
4,6
       Operating-Systems       Page-Replacement-algorithm        Nielit Scientific Assistance IT 15-10-2017
Question 30 Explanation: 
→ Page are fitted in frames, so first we need to determine the pages but given request are just the record request in decimal. We can assume that first page to address from 0000 to 0099 and page 2 contains records from 0100 to 0199 and so on (it is given in question that each page contains 100 records) and so on. So page request string is
01, 02, 04, 04, 05, 05, 05, 01, 02, 02, 02, 03, 03.
Clearly 7 page faults.
Question 31
How many page faults occur in LRU page replacement algorithm for the given reference string, with four page frames
7,0,1,2,0,3,4,2,3,0,3,2,1,2,0,1
A
6
B
8
C
7
D
9
       Operating-Systems       Page-Replacement-algorithm        KVS 22-12-2018 Part-B
Question 31 Explanation: 
In the Least Recently Used (LRU) page replacement policy, the page that is used least recently will be replaced.

Question 32
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. 0100, 0200, 0430, 0499, 0510, 0530, 0560, 0120, 0220, 0240, 0260, 0320, 0370, What is the number of page faults?
A
15,4
B
6,4
C
7,2
D
4,6
       Operating-Systems       Page-Replacement-algorithm        Nielit Scientific Assistance CS 15-10-2017
Question 32 Explanation: 
Memory page numbers will be calculated by using corresponding to given address as follows
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 33

In page replacement, ‘adding more frames may cause more page faults’ is referred to as:

A
Thrashing
B
Belady’s anomaly
C
Banker’s anomaly
D
Ageing
       Operating-Systems       Page-Replacement-algorithm        JT(IT) 2016 PART-B Computer Science
Question 33 Explanation: 
In FIFO page replacement policy sometimes behaves differently. The abnormal behaviour is nothing but Belady’s anomaly. Belady’s anomaly is nothing but adding more frames may cause more page faults.
Question 34
Suppose there are six files F1, F2, F3, F4, F5, F6 with corresponding sizes 150 KB, 225KB,75 KB, 60 KB, 275 KB and 65 KB respectively. The files are to be stored on a sequential device in such a way that optimizes access time. In what order should the files be stored ?
A
F5, F2, F1, F3, F6, F4
B
F4, F6, F3, F1, F2, F5
C
F1, F2, F3, F4, F5, F6
D
F6, F5, F4, F3, F2, F1
       Operating-Systems       Page-Replacement-algorithm        UGC NET CS 2017 Nov- paper-2
Question 34 Explanation: 
Here, clearly mentioned that files are stored in sequential device. It is like optimal merge pattern. We want to get optimum access time, first sort all the files according to their sizes. For sorting it will take worst case O(nlogn) but will give optimal result. So, Option D is correct order.
Note: Merging files required m+n-1 comprisions
Question 35
Suppose that the virtual Address space has eight pages and physical memory with four page frames. If LRU page replacement algorithm is used, _____ number of page faults occur with the reference string. 0 2 1 3 5 4 6 3 7 4 7 3 3 5 5 3 1 1 1 7 2 3 4 1
A
11
B
12
C
10
D
9
E
None of the above
       Operating-Systems       Page-Replacement-algorithm        UGC NET CS 2016 Aug- paper-2
Question 35 Explanation: 

Total number of page frames are 13.
None: Actually they given options are wrong. Excluded for evaluation.
Question 36
Consider the reference string
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.
A
10, 9
B
9, 9
C
10, 10
D
9,10
       Operating-Systems       Page-Replacement-algorithm        UGC NET CS 2016 July- paper-2
Question 36 Explanation: 
FIFO page replacement algorithm with 3 page frames

FIFO page replacement algorithm with 3 page frames
Question 37
A LRU page replacement is used with four page frames and eight pages. How many page faults will occur with the reference string 0172327103 if the four frames are initially empty?
A
6
B
7
C
8
D
5
       Operating-Systems       Page-Replacement-algorithm        UGC NET CS 2015 Jun- paper-2
Question 37 Explanation: 
Question 38
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
A
6
B
4
C
3
D
5
       Operating-Systems       Page-Replacement-algorithm        UGC NET CS 2018-DEC Paper-2
Question 38 Explanation: 

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 39
Consider a virtual page reference string 1, 2, 3, 2, 4, 2, 5, 2, 3, 4. Suppose LRU page replacement algorithm is implemented with 3 page frames in main memory. Then the number of page faults are .
A
5
B
7
C
9
D
10
       Operating-Systems       Page-Replacement-algorithm        UGC NET CS 2018 JUNE Paper-2
Question 39 Explanation: 

So total number of page faults are 7.
Question 40
Consider the following page trace :
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
A
8
B
9
C
10
D
12
       Operating-Systems       Page-Replacement-algorithm        UGC NET CS 2012 June-Paper2
Question 40 Explanation: 

Total 10 page faults will happen.
Question 41
Determine the number of page faults when references to pages occur in the occur -1, 2, 4, 5, 2, 1, 2, 4. Assume that the main memory can accommodate 3 pages and the main memory already has the pages 1 and 2, with page 1 having been brought earlier than page 2. (Assume LRU algorithm is used)
A
3
B
5
C
4
D
none of the above
       Operating-Systems       Page-Replacement-algorithm        NIELIT Junior Teachnical Assistant_2016_march
Question 42
Which page replacement policy suffers from Belady’s anomaly ?
A
LRV
B
LFU
C
FIFO
D
OPTIMAL
       Operating-Systems       Page-Replacement-algorithm        UGC NET CS 2007 June-Paper-2
Question 42 Explanation: 
FIFO page replacement policy suffers from Belady’s anomaly.
Question 43
Consider a virtual page reference string 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1 Suppose a demand paged virtual memory system running on a computer system such that the main memory has 3 page frames. Then __________ page replacement algorithm has minimum number of page faults.
A
FIFO
B
LIFO
C
LRU
D
Optimal
       Operating-Systems       Page-Replacement-algorithm        UGC NET CS 2017 Nov- paper-3
Question 43 Explanation: 


Question 44
Consider the following page reference string :  1, 2, 3, 4, 2, 1, 5, 6, 2, 1, 2, 3, 7, 6, 3, 2, 1, 2, 3,6  Which of the following options, gives the correct number of page faults related to LRU,FIFO, and optimal page replacement algorithms respectively, assuming 05 page frames and all frames are initially empty ?
A
10, 14, 8
B
8, 10, 7
C
7, 10, 8
D
7, 10, 7
       Operating-Systems       Page-Replacement-algorithm        UGC NET CS 2016 Aug- paper-3
Question 44 Explanation: 


Question 45
Consider that a process has been allocated 3 frames and has a sequence of page referencing 1,2,1,3,7,4,5,6,3,1
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?
A
2
B
0
C
1
D
3
       Operating-Systems       Page-Replacement-algorithm        UGC NET June-2019 CS Paper-2
Question 45 Explanation: 

Question 46
Consider the following page reference string
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?
A
7
B
4
C
6
D
5
       Operating-Systems       Page-Replacement-algorithm        ISRO CS 2020       Video-Explanation
Question 46 Explanation: 
The minimum number of frames required are 6. If we use 4 frames or 5 frames, we get more than one-page fault using LRU page replacement algorithm.
Question 47
Which of the following page replacement algorithms results in minimum page fault frequency for a given number of frames?
A
LRU page replacement
B
FIFO page replacement
C
Optimal page replacement
D
Enhanced second chance algorithm
       Operating-Systems       Page-Replacement-algorithm        APPSC-2016-DL-CS
Question 47 Explanation: 
Optimal page replacement algorithm results in minimum page fault frequency because in this algorithm, OS replaces the page that will not be used for the longest period of time in future.
Question 48

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?

A
9
B
7
C
8
D
10
       Operating-Systems       Page-Replacement-algorithm        CIL 2020
Question 48 Explanation: 
The given page reference string is,
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 49

Which one from the following is a false statement about page replacement algorithm?

A
LRU page replacement algorithm uses the principle of locality of reference.
B
LRU page replacement algorithm does not posses the stack property.
C
Optimal page replacement algorithm is infeasible.
D
FIFO page replacement algorithm does not posses the stack property.
       Operating-Systems       Page-Replacement-algorithm        APPSC-2012-DL CA
Question 49 Explanation: 
S1 is true.
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.
Question 50
Consider a program that consists of 8 pages (from 0 to 7) and we have 4 page frames in the physical memory for the pages. The page reference string is : 1 2 3 2 5 6 3 4 6 3 7 3 1 5 3 6 3 4 2 4 3 4 5 1 The number of page faults in LRU and optimal page replacement algorithms are respectively (without including initial page faults to fill available page frames with pages) :
A
9 and 6
B
10 and 7
C
9 and 7
D
10 and 6
       Operating-Systems       Page-Replacement-algorithm        UGC NET CS 2014 June-paper-3
Question 50 Explanation: 
Question 51
Which of the following page replacement algorithms DOES NOT suffer from Belady's Anomaly?
A
First Come First Serve
B
LRU
C
Most Recently Used
D
None of the Above
       Operating-Systems       Page-Replacement-algorithm        HCU PHD CS MAY 2019
Question 51 Explanation: 
Generally, on increasing the number of frames to a process’ virtual memory, its execution becomes faster as less number of page faults occur. Sometimes the reverse happens, i.e. more number of page faults occur when more frames are allocated to a process. This most unexpected result is termed as Belady’s Anomaly.
Question 52
In an operating system, a process refers to 5 pages, A, B, C, D, E in the order : A, B, C, D, A, B, E, A, B, C, D, E. If the page replacement algorithm is FIFO, the number of page transfers with an empty internal store of 3 frames is :
A
8
B
10
C
9
D
7
       Operating-Systems       Page-Replacement-algorithm        HCU PHD CS MAY 2015
Question 52 Explanation: 
We have to use FIFO page replacement policy for the given sequence,
A, B, C, D, A, B, E, A, B, C, D, E
Question 53
Consider a hypothetical machine with 3 pages of physical memory, 5 pages of virtual memory, and < A,B,C,D,A,B,E,A,B,C,D,E,B,A,B> as the stream of page reference by an application. if P and Q are the number of page faults that the application would incur with FIFO and LRU page replacement algorithms respectively, then (P,Q)=____(Assuming enough space for storing 3 page frames)
A
(11,10)
B
(12,11)
C
(10,11)
D
(11,12)
       Operating-Systems       Page-Replacement-algorithm        UGC NET JRF November 2020 Paper-2
Question 53 Explanation: 
A, B, C, D, A, B, E, A, B, C, D, E, B, A, B
Question 54
Which of the following Page Replacement Algorithm suffers from the belady’s anomaly?
A
LRU
B
Optimal Page Replacement
C
FIFO
D
Both LRU and FIFO
       Operating-Systems       Page-Replacement-algorithm        NIC-NIELIT Scientist-B 2020
Question 54 Explanation: 
FIFO Page Replacement Algorithm suffers from the belady’s anomaly.
There are 54 questions to complete.