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 28.09.2012
Hier mein Lösungsvorschlag (soweit vorhanden) zur Klausur vom 28.09.2012
Feedback, Verbesserungsvorschläge und fehlende Lösungsvorschläge sind ausdrücklich erwünscht 
Aufgabe 1 (Spezifikation & Modellierung)
a) Doppeldachmodell
1. Erstellen und beschriften Sie das aus der Vorlesung bekannte Doppeldachmodell
Siehe Skript “A_Einfuehrung_Handout” Folie 18
2. Welche Bedeutung haben die beiden “Dächer” des Modells?
Oberes Dach = Verhalten
Unteres Dach = Struktur
3. Wodurch wird die Synthese im Doppeldachmodell dargestellt?
Durch die Pfeile zwischen den beiden Dächern Verhalten & Struktur
b) Grundlagen
Welche der folgenden Aussagen ist wahr bzw. falsch? Bitte kurz begründen bzw. richtigstellen.
1. Folgendes Petri-Netz kann auch durch einen äquivalenten markierten Graph dargestellt werden.
Ja, da die Kapazität aller Stellen unendlich ist und das Kantengewicht überall 1 beträgt.
2. Folgendes Petri-Netz ist stark lebendig.
Ja, da alle Transaktionen lebendig sind
3. Folgendes Petzi-Netz ist beschränkt
Ja, da die Anzahl der Token in einem Knoten nicht ins unendliche steigt und somit eine obere Schrank n € N angegeben werden kann
4. Durch Statecharts kann nicht mehr modelliert werden als durch konventionelle FSMs.
Falsch, Statecharts könenn zusätzlich
- Hierarchien
- Nebenläufige Zustände
- Broadcastkommunikation
modellieren
c) Petri-Netze
1. Vervollständigen Sie das oben abgebildete Petri-Netz so, dass es das Verhalten modelliert, das in der Spezifikation beschrieben wird.
Siehe Anhang
2. Es sollen nur Puffer zum Einsatz kommen, die maximal 10 Datenelemente speichern können. Erweitern Sie das Petri-Netz, so dass diese Eigenschaft erfüllt ist.
Siehe Anhang
3. Zwei Daten aus dem Puffer A sollen in einem zweiten Schritt mit einem Datum aus Puffer B fusioniert und dann an den Aktuator weitergeleitet werden. Erweitern Sie das Petri-Netz entsprechend.
Siehe Anhang
4. Ist das entstandene Petri-Netz konfliktfrei?
Ja
5. Gib es einen zum Petri-Netz äquivalenten synchronen Datenflussgraphen (SDF)? Begründen Sie Ihre Antwort.
Nein, da Kapazität != unendlich
d) Synchrone Datenflussgraphen
1. Geben Sie die Topologiematrix C dieses Graphen an.
(-1 0 X)
C = (1 -2 0)
(0 1 -2)
2. Bestimmen Sie den Repetitionsvektor y für diesen SDF-Graphen, y != 0. Die Herleitung wird mitbewertet.
C^T * y = 0
=> x = 4
=> y = (1, -1, 2)^T
3. Ist der SDF-Graph konsistent? Begründen Sie Ihre Antwort.
Rang (C) = 2 = |V| - 1
=> SDF-Graph ist konsistent
Aufgabe 2 (Hardwaresynthere)
a) Ablaufplanung
1. Bestimmen Sie die Startzeitpunkte t(vi), i = 1,2,…5 mit Hilfe des ASAP- und des ALAP-Verfahrens für eine Laufzeitschranke von L = 7.
Task | ASAP | ALAP
v1 | 0 | 1
v2 | 0 | 2
v3 | 1 | 2
v4 | 2 | 4
v5 | 4 | 5
2. Bestimmen Sie die Mobilität u(vi) der Operationen vi € V für eine Laufzeitschranke von L = 7
Task | u(vi)
v1 | 1
v2 | 2
v3 | 1
v4 | 2
v5 | 1
b) Ganzzahlige Lineare Programme
1. Formulieren Sie die Bedingung, dass jede Operation genau einmal ausgeführt wird für alle Operation vi € V als lineare Gleichung. Verwenden Sie dazu die ermittelten ASAP- und ALAP-Zeiten aus Aufgabenteil a).
x1,0 + x1,1 = 1
x2,0 + x2,1 + x2,2 = 1
x3,1 + x3,2 = 1
x4,2 + x4,3 + x4,4 = 1
x5,4 + x5,5 = 1
2. Zeigen Sie für alle Knoten vi € V, wie aus den binären Variablen die tatsächlichen Startzeitpunkte t(vi) durch lineare Gleichungen bestimmt werden können.
0 * x1,0 + 1 * x1,1 = t(v1)
0 * x2,0 + 1 * x2,1 + 2 * x2,2 = t(v2)
1 * x3,1 + 2 * x3,2 = t(v3)
2 * x4,2 + 3 * x4,3 + 4 * x4,4 = t(v4)
4 * x5,4 + 5 * x5,5 = t(v5)
3. Formulieren Sie nun die im Sequenzgraph abgebildeten Datenabhängigkeiten mit Hilfe linearer Ungleichungen für alle Knoten vi € V
t(v3) - t(v1) >= 1
t(v4) - t(v2) >= 2
t(v5) - t(v3) >= 3
t(v5) - t(v4) >= 1
t(vn) - t(v5) >= 2
t(v1), t(v3) >= t(vo) >= 0
4. Durch das ILP soll nun die Latenz minimiert werden. Formulieren Sie die Zielfunktion des ILPs.
min L = t(vn) - t(v0)
5. Durch das ILP soll nun auch eine geeignete Allokation der Ressourcen gefunden werden. Dazu wird die Variable a(r2) eingeführt. Formulieren Sie die Ressourcenbeschränkungen für die Ressource r2.
t = 0: x1,0 <= a(r2)
t = 1: x1,1 + x3,1 <= a(r2)
t = 2: x3,1 + x3,2 + x4,2 <= a(r2)
t = 3: x3,1 + x3,2 + x3,3 + x4,3 <= a(r2)
t = 4: x3,2 + x3,3 + x3,4 + x4,4 + x5,4 <= a(r2)
t = 5: x5,5 <= a(r2)
Aufgabe 3 (Software-Synthese)
a)
1. Was unterscheidet harte und weiche Echtzeitbedingungen?
Hart: Abarbeitung des Tasks nach seiner Deadline hat katastrophale Auswirkungen auf das Gesamtsystem
Weich: Verpassen der Deadline setzt “nur” die Leistungsfähigkeit/Qualität herab, jedoch nicht die Funktionsfähigkeit
2. Die folgende Abbildung stellt die Nützlichkeit eines Ergebnisses n_vi(t)für die Tasks vi mit den Deadline td(vi) mit i € {1,2,3} über die Zeit t dar. Welche Art (hart, weich) von Echtzeittask entspricht v1, v2 und v3?
v1: weich
v2: hart
v3: weich
b) In der folgenden Abbildung sind die Tasks vi mit den Ankunfszeiten tr(vi) und den Deadlines td(vi) mit i € {1,2,3} gegeben. Geben Sie die Startzeiten tb(vi), die Endzeiten te(vi), die Berechnungszeiten di sowie den Überhang tT(vi) der einzelnen Tasks vi an. Berechnen Sie im Anschluss die mittlere Antwortzeit F, sowie die gesamte Berechnungszeit L.
| tb(vi) | te(vi) | di | tT(vi)
v1 | 0 | 19 | 12 | 0
v2 | 4 | 26 | 11 | 1
v3 | 9 | 30 | 7 | 2
F | 21 2/3
L | 30
c) In folgender Tabelle sind für fünf unterbrechbare Tasks die Ankunftszeiten tr(vi), die Ausführungszeiten di und die Deadline td(vi) gegeben. Bestimmen Sie graphisch einen Ablaufplan durch Anwendung des EDF-Algorithmus.
[m]v5 -| | |–|–|–|–|–|–| | |—|—|—|—|—|—|—|—|—|—|–
v4 -|–|–| | |–|–|–|–|–|–|—|—|—|—|—|—|—|—|—|—|–
v3 -|–|–|–|–|–|–|–|–|–|–|—|—| | | | | | | |—|–
v2 -|–|–|–|–| | | | |–|–|—|—|—|—|—|—|—|—|—|—|–
v1 -|–|–|–|–|–|–|–|–|–|–| | |—|—|—|—|—|—|—|—|–
----0–1–2–3–4–5–6–7–8–9–10–11–12–13–14–15–16–17–18–19–20–>[/m]
d) Zusätzlich sollen nun folgende Abhängigkeiten gelten: v1 → v2, v2 → v4, v5 → v4
1. Bestimmen Sie die veränderten Ankunftszeiten tr(vi) und Deadlines td(vi) für einen EDF-Algorithmus, der Datenabhängigkeiten berücksichtigt (EDF*).
[m]
| v1 | v2 | v3 | v4 | v5
----|----|----|----|----|----
tr* | 2 | 4 | 10 | 8 | 0
td* | 7 | 11 | 20 | 13 | 11
[/m]
2. Zeichnen Sie den Ablaufplan gemäß EDF*-Algorithmus.
[m]v5 -| | | | |–|–|–|–|–|–|—|—|—|—|—|—|—|—|—|—|–
v4 -|–|–|–|–|–|–|–|–|–|–| | |—|—|—|—|—|—|—|—|–
v3 -|–|–|–|–|–|–|–|–|–|–|—|—| | | | | | | |—|–
v2 -|–|–|–|–|–|–| | | | |—|—|—|—|—|—|—|—|—|—|–
v1 -|–|–|–|–| | |–|–|–|–|—|—|—|—|—|—|—|—|—|—|–
----0–1–2–3–4–5–6–7–8–9–10–11–12–13–14–15–16–17–18–19–20–>[/m]
e) Gegeben ist die folgende Menge von periodischen Tasks. Führen Sie eine Ablaufplanung mittels des RM-Verfahrens durch.
1. Geben Sie hierfür zunächst einen hinreichenden Planbarkeitstest an, der allgemein für eine Menge von n gegeben Tasks gilt.
Summe von (i=1) bis (n) über [di / td(vi)] <= n * (2^(1/n) - 1)
2. Zeichnen Sie nun den Ablaufplan gemäß des RM-Verfahrens im Intervall von 0 bis 20.
ANTWORT FEHLT
3. Würde der EDF-Algorithmus für diese Taskmenge einen gültigen Ablaufplan erzeugen? Begründen Sie Ihre Antwort.
4
Summe [di / P(vi)] = U <= 1
i=1
0,25 + 0,1 + 0,22 + 0,33 <= 1
0,9055 <= 1
=> Ja, da obige Ungleichung erfüllt
Attachment:
aufgabe 1c 1.-3…jpg: https://fsi.cs.fau.de/unb-attachments/post_129666/aufgabe 1c 1.-3…jpg
1 „Gefällt mir“
Hallo,
zwei Anmerkungen:
- ist der Repititionsvektor bei Aufgabe 1d nicht y = (1, 1, 2)^T
- bei Aufgabe 3d wird Task 5 bei t=2 doch von Task 1 unterbrochen, welcher eine kleinere Deadline hat
Wie kommst du bei Aufgbabe 2b) die 5. auf z.B.:
t = 4: x3,2 + x3,3 + x3,4 + x4,4 + x5,4 <= a(r2)?
Weil bei mir sieht das so aus:
t=4:
i=3: min{3-1,4-2}=2, max{0,4-4}=0 =>
Wenn ich das so weiter mache, kommt dann bei mir raus:
Edit:
Nevermind, ich glaub ich bin in meinen Notizen einfach in der Zeile verrutscht und der Fehler hat sich fortgeplanzt. -.-’
Nur als Vergleich zur A2b,5.), bei mir kommt folgendes raus:
Ich finde allerdings den Fehler nicht, kann mir evtl. jmd. erklären, wie man das richtig ausrechnet? Ich gehe zwar nach der Formel vor, aber irgendwie kommt anscheinend was falschen raus. V: Komischerweise wenn ich die Übungsaufgaben so berechne, kommt alles richtig raus. Kann es sein, dass du dich evtl. irgendwo verrechnet hast (oder ich vielleicht)?
Nur ne Kleinigkeit nebenbei:
Der Fehler passiert mir auch ständig. xD
Ja, das stimmt. Da hab ich mich verrechnet.
Nein. Es handelt sich dabei um den EDF*-Algorithmus, welcher von ununterbrechbaren Tasks ausgeht.
Sicher, dass wir bei Aufgabe 1 den Repetitionsvektor nicht in Abhängigkeit von x ausdrücken sollen? Mir kommt die Aufgabe bissl suspekt vor. xD Mein Repetitionsvektor hat dann nämlich die Form:
y = (x,2x,4x)^T,
die Topologiematrix hat in der letzten Spalte: (x,x,2-(1/2)x)^T. Wenn wir dann für x=4 einsetzen, kommt nämlich heraus: (4,4,0), was dann mit deiner Matrix übereinstimmen würde.
Oder hab ich da die Aufgabe zu allgemein aufgefasst? Den Fehler mach ich nämlich häufig. ^-^
nein, der EDF* geht eindeutig von unterbrechbaren Tasks aus (siehe Foliensatz D, Folie 37).
1 „Gefällt mir“
Hab fast das selbe Ergebnis. Nur bei t=6 hab ich x5,5 anstatt x5,4
Jupp, du hast Recht, es muss x5,5 lauten, hab mich verrechnet. xD
Auch wenn der Thread etwas veraltet ist, will ich gern einige Lösungen zu den ES-Klausuren besprechen:
@ R3count: Bei der Aufgabe 1 muss der Repetitionsvektor in Abhängigkeit von x ausgedrückt werden, aber die Matrix darf nicht den vollen Rang haben. Da die beiden ersten Zeilen von C^T linear unabhängig sind, muss die dritte Zeile gerade 0 sein. Deshalb kann man x auf 4 setzen.
@ all: Bei der Aufgabe 3b habe ich etwas Anderes heraus. tau_e ist 18 für v_1 und folglich ist auch F durch 64/3 statt 65/3 gegeben (also 21 1/3 und nicht 21 2/3). Weiterhin habe ich als Tardiness t_T(v_i) = max(0, T_L(v_i)) eingesetzt, wobei T_L(v_i) = t_e(v_i) - t_d(v_i) ist. Daher ist t_T(v_1) = t_T(v_2) = 0; t_T(v_3) = 1.
1 „Gefällt mir“
A1 b) 4. ist übrigens falsch!
Laut Übungslösungen ist die Modellierungsmächtigkeit dieselbe.
Hierarchie, Nebenläufigkeit etc. könnnen genauso in FSMs (jedoch mit deutlich mehr Knoten und Kanten) dargestellt werden.
Bei der A3 e) 2. müsste das Diagramm doch prinzipiell so aussehen
v4 -| | |–|–|–|–| | |—|–|—|—| | |—|—|—|----| | |–
v3 -|–|–|–|–| | |–|–|—|—| | |—|----|—|—|—|—|—|—|–
v2 -|–|–|–|–|–|–|–|–|—|—|—|—|—|----| | |—|—|—|—|–
v1 -|–|–| | |–|–|–|–| | |—|—|—|----|—|—| | |—|—|–
----0–1–2–3–4–5–6–7–8–9–10–11–12–13–14–15–16–17–18–19–20–>
Ich bin mir nur nicht sicher, wie es bei v2 ist, ob er wegen seiner Deadline unterbrechen darf oder nicht. Ich hab es jetzt komplett nach der Priorität gemacht und da gilt ja P(v_4) < P(v_1) < P(v_3) < P(v_2).
Aufgabe 1 (Spezifikation & Modellierung)
b) Grundlagen
Welche der folgenden Aussagen ist wahr bzw. falsch? Bitte kurz begründen bzw. richtigstellen.
-
Folgendes Petri-Netz kann auch durch einen äquivalenten markierten Graph dargestellt werden.
Ja, da die Kapazität aller Stellen unendlich ist und das Kantengewicht überall 1 beträgt.
Und jede Stelle hat 1 Eingang und 1 Ausgang -
Folgendes Petri-Netz ist stark lebendig.
Ja, da alle Transaktionen lebendig sind
Nein, da t2 nach einmal schalten tot ist -
Folgendes Petzi-Netz ist beschränkt
Ja, da die Anzahl der Token in einem Knoten nicht ins unendliche steigt und somit eine obere Schrank n € N angegeben werden kann -
Durch Statecharts kann nicht mehr modelliert werden als durch konventionelle FSMs.
Falsch, Statecharts könenn zusätzlich
- Hierarchien
- Nebenläufige Zustände
- Broadcastkommunikation
modellieren
, welche durch FSMs darstellbar sind → Antwort ja
c) Petri-Netze
-
Vervollständigen Sie das oben abgebildete Petri-Netz so, dass es das Verhalten modelliert, das in der Spezifikation beschrieben wird.
Siehe Anhang -
Es sollen nur Puffer zum Einsatz kommen, die maximal 10 Datenelemente speichern können. Erweitern Sie das Petri-Netz, so dass diese Eigenschaft erfüllt ist.
Siehe Anhang -
Zwei Daten aus dem Puffer A sollen in einem zweiten Schritt mit einem Datum aus Puffer B fusioniert und dann an den Aktuator weitergeleitet werden. Erweitern Sie das Petri-Netz entsprechend.
Siehe Anhang -
Ist das entstandene Petri-Netz konfliktfrei?
Ja -
Gib es einen zum Petri-Netz äquivalenten synchronen Datenflussgraphen (SDF)? Begründen Sie Ihre Antwort.
Nein, da Kapazität != unendlich
oder auch weil nicht alle Stellen 1 Ein/Ausgang haben
d) Synchrone Datenflussgraphen
-
Geben Sie die Topologiematrix C dieses Graphen an.
(-1 0 X)
C = (1 -2 0)
(0 1 -2) -
Bestimmen Sie den Repetitionsvektor y für diesen SDF-Graphen, y != 0. Die Herleitung wird mitbewertet.
C^T * y = 0
[b] (-1 1 0)
C^T = (0 -2 1)
(X 0 -2)
-y1 + y2 = 0 => y1 = y2
-2y2 + y3 = 0 => y3 = 2y2
x*y1 - 2y3 = 0 => wegen I ist x = 2
=> y = (1, 1, 2)^T[/b]
- Ist der SDF-Graph konsistent? Begründen Sie Ihre Antwort.
Rang (C) = 3 =/= |V| - 1
=> SDF-Graph ist nicht konsistent