OSS 10

1 files changed, 111 insertions, 0 deletions

diff --git a/ws2015/oss/blaetter/10/abgabe.md b/ws2015/oss/blaetter/10/abgabe.md
new file mode 100644
index 0000000..530ce2d
--- /dev/null
+++ b/ws2015/oss/blaetter/10/abgabe.md
@@ -0,0 +1,111 @@
+---
+header-includes:
+  - \usepackage{tikz}
+  - \usetikzlibrary{petri}
+  - \usepackage[ngerman]{babel}
+---
+# Petrinetze und Erreichsbarkeitsgraphen
+
+a)
+
+\begin{figure}[!h]
+\centering
+\begin{tikzpicture}
+\node [place, tokens=1, label=right:$BS$] (bs) at (0.5,0) {};
+\node [place] (p1) at (0, 2) {$P_1$};
+\node [place] (p2) at (1, 2) {$P_2$};
+
+\node [transition] (t1) at (0,1) {$T_1$}
+  edge [pre] (bs)
+  edge [post] (p1);
+
+\node [transition] (t3) at (1,1) {$T_3$}
+  edge [pre] (bs)
+  edge [post] (p2);
+
+\node [transition] (t4) at (1, 3) {$T_4$}
+  edge [pre] (p2)
+  edge [post, bend left=45] (bs);
+
+\node [transition] (t2) at (0, 3) {$T_2$}
+  edge [pre] (p1)
+  edge [post, bend right=45] (bs);
+\end{tikzpicture}
+\caption{Generisches preemptives Multitasking}
+\label{fig:45a}
+\end{figure}
+
+Die Stelle $BS$ steht für die Betriebsystemsfunktionen, $P_1$ für den ersten, und $P_2$ für den zweiten Prozess.
+Hat eine der Stellen eine Marke so heißt dies, dass der jeweilige Prozess bzw.\, die Funktionen momentan ausgeführt werden.
+
+Die Transitionen bezeichnen Prozesswechsel.
+
+b)
+
+\begin{figure}[!h]
+\centering
+\begin{tikzpicture}
+\node [place, tokens=1, label=right:$BS_1$] (bs1) at (1,0) {};
+\node [place, label=left:$BS_2$] (bs2) at (0,0) {};
+\node [place] (p1) at (0, 2) {$P_1$};
+\node [place] (p2) at (1, 2) {$P_2$};
+
+\node [transition] (t1) at (0,1) {$T_1$}
+  edge [pre] (bs1)
+  edge [post] (p1);
+
+\node [transition] (t3) at (1,1) {$T_3$}
+  edge [pre] (bs2)
+  edge [post] (p2);
+
+\node [transition] (t4) at (1, 3) {$T_4$}
+  edge [pre] (p2)
+  edge [post, bend left=45] (bs1);
+
+\node [transition] (t2) at (0, 3) {$T_2$}
+  edge [pre] (p1)
+  edge [post, bend right=45] (bs2);
+\end{tikzpicture}
+\caption{Round-Robin Scheduling}
+\label{fig:45b}
+\end{figure}
+
+Sowohl $BS_1$ als auch $BS_2$ bezeichnen hier Betriebssystemsfunktionen tragen jedoch zusätzlich die Information welcher Prozess vom Round-Robin Verfahren als nächstes ausgewählt wird.
+
+c)
+
+
+\begin{figure}[!h]
+\centering
+\begin{tikzpicture}
+\node (A) {$M_0 = (1, 0, 0, 0)$};
+\node (B) [below of=A] {$M_1 = (0, 0, 1, 0)$};
+\node (C) [below of=B] {$M_2 = (0, 1, 0, 0)$};
+\node (D) [below of=C] {$M_3 = (0, 0, 0, 1)$};
+
+\draw[thick, ->] (A) -- node[right] {$T_1$} ++ (B);
+\draw[thick, ->] (B) -- node[right] {$T_2$} ++ (C);
+\draw[thick, ->] (C) -- node[right] {$T_3$} ++ (D);
+\draw[thick, ->] (D) to [bend right=90] node[midway,left] {$T_4$} (A);
+\end{tikzpicture}
+\caption{Erreichbarkeitsgraph für das Petrinetz aus Abbildung \ref{fig:45b}. Das Format ist $M_n = (BS_1, BS_2, P_1, P_2)$}
+\label{fig:45c}
+\end{figure}
+
+d) Damit mindestens ein Prozess verhungern könnte müsste es einen Pfad geben, der nur endlich oft durch eine Markierung läuft, die eine Marke für den betrachteten Prozess gesetzt hat.
+
+Es gibt in Abbildung \ref{fig:45c} nur einen geschlossenen Pfad, der sowohl $M_1$ als auch $M_3$ trifft.
+Insbesondere ist obig beschriebene Situation für keinen der beiden Prozesse der Fall.
+
+e) Eine Verklemmung könnte genau dann auftreten, falls es in Abbildung \ref{fig:45c} eine Markierung gäbe, die keine Folgemarkierung hat---Dies ist nicht der Fall.
+
+Eine Teilweise Verklemmung könnte genau dann auftreten, falls es in Abbildung \ref{fig:45c} eine Markierung gäbe, die nicht durch das Schalten von endlich vielen Transaktionen von jeder anderen Markierung erreichbar wäre.
+Da der Erreichbarkeitsgraph genau aus einem zyklischen Pfad besteht, der alle Markierungen enthält, ist dies nicht der Fall.
+
+# Multiprocessing
+
+a) Die neu hinzukommenden Marken dürfen die Kapazität der Stelle nicht überschreiten
+b) $M(s) - W(s,t)$
+c) Der gemeinsam genutzte Speicherbereich muss immer genau zu 60% gefüllt sein
+d) (iii)
+e) Es enthält eine teilweise Verklemmung