# GATE2014-2-33

14.5k views

A computer has twenty physical page frames which contain pages numbered $101$ through $120$. Now a program accesses the pages numbered $\text{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?

1. Least-recently-used
2. First-in-first-out
3. Last-in-first-out
4. Most-recently-used

edited
3
Why we can't consider Last In First Out ?

Each time it will replace the most recent frame only like MRU, so how option D is more appropriate than option C ?
2

1
How  many Page fault will occur?
4

I think there would be

Optimal: 260-page fault

MRU: 260-page fault

LIFO: 262-page fault

NOTE (if reference string has 300-page request i.e 1 2 .... 100 1 2 .... 100 1 2 .... 100 and demand paging is used)

2
I think in MRU  when 1st page is arrived then it  replace  101 or any of 101 .....120 .Then when the 2nd page comes then it will replace 1St page ,,isnt as it is used most recent.Then how optimal page replacement algorithm is same as MRU . I think no option is correct.correct me if i am wrong.
0
what if in in the second round access is reverse means 100 to 1

then the answer for the same question would  be FIFO or not ?

0
I have the same doubt!
2

@Arjun sir, here all the answers have made the assumption that for MRU the pages 101 to 120 will be swaped out. Can we make assumptions like this in exam? Because in this case Optimal will not behave exactly like MRU, and the reason is the twenty pages that were already loaded. Please note here I have taken the sequence as 1,2,3,.....99,100,1,2,3......99,100,1,2,3.....99,100.

Please correct me if I am wrong, according to my calculations, in Optimal we will get 40/300 page hit rate, and in MRU we will get 0/300 Page Hit Rate.

I know MRU and Optimal work exactly same when the sequence is in a loop but in this question, the twenty frames are already loaded and that is what is making the difference.

Explanation: The optimal page replacement algorithm swaps out the page whose next use will occur farthest in the future.

In the given question, the computer has 20 page frames and initially page frames are filled with pages numbered from 101 to 120. Then program accesses the pages numbered 1, 2, …, 100 in that order, and repeats the access sequence THRICE.

The first 20 accesses to pages from 1 to 20 would definitely cause page fault. When 21st is accessed, there is another page fault. The page swapped out would be 20 because 20 is going to be accessed farthest in future. When 22nd is accessed, 21st is going to go out as it is going to be the farthest in future.

The above optimal page replacement algorithm actually works as most recently used in this case.

Iteration 1: (1-100) Not present – all replaced 1-20 in 20 frames, 21-100 in 20th frame. hence, page faults = 100

Iteration 2: (1-19) present | (20-99) NOT present | (100) present – the replacements are done at the 19th frame hence, page faults = 100 – 19 – 1 = 80

Iteration 3: (1-18) present | (19-98) NOT present | (99-100) present – the replacements are done at the 18th frame hence page faults = 100 – 18 – 2 = 80

Iteration 4: (1-17) present | (17-97) NOT present | (98-100) present – the replacements are done at the 17th frame hence page faults = 100 – 17 – 3 = 80

Total page faults = 100 + 80 + 80 +80 = 340

Along with generating same number of page faults M.R.U also generates replacements at the same positions as in the Optimal algorithm.(Assuming the given 101-120 pages are INVALID (not belonging to the same process) or Empty).

While the LIFO replacement does not behave like Optimal replacement algorithm as it generates 343 page faults. Because from 21st page all pages are placed in 20th frame, therefore hits per iteration reduces down to 19 from the 2nd iteration of pages. Whereby

Total Page faults = 100 + 81 + 81 + 81 = 343

101….120 are already loaded in 1…..20...by MRU we would end up replacing 20th frame(120) as this is most recently used..I dont think it will match Optimal Algo..

## Related questions

1
3.3k views
Assume that there are $3$ page frames which are initially empty. If the page reference string is $\text{1, 2, 3, 4, 2, 1, 5, 3, 2, 4, 6}$ the number of page faults using the optimal replacement policy is__________.
Consider the main memory system that consists of $8$ memory modules attached to the system bus, which is one word wide. When a write request is made, the bus is occupied for $100$ nanoseconds (ns) by the data, address, and control signals. During the same $100$ ns, ... be on the bus at any time. The maximum number of stores (of one word each) that can be initiated in $1$ millisecond is ________
Three processes $A$, $B$ and $C$ each execute a loop of $100$ iterations. In each iteration of the loop, a process performs a single computation that requires $t_c$ CPU milliseconds and then initiates a single I/O operation that lasts for $t_{io}$ ... uses a time slice of $50$ milliseconds. The time in milliseconds at which process C would complete its first I/O operation is ___________.
Consider the procedure below for the Producer-Consumer problem which uses semaphores: semaphore n = 0; semaphore s = 1; void producer() { while(true) { produce(); semWait(s); addToBuffer(); semSignal(s); semSignal(n); } } void consumer() { while(true) { semWait(s) ... semaphore s when the buffer is empty. The starting value for the semaphore $n$ must be $1$ and not $0$ for deadlock-free operation.