\begin{slide}{Fünf Philosophen}

ein klassisches Beispiel für multi-threading:

\begin{itemize}
\item
  5 Philosophen. 

  Jeder einzelne:
  denkt, wird hungrig, ißt, denkt, wird hungrig, ißt, \dots
\item
  runder Tisch, in der Mitte ein Topf Spaghetti
  (wird nie alle)
\item
  es gibt zwischen je zwei Tellern genau eine Gabel,
  zum Essen benötigt man beide.
\end{itemize}

Die Ressourcen (Gabeln) müssen den Clients (Philosophen)
sinnvoll zugeteilt werden,
\emph{so daß keiner verhungert}.
\end{slide}


\begin{slide}{Eine Gabel (im Prinzip)}

\begin{verbatim}
class Fork {
    private int me;
    String id () { return "Fork-" + me; }
    private boolean taken;
    Fork (int m) { me = m; taken = false; }

    synchronized void drop (Philo p) { .. }
    synchronized void take (Philo p) { .. }
}
\end{verbatim}
 
\end{slide} 

\begin{slide}{Ein Philosoph (im Prinzip)}
\begin{verbatim}
class Philo implements Runnable {
  private int me;
  String id () { return "Philo-" + me; }
  private Fork left; private Fork right;
  Philo ( int m, Fork l, Fork r ) {
      me = m; left = l; right = r;
  }
  public void run () { 
    while (true) {
      right.take (this); left.take (this);
      right.drop (this); left.drop (this);
    } 
  }
}
\end{verbatim}
\end{slide}

\begin{slide}{Das Hauptprogramm}
\begin{verbatim}
class Philo { ...
  public static void main (String [] argv) {
    int size = 5;
    Fork  fo [] = new Fork  [size];
    for (int i=0 ; i<size; i++) {
      fo[i] = new Fork (i);
    }
    Philo ph [] = new Philo [size];
    for (int i=0 ; i<size; i++) {
      ph[i] = new Philo 
         (i, fo[i], fo[(i+1) % size]);
      new Thread (ph[i]).start ();
} } }
\end{verbatim}
\end{slide}


\begin{slide}{Eine Gabel (genauer)}

\begin{verbatim}
class Fork {
  boolean taken;
  synchronized void drop (Philo p) {
    taken = false;
    notify ();
  }
  synchronized void take (Philo p) {
    while (taken) {
        wait ();
    }
    taken = true;
  }
}
\end{verbatim}
\end{slide}

\begin{slide}{Eine Gabel (wait/notify)}

Durch \verb|wait()| wird der aufrufende Thread angehalten
(er wartet auf das Objekt (die Gabel)).

Jedes Objekt hat eine Warteschlange von Threads.

Durch \verb|notify| wird \emph{irgendein}
Thread aus der Warteschlange ausgewählt und fortgesetzt.

\end{slide}


\begin{slide}{Gefahr 1: Deadlock (Verklemmen)}

  \begin{itemize}
  \item wechselseitiger Ausschluß 
    (jede Ressource von nur einem Prozeß benutzbar)
  \item besitzen und warten
    (Prozeß besitzt bereits Ressourcen und wartet auf weitere)
  \item kein Ressourcenentzug
    (kein anderer als der Besitzer-Prozeß selbst
    kann die Ressource freigeben)

    (beachte: bis hierher sind es sehr vernünftige Forderungen)
  \item Zyklisches Warten
    (jeder Prozeß besitzt wenigstens eine Ressource,
    auf die ein andere wartet)
  \end{itemize}
\end{slide}

\begin{slide}{Gefahr 2: Unfairness (Verhungern)}

  falls es einen Ablauf der Ereignisse gibt,
  bei dem wenigstens ein Prozeß
  nie die gewünschten Ressourcen erhält.

  (\dots weil ihm die anderen abwechselnd alles wegnehmen)

\end{slide}



\begin{slide}{Deadlock?}

Dieser Ansatz hat Deadlock (ausprobieren):
\begin{verbatim}
class Philo {
  void run () {
    while (true) {
      System.out.println (id() + " hat Hunger");
      right.take (this);
      left.take (this);
      System.out.println (id() + " ist satt");
      right.drop (this);
      left.drop (this);
} } }
\end{verbatim}
Wie kann man das verhindern?

\end{slide}


\begin{slide}{Lösungen}

\begin{itemize}
\item
  ein Diener läßt immer höchstens vier Philosophen
  am Tisch platznehmen
\item
  der Philosoph mit Nummer 0 ist Linkshänder 
  ($=$ nimmt linke Gabel zuerst)
\end{itemize}

Beweisen Sie, daß damit Verklemmen und Verhungern 
vermieden werden!

\end{slide}
