Das Problem des Austauschens von Speicherseiten zwischen einem schnellen Arbeitsspeicher und einem langsamen Hauptspeicher ist ein klassisches Online Problem. Es ist nicht klar, auf welche Seiten die Prozesse in der Zukunft zugreifen werden. Wenn sich eine angeforderte Seite bereits im Arbeitsspeicher befindet, verursacht das keine Kosten. Jede angeforderte Seite, die sich aber nicht im Arbeitsspeicher befindet, muß erst geladen werden, das verursacht eine Kosteneinheit. Es wird gezeigt, daß jeder Online Algorithmus für einen Arbeitsspeicher mit k Seiten mindestens k-mal mehr Kosten verursacht als der optimale Algorithmus, der alle Anfragen vorher kennt. Eine spezielle Klasse von Online Algorithmen (Marking) erzielt diese Güte. FIFO und LRU gehören dazu.
Inhalt des Vortrags:
Literatur:
A. Fiat and 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
Betreuer:
Elmar Langetepe