\documentclass{uebungsblatt}
\author{Marek Kubica, kubica@in.tum.de}
\fach{Grundlagen Betriebssysteme}
\blatt{5}
\gruppe{22}
\usepackage{listings}
\usepackage{tikz}

\begin{document}

\aufgabe

\teilaufgabe

\begin{tabular}{r|r|r}
$e_1$ & Laura und Fred vor der Bank & $a_1$\\
$e_2$ & Fred geht zu Schalter A & $a_2$\\
$e_3$ & Laura geht zu Schalter B & $a_2$\\
$e_4$ & Fred geht zu Schalter B & $a_2$\\
$e_5$ & Laura geht zu Schalter A & $a_2$\\
$e_6$ & Fred wird an Schalter A beraten & $a_3$\\
$e_7$ & Fred wird an Schalter B beraten & $a_3$\\
$e_8$ & Laura wird an Schalter A beraten & $a_3$\\
$e_9$ & Laura wird an Schalter B beraten & $a_3$\\
$e_{10}$ & Fred ist fertig & $a_4$\\
$e_{11}$ & Laura ist fertig & $a_4$\\
$e_{12}$ & Laura und Fred verlassen die Bank & $a_5$
\end{tabular}

\teilaufgabe

$e_1 \leq e_2$, $e_1 \leq e_3$, $e_1 \leq e_4$, $e_1 \leq e_5$, $e_1 \leq e_6$,
$e_3 \leq e_9$, $e_4 \leq e_7$, $e_5 \leq e_8$, $e_6 \leq e_{10}$, $e_8 \leq e_{11}$,
$e_9 \leq e_{11}$, $e_{10} \leq e_{12}$ $e_{11} \leq e_{12}$

\teilaufgabe

\begin{tikzpicture}
  [node distance=1.5cm,
   re/.style={<-,shorten <=1pt,>=stealth’,semithick},
   post/.style={->,shorten >=1pt,>=stealth’,semithick}]

  \node (e1) {$e_1$};
  \node (e3) [above right of=e1] {$e_3$};
  \node (e2) [above of=e3] {$e_2$};
  \node (e4) [below right of=e1] {$e_4$};
  \node (e5) [below of=e4] {$e_5$};

  \node (e6) [right of=e2] {$e_6$};
  \node (e9) [right of=e3] {$e_9$};
  \node (e7) [right of=e4] {$e_7$};
  \node (e8) [right of=e5] {$e_8$};

  \node (e10) [right of=e9] {$e_{10}$};
  \node (e11) [right of=e7] {$e_{11}$};

  \node (e12) [below right of=e10] {$e_{12}$};

  \draw [->] (e1) to (e2);
  \draw [->] (e1) to (e3);
  \draw [->] (e1) to (e4);
  \draw [->] (e1) to (e5);

  \draw [->] (e2) to (e6);
  \draw [->] (e3) to (e9);
  \draw [->] (e4) to (e7);
  \draw [->] (e5) to (e8);

  \draw [->] (e6) to (e10);
  \draw [->] (e9) to (e11);
  \draw [->] (e7) to (e10);
  \draw [->] (e8) to (e11);

  \draw [->] (e10) to (e12);
  \draw [->] (e11) to (e12);
\end{tikzpicture}

\teilaufgabe

Gegenseitige Nebenläufigkeit von $e_2$, $e_6$, $e_{10}$ zu $e_3$, $e_9$, $e_{11}$
sowie $e_4$, $e_7$, $e_{10}$ zu $e_5$, $e_8$, $e_{11}$.

\teilaufgabe

$P_1^\prime$: $e_1 \rightarrow e_2 \rightarrow e_6 \rightarrow e_3 \rightarrow e_9
\rightarrow e_{10} \rightarrow e_{11} \rightarrow e_{12}$

Algorithmus: Für jedes Element, das von keinem voerherigen Ereignis abhängt:
Führe es aus und lösche Abhängigkeit zu diesem Ereignis aus der Abhängigkeits-Liste
aller anderen Ereignisse. Wiederhole, bis alle Ereignisse durchgelaufen sind.

\teilaufgabe

$2 * 6!$ Möglichkeiten

\teilaufgabe

Annahme: Menge aller Sequentialisierungen beschreibt Prozess nicht eindeutig.

Folge: Prozess lässt sich in einer Reihenfolge ausführen, die nicht einer seiner 
Sequentialisierungen entspricht. Diese Ausfürung wäre allerdings wieder eine 
Sequentialisierung des Prozesses. Widerspruch zur Annahme!


\teilaufgabe

1.2 beschreibt einen Zustandsautomaten wenn man die Zweige $e_2$ mit $e_3$,
$e_6$ mit $e_9$, $e_{10}$ mit $e_{11}$, $e_4$ mit $e_5$, $e_7$ mit $e_8$ zu
Knoten zusammenfasst.

\aufgabe

\teilaufgabe

\begin{enumerate}
  \item \textbf{Race condition}: ein unerwarteter Fall, der nur bei einer speziellen,
    meist unerwarteten Reihenfolge der Threadausführung auftritt
  \item \textbf{Mutual exclusion}: Wenn mehrere Threads den Zugriff auf eine
    exklusive Resource benötigen, ist es notwendig dass sie sichergehen, dass sie
    diese Resource nicht beide zur gleichen Zeit nutzen -- sie müssen sich also
    wechselseitig ausschließen.
  \item \textbf{Critical region/section}: Codeabschnitt, der nur von einem Thread
    zum gleichen Zeitpunkt ausgeführt werden darf.
  \item \textbf{Busy waiting}: Warten auf eine Resource in einer Endlosschleife
  \item \textbf{Deadlock}: Wenn ein Thread auf eine bestimmte Aktion eines anderen
    Threads wartet und der andere Thread wiederrum auf den ersten Thread wartet.
\end{enumerate}

\teilaufgabe

\begin{enumerate}
  \item Höhere Ressourcenbelegung, Deadlocks
  \item Ohne atomare Befehle wie TSL wirds schwerer, Multiprozessoren machen
    Speicherzugriff zudem noch komplizierter
  \item Ja, es reichen aber atomare Operationen aus.
\end{enumerate}

\teilaufgabe

\begin{enumerate}
  \item Zwischen der Prüfung im While-Kopf und dem blokieren des anderen
    Prozesses kann ein Threadwechsel stattfinden und der andere Thread
    greift auf den kritischen Bereich zu. Daraufhin wechselt der Kontext
    wieder und beide Threads sind also im kritischen Bereich. Fail!
  \item Ohne TSL oder ähnlichen Befehl nicht möglich, da es sich womöglich
    um Mehrkern/Mehrprozessorsysteme handelt.
\end{enumerate}

\teilaufgabe

\begin{lstlisting}
P1 & P2
BEGIN
P();
-- kritischer Bereich
V();
END;
\end{lstlisting}

\aufgabe

\teilaufgabe

Der Graph sieht kreisförmig aus. Eine Kante von einer Ressource (Straße) zu
einem Prozess (Auto) bedeutet dabei, dass die Ressource das Auto am fahren
hindert, weil keine Vorfahrt gewährt wird. Jede Ressource wird von genau einem
Auto belegt, und jeder Prozess fordert genau eine Ressource (``links'' von
sich) an.

\teilaufgabe

\begin{itemize}
  \item Kreuzung nicht exklusiv machen / mehrere Ebenen / Autobahnkreuz-Modell
  \item Kreuzung durch Ampel regeln / unterbrechbar machen
  \item Straßen Prioritäten zuordnen
  \item Zyklus entfernen
\end{itemize}

\end{document}
