Участник:Vlad SG

Формулировка

Пусть задана последовательность запросов к внешней памяти. Необходимо решить для каждого запроса: сохранить его значение в кэш размера [math]k[/math] или оставить его во внешней памяти.

Основные определения

Определение:

Кэш попадание (англ. cache hit) — результат обрабатываемого запроса уже хранится в кэше и его можно вернуть мгновенно. Будем считать, что время обработки такого запроса равно 0.

Определение:

Кэш промах (англ. cache miss) — результат обрабатываемого запроса отсутствует в кэше и чтобы его получить необходимо обращаться к внешней памяти. При получении ответа мы так же можем сохранить новое значение в кэш, вытеснив(удалив) некоторое старое. Будем считать, что время обработки такого запроса равно 1.

Определение:

Временем работы алгоритма кэширования будем называть количество кэш промахов случившихся при обработке всех запросов.

При анализе случайных алгоритмов будем использовать матожидание количества кэш промахов при всех возможных случайных выборах, но для фиксированной последовательности запросов.

Определение:

Онлайн алгоритм (англ. on-line algorithm) — алгоритм, который при обработке запроса не знает следующих запросов.

Определение:

Оффлайн алгоритм (англ. off-line algorithm) — алгоритм, которому на вход даются все запросы сразу.

Определение:

[math]\alpha[/math]-оптимальность — свойство онлайн алгоритма, означающее что время работы этого алгоритма на любых входных данных не более чем в [math]\alpha[/math] раз больше, чем у любого оффлайнового, с точностью до аддитивной константы.

Ограничение детерминированных алгоритмов

Теорема:

[math]k[/math] — размер кэша. Любой [math]\alpha[/math]-оптимальный детерменированный алгоритм кэширования имеет [math]\alpha \geq k[/math].

Доказательство:

[math]\triangleright[/math]

Чтобы показать, что [math]\alpha \geq k[/math], достаточно для каждого алгоритма предоставить одну такую последовательность запросов, при которой Теорема доказана.

[math]\triangleleft[/math]

Источники

• A. Fiat, R. M. Karp, M. Luby, L. A. McGeoch, D. D. Sleator, N. E. Young, Competitive Paging Algorithms, Journal of Algorithms 12, 685-699 (1991)