DEPARTMENT OF MATHEMATICS AND COMPUTER SCIENCE               
                    UNIVERSITY OF SOUTHERN DENMARK, ODENSE                   

                      Paging with Locality of Reference                      

                              Lene M. Favrholdt                              
                Department of Mathematics and Computer Science               
                    University of Southern Denmark, Odense                   

                    Tuesday, November 20, 2001, at 2:15 PM                   
                               The Seminar Room                              


Motivated by  the  fact that  competitive  analysis yields  too  pessimistic
results when  applied to  the paging  problem, there  has been  considerable
research  interest  in  refining  competitive  analysis  and  in  developing
alternative models for studying online paging.  The goal is to devise models
in which theoretical results capture phenomena observed in practice.

In the  talk  a new,  simple  model for  studying  paging with  locality  of
reference is presented.  The model  is closely related  to Denning's working
set concept  and  directly reflects  the  amount  of locality  that  request
sequences exhibit.

We use the  page fault rate  to evaluate  the quality of  paging algorithms,
which is the  performance measure  used in  practice.  In our  model LRU  is
optimal whereas FIFO and deterministic marking strategies are not optimal in
general.

This is joint work with Susanne Albers and Oliver Giel.


                                                            Host: Joan Boyar