# Guest Talks

## title

*On adequate performance measures for paging*

## speaker

## date & place

Wednesday, 20.09.2006, 16:15 h

Room C252

Room C252

## abstract

Caching is a fundamental problem that often occurs when large datastreams have to be handeled, e.g. in computer architecture and operating systems. We consider a two-level memory system with fast, but small cache and slow, but large main memory. The underlying theoretical problem is known as the paging problem. A sequence of requests to pages has to be served by making each requested page available in the cache. A paging strategy replaces pages in the cache with requested ones. The aim is to minimize the number of page faults that occur whenever a requested page is not in the cache. Experience shows that the Least-Recently-Used (LRU) paging strategy usually achieves a factor around 2 to 3 compared to the optimum number of faults. This contrasts the theoretical worst case, in which this factor can be as large as the cache size k.We give a theoretical explanation why LRU performs well in practice. We classify the set of all request sequences according to certain parameters and prove a bound on the competitive ratio of LRU, which depends on these. This bound varies between 2 and k, i.e., it includes the worst-case, but explains for which sequences LRU achieves constant competitive ratio. The classification is motivated from the structure of request sequences of practical applications: locality of reference and characteristic data access patterns. We argue that this structure yields values around 2 for our bound. Indeed, it is between 2 and 5 in extensive practical experiments.