Ohne Futex ist es bedeutungslos

(h4x0r.org)

4 Punkte von GN⁺ 2025-08-21 | Noch keine Kommentare. | Auf WhatsApp teilen

Es wird kritisiert, dass das Lehrbuch The Art of Multiprocessor Programming das Konzept des Futex (futex) nicht behandelt
Futex ist ein zentraler Baustein für effiziente Synchronisation in der modernen Parallelprogrammierung und bietet bessere Leistung als ältere Locks auf Basis von System V
Futex trennt Lock-Erwerb und Warten/Aufwecken, wodurch unnötige System Calls und Overhead reduziert werden
Enthalten sind Beispiele und Techniken, um auf Futex-Basis verschiedene Concurrency-Primitiven wie Spinlocks, Mutexe und rekursive Locks direkt zu implementieren
Der Autor bemängelt, dass das Buch keine modernen Synchronisationsmethoden, die für die Engineering-Praxis essenziell sind, behandelt, und verweist damit auf die Kluft zwischen akademischer Welt und Praxis

Einleitung

Phil Eaton startet einen Buchclub zu The Art of Multiprocessor Programming, 2nd Edition
Das Buch gilt als maßgebliches Lehrwerk im Bereich Parallelprogrammierung, doch der Autor kritisiert den Mangel an praktischer Relevanz
Insbesondere wird beanstandet, dass ein Werk, das sich an fortgeschrittene Bachelor-Studierende und Graduierte richtet, die zentrale Synchronisationstechnik Futex nicht behandelt

Futex ist die Abkürzung für „fast user space mutex“ und tatsächlich weniger ein Mutex als vielmehr ein vom Betriebssystem unterstützter Synchronisations-Primitive-Baustein für moderne Lock-Implementierungen
Früher wurden die meisten Locks auf Basis von Semaphore-Mechanismen aus System V IPC implementiert, was Effizienz und Skalierbarkeit begrenzte
Mit der Einführung von Futex in Linux im Jahr 2002 zeigte sich in Umgebungen mit 1000 gleichzeitigen Tasks eine 20- bis 120-fach höhere Leistung gegenüber System-V-Locks
Andere Betriebssysteme wie Windows (2012) und macOS (2016) führten ähnliche Mechanismen ein
Heute verwenden Locks in verbreiteten Systembibliotheken wie pthreads Futex

Klassische Semaphore kombinierten Locking und Warten, doch Futex trennt Lock-Erwerb und Warten/Aufwecken
Dadurch lassen sich unnötige Verzögerungen und System Calls verringern; wenn beim Freigeben eines Locks sicher keine wartenden Threads existieren, ist kein Eintritt in den Kernel nötig
Der Futex-wait-Aufruf blockiert nur dann, wenn „der Wert an einer bestimmten Speicheradresse dem erwarteten Zustand entspricht“, und unterstützt auch Timeouts
Der Futex-wake-Aufruf weckt aus einer internen Warteliste, die an eine bestimmte Speicheradresse gebunden ist, die gewünschte Anzahl von Threads auf
Weil eine Validierung des tatsächlichen Werts an der Speicheradresse verlangt wird, wird unnötiges Warten vermieden, wenn sich der Zustand bereits geändert hat

Da Futex eine Low-Level-Primitive ist, werden unter Berücksichtigung von Fragen der Reihenfolge von Speicheroperationen durch Compiler und Hardware atomic-Datentypen verwendet
Unter Linux muss der Futex-System-Call direkt per syscall aufgerufen werden; unter macOS wird die __ulock-Schnittstelle verwendet (inzwischen gibt es auch einfachere APIs)
Grundsätzlich liefert Futex-Wait bei Erfolg 0, bei Fehlschlag einen Fehlercode (z. B. Timeout) zurück
Zentrale Operationen auf Futex-Basis:
- h4x0r_futex_wait_timespec() : wartet, wenn der Erwartungswert übereinstimmt; Timeout möglich
- h4x0r_futex_wake() : weckt einen oder alle Wartenden auf

Die einfachste Form eines Locks, die nur mit einem einzelnen Bit (atomic_fetch_or) arbeitet
Es wird in einer Endlosschleife („Spin“) gewartet, bis das Lock verfügbar ist; bei hoher Contention führt das jedoch zu CPU-Verschwendung sowie zu strukturellen Problemen wie fehlerhaftem Freigeben und Deadlocks bei rekursiven Aufrufen

Üblicherweise wird zuerst per Spinlock versucht zu sperren; nach einer bestimmten Zahl erfolgloser Versuche wird für effizientes Blockieren auf Futex umgeschaltet
Wenn keine Wartenden existieren, lassen sich unnötige System Calls vermeiden, und die Zahl der Wake-System-Calls kann minimiert werden
Da strikte Ownership-Prüfung und Rekursionsbehandlung fehlen, wird die Bezeichnung „unsafe“ verwendet

Ein Bit steht für den Lock-Zustand, die übrigen Bits dienen zur Erfassung der Zahl wartender Threads, um unnötige Wake-System-Calls zu reduzieren
Ownership- und Rekursionsbehandlung fehlen weiterhin

Über pthread_t wird der Besitzer des Locks und dessen Zustand eindeutig nachverfolgt, sodass Probleme bei fehlerhaftem unlock oder rekursiver Nutzung erkannt werden können
Lock-Erwerb, Freigabe und Verwaltung der Wartenden werden vollständig durch strikte atomare Operationen gesteuert

Durch einen zusätzlichen Depth-Zähler pro Thread kann derselbe Thread ein Lock mehrfach verschachtelt erwerben
Beim unlock wird die Depth verringert; erreicht sie 0, erfolgt die tatsächliche Freigabe samt Aufwecken
Alle Operationen werden mit atomaren Operationen und strenger Ownership-Prüfung implementiert

Wenn der Thread, der ein Lock hält, abnormal beendet wird oder stirbt, sind zur Lock-Verwaltung zusätzliche Verwaltungslisten, Exit-Callbacks und ähnliche Mechanismen nötig
Auch bei gemeinsam genutzten Mutexen zwischen Prozessen sind zusätzliche Überlegungen zum Zustandsmanagement erforderlich
POSIX-RW-Locks definieren rekursive Verschachtelung nicht einheitlich, und das Verhalten unterscheidet sich je nach Implementierung, was die Absicherung in der Praxis erschwert
Der Autor kritisiert, dass das Buch in der Praxis wirklich wichtige Concurrency-Themen (Futex, rekursive Locks, asynchrone Runtimes usw.) nicht in den Lehrplan aufnimmt

The Art of Multiprocessor Programming ist zu stark auf historische oder theoretische Perspektiven fokussiert und vermittelt wichtiges modernes Praxiswissen zur Parallelprogrammierung nicht angemessen
Wenn zentrale Synchronisationsbausteine wie Futex in der Lehre nicht angemessen behandelt werden, kann das für nachfolgende Generationen von Entwicklerinnen und Entwicklern praktischen Schaden anrichten
Der Autor betont die Notwendigkeit, aktuelle Konzepte einzubeziehen und die Inhalte praxisnäher zu ergänzen