Ohne Futex ist es bedeutungslos

 (h4x0r.org)
4 Punkte von GN⁺ 2025-08-21 | 1 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

Was ist Futex – und warum ist es wichtig?

  • 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

Funktionsweise und Unterschiede von 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

Praktischer Einsatz von Futex – direkte Implementierung

  • 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

Praxisnahe Beispiele für die Implementierung von Mutexen/Spinlocks/rekursiven Locks

Spinlock

  • 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

Hybrider Mutex („unsicherer“ Mutex)

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

Mutex mit Wartenden-Zähler

  • 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

Mutex mit Ownership-Verwaltung

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

Rekursiver Lock

  • 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

Offene Aufgaben und die Realität im Engineering-Alltag

  • 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

Fazit

  • 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

Referenzmaterial

  • Das vollständige Codebeispiel ist auf codeberg verfügbar

Verwandte Beiträge

1 Kommentare

 
GN⁺ 2025-08-21
Hacker-News-Kommentare

  • Windows hat eine Funktion namens WaitForMultipleObjects, und Linux hat mit Futex2 in 5.16 (Ende 2021) ebenfalls etwas in dieser Richtung eingeführt.
    Zugehöriger Link
    In letzter Zeit gab es verschiedene Verbesserungen an Futex2.
    Auch NUMA-Unterstützung wurde endlich hinzugefügt.
    NUMA-Link 1
    NUMA-Link 2
    NUMA ist für die Performance ein sehr wichtiger Faktor.
    Als io_uring in 6.7 (2024) auf futex angewendet wurde, half das bei Performance-Verbesserungen für PostgreSQL AIO.
    Zugehöriger Beitrag
    In 6.7 kamen außerdem Small requeue und Single-wait-Funktionen hinzu.
    Zugehöriger Link

    • Windows hat WaitForMultipleObjects nicht neu hinzugefügt, sondern diese Funktion seit über 30 Jahren von Anfang an gehabt.
      WaitForMultipleObjects war zwar ein Vorteil von Windows NT gegenüber UNIX, aber IBM PL/I hatte bereits 1965 eine ähnliche Funktion.
      Die wait-Funktion in UNIX war eine vereinfachte Version von wait aus IBM PL/I und war wie viele aus Multics übernommene Funktionen schwächer als das ursprüngliche Modell.
      Auch die Implementierungen von WaitForSingleObject und WaitForMultipleObjects bei Microsoft waren nicht effizient, sodass am Ende mit WaitOnAddress doch etwas eingeführt werden musste, das dem Linux-futex entspricht.
      Linux-futex hat die Einschränkungen einer 32-Bit-Größe und dass nur auf ein einzelnes Ereignis gewartet werden kann.
      Mit atomaren Bit-Operationen lässt sich Warten auf mehrere Ereignisse umsetzen, aber das ist ineffizient, wodurch die 32-Bit-Größenbeschränkung stärker ins Gewicht fällt.
      Es ist erfreulich, dass versucht wird, einige Vorteile von WaitForMultipleObjects mit futex zu verbinden.
      Das ist kein bloßes Nachahmen von Windows, sondern eigentlich die Neuimplementierung einer klassischen Technik, die weit länger als Microsoft bekannt ist — seit über 50 Jahren.

    • Schade, dass es immer noch keine futex_swap-Funktion gibt.
      Verwandte Diskussion 1
      Verwandtes Material 2

    • Futex hat nichts mit WFMO (WaitForMultipleObjects) zu tun, sondern entspricht eher keyed events.
      Die Entsprechung zu WFMO unter Linux sind select/poll/epoll.

    • Futex-Unterstützung in io_uring ist wirklich ein großartiges Feature.
      Ich habe sie bei der Arbeit mit Ruby Fibers für die Implementierung von Mutexen und Queues genutzt.
      Quellcode-Referenz

  • Im Buch steht ausdrücklich, dass man lieber die von Bibliotheken/Sprachen/Systemen bereitgestellten Synchronisationsstrukturen verwenden soll, statt sie selbst zu implementieren.
    Der Hauptfokus des Buchs liegt auf allgemeinen Concurrency-Konzepten, nicht auf einer bestimmten Plattform.
    Schade, dass der Autor des Artikels die Sache etwas überzogen als Gegensatz dargestellt hat.
    Es wäre besser gewesen, den Text aus einer kooperativen Perspektive zu behandeln, etwa als „Was TAoMP nicht sagt“.
    Auffällig ist, dass dieser Blog neu ist, Phil den Artikel gepostet hat und Phil auch andere Artikel beworben hat.

    • Ich habe den Artikel geschrieben, nachdem ich das Buch gelesen hatte und enttäuscht war.
      Ich hatte das Gefühl, dass sowohl in der akademischen Welt als auch in der Industrie zu wenig wirklich praxisnahes Wissen vermittelt wird.
      Es ging also nicht um eine Botschaft nach dem Motto „Lasst uns futex lernen!“.
      Ich war tatsächlich so enttäuscht vom Buch, dass ich andere Texte zurückgestellt und diesen zuerst geschrieben habe.
      Mit Phil habe ich durch frühere Zusammenarbeit Kontakt, aber bisher hatte ich keine großen Schwierigkeiten, Leser für meine Texte zu finden.

    • Im Nachhinein denke ich, dass die frühere Formulierung, SysV-Stil nicht einmal mit Dinosauriern zu vergleichen, zu hart war.
      Da wäre mehr Bescheidenheit angebracht gewesen.

  • Das Coolste an futex ist, dass es handle-less aufgebaut ist.
    Es liefert als kernelbasierter Speicher-Wächter ohne Allokation/Freigabe per Syscall ein sehr nützliches Grundverhalten.
    Wenn keine Threads warten, wird alles sauber aufgeräumt, und ohne Contention merkt der Kernel von dem Mutex überhaupt nichts.
    Mich würde eine detaillierte Analyse interessieren, wie der Kernel futex mit hoher Performance verwaltet.
    Von futex2 habe ich heute zum ersten Mal gehört.
    Zugehörige Dokumentation

    • Genau, und man möchte auch nicht, dass jedes Mal malloc() im Kernel aufgerufen wird, um Daten zu allokieren, wenn ein Thread an einem Lock blockiert.
      Um das zu vermeiden, allokieren viele Betriebssysteme bei der Thread-Erstellung ein „Queue Object“ und hängen dieses Objekt an das Lock, wenn der Thread auf ein umkämpftes Lock trifft.
      Dann gibt es also eine mit dem Lock verbundene Linked List aus Queue Objects verschiedener Threads, und beim Aufwachen nimmt ein Thread jeweils eines davon wieder mit.
      Es gibt keine Garantie, dass ein Thread beim Beenden genau das Objekt zurückbekommt, das er anfangs erstellt hat; unterwegs werden diese Objekte durchmischt.
      Solaris hat eine solche Struktur (Turnstile) zuerst eingeführt, und die BSDs haben dieses Verfahren übernommen.
      Verweis auf Solaris Internals
      BSD-PDF

    • So funktionierten auch die frühen Wait Queues im Unix-Kernel.

  • Schon im ursprünglichen futex-Paper von 2002 wurde die Effizienz von futex klar belegt; in Tests mit 1000 parallelen Tasks war es 20- bis 120-mal schneller als SysV-Locks.
    Allerdings ist SysV-Locking in der Praxis nicht wirklich die relevante Baseline.
    Praktisch hat eine Lock-Implementierung auch ohne futex meist keinen Kernel-Eintritt auf dem Fast Path und wechselt nur auf dem Slow Path zum Warten in den Kernel; die eigentliche Verbesserung durch futex ist nur, dass die User-Space-Datenstruktur für wartende Locks kleiner geworden ist.
    Andere Alternativen sind thin locks (wie in der JVM) oder ParkingLot (vollständig in Userland implementiert), die auch ohne OS-futex funktionieren.

    • Meiner Erfahrung nach lernen die meisten in der Praxis ohnehin die bereitgestellten Basis-Primitives kennen und konzentrieren sich darauf, was die Standardbibliothek ihrer Sprache anbietet.
      Der Übergang von SysV zu futex war also prägend, und in letzter Zeit gibt es zwar auch Custom-Ansätze, aber futex ist der Mainstream.
      Wenn man einen eigenen Userland-Scheduler bauen würde, könnte man natürlich auch etwas Eigenes implementieren, aber die meisten würden wahrscheinlich auf File Descriptors schreiben und ihre Queues selbst verwalten.
      Ich frage mich, wie groß der Nutzen einer solchen Vorgehensweise wirklich wäre.

    • Tatsächlich verwendet praktisch jedes moderne Lock intern letztlich futex, sofern es unterstützt wird.
      Weil futex unter Linux die effizienteste Form des Wartens ist, ist auf dem langsamen (down) Pfad die Nutzung von futex immer wünschenswert.
      Auch Dinge wie thread.park() in Sprachen laufen am Ende wahrscheinlich auf futex auf.

    • Ich frage mich, ob die JVM immer noch thin locks verwendet.
      Ich habe früher Verweise darauf gefunden, dass die JVM futex aufruft, und frage mich nun, ob inzwischen eine Migration zu thin locks stattgefunden hat.
      Verwandte Diskussion auf Stack Overflow

  • Die tatsächliche Implementierung von [recursive locks] ist nicht einmal zwischen Standards konsistent, und oft wird es gar nicht definiert, weil es als schwierig gilt.
    Diese Haltung ist ziemlich frustrierend.
    Das läuft auf ein „Wenn der OS- oder Sprachimplementierer Feature X nicht ordentlich implementieren kann, soll es eben der Applikationsentwickler selbst lösen“ hinaus.
    Für Downstream-Nutzer bleibt dann am Ende kaum mehr übrig, als den Vendor zu wechseln.

    • Zu starke Einschränkungen in Standards können bessere Implementierungen verbauen.
      Zum Beispiel sind die C++-Standard-Hashtabellen und regulären Ausdrücke wegen ihrer vielen Vorgaben deutlich langsamer als Alternativen von Drittanbietern.
      Wenn bestimmte Einschränkungen oder Feature-Garantien festgeschrieben werden — etwa nur Chaining zuzulassen — blockiert das alternative High-Performance-Implementierungen.
      Auch bei rekursiven RWLocks sind Implementierungen denkbar, die Performance opfern oder weniger prüfen; deshalb finde ich nicht, dass man verschiedene Richtungen unnötig verbauen sollte.

    • Ich persönlich finde ohnehin, dass man recursive locks besser gar nicht verwenden sollte, deshalb sehe ich keinen großen Grund, dafür überhaupt eine Support-Spezifikation in den Standard aufzunehmen.

    • Wer mehr über das Phänomen worse is better wissen will, kann im Wiki nachlesen.
      Ich mag es nicht besonders, aber es ist nun einmal Realität.

  • Ich habe mich gefragt, warum futex unter Linux auf 32-Bit-int beschränkt ist, und ein wenig nachgesehen.
    In der Diskussion über 64-Bit-Unterstützung erwähnte Linus, man könne im User Space 64-Bit-Atomics verwenden und nur die unteren 32 Bit als futex nutzen.
    In C/C++ gelten Mixed-Size-Atomics allerdings als Undefined Behavior, und auch die Semaphore-Implementierung in glibc arbeitet offenbar so.
    Bei einem 64-Bit-Integer werden die oberen 32 Bit als Waiter Count und die unteren 32 Bit als Semaphore-Wert verwendet, und futex wird nur auf die unteren 32 Bit angewendet.
    Ich frage mich, ob das in gcc als definiertes Verhalten gilt, ob es wegen der Prozessgrenze zum Kernel egal ist oder ob selbst glibc hier Undefined Behavior verwendet.

  • Ich empfehle auch Anthony Williams’ C++ Concurrency in Action; futex oder die direkte Implementierung von Synchronisations-Primitives werden dort zwar nicht behandelt, aber dafür praxisnähere Themen wie Memory Ordering und für lock-free Strukturen nötiges SMR.
    Wer eine stärker hardwareorientierte Perspektive möchte, dem sei außerdem Paul McKenneys kostenloses Buch „Is Parallel Programming Hard, And, If So, What Can You Do About It?“ empfohlen.
    Auch dieses Buch behandelt futex nicht im Detail, verweist aber auf Ulrich Dreppers „Futexes Are Tricky“.
    TAOMPP eignet sich gut für höherstufige Concurrency-Konzepte; Details der Implementierung auf OS-Ebene gehören dort nicht unbedingt hinein.
    Wie auch immer: Peterson- oder Bakery-Locks sind für den Praxiseinsatz nutzlos, aber schon das Verstehen ihrer Beweise hilft enorm beim Verständnis realer Concurrency-Algorithmen.

    • Bakery-Locks eignen sich als Spinlocks gut und sind cache-freundlich.
      Auch Reader/Writer-Spinlocks lassen sich damit umsetzen, allerdings mit strengem FIFO.
      Man könnte futex zwar an Spin-Waiting mit Bakery-Locks im User Space ankoppeln, aber das wäre sehr ineffizient.
      Futex wurde für solche Einsatzzwecke — also Spin-Waiting — von vornherein nicht entworfen.
      Lock-free-Strukturen, Hazard Pointers, RCU* und Ähnliches bleiben ebenfalls knifflig.
      Sogar wait-free Hazard Pointers lassen sich tatsächlich bauen.
      *Bei RCU ist Copy-on-Write zwar intuitiv, aber bei häufigen Updates steigen die Kosten.

  • So wie unter Windows 8 ein futex-ähnlicher Mechanismus eingeführt wurde, basierte die ursprüngliche Win32 Critical Section auf Kernel-Semaphoren.
    Mich würde interessieren, wie die in Vista eingeführten SRW Locks intern aufgebaut sind.

    • Sowohl CRITICAL_SECTION als auch SRWLock kommen ohne Kernel-Eintritt aus, wenn es keine Contention gibt.
      SRWLock basiert auf keyed events, während CRITICAL_SECTION bei Fehlschlägen bei Bedarf Kernel-Objekte erzeugt und auf keyed events zurückfällt.

  • Bei der 2014 von Pinkie Pie entdeckten Schwachstelle in der Linux-futex-Implementierung gilt die Requeue-once-Regel nur für den futex, der an futex_wait_requeue_pi übergeben wurde.
    Ein Requeue von A nach B und danach erneut von B nach C ist nicht möglich, aber eine Umleitung von B nach B schon.
    Dabei gibt es einen Bug, bei dem unter bestimmten Bedingungen keine Cleanup-Funktion aufgerufen wird und ein Pointer dangling zurückbleibt.
    Ein zugehöriger Fall lässt sich hier nachverfolgen.
    Zugehöriges Issue

  • Manche machen sich keine Sorgen um die Datenkonsistenz bei abgestürzten Threads, aber solange nicht gleich der ganze Prozess stirbt, bleibt das Problem der Lock-Bereinigung bestehen.
    Die Lösung dafür sind robust locks.
    Man registriert beim Kernel eine Liste gehaltener futexes, und sys_set_robust_list sorgt beim Thread-Ende dafür, dass das entsprechende Bit behandelt und die wartende Seite aufgeweckt wird.

    • Der größte Nachteil von robust locks ist, dass die vom Lock geschützte Ressource selbst möglicherweise schon in einem inkonsistenten Zustand ist.
      Wenn man nicht sicher weiß, warum der Thread abgestürzt ist, sind die Daten womöglich nicht mehr integer und eine Wiederherstellung unmöglich.
      Deshalb kann es in der Praxis sinnvoller sein, gleich die ganze Anwendung mit zu beenden.
      Cleanup- und Recovery-Funktionalität mit robust locks ist zwar elegant, aber wahrscheinlich würden 95 % der Engineers keine wirklich robusten Datenstrukturen dafür entwerfen.
      4 % hätten keine Zeit dafür, und nur das verbleibende 1 % würde es sauber umsetzen und stark davon profitieren.

    • Wenn futex zwischen mehreren Prozessen verwendet wird — also mit prozessübergreifendem Zustand — könnte ein Watchdog-Prozess pro Prozess einen Unix-Domain-Socket (SOCK_STREAM oder SOCK_SEQPACKET) offenhalten, Crashes erkennen und den jeweiligen Prozesszustand bereinigen.

    • Ich habe die Mutex-Diskussion absichtlich nur bis zur Prozessgrenze geführt, weil ich befürchtete, dass sie sonst in einer endlosen Tiefendiskussion endet.