Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
[ES] Lösungsvorschlag zur Klausur vom 01.04.2015
Anbei mein Lösungsvorschlag zur Klausur in Eingebetteten Systemen vom 1. April 2015. Dieser Vorschlag ist inoffiziell, insbesondere erhebe ich keine Ansprüche auf Vollständigkeit oder Korrektheit. Verbesserungsvorschläge sind erwünscht.
Aufgabe 1. (Spezifikation und Modellierung)
a) Grundlagen
- Graph: siehe Skript zur Einführung, S. 18
- horizontale Pfeile: Verfeinerungsschritte
- vertikale Pfeile: Synthese
-
Falsch, denn das Gewicht der Kante von p2 nach t2 ist ungleich 1.
-
Falsch, denn sobald t2 2 Marken nach t3 transportiert hat, kann t2 nicht mehr feuern.
-
Richtig, denn keine Transition erzeugt mehr Marken, als sie verbraucht. Folglich bleibt die Gesamtanzahl der Marken nach jedem Feuern konstant, also ist der Graph k-beschränkt, wobei k maximal 3 ist.
-
Falsch, die Modellierungsstärke von Statecharts und konventionellen FSMs ist gleich. Statecharts brauchen nur weniger Knoten und Kanten.
b) Statecharts
-
XOR: weniger Kanten, AND: weniger Knoten
Zustände: {CEG, CEH, CFG, CFH, DEG, DEH, DFG, DFH}
Startzustände: {CEG, CEH}
Kanten: {(CEG, DEG, alpha), (CEH, DEH, alpha), (CFG, DFG, alpha), (CFH, DFH, alpha), (DEG, CEG, beta), (DEH, CEH, beta), (DFG, CFG, beta), (DFH, CFH, beta), (CEG, CFG, gamma), (CEH, CFH, gamma), (CFG, CEG, delta), (CFH, CEH, delta), (DFG, DEG, delta), (DFH, DEH, delta), (DEG, DEH, epsilon), (DFG, DFH, epsilon)}
c) Petri-Netze
P = {p1, p2, p3, p4}
T = {t1, t2, t3, t4}
F = {(p1, t1), (p1, t2), (t1, p2), (p2, t2), (t2, p3), (p3, t3), (t3, p1), (t3, p4), (p4, t4), (t4, p1)}
K = {unendlich, unendlich, unendlich, unendlich}
M0 = {2, 0, 0, 0}
W = {1, 1, 1, 1, 1, 1, 1, 1, 1, 1}
- (als Adjazenzliste)
G = (V, E)
V = {(2, 0, 0, 0), (1, 1, 0, 0), (0, 1, 0, 1), (1, 0, 0, 1), (0, 2, 0, 0), (0, 0, 1, 0)}
E = {
(2, 0, 0, 0) => {(1, 1, 0, 0)}
(1, 1, 0, 0) => {(0, 2, 0, 0), (0, 0, 1, 0)}
(0, 2, 0, 0) => {}
(0, 0, 1, 0) => {(1, 0, 0, 1)}
(1, 0, 0, 1) => {(0, 1, 0, 1), (2, 0, 0, 0)}
(0, 1, 0, 1) => {(1, 1, 0, 0)}
}
- nicht konfliktfrei (Verzweigung in t3)
- beschränkt (endlicher Erreichbarkeitsgraph)
- nicht deadlockfrei (ist der Zustand (0, 2, 0, 0) erreicht, so kann keine Transition feuern)
- (als Adjazenzliste)
Die Kanten seien folgendermaßen gespeichert:
e = (n, x1, x2, x3)
- n: Nachfolger der Kante
- x1: Gewicht am Anfang der Kante
- x2: Gewicht am Ende der Kante
- x3: Anzahl der Marken auf der Kante
G = (V, E)
V = {t1, t2, t3, t4, t5}
E = {
t1 => {(t2, 1, 1, 0)}
t2 => {(t2, 2, 2, 2), (t3, 2, 2, 0)}
t3 => {(t4, 3, 1, 0), (t5, 3, 4, 0)}
t4 => {(t1, 1, 2, 2)}
t5 => {}
}
Aufgabe 2. (Architektursynthese)
a) Grundbegriffe
Kostenfunktion: c
Gewichtsfunktion: w
Allokation: alpha
Bindung: beta, gamma
-
Die Latenz L eines Ablaufplans bezeichnet die Anzahl Zeitschritte des kleinsten Intervalls, das benötigt wird, um den gegebenen Ablaufplan auszuführen. L = max(tau(v_i) - d_i) - min(tau(v_i)) über alle Knoten v_i im Sequenzgraph V_S.
-
Für alle Kanten (v_i, v_j) in E_S soll gelten: tau(v_j) - tau(v_i) >= d_i
i)
algebraisch:
G_S = (V_S, E_S)
V_S = {v0, v1, v2, v3, v4, v5, v6, v7, vn)
E_S = {(v0, v1), (v0, v2), (v0, v3), (v0, v4), (v1, v5), (v2, v5), (v3, v6), (v4, v7), (v5, v6), (v6, v7), (v7, vn)}
graphisch: …
ii)
als Adjazenzliste:
G_R = (V_R, E_R)
V_R = {v1, v2, v3, v4, v5, v6, v7, r1, r2}
E_R = {(v1, r1, 1), (v2, r2, 3), (v3, r2, 3), (v4, r2, 3), (v5, r2, 3), (v6, r1, 1), (v7, r1, 1)}
b) Allokation, Ablaufplanung
-
Die Operation v7 soll entweder zum Zeitpunkt 5 oder 6 gestartet werden. Die Mobilität von v7 ist damit 6-5=1 und die Latenzschranke besitzt den Wert von L=6+3=9.
Task | mu(v_i) | tau_1(v_i) | tau_2(v_i)
v1 | 2 | 0 | 2
v2 | 2 | 0 | 2
v3 | 3 | 0 | 3
v4 | 2 | 1 | 3
v5 | 3 | 1 | 4
v6 | 2 | 4 | 6
v7 | 2 | 5 | 7
x_3,0 + x_3,1 + x_3,2 + x_3,3 = 1 => tau(v3) = 0 * x_3,0 + 1 * x_3,1 + 2 * x_3,2 + 3 * x_3,3
x_5,1 + x_5,2 + x_5,3 + x_5,4 = 1 => tau(v5) = 1 * x_5,1 + 2 * x_5,2 + 3 * x_5,3 + 4 * x_5,4
tau(v4) - tau(v1) >= 1
tau(v4) - tau(v2) >= 1
tau(v5) - tau(v2) >= 1
tau(v5) - tau(v3) >= 1
tau(v7) - tau(v5) >= 3
tau(v7) - tau(v6) >= 1
t = 0: x_1,0 + x_2,0 + x_3,0 <= 2
t = 1: x_1,1 + x_2,1 + x_3,1 <= 2
t = 2: x_1,2 + x_2,2 + x_3,2 <= 2
t = 3: x_1,3 + x_2,3 + x_3,3 <= 2
t = 4: x_1,4 + x_2,4 + x_3,4 + x_6,4 <= 2
Die übrigen Ressourcenbedingungen sind immer erfüllt, denn zu keinem Zeitpunkt von 0 bis 4 können mehr als die verfügbaren 2 Multiplizierer benötigt werden.
- minimiere tau(vn) - tau(v0)
c) Bindung
i) Schwache Verträglichkeit:
G = (V, E)
V = {v1, v2, v3, v4, v5, v6, v7}
E = {(v2, v6), (v2, v7), (v6, v7), (v1, v3), (v1, v4), (v1, v5), (v3, v4), (v3, v5), (v4, v5)}
ii) Ablaufplanverträglichkeit:
G = (V, E)
V = {v1, v2, v3, v4, v5, v6, v7}
E = {(v2, v6), (v2, v7), (v6, v7), (v1, v3), (v1, v4), (v1, v5), (v3, v5), (v4, v5)}
iii) Starke Verträglichkeit:
G = (V, E)
V = {v1, v2, v3, v4, v5, v6, v7}
E = {(v2, v6), (v2, v7), (v6, v7), (v1, v4), (v3, v5)}
Aufgabe 3. (Softwaresynthese)
a) Grundbegriffe und Kurzfragen
-
Speicherverwaltung, Prozessverwaltung, Ein-/Ausgabeverwaltung, Sicherheits- und Schutzfunktionen
Wartezeit: t_W(v_i) = tau_e(v_i) - t_r(v_i) - d_i
Überhang: t_T(v_i) = max{0, t_d(v_i) - t_e(v_i)}
Mittlere Antwortzeit: F = (sum for i = 1 to n over tau_e(v_i) - t_r(v_i)) / n
Berechnungszeit: L = max_i(tau_e(v_i)) - min_i(tau_r(v_i))
- Falsch, SRTN minimiert immer die mittlere Antwortzeit
- Richtig
- Falsch, das geht nur bei präemptiven Scheduling
- Richtig
- Richtig
- Falsch, EDF arbeitet mit dynamischen Deadlines
- Richtig
- Falsch, wenn Deadline < Periode ist, ist die Taskmenge nicht mit RM planbar
- Falsch, sie werden mit niedrigster Priorität abgearbeitet
- Wahr
b) Aperiodische Ablaufplanung
t = 0 bis 1: v1
t = 1 bis 3: v2
t = 3 bis 4: v3
t = 4 bis 6: v4
t = 6 bis 7: v2
t = 7 bis 9: v1
t = 9 bis 11: v6
t = 11 bis 12: v1
t = 12 bis 14: v5
t_r(v1) = 0; t_r(v2) = 6; t_r(v3) = 6; t_r(v4) = 4; t_r(v5) = 8; t_r(v6) = 10
t_d(v1) = 5; t_d(v2) = 11; t_d(v3) = 8; t_d(v4) = 7; t_d(v5) = 11; t_d(v6) = 13
t = 0 bis 4: v1
t = 4 bis 6: v4
t = 6 bis 7: v3
t = 7 bis 10: v2
t = 10 bis 12: v5
t = 12 bis 14: v6
=> Der Ablaufplan ist also ungültig, denn die Deadline von v5 wird verletzt.
c) Periodische Ablaufplanung
-
sum for i = 1 to n over d_i / t*_d(v_i) <= n(2^(1/n) - 1)
Linke Seite: 17/12 > 1
Rechte Seite: 4 * (1,189 - 1) < 1
=> kein gültiger Ablaufplan möglich
- Antwort fehlt.
Hey danke erst mal für deine Lösungen! Ich werds leider nicht schaffen, alles aufzudröseln. Wenn ich meine Zusammenfassung noch rechtzeitig fertig bekomme, lade ich sie mal hoch (im anderen Thread mit der Zusammenfassung), damit sollten sich so ziemlich alle Klausurfragen lösen lassen. Bin leider etwas unter Zeitdruck :rolleyes:
Hab eine Frage zu der ersten Aufgabe. Ich finde die Frage mit den Pfeilen im Doppeldachmodell immer so schwammig und ich hab noch nie irgendwo eine eindeutige Lösung gesehen.
Handelt es sich nicht bei horizontalen und vertikalen Pfeilen um eine Synthese? Im Skript steht dazu folgendes: “Aufgabe der Synthese ist die (teil-)automatische Transformation zwischen den verschiedenen Abstraktionsebenen [imho horizontal] und Sichten [imho vertikal].” Oder woher hast du die Antwort mit den Verfeinerungsschritten?
Ich lese das aus Seite 12 im ES Buch. Da steht:
"Anhand dieser Klassifizierung lässt sich der Entwurf eines Komplexen Systems als Abfolge von Verfeinerungsschritten verstehen bei denen einer Verhaltensbeschreibung strukturelle Informationen über die Implementierung zugefügt werden und die entstehenden Teilmodule dann wieder Ausgangspunkte für Verfeinerungen(horizontale Pfeile in Abb. 1.7 (Doppeldachmodell) auf die nächst niedrigere Abstraktionsebene sind.
Bei Aufgabe 3a)
3(10): Ist es nich so, dass die Kapazität beim Deferrable-Server eben NICHT verloren geht? Oder verstehe ich das falsch?
Ja du hast recht, das ist gerade der sinn von dieser Art von Server.
Danke!
Mir ist noch etwas aufgefallen.
Beim ILP bei 5. kann doch in t=3 von den ADDS nur noch x3,3 starten oder?
Selbes gilt in Zeitschritt t=6 für x6,4.
Hier mal die A3)c) 3. Ablaufplan gemäß DM-Algorithmus
t = 0 bis 1 : v1
t = 1 bis 3 : v4
t = 3 bis 4 : v2
t = 4 bis 5 : v1
t = 5 bis 6 : v2
t = 6 bis 7 : v3
t = 7 bis 8 : v4
t = 8 bis 9 : v1
t = 9 bis 10: v4
t = 10 bis 12: v2
t = 12 bis 13: v1
t = 13 bis 14: v3
t = 14 bis 16: v4
t = 16 bis 17: v1
t = 17 bis 18: v3
t = 18 bis 20: v2
t = 20 bis 21: v1
t = 21 bis 23: v4
t = 23 bis 24: v3
t = 24 bis 25: v1
Hey, ich komme bei Aufgabe 2) 4. i. auf eine andere Lösung:
Die bisherige Lösung:
G_S = (V_S, E_S)
V_S = {v0, v1, v2, v3, v4, v5, v6, v7, vn)
E_S = {(v0, v1), (v0, v2), (v0, v3), (v0, v4), (v1, v5), (v2, v5), (v3, v6), (v4, v7), (v5, v6), (v6, v7), (v7, vn)}
(v1) (v2) (v3) (v4)
\ / / /
(v5) / /
\ / /
(v6) /
\ /
(v7)
Meine Lösung:
G_S = (V_S, E_S)
V_S = {v0, v1, v2, v3, v4, v5, v6, v7, vn)
E_S = {(v0, v1), (v0, v2), (v0, v3), (v1 ,v4), (v2, v4), (v3, v5), (v4, v5), (v3, v6), (v5, v7), (v6, v7), (v7, vn)}
(v1) (v2) (v3)
\ / /
(v4) /
\ /
(v5) (v6)
\ /
(v7)
Meiner Meinung nach beachtet die bisherige Lösung nicht die Abhängigkeiten zu y2 in der Code-Zeile 26: y4 = y2 + 2
Aufgabe 2) c) 1. ii.
ii) Ablaufplanverträglichkeit:
Bisherige Lösung:
E = {(v2, v6), (v2, v7), (v6, v7), (v1, v3), (v1, v4), (v1, v5), (v3, v5), (v4, v5)}
Meine Lösung:
E = {(v2, v6), (v2, v7), (v6, v7), (v1, v4), (v1, v5), (v3, v4), (v3, v5)}
Es werden doch alle Kanten zwischen Knoten der gleichen Ressource welche zeitlich gesehen in der selben horizontalen Ebene liegen aus dem schwachem Verträglichkeitsgraph entfernt?!
ii) Starke Verträglichkeit:
Bisherige Lösung:
E = {(v2, v6), (v2, v7), (v6, v7), (v1, v4), (v3, v5)}
Meine Lösung:
E = {(v6, v7), (v1, v4), (v3, v5)}
Es werden nur Kanten zwischen Knoten der selben Ressource gezeichnet, falls diese im Sequenzgraph direkt von einander abhängen?!
2 „Gefällt mir“
Jap ebenso ist dazu A2) 4 ii) nicht richtig:
v1, v5, v6 auf r1 mit jeweils 1
v2, v3, v4 ,v7 auf r2 mit jeweils 3
wenn man hier wirklich nur r1 betrachten muss und einfach die maximale Anzahl als gegeben nimmt, kann trotzdem x_1 x_2 und x_3 nicht bei 4 starten etc.
t = 0: x_1,0 + x_2,0 + x_3,0 <= 2
t = 1: x_1,1 + x_2,1 + x_3,1 <= 2
t = 2: x_1,2 + x_2,2 + x_3,2 <= 2
t = 3: x_3,3 <= 2
t = 4: x_6,4 <= 2
Ich würde allerdings allgemeiner Formulieren:
t = 0: x_1,0 + x_2,0 + x_3,0 <= a(r1)
t = 1: x_1,1 + x_2,1 + x_3,1 <= a(r1)
x_4,1 + x_5,1 <=a(r2)
t = 2: x_1,2 + x_2,2 + x_3,2 <= a(r1)
x_4,1 + x_4,2 + x_5,1 + x_5,1 <=a(r2)
t = 3: x_3,3 <= a(r1)
x_4,1 + x_4,2 + x_4,3 + x_5,1 + x_5,1 + x_4,3 <=a(r2)
t = 4: x_6,4 <= a(r1)
x_4,2 + x_4,3 + x_5,1 + x_4,3 <=a(r2)
Seh ich auch so!
Aufgabe 2) c) 2.
v1, v4: Farbe 2
Rest: Farbe 1
=> 2 Addierer 1 Multiplizierer
Die bisherige Loesung sollte aber stimmen, da die Startzeiten der Operationen durch tau(v_i) zum Schluss in der Aufgabenstellung gegeben sind. Somit ist z.B. die Kante (v3, v4) aus deiner Loesung falsch, weil tau(v_3) = tau(v_4) = 1.
Korrigiert mich, falls ich falsch liege, aber in den Vorlesungsfolien steht zu starker Vertraeglichkeit:
„stark verträglich, falls (v_i,v_j) schwach verträglich ist und
falls in G ein gerichteter Pfad von v_i nach v_j oder
umgekehrt existiert.“
Da ist vom gerichteten Pfad die Rede, was doch mehrere Kanten sein koennen.
Demnach sollte die urspruengliche Loesung richtig sein.
2 „Gefällt mir“
Oh verdammt du hast recht habe Stark Verträglich falsch gelernt.
Und auch mit den Startzeiten. Ist aber auch mies in der Aufgabe den Graphen anders zu zeichnen als er eigentlich gestartet wird.
Aufgabe 2 b) 1. Latenz
Kann mir jemand erklären, wie man hier auf 9 kommt? Mein Ergebnis wäre 8 gewesen.
Soweit ich weis, liegt das daran, dass der letzt mögliche Startzeitpunkt t=6 ist und die Ausführung nochmal 3 Zeitschritte dauert. → 6+3 = 9
Macht Sinn! Hab ich total übersehen, dass v7 zum Zeitpunkt 5 oder 6 ausgeführt wird…