Folgende Materialien helfen beim Erstellen von wissenschaftlichen Arbeiten:

• Vorlage für Studien-, Bachelor und Masterarbeiten am FG Echtzeitsysteme [Github]
• Vorlage für Präsentationen am FG Echtzeitsysteme [Github]

Typ der Arbeit: Bachelor-Thesis, Master-Thesis
Bearbeitungsstand: Offene Arbeiten
Möglicher Beginn der Arbeit: 01.06.2023
Betreuer*in: M.Sc. Maximilian Kratz

Zurück zur Übersicht

Motivation

Im Bereich der echtzeitkritischen Systeme werden sogenannte Schedulingalgorithmen eingesetzt um beispielsweise Rechenaufgaben mit festen Fristen den zur Verfügung stehenden CPU-Kernen eines Prozessors zuzuweisen.
Dabei müssen Fristen und eventuell weitere Bedingungen eingehalten werden, da ansonsten Konflikte bei der Ausführung des gesamten Programms (welches aus den einzelnen Rechenaufgaben besteht) auftreten können.
Ein Schedulingalgorithmus muss dabei nicht nur die Reihenfolge der einzelnen Rechenaufgaben berücksichtigen sondern auch die Zuweisung (Mapping) der Aufgaben zu CPU-Kernen berechnen.

Ein Ansatz zur Berechnung von Scheduling-Algorithmen ist die Verwendung eines Integer Linear Programming (ILP) Solvers um stets eine optimale Lösung zu finden.
Bisher werden dafür die ILP-Probleme in der Regel entweder per Hand erstellt oder es muss aufwändig ein Generator implementiert werden, der anschließend für verschiedene Scheduling-Probleme jeweils ein ILP-Problem generiert.

Das am Fachgebiet entwickelte Tool GIPS (https://gips.dev) wird dazu verwendet, um automatisch aus graphbasierten Einbettungsproblemen ILP-Probleme zu generieren und diese durch einen ILP-Solver lösen zu lassen.
Ein Teil dieses Workflows ist eine Problemspezifikation in der domänenspezifischen Sprache GIPSL.
Mit der Hilfe von GIPS ist es folglich möglich, ILP-Probleme aus einer Spezifikation (=GIPSL) und einer Modellinstanz (=einem Graphen) automatisiert zu generieren.

Aufgabenstellung

Das Ziel der Arbeit ist, einen bekannten Scheduling-Algorithmen (Rate Monotonic Scheduling) mit Hilfe des GIPS-Frameworks zu implementieren und zu evaluieren.
Dafür sind folgende Arbeitspakete notwendig:

• Entwurf eines kleinen Simulationsframeworks für Scheduling-Algorithmen
• Implementierung eines Aufgabengenerators sowie eines Lösungsvalidators
• Erstellung eines Lastenheftes und Arbeitsplans in Absprache mit dem Betreuer
• Forschungsfragen:
  • Lässt sich der Rate Monotonic Scheduling Algorithmus mit GIPSL spezifizieren?
  • Bis zu welcher Modellgröße ist der ILP-Solver in der Lage, eine Zuweisen der Aufgaben in annehmbarer Zeit durch den Algorithmus zu finden?
• Evaluation: Performancemessung und Vergleich des Scheduling-Algorithmus für mehrere Modellgrößen (=Menge an Aufgaben).

Voraussetzungen

• Sehr gute Java-Programmierkenntnisse
• Vorkenntnisse über ILP (wünschenswert aber optional)
• Vorkenntnisse aus dem Bereich der Echtzeitsysteme, z. B. aus der gleichnamigen Vorlesung (hilfreich aber optional)
• Vorerfahrung modellgetriebene Softwareentwicklung (hilfreich aber optional)

Zurück zur Übersicht

Zu den abgeschlossenen Arbeiten