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 05.04.2013
Danke an Eumel fuer die Loesungsvorschlaege! Um das Ganze zu vervollstaendigen hier meiner zu 2013
Feedback, Verbesserungsvorschläge und fehlende Lösungsvorschläge sind ausdrücklich erwünscht 
Aufgabe 1 (Spezifikation & Modellierung)
a) Doppeldachmodell
-
Erstellen und beschriften Sie das aus der Vorlesung bekannte Doppeldachmodell
Siehe Skript “A_Einfuehrung_Handout” Folie 18 -
Welche Bedeutung haben die beiden “Dächer” des Modells?
Oberes Dach = Verhalten
Unteres Dach = Struktur -
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.
-
Folgendes Petri-Netz kann auch durch einen äquivalenten markierten Graph dargestellt werden.
Nein, da |p1*|=2 >1 also mehr als eine Kante von p1 wegfuehrt -
Folgendes Petri-Netz ist Konfliktfrei.
Nein, t3 steht im Konflikt zu t1, wenn t3 schaltet kann t1 nicht mehr (nie)
feuern -
Folgendes Petzi-Netz ist stark lebendig
Nein, sobald t3 schaltet ist t1 und t2 nicht mehr aktivierbar also sind t1 und t2 nicht lebendig. -
Statecharts besitzen eine höhere Modellierungskraft als konventionelle FSMs.
Falsch, es kann unter Umstaenden Mehr Kanten und Knoten brauchen aber die Modellierungskraft ist gleich.
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 -
Erweitern sie das Petri Netz so, dass nur maximal 10 Lese- und maximal 10 Schreibprozesse warten koennen. Realisiern sie dass ohne die Kapazitaet der Stellen “wartender Schreibprozess” und “wartender Leseprozess” zu beschraenken.
Siehe Anhang -
Sobald mindestens ein Schreibprozess wartet, soll kein Leseprozess mehr starten koennen. Momentan ausgefuehrte Leseprozesse duerfen noch beendet werden. Erweitern sie das netz entsprechened.
Siehe Anhang
d) Synchrone Datenflussgraphen
-
Geben Sie die Topologiematrix C dieses Graphen an.
(-1 -2 0 0)
C = ( 2 0 y -1)
( 0 x -3 0)
( 0 0 -0 1) -
Bestimmen Sie den Repetitionsvektor y für diesen SDF-Graphen, y != 0. Die Herleitung wird mitbewertet.
NICHT SICHER
C^T * y = 0
=> y = (2, 1, y/3, 1)^T -
Ist der SDF-Graph konsistent? Begründen Sie Ihre Antwort.
NICHT SICHER
falls 4/x=-y/3 ist
Rang (C) = 2 = |V| - 1
=> SDF-Graph ist konsistent
sonst inkosistent
Aufgabe 2 (Hardwaresynthere)
a) Problemgraph
Gegeben sei folgendes GLS
x = 3a + bb-c
y= a + bx
z= b - c(a + b)
Erstellen Sie den Problemgraphen G(V, E) wobei jeder Knoten vi in V eine Operation (+, -, *) und jede Kante e=(vi, vj) in E eine Datenabhaengigkeit darstellt.
Siehe Anhang
b)Ablaufplanung
Gegeben sei der Graph und Resourcegraph.
- Bestimmen Sie den latenzoptimalen Ablaufplan ohne Ressourcenbeschraenkung. Tragen sie die Startzeitpunkte T(vi), i=1,2,…,8 in die Tabelle 1 ein
- Bestimmen Sie nun die Startzeitpunkte t(vi), i = 1,2,…5 mit Hilfe des ALAP-Verfahrens für eine Laufzeitschranke von L = 9. in Tabelle 2
- Bestimmen Sie die Mobilität u(vi) der Operationen vi € V für eine Laufzeitschranke von L = 9 in Tabelle 3
Habe alles in eine Tabelle
Task | ASAP | ALAP | u(vi)
v1 | 0 | 1 | 1
v2 | 0 | 1 | 1
v3 | 0 | 4 | 4
v4 | 3 | 4 | 1
v5 | 3 | 7 | 4
v6 | 4 | 5 | 1
v7 | 7 | 8 | 1
v8 | 4 | 8 | 4
c) Ganzzahlige Lineare Programme
-
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 = 1
x3,0 + x3,1 + x3,2 + x3,3 + x3,4 = 1
x4,3 + x4,4 = 1
x5,3 + x5,4 + x5,5 + x5,6 + x5,7 = 1
x6,4 + x6,5 = 1
x7,7 + x7,8 = 1
x8,4 + x8,5 + x8,6 + x8,7 + x8,8 = 1 -
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.
0x1,0 + 1x1,1 = t(v1)
0x2,0 + 1x2,1 = t(v2)
0x3,0 + 1x3,1 + 2x3,2 +3 x3,3 + 4x3,4 = t(v3)
3x4,3 + 4x4,4 = t(v4)
3x5,3 + 4x5,4 + 5x5,5 + 6x5,6 + 7x5,7 = t(v5)
4x6,4 + 5x6,5 = t(v6)
7x7,7 + 8x7,8 = t(v7)
4x8,4 + 5x8,5 + 6x8,6 + 7x8,7 + 8*x8,8 = t(v8) -
Formulieren Sie nun die im Sequenzgraph abgebildeten Datenabhängigkeiten mit Hilfe linearer Ungleichungen für alle Knoten vi € V
t(v4) - t(v1) >= 3
t(v4) - t(v2) >= 3
t(v5) - t(v3) >= 3
t(v6) - t(v4) >= 1
t(v7) - t(v6) >= 3
t(v7) - t(v5) >= 1
t(v8) - t(v5) >= 1
t(v1), t(v2),t(v3) >= t(vo) >= 0
t(v_n) - t(v7) >= 1
t(v_n) - t(v8) >= 1 -
Nun soll garantiert werden, dass zu keinem Zeitpunkt mehr als die zur Verfuegung stehenden Instanzen benutzt werden. Formulieren sie dafuer das notwendige lineare Ungleichungssystem fuer die ersten 5 Takte (t=0 bis t=4)
t = 0: x1,0 + x2,0 + x3,0 <= a(r1)
t = 1: x1,0 + x1,1 + x2,0 + x2,1 + x3,0 + x3,1 <= a(r1)
t = 2: x1,0 + x1,1 + x2,0 + x2,1 + x3,0 + x3,1 + x3,2 <= a(r1)
t = 3: x1,1 + x2,1 + x3,1 + x3,2 + x3,3 <= a(r1)
x4,3+ x5,3 <= a(r2)
t = 4: x3,2 + x3,3 + x3,4 + x6,4 <= a(r1)
x4,4+ x5,4 + x8,4 <= a(r2)
- Durch das ILP soll nun die Latenz minimiert werden. Formulieren Sie die Zielfunktion des ILPs.
min L = t(vn) - t(v0)
Aufgabe 3 (Software-Synthese)
a)Grundbegriffe und Kurzfragen
-
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 -
Gegeben sei ein Task vi aus einer Taskmenge V. Ordnen sie den Variablen di, td(vi), Tb(vi), tr(vi), Te(vi) ihren folgenden Bedeutungen zu.
Ankunftszeit: tr(vi)
Startzeit: Tb(vi)
Endzeit: Te(vi)
Deadline: td(vi)
Berechnungszeit: di -
Verwenden Sie die Variablen der vorherigen Aufgabe und geben Sie Formeln fuer folgende Zeiten an.
Flusszeit: tF(vi)=Te(vi) - tr(vi)
Mittlere Flusszeit: F = (SUM (i=1 to |V|) tF(vi)) /|V|
Wartezeit tW(vi)= tF(vi) - di
Verspaetung: TL(vi)= Te(vi)-td(vi)
Ueberhang: tT(vi)= max{0,TL(vi)} -
Im Bereich von Echtzeitsystemen kommen häufig prioritätsbasierte Einplanungsstrategien zum Einsatz. Welches Problem kann hierbei beim Zugriff auf gemeinsame Ressourcen auftreten? Erläutern Sie (ggf. anhand einer Skizze), wie es dazu kommen kann.
Priority Inversion
- Geben Sie drei Möglichkeiten an, wie man das Problem, das beim gemeinsamen Ressourcen-zugriff in prioritätsbasierten Echtzeitsystemen auftreten kann, verhindern kann und erläutern Sie kurz deren Funktionsweisen.
-Priority Inheritance
-Priority Ceiling
-Starres Einhalten der Prioritäten mit Verdrängung
- Nennen Sie drei Ablaufplanungsverfahren, die zur Planung gemischter Taskmengen (beste-hend aus periodischen und aperiodischen Tasks) geeignet sind.
-Hintergrundscheduling
-RM-Polling Server
-RM-Deferrable Server
(Foliensatz D ab Folie 66)
b) Gegeben:
| v1 | v2 | v3 |
—|----|—|----|
tr | 1 | 0 | 13 |
td | 5 | 7 | 4 |
1.) FCFS
v3 -|–|–|—|–|–|—|–|–|–|–|—|----|----|||||—|----|—|–
v2 -||_||||_||–|–|–|—|----|----|—|—|—|—|—|—|—|–
v1 -|–|–|—|–|–|—|–|||||_|----|—|—|—|—|—|—|—|–
----0–1–2–3–4–5–6–7–8–9–10–11–12–13–14–15–16–17–18–19–20–>
2.) SJF
v3 -|–|–|—|–|–|—|–|–|–|–|—|----|----|||||—|----|—|–
v2 -|||_||||_|–|–|–|—|----|----|—|—|—|—|—|—|—|–
v1 -|–|–|—|–|–|—|–|||||_|----|—|—|—|—|—|—|—|–
-----0–1–2–3–4–5–6–7–8–9–10-11-12–13–14–15–16–17–18–19–20–>
3.) SRTN
v3 -|–|–|—|–|–|–|–|–|–|–|—|—|—|||||—|----|—|–
v2 -||–|–|—|–|–|||||||—|—|—|—|—|—|—|—|–
v1 -|–||||||–|–|–|—|—|—|----|—|—|—|—|—|—|—|–
----0–1–2–3–4–5–6–7–8–9–10–11–12–13–14–15–16–17–18–19–20–>
4.) RR mit Q=1
v3 -|–|–|—|–|–|—|–|–|–|–|—|—|—|||||—|----|—|–
v2 -||–||–||–||—||–|||—|—|—|—|—|—|—|—|–
v1 -|–||–||—||–||–||—|—|----|—|—|—|—|—|—|—|–
----0–1–2–3–4–5–6–7–8–9–10–11–12–13–14–15–16–17–18–19–20–>
c)Ablaufplanung mit Echtzeitanforderungen
1)Ordnen sie die folgenden acht Algorithmen gemaes ihrer Eigenschaften den Tabelen zu
Skript Teil D seite 38 +53
2)EDF
| v1 | v2 | v3 | v4 | v5
–|----|—|----|—|----
tr | 0 | 2 | 0 | 3 | 6
di | 1 | 2 | 2 | 4 | 8
td | 2 | 4 | 5 | 18 | 15
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–>
Attachment:
petri.pdf: https://fsi.cs.fau.de/unb-attachments/post_150774/petri.pdf
2 „Gefällt mir“
Hey X-Flix, danke für deinen Lösungsvorschlag.
Ich arbeite ihn gerade durch und poste hier mal nach und nach wo ich evtl. anderer Meinung bin:
Aufgabe 1:
d) Synchrone Datenflussgraphen
- Geben Sie die Topologiematrix C dieses Graphen an.
Die Spalten der Topologiematrix: (s1,s2),(s1,s3),(s3,s2),(s2,s4)
(-1 -2 0 0)
C = ( 2 0 y -1)
( 0 x -3 0)
( 0 -1 -0 1)
Ich komme hier auf:
(-1 -2 0 0)
C = ( 2 0 y -1)
( 0 x -3 0)
( 0 0 0 1)
Aufgabe 2 (Hardwaresynthere)
c) Ganzzahlige Lineare Programme
3. Formulieren Sie nun die im Sequenzgraph abgebildeten Datenabhängigkeiten mit Hilfe linearer Ungleichungen für alle Knoten vi € V
Hier fehlen die beiden Abschlussknoten:
t(v_n) - t(v7) >= 1
t(v_n) - t(v8) >= 1
Aufgabe 3 (Software-Synthese)
a)Grundbegriffe und Kurzfragen
3. Verwenden Sie die Variablen der vorherigen Aufgabe und geben Sie Formeln fuer folgende Zeiten an.
Flusszeit: tF(vi)=Te(vi) - Tb(vi)
Verspaetung: TL(vi)=max{0 , Te(vi)-td(vi)}
Die Antwortzeit ist laut Foliensatz-D, Seite 28 über dem Ankunftszeitpunkt und nicht dem Startzeitpunkt definiert:
Flusszeit: tF(vi)=Te(vi) - tr(vi)
Die Verspätung ist laut Foliensatz-D, Seite 21 definiert als:
Verspaetung: TL(vi)=Te(vi)-td(vi)
2 „Gefällt mir“
Hey, vielen Dank für die Mühe!
Bei Aufgabe 3 a) 5. würde ich noch
-Starres Einhalten der Prioritäten mit Verdrängung (Siehe Übung 13)
ergänzen.
Ich denke bei Aufgabe 3 a) 6. ist eher Hintergrundscheduling, RM-Polling Server, RM-Deferrable Server, RM- Sporadic Server (und auch EDF-Total Bandwith Server) gefragt.(Foliensatz D ab Folie 66)
1 „Gefällt mir“
Hey,
kein Problem. Ebenfalls danke euch beiden für die Mitarbeit!
werde es dementsprechend ausbessern.
Jetzt weiß ich was ich noch machen wollte. Aufgabe 3 a) war hauptsächlich geraten 
Hey,
Ich glaube du hast dich bei der Aufgabe 1 Abschnitt B Teilaufgabe 4 vertan.
Die Frage lautet: Statecharts besitzen eine höhere Modellierungskraft als konventionelle FSMs.
Antwort: Nein, sie besitzen die gleiche Modellierungskraft
Da hast du recht, danke.
Um diesem älteren Thread etwas Leben einzuhauchen, X-Flix du hattest erwähnt, dass deine Lösung für den Problemgraphen sich im Anhang befindet, nur finde ich nur die Petri.pdf 
Könntest du das vielleicht noch hochladen?
Gruß
Hallo alle, ich tue mich schwer mit dem Repetitionsvektor. Kann mir jemand mal bitte schritt für schritt erklären wie ihr das findet ?
Danke
Aufgabe 1
d) Synchrone Datenflussgraphen
-
Geben Sie die Topologiematrix C dieses Graphen an.
(-1 -2 0 0)
C = ( 2 0 y -1)
( 0 x -3 0)
( 0 0 -0 1) -
Bestimmen Sie den Repetitionsvektor y für diesen SDF-Graphen, y != 0. Die Herleitung wird mitbewertet.
C^T * g = 0
g = gamma
-g1 + 2g2 = 0
-2g1 + xg3 = 0
yg2 - 3g3 = 0
-g2 + g4 = 0
=> g1 = 2g2, g2 = g4
I in II einsetzen:
xg3 = 4g2
sowie laut III:
3g3 = yg2
=> x = 3, y = 4
also 3g3 = 4g2
ganzzahlige Lsg ist g2 = 3, g3 = 4
damit g1 = 6, g4= 3
=> g = (6,3,4,3)^T
- Ist der SDF-Graph konsistent? Begründen Sie Ihre Antwort.
folgende Schritte
II = 2I + II
II = II + IV
III = 4III + 3II
=>
Rang (C) = 3 = |V| - 1
=> SDF-Graph ist konsistent