BROWSE
Detail
Conference Paper
On the Cache Sojourn Time Distribution of the LRU Replacement Algorithm
Cited - time in 
Share 
Share
- Authors
- Jong-Geun Park, Hoon Choi, Soon-Seok Lee, Chi-Hoon Shin
- Issue Date
- 2012-02
- Citation
- International Conference on Advanced Information Technology and Sensor Application (AITS) 2012, pp.1-8
- Language
- English
- Type
- Conference Paper
- Abstract
- While considerable studies on the LRU cache replacement algorithm have been conducted, various characteristics of the LRU have yet to be evaluated. Since a mathematical analysis can give us deeper insight into the system and can provide a foundation for future studies, various analytical approaches are encouraged. In this manuscript, we investigate the cache sojourn time distribution that is the time spent in the cache, and the non-cached time distribution that is the time spent out of the cache, of an arbitrary item under an LRU replacement algorithm in the presence of independent reference request processes. We then show that the cache sojourn time is only affected by the sum of probabilities of requesting non-cached items, regardless of any request probability patterns. In addition, we present the cache hit ratio and provide a numerical example with brief interpretation from the results.
- KSP Keywords
- Cache Replacement Algorithm, Sojourn time distribution, cache hit ratio, mathematical analysis, numerical examples