How to understand Clock-Pro algorithm?
Hi, every in LKML/linux-mm:
I have been read CLOCK-Pro paper since last week, and am going to
write one python demo.
After just read , I think I can understand it, however once I begin
implement it, I
found there are many point that not clear.
First, two important parameters Mc, Mh,
In that paper, it assume total memory size is M. (in number of page)
There is a formula:
M = Mc+Mh.
Mc, number of cold pages in memory,
Mh, number of hot pages in memory.
So, in clock list, we can keep track 2M page metadatas at most, we
may include M
non-resident pages.
In '4.3 operationes on searching vicim pages' , the authors said
"we keep track of the number of non-resident cold pages, Once the number
exceeds m the memory size in number of pages. we terminted the test period of the cold page pointed to by HAND-test."
My question is out:As this paper words, the number of cold page is
total of resident cold pages
and non-resident pages. It's the seem number of non-resident cold pages can not beyond M at all!
I also have more questions on CLOCK-Pro. but this question is most
doublt for me.
Any clear word is welcome. thank in advanced.
I suppose experience is more important than theory in
page-replacement field, is it right?
liyu
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>
Quoted 4 lines · liyu
My question is out:As this paper words, the number of cold page is
total of resident cold pages
and non-resident pages. It's the seem number of non-resident cold pages can not beyond M at all!
You are right. So the total number of pages (non-resident + resident) around the clock is no more than 2m
(m is the memory size in pages).
Quoted 4 lines
I also have more questions on CLOCK-Pro. but this question is most
doublt for me.
I am happy to help. I also have the clock-pro simulator that
almost exactly simulates what's described in the paper. Let me know if you want it.
Song Jiang
Quoted 10 lines
liyu
Quoted 5 lines
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>
Hi:
OOh, the original author here! Thanks a lot.
Let's assume Mn is the total number of non-resident pages in follow
words.
Nod, 'M=Mh+Mc' and 'Mc+Mn' < 2M are always true.
Have this implied that Mn is alway less than M? I think so.
but if "Once the number exceeds M the memory size in number of pages,
we terminted the test period of the cold page pointed to by HAND-test."
If Mn is alway less than M, when we move to HAND-test?
Or, my view have error.
I doublt on this, in fact.
Good luck.
Liyu
Song Jiang Wrote:
Quoted 46 lines · liyu
Quoted 8 lines
My question is out:As this paper words, the number of cold page is
total of resident cold pages
and non-resident pages. It's the seem number of non-resident cold pages can not beyond M at all!You are right. So the total number of pages (non-resident + resident) around the clock is no more than 2m (m is the memory size in pages).
Quoted 6 lines
I also have more questions on CLOCK-Pro. but this question is most
doublt for me.I am happy to help. I also have the clock-pro simulator that
almost exactly simulates what's described in the paper. Let me know if you want it.Song Jiang
Quoted 9 lines
liyu
Quoted 7 lines
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>
Quoted 9 lines
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>
Quoted 7 lines · liyu
Let's assume Mn is the total number of non-resident pages in follow
words.Nod, 'M=Mh+Mc' and 'Mc+Mn' < 2M are always true.
Have this implied that Mn is alway less than M? I think so.
Yes.
Quoted 5 lines
but if "Once the number exceeds M the memory size in number of pages,
we terminted the test period of the cold page pointed to by HAND-test."If Mn is alway less than M, when we move to HAND-test?
The algorithm tries to ensure that Mn <= M holds. Once Mn == M+1 is detected, run HAND-test to bring it back to Mn == M. That is, only during the transition period, Mn <= M might not hold, and we make a correction quickly.
So there is no contradiction here.
Song
Quoted 1 line
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>
Hi, All.
In my words, pages in memory is either resident or non-resident.
In linux internal, mapped or unmapped.
So number of non-resident pages is alway less than total number
of pages in memory.
Is your pages physics pages? or, it is Logical pages? However,
I think both is same here.
Waitting for your answer.
Thanks.
liyu
Song Jiang Wrote:
Quoted 23 lines · liyu
Quoted 11 lines
Let's assume Mn is the total number of non-resident pages in follow
words.Nod, 'M=Mh+Mc' and 'Mc+Mn' < 2M are always true.
Have this implied that Mn is alway less than M? I think so.
Yes.
Quoted 6 lines
but if "Once the number exceeds M the memory size in number of pages,
we terminted the test period of the cold page pointed to by HAND-test."If Mn is alway less than M, when we move to HAND-test?
Quoted 14 lines
The algorithm tries to ensure that Mn <= M holds. Once Mn == M+1 is detected, run HAND-test to bring it back to Mn == M. That is, only during the transition period, Mn <= M might not hold, and we make a correction quickly.
So there is no contradiction here.
Song
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>
Hi, All.
Quoted 2 lines
So number of non-resident pages is alway less than total number
of pages in memory.
More clearly. I think this condition can not be satisfied forever.
beacause
of number of non-residnent pages can not more than total number of memory pages.
But, I think there must have one or more errors in my words. But
where's bug?
Waitting for your answer.
Thanks.
liyu
Song Jiang Wrote:
Quoted 23 lines · liyu
Quoted 11 lines
Let's assume Mn is the total number of non-resident pages in follow
words.Nod, 'M=Mh+Mc' and 'Mc+Mn' < 2M are always true.
Have this implied that Mn is alway less than M? I think so.
Yes.
Quoted 6 lines
but if "Once the number exceeds M the memory size in number of pages,
we terminted the test period of the cold page pointed to by HAND-test."If Mn is alway less than M, when we move to HAND-test?
Quoted 14 lines
The algorithm tries to ensure that Mn <= M holds. Once Mn == M+1 is detected, run HAND-test to bring it back to Mn == M. That is, only during the transition period, Mn <= M might not hold, and we make a correction quickly.
So there is no contradiction here.
Song
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>