[Question] How to understand Clock-Pro algorithm?

[Question] How to understand Clock-Pro algorithm?

[liyu]

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

   



   
   

Re: [Question] How to understand Clock-Pro algorithm?

[Song Jiang]

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>

Re: [Question] How to understand Clock-Pro algorithm?

[liyu]

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>
>
>
>  
>

Re: [Question] How to understand Clock-Pro algorithm?

[Song Jiang]

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

> 

Re: [Question] How to understand Clock-Pro algorithm?

[liyu]

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
>
>  
>
>
>
>
>
>  
>