You have four physical pages of memory and eight virtual pages. All of the physical pages start out unallocated for any particular purpose. The virtual table of eight entries starts out with all the virtual pages being invalid.

That's the starting situation. One more detail may be useful here -- defining HOW new physical pages will be allocated. Given the results, I think it's clear that the allocation method starts out by allocating physical page 0, first. Then physical page 1. Etc. Once all the physical pages have been allocated at least once, this is when the LRU (least recently used) algorithm comes into play.

So that sets up the process.

One more thing might be useful to consider adding. This is how the LRU itself gets handled. Think of this as a stack of eaight cards. One card representing each virtual page. So let's call the cards: 0, 1, 2, 3, etc., for obvious reasons. The deck always has eight cards in it. Initially, the deck starts out as 01234567 (or any other order you like.) When allocating a new page, we always take the top card (which will be the left-most digit here) from the deck, use whatever physical page it indicates, and then place that card back at the bottom of the deck. So, for example, if we were to need a new physical page we'd go to this initial deck of "0123", pull the top card (which is "0"), allocate that physical page, then place that card back into the deck at the bottom. So the new deck would be "1230" after we were done with this step. Every time a physical page is accessed, we find its card in this deck and move it to the bottom, too.

To summarize the LRU deck: When we need a new physical page, we always take the top card and use whatever page is indicated by the value there and then move that card to the bottom of the deck. Whenever we access a physical page, we always find the card associated with that page and move it to the bottom of the deck.

That's it. I'll show the deck along with each step taken.

Now all you have to do is "act like the computer" and do the work by hand, running down the list of successive addresses in order. It's just simple hand work.

Each virtual address has a page and an offset. The offset value is the low-order 9 bits of the virtual address and the page is the upper 3 bits of the virtual address. The logic is as follows:

If the virtual table entry is invalid, then allocate a page from a list of free physical pages. But if there are no free physical pages left, then from a search of valid virtual table entries allocate the physical page from the virtual table entry holding the least recently used page. Also, in this case, mark the found virtual table entry as invalid because the physical page it owns is being re-allocated now. Then take this physical page and place it into the current virtual table entry and mark it as valid. Finally, pull this virtual table entry to the top of the LRU list, indicating it is very recently used.

If the virtual table entry is marked as valid, then pull this virtual table entry to the top of the LRU list, again indicating it is very recently used.

The above algorithm is repeated over and over for each of your virtual addresses, in sequence order. It ignores the details of forming the full 11-bit physical memory address. But I don't need to worry about that part of it, because your question isn't about that but instead about how that table got into the condition it was in. So I'm neglecting that detail to avoid excess detail here.

Here are the steps with your addresses, in order:

$$ \begin{array}{lrllll} \underline{\textrm{Step}} & {\underline{~~~~~~~~~~~~~~~~~~~~\textrm{Action}~~}} & \underline{\textrm{Free}} & \underline{\textrm{LRU}} & \underline{\textrm{Valid}~~~~~~~~~~~} & \underline{\textrm{Frame}~~~~} \\ & & 0123 & & \textrm{FFFFFFFF} & \textrm{oooooooo} \\ & \textbf{new address 1:265} & & & & \\ (1) & alloc = free & 123 & & \textrm{FFFFFFFF} & \textrm{oooooooo} \\ (2) & frame_1 = alloc & 123 & & \textrm{FFFFFFFF} & \textrm{o0oooooo} \\ (3) & valid_1 = true & 123 & & \textrm{FTFFFFFF} & \textrm{o0oooooo} \\ (4) & LRU(1) & 123 & 1 & \textrm{FTFFFFFF} & \textrm{o0oooooo} \\ & \textbf{new address 3:511} & & & & \\ (1) & alloc = free & 23 & 1 & \textrm{FTFFFFFF} & \textrm{o0oooooo} \\ (2) & frame_3 = alloc & 23 & 1 & \textrm{FTFFFFFF} & \textrm{o0o1oooo} \\ (3) & valid_3 = true & 23 & 1 & \textrm{FTFTFFFF} & \textrm{o0o1oooo} \\ (4) & LRU(3) & 23 & 31 & \textrm{FTFTFFFF} & \textrm{o0o1oooo} \\ & \textbf{new address 2:175} & & & & \\ (1) & alloc = free & 3 & 31 & \textrm{FTFTFFFF} & \textrm{o0o1oooo} \\ (2) & frame_2 = alloc & 3 & 31 & \textrm{FTFTFFFF} & \textrm{o021oooo} \\ (3) & valid_2 = true & 3 & 31 & \textrm{FTTTFFFF} & \textrm{o021oooo} \\ (4) & LRU(2) & 3 & 231 & \textrm{FTTTFFFF} & \textrm{o021oooo} \\ & \textbf{new address 2:76} & & & & \\ (4) & LRU(2) & 3 & 231 & \textrm{FTTTFFFF} & \textrm{o021oooo} \\ & \textbf{new address 1:34} & & & & \\ (4) & LRU(1) & 3 & 123 & \textrm{FTTTFFFF} & \textrm{o021oooo} \\ & \textbf{new address 0:129} & & & & \\ (1) & alloc = free & & 123 & \textrm{FTTTFFFF} & \textrm{o0o1oooo} \\ (2) & frame_0 = alloc & & 123 & \textrm{FTTTFFFF} & \textrm{3021oooo} \\ (3) & valid_0 = true & & 123 & \textrm{TTTTFFFF} & \textrm{3021oooo} \\ (4) & LRU(0) & & 0123 & \textrm{TTTTFFFF} & \textrm{3021oooo} \\ & \textbf{new address 6:129} & & & & \\ (1) & alloc = frame_{LRU} & & 012 & \textrm{TTTFFFFF} & \textrm{3021oooo} \\ (2) & frame_6 = alloc & & 012 & \textrm{TTTFFFFF} & \textrm{3021oo1o} \\ (3) & valid_6 = true & & 012 & \textrm{TTTFFFTF} & \textrm{3021oo1o} \\ (4) & LRU(6) & & 6012 & \textrm{TTTFFFTF} & \textrm{3021oo1o} \\ \end{array} $$

You should be able to match up the last entry above with your table, I think. The only trick here is to note that the LRU virtual table entry is '3' but the physical page owned by that virtual table entry is physical page '1'. The virtual table entry for '3' is marked false, but the alloc variable is set to 1, since that is the physical page that was assigned there.