[ES] Lösungvorschlag zur Klausur vom 28.03.2014

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ösungvorschlag zur Klausur vom 28.03.2014
Aufgabe 1
=======

a)
1. Erstellen und beschriften Sie das aus der Vorlesung bekannte Doppeldachmodell was wird durch die Pfeile dargestellt
Siehe Skript in den ersten Folien
2. Was versteht man unter Synthese? Nennen Sie drei Hauptaufgaben!
Die Aufgabe der Synthese ist die (teil)automatische Transformation zwischen den verschiedenen Abstraktionsebenen und Schichten.

  • Allokation
  • Bindung
  • Ablaufplanung

3. Wie wird die Synthese im Doppeldach dargestellt?
Durch vertikale Pfeile zwischen den einzelnen Abschnitten

b) Zustandsautomaten

1. Welche Arten von Dekomposition gibt es bei hierarchischen Zustandsautomaten?

  • Petri-Netz
  • Statechart
    2. Gegeben ist der folgender Zustandsautomat …

Zustände = {(CF),(DF),(EF),(CG),(DG),(EG)}
Kanten = {
CF → DF mit alpha
DF → EF mit Beta
EF → EG mit epsilon
EG → EF mit Delta
EG → CG mit y
CG → DG mit alpha
DG → EG mit Beta }

c) Petri-Netz
1.&2. Geg.: Petri-Netz

Das Petrie Netzt wird um 4 Positionen erweitert.
P2 liegt zwischen den ProzessA und ProzessB. P2 hat zwei ausgehende Transitionen (eine nach StartA und eine nach StartB). P2 zwei eingehende Transitionen (eine von EndeA und eine von EndeB) und hat eine Marke!
P1 ist zwischen StartA und EndeA und enthält eine eine Marke von der Transition StartA. Mit EndeA wird eine Marke in verarbeitet und eine in P1 gelegt.
P3 ist zwischen StartB und EndeB und enthält eine eine Marke von der Transition StartB. Mit EndeB wird eine Marke in verarbeitet und eine in P1 gelegt.
P4 hat eine Marke und hat eine ausgehende Kante nach StartB und eine eingehende Kante nach EndeB

3. Ist das Petri-Netz sicher?
Ja, denn es gibt keine Stelle an der sich unendlich viele Marken sammeln können. (Es handelt sich hierbei um eine Trickfrage! Die beiden Wartezustände haben jeweils nur eine Marken und werden durch KEINE Transition aufgefüllt!)

4. Ist das Petri-Netz Konfliktfrei?
Nein, denn in warteA, warteB und P2 liegen Marken somit kann StartA und StartB “feuern” ← Konfikt

d)
1. Beschreiben Sie kurz in eigenen Worten, wann ein markierter Graph lebendig ist.
Ein markierter Graph ist genau dann lebendig, wenn jeder Kreis mind einen anfangsmarkierten Platz hat.

2. Gegen sei der folgende markierte Graph. Ist der Graph lebendig und falls nein erweitern Sie den Graphen um eine geeignete Anfangsmarkenverteilung. (KORRIGIERTE VERSION, dank an x-Flix)

Nein der Graph ist nicht lebendig!

Kreise = {
k1 = e3,e5,e1
k2 = e4,e5
k3 = e1,e2
}

K1 und K3 erfüllen die Bedingung aber nicht K2 → auf e4 muss eine Anfangsmarke hinzugefügt werden

3. Ist der von Ihnen erweitere Graph sicher? Wie viele Marken können auf jeder Kante max. akkumulieren.
Ja ist sicher
Es können sich maximal drei Marken akkumuliert werden (bei e3)

4.Stellen Sie die Topologiematrix für den gegebenen Graphen auf
| 1 -1 -1 0 0 |
C =| 0 0 1 1 -1 |
| -1 1 0 -1 1 |

5. Zeigen Sie für alle gerichteten Zyklen des in 2. dargestellten Graphen, dass die Summe der Marken unter allen Feuerbedingungen konst. ist.
^T := bedeutet Transponiert! Nicht hoch T!!!

d’ = d - C^T * y
p* C^T = 0
P_{1,2,3} ={ (1 0 1 0 1)^T , (1 1 0 0 0)^T, (0 0 0 1 1)^T

pd’ = pd - p * C^T * y


Aufgabe 2 (Hardwaresynthese)
========================

[i]a) Grundbegriffe

  1. [/i]
    X_tmp1 :== Index von X = tmp1

Kostenfunktion: V_T → Q_o^+
Gewichtsfunktion: w_s = w ( v_s, v_t)
Ablaufplan: t(v_j) - t(v_i) >= d_i
Latenz: L = max {t(v_i) +d_i} - min{t(v_j)}
Allokation: a(v_t)
Bindung: y und Beta y: V_s → Z^+

2. Geben Sie eine Formel an, wie man L berechnen kann. Was bezeichnet L
L bezeichnet die Latenz
L = max {t(v_i) +d_i} - min{t(v_j)}

3.
i)

Zeichnung fehlt!
G_s = (V_s , E_s)
V_s = { v_0 , v_1, v_2, …, v_8, v_r}
E_s = { (v0,v1)(v0,v2)(v0,v3)(v1,v4)(v2,v4)(v3,v6)(v3,v5)(v4,v6)(v6,v8)(v5,v7)(v7,v8)(v8,vR)}

ii)
Zeichnung!!!
Zeichnung beschrieben:
v1, v3, v6, v7 bilden auf r1 ab mit d_+ = 1
v2,v4,v5,v8 bilden auf r2 ab mit D_*/= 3

b) Allokation und Bindung

  1. (KORRIGIERTE VERSION, dank an x-Flix)
    i) eine Allokation ordnet jedem Ressourcentyp die Anzahl verfügbarer Instanzen zu.

ii) Für einen gegeben datenflussgraphen ohne Ressourcenbeschränkung ergeben die Ablaufplanungsverfahren ALAP und ASAP immer die gleiche Latenz (bin mir hier unsicher!)

iii) Die Mobilität wird als Differenz der Startzeitpunkte von ALAP und ASAP bestimmt.

2.

t K S
0 v1,v2,v3
1 v2,v5 v3,v1
2 v4, v7 v3,v1,v2,v5
3 v6, v8,v9,v10 v3,v1,v2,v5,v7,v4
4 v9,v10,v11 v3,v1,v2,v5,v7,v4,v6,v8
5 v11 v3,v1,v2,v5,v7,v4,v6,v8, v9,v10

[i]3.

i)[/i]
x_{11,0} + x_{11,1} +x_{11,2} + x_{11,3} + x_{11,4} + x_{11,5} = 1

ii)
Das sagt aus, dass die Operation v4 zum Zeitpunkt 1,2,3 starten muss und v6 bei 2,3 oder 4 starten muss
u(v4) = 3 - 1 = 2
u(v6) = 4 - 2 = 2

iii)

1 * x_{4,1} + 2* x_{4,2} + 3 * x_{4,3} <= T(v4)
2* x_{6,2} + 3 * x_{6,3} + 4 * x_{6,4} <= T(v6)

iv) (KORRIGIERTE VERSION, dank an x-Flix)
T(v11) >= T(v6)+1
T(v11) >= T(v8)+1
T(v11) >= T(v9)+1
T(v4) >= T(v1)+1
T(v4) >= T(v2)+1

c)
1.

Ich schreibe hier nur die Verbindungen hin, da Zeichnungen nicht möglich sind! Die Kanten sind ungerichtet, macht es aber einfacher beim schreiben!

i)
Kanten 1->3 ; 1->4 ; 3->4 ; 2->6; 2->5 ; 6->5

ii)
Kanten: 1->3 ; 1->4 ; 2->6 ; 2->5; 6->5

iii)
Kanten: 1->4 ; 5->6

2.
i)

Kanten: 4->5

ii)
Kanten: 1->3 , 3->4 , 2->5, 2->6

3)
2 * Addierer
1 * MUL

Aufgabe 3
==========

a)

1. Wie sind harte und weiche Tasks bei Echtzeitsystemen definiert?
hart: Ein Task heißt hart, falls eine Abarbeitung nach seiner Deadline katastrophale Auswirkungen auf das Gesamtsystem hat.
weich: Ein Task heißt weich, falls das Verpassen seiner Deadline nur die Leistungsfähigkeit (Qualität) des Gesamtsystems herabsetzt, nicht aber die Funktionsfähigkeit.

2.

  • Ankunftszeit t_r(v_i)
  • Startzeit: T_b(v_i)
  • Endzeit: T_e(v_i)
  • Deadline: t_d(v_i)
  • Berechungszeit :d_i

Flusszeit: tf_f = T_e(v_i) - t_r(vi)
Mittlere Flusszeit: F = 1/N sum^N_{i=1} (T_e(v_i)- t_r(v_I))
Wartezeit: t_w = T_e(v_i)- t_r(vi)
Verspätung t_L = T_e(v_i) - t_D(v_i)
Überhang t_T = max{0,t_L(v_i)^2}

b)
1.

| -1 -2 0 0 0 |
|3 0 -1 0 0 |
C = | 0 3 0 -1 0 |
| 0 0 2 4 -1 |
| 0 0 0 0 2 |

2((6A)(2B)(4C)D)E = (12A)(4B)(8C)(2D)(E)

y = (12 4 8 2 1)^T

2.
SAS Sind Looped Schedules bei denen jeder Knotenbezeichner nur genau einmal vorkommt. Minimiert wird das Clustering unter Beibehaltung gültiger Ablaufreihenfolgen

3.

2((6A)(2B)(4C)D)E
D = max {Sum d(e,k)}

D = 2 + 6 +2 +4 = 14

c)
1)
(KORRIGIERTE VERSION, dank x-Flix)

|   v1  |  v2 |   v3  |  v4  |   v5 |

tr | 4 | 9 | 5 | 1 | 6 |
td | 12 |13 | 11 | 10 | 17 |

Zeichnung:
v4 von 1-> 4
v1 von 4-> 5, 9 ->10
v3 von 5-> 9
v2 von 10-> 12
v5 von 12 ->17

3. Nennen Sie drei geeignete Verfahren um Konflikte beim Zugriff auf gemeinsame Ressourcen durch verschiedene Task zu lösen. (Zur Zeit in Diskussion)
Entweder:

  • PIP
  • PCP
  • starres einhalten der Prioritäten

oder:

  • First-come-first-serve
  • Short-Job-First
  • Round-Robin

Hiho,

danke Fürs Lösen! ich vergleiche auch mal mit meiner Lösung und Schreibe alle Abweichungen hier nach und nach auf.
Und hätte auch noch ne Allgemeine Frage? kann jemand der in der Vorlesung war bestätigen / negieren das Looped Shedules drankamen?

hier hast du dich glaube ich verschrieben e5 oder e4 müsste eine Marke bekommen.

A2) b) 1.

iii) Die Mobilität wird als Differenz der Startzeitpunkte von ALAP und ASAP bestimmt.

A2) b) iv)
T(v11) >= T(v6)+1
T(v11) >= T(v8)+1
T(v11) >= T(v9)+1
T(v4) >= T(v1)+1
T(v4) >= T(v2)+1

a3) 2.

v4 von 1-> 4
v1 von 4-> 5, 9 ->10
v3 von 5-> 9
v2 von 10-> 12
v5 von 12 ->17

A3) 3.

bei mir steht hier eine komplett andere Aufgabe xD
„Wie hoch ist der maximale Datenspeicheraufwand?(Hinweis: Der Speicheraufwand ergibt sich aus der SUmme der Marken auf allen Kanten zu einem Bestimmten Zeitpunkt.)“


Aufgabe 3 c) 3.

Mir mir steht hier die selbe Aufgabenstellung wie bei MRX:
3. Nennen Sie drei geeignete Verfahren um Konfikte beim Zugriff auf gemeinsame Ressourcen durch verschiedene Task zu lösen.

Wobei ich hier als Antwort eher die Ressourcezugriffsprotokolle nennen würde (Skript-D, Seite 93):
-Priority Inheritance Protocol
-Priority Ceiling Protocol
-NPCS (habe in den Folien kein drittes Protokoll gefunden und daher eines aus der EZS-Vorlesung des 4.Lehrstuhls genommen)


Hi pd,

Ich glaube die Frage ist ungünstig gestellt.

Man kann sowohl mit

  • PIP
  • PCP
  • starres einhalten der Prioritäten

als auch mit
*FCFS
*RR
*SJF

antworten.

Denn wenn man sich an GRa erinnert, dann enthält ein Task eine Reihe von Makro Befehlen, diese können dann sequentiell, bzw. zum Teil auch parallel ausgeführt werden. (Hint: Daten-/Steuerhazards)
Nehmen wir mal zwei Task t1 und t2 an. Da mit den Verfahren(FCFS,…) immer nur ein Task arbeiten kann, sollte es keinen anderen Task geben der auf die Ressourcen zugreifen kann. Innerhalb eines Tasks sollte der Zugriff auf die Ressourcen geklärt sein.

Seit ihr mit dieser Lösung der Teilaufgabe einverstanden? Wenn ja editiere ich mal meinen ersten Post


Hey,

auch von mir Danke fürs Lösen und abtippen!

Wie kommst du bei der Aufgabe 3 b 3. auf 14?
MMn ist die maximale Anzahl an Marken im System 19. Und zwar wenn A zum zweiten Mal 6 Mal gefeuert hat.
6A → 12 Marken auf AC + 6 Marken auf AB
3
B → 12 Marken auf AC + 2 Marken au BD
4C → 2 Marken auf BD + 4 Marken auf CD
1
D → 1 Marke auf DE
6*A → 12 Marken auf AC + 6 Marken auf AB + 1 Marke auf DE → 19 Marken → danach wieder weniger.


Hi,

Ich habe mich an das Beispiel aus den Folien gehalten. (Foliensatz D S.140)
Gegeben war:
un :== unendlich

(un(x(4y)(12z))) → Speicherbedarf D = 4+ 12 = 16
(un(x4(y(3z)))) → Der Datenspeicheraufwand D = 4 + 3 = 7 Einheiten

Ich verstehe das so: Wenn du den Ablaufplan ausmultiplizierst und die Summe über die Zahlen bildest, dann erhältst du den Speicherbedarf.
Den Datenspeicher erhält man, indem man so weit wie möglich kürzt und die Summe über die Zahlen bindet. In unserem Fall einfach die Summe nehmen.


In der Vorlesung wurde scheinbar der Datenspeicher für die Marken auf den Kanten und der Datenspeicher für den Code gleich benannt. Ich denke hier muss eher die Formel von Foliensatz D S.136 genommen werden. Zumal diese ausformuliert als Hinweis gegeben ist. Damit ist der Zeitpunkt gesucht an dem die Anzahl der Marken maximal ist. In dem Beispiel in den Folien wäre das bei dem ersten Ablaufplan 12 beim Zeitpunkt 5 und beim zweiten 6 beim Zeitpunkt 3. Und in der Klausuraufgabe 19 Marken beim Zeitpunkt 19.
Das Beispiel auf Foliensatz D S.140 bezieht sich denke ich auf S.139.


Und noch 2 Kleinigkeiten:
Bei Aufgabe 1 b 1. ist XOR und AND Dekomposition gefragt.
Bei Aufgabe 1 b 2. fehlen 2 Kanten ->von DG nach DF mit Delta und von CD nach CD mit Delta

1 „Gefällt mir“

hä, wie kommt man bei Folie 141 dann auf

(∞(7(7(3(AB)(2C))(4D))(32(E(5F)))) = (∞((147A)(147B)(98C)(28D)(32E)(160F)))
=>D = 264 =>S= 147+ 294+ 196+ 224+ 160 = 1021

Wäre der Datenspeicheraufwand D dann nicht 7+7+3+2+4+32+5=60?


also die Rechnung bei Folie 141 ist so:

bei der oberen mit (∞((147A)(147B)(98C)(28D)(32E)(160F))) rechnest du wie folgt: D= 1471+1472+982+288+325+1601 = 1021

Auf die Zahlen für die Multiplikation kommst du durch das Diagramm, wo an jedem Knoten eine Zahl steht, wie viel raus geht. Mit dieser Zahl multiplizierst du dann die entsprechende Zahl vom Ablaufplan.

Was mich dabei stört das es dann im wiederspruch mit dem Beispiel auf Folie 140 steht.


Aso, danke ! Aber woher kommen nun die 264 im ausgeklammerten Fall?
Ist glaub ich ein Fall für Skript mit in die Einsicht nehmen und argumentieren. :smiley:


Ok, ich denke ich weiß wieder wie er es in der Vorlesung erklärt hat.
Man zählt für jede Kante wieviele Marken maximal darauf liegen während dem Ablaufplan und summiert alle Kanten auf. Im Skript kommt man da auf 1+6+28+224+5=264 bzw 11 + 32 + 14*2 +28 8 + 51 =264

Und in der Klausuraufgabe dann 62 + 61 + 21 + 41 +1 = 25

2 „Gefällt mir“

Danke dir, habe ich glaub ich jetzt grundsätzlich verstanden. In der Klausuraufgabe verstehe ich das Prinzip und kommme auch auf 25 .Aber bei dem Shedule von 141 würde doch A und B jeweils 1 mal, C 2 mal, D 4 mal und E 1 mal feuern und somit bekomem ich
11 + 12+ 22 + 48 + 1*5=44

Steh gerade glaube ich auf dem Schlauch…


Wenn A feuert entsteht auf Kante AB 1 Marke. Diese wird sofort wieder abgearbeitet indem B feuert.
Das ganze passiert 3 Mal und B produziert jedes Mal 2 Marken, so dass jetzt 6 Marken auf Kante BC liegen.
Dann feuert C 2 mal und das ganze wird 7 mal wiederholt. Also liegen auf der Kante CD 722=28 Marken.
Dann feuert D 4 mal und alles wird 7 mal wiederholt also produziert er 478=244 Marken die dann auf der Kante DE liegen.
E feuert dann 32 mal einzeln und die Marken werden immer sofort von F abgearbeitet. Es liegen also maximal 5 Marken auf dem Knoten EF.

1 „Gefällt mir“

Super danke nadanosh, jetzt hab ichs verstanden!

1 „Gefällt mir“

Jetzt habe ich leider noch eine kleine Rückfrage zur Klausuraufgabe:
Wenn doch da steht (2(6A)(2B)(4C)D) dann wird diese Folge doch 2mal ausgeführt. Also müssten doch auf der Kante DE 2 Tokens rumliegen und nicht nur 1 wie du in der Rechnung schreibst.
Für alle anderen Kanten ist die Mehrfachausführung nicht relevant, weil die Tokens weggeräumt werden. Bei DE bleiben die aber ja bis E die wegräumen kann?
Deshalb hätte ich 26 “getippt”.
Aus 62 + 61 + 21 + 41 + 2*1 =26


1 „Gefällt mir“