Concurrency platforms are a widespread tool for writing
comprehensible and maintainable programs utilizing the parallel
computing resources provided by modern hardware. Language-based
concurrency platforms like Google’s Go expand the benefits of concurrent
programming to system requests by providing a seemingly blocking API and
thus allow, e.g., the creation of simple while high-performant network
services. Existing concurrency platforms rely on outdated synchronous
I/O and readiness interfaces of the underlying operating system. Schmaus
et al. proposed a general and highly efficient way to integrate
system-request capabilities into a prototypical concurrency platform
employing modern queue-based asynchronous system-request interfaces
(e.g., Linux’s io_uring). This thesis takes the proposed
integration one step further by adapting the inexpensive and effective
work-stealing scheme to the request completions asynchronously generated
by the operating system. Furthermore, it presents a novel synthesis of
the concurrency platform worker-suspension mechanisms with the
queue-based system-request interface. This synthesis, combined with
specialized task-suspension kernel-interface waitfd,
increases the runtime systems throughput while reducing its latency. The
in this thesis proposed waitfd interface allows efficient
futex-like suspension while passing information about where
new work can be obtained to an awoken worker. This information helps to
mitigate the initial uninformed randomized work stealing. Additionally,
using a specialized in-kernel object (i.e., waitfd) allows
the operating system to participate in the suspension mechanisms by
directly posting notifications about completed system requests (e.g., a
completed read() operation). This participation prevents
further context-switches caused otherwise by an additional round-trip
through user space. Micro-benchmarks show that posting notifications
from the kernel is an adequate tradeoff compared to busy polling between
continuation latency (42us higher latency) and power consumption (55.51%
less energy needed). A network echo server benchmark shows that
completion stealing increases the runtime system’s throughput by 54.87%
and using a waitfd-based sleep strategy by 61.2% compared
to the status quo. Furthermore, a waitfd-based sleep
strategy can reduce the time needed to search the Linux kernel source
for a fixed string by 4.95%.
Nebenläufigkeitsplattformen sind ein weit verbreitetes Werkzeug, um
verständliche und wartbare Programme zu schreiben, welche die parallelen
Rechenressourcen moderner Hardware ausnutzen.
Programmiersprachenbasierte Nebenläufigkeitsplattformen, wie z.B. Go der
Firma Google, erweitern die Vorteile nebenläufiger Programmierung mit
Betriebssystemfunktionen, indem sie eine vermeintlich blockierende
Programmierschnittstelle anbieten, wodurch z.B. das Schreiben einfacher
aber hoch-performanter Netzwerkdienste ermöglicht wird. Bestehende
Nebenläufigkeitsplattformen setzen auf überholte synchrone E/A- und
Verfügbarkeitsschnittstellen des zugrundeliegenden Betriebssystems.
Schmaus et al. haben eine generische, hocheffiziente Integration von
Betriebssystemfunktionen in eine prototypische Nebenläufigkeitsplattform
vorgestellt, basierend auf modernen warteschlangenbasierten, asynchronen
Schnittstellen, wie Linux’s io_uring. Diese Arbeit
verbessert die vorgeschlagene Integration durch die Anwendung der
günstigen und effektiven Arbeitsentzugs-Ablaufplanung auf die asynchron
erzeugten Ergebnisse der Betriebssystemfunktionen. Des Weiteren
präsentiert sie eine neuartige Synthese der Arbeiterprozessstilllegung
einer Nebenläufigkeitsplattform mit der warteschlangenbasierten
Betriebssystemschnittstelle. Diese Synthese in Kombination mit der auf
Stilllegung spezialisierten Kernschnittstelle waitfd
erhöhen den Durchsatz und reduzieren die Verzögerung des
Laufzeitsystems. Die in dieser Arbeit vorgeschlagene waitfd
Schnittstelle erlaubt die futex ähnliche Prozessstilllegung
sowie das Zustellen von Informationen an aufgeweckte Prozesse, wo Arbeit
gefunden werden kann. Diese Information hilft den anfänglichen,
uninformierten zufälligen Arbeitsentzug einzudämmen. Zusätzlich
ermöglicht die Verwendung des spezialisierten Kernobjekts
waitfd dem Betriebssystem am Stilllegungsverfahren
teilzunehmen, indem es direkt Benachrichtigungen über abgeschlossene
Systemanfragen (z.B. eine abgeschlossene Leseoperation) bekanntmacht.
Diese Kooperation des Betriebssystems vermeidet zusätzliche
Kontextwechsel erzeugt durch ein ansonsten benötigtes Hin-und-Zurück
durch den Benutzerbereich. Mikroexperimente zeigen, dass das
Bekanntmachen von Ereignissen aus dem Kern einen geeigneten Kompromiss
zwischen Verzögerung (42us höhere Verzögerung) und Stromverbrauch
(55.51% weniger Stromverbrauch) im Vergleich zu anhaltendem Abfragen
darstellt. Ein Netzwerk-Echoserver-Experiment zeigt, dass Ergebnisentzug
den Durchsatz des Systems um 54.87% steigert, sowie die Verwendung eines
auf waitfd basierenden Stilllegungsverfahrens 61.2%
verglichen mit dem Status Quo. Darüber hinaus verkürzt das
waitfd basierte Verfahren die Zeit, den Linux Quellcode
nach einem festen Wort zu durchsuchen, um 4.95%.
Florian Fischer, “Elevating System Requests to First-Class Citizens of Work-Stealing Concurrency Platforms”, Master’s Thesis, Friedrich-Alexander-Universität Erlangen-Nürnberg (FAU), Dept. of Computer Science, June 2022. MA-I4-2022-01. DOI: 10.25593/opus4-fau-19938
PDF Copyright 2022 Florian Fischer.
This thesis is licensed under a Creative Commons
Attribution-NonCommercial-NoDerivatives 4.0 International License. To
view a copy of this license, visit https://creativecommons.org/licenses/by-nc-nd/4.0/.
Fischer, Florian. (2022). Florian Fischer Master thesis data. Zenodo. https://doi.org/10.5281/zenodo.6587463