OSS - 08

1 files changed, 150 insertions, 0 deletions

diff --git a/ws2015/oss/blaetter/08/abgabe.md b/ws2015/oss/blaetter/08/abgabe.md
new file mode 100644
index 0000000..f216bb5
--- /dev/null
+++ b/ws2015/oss/blaetter/08/abgabe.md
@@ -0,0 +1,150 @@
+---
+header-includes:
+  - \usepackage{tikz}
+  - \usepackage[ngerman]{babel}
+---
+# Preemptives Scheduling
+
+a)
+
+\begin{figure}[!h]
+\centering
+\begin{tikzpicture}
+  \draw[thick, <->] (0, 6) -- (0, 0) -- (9.5, 0);
+  \foreach \x in {1, 2, 3, 4, 5}
+    \draw[thick] (-1pt, \x) -- (1pt, \x) node [anchor=east] {$P_{\x}$};
+  \foreach \x in {0, ..., 18}
+    \draw[thick] ({\x / 2}, -1pt) -- ({\x / 2}, 1pt) node [anchor=north] {$\x$};
+
+  \draw[xstep=0.5, ystep=1, gray, very thin] (0, 5) grid (9, 0); 
+
+  \draw[|-|] (0, 1) -- (1, 1);
+
+  \draw[|-|] (1, 2) -- (3, 2);
+
+  \draw[|-|, dashed] (1, 3) -- (5.5, 3);
+  \draw[|-|] (5.5, 3) -- (9, 3);
+
+  \draw[|-|, dashed] (2, 4) -- (4, 4);
+  \draw[|-|] (4, 4) -- (5.5, 4);
+
+  \draw[|-|, dashed] (2.5, 5) -- (3, 5);
+  \draw[|-|] (3, 5) -- (4, 5);
+\end{tikzpicture}
+\caption{SRPT}
+\label{fig:srpt}
+\end{figure}
+
+b)
+
+\begin{figure}[!h]
+\centering
+\begin{tikzpicture}
+  \draw[thick, <->] (0, 6) -- (0, 0) -- (9.5, 0);
+  \foreach \x in {1, 2, 3, 4, 5}
+    \draw[thick] (-1pt, \x) -- (1pt, \x) node [anchor=east] {$P_{\x}$};
+  \foreach \x in {0, ..., 18}
+    \draw[thick] ({\x / 2}, -1pt) -- ({\x / 2}, 1pt) node [anchor=north] {$\x$};
+
+  \draw[xstep=0.5, ystep=1, gray, very thin] (0, 5) grid (9, 0); 
+
+  \draw[|-|] (0, 1) -- (1, 1);
+
+  \draw[|-|, dashed] (1, 2) -- (6, 2);
+  \draw[|-|] (1, 2) -- (2, 2);
+  \draw[|-|] (5, 2) -- (6, 2);
+
+  \draw[|-|, dashed] (1, 3) -- (9, 3);
+  \draw[|-|] (2, 3) -- (3, 3);
+  \draw[|-|] (6, 3) -- (7, 3);
+  \draw[|-|] (7.5, 3) -- (9, 3);
+
+  \draw[|-|, dashed] (2, 4) -- (7.5, 4);
+  \draw[|-|] (3, 4) -- (4, 4);
+  \draw[|-|] (7, 4) -- (7.5, 4);
+
+  \draw[|-|, dashed] (2.5, 5) -- (4, 5);
+  \draw[|-|] (4, 5) -- (5, 5);
+\end{tikzpicture}
+\caption{RR}
+\label{fig:rr}
+\end{figure}
+
+c) Es seien $W(P_n)$, $V(P_n)$, $W^\prime(P_n)$, und $V^\prime(P_n)$ die Wartezeit und die Verweilzeit des Prozesses $P_n$ für SRPT und RR.
+
+\begin{align*}
+\frac{\sum_{i = 1}^n W(P_n)}{5} &= \frac{0 + 0 + 9 + 4 + 1}{5} = \frac{14}{5} = 2.8 \\
+\frac{\sum_{i = 1}^n V(P_n)}{5} &= \frac{2 + 4 + 16 + 7 + 3}{5} = \frac{32}{5} = 6.4
+\\
+\frac{\sum_{i = 1}^n W^\prime(P_n)}{5} &= \frac{0 + 6 + 9 + 8 + 3}{5} = \frac{26}{5} = 5.2 \\
+\frac{\sum_{i = 1}^n V^\prime(P_n)}{5} &= \frac{2 + 10 + 16 + 11 + 5}{5} = \frac{44}{5} = 8.8
+\end{align*}
+
+d) Ist die maximale Bedienzeit der Prozesse kleiner als die Zeitscheibe wird RR identisch zu FCFS.
+
+# Prozessfortschrittsdiagramm
+
+a) Wir bezeichnen mit $G_n$ das Erfassen des Betriebsmittels $n$ und mit $F_n$ das Freigeben des BM $n$.
+
+\begin{figure}[!h]
+\centering
+\begin{tikzpicture}
+  \draw[thick, <->] (-0.25, 6.25) node [anchor=south] {$A$} -- (-0.25, -0.25) -- (5.25, -0.25) node [anchor=west] {$B$};
+  \draw[step=0.5, gray, very thin] (-0.25,6) grid (5, -0.25);
+
+  \draw[thick] (0, -0.20) -- (0, -0.30) node[anchor=north] {$0$};
+  \draw[thick] (-0.20, 0) -- (-0.30, 0) node[anchor=east] {$0$};
+
+  \draw[thick] (2.5, -0.20) -- (2.5, -0.30) node[anchor=north] {$G_1$}; 
+  \draw[thick] (4, -0.20) -- (4, -0.30) node[anchor=north] {$F_1$}; 
+
+  \draw[thick] (2, -0.20) -- (2, -0.30) node[anchor=north] {$G_2$}; 
+  \draw[thick] (3.5, -0.20) -- (3.5, -0.30) node[anchor=north] {$F_2$}; 
+
+  \draw[thick] (0.5, -0.20) -- (0.5, -0.30) node[anchor=north] {$G_3$}; 
+  \draw[thick] (1.5, -0.20) -- (1.5, -0.30) node[anchor=north] {$F_3$}; 
+
+  \draw[thick] (-0.20, 1) -- (-0.30, 1) node[anchor=east] {$G_1$};
+  \draw[thick] (-0.20, 3) -- (-0.30, 3) node[anchor=east] {$F_1$}; 
+
+  \draw[thick] (-0.20, 2) -- (-0.30, 2) node[anchor=east] {$G_2$};
+  \draw[thick] (-0.20, 3.5) -- (-0.30, 3.5) node[anchor=east] {$F_2$}; 
+
+  \draw[thick] (-0.20, 0.5) -- (-0.30, 0.5) node[anchor=east] {$G_3$};
+  \draw[thick] (-0.20, 1.5) -- (-0.30, 1.5) node[anchor=east] {$F_3$}; 
+
+  \draw[thick] (2.5, 1) rectangle (4, 3);
+  \draw[thick] (2, 2) rectangle (3.5, 3.5);
+  \draw[thick] (0.5, 0.5) rectangle (1.5, 1.5);
+
+  \draw[thick, dashed] (2, 2) rectangle (2.5, 1);
+
+  \draw[->] (0, 0) -- (5, 0) -- (5, 3) node[anchor=west] {$p_1$} -- (5, 5.9);
+  \draw[->] (0, 0) -- (0, 6) -- (2.5, 6) node[anchor=south] {$p_2$} -- (4.9, 6);
+
+  \draw[dashed, ->] (0,0) -- (0.25, 0.25) -- (1.75, 0.25) -- (1.75, 3) node[anchor=east] {$p^\prime$} -- (1.75, 5.75) -- (4.75, 5.75) -- (4.9, 5.9);
+\end{tikzpicture}
+\caption{Prozessfortschrittsdiagramm}
+\begin{minipage}{\textwidth}
+\centering
+\footnotesize
+Wir bezeichnen mit \begin{tikzpicture}[baseline] \draw[thick] (0,0) rectangle (20pt, 6pt); \end{tikzpicture} unmögliche und mit \begin{tikzpicture}[baseline] \draw[thick, dashed] (0,0) rectangle (20pt, 6pt); \end{tikzpicture} unsichere Bereiche.
+\end{minipage}
+\label{fig:pfd}
+\end{figure}
+
+Es kann, wird der in Abbildung \ref{fig:pfd} mit einem gestrichelten Rechteck markierte Bereich *betreten* ein Deadlock auftreten.
+
+b) Bei nicht-preemptiven Scheduling (Pfade $p_1$ und $p_2$ in Abbildung \ref{fig:pfd}) kann es nicht zu einem Deadlock kommen, da, sobald $B$ zur Ausführung kommt (O.b.d.a. wird $A$ zuerst ausgeführt), alle locks bereits released sind.
+
+c) Bei preemptiven Scheduling können alle in Abbildung \ref{fig:pfd} eingezeichneten Pfade ($p_1$, $p_2$, und $p^\prime$) genommen werden.
+
+Die Zahl der möglichen Pfade ist die Zahl der Zusammenhangskomponenten von $\{ (a, b) \ | \ a < 0 \land b < 0 \} \cap U \cap U^\prime$ wobei $U$ die Vereinigung aller Unmöglichen Bereiche und $U^\prime$ die Vereinigung aller Unsicheren Bereiche bezeichnet
+
+# Scheduling
+
+(a) Preemptive Scheduling
+(b) Einhaltung von Fristen
+(c) Ankunftszeit
+(d) $\text{Verweildauer} = \text{Wartezeit} + \text{Bedienzeit}$
+(e) Shortest Remaining Processing Time (SRPT)