Matrikelnr.: 1
RTS (SS 17)
Don’t open until notified!
Nicht o¨ffnen, warten Sie auf Anweisungen!
EXAM
REAL-TIME SYSTEMS
SS 2017
EN: Welcome to the exam on Real-Time Systems.
DE: Willkommen zur Klausur Echtzeitsysteme.
Rules Regeln
• You have 90 minutes for answering all questions. You can answer in english or german.
Sie haben zur Beantwortung aller Fragen 90 Minuten Zeit. Sie ko¨nnen auf englisch oder deutsch antworten.
• By accepting this task sheet you declare that you are in a proper health condition for an exam.
Durch Annahme des Aufgabenblattes erkla¨ren Sie, dass Sie gesundheitlich in der Lage sind, eine Pru¨fung
abzulegen.
• Please write clear and readable. Write the final results on this exam sheet!
Bitte stellen Sie Ihre Lo¨sung lesbar und sauber dar. Schreiben Sie Ihre Lo¨sungen auf dieses Aufgabenblatt!
• The only tools to be used are pens, a non-programmable calculator, and a printed dictionary without
handwritten notes.
Erlaubte Hilfsmittel sind Schreibwerkzeug, ein nichtprogrammierbarer Taschenrechner und ein gedrucktes
Wo¨rterbuch ohne handschriftliche Notizen.
• Devices with non-volatile storage or communication capabilities (whether enabled or not) are forbidden. The
presence of such devices in your proximity can be interpreted as a case of fraud.
Elektronische Gera¨te mit nichtflu¨chtigem Speicher oder Kommunikationsfa¨higkeiten - egal ob aktiviert oder
nicht - sind untersagt. Das Vorhandensein solcher Gera¨te in Ihrer Reichweite kann als Betrugsversuch gewertet
werden.
• If you have questions or if you need to go to the toilet notify a supervisor.
Wenn Sie eine Frage haben oder die Toilette besuchen mu¨ssen, melden Sie sich bitte und warten auf eine
Aufsichtsperson.
• Talking to other students or exchange of written notes during the exam can be interpreted as a case of fraud.
Gespra¨che mit anderen Studenten und der Austausch von schriftlichen Notizen sind wa¨hrend der Bearbeitungs-
zeit untersagt und ko¨nnen als Betrugsversuch gewertet werden.
• In case of a fraud, all participating students will fail the exam.
Bei unerlaubten Handlungen werden die Pru¨fungunterlagen bei allen involvierten Studierenden
eingezogen und ihnen die Note 5 erteilt.
Question 8 is a bonus task, you don’t need it to get full points.
Frage 8 ist eine Bonusaufgabe und daher zum Erreichen der vollen Punktzahl nicht no¨tig.
For passing the exam you need at least 26 points. We wish you success!
Zum Bestehen der Pru¨fung mu¨ssen sie mindestens 26 Punkte erreichen. Viel Erfolg!
Problem 1 2 3 4 5 6 7 8 Overall
Points 14 2 3 6 11 10 2 0 48
Bonus 0 0 0 0 0 0 0 3 3
Achieved
2 RTS SS 17
Problem 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . (14 Points)
All multiple choice questions have exactly one correct answer. If you mark more than one, you will get
no points. If you need to correct yourself, invalidate all checkboxes of this particular question and write
the word
”
CORRECT“ beside your intended choice. Alle Multiple-Choice-Fragen haben genau eine
korrekte Antwort. Wenn Sie mehr als eine markieren, erhalten Sie keine Punkte. Bei Korrekturbedarf
machen Sie alle Ka¨stchen fu¨r die jeweilige Frage ungu¨ltig und schreiben das Wort
”
KORREKT“ neben
die angedachte Antwort.
(a) (1)A bandlimited signal must be sampled with a sampling frequency, which is at least twice the highest
signal frequency, to allow a perfect reconstruction of the original signal.
Fu¨r ein Signal mit begrenzter Bandbreite muss die Abtastrate mindestens doppelt so hoch wie die
ho¨chste Signalfrequenz sein, um es perfekt rekonstruieren zu ko¨nnen.
© True Wahr
© False Falsch
(b) (2)Under EDF, a task set is most difficult to schedule (fully utilizes a processor) if its utilization is 1.
Unter EDF ist ein Taskmenge schwer zu planen wenn ihre Last 1 ist.
© True Wahr
© False Falsch
(c) (1)Under RMS, a critical instant of a task is if it arrives while a running low-priority task has taken a
resource, which the newly arrived task is also trying to access.
Unter RMS liegt ein kritischer Zeitpunkt fu¨r einen Task vor, wenn er freigegeben wird wa¨hrend
ein laufender niedrig priorisierterer Task eine Ressource inne hat, auf welche der neu angekommene
Task ebenfalls zugreift.
© True Wahr
© False Falsch
(d) (1)A task set is always not schedulable under RMS if its utilization violates the Liu-Layland bound.
Eine Task-Menge ist stets nicht planbar unter RMS, wenn ihre Last die Liu-Layland-Grenze verletzt.
© True Wahr
© False Falsch
(e) (1)A task set is harmonic if and only if the relations between the periods of the tasks are prime num-
bers.
Eine Task-Menge heißt harmonisch genau dann wenn die Beziehungen zwischen den Perioden Prim-
zahlen sind.
© True Wahr
© False Falsch
(f) (2)Under PCP and PIP, a job with the highest priority will never be indirectly blocked.
Unter PCP und PIP wird ein Job mit ho¨chster Priorita¨t nie indirekt blockiert.
© True Wahr
© False Falsch
Matrikelnr.: 3
(g) (1)Priority inheritance is transitive under PIP.
Priorita¨tsvererbung ist unter PIP transitiv.
© True Wahr
© False Falsch
(h) (1)Among NPCS, PIP, PCP and HLP, only NPCS is transparent to the programmer.
Von NPCS, PIP, PCP und HLP ist nur NPCS transparent fu¨r den Programmierer.
© True Wahr
© False Falsch
(i) (1)NPCS introduces two extra context switches per direct blocking.
NPCS verursacht zwei zusa¨tzliche Kontextwechsel pro direkter Blockierung.
© True Wahr
© False Falsch
(j) (1)RTO is only optimal in a deeply red system.
RTO ist nur in einem tief-roten System optimal.
© True Wahr
© False Falsch
(k) (2)In PIP, indirect blocking can only occur after direct blocking.
In PIP kann indirekte Blockierung nur nach direkter Blockierung auftreten.
© True Wahr
© False Falsch
4 RTS SS 17
Problem 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . (2 Points)
Let wi(t) be the time demand of any task Ti = (Pi, ei) till time t within a task set T = {T1, . . . , Tn}.
Provide the feasibility criterion for T!
Sei wi(t) die von allen Tasks Ti = (Pi, ei) einer Task-Menge T{T1, . . . , Tn} angeforderte Zeit bis zum
Zeitpunkt t. Geben Sie das Kriterium fu¨r die Planbarkeit von T an.
Problem 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . (3 Points)
Given a task set of n periodic tasks Ti(Pi, ei) to be scheduled by timeline scheduling (cyclic executive
scheduling). A proper framesize f is already determined. Answer the following questions using only
the given parameters!
Gegeben eine Taskmenge von n periodischen Tasks Ti(Pi, ei), die mit Timeline Scheduling (Cyclic Execu-
tive Scheduling) geplant werden sollen. Eine geeignete Framegro¨ße f wurde bereits bestimmt. Benutzen
Sie zur Beantwortung der folgenden Fragen nur die gegebenen Parameter!
(a) (1)What is the minimal length of the schedule?
Was ist die Mindestla¨nge des Plans?
(b) (1)How many jobs are to be scheduled? (without job slicing)
Wie viele Jobs entha¨lt der Plan? (ohne Jobslicing)
(c) (1)How many frames does the schedule include?
Wie viele Frames entha¨lt der Plan?
Matrikelnr.: 5
Problem 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . (6 Points)
Given a periodic task set T = {(Pi, ei)}, T = {T1(48; 18), T2(6; 2), T3(4; 1)}. It shall be scheduled on a
single processor with preemption.
Gegeben ist eine periodische Task-Menge T = {(Pi, ei)}, T = {T1(48; 19), T2(6; 2), T3(4; 1)}, die auf
einem einzelnen Prozessor mit Unterbrechbarkeit geplant werden soll.
(a) (3)Schedule T by RMS within the interval [0; 50] and draw the result into the following scheme! Do
not reorder the rows!
Planen Sie T mittels RMS im Intervall [0; 50] und zeichnen Sie ihr Ergebnis in die folgende U¨bersicht.
Vera¨ndern Sie dabei die angegebene Zeilenordnung nicht.
T3
T2
T1
0 5 10 15 20 25 30 35 40 45 50
(b) (3)Schedule T by EDF within the interval [0; 50] and draw the result into the following scheme! Do
not reorder the rows!
Planen Sie T mittels EDF im Intervall [0; 50] und zeichnen Sie ihr Ergebnis in die folgende U¨bersicht.
Vera¨ndern Sie dabei die angegebene Zeilenordnung nicht.
T3
T2
T1
0 5 10 15 20 25 30 35 40 45 50
Replacement (in case of revision) Ersatz:
T3
T2
T1
0 5 10 15 20 25 30 35 40 45 50
6 RTS SS 17
Problem 5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . (11 Points)
Given a set of jobs, resources and the corresponding (potential) requests in the picture below. A lower
job index implicates a higher priority.
Gegeben sind eine Menge an Jobs und Resourcen, sowie die entsprechenden (potentiellen) Resourcen-
Anfragen im untenstehenden Bild. Ein niedrigerer Index impliziert ho¨here Priorita¨t.
J1
J3
J2
J4
J5
X
Y
Z
(a) (9)Provide ALL the possible scenarios where J3 could be indirectly blocked under PCP. As an example,
consider the blocking by J4 after J4 has inherited the priority of J1 due to direct blocking via resource
X.
Geben Sie ALLE mo¨glichen Szenarien an, in denen J3 unter PCP indirekt blockiert werden ko¨nnte.
Zum Beispiel kann J3 durch J4 blockiert werden, nachdem J4 die Priorita¨t von J1 wegen direkter
Blockierung durch Resource X erhielt.
blocked by Ji pi inherited after blocking resource
blockiert durch Ji pi vererbt wegen blockierende Resource
J4 pi1 direct blocking X
(b) (2)Can J1 be blocked by avoidance? If yes, by whom? If no, why not?
Kann J1 durch Grenzwertblockierung blockiert werden? Wenn ja, durch wen? Wenn nein, warum?
Matrikelnr.: 7
Problem 6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . (10 Points)
Given a set J of jobs. Gegeben eine Menge J an Jobs.
(a) (8)Schedule it according to the scenario provided in the table below using PIP as resource policy.
Lower index values imply higher priority (1 is the highest). A triple [X, td, ta] means that a job
requests resource X for td time units after a execution time ta since its start. The values ri, ei and
pii indicate the release time, execution time and priority of job i, respectively.
Planen Sie J entsprechend des Szenarios aus der folgenden Tabelle unter der Verwendung von PIP.
Niedrigere Indizes implizieren ho¨here Priorita¨t, wobei 1 die ho¨chste ist. Das Tripel [X, td, ta] re-
pra¨sentiert eine Anfrage nach ResourceX fu¨r eine Dauer von td Zeiteinzeiten nach ta Ausfu¨hrungszeiteinheiten.
Die Werte ri, ei und pii geben release Zeit, Ausfu¨hrungszeit und Priorita¨t von Job i an.
Job ri ei pii Requests
J1 7 5 1 [X; 1; 1] [Z; 1; 3]
J2 5 4 2 [Z; 1; 2]
J3 3 4 3 [Y; 2; 1]
J4 2 2 4 -
J5 0 6 5 [X; 4; 1] [Y; 1; 3]
T5
T4
T3
T2
T1
0 5 10 15 20 25
Replacement (in case of revision):
T5
T4
T3
T2
T1
0 5 10 15 20 25
8 RTS SS 17
(b) (2)Is it possible to construct a deadlock situation with this task set by ONLY shifting the arrival times
of the tasks? Support your answer with an example or a proof!
Ist es mit dieser Task-Menge mo¨glich eine Deadlock-Situation zu konstruieren indem man NUR
die Ankunftzeiten der Tasks vera¨ndert? Erweitern Sie Ihre Antwort mit einem Beispiel oder einem
Beweis!
Problem 7 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . (2 Points)
Given a task set T with two tasks T1 = {12, 9} and T2 = {16, 11}. Both have a skip parameter
s1 = s2 = 2. Determine the effective utilization!
Gegeben eine Task-Menge T mit zwei Tasks T1 = {12, 9} und T2 = {16, 11}. Beide haben einen Skip-
Parameter s1 = s2 = 2. Bestimmen Sie die effektive Last.
Matrikelnr.: 9
Problem 8 (Bonus) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . (3 Points)
A basic block consists of 500 lines of code, of which 20% is accessing memory. Assume that the underlying
hardware architecture is using 2-level caching with access times for a cache hit lasting 2 and 5 ns,
respectively, and 10 and 20 ns for a cache miss. Memory is accessed after cache miss time and memory
access time is 1500 ns. Compute the overestimation of WCET in % if the real cache miss rate is 2%.
Assume for the estimation that EVERY memory access ends in a cache miss.
Ein Basisblock besteht aus 500 Codezeilen, von denen 20% auf den Speicher zugreifen. Nehmen Sie
an, dass die zugrundeliegende Architektur einen 2-stufigen Cache verwendet, dessen Zugriffszeiten fu¨r
einen Cache Hit 2 und 5 ns betra¨gt, wa¨hrend ein Cache Miss 10 und 20 ns dauert. Ein Speicherzugriff
findet im Anschluss an einen Cache Miss statt und dauert 1500 ns. Berechnen Sie die U¨berscha¨tzung der
WCET, wenn die reale Cache Miss Rate 2% betra¨gt. Nehmen Sie fu¨r die Einscha¨tzung an, dass JEDER
Speicherzugriff einen Cache Miss erzeugt.