1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
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
|
