Подкачка страниц: различия между версиями

Задача, представленная в данной статье, уже решена, поскольку получены верхняя и нижняя границы k для детерминированных алгоритмов и верхняя и нижняя границы Hk – для рандомизированных.

Однако вариации этой задачи продолжают вдохновлять на новые исследования. Первоначальная проблема также подверглась дальнейшему изучению, поскольку верхняя граница k для подхода LRU (наиболее давно использовавшийся) разочаровывающе высока, а из практики известно, что «на самом деле» коэффициент конкурентоспособности для этого подхода константен. Недавно Панагиоту и Соуза [5] сумели дать теоретическое обоснование этому наблюдению, формально ограничив входные последовательности таким образом, чтобы они были ближе к тем, которые встречаются на практике. Дополнительное обоснование использования LRU было дано Ангелопулосом и коллегами [1], которые выполнили прямое сравнение LRU со всеми другими онлайновыми алгоритмами.