Hardware Implementation of LRU: Can we know the evicted page and ...

[zak100]

Hi,

I am trying to understand the hardware implementation of LRU. I got its explanation from the following link:

LRU implementation using a Matrix

I can't understand can we use this technique to tell (i)which page has been evicted and (ii) which pages are in the memory

 

I have attached its image:

 

Somebody please guide me.

 

Zulfi.

[Strange]

6 hours ago, zak100 said:

I can't understand can we use this technique to tell (i)which page has been evicted and (ii) which pages are in the memory

No. You would need something else to keep track of that. This purely keeps track of the Least Recently Used page. (I have no idea, why it works. It looks like magic! But there is a probably a simple explanation of why it works.)

In case that diagram is not clear (their description is not very clear - I had read it twice), it is showing the state of matrix after each step; that is, after accessing each of the pages: 0 1 2 3 2 1 0 3 2 3

It would be clearer to see what is happening if you draw the table yourself (on paper or in a Word document) and work through their example. Fill all the cells with zero to start, then follow the algorithm for each of the pages above (as each page number is referenced, set all the bits of the corresponding row to 1 and all the bits of the corresponding column to 0). You should get the sequence shown in (a) to (i) above and you can confirm that the lowest number in the rows correspond to the lest recent page number.

[zak100]

Hi,

Thanks.

In figure (a) page 0 column is zero  and row is 1, so page 0 is in memory, in (b) page 1 column is 0 and its row is 1, so  page 1 is also in memory. In (c) page 2 row is 1 and column is zero so page 2 is also in memory. In (d) page 3 row is 1 and column is 0 , so page 3 is in memory. So we have 4 pages  in memory and the h/w is indicating this from figure (a) to (d).

 

I though at (e) we have to evict a page 2 but I think its not correct,  we are not evicting any page, we always have pages: 0, 1, 2, 3 and the matrix is telling us which is the least recently page.

At (e), page 0 is shown as the least recently used page because its row has the lowest binary value.

 

Thanks a lot. God bless you.

 

Zulfi.

Edited May 8, 2020 by zak100