algorithm
Интернет-алгоритмы

замечания

Пейджинг (онлайн-кэширование)

Предисловие

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

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

Paging

Проблема поискового вызова возникает из-за ограничения конечного пространства. Предположим, что наш кеш C имеет k страниц. Теперь мы хотим обработать последовательность из m запросов страниц, которые должны были быть помещены в кеш, прежде чем они будут обработаны. Конечно, если m<=k мы просто поместим все элементы в кеш, и он будет работать, но обычно это m>>k .

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

Существует множество стратегий для этой проблемы, давайте рассмотрим некоторые:

1. Первое, сначала (FIFO) : старейшая страница выселяется
2. Последний, первый (LIFO) : самая новая страница выселяется
3. Наименее недавно использованная (LRU) : страница с выездом, последний доступ которой был самым ранним
4. Наименее часто используемая (LFU) : страница с наименьшим количеством запросов
5. Самое длинное прямое расстояние (LFD) : вырезать страницу в кеше, которая не запрашивается дольше в будущем.
6. Сброс при заполнении (FWF) : очистите кеш, как только произойдет сбой кеша

Существует два способа решения этой проблемы:

1. offline : последовательность запросов страницы известна заранее
2. онлайн : последовательность запросов страницы не известна заранее

Автономный подход

Для первого подхода рассмотрите тему « Применения жадности» . Это третий пример. Оффлайн Кэширование рассматривает первые пять стратегий сверху и дает вам хорошую точку входа для следующего.

Пример программы был расширен с помощью стратегии FWF :

class FWF : public Strategy {
public:
    FWF() : Strategy("FWF")
    {
    }

    int apply(int requestIndex) override
    {
        for(int i=0; i<cacheSize; ++i)
        {
            if(cache[i] == request[requestIndex])
                return i;

            // after first empty page all others have to be empty
            else if(cache[i] == emptyPage)
                return i;
        }

        // no free pages
        return 0;
    }

    void update(int cachePos, int requestIndex, bool cacheMiss) override
    {

        // no pages free -> miss -> clear cache
        if(cacheMiss && cachePos == 0)
        {
            for(int i = 1; i < cacheSize; ++i)
                cache[i] = emptyPage;
        }
    }
};

Полный исходный код доступен здесь . Если мы повторно используем пример из этой темы, мы получаем следующий результат:

Strategy: FWF

Cache initial: (a,b,c)

Request cache 0 cache 1 cache 2 cache miss
  a       a       b       c
  a       a       b       c
  d       d       X       X       x
  e       d       e       X
  b       d       e       b
  b       d       e       b
  a       a       X       X       x
  c       a       c       X
  f       a       c       f
  d       d       X       X       x
  e       d       e       X
  a       d       e       a
  f       f       X       X       x
  b       f       b       X
  e       f       b       e
  c       c       X       X       x

Total cache misses: 5

Несмотря на то, что LFD является оптимальным, FWF имеет меньше промахов в кэше. Но главная цель заключалась в том, чтобы свести к минимуму количество выселений, а для FWF пять промахов означают 15 выселений, что делает его самым бедным выбором для этого примера.

Интернет-подход

Теперь мы хотим подойти к онлайн-проблеме пейджинга. Но сначала нам нужно понять, как это сделать. Очевидно, онлайн-алгоритм не может быть лучше, чем оптимальный автономный алгоритм. Но насколько это хуже? Нам нужны формальные определения для ответа на этот вопрос:

Определение 1.1. Задача оптимизации Π состоит из множества экземпляров Σ _Π . Для каждого экземпляра σ∈Σ _Π существует множество Ζ _σ решений и целевая функция f _σ : Ζ _σ → ℜ _≥0, которая присваивает апо- _{зитивное} вещественное значение каждому решению.
Скажем, OPT (σ) является значением оптимального решения, A (σ) является решением Алгоритма A для задачи Π и w _A (σ) = f _σ (A (σ)) его значение.

Определение 1.2. Онлайн-алгоритм A для задачи минимизации Π имеет конкурентное отношение r ≥ 1, если существует постоянная τ∈ℜ с

w _A (σ) = f _σ (A (σ)) ≤ r ⋅ OPT (σ) + τ

для всех экземпляров σ∈Σ _Π . A называется r-конкурентным онлайн-алгоритмом. Даже

w _A (σ) ≤ r ⋅ OPT (σ)

для всех экземпляров σ∈Σ _Π, тогда A называется строго r-конкурентным онлайн-алгоритмом.

Поэтому вопрос заключается в том, насколько конкурентоспособным является наш онлайн-алгоритм по сравнению с оптимальным автономным алгоритмом. В своей знаменитой книге Аллан Бородин и Ран Эль-Янив использовали другой сценарий для описания ситуации онлайн-пейджинга:

Существует злой противник, который знает ваш алгоритм и оптимальный автономный алгоритм. На каждом шагу он пытается запросить страницу, которая для вас хуже всего, и одновременно лучше подходит для автономного алгоритма. конкурентный фактор вашего алгоритма - это фактор того, насколько плохо ваш алгоритм против оптимального автономного алгоритма противника. Если вы хотите попытаться стать противником, вы можете попробовать Противную игру (попытайтесь победить стратегии поискового вызова).

Алгоритмы маркировки

Вместо того, чтобы анализировать каждый алгоритм отдельно, давайте посмотрим на специальное семейство онлайн-алгоритмов для проблемы поискового вызова, называемой алгоритмами маркировки .

Пусть σ = (σ ₁ , ..., σ _p ) экземпляр для нашей задачи и k размер кеша, чем σ можно разделить на фазы:

• Фаза 1 - это максимальная подпоследовательность σ от начала до максимального k различных страниц
• Фаза i ≥ 2 - максимальная подпоследовательность σ от конца pase i-1 до максимального k различных страниц

Например, при k = 3:

Алгоритм маркировки (неявно или явно) поддерживает, отмечена ли страница или нет. В начале каждого этапа все страницы не отмечены. Является ли страница запрошенной в течение фазы, она становится отмеченной. Алгоритм является алгоритмом маркировки, если он никогда не высекает отмеченную страницу из кеша. Это означает, что страницы, которые используются во время фазы, не будут выселены.

Предложение 1.3: LRU и FWF - это алгоритм маркировки.

Доказательство. В начале каждой фазы (кроме первой) FWF имеет пропущенную кэш и очищает кеш. это означает, что у нас есть пустые страницы. В каждой фазе запрашивается максимальное количество k различных страниц, поэтому на этапе будет выселение. Таким образом, FWF является алгоритмом маркировки.
Предположим, что LRU не является алгоритмом маркировки. Тогда есть экземпляр σ, где LRU - отмеченная страница x на фазе i, выселенная. Пусть σ _t запрос в фазе i, где x выселяется. Так как x отмечен, в той же фазе должен быть более ранний запрос σ _{t *} для x, поэтому t * <t. После того, как t * x является последней страницей кэшей, поэтому для выселения в t последовательность σ _{t * + 1} , ..., σ _t должна запрашивать не менее k из x разных страниц. Это означает, что фаза i запросила не менее k + 1 разных страниц, что противоречит определению фазы. Поэтому LRU должен быть алгоритмом маркировки.

Предложение 1.4: Каждый маркерный алгоритм строго k-конкурентный .

Доказательство. Пусть σ - пример для проблемы поискового вызова и l число фаз для σ. L = 1, то каждый алгоритм маркировки оптимален, и оптимальный автономный алгоритм не может быть лучше.
Предположим, что l ≥ 2. стоимость каждого алгоритма маркировки, например, σ ограничена сверху с l ⋅ k, поскольку на каждой фазе алгоритм маркировки не может выселить более k страниц, не вытесняя одну отмеченную страницу.
Теперь мы попытаемся показать, что оптимальный автономный алгоритм выдает по крайней мере k + l-2 страницы для σ, k в первой фазе и по крайней мере один для каждой следующей фазы, за исключением последней. Для доказательства можно определить l-2 дизъюнктных подпоследовательностей σ. Подпоследовательность i ∈ {1, ..., l-2} начинается со второго положения фазы i + 1 и заканчивается первой позицией фазы i + 2.
Пусть x - первая страница фазы i + 1. В начале подпоследовательности i есть страница x и не более k-1 разных страниц в кеше оптимальных автономных алгоритмов. В подпоследовательности i есть запрос страницы k, отличный от x, поэтому оптимальный автономный алгоритм должен вытеснять по крайней мере одну страницу для каждой подпоследовательности. Поскольку на этапе 1 кеш все еще пуст, оптимальный автономный алгоритм вызывает k выселений в течение первой фазы. Это показывает, что

w _A (σ) ≤ l⋅k ≤ (k + l-2) k ≤ OPT (σ) ⋅ k

Следствие 1.5: LRU и FWF являются строго k-конкурентными .

Упражнение: покажите, что FIFO не является алгоритмом маркировки, но строго k-конкурентным .

Нет ли константы r, для которой онлайн-алгоритм A является r-конкурентным, мы называем A неконкурентоспособным

Предложение 1.6: LFU и LIFO не являются конкурентоспособными .

Доказательство. Пусть l ≥ 2 константа, k ≥ 2 размер кеша. Различные страницы кеша имеют нулевое значение 1, ..., k + 1. Мы рассмотрим следующую последовательность:

Первая страница 1 запрашивается l раз, чем страница 2, и поэтому одна. В конце есть (l-1) чередующиеся запросы для страниц k и k + 1.
LFU и LIFO заполняют свой кеш страницами 1-k. Когда страница k + 1 запрашивается, страница k вызывается и наоборот. Это означает, что каждый запрос подпоследовательности (k, k + 1) ^l-1 высылает одну страницу. Кроме того, их кешируют кэширование k-1 для использования в первый раз страниц 1- (k-1). Таким образом, LFU и LIFO выселяют точные k-1 + 2 (l-1) страницы.
Теперь мы должны показать, что для любой константы τ∈ℜ и любой константы r ≤ 1 существует l, так что

которая равна

Чтобы удовлетворить этому неравенству, вам просто нужно выбрать l достаточно большой. Таким образом, LFU и LIFO не являются конкурентоспособными.

Предложение 1.7: Не существует r-конкурентного детерминированного онлайн-алгоритма для пейджинга с r <k .

Доказательство этого последнего предложения довольно длинное и основано на утверждении, что LFD является оптимальным автономным алгоритмом. Заинтересованный читатель может найти это в книге Бородина и Эль-Янива (см. Источники ниже).

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

Рандомизированный пейджинг будет обсуждаться в одном из следующих примеров ...