Proseminar Online-Algorithmen WS 00/01
Prof. Dr. Rolf Klein, Dr. Elmar Langetepe, Dipl. Inform. Thomas Kamphans

Kompetitive Analyse des Pagings

von Christoph Miebach




Einleitung
OPT
c-Kompetitivität
Theorem 1
Marking Algorithmen :      LRU
Theorem 2
FIFA-Algorithmus




Einleitung

Die Aufgabe eines Paging-Algorithmus besteht darin, im Cache Platz zu schaffen, wenn eine Seite außerhalb des Caches aufgerufen wird.


Für die Bewertung der verschiedenen Paging-Algorithmen legen wir die folgenden Kosten zu Grunde:
Kosten von 1 : für jede Seite, die in den Cache geladen werden muss
Kosten von 0 : wenn sich die Seite schon im Cache befindet
Man zählt also einfach die Seiten, die geladen werden müssen.


Im folgenden steht:
OPT für den optimalen Offline-Algorithmus
A für einen Algorithmus
k für die Anzahl der Seiten im Cache
s für eine Eingabe-Sequenz
|s| für die Länge der Eingabe-Sequenz
cost k,A ( s ) für die Kosten des Algorithmus A bei der Sequenz s und einem k großen Cache
cost k,OPT ( s ) für die Kosten von OPT bei der Sequenz s und einem k großen Cache


Anfang


Der optimale Paging-Algorithmus: OPT

löscht immer dann, wenn er eine Seite in den Cache laden muss, die Seite, die am längsten nicht benötigt wird. Dass dieser Algorithmus optimal ist, sieht man sehr leicht:
Mit jeder anderen Wahl würden sich schon früher Kosten ergeben, und dann wäre der Algorithmus an dieser Stelle nicht optimal.


Anfang


Für die Kompetivität bekommen wir nun die
Definition:

Ein Algorithmus A ist c-kompetitiv, wenn es eine Konstante b gibt, so dass für jede Eingabe-Sequenz s gilt:

cost k,A (s) <= c * cost k,OPT (s) + b


Man bewertet den Online-Algorithmus also im direkten Vergleich zu OPT.


Anfang


Theorem 1:

Für jeden deterministischen Online-Algorithmus gilt: c <= k

Der Beweis ist sehr anschaulich:
Wir gehen davon aus, dass beide Algorithmen ( A und OPT ) zu Anfang die gleichen Seiten im Cache haben. Unser s beginnt jetzt mit einer Seite die noch nicht im Cache ist.
A muss nun eine Seite aus dem Cache löschen ( er arbeitet ja online).
Und mit genau dieser Seite geht unser s jetzt weiter.
Auch diese Seite ist jetzt nicht mehr im Cache ==> A muss wieder eine Seite löschen.
Dieses Spiel kann man solange treiben wie man will: Man verlangt einfach immer die Seite, die A gerade gelöscht hat. Die Kosten die A dabei verursacht sind genau gleich der Länge von s, denn er muss ja jedes Mal eine Seite laden.

==> cost k,A (s) = |s|

OPT hat es da wesentlich leichter:
Er bekommt ja die ganze Sequenz, und muss erst dann entscheiden, welche Seiten er jeweils löscht.
Die erste Seite in s muss auch OPT laden und dabei eine Seite aus dem Cache löschen. Wir wissen aber, dass diese Seite erst wieder nach allen anderen Seiten im Cache verlangt wird.
==> die nächsten k-1 Seiten müssen nicht geladen werden.
Wenn jetzt die nächste Seite gelöscht wird, wissen wir auch aber, dass wieder frühestens nach k-1 Seiten eine Seite kommen kann, die nicht im Cache ist usw.

==> cost k,OPT (s) <= |s|/ k (aufgerundet)



Nachdem wir bewiesen haben, dass es keinen Online-Algorithmus gibt, der besser als k-kompetitiv ist, zeigen wir jetzt, dass diese untere Schranke tatsächlich von einigen Algorithmen erreicht wird:
Dafür definieren wir zuerst:

Anfang


Marking-Algorithmen

sind eine Klasse von Algorithmen, auf die das folgende Schema zutrifft:
Der Algorithmus verläuft in Phasen. Jede Phase hat diesen Verlauf:
- Zu Beginn sind alle Seiten unmarkiert
- Jede aufgerufene Seite wird markiert ( egal ob sie schon im Cache war, oder geladen werden musste)
- Wenn eine Seite geladen werden muss, wird eine unmarkierte Seite gelöscht ( welche genau entscheidet der Algorithmus)
- Die Phase endet,
wenn alle Seiten markiert sind und trotzdem eine Seite geladen werden soll
<=> wenn alle Seiten markiert sind, unmittelbar vor dem Aufruf der nächsten Seite außerhalb des Caches
<=> genau vor dem Aufruf der k+1-ten unterschiedlichen Seite in dieser Phase
- Am Ende jeder Phase werden alle Markierungen aufgehoben


Jetzt noch zwei Bemerkungen:

- Wo die Phasen enden, hängt nur von der Sequenz ab, jedoch nicht davon, welche unmarkierte Seite der Algorithmus löscht.

- LRU ist ein Marking-Algorithmus. Es wird ja immer die Seite gelöscht, die am längsten nicht benötigt ( also auch nicht markiert ) wurde.


Anfang


Theorem 2:

Jeder Marking Algorithmus ist k-kompetitiv


Für den Beweis wird die Sequenz in "Segmente" eingeteilt. Jedes Segment beginnt mit dem zweiten Aufruf in einer Phase und endet mit dem ersten der nachfolgenden Phase ( jeweils einschließlich).

Dadurch erreicht man folgendes:
Vor dem Beginn des Segments haben sowohl OPT als auch A die Seite direkt vor diesem Segment im Cache. Geht ja nicht anders, es gab ja noch keinen Aufruf danach.
In diesem Segment werden jetzt aber noch genau k andere Seiten verlangt.
==>OPT verursacht zumindest Kosten von 1.
Andererseits verursacht jeder Marking-Algorithmus höchsten Kosten k ( jede Seite wird höchsten einmal geladen und ist dann markiert).


Anfang


FIFA:=First-In-First-Aut ( neue Rechtschreibung! )

ist natürlich Quatsch, aber ich hatte gehofft, das würde euch neugierig genug machen, damit ihr das auch noch lest...


FIFO ist k-kompetitiv:
Da FIFO kein Marking-Algorithmus ist, muss diese Aussage noch bewiesen werden.
Das geht jetzt wieder schnell:
Wir beginnen bei einer Seite, die FIFO laden muss ( die anderen Seiten kann man weglassen, da ja keine Kosten verursacht werden). Diese Seite wird erst wieder überschrieben, wenn noch k weitere ( unterschiedliche) Seite verlangt wurden.
Aber spätestens bei der k-ten Seite verursacht auch OPT Kosten von 1, weil ja dann insgesamt k+1 Seiten verlangt wurden und auch OPT nur k Seiten gleichzeitig im Cache haben kann.


Anfang



Literatur:

A. Fiat und G.J. Woeginger
Online Algorithms: The State of the Art, LNCS 1442
Kap. 3 S. 52-73, relevant S.52-56.


D. Sleater, R.E. Tarjan
Amortized efficiency of list update and paging rules.
Communications of the ACM 28:202-208, 1985
relevant Abschnitt über Paging


A. Karlin, M. Manasse, L. Rudolph, D. Sleator
Competitive snoopy caching, Algorithmica, 3(1):79-119, 1988
relevant Abschnitt über untere Schranke



Best viewed with:
ANY-Browser

by Christoph Miebach