\begin{slide}{Non-Blocking Queue (Problem)}


\begin{itemize}
\item einfach verkettete Liste
\begin{verbatim}
private static class Node<E> {
   E item; AtomicReference<Node<E>> next; }
\end{verbatim}
\item Zeiger \verb|head,tail| auf Anfang/Ende,
  benutze Sentinel (leerer Startknoten)
\end{itemize}

Auslesen (am Anfang) ist leicht,

Problem beim Einfügen (am Ende):
\begin{itemize}
\item zwei Zeiger \verb|next| und \verb|tail|
  müssen geändert werden,
\item aber wir wollen keinen Lock benutzen.
\end{itemize}



\end{slide}

\begin{slide}{Non-Blocking Queue (Lösung)}

\parskip 5mm

(Michael and Scott, 1996)
\url{http://www.cs.rochester.edu/research/synchronization/pseudocode/queues.html}

Idee: die zwei zusammengehörigen Änderungen 
  mglw. durch verschiedene Threads ausführen (!)

  Queue hat zwei Zustände:
  \begin{itemize}
  \item A: tail zeigt auf letzten Knoten
  \item B: tail zeigt auf vorletzten Knoten
  \end{itemize}

wer B bemerkt, muß reparieren.

in Java realisiert als ConcurrentLinkedQueue
\end{slide}
