Подкачка страниц
Ключевые слова и синонимы
Кэширование (Caching)
Постановка задачи
В компьютерах обычно имеется небольшой объем быстрой памяти, чтобы важные данные всегда были «под рукой». Эта память называется кэш-памятью. Рассматриваемый здесь вопрос заключается в том, какие страницы должны сохраняться в кэше при запросе новой страницы.
Говоря формально, рассматривается двухуровневое хранилище памяти. Кэш может содержать [math]\displaystyle{ k }[/math] страниц, а медленная память – [math]\displaystyle{ n }[/math] страниц, где [math]\displaystyle{ n }[/math] обычно намного больше [math]\displaystyle{ k }[/math]. На вход подается последовательность запросов к страницам. Если запрашиваемая страница отсутствует в кэше, алгоритм выдает ошибку. Цель заключается в том, чтобы минимизировать совокупное количество ошибок страниц.
Легко предложить оптимальный алгоритм, если известна вся последовательность запросов: при каждой ошибке вытеснять из кэша ту страницу, которая в следующий раз будет запрашиваться в наиболее отдаленном будущем [2]. Однако на практике решения о подкачке приходится принимать без знания будущего. Таким образом, необходим онлайновый алгоритм, который принимает решения для каждого запроса, основываясь только на нем и на предыдущих запросах.
Основные результаты
Основным вкладом работы Слейтора и Тарьяна [6] стала идея конкурентного анализа. В этом типе анализа производительность онлайнового алгоритма сравнивается с производительностью оптимального оффлайнового алгоритма OPT. Оффлайновый алгоритм знает все входные данные и, более того, может использовать неограниченные вычислительные ресурсы для поиска наилучшего возможного решения для этих входных данных.
Обозначим стоимость алгоритма [math]\displaystyle{ ALG }[/math] на входной последовательности [math]\displaystyle{ \sigma }[/math] за [math]\displaystyle{ ALG(\sigma) }[/math]. Онлайновый алгоритм [math]\displaystyle{ \mathcal{A} }[/math] называется c-конкурентным, если существует константа [math]\displaystyle{ b }[/math], такая, что для каждой последовательности запросов [math]\displaystyle{ \sigma }[/math] выполняется соотношение
(1) [math]\displaystyle{ \mathcal{A}(\sigma) \le с \cdot ОРТ(\sigma) + b }[/math].
Коэффициентом конкурентоспособности алгоритма [math]\displaystyle{ \mathcal{A} }[/math] является наименьшее значение [math]\displaystyle{ c }[/math], такое, что [math]\displaystyle{ \mathcal{A} }[/math] остается c-конкурентным. Это определение очень похоже на определение коэффициента аппроксимации для аппроксимационных алгоритмов. Однако следует отметить, что на онлайновый алгоритм не накладывается никаких вычислительных ограничений. В частности, ему разрешается использовать экспоненциальное время для принятия решений. Таким образом, коэффициент конкурентоспособности измеряет исключительно потерю производительности, возникающую из-за незнания будущего.
Используя это определение, Слейтор и Тарьян дают строгие границы наилучшего коэффициента конкурентоспособности, который может быть достигнут детерминированным алгоритмом. Они показывают, что два известных алгоритма имеют коэффициент конкурентоспособности [math]\displaystyle{ k }[/math]:
• FIFO (первым пришел – первым вышел), который при ошибке вытесняет страницу, которая была загружена в кэш раньше всех;
• LRU (наиболее давно использовавшийся), который при ошибке вытесняет страницу, которая была запрошена давнее всего.
Кроме того, они показывают, что любой детерминированный алгоритм имеет коэффициент конкурентоспособности не менее [math]\displaystyle{ k }[/math], что означает, что [math]\displaystyle{ k }[/math] – это наилучшее значение, которое может быть достигнуто.
Фиат и др. [3] рассмотрели рандомизированные алгоритмы подкачки страниц. Рандомизированному онлайновому алгоритму при принятии решений разрешается использовать случайные биты. Чтобы измерить его производительность, необходимо рассмотреть матожидание стоимости для определенной входной последовательности и сравнить его с оптимальной стоимостью для этой последовательности. Таким образом, рандомизированный онлайновый алгоритм является c-конкурентным, если существует константа [math]\displaystyle{ k }[/math], такая, что для каждой последовательности запросов [math]\displaystyle{ \sigma }[/math] выполняется соотношение
(2) [math]\displaystyle{ \mathbb{E}(\mathcal{A}(\sigma)) \le с \cdot ОРТ(\sigma) + b }[/math].
Фиат и др. представили алгоритм маркировки. Этот алгоритм маркирует запрашиваемые страницы. При возникновении ошибки немаркированная страница равномерно выбирается случайным образом и вытесняется из кэша. Если все страницы маркированы и произошла ошибка, алгоритм снимает метки со всех страниц, а затем вытесняет одну из них равномерно случайным образом.
Фиат и др. показали, что этот алгоритм является [math]\displaystyle{ 2H_k }[/math] -конкурентным. Здесь [math]\displaystyle{ H_k }[/math] – это [math]\displaystyle{ k }[/math]-е гармоническое число: [math]\displaystyle{ H_k = 1 + \frac{1}{2} + \frac{1}{3} + \dots + \frac{1}{k} }[/math]. Известно, что [math]\displaystyle{ ln(k + 1) \le H_k \le ln(k) + 1 }[/math]. Они также показали, что ни один рандомизированный алгоритм подкачки страниц не может иметь коэффициент конкурентоспособности меньше [math]\displaystyle{ H_k }[/math]. Таким образом, алгоритм маркировки не более чем в два раза хуже наилучшего возможного онлайнового алгоритма (с точки зрения коэффициента конкурентоспособности). Рандомизированный алгоритм с коэффициентом конкурентоспособности, строго равным Hk, был приведен Макгиохом и Слейтором [4]. Он гораздо сложнее алгоритма маркировки.
Применение
Управление памятью долгое время было и остается принципиально важной задачей в вычислительных системах. В частности, вопрос о том, как управлять двухуровневым или многоуровневым хранилищем памяти, по-прежнему имеет решающее значение для производительности компьютеров – от простейших персональных или игровых до крупнейших серверов.
Изучение проблемы подкачки также имело большое значение для развития всей области онлайновых алгоритмов. В работе Слейтора и Тарьяна было официально введено понятие коэффициента конкурентоспособности как меры производительности для онлайн-алгоритмов. Это понятие широко используется и сегодня.
Открытые вопросы
Задача, представленная в данной статье, уже решена, поскольку получены верхняя и нижняя границы [math]\displaystyle{ k }[/math] для детерминированных алгоритмов и верхняя и нижняя границы [math]\displaystyle{ H_k }[/math] – для рандомизированных.
Однако вариации этой задачи продолжают вдохновлять на новые исследования. Первоначальная проблема также подверглась дальнейшему изучению, поскольку верхняя граница [math]\displaystyle{ k }[/math] для подхода LRU (наиболее давно использовавшийся) разочаровывающе высока, а из практики известно, что «на самом деле» коэффициент конкурентоспособности для этого подхода константен. Недавно Панагиоту и Соуза [5] сумели дать теоретическое обоснование этому наблюдению, формально ограничив входные последовательности таким образом, чтобы они были ближе к тем, которые встречаются на практике. Дополнительное обоснование использования LRU было дано Ангелопулосом и коллегами [1], которые выполнили прямое сравнение этого подхода со всеми другими онлайновыми алгоритмами.
См. также
Литература
1. Angelopoulos, S., Dorrigiv, R., Lopez-Ortiz, A.: On the separation and equivalenceof paging strategies. In: Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms. ACM/SIAM, New York, Philadelphia (2007)
2. Belady, L.A.: A study of replacement algorithms for virtual storage computers. IBM Syst. J. 5, 78-101 (1966)
3. Fiat, A., Karp, R., Luby, M., McGeoch, L.A., Sleator, D., Young, N.E.: Competitive paging algorithms. J. Algorithms 12,685-699 (1991)
4. McGeoch, L., Sleator, D.: A strongly competitive randomized paging algorithm. Algorithmica 6(6), 816-825 (1991)
5. Panagiotou, K., Souza, A.: On adequate performance measures for paging. In: STOC '06: Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, pp. 487-496. ACM Press, New York, NY, USA (2006)
6. Sleator, D., Tarjan, R.E.: Amortized efficiency of list update and paging rules. Commun. ACM 28,202-208 (1985)
