algorithm
Algorytmy online

Uwagi

Stronicowanie (buforowanie online)

Przedmowa

Zamiast zaczynać od formalnej definicji, celem jest podejście do tego tematu za pomocą szeregu przykładów, wprowadzając definicje po drodze. Sekcja uwag Teoria będzie się składać ze wszystkich definicji, twierdzeń i twierdzeń, aby dostarczyć wszystkich informacji umożliwiających szybsze wyszukiwanie określonych aspektów.

Źródła sekcji uwag składają się z materiału podstawowego użytego do tego tematu i dodatkowych informacji do dalszego czytania. Ponadto znajdziesz tam pełne kody źródłowe dla przykładów. Proszę zwrócić uwagę, że aby kod źródłowy dla przykładów był bardziej czytelny i krótszy, powstrzymuje się on przed takimi funkcjami, jak obsługa błędów itp. Ponadto przekazuje pewne specyficzne funkcje językowe, które zaciemniłyby przejrzystość przykładu, takie jak szerokie użycie zaawansowanych bibliotek itp.

Stronicowanie

Problem przywoływania wynika z ograniczenia skończonej przestrzeni. Załóżmy, że nasza pamięć podręczna C ma k stron. Teraz chcemy przetworzyć sekwencję żądań m stron, które muszą zostać umieszczone w pamięci podręcznej przed ich przetworzeniem. Oczywiście, jeśli m<=k to po prostu umieszczamy wszystkie elementy w pamięci podręcznej i będzie działać, ale zwykle jest to m>>k .

Mówimy, że żądanie jest trafieniem do pamięci podręcznej , gdy strona jest już w pamięci podręcznej, w przeciwnym razie jest nazywana brakiem pamięci podręcznej . W takim przypadku musimy przenieść żądaną stronę do pamięci podręcznej i eksmitować inną, zakładając, że pamięć podręczna jest pełna. Celem jest harmonogram eksmisji, który minimalizuje liczbę eksmisji .

Istnieje wiele strategii na ten problem, spójrzmy na niektóre:

1. Pierwsze weszło, pierwsze wyszło (FIFO) : najstarsza strona zostaje eksmitowana
2. Last in, first out (LIFO) : Najnowsza strona zostaje eksmitowana
3. Najmniej ostatnio używany (LRU) : strona eksmisji, do której ostatni dostęp był najwcześniejszy
4. Najrzadziej używane (LFU) : strona eksmitowana, o którą najczęściej pytano
5. Najdłuższa odległość do przodu (LFD) : strona eksmisji w pamięci podręcznej, która nie jest wymagana, aż do najdalej w przyszłości.
6. Opróżnij po zapełnieniu (FWF) : wyczyść pamięć podręczną zakończoną, gdy tylko wystąpi brak pamięci podręcznej

Istnieją dwa sposoby rozwiązania tego problemu:

1. offline : sekwencja żądań stron jest znana z góry
2. online : sekwencja żądań stron nie jest znana z góry

Podejście offline

Po pierwsze podejście zobacz temat Zastosowania techniki chciwości . To trzeci przykład buforowanie offline bierze pod uwagę pierwsze pięć strategii z góry i daje dobry punkt wyjścia dla poniższych.

Przykładowy program został rozszerzony o strategię 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;
        }
    }
};

Pełny kod źródłowy jest dostępny tutaj . Jeśli ponownie wykorzystamy przykład z tematu, otrzymamy następujące dane wyjściowe:

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

Mimo że LFD jest optymalny, FWF ma mniej braków pamięci podręcznej. Ale głównym celem było zminimalizowanie liczby eksmisji, a dla FWF pięć chybień oznacza 15 eksmisji, co czyni go najgorszym wyborem w tym przykładzie.

Podejście online

Teraz chcemy podejść do internetowego problemu stronicowania. Ale najpierw potrzebujemy zrozumienia, jak to zrobić. Oczywiście algorytm online nie może być lepszy niż optymalny algorytm offline. Ale o ile gorzej? Potrzebujemy formalnych definicji, aby odpowiedzieć na to pytanie:

Definicja 1.1: Problem optymalizacji Π składa się z zestawu instancji Σ _Π . Dla każdej instancji σ∈Σ _Π istnieje zbiór Ζ _σ rozwiązań i funkcja celu f _σ : Ζ _σ → ℜ _≥0, która przypisuje dodatnią rzeczywistą wartość każdemu rozwiązaniu.
Mówimy, że OPT (σ) jest wartością optymalnego rozwiązania, A (σ) jest rozwiązaniem algorytmu A dla problemu Π, aw _A (σ) = f _σ (A (σ)) jego wartością.

Definicja 1.2: Algorytm online A dla problemu minimalizacji Π ma współczynnik konkurencyjny r ≥ 1, jeżeli istnieje stała τ∈ℜ z

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

dla wszystkich instancji σ∈Σ _Π . A nazywa się konkurencyjnym algorytmem online. Jest parzysty

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

we wszystkich przypadkach σ∈Σ _Π wtedy A jest nazywany algorytmem online ściśle konkurencyjnym .

Pytanie brzmi zatem, jak konkurencyjny jest nasz algorytm online w porównaniu z optymalnym algorytmem offline. W swojej słynnej książce Allan Borodin i Ran El-Yaniv wykorzystali inny scenariusz do opisania sytuacji stronicowania online:

Istnieje zły przeciwnik, który zna twój algorytm i optymalny algorytm offline. Na każdym kroku próbuje poprosić o stronę, która jest dla ciebie najgorsza, a jednocześnie najlepsza dla algorytmu offline. Współczynnik konkurencyjny Twojego algorytmu jest czynnikiem wpływającym na to, jak źle działał Twój algorytm w stosunku do optymalnego algorytmu offline przeciwnika. Jeśli chcesz spróbować zostać przeciwnikiem, możesz wypróbować grę przeciwnika (spróbuj pokonać strategie stronicowania).

Algorytmy znakowania

Zamiast analizować każdy algorytm osobno, spójrzmy na specjalną rodzinę algorytmów online dla problemu stronicowania zwaną algorytmami znakowania .

Niech σ = (σ ₁ , ..., σ _p ) wystąpienie naszego problemu ik nasz rozmiar pamięci podręcznej, niż σ można podzielić na fazy:

• Faza 1 to maksymalna podsekwencja σ od początku do momentu, gdy zażądano maksymalnej liczby różnych stron
• Faza i ≥ 2 to maksymalna podsekwencja σ od końca fazy i-1 do żądania maksymalnej liczby różnych stron

Na przykład przy k = 3:

Algorytm znakowania (domyślnie lub jawnie) utrzymuje, czy strona jest oznaczona, czy nie. Na początku każdej fazy wszystkie strony są nieoznaczone. Strona żądana podczas fazy zostaje oznaczona. Algorytm jest algorytmem znakującym, jeśli nigdy nie eksmituje zaznaczonej strony z pamięci podręcznej. Oznacza to, że strony używane podczas danej fazy nie zostaną eksmitowane.

Twierdzenie 1.3: LRU i FWF są algorytmem znakowania.

Dowód: na początku każdej fazy (z wyjątkiem pierwszej) FWF ma brak pamięci podręcznej i wyczyścił pamięć podręczną. oznacza to, że mamy k pustych stron. W każdej fazie żądanych jest maksymalnie k różnych stron, więc w tej fazie nastąpi eksmisja. FWF jest więc algorytmem znakowania.
Załóżmy, że LRU nie jest algorytmem znakowania. Następnie jest instancja σ, w której LRU oznaczono stronę x w fazie i eksmitowano. Niech σ _t to żądanie w fazie i, gdzie x jest eksmitowane. Ponieważ x jest zaznaczone, musi być wcześniejsze żądanie σ _{t *} dla x w tej samej fazie, więc t * <t. Gdy t * x jest najnowszą stroną pamięci podręcznej, więc aby zostać eksmitowanym w sekwencji σ _{t * + 1} , ..., σ _t musi zażądać co najmniej k z x różnych stron. Oznacza to, że faza i zażądała co najmniej k + 1 różnych stron, co jest sprzeczne z definicją fazy. Zatem LRU musi być algorytmem znakowania.

Twierdzenie 1.4: Każdy algorytm znakowania jest ściśle konkurencyjny .

Dowód: Niech σ będzie wystąpieniem problemu stronicowania, a l liczbę faz dla σ. Jeśli l = 1, to każdy algorytm znakowania jest optymalny, a optymalny algorytm offline nie może być lepszy.
Zakładamy, że l ≥ 2. koszt każdego algorytmu znakowania, na przykład σ jest ograniczony od góry l ⋅ k, ponieważ w każdej fazie algorytm znakowania nie może eksmitować więcej niż k stron bez eksmisji jednej zaznaczonej strony.
Teraz próbujemy pokazać, że optymalny algorytm offline eksmituje co najmniej k + l-2 stron dla σ, k w pierwszej fazie i co najmniej jedną dla każdej kolejnej fazy, z wyjątkiem ostatniej. Na dowód zdefiniujmy rozłączne podsekwencje l-2 σ. Kolejność i ∈ {1, ..., l-2} zaczyna się od drugiej pozycji fazy i + 1 i kończy na pierwszej pozycji fazy i + 2.
Niech x będzie pierwszą stroną fazy i + 1. Na początku podsekwencji i znajduje się strona x i co najwyżej k-1 różnych stron w optymalnej pamięci podręcznej algorytmów offline. W podsekwencji i k jest żądaniem strony innym niż x, więc optymalny algorytm offline musi eksmitować co najmniej jedną stronę dla każdej podsekwencji. Ponieważ na początku fazy 1 pamięć podręczna jest nadal pusta, optymalny algorytm offline powoduje eksmisje w pierwszej fazie. To pokazuje, że

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

Wniosek 1.5: LRU i FWF są ściśle konkurencyjne .

Ćwiczenie: pokaż, że FIFO nie jest algorytmem znakowania, ale ściśle k-konkurencyjnym .

Czy nie ma stałej r, dla której algorytm online A jest konkurencyjny, nazywamy A niekonkurencyjnym

Twierdzenie 1.6: LFU i LIFO nie są konkurencyjne .

Dowód: Niech l ≥ 2 stała, k ≥ 2 rozmiar pamięci podręcznej. Różne strony pamięci podręcznej mają numery 1, ..., k + 1. Patrzymy na następującą sekwencję:

Pierwsza strona 1 jest wymagana 1 razy niż strona 2, a więc jedna. Na końcu są (l-1) naprzemienne żądania strony k i k + 1.
LFU i LIFO wypełniają swoją pamięć podręczną stronami 1-k. Na żądanie strony k + 1 strona k zostaje eksmitowana i odwrotnie. Oznacza to, że każde żądanie podsekwencji (k, k + 1) ^l-1 wyklucza jedną stronę. Ponadto są to błędy pamięci podręcznej k-1 przy pierwszym użyciu stron 1- (k-1). Zatem LFU i LIFO eksmitują dokładne strony k-1 + 2 (l-1).
Teraz musimy pokazać, że dla każdej stałej τ∈ℜ i każdej stałej r ≤ 1 istnieje l tak, że

co jest równe

Aby zaspokoić tę nierówność, musisz po prostu wybrać wystarczająco duży. Zatem LFU i LIFO nie są konkurencyjne.

Twierdzenie 1.7: Nie ma konkurencyjnego deterministycznego algorytmu online dla stronicowania za pomocą r <k .

Dowód tej ostatniej propozycji jest dość długi i opiera się na stwierdzeniu, że LFD jest optymalnym algorytmem offline. Zainteresowany czytelnik może to sprawdzić w książce Borodin i El-Yaniv (patrz źródła poniżej).

Pytanie brzmi, czy moglibyśmy zrobić lepiej. W tym celu musimy zostawić za sobą deterministyczne podejście i zacząć randomizować nasz algorytm. Oczywiście przeciwnikowi jest znacznie trudniej ukarać algorytm, jeśli jest on losowy.

Randomizowane stronicowanie zostanie omówione w jednym z kolejnych przykładów ...