4,200 views
2 votes
2 votes
Consider the following passage to answer questions from Q. Nos. 1 to 6 :
Virtual Memory is a technique that allows the execution of processes that may
not be completely in the memory. In this system of over-allocation, while a
user process is executing, a page fault occurs. The operating system determines
where the desired page is in the memory, but then finds that there are no
free frames. In that case, it finds a victim page to be swapped out, thereby
making a frame free for the desired page to be swapped in. For this, there
are many different page-replacement algorithms. FIFO Page Replacement, LRU
Page Replacement, Optimal Page Replacements, etc. are some of the known
algorithms. The basic objective of page-replacement algorithms is to minimize
the number of page faults. We can do this minimization by distributing heavily-
used pages evenly over all of memory, rather than having them compete for
a small number of page frames. We can also associate with each page frame
a counter of the number of pages that are associated with that frame. Then,
to replace a page, we search for the page frame with the smallest counter. We
may consider such a customized page-replacement algorithm, known as “Best
CBPR Algorithm” defined as under :
“The initial value of the counter for each page frame is 0. The counter is
incremented whenever a new page is associated with that frame and the counter
is decremented whenever one of the pages associated with that frame is no longer
required. In order to replace a page, the frame with the smallest counter value
is selected. In case of a tie. FIFO is used to break the tie.”
In general, for a process with m frames (initially all empty) assume a page
reference string of length p, with n distinct page numbers occurring in it.

1. What is a lower bound on the number of page faults ?
(A) p page faults         (B) n page faults
(C) m page faults        (D) p/m page faults

2. What is an upper bound on the number of page faults ?
(A) n page faults         (B) n * m page faults
(C) p page faults         (D) p/m page faults

3. Suppose that for a particular process under execution, the following page reference
string is encountered :
1, 2, 3, 4, 5, 3, 4, 1, 6, 7, 8, 7, 8, 9, 7, 8, 9, 5, 4, 5, 4, 2.
 How many page faults occur for “FIFO Page Replacement Algorithm” for the
above given page reference string for four frames ?
(A) 11 page faults      (B) 20 page faults
(C) 16 page faults      (D) 13 page faults

4. How many page faults occur for “LRU Page Replacement Algorithm” for the
above given page reference string for four frames ?
(A) 11 page faults     (B) 10 page faults
(C) 13 page faults     (D) 18 page faults

5. How many page faults occur for “Optimal Page Replacement Algorithm” for
the above given page reference string for four frames ?
(A) 11 page faults      (B) 13 page faults
(C) 15 page faults      (D) 17 page faults

6. How many page faults occur for “Best CBPR Algorithm” for the above given
page reference string for four frames ?
(A) 09 page faults      (B) 10 page faults
(C) 14 page faults      (D) 12 page faults

1 Answer

0 votes
0 votes
1-b

2-c

3-d

4-c

5-a

6-c

Related questions

0 votes
0 votes
0 answers
3
Harikesh Kumar asked Feb 3, 2018
256 views
There is any difference or same these two statement?1. Page fault service time is 10ms.2. The Time to service a page fault is on average 10ms.