Deadline Miss Models for Temporarily Overloaded Systems
A wide range of embedded systems falls into the category of safety-critical systems. Such systems impose different levels of safety requirements depending on how critical the functions assigned to the system are and on how humans interact with the system. Safety requirements involve timing constraints, the violation of which may lead to a system failure. Timing constraints are graded from soft to hard real-time constraints. While satisfying soft real-time constraints requires only best-efforts guarantees, hard real-time constraints are best-treated with worst-case analysis methods for verifying all timing constraints. Weakly-hard real-time systems have extra demands on the timing verification as they tolerate few deadline-misses in certain distributions. Applying worst-case analysis methods, in which a task is schedulable only when it can meet its deadline in the worst-case, to weakly-hard real-time systems questions the expressiveness of the computed guarantees. Considering tolerable deadline-misses raises the need for weakly-hard schedulability analyses to verify weakly-hard real-time constraints and to provide more expressive guarantees. This thesis addresses the schedulability analysis problem of weakly-hard real-time systems. It presents an efficient analysis to compute weakly-hard real-time guarantees in the form of a deadline miss model for various system models. The first contribution is a deadline miss model for a temporarily overloaded uniprocessor system with independent tasks under the Fixed Priority Preemptive and NonPreemptive scheduling policy (FPP & FPNP) using Typical Worst-Case Analysis. In our application context, the transient overload is due to sporadic tasks, for example, interrupt service routines. We adopt the proposed analysis to compute deadline miss models for independent tasks under the Earliest Deadline First (EDF) and Weighted Round-Robin (WRR) scheduling policies. In the second contribution, we extend the analysis to compute deadline miss models for task chains. The extension is motivated by an industrial case study. The third contribution of this thesis targets the system extensibility to budget under-specified tasks in a weakly-hard real-time system. Adding recovery or reconfiguration tasks such that the system still meets its weakly-hard timing constraints is of interest of an industrial case study (satellite on-board software) that is considered in this thesis.
Eine große Zahl von eingebetteten Systemen fällt in die Kategorie der sicherheitskritischen Systeme. Solche Systeme stellen unterschiedliche Sicherheitsanforderungen, je nachdem wie kritisch die dem System zugewiesenen Funktionen sind und wie Menschen mit dem System interagieren. Sicherheitsanforderungen beschreiben insbesondere das geforderte Echtzeitverhalten, dessen Verletzung zu einem Systemausfall führen kann. Anforderungen an das Echtzeitverhalten können unterschiedlich strikte Echtzeitbedingungen umfassen. Während die Erfüllung weicher Echtzeitbedingungen nur wenn möglich gefordert ist, braucht es zur Gewährleistung harter Echtzeitbedingungen die Anwendung von Worst-Case-Analysen zur Überprüfung der zeitlichen Bedingungen in allen Fällen. Die besondere Kategorie der schwach-harten Echtzeitsysteme hat zusätzliche Anforderungen an die Timing-Verifikation, da sie wenige Deadline-Überschreitungen mit bestimmten Mustern tolerieren. Das stellt die Aussagekraft der mit Methoden der Antwortzeitanalyse berechneten Grenzen in Frage und erhöht den Bedarf an Analysen, um die schwach-harten Echtzeitbeschränkungen zu verifizieren und aussagekräftigere Garantien zu liefern. Diese Arbeit befasst sich mit dem Problem der Scheduling-Analyse von schwach-harten Echtzeitsystemen. Es stellt eine effiziente Analyse zur Berechnung von schwach-harten Echtzeitgarantien in Form eines Deadline Miss Modells für verschiedene Systemmodelle dar. Der erste Beitrag ist ein Deadline-Überschreitungsmodell für ein temporär überlastetes Uniprozess-System mit eigenständigen Aufgaben im Rahmen der Fixed Priority Scheduling Policy mittels Typical Worst-Case Analysis. In unserem Anwendungskontext sind sporadische Tasks die Ursache von temporärer Überlast, wie zum Beispiel Interrupt Service Routines. Wir adaptieren die vorgeschlagene Analyse für Earliest Deadline First (EDF) und gewichtete Round-Robin (WRR) Scheduling. Zweitens erweitern wir die Analyse, um ein Deadline-Überschreitungsmodell für Taskketten zu berechnen. Die Erweiterung wird durch eine industrielle Fallstudie motiviert. Der dritte Beitrag dieser Arbeit zielt auf die Erweiterbarkeit des Systems bei unterdefinierte Tasks in einem schwach-harten Echtzeitsystem ab. Ziel ist es, ein Budget für Wiederherstellungs- oder Rekonfigurationstasks herzuleiten, so dass das System immer noch seine schwach-harten Echtzeitbedingungen erfüllt. Dies ist von Interesse für eine industrielle Fallstudie, die in dieser Arbeit berücksichtigt wird.
Preview
Cite
Access Statistic
Rights
Use and reproduction:
All rights reserved