* [Question] How to understand Clock-Pro algorithm?
@ 2005-09-20 3:11 liyu
2005-09-20 4:01 ` Song Jiang
0 siblings, 1 reply; 6+ messages in thread
From: liyu @ 2005-09-20 3:11 UTC (permalink / raw)
To: LKML, Linux-MM
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 majordomo@kvack.org. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>
^ permalink raw reply [flat|nested] 6+ messages in thread* Re: [Question] How to understand Clock-Pro algorithm?
2005-09-20 3:11 [Question] How to understand Clock-Pro algorithm? liyu
@ 2005-09-20 4:01 ` Song Jiang
2005-09-20 5:02 ` liyu
0 siblings, 1 reply; 6+ messages in thread
From: Song Jiang @ 2005-09-20 4:01 UTC (permalink / raw)
To: liyu; +Cc: LKML, Linux-MM
On Mon, 2005-09-19 at 21:11, liyu wrote:
> 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).
>
> 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
>
> liyu
>
>
>
>
>
>
>
>
> --
> To unsubscribe, send a message with 'unsubscribe linux-mm' in
> the body to majordomo@kvack.org. For more info on Linux MM,
> see: http://www.linux-mm.org/ .
> Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>
^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: [Question] How to understand Clock-Pro algorithm?
2005-09-20 4:01 ` Song Jiang
@ 2005-09-20 5:02 ` liyu
2005-09-20 5:16 ` Song Jiang
0 siblings, 1 reply; 6+ messages in thread
From: liyu @ 2005-09-20 5:02 UTC (permalink / raw)
To: Song Jiang; +Cc: LKML, Linux-MM
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:
>On Mon, 2005-09-19 at 21:11, liyu wrote:
>
>
>
>> 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).
>
>
>
>>
>> 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
>
>
>
>>liyu
>>
>>
>>
>>
>>
>>
>>
>>
>>--
>>To unsubscribe, send a message with 'unsubscribe linux-mm' in
>>the body to majordomo@kvack.org. For more info on Linux MM,
>>see: http://www.linux-mm.org/ .
>>Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>
>>
>>
>
>--
>To unsubscribe, send a message with 'unsubscribe linux-mm' in
>the body to majordomo@kvack.org. For more info on Linux MM,
>see: http://www.linux-mm.org/ .
>Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>
>
>
>
>
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>
^ permalink raw reply [flat|nested] 6+ messages in thread* Re: [Question] How to understand Clock-Pro algorithm?
2005-09-20 5:02 ` liyu
@ 2005-09-20 5:16 ` Song Jiang
2005-09-20 5:28 ` liyu
2005-09-20 6:01 ` liyu
0 siblings, 2 replies; 6+ messages in thread
From: Song Jiang @ 2005-09-20 5:16 UTC (permalink / raw)
To: liyu; +Cc: LKML, Linux-MM
On Mon, 2005-09-19 at 23:02, liyu wrote:
>
> 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.
>
> 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
>
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>
^ permalink raw reply [flat|nested] 6+ messages in thread* Re: [Question] How to understand Clock-Pro algorithm?
2005-09-20 5:16 ` Song Jiang
@ 2005-09-20 5:28 ` liyu
2005-09-20 6:01 ` liyu
1 sibling, 0 replies; 6+ messages in thread
From: liyu @ 2005-09-20 5:28 UTC (permalink / raw)
To: Song Jiang; +Cc: LKML, Linux-MM
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:
>On Mon, 2005-09-19 at 23:02, liyu wrote:
>
>
>
>> 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.
>
>
>
>> 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
>
>
>
>
>
>
>
>
>
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>
^ permalink raw reply [flat|nested] 6+ messages in thread* Re: [Question] How to understand Clock-Pro algorithm?
2005-09-20 5:16 ` Song Jiang
2005-09-20 5:28 ` liyu
@ 2005-09-20 6:01 ` liyu
1 sibling, 0 replies; 6+ messages in thread
From: liyu @ 2005-09-20 6:01 UTC (permalink / raw)
To: Song Jiang; +Cc: Linux-MM
Hi, All.
> 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:
>On Mon, 2005-09-19 at 23:02, liyu wrote:
>
>
>
>> 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.
>
>
>
>> 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
>
>
>
>
>
>
>
>
>
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>
^ permalink raw reply [flat|nested] 6+ messages in thread
end of thread, other threads:[~2005-09-20 6:01 UTC | newest]
Thread overview: 6+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2005-09-20 3:11 [Question] How to understand Clock-Pro algorithm? liyu
2005-09-20 4:01 ` Song Jiang
2005-09-20 5:02 ` liyu
2005-09-20 5:16 ` Song Jiang
2005-09-20 5:28 ` liyu
2005-09-20 6:01 ` liyu
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox