Latency awareness in operating systems for massively parallel processors

• Applicant: Professor Dr.-Ing. Wolfgang Schröder-Preikschat
• Subject Area: Security and Dependability, Operating-, Communication- and Distributed Systems
• Term: from 2011 to 2022
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 188499432

• Final Report Year: 2022

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
  
• 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
  
• 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
  
• 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
  
• 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
  
• 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
  
• 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