Problem with understanding: Software Implementation of LRU

[zak100]

Hi,

I am trying to understand the aging algorithm. I found the algorithm in the “Modern Operating Systems” book 4^th Edition.

Quote

Figure 3-17 illustrates how the modified algorithm, known as aging, works. Suppose that after the first clock tick the R bits for pages 0 to 5 have the values 1,  0, 1, 0, 1, and 1, respectively (page 0 is 1, page 1 is 0, page 2 is 1, etc.). In other words, between tick 0 and tick 1, pages 0, 2, 4, and 5 were referenced, setting their R bits to 1, while the other ones remained 0.

I am able to understand the above but I can't understand the following:

I can’t understand the following stuff:

Quote

 

After the six corresponding counters have been shifted and the R bit inserted at the left, they have the values shown in Fig. 3-17(a). The four remaining columns show the six counters after the next four clock ticks.

 

I think what it talks above happens in the row 0 which is my second figure, I have uploaded just the row correspond to Page 0:

 

Somebody please guide me about the working of the algorithm according to the figure.

 

Zulfi.

 

Edited May 8, 2020 by zak100

[zak100]

Hi,

Answer: I think it also works in the same way as LRU for hardware which is done with the help of matrix, software is done by keeping a counter for each page. For example, figure (a) tells us the bit pattern corresponding to each page. And we can choose  one of 1 or 3 at random to evict if the page fault occurs. In (e), we can choose either page3 or page 5 but we can prefer page 5 in the memory because it was referenced two clock cycles earlier.

 

Zulfi.