SC(5): Schneller Gegenseitiger Ausschluss im Userspace

Im SystemCall Podcast beschäftigen wir uns mit aktueller
Betriebssystemforschung. Diese fünfte Folge ist eine besondere
Folge, denn wir sprechen mit dem Preisträger des
Promotionspreises der Fachgruppe Betriebssysteme, Alexander Züpke
über einen Teil seiner Dissertation. Alex ist Postdoc an der TU
München und hat im Bereich Echtzeit-Mikrokernel unter Anderem an
schnellen Mechanismen für gegenseitigen Ausschluss geforscht.


Alex beschreibt uns den Stand von Futexes, also schnellem
Gegenseitigen Ausschluss im Userspace, in Linux. Dieser
optimistische Ansatz geht davon aus, dass die meisten Locks oder
Mutexes genommen werden, obowohl wahrscheinlich kein Wettstreit
darum herrscht, d.h. die meiste Kerninteraktion für diesen
gegenseitigen Ausschluss nicht nötig wäre.


Beim Futex arbeiten die Synchronisationsprimitive erst einmal
optimistisch mit atomaren Operationen im Userspace, und erst
falls festgestellt wird, dass das Futex umstritten ist, wird in
den Kernel gewechselt um passives Warten umzusetzen. Atomare
Operationen sind dabei Prozessorinstruktionen, die bspw. ein
Laden und das Setzen einer Speicherstelle in einem Zug erledigen,
also aus der Sicht der anderen Prozessoren untrennbar (atomar).
Das wird benutzt um gleichzeitig einen neuen Wert zu schreiben
und den alten Wert zu lesen, um den gegen bekannte Werte zu
vergleichen. Bspw. bedeutet 0, der kritische Abschnitt ist nicht
besetzt, 1 er ist besetzt und 2 er ist besetzt und es warten
Threads.


Alex beschreibt die Defizite der Implementierung der
Warteschlangen im Linux-Kernel, und diskutiert die
Implementierung der Futexe in einem Echtzeit-Mikrokernel.
Echtzeit bedeutet in dem Kontext, dass jede Operation im System
gewisse Zeitgarantien einhalten kann, und das belegbar ist. Bspw.
dass eine kritische Anwendung auch mit diesen Futexen, aller X
Millisekunden läuft und seine Berechnungen durchführen kann.
Links

https://blexi.de/papers/



A. Zuepke, R. Kaiser, Deterministic Futexes: Addressing WCET and
Bounded Interference Concerns, RTAS 2019, DOI:
10.1109/RTAS.2019.00014


IEEE

Authors Copy



A. Zuepke, Turning Futexes Inside-Out: Efficient and
Deterministic User Space Synchronization Primitives for Real-Time
Systems with IPCP, ECRTS 2020, DOI: 10.4230/LIPIcs.ECRTS.2020.11


Dagstuhl

Authors Copy

Intro-/Outrotheme

the_emergent