Ein hierarchisches Scheduling-Modell für unbekannte Anwendungen mit schwankenden Ressourcenanforderungen

Abstract

Weiche Echtzeitsysteme, die mit unbekannten, dynamisch gestarteten und gestoppten Anwendungen umgehen müssen, sind schwer zu analysieren in Hinblick auf ihre Planbarkeit. Ein solches System muss in der Lage sein, sich dynamisch an die tatsächlichen Anforderungen der Anwendungen anzupassen. Es benötigt ebenso Mechanismen zur Kontrolle und Behebung von Überlast, welche durch die Konkurrenz der Anwendungen um gemeinsam genutzte Ressourcen entstehen kann. Da Schätzungen der Ausführungszeiten von Anwendungsaktivitäten von vornherein nicht bekannt sind, muss das System diese zur Laufzeit ermitteln und sich auf Schwankungen im Ressourcenverbrauch der Aktivitäten einstellen. Im Rahmen dieser Promotionsarbeit wurde aus diesem Kontext ein adaptives, hierarchisches Scheduling-Modell abgeleitet, das mit einer dynamischen Menge von unbekannten Applikationen mit schwankenden Ressourcenanforderungen umgehen kann. Auf der untersten Ebene stellt der Scheduler die korrekte Ausführung von Applikationsaufgaben, gemäß ihrer zur Laufzeit approximierten Bedarfe, sicher. Auf den höheren Ebenen werden Applikationen voneinander isoliert, während der Scheduler kontinuierlich die ihnen zugewiesenen Kapazitäten kalibriert und lokale Planbarkeitsanalyse betreibt. Entstehen Engpasssituationen, so wird ein Mechanismus zur gezielten Herabsetzung (Degradierung) der Ressourcenanforderungen der Applikationen angewendet. Dabei wird dynamisch jeweils eine von mehreren Qualitätsstufen (Betriebsmodi) der Anwendungen ausgewählt und umgeschaltet. Solche Rekonfigurationen sollen allerdings so selten wie möglich stattfinden, da sie mit zusätzlichen Kosten für die Anwendungen und das System verbunden sind. Mit dem erarbeiteten Scheduling-Modell wird das Problem des Planbarkeitsnachweises räumlich partitioniert und zeitlich verteilt. Planbarkeitstests werden nur bei Bedarf für bestimmte Bereiche im System betrieben, dann und dort, wo es notwendig ist. In der Zwischenzeit nimmt der Scheduler die Planbarkeit der bestehenden Konfiguration an, solange die Kostenschätzungen der Applikationsaktivitäten bestimmte adaptive Sicherheitspuffer nicht überschreiten. Werden die Toleranzgrenzen verletzt, so wird eine neue optimale Ressourcenkonfiguration berechnet und dabei unter Umständen die Qualität einer oder mehrerer Anwendungen verändert. Treten Frist- oder Toleranz-Verletzungen periodisch auf, so werden diese vom System detektiert und damit verbundene periodische Rekonfigurationen automatisch unterdrückt. Das Scheduling-Modell wurde mit RTSJ implementiert und innerhalb eines Soft-Echtzeit-Frameworks ARTOS integriert. Für dessen Evaluation wurden unter anderem künstliche Anwendungen entwickelt, die eine reale Arbeitslast erzeugen und dabei bestimmte Lastprofile befolgen. Bei den Experimenten wurden die Applikationen zunächst mit einer niedrigen Priorität gestartet und initial ausgemessen. Dadurch entstehen erste Schätzungen für alle Anwendungsmodi, welche bei späterer Aktivierung verfeinert werden. Somit konnte bereits experimentell nachgewiesen werden, dass (a) das System schnell eine optimale Modi-Selektion für die Anwendungen etabliert, (b) es planbar bleibt, solange Tasks innerhalb der ermittelten Toleranzgrenzen verbleiben, (c) Fristverletzungen nur dann auftreten, wenn Tasks ihre Grenzen verlassen, (d) Planbarkeitstests häufiger für Apps durchgeführt werden, deren Task-Anforderungen sich stärker als die Adaptionsgeschwindigkeit ihrer Sicherheitspuffer verändern und (f) zyklische Bursts automatisch durch das System detektiert und behandelt werden. Eine automatische Anpassung der Adaptionsgeschwindigkeit der Sicherheitspuffer, anhand eines dynamisch extrahierten Verhaltensprofils für die jeweilige Anwendung, ist in Arbeit. Anhand des bereitgestellten Entwicklungsmodells für ARTOS-kompatible Applikationen, wurde darüber hinaus im Rahmen dieser Arbeit eine Video-On-Demand Anwendung implementiert, die zur weiteren Evaluation des Modells anhand eines realen Szenarios dient. Das Scheduling-Modell wurde bereits als Grundlage für die Ressourcensteuerung innerhalb einer dynamischen Cloud-Plattform verwendet.Soft real-time systems that have to deal with unknown, dynamically loaded and stopped applications are hard to analyse for feasibility. Such systems must be capable to dynamically adapt themselves to actual requirements of applications. They further require mechanisms to control and resolve overload situations, which may arise while apps compete for common shared resources. Since estimations of actual execution times of activities are not available from the start, they have to be determined by the system during runtime. The estimations must be also adopted to fluctuations within the measured resource demands of the activities. In this PhD thesis an adaptive hierarchical scheduling model for a dynamic set of applications with fluctuating resource demands has been developed. On the lowest level the scheduler ensures correct execution of application tasks according to online approximations of their demands. On the higher levels isolation between the apps is provided while the scheduler continuously re-calibrates given capacities and performs local schedulability analysis for application tasks. In bottleneck situations an optimal degradation is applied by assigning one of different quality levels to the apps based on their resource estimations and priorities. Thereby, applications are activated in different operational modes. However, such reconfigurations must happen as rarely as possible, because they introduce an additional computational overhead for the system. With the proposed scheduling architecture the problem of proving schedulability is spatially partitioned and temporally distributed. Tests are performed portion-wise only when and where necessary. The model maintains feasibility until cost estimations violate custom safety buffers and resource bounds. In such cases a new optimal resource configuration is computed changing the quality of some apps. Periodic violations are also dedected automatically suppressing recurring reconfigurations in the system. The scheduling model was implemented with RTSJ and integrated within a soft real-time framework ARTOS. For evaluation of its scheduling mechanisms artificial apps were developed, which can produce real computational overhead within a platform following a certain load-profile. In our experiments new apps were run with a low priority until their modes were initially estimated. We were able to verify that (a) the system quickly establishes an optimal modes selection respecting priorities (b) it remains feasible when tasks reside within their tolerance limits (c) deadline misses occur only if tasks leave their safety buffers (d) feasibility analysis is performed more frequently for apps with stronger fluctuations than their buffer adaptation speed and (f) cyclic bursts can be automatically detected and treated by the system. An automatic adjustment of the buffer adaptation speed based on dynamically extracted application profiles is planned for the future. Based on the provided architectural model for multi-mode applications, an ARTOS-compatible Video-on-Demand application was implemented and used for further evaluation of the scheduler within a realistic scenario. The scheduling model has been further used as a basis for an adaptive resource-management framework within a dynamic cloud-platform~\cite{nikolov2014}.