algorithm
Online-Algorithmen

Bemerkungen

Paging (Online-Caching)

Vorwort

Anstatt mit einer formalen Definition zu beginnen, ist es das Ziel, diese Themen anhand einer Reihe von Beispielen zu behandeln und dabei Definitionen einzuführen. Die Bemerkung Abschnitt Theorie aller Definitionen, Sätze und Sätze bestehen finden Sie alle Informationen zu geben , um schneller spezifische Aspekte nachschlagen.

Die Quellen des Anmerkungsteils umfassen das für dieses Thema verwendete Basismaterial sowie zusätzliche Informationen zum weiteren Lesen. Außerdem finden Sie dort die vollständigen Quellcodes für die Beispiele. Bitte beachten Sie, dass der Quellcode für die Beispiele lesbarer und kürzer ist, da er beispielsweise Fehlerbehandlung usw. unterlässt. Außerdem werden bestimmte Sprachfeatures weitergegeben, die die Klarheit des Beispiels beeinträchtigen würden, z. B. die Verwendung fortgeschrittener Bibliotheken usw.

Paging

Das Paging-Problem ergibt sich aus der Begrenzung des endlichen Raums. Nehmen wir an, unser Cache C hat k Seiten. Nun möchten wir eine Folge von m Seitenanforderungen verarbeiten, die vor der Verarbeitung im Cache abgelegt wurden. Wenn m<=k natürlich alle Elemente in den Cache eingefügt, und es funktioniert, aber normalerweise ist m>>k .

Eine Anforderung ist ein Cache-Treffer , wenn sich die Seite bereits im Cache befindet, andernfalls wird sie als Cache-Miss bezeichnet . In diesem Fall müssen wir die angeforderte Seite in den Cache aufnehmen und eine andere löschen, vorausgesetzt der Cache ist voll. Das Ziel ist ein Räumungsplan, der die Anzahl der Räumungen minimiert .

Es gibt zahlreiche Strategien für dieses Problem, schauen wir uns einige an:

1. First In, First Out (FIFO) : Die älteste Seite wird geräumt
2. Last in, first out (LIFO) : Die neueste Seite wird geräumt
3. Zuletzt verwendet (LRU) : Evict-Seite, deren jüngster Zugriff am frühesten war
4. Am wenigsten häufig verwendete (LFU) : Evict-Seite, die am seltensten aufgerufen wurde
5. Longest Forward Distance (LFD) : Die Seite im Cache wird entfernt, die erst in der Zukunft angefordert wird.
6. Leeren bei vollem Inhalt (FWF) : Leeren Sie den Cache, sobald ein Cache-Miss auftritt

Es gibt zwei Möglichkeiten, dieses Problem anzugehen:

1. offline : Die Reihenfolge der Seitenanfragen ist vorab bekannt
2. online : Die Reihenfolge der Seitenanfragen ist nicht vorab bekannt

Offline-Ansatz

Für den ersten Ansatz schauen Sie sich das Thema Applications of Greedy an . Das dritte Beispiel für das Offline-Caching berücksichtigt die ersten fünf Strategien von oben und gibt Ihnen einen guten Einstiegspunkt für das Folgende.

Das Beispielprogramm wurde um die FWF- Strategie erweitert:

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;
        }
    }
};

Den vollständigen Quellcode finden Sie hier . Wenn wir das Beispiel aus dem Thema wiederverwenden, erhalten wir folgende Ausgabe:

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

Obwohl LFD optimal ist, weist FWF weniger Cache-Misses auf. Das Hauptziel bestand jedoch darin, die Anzahl der Vertreibungen zu minimieren, und für die FWF bedeuten fünf Fehlschüsse 15 Vertreibungen, was die schlechteste Wahl für dieses Beispiel darstellt.

Online-Ansatz

Nun wollen wir uns dem Online-Problem des Paging nähern. Aber zuerst brauchen wir ein Verständnis dafür, wie es geht. Offensichtlich kann ein Online-Algorithmus nicht besser sein als der optimale Offline-Algorithmus. Aber wie viel schlimmer ist es? Wir brauchen formale Definitionen, um diese Frage zu beantworten:

Definition 1.1: Ein Optimierungsproblem Π besteht aus einer Menge von Instanzen Σ _Π . Für jede Instanz σ∈Σ _Π gibt es eine Menge Ζ _σ von Lösungen und eine Zielfunktion f _σ : Ζ _σ → ℜ _≥ 0, die jeder Lösung einen positiven Wert zuweist.
Wir sagen, OPT (σ) ist der Wert einer optimalen Lösung, A (σ) ist die Lösung eines Algorithmus A für das Problem Π und w _A (σ) = f _σ (A (σ)) sein Wert.

Definition 1.2: Ein Online-Algorithmus A für ein Minimierungsproblem Π hat ein Konkurrenzverhältnis von r ≥ 1, wenn eine Konstante τ∈ℜ mit vorliegt

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

für alle Fälle σ∈Σ _Π . A wird als r-kompetitiver Online-Algorithmus bezeichnet. Ist gerade

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

für alle Fälle σ A _Π wird A als streng r-kompetitiver Online-Algorithmus bezeichnet.

Die Frage ist also, wie wettbewerbsfähig unser Online-Algorithmus im Vergleich zu einem optimalen Offline-Algorithmus ist. In ihrem berühmten Buch verwendeten Allan Borodin und Ran El-Yaniv ein anderes Szenario, um die Online-Paging-Situation zu beschreiben:

Es gibt einen bösen Gegner, der Ihren Algorithmus und den optimalen Offline-Algorithmus kennt. In jedem Schritt versucht er, eine Seite anzufordern, die für Sie am schlechtesten und gleichzeitig für den Offline-Algorithmus am besten ist. Der Wettbewerbsfaktor Ihres Algorithmus ist der Faktor, wie schlecht Ihr Algorithmus gegen den optimalen Offline-Algorithmus des Gegners war. Wenn Sie versuchen möchten, der Gegner zu sein, können Sie das Gegner- Spiel ausprobieren (versuchen Sie, die Paging-Strategien zu schlagen).

Markierungsalgorithmen

Anstatt jeden Algorithmus separat zu analysieren, betrachten wir eine spezielle Online-Algorithmusfamilie für das Paging-Problem, die als Markierungsalgorithmen bezeichnet wird .

Sei σ = (σ ₁ , ..., σ _p ) eine Instanz für unser Problem und k unsere Cache-Größe, dann kann σ in Phasen unterteilt werden:

• Phase 1 ist die maximale Teilsequenz von σ vom Start bis zur maximalen Anzahl von k verschiedenen Seiten
• Phase i ≥ 2 ist die maximale Untersequenz von σ vom Ende von Schritt i-1 bis maximal k verschiedene Seiten angefordert werden

Zum Beispiel mit k = 3:

Ein Markierungsalgorithmus (implizit oder explizit) gibt an, ob eine Seite markiert ist oder nicht. Zu Beginn jeder Phase sind alle Seiten nicht markiert. Wird eine Seite während einer Phase angefordert, wird sie markiert. Ein Algorithmus ist ein Markierungsalgorithmus, wenn eine markierte Seite niemals aus dem Cache entfernt wird. Das bedeutet, dass Seiten, die während einer Phase verwendet werden, nicht gelöscht werden.

Satz 1.3: LRU und FWF sind Markierungsalgorithmus.

Beweis: Zu Beginn jeder Phase (außer der ersten) hat FWF einen Cache-Miss und den Cache gelöscht. Das heißt, wir haben k leere Seiten. In jeder Phase werden maximal k verschiedene Seiten angefordert, daher wird es nun während der Phase entfernt. FWF ist also ein Markierungsalgorithmus.
Nehmen wir an, LRU ist kein Markierungsalgorithmus. Dann gibt es eine Instanz σ, bei der LRU eine markierte Seite x in Phase i entfernt hat. Lassen σ _t die Anfrage in Phase I , in der x vertrieben wird. Da x markiert ist, muss es eine frühere Anforderung σ _{t *} für x in derselben Phase geben, also t * <t. Nachdem t * x die neueste Seite des Caches ist, muss die Folge σt _{* + 1} , ..., σt mindestens _t von x verschiedenen Seiten abfragen, um die Zeit zu verlassen. Dies bedeutet, dass die Phase i mindestens k + 1 verschiedene Seiten angefordert hat, was der Phasendefinition widerspricht. LRU muss also ein Markierungsalgorithmus sein.

Satz 1.4: Jeder Markierungsalgorithmus ist streng k-kompetitiv .

Beweis: Sei σ eine Instanz für das Paging-Problem und l die Anzahl der Phasen für σ. Ist l = 1, ist jeder Markierungsalgorithmus optimal und der optimale Offline-Algorithmus kann nicht besser sein.
Wir gehen davon aus, dass l ≥ 2 ist. Die Kosten für jeden Markierungsalgorithmus sind beispielsweise σ von oben mit l ⋅ k begrenzt, da in jeder Phase ein Markierungsalgorithmus nicht mehr als k Seiten entfernen kann, ohne eine markierte Seite zu löschen.
Wir versuchen nun zu zeigen, dass der optimale Offline-Algorithmus in der ersten Phase mindestens k + l-2 Seiten für σ, k und mindestens eine für jede nachfolgende Phase außer der letzten enthält. Zum Beweis definieren wir l-2 disjunkte Untersequenzen von σ. Die Folge i ∈ {1, ..., l-2} beginnt an der zweiten Position der Phase i + 1 und endet mit der ersten Position der Phase i + 2.
Sei x die erste Seite von Phase i + 1. Am Anfang der Untersequenz i befinden sich Seite x und höchstens k-1 verschiedene Seiten im Cache für optimale Offline-Algorithmen. In der Teilsequenz i sind k Seitenanfragen von x verschieden, so dass der optimale Offline-Algorithmus für jede Teilsequenz mindestens eine Seite entfernen muss. Da zu Beginn der Phase 1 der Cache noch leer ist, führt der optimale Offline-Algorithmus während der ersten Phase zu K ektionen. Das zeigt das

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

Folgerung 1.5: LRU und FWF sind strikt konkurrenzfähig .

Übung: Zeigen Sie, dass FIFO kein Markierungsalgorithmus ist, sondern streng k-konkurrenzfähig ist .

Gibt es keine Konstante r, für die ein Online-Algorithmus A wettbewerbsfähig ist, nennen wir A nicht wettbewerbsfähig

Vorschlag 1.6: LFU und LIFO sind nicht wettbewerbsfähig .

Beweis: Sei l ≥ 2 a konstant, k ≥ 2 die Cache-Größe. Die verschiedenen Cache-Seiten sind in 1, ..., k + 1 unterteilt. Wir betrachten die folgende Reihenfolge:

Die erste Seite 1 wird l-mal als Seite 2 und somit eine angefordert. Am Ende gibt es (l-1) abwechselnde Anforderungen für die Seite k und k + 1.
LFU und LIFO füllen ihren Cache mit den Seiten 1-k. Wenn Seite k + 1 angefordert wird, wird Seite k geräumt und umgekehrt. Das bedeutet , dass jede Anforderung von Subsequenz (k, k + 1) ^L-1 evicts einer Seite. Außerdem gibt es k-1 Cache-Misses für die erstmalige Verwendung der Seiten 1- (k-1). So entfernen LFU und LIFO exakte k-1 + 2 (l-1) Seiten.
Nun müssen wir zeigen, dass für jede Konstante τ∈ℜ und für jede Konstante r ≤ 1 ein l existiert

das ist gleich

Um diese Ungleichheit zu befriedigen, muss man nur groß genug wählen. LFU und LIFO sind also nicht wettbewerbsfähig.

Satz 1.7: Es gibt keinen r-kompetitiven deterministischen Online-Algorithmus für das Paging mit r <k .

Der Beweis für diesen letzten Vorschlag ist ziemlich lang und basiert auf der Aussage, dass LFD ein optimaler Offline-Algorithmus ist. Der interessierte Leser kann im Buch von Borodin und El-Yaniv nachschlagen (siehe Quellen unten).

Die Frage ist, ob wir es besser machen könnten. Dafür müssen wir den deterministischen Ansatz hinter uns lassen und anfangen, unseren Algorithmus zu randomisieren. Offensichtlich ist es für den Gegner viel schwieriger, den Algorithmus zu bestrafen, wenn er randomisiert ist.

Randomisiertes Paging wird in einem der nächsten Beispiele besprochen ...