Integrated Task and Message Scheduling in Time-Triggered Aeronautic Systems
This thesis presents generation techniques for task and message configurations in time-triggered IMA architectures. The commonality among the given techniques is the problem of integrated task and message scheduling for time-triggered networks. The proposed approaches allow the automatic generation of task and message schedules, which comprises certain system requirements.
Our first approach solves the task and message scheduling problem by regarding it as a graph problem. We present an off-line scheduling algorithm that traverses the precedence graph. The approach integrates task scheduling at system level and message scheduling at communication level by iteratively traversing the given precedence graph. The algorithm incorporates backtracking and path extension functionality, guaranteeing the consistency of the developed schedule.
The main advantage of the algorithm is that it scales up well even for large avionics applications.
Furthermore, this thesis extends ongoing research into task and message scheduling based on time-triggered networks by first using model checking techniques for solving this kind of problem. We demonstrate that state-of-the-art model checking and bounded model checking techniques can be used to compute a schedule that fulfills certain system requirements. Therefore, we introduce an approach that adopts the principle of symbolic state space exploration to schedule synthesis and provides a symbolic encoding which makes it possible to guarantee an optimal solution with respect to minimizing the system’s end-to-end latency. A developed heuristic approach extends this approach in order to increase scalability by preventing from an exhaustive search through a guided, weight-based state-space exploration. The developed approaches are implemented in a framework for scheduling synthesis. This framework enables the generation and investigate certain system configurations in terms of complexity. This is done by using a complexity evaluation approach, which is developed is this thesis.
Diese Arbeit präsentiert Techniken zur Generierung von integrierten Task- und Message Konfigurationen für zeitgesteuerte IMA Architekturen. Den präsentierten Ansätzen liegt das Problem der Erzeugung von integrierten Task und Message Schedules für zeitgesteuerte Netzwerke zugrunde.
Die entwickelten Ansätze generieren dabei automatisch integrierte Task und Message Schedules, die speziellen Systemanforderungen genügen.
Unser erster Ansatz löst das Task und Message Scheduling Problem mittels Transformierung in ein Graphen - Problem. Ein Algorithmus wird entwickelt, der den Abhängigkeitsgraphen durchläuft und dabei sowohl das Task Scheduling auf Systemebene, als auch das Message Scheduling auf Kommunikationsebene einbezieht. Der präsentierte Ansatz arbeitet iterativ und enthält Überprüfungs- und Pfad-Erweiterungs-Funktionalität, die die zeitliche Konsistenz des entwickelten Schedules garantieren. Einer der Vorteile dieses Ansatzes ist die Skalierbarkeit, die es ermöglicht, auch größere aeronautische Architekturen zu untersuchen und entsprechende Konfigurationen bereitzustellen.
Ein zweiter Ansatz beschreibt und löst erstmals das gegebene Problem mit Hilfe von Model - Checking Techniken. Diese Arbeit zeigt, dass aktuelle Model - Checking und Bounded Model - Checking Techniken genutzt werden können, um integrierte Task und Message Schedules zu berechnen, die speziellen Systemeigenschaften genügen. Wir präsentieren einen Ansatz, der das Prinzip der Zustandsraumexploration zur Scheduling Synthese nutzt. Dazu entwickeln wir eine symbolische Kodierung, die es nicht nur ermöglicht gültige Konfigurationen zu finden, sondern auch solche, die optimal sind bezüglich der Minimierung der Ende-zu-Ende Latenz.
Zusätzlich präsentieren wir einen heuristischen Ansatz, der es erlaubt, die Skalierbarkeit deutlich zu verbessern, indem er das Problem der erschöpfenden Suche einschränkt. Die entwickelte Heuristik führt dabei eine gesteuerte, gewichtsbasierte Erkundung des Zustandsraumes durch.
Die entwickelten Ansätze sind in einem Framework zur Scheduling Synthese implementiert. Dieses Framework erlaubt die Generierung von geeigneten System Konfigurationen als auch Komplexitätsuntersuchung für verschiedene Systemarchitektur - Szenarien. Dazu wird ein Ansatz zur Evaluierung von Komplexitätsuntersuchungen entwickelt.
Vorschau
Zitieren
Zitierform:
Zitierform konnte nicht geladen werden.