---
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 \} \cup U \cup 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)