From da8c58f78b90736b028f265153a6d050f5b049f7 Mon Sep 17 00:00:00 2001 From: Gregor Kleen Date: Wed, 9 Dec 2015 16:54:21 +0100 Subject: OSS - 08 --- ws2015/oss/blaetter/08/abgabe.md | 150 +++++++++++++++++++++++++++++++++++++++ 1 file changed, 150 insertions(+) create mode 100644 ws2015/oss/blaetter/08/abgabe.md (limited to 'ws2015/oss/blaetter/08/abgabe.md') 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) -- cgit v1.2.3