Page faults and LRU Algorithm

Question

A main memory can retain up to 4 pages. Which page will be the first one to get a page fault if LRU algorithm is used on the following pages that is in order?

1,2,3,1,2,4,1,2,3

This is a test question which I thought there is no answer to. The main memory can have 4 pages retained, and since there are pages 1,2,3,4, there shouldn't be a page fault occurring.

The answer is 4th page but I don't understand why.

Answer 1

The only way that seems to make sense is if the numbers in that sequence are the in-memory page numbers rather than the pages being retrieved from disk.

In other words, they are the page numbers that have been selected for loading a page into. This is (at least tacitly) supported by the phrase "if LRU algorithm is used on the following pages that is in order".

An LRU algorithm is used to select which page to toss out and re-use so, if it's selected page 1, then that would cause the page to be swapped out for replacement.

So the fourth page in this sense is:

1,2,3,1
      ^
      |
      +-- this one.

And, because the first in-memory page is already in use, a page fault occurs to bring in the new page to it.

I can't think of any other scenario that even comes close to matching that answer.

Answer 2

First '1' will be the first page fault because frames are empty in the starting, when '1' will be called for first time it will show page fault as frames are empty. And total page faults will be 4.

Answer 3

(even though post, I am just adding a few insights not described in other answers) LRU is implemented by Unix by maintaining a linked list of all pages. This list will have most recently used pages on front while least recently used pages on back (tail) As list is reorganized on every memory reference so last order of 4 pages is of our interest 4,1,2,3.

In the given sequence of pages, 4 is the least recently used page while 3 is the most recently used. so page 4 will be on the back of list. Any event, that cause purging of one of pages, will page out frame 4 as it is on back of list