Skip to contentSkip to conversation

How kernel applies LRU to swap out physical pages?

DISCUSSION Pan ruochen 3 participants 6 messages Nov 11, 2008 – Nov 12, 2008

lore
Share & tools
lore
#0 lore raw

Hi All,
I'm reading the linux kernel 2.6.14. But can't understand how LRU algorithm is applied to page swapping. what is the 'USED' of LRU referred to? The reference counter which the page is mapped by processes, or the frequency that CPU reads/writes in the page. In common sense, the LRU algorithm will be more optimal for the second case. But it depends on CPU capability.
I will be very appreciated if somebody can explain that in details.

-------------
Best Regards,
PRC
Nov 11, 2008

#1 lore raw
Quoted 7 lines · Pan ruochen

Hi All,
I'm reading the linux kernel 2.6.14. But can't understand how LRU algorithm is applied to page swapping. what is the 'USED' of LRU referred to? The reference counter which the page is mapped by processes, or the frequency that CPU reads/writes in the page. In common sense, the LRU algorithm will be more optimal for the second case. But it depends on CPU capability.
I will be very appreciated if somebody can explain that in details.

We don't actually use LRU but something like CLOCK.

#2 lore raw
Quoted 10 lines · Pan ruochen
Quoted 7 lines

Hi All,
I'm reading the linux kernel 2.6.14. But can't understand how LRU algorithm is applied to page swapping. what is the 'USED' of LRU referred to? The reference counter which the page is mapped by processes, or the frequency that CPU reads/writes in the page. In common sense, the LRU algorithm will be more optimal for the second case. But it depends on CPU capability.
I will be very appreciated if somebody can explain that in details.

We don't actually use LRU but something like CLOCK.

Yup.

However, VM replace algorithm folks commonly call it to "LRU" because MACH call so.

IOW, it is historical reason word, shouldn't imazine strict "Least Recently Used" algorithm.

#3 lore raw
Quoted 10 lines · KOSAKI Motohiro
Quoted 10 lines · Pan ruochen
Quoted 7 lines

Hi All,
I'm reading the linux kernel 2.6.14. But can't understand how LRU algorithm is applied to page swapping. what is the 'USED' of LRU referred to? The reference counter which the page is mapped by processes, or the frequency that CPU reads/writes in the page. In common sense, the LRU algorithm will be more optimal for the second case. But it depends on CPU capability.
I will be very appreciated if somebody can explain that in details.

We don't actually use LRU but something like CLOCK.

FWIW in case you hadn't found it yet:

http://en.wikipedia.org/wiki/Page_replacement_algorithm

is a fairly decent page on the subject.

#4 lore raw

Thanks to all, I've have a study.

2008/11/11 Peter Zijlstra <[email protected]>:

Quoted 18 lines · KOSAKI Motohiro
Quoted 10 lines
Quoted 10 lines · Pan ruochen
Quoted 7 lines

Hi All,
I'm reading the linux kernel 2.6.14. But can't understand how LRU algorithm is applied to page swapping. what is the 'USED' of LRU referred to? The reference counter which the page is mapped by processes, or the frequency that CPU reads/writes in the page. In common sense, the LRU algorithm will be more optimal for the second case. But it depends on CPU capability.
I will be very appreciated if somebody can explain that in details.

We don't actually use LRU but something like CLOCK.

FWIW in case you hadn't found it yet:

http://en.wikipedia.org/wiki/Page_replacement_algorithm

is a fairly decent page on the subject.

#5 lore raw
In reply to Pan ruochen

Hi

Quoted 2 lines

Hi All,
I'm reading the linux kernel 2.6.14.

it seems too old.
I recommend to read newest kernel.

Quoted 6 lines

But can't understand how LRU algorithm
is applied to page swapping. what is the 'USED' of LRU referred to? The reference counter which the page is mapped by processes, or the frequency that CPU reads/writes in the page. In common sense, the LRU algorithm will be more optimal for the second case. But it depends on CPU capability.
I will be very appreciated if somebody can explain that in details.

I recommend to read page_referenced() and its related function :)