Looking for algorithm Keywords? Try Ask4Keywords

algorithmOnline-Algorithmen


Bemerkungen

Theorie

Definition 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 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 (& sigma) + τ

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

w A (σ) ≤ r ⋅ OPT (& sigma)

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

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 nehmen an, dass l ≥ 2 ist. Die Kosten für jeden Markierungsalgorithmus beispielsweise σ sind von oben mit l with k begrenzt, da in jeder Phase ein Markierungsalgorithmus nicht mehr als k Seiten entfernen kann, ohne eine markierte Seite zu entfernen.
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 .

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:

Geben Sie hier die Bildbeschreibung ein

Die erste Seite 1 wird l-mal als Seite 2 angefordert und so eine. 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

Geben Sie hier die Bildbeschreibung ein

das ist gleich

Geben Sie hier die Bildbeschreibung ein

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 .

Quellen

Grundmaterial

  1. Script Online Algorithms (deutsch), Heiko Roeglin, Universität Bonn
  2. Algorithmus zum Ersetzen der Seite

Lesen Sie weiter

  1. Online-Berechnung und Wettbewerbsanalyse von Allan Borodin und Ran El-Yaniv

Quellcode

  1. Quellcode für das Offline-Caching
  2. Quellcode für ein gegnerisches Spiel

Online-Algorithmen Verwandte Beispiele