Page-Replacement-algorithm

Question 1

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
Question 1 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 2

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
Question 2 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 3

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

A
Optimal replacement
B
LRU
C
FIFO
D
Both (A) and (C)
Question 3 Explanation: 
FIFO is suffers from Belady's Anamoly.
Question 4

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
Question 4 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 5

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.
Question 6

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

A
FIFO
Question 6 Explanation: 
FIFO, because it sometimes leads to more page faults when size of memory is increased.
Question 7

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
Question 7 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 8
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
Question 8 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 9

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
Question 9 Explanation: 

∴ Number of page faults = 9

∴ Number of page faults = 9
Question 10

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)
Question 10 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 11

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
Question 11 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 12
Which one or more of the following options guarantee that a computer system will transition from user mode to kernel mode?
A
Function Call
B
malloc Call
C
Page Fault
D
System Call
Question 13
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
Question 13 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 14

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
Question 14 Explanation: 

Total 7 faults are there.
There are 14 questions to complete.

Access quiz wise question and answers by becoming as a solutions adda PRO SUBSCRIBER with Ad-Free content

Register Now

If you have registered and made your payment please contact solutionsadda.in@gmail.com to get access