TUD Logo

TUD Home » ... » Teaching » Operating Systems and Security » Quantitative Methods

Operating Systems

Exercise: Quantitative Methods

Quantitative Methoden

Geplante Bearbeitungszeit: eine Woche

1. Aufgabe:

Gegeben sei die Präzedenzrelation {(A, C), (B, C), (C, D), (E, D), (E, F)} zwischen sechs Jobs A, …, F. Die Jobs erfordern folgende Bedienungszeiten (in einer bestimmten Zeiteinheit):
A B C D E F
2 3 3 2 5 4
Zur Bearbeitung stehen zwei gleichartige Prozessoren zur Verfügung. Die Jobs sind nicht unterbrechbar.
  1. Zeichnen Sie den Präzedenzgraphen (einschließlich der Bedienungszeiten) als Vorgangspfeilnetz. Beachten Sie dabei die folgenden Regeln, die für Vorgangspfeilnetze gelten:
    • Es darf nur einen Anfangsknoten und einen Endknoten geben.
    • Zwischen zwei Knoten darf es nur eine Kante (ohne weitere Zwischenknoten) geben.
    • Kanten sollten sich nicht kreuzen.
    • Es sollten so wenig Scheinvorgänge als möglich verwendet werden.
    • Alle Pfeile (alle Kanten des Graphen) müssen von links nach rechts gerichtet sein.
    Überlegen Sie sich auch, welches die Motivationen für diese Regeln sind!
  2. Geben Sie die Ablaufpläne (Gantt-Diagramme) gemäß FIFO (dies sei die in der Tabelle stehende Reihenfolge), SPT und LPT an. Berechnen Sie in allen Fällen die relevanten Bewertungsgrößen! Erläutern Sie (unter Einbeziehung dieser Ergebnisse) die Bedeutung der einzelnen Zuteilungsstrategien. Welcher Ablaufplan ist optimal?
  3. Versuchen Sie, einen Ablaufplan zu konstruieren, der gleichzeitig zu maximalem Durchsatz und zu minimaler mittlerer Jobverweilzeit führt. Vergleichen Sie die Ergebnisse mit den in  ermittelten Werten.
  4. Unter welchen Modifikationen der Voraussetzungen lassen sich prinzipiell weitere Verbesserungen erreichen? Inwieweit ist dies im konkreten Fall möglich?
  5. Inwieweit ändern sich die Ergebnisse, wenn nur ein Prozessor zur Verfügung steht?

2. Aufgabe:

In einem Betriebssystem erfolge das Scheduling nach dem Round-Robin-Verfahren mit der Zeitscheibenlänge Q. n Jobs, von denen jeder den (einzigen) Prozessor für T = kQ Zeiteinheiten (k ∈ ℕ + ) beansprucht, werden gleichzeitig in die Warteschlange bereiter Jobs eingereiht. Berechnen Sie die Wartezeit für jeden Job und die mittlere Wartezeit für die Menge der n Jobs. Was folgt daraus für den Fall des sog. Prozessor-Sharings (Zeitquant der Größe 0)?
Hinweis: Betrachten Sie zunächst bei n = 4 und T = 10 die drei Fälle Q = 10, Q = 5, Q = 1.


3. Aufgabe:

Geben Sie einen Überblick über das Scheduling in Echtzeitsystemen (Aufgaben und Begriffe – Modellannahmen – wichtige Scheduling-Verfahren und deren Eigenschaften – Kriterien für die Zulassung einer Task-Menge).

4. Aufgabe:

In einem Ein-Prozessor-Echtzeitsystem sind zwei periodische Tasks T1, T2 einzuplanen mit folgenden Werten (pi Periodenlänge, ti Bearbeitungszeit, Periodenende = Zeitschranke):
p1 = 5  s,  t1 = 2  s p2 = 3  s,  t2 = 1  s
Zwischen den Tasks bestehen keine Abhängigkeiten; sie sind an beliebiger Stelle unterbrechbar. Die Tasks sollen auf möglichst einfache Weise (geringer Overhead) eingeplant werden.
  1. Untersuchen Sie, inwieweit dies möglich ist.
  2. Nach einiger Zeit ist eine weitere Task T3 einzuplanen mit p3 = 5  s,  t3 = 1  s. Diskutieren Sie die entstandene Situation.
  3. Nachträglich stellt sich heraus, dass für T1 ein Prozessorbedarf von 2, 1  s erforderlich ist. Welche Konsequenzen hat dies für Zulassung und Einplanung der drei Tasks?
Last modified: 15th Nov 2018, 8.30 PM
Author: Jan Bierbaum

Contact
Sorry — there was an error in gathering the desired information

Regulations
  • ModuleModules: INF-B-380, INF-LE-EUI
  • 4/2/0 = 6 SWS
Time and Place
  • Lecture, weekly
    TimeTue, 9.20 AM PlaceHSZ 0004
  • Lecture, weekly
    TimeFri, 9.20 AM PlaceHSZ 0003
Time and Place
  • Lecture, weekly
    TimeTue, 9.20 AM PlaceHSZ 0004
  • Lecture, weekly
    TimeFri, 9.20 AM PlaceHSZ 0003