Department of Computer Science | Institute of Theoretical Computer Science | CADMO

Prof. Emo Welzl and Prof. Bernd Gärtner

Mittagsseminar Talk Information |

**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

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: 2024 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