The optimal algorithm gives 340 page faults(assuming 3 sequences from 1-100):

We have 20 frames containing 20 pages: 101, 102, 103, 104.....120. Since these pages are never referred again in future, we will replace them all. So, we now have 1, 2, 3, .... 17, 18, 19, 20 in the frames. 20 would not be used for the longest duration, so we remove 20 and load 21. Repeating this till we reach 100.

Now, we have 1, 2, 3,... 17, 18 , 19, 100. In second repetition we get 19 hits (for 1-19). Now 100 is needed in this repetition but 19 in next.

**(1, 2, 3, 4, .... 19, 20,.... 99, ***100* | 1, 2, 3,... *19*, 20, 100)

So removing 19 and loading 20^{th} page. At this instance main memory has

**1, 2, 3, .... 20, ... 99, 100**

20 is the best candidate to remove because it'd be needed later than the rest (like 1 , 2, 3...) in next iteration. So removing 20 and loading 21. Again to accommodate 22, 21 is best candidate to be removed. Repeating this process, we reach 100, which is already present in memory. So total hits become 20. Before the next repetition, main memory has

**1,** **2, 3, ...18, 99, 100**

At the beginning, there would be total 18 hits. Since we need 99 and 100 in this iteration, 18 shall be removed, followed by 19, 20.... till 98. So at the end, again we have 20 hits. In the third iteration too, 17 shall be replaced, 98, 99, 100 already found in main memory, summing up the total hits to 20. So total page faults with optimal algorithm are 100+(100-20)+(100-20)+(100-20)=340

This clearly is MRU or most recently used where the latest referred page gets removed. For eg, in first iteration, since 19 was referred last, we removed it. But the frames were not empty at the beginning. **Only optimal algorithm looks at the future demands and decides the best course, all the other algorithms make decisions based on previous entries.** Hence neither MRU nor LIFO would eliminate all the 20 entries 101, 102, .... 120.

In fact MRU and LIFO in such circumstances would yield same results because they would keep replacing the last entry and perform worst. Thus to answer, we must assume the frames as empty, in which case MRU would better LIFO (because LIFO would remove the last entered page such as 100, thus reducing hits by 1.)