Galvin

Question

Assume that you have a page-reference string for a process with m frames (initially all empty). The page-reference string has length p; n distinct page numbers occur in it.Answer these questions for any page replacement algorithms:

a. What is a lower bound on the number of page faults?

b. What is an upper bound on the number of page faults?

Comments

Minimimum would be 'n' Page faults and maximum would be 'p' page faults.

Minimum is 'n'  because, each distinct page number has to be in frame, if there is a repeating page number, that may not be added to frame as it is already present.

Maximum is 'p' because, it might so happen that every page number in reference string is not present in any of the 'm' frames.

Please Correct me if iam wrong.

Answer 1

a) lower bound on the number of page faults:
 n when all pages in reference string must page in (given distinct page numbers)

b) upper bound on the number of page faults:
 p when every page in ref string causes a fault

Comments

@pawan kumarln

when there are total n distinct pages then how upper bound can have 'p' page faults?
Even if we probe for the first time there will be n misses but after that there will be no misses?

is the scope of getting pages >n? there can be more pages other than those n distinct pages?

@ayushsomani

Answer 2

"The page-reference string has length p; n distinct page numbers occur in it." It means, p references to pages with n of them being unique. Or p-n are repetitions.

So, the lower bound on the number of page fault = n (but we have to set n<m, else we may get more page faults than 'n') and

Upper Bound should be = P (but again we've to set m=1, else we may get less page faults than P)

Answer 3

1.Best Case:

When the number of distinct pages are 'n' which is less than the total number of available page frame 'm'.In this case there will be only n page faults.

So the minimum number of page faults will be n.

2.Worst case:

Let us assume that m=1 i.e there is only one page frame available.In this case all the p page references will create page faults.

So the maximum page faults will be p.