Open Access

Eric Hutter

• Die allgemein steigende Komplexität technischer Systeme macht sich auch in eingebetteten Systemen bemerkbar. Außerdem schrumpfen die Strukturgrößen der eingesetzten Komponenten, was wiederum die Auftrittswahrscheinlichkeit verschiedener Effekte erhöht, die zu Fehlern und Ausfällen dieser Komponenten und damit der Gesamtsysteme führen können. Da in vielen Anwendungsbereichen ferner Sicherheitsanforderungen eingehalten werden müssen, sind zur Gewährleistung der Zuverlässigkeit flexible Redundanzkonzepte nötig. Ein Forschungsgebiet, das sich mit Methoden zur Beherrschung der Systemkomplexität befasst, ist das Organic Computing. In dessen Rahmen werden Konzepte erforscht, um in natürlichen Systemen beobachtbare Eigenschaften und Organisationsprinzipien auf technische Systeme zu übertragen. Hierbei sind insbesondere sogenannte Selbst-X-Eigenschaften wie Selbstorganisation, -konfiguration und -heilung von Bedeutung. Eine konkrete Ausprägung dieses Forschungszweigs ist das künstliche Hormonsystem (artificial hormone system, AHS). Hierbei handelt es sich um eine Middleware für verteilte Systeme, welche es ermöglicht, die Tasks des Systems selbstständig auf seine Prozessorelemente (PEs) zu verteilen und insbesondere Ausfälle einzelner Tasks oder ganzer PEs automatisch zu kompensieren, indem die betroffenen Tasks auf andere PEs migriert werden. Hierbei existiert keine zentrale Instanz, welche die Taskverteilung steuert und somit einen Single-Point-of-Failure darstellen könnte. Entsprechend kann das AHS aufgrund seiner automatischen (Re)konfiguration der Tasks als selbstkonfigurierend und selbstheilend bezeichnet werden, was insbesondere die Zuverlässigkeit des realisierten Systems erhöht. Die Dauer der Selbstkonfiguration und Selbstheilung unterliegt zudem harten Zeitschranken, was den Einsatz des AHS auch in Echtzeitsystemen erlaubt. Das AHS nimmt jedoch an, dass alle Tasks gleichwertig sind, zudem werden alle Tasks beim Systemstart in einer zufälligen Reihenfolge auf die einzelnen PEs verteilt. Häufig sind die in einem System auszuführenden Tasks jedoch für das Gesamtsystem von unterschiedlicher Wichtigkeit oder müssen gar in einer bestimmten Reihenfolge gestartet werden. Um den genannten Eigenschaften Rechnung zu tragen, liefert diese Dissertation gegenüber dem aktuellen Stand der Forschung folgende Beiträge: Zunächst werden die bisher bekannten Zeitschranken des AHS genauer betrachtet und verfeinert. Anschließend wird das AHS durch die Einführung von Zuteilungsprioritäten erweitert: Mithilfe dieser Prioritäten kann eine Reihenfolge definiert werden, in welcher die Tasks beim Start des Systems auf die PEs verteilt beziehungsweise in welcher betroffene Tasks nach einem Ausfall auf andere PEs migriert werden. Die Zeitschranken dieser AHS-Erweiterung werden im Detail analysiert. Durch die Priorisierung von Tasks ist es möglich, implizit Teilmengen von Tasks zu definieren, die ausgeführt werden sollen, falls die Rechenkapazitäten des Systems nach einer bestimmten Anzahl von PE-Ausfällen nicht mehr ausreichen, um alle Tasks auszuführen: Die im Rahmen dieser Dissertation entwickelten Erweiterungen erlauben es in solchen Überlastsituationen, das System automatisch und kontrolliert zu degradieren, sodass die wichtigsten Systemfunktionalitäten lauffähig bleiben. Überlastsituationen werden daher im Detail betrachtet und analysiert. In solchen müssen gegebenenfalls Tasks niedriger Priorität gestoppt werden, um auf den funktionsfähig verbleibenden PEs hinreichend viel Rechenkapazität zu schaffen, um Tasks höherer Priorität ausführen zu können und das System so in einen wohldefinierten Zustand zu überführen. Die Entscheidung, in welcher Reihenfolge hierbei Tasks gestoppt werden, wird von einer Task-Dropping-Strategie getroffen, die entsprechend einen großen Einfluss auf die Dauer einer solchen Selbstheilung nimmt. Es werden zwei verschiedene Task-Dropping-Strategien entwickelt und im Detail analysiert: die naive Task-Dropping-Strategie, welche alle niedrigprioren Tasks auf einmal stoppt, sowie das Eager Task Dropping, das in mehreren Phasen jeweils höchstens eine Task pro PE stoppt. Im Vergleich zeigt sich, dass von letzterem fast immer weniger Tasks gestoppt werden als von der naiven Strategie, was einen deutlich schnelleren Abschluss der Selbstheilung ermöglicht. Lediglich in wenigen Sonderfällen ist die naive Strategie überlegen. Es wird detailliert gezeigt, dass die entwickelte AHS-Erweiterung auch in Überlastsituationen die Einhaltung bestimmter harter Zeitschranken garantieren kann, was den Einsatz des erweiterten AHS in Echtzeitsystemen erlaubt. Alle theoretisch hergeleiteten Zeitschranken werden durch umfassende Evaluationen vollumfänglich bestätigt. Abschließend wird das erweiterte, prioritätsbasierten AHS mit verschiedenen verwandten Konzepten verglichen, um dessen Vorteile gegenüber dem Stand der Forschung herauszuarbeiten sowie zukünftige vertiefende Forschung zu motivieren.
• The generally rising complexity of technical systems is also noticeable in embedded systems. Additionally, the used components’ feature size is shrinking, which in turn increases the probability of occurrence of various effects that can cause faults and failures of these components or the entire system. Since safety requirements must be met in many application areas, flexible redundancy concepts are necessary to ensure reliability. Organic Computing is a research field dealing with methods to control system complexity. It focuses on concepts to transfer properties and organizational principles that are observable in natural systems to technical systems. In this context, so-called self-x properties such as self-organization, self-configuration and self-healing are of particular importance. A particular manifestation of this branch of research is the artificial hormone system (AHS). The AHS is a middleware for distributed systems that allows to distribute a system’s tasks autonomously to its computing nodes (processor elements, PEs) and especially to compensate failures of individual tasks or whole PEs automatically by migrating the affected tasks to other PEs. In this process, no central instance exists that controls the task distribution and would thus pose a single point of failure. Accordingly, the AHS can be described as self-configuring and self-healing due to its automatic task (re)configuration, increasing in particular the realized system’s reliability. In addition, the time required for self-configuration and self-healing is limited by hard time bounds, allowing the use of the AHS in real-time systems. However, the AHS assumes that all tasks are of the same importance for the system regardless of their respective functionality and distributes them in a random order to the individual PEs during system startup. Often, though, the tasks to be executed in a system are of varying importance to the overall system or are even required to be started in a particular sequence. In order to accommodate the aforementioned properties, this dissertation improves upon the state of the art in the following ways: Initially, the AHS’ time bounds known so far are examined more closely and refined. Afterwards, the AHS is extended by introducing assignment priorities: By utilizing these priorities, an order can be defined in which all tasks are distributed during the system’s startup or affected tasks are migrated to other PEs after a failure, respectively. The AHS extension’s time bounds are analyzed in detail. Prioritization of tasks allows to implicitly define task subsets that shall be executed if the system’s computational capacities are no longer sufficient to execute all tasks after a certain number of PE failures occurred: The extensions developed in the scope of this dissertation allow automatic and controlled system degradation in such overload situations, keeping the most important system functionality running. Consequentially, overload situations are examined and analyzed in detail. In such situations, tasks of low priority might need to be stopped after PE failures in order to free up sufficient capacities on the remaining PEs to execute tasks of higher priority, thus transitioning the system into a well-defined state. The decision in which order tasks are stopped in this process is made by a task dropping strategy that correspondingly has a great influence on the duration of such a self-healing of the system. Two different task dropping strategies are developed and analyzed in detail: the naive task dropping strategy that stops all tasks of low priority at once, and the eager task dropping which operates incrementally in multiple phases by stopping no more than one task per PE and phase. A direct comparison shows that eager task dropping almost always stops fewer tasks than the naive strategy, allowing a faster completion of the self-healing. Only in a few special cases is the naive strategy superior to the eager task dropping. It is shown in detail that the developed AHS extension can also guarantee dedicated hard time bounds in overload situations, allowing the extended AHS’ use in real-time systems. All theoretically derived time bounds are fully confirmed by comprehensive evaluations. The dissertation concludes with a comparison of the extended, priority-based AHS with different related concepts in order to highlight its advantages over the state of the art and to motivate future research.