Mittagsseminar (in cooperation with A. Steger, D. Steurer and B. Sudakov)

Date and Time: Tuesday, November 08, 2005, 12:15 pm

Duration: This information is not available in the database

Location: This information is not available in the database

Speaker: Konstantinos Panagiotou

Performance Measures for Paging

Memory management is a fundamental problem 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 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.

In this talk we present a general lower bound for the minimum number of faults, which provides insight into the global structure of a given request sequence. In addition, we derive a characterization for the number of faults incurred by LRU. Furthermore, we classify the set of all request sequences according to certain parameters and prove bounds on the competitive ratio of LRU, which depends on them. This bound varies between 3 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.

Moreover, we investigate the alternative approach of variable cache size and prove tight bounds for the expected competitive ratio E[ALG]/E[OPT] and the average performance ratio E[ALG/OPT].

Upcoming talks     |     All previous talks     |     Talks by speaker     |     Upcoming talks in iCal format (beta version!)

Previous talks by year:   2023  2022  2021  2020  2019  2018  2017  2016  2015  2014  2013  2012  2011  2010  2009  2008  2007  2006  2005  2004  2003  2002  2001  2000  1999  1998  1997  1996  

Information for students and suggested topics for student talks

Automatic MiSe System Software Version 1.4803M   |   admin login