Latency awareness in operating systems for massively parallel processors
Final Report Abstract
Ziel von LAOS (latency awareness in operating systems) war die Erforschung von Techniken zur Minimierung von Prozesslatenzen, die durch Aktionen innerhalb von Betriebssystemen entstehen und so indirekt Prozessverhalten auf Anwendungsebene beeinflussen. Im Vordergrund standen Verfahren zur Koordinierung der Kooperation und Kommunikation von gleichzeitigen und (direkt/indirekt) gekoppelten Betriebssystemprozessen, also deren Synchronisation. Eine wichtige Nebenbetrachtung dabei war, durch ein Betriebssystem keine zusätzliche Funktion zu leisten, wenn diese durch die gegebene Hardware zeitlich besser (d.h., schneller, aber auch berechen- bzw. vorhersagbar) erfüllbar ist. Thema des Projekts war ein Programmier- und Laufzeitsystem für sogenannte ”abgeschirmte Abschnitte“ (guarded sections), einem Synchronisationsparadigma, das zur Latenzverbergung beitragen kann. Abgeschirmte Abschnitte lassen wettstreitige Prozesse beim Eintrittsversuch nicht blockieren. Stattdessen erstellt jeder Prozess, der auf einen solchen Abschnitt trifft, einen Ausführungsauftrag. Diese Aufträge werden nacheinander ausgeführt, und zwar von dem Prozess, der aktuell die Kontrolle über den abgeschirmten Abschnitt besitzt. Ein Prozess erlangt Kontrolle über den Abschnitt, indem er ihn betritt und dadurch aktiviert. Es ist sichergestellt, dass niemals mehr als ein Prozess zugleich in dem Abschnitt sein kann. Prozesse, denen der Eintritt verwehrt wird, umgehen den Abschnitt und damit die Auftragsausführung als Kontrollprozess. Ist der den Abschnitt umgehende Prozess direkt von Berechnungsergebnissen oder Zustandsänderungen abhängig, die innerhalb eines solchen Abschnitts geschehen, fordert er mit dem Auftrag das Versprechen vom Kontrollprozess ein, ein diesbezügliches Ereignis in der Zukunft angezeigt und gegebenenfalls einen damit verbundenen Wert geliefert zu bekommen. In dem Fall vollzieht der Prozess Bedingungssynchronisation: Er wartet (d.h., blockiert) nur, wenn dieses Ereignis noch nicht angezeigt wurde. Einen großen Stellenwert nahmen Arbeiten zur statischen Programmanalyse ein. Diese dienten nicht nur dazu, in bestehendem Quelltext annotierte und abzuschirmende ”kritische Abschnitte“ in Bezug auf der zu erwartenden ungünstigsten Laufzeit (worst-case execution time, WCET) zu erfassen, sondern darüber hinausgehend insbesondere auch systemweite Aussagen zum voraussichtlichen Zeitverhalten eines Maschinenprogramms im Zusammenspiel mit einem Betriebssystem treffen zu können. Zu diesem Zweck wurde eine ausdrucksstarke Quelltextannotationssprache bereitgestellt, die es ermöglicht, Kontextabhängigkeit auf Bibliotheksebene unter Verwendung benutzerdefinierter Abstraktionen auszudrücken. Diese Abstraktionen ermöglichen es, kontextabhängige Daten-/Kontrollflussfakten bis hin zur Granularität einzelner Schleifenkontexte generisch zu kommentieren und compilergestützt bis auf die Befehlssatzebene hinunter zu übertragen.
Publications
- In the heat of conflict: On the synchronisation of critical sections. In S. Fischmeister, M. Pacher, A. Myrick, O. Rana, and A. Easwaran, editors, Proceedings of the 20th IEEE International Symposium on Real-Time Distributed Computing (ISORC 2017), pages 42–51. IEEE Computer Society Press, 2017
S. Reif, T. Hönig, and W. Schröder-Preikschat
(See online at https://doi.org/10.1109/ISORC.2017.18) - A predictable synchronisation algorithm. In A. Krall and T. Gross, editors, Proceedings of the 23rd ACM SIGPLAN Annual Symposium on Principles and Practice of Parallel Programming (PPoPP ’18), pages 415–416, New York, NY, USA, 2018. ACM Digital Library
S. Reif and W. Schröder-Preikschat
(See online at https://doi.org/10.1145/3178487.3178533) - INTspect: Interrupt latencies in the Linux kernel. In Proceedings of the VIII Brazilian Symposium on Computing System Engineering (SBESC 2018), pages 83–90. IEEE Xplore, 2018
B. Herzog, L. Gerhorst, B. Heinloth, S. Reif, T. Hönig, and W. Schröder-Preikschat
(See online at https://doi.org/10.1109/SBESC.2018.00021) - Towards system-wide timing analysis of real-time–capable operating systems. In M. Maggio, editor, Proceedings of the Work-in-Progress Session of the 30th Euromicro Conference on Real-Time Systems (ECRTS’18), pages 10–12. ECRTS, 2018
S. Schuster, P. Wägemann, P. Ulbrich, and W. Schröder-Preikschat
- Asynchronous abstract machines: Anti-noise system software for many-core processors. In Proceedings of the 9th International Workshop on Runtime and Operating Systems for Supercomputers (ROSS 2019), pages 16–26, New York, NY, USA, 2019. ACM, ACM Digital Library
S. Maier, T. Hönig, P. Wägemann, and W. Schröder-Preikschat
(See online at https://doi.org/10.1145/3322789.3328744) - Control-flow migration for datalocality optimisation in multi-core real-time systems. In Proceedings of the 41st IEEE Real-Time Systems Symposium (RTSS 2020), Brief Presentations: Work-in-Progress, pages 371–374. IEEE Computer Society, 2020
S. Reif, P. Raffeck, P. Ulbrich, and W. Schröder-Preikschat
(See online at https://doi.org/10.1109/RTSS49844.2020.00041) - Precisely timed task execution. In Proceedings of the 2020 IEEE 23rd International Symposium on Real-Time Distributed Computing (ISORC), pages 10–19. IEEE Computer Society, 2020
S. Reif and W. Schröder-Preikschat
(See online at https://doi.org/10.1109/ISORC49007.2020.00012) - Annotate once — analyze anywhere: Context-aware WCET analysis by user-defined abstractions. In Proceedings of the 22nd ACM SIGPLAN/SIGBED International Conference on Languages, Compilers, Tools and Theory for Embedded Systems (LCTES’21), pages 54–66. ACM, 2021
S. Schuster, P. Wägemann, P. Ulbrich, and W. Schröder-Preikschat
(See online at https://doi.org/10.1145/3461648.3463847)
