\documentclass{paper}

\setlength {\parindent} {0 pt}
\setlength {\parskip} {1.5 ex plus 0.5 ex minus 0.2 ex}

\usepackage{fullpage}
\usepackage {amssymb}
\usepackage {amsmath}
\usepackage {amsthm}
%\usepackage {wasysym}
\usepackage [usenames] {color}

\usepackage {enumerate}
\usepackage {cite}
\usepackage{float}
\usepackage {xspace}


\floatstyle{ruled}
\newfloat{algorithm}{thp}{alg}
\floatname{algorithm}{Algorithm}


%\usepackage {hyperref}

\newcommand {\mathset} [1] {\ensuremath {\mathbb {#1}}}
\newcommand {\R} {\mathset {R}}
\newcommand {\N} {\mathset {N}}
\newcommand {\Q} {\mathset {Q}}
\newcommand {\Z} {\mathset {Z}}
\newcommand {\EX} {\mathbf {E}}
\newcommand {\script} [1] {\ensuremath {\mathcal {#1}}}
\newcommand {\etal} {\textit {et al.}}
\newcommand {\eps} {\varepsilon}
\newcommand {\eqdef} {:=}
\newcommand {\boruvka}{Bor\r{u}vka}
\newcommand {\wspd}{\texttt{wspd}}
\DeclareMathOperator {\emst}{emst}
\DeclareMathOperator {\conv}{CH}
\DeclareMathOperator {\argmin}{argmin}
\DeclareMathOperator {\DT}{DT}
\DeclareMathOperator {\UC}{UC}
\DeclareMathOperator {\LC}{LC}

\newtheorem {theorem} {Satz}
\newtheorem {problem}[theorem] {Problem}
\newtheorem {lemma}[theorem] {Lemma}
\newtheorem {observation}[theorem] {Observation}
\newtheorem {corollary}[theorem] {Corollary}
\newtheorem {claim}[theorem] {Behauptung}


\title{Das Offline-Caching Problem}
\author{Wolfgang Mulzer}

\begin{document}
\maketitle

Gegeben seien ein Hauptspeicher mit $n$ Datenw\"ortern und ein
Cache, der $k$ W\"orter zwischenspeichern kann.

Wir wollen eine Zugriffsfolge $d_1, d_2, ­\dots, d_n$ von
$n$ Anfragen auf den Hauptspeicher verarbeiten. Der Zugriff
muss \"uber den Cache erfolgen, d.h., ein Datum muss bei
einem Zugriff im Cache vorhanden sein. Ist dies nicht der
Fall, so m\"ussen wir auf den Hauptspeicher zugreifen
und das Datum nachladen.

Bei einer \emph{Ersetzungsstrategie} handelt es sich um eine
Strategie, die entscheidet, welche Daten im Cache
vorgehalten werden sollen. Bei jedem Zugriff k\"onnen
wir ein Element aus dem Cache entfernen und durch
ein Element aus dem Hauptspeicher ersetzen. Die 
Strategie sagt uns, wie dies von statten gehen soll.
Ziel ist, die Anzahl der Hauptspeicherzugriffe 
zu minimieren.

Eine Ersetzungstrategie hei\ss{}t \emph{reduziert}, wenn sie nur
dann ein Element aus dem Hauptspeicher l\"adt, wenn auf
dieses zugegriffen wird und es nicht im Cache vorhanden
ist. Die Anzahl der Hauptspeicherzugriffe entspricht dann
der Anzahl der Cache-Misses.

\begin{claim}\label{beh:reduziert}
Jede Ersetzungsstrategie $S$ l\"asst sich in eine
reduzierte Strategie \"uberf\"uhren, die 
h\"ochstens so viele Speicherzugriffe 
durchf\"uhrt wie $S$.
\end{claim}

Nun betrachten wir die folgende reduzierte Erzetzungstrategie
SFF (furthest in the future Regel): Bei jedem Cache-Miss, 
entferne dasjenige Element aus dem Cache, dessen n\"achster 
Zugriff am weitesten in der Zukunft liegt.

\begin{theorem}
Die Strategie SFF minimiert die Anzahl der 
Hauptspeicherzugriffe.
\end{theorem}

Der Beweis benutzt das folgende 

\begin{lemma}[Austauschlemma]
Sei $d_1, d_2, \dots, d_n$ eine Folge von
Speicherzugriffen und $S$ eine reduzierte Ersetzungstrategie,
die mit SFF bei den ersten $j$ Zugriffen übereinstimmt.
Dann existiert eine reduzierte Strategie $S'$, die mit
SFF bei den ersten $j+1$ Zugriffen \"ubereinstimmt, und
h\"ochstens so viele Hauptspeicherzugriffe durchf\"uhrt
wie $S$.
\end{lemma}

\begin{proof}
Betrachte den Zugriff $d_{j+1}$. Da $S$ und SFF bis jetzt
dasselbe getan haben, muss der Cache f\"ur beide Strategien
bei diesem Zugriff den gleichen Inhalt besitzen.

Wenn $d_{j+1}$ im Cache vorhanden ist, so tun SFF und $S$ nichts
(weil $S$ reduziert ist), und wir k\"onnen $S' = S$ w\"ahlen.

Wenn $d_{j+1}$ nicht im Cache vorhanden ist, so m\"ussen SFF und
$S$ ein Element aus dem Cache entfernen und es durch $d_{j+1}$
ersetzen. Wenn beide Strategien das gleiche Element w\"ahlen,
so setzen wir wieder $S'= S$ und sind fertig.

Also nehmen wir an, dass $S$ das Element $e$ entfernt, w\"ahrend
SFF das Element $f$ entfernt. Wir beschreiben nun die 
Konstruktion von $S'$. In den ersten $j+1$ Schritten stimmt $S'$
mit SFF \"uberein. Danach verh\"alt sich $S'$ zun\"achst 
genauso wie $S$. Solange die Elemente $e$ und $f$ keine 
Rolle spielen, sind die Caches von $S$ und $S'$ fast
gleich, blo\ss{} dass der Cache von $S$ das Element $f$ 
enth\"alt und der Cache von $S'$ das Element $e$. 
Ein Problem gibt es erst, wenn zum ersten Mal einer
der folgenden F\"alle eintritt:

\begin{enumerate}
\item Zugriff auf ein Element $g \neq e,f$, das nicht im Cache
ist, und $S$ entfernt $f$. Dann entfernt $S'$ das Element $e$. Danach
sind die Caches gleich, und $S'$ kann sich wie $S$ verhalten.
Die Anzahl der Cache-Misses von $S'$ und $S$ ist gleich.

\item Zugriff auf das Element $e$. Das ergibt einen Cache Miss
bei $S$, aber nicht bei $S'$. Nehmen wir an, $S$ entfernt
das Element $g$ aus dem Cache, um $e$ einzulagern. Es
gibt zwei F\"alle:

\begin{enumerate}
\item $g = f$: Dann sind hinterher die Caches von $S$ und $S'$ 
gleich, und $S'$ kann sich danach komplett wie $S$ verhalten.
Die Stratege $S'$ hat sogar weniger Cache-Misses als $S$.

\item $g \neq f$: Nun entfernt $S'$ das Element $g$ aus dem Cache und 
l\"adt statt dessen $f$. Danach sind die Caches wieder gleich und $S'$
kann von nun an $S$ simulieren und hat die gleiche Anzahl
von Speicherzugriffen. Leider ist das so konstruierte
$S'$ keine reduzierte Strategie. Wir k\"onnen aber 
Behauptung~\ref{beh:reduziert}
benutzen, um aus $S'$ eine reduzierte Strategie zu machen,
ohne die Anzahl der Speicherzugriffe zu erh\"ohen und ohne die
ersten $j+1$ Ersetzungen zu \"andern.
\end{enumerate}

\item Zugriff auf das Element $f$. Dieser Fall kann nicht eintreten,
da wir nach Konstruktion von SFF erst auf $e$ zugreifen, bevor wir
auf $f$ zugreifen.
\end{enumerate}
\end{proof}

Um die Optimalit\"at von SFF zu beweisen, kann man nun eine optimale 
reduzierte Strategie $S^*$ nehmen und mit dem Austauschlemma sukzessive 
in SFF \"uberf\"uhren. Da sich die Anzahl der Speicherzugriffe nicht 
erh\"oht, ist auch SFF optimal.
Man kann auch eine optimale reduzierte Strategie $S^*$ nehmen, die 
auf einem maximalen Pr\"afix von Zugriffen mit SFF \"ubereinstimmt. 
Wenn $S^* = \text{SFF}$ ist, sind wir fertig. 
Der Fall $S^* \neq \text{SFF}$ ist aber unm\"oglich, weil
wir sonst durch das Austauschlemma die L\"ange der \"Ubereinstimmung
erh\"ohen k\"onnten, ohne die Anzahl der Speicherzugriffe zu \"andern.
\end{document}