In this paper we explore the effects of locality on the performance of paging algorithms. Traditional competitive analysis fails to explain important properties of paging assessed by practical experience. In particular, the competitive ratios of paging algorithms that are known to be efficient in practice (e.g. LRU) are as poor as those of naive heuristics (e.g. FWF). It has been recognized that the main reason for these discrepancies lies in an unsatisfactory modelling of locality of reference exhibited by real request sequences. Following [13], we explicitely address this issue, proposing an adversarial model in which the probability of requesting a page is also a function of the page's age. In this way, our approach allows to capture the effects of locality of reference. We consider several families of distributions and we prove that the competitive ratio of LRU becomes constant as locality increases, as expected. This result is strengthened when the distribution satisfies a further concavity/convexity property: in this case, the competitive ratio of LRU is always constant. We also propose a family of distributions parametrized by locality of reference and we prove that the performance of FWF rapidly degrades as locality increases, while the converse happens for LRU. We think, our results provide one contribution to explaining the behaviours of these algorithms in practice.
Modeling locality: a probabilistic analysis of LRU and FWF / Becchetti, Luca. - 3221:(2004), pp. 98-109. (Intervento presentato al convegno 12th Annual European Symposium on Algorithms (ESA 2004) tenutosi a Bergen, NORWAY) [10.1007/978-3-540-30140-0_11].
Modeling locality: a probabilistic analysis of LRU and FWF
BECCHETTI, Luca
2004
Abstract
In this paper we explore the effects of locality on the performance of paging algorithms. Traditional competitive analysis fails to explain important properties of paging assessed by practical experience. In particular, the competitive ratios of paging algorithms that are known to be efficient in practice (e.g. LRU) are as poor as those of naive heuristics (e.g. FWF). It has been recognized that the main reason for these discrepancies lies in an unsatisfactory modelling of locality of reference exhibited by real request sequences. Following [13], we explicitely address this issue, proposing an adversarial model in which the probability of requesting a page is also a function of the page's age. In this way, our approach allows to capture the effects of locality of reference. We consider several families of distributions and we prove that the competitive ratio of LRU becomes constant as locality increases, as expected. This result is strengthened when the distribution satisfies a further concavity/convexity property: in this case, the competitive ratio of LRU is always constant. We also propose a family of distributions parametrized by locality of reference and we prove that the performance of FWF rapidly degrades as locality increases, while the converse happens for LRU. We think, our results provide one contribution to explaining the behaviours of these algorithms in practice.File | Dimensione | Formato | |
---|---|---|---|
VE_2004_11573-53957.pdf
solo gestori archivio
Tipologia:
Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza:
Tutti i diritti riservati (All rights reserved)
Dimensione
201.04 kB
Formato
Adobe PDF
|
201.04 kB | Adobe PDF | Contatta l'autore |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.