Efficient and robust dynamic scheduling and synchronization in practical embedded real-time multiprocessor systems

Multiprocessors are on the way to become a standard platform for embedded systems with real-time requirements. For real-time systems, it is crucial that functional and temporal constraints are fulfilled. The focus of this dissertation lies on the aspect of these timing requirements. Within this context, two fundamental questions arise: (1) How to schedule a given task set on the available cores, and (2) How to synchronize tasks without a loss of data consistency and unbounded blocking times. In theory, optimal scheduling algorithms are already known. In this case, optimal means that if there is any option that a task set fulfills all its temporal requirements, the algorithm finds such a schedule. Nevertheless, they are not in practical use (at least in automotive powertrain systems) because these optimal algorithms are accompanied by overheads caused by core migrations, context switches and the need for repeatedly priority calculations. This thesis tries to close the gap between theory and practice by developing a concept for an efficient implementation global scheduler with dynamic priorities that fulfills the requirements of engine control units. Furthermore, there exists no generic optimal multiprocessor real-time synchronization mechanism that is able to handle all types of task allocation and priorities, and supports as well resting of resource requests. Thus, two different locking protocols are provided that outperform existing ones for specific types of task sets for embedded multiprocessor real-time systems. Case studies are presented that evaluate the assumptions of the efiiciency and robustness of the locking protocols.Multi-Prozessor Systeme haben in eingebettete Systeme mit Echtzeit Anforderungen Einzug gehalten. Für Echtzeitsysteme ist entscheidend, dass sowohl funktionale als auch temporale Erfordernisse eingehalten werden. Diese Dissertation beschäftigt sich mit dem Aspekt der zeitlichen Anforderungen an Echtzeitsysteme. In diesem Kontext stehen zwei grundlegende Fragen im Raum, nämlich (1) Wie verteilt man die zur Ausführung bereiten Tasks am besten auf die zur Verfügung stehenden Rechenkerne? (2) Wie synchronisiert man die Tasks ohne dass die Datenkonsistenz beeinträchtigt wird und unnötige oder endlose Blockierzeiten entstehen? Es wurden bereits Scheduling-Algorithmen entwickelt, die theoretisch optimal sind. Optimal bedeutet in diesem Kontext, dass wenn immer es eine Möglichkeit gibt, ein Task-Set ohne Deadline Verletzung auszuführen, der Algorithmus eine solche Möglichkeit auch findet. Diese optimalen Algorithmen haben sich jedoch in der Praxis (z.B. im Antriebsstrang von Automobilen) bisher nicht durchgesetzt, da mit dem Einsatz dieser Scheduling Algorithmen eine Vielzahl an Kern-Migrationen, Kontextwechsel und die Notwendigkeit von Prioritäts-Neuberechnungen einhergehen, die zu Verzögerungen des gesamten Systems führen. Diese Arbeit versucht, die Lücke zwischen Theorie und Praxis ein Stück weit zu schließen. Dafür wurde ein Konzept für einen globalen Scheduling Algorithmus entwickelt, der effizient zu implementieren ist und Prioritätsänderungen während der Laufzeit zulässt. Er enthält außerdem Erweiterungen, die beim Einsatz in Motorsteuergeräten benötigt werden. Im Fall der zweiten Frage stellte sich heraus, dass es kein Synchronisationsprotokoll gibt, das für alle Arten von Task-Sets und Hardwarearchitekturen optimal ist, also so wenig Blockierzeiten wie möglich verursacht. Daher werden im Rahmen dieser Arbeit zwei Synchronisationsprotokolle für Multi-Prozessor Echtzeitsysteme vorgestellt, die bisher entwickelten Protokolle in der Vermeidung von Blockierzeiten für bestimmte Task-sets überlegen sind. Diese Protokolle werden mittles diskreter, event-basierter Simulation im Rahmen einer Fallstudie experimentell evakuiert