The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+2 votes
1.5k views
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
in Operating System by (489 points) | 1.5k views

1 Answer

0 votes
1-b

2-c

3-d

4-c

5-a

6-c
by (75 points)
0
pls provide some reference for this
+1
from where this ques taken?? Galvin?
0
pls clear  1 ,2 and 6 point.i also checked ,but it is not mention in galvin
0
How to implement “Best CBPR Algorithm” ?
0
How have you done it.?

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
49,845 questions
54,787 answers
189,449 comments
80,542 users