<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">\begin{slide}{Mark/Sweep}

Plan: wenn Speicher voll, dann:
\begin{itemize}\itemsep 2pt
\item alle lebenden Zellen markieren
\item alle nicht markierten Zellen in Freispeicherliste
\end{itemize}

Problem: zum Markieren muÃŸ man den Graphen durchqueren,
man hat aber keinen Platz (z. B. Stack),
um das zu organisieren.

\bigskip

LÃ¶sung:

H. Schorr, W. Waite: 
\emph{An efficient machine-independent
procedure for garbage collection in various list structures},
Communations of the ACM, 10(8):481-492, August 1967.

temporÃ¤re Ã„nderungen im Graphen selbst (pointer reversal)

\end{slide}

\begin{slide}{Pointer Reversal (Invariante)}

ursprÃ¼nglicher Graph $G_0$, aktueller Graph $G$:

Knoten (cons) mit zwei Kindern (head, tail), markiert mit 
\begin{itemize}\itemsep 0pt
\item 0: noch nicht besucht
\item 1: head wird besucht (head-Zeiger ist invertiert)
\item 2: tail wird besucht (tail-Zeiger ist invertiert)
\item 3: fertig
\end{itemize}

globale Variablen $p$ (parent), $c$ (current).

Invariante: man erhÃ¤lt $G_0$ aus $G$, wenn man
\begin{itemize}
\item head/tail-Zeiger aus 1/2-Zellen (nochmals) invertiert
\item und Zeiger von $p$ auf $c$ hinzufÃ¼gt.
\end{itemize}

\end{slide}

\newcommand{\Mark}{\operatorname{mark}}
\newcommand{\Head}{\operatorname{head}}
\newcommand{\Tail}{\operatorname{tail}}

\begin{slide}{Pointer Reversal (Ablauf)}

  \begin{itemize}\itemsep 2pt
  \item pre: $p = $ null, $c=$ root, $\forall z: \Mark(z)=0$
  \item post: $\forall z: \Mark(z)=
    \text{if}~ (\text{root}\to^* z)~ \text{then} ~3 ~\text{else}~ 0 $
  \end{itemize}

Schritt (neue Werte immer mit $'$): falls $\Mark(c)=$ \dots
\begin{itemize}
\item 0: $c' = \Head(c); \Head'(c)=p; \Mark'(c)=1; p'=c;$
\item 1,2,3: falls $\Mark(p)=\dots$
  \begin{itemize}
  \item 1: $\Head'(p)=c;\Tail'(p)=\Head(p);\Mark'(p)=2;c'=\Tail(p);p'=p$
  \item 2: $\Tail'(p)=c;\Mark'(p)=3;p'=\Tail(p);c'=p;$
  \end{itemize}
\end{itemize}

Knoten werden in Tiefensuch-Reihenfolge betreten.

\end{slide}

\begin{slide}{Eigenschaften Mark/Sweep}

  \begin{itemize}\itemsep 2pt
  \item benÃ¶tigt 2 Bit Markierung pro Zelle, aber keinen weiteren Zusatzspeicher
  \item Laufzeit fÃ¼r mark $\sim$ $|$ lebender Speicher $|$
  \item Laufzeit fÃ¼r sweep  $\sim$ $|$ gesamter Speicher $|$
  \item Fragmentierung (Freispeicherliste springt)
  \end{itemize}

Ablegen von Markierungs-Bits:
\begin{itemize} \itemsep 2pt
\item in Zeigern/Zellen selbst 

(Beispiel: Rechner mit Byte-Adressierung, aber Zellen immer
auf Adressen $\equiv 0\pmod 4$: zwei LSB sind frei.)
\item in separaten Bitmaps
\end{itemize}

\end{slide}
</pre></body></html>