Futex- Futex
In der Computertechnik ist ein Futex (kurz für "fast userspace mutex ") ein Kernel -Systemaufruf , den Programmierer verwenden können, um grundlegende Sperren zu implementieren , oder als Baustein für Sperrabstraktionen auf höherer Ebene wie Semaphoren und POSIX- Mutexes oder Bedingungsvariablen .
Ein Futex besteht aus einer Kernelspace- Warteschlange , die an eine atomare Ganzzahl im Userspace angehängt ist . Mehrere Prozesse oder Threads arbeiten mit der Ganzzahl vollständig im Userspace (mit atomaren Operationen , um gegenseitige Störungen zu vermeiden) und greifen nur auf relativ teure Systemaufrufe zurück , um Operationen in der Warteschlange anzufordern (z den aktuellen Prozess in der Warteschlange). Eine richtig programmierte futex-basierte Sperre verwendet keine Systemaufrufe, es sei denn, die Sperre ist umstritten; Da die meisten Operationen keine Arbitrierung zwischen Prozessen erfordern, wird dies in den meisten Fällen nicht passieren.
Geschichte
Unter Linux haben Hubertus Franke ( IBM Thomas J. Watson Research Center ), Matthew Kirkwood, Ingo Molnár ( Red Hat ) und Rusty Russell ( IBM Linux Technology Center ) den futex-Mechanismus entwickelt. Futexes erschien erstmals in der Version 2.5.7 der Linux-Kernel-Entwicklungsserie; die Semantik stabilisierte sich ab Version 2.5.40, und futexes sind seit der Veröffentlichung der stabilen Kernel-Serie 2.6.x im Dezember 2003 Teil der Linux-Kernel-Mainline .
Im Jahr 2002 wurde ein Vorschlag diskutiert, Futexe über das Dateisystem zugänglich zu machen, indem ein spezieller Knoten in /dev
oder erstellt wird /proc
. Doch Linus Torvalds strikt gegen diese Idee und verwarf alle zugehörigen Patches.
Futexe werden seit Windows 8 bzw. Windows Server 2012 unter dem Namen WaitOnAddress in Microsoft Windows implementiert.
Im Jahr 2013 patentierte Microsoft Futexe und das Patent wurde 2014 erteilt.
Im Mai 2014 gab das CVE- System eine im futex-Subsystem des Linux-Kernels entdeckte Schwachstelle bekannt, die Denial-of-Service-Angriffe oder lokale Rechteausweitung ermöglichte.
Im Mai 2015 führte der Linux-Kernel über Commit b0c29f79ecea einen Deadlock-Bug ein , der zu einem Hängenbleiben in Benutzeranwendungen führte. Der Fehler betraf viele Enterprise-Linux-Distributionen, einschließlich 3.x- und 4.x-Kernel sowie Red Hat Enterprise Linux Version 5, 6 und 7, SUSE Linux 12 und Amazon Linux.
Futexe sind seit 2016 in OpenBSD implementiert.
Der futex Mechanismus ist eine der grundlegenden Konzepte des Zircon - Kernel in Google ‚s Fuchsia Betriebssystem seit mindestens April 2018.
Betrieb
Futexes haben zwei grundlegende Operationen WAIT
und WAKE
.
WAIT(addr, val)
- Wenn der Wert an der Adresse gespeichert
addr
istval
, legt den aktuellen Thread zu schlafen.
WAKE(addr, num)
- Weckt die
num
Anzahl der Threads auf, die auf die Adresse wartenaddr
.
Für fortgeschrittenere Anwendungen gibt es eine Reihe anderer Operationen, die am häufigsten verwendet werden REQUEUE
und WAKE_OP
die beide als allgemeinere WAKE
Operationen fungieren .
CMP_REQUEUE(old_addr, new_addr, num_wake, num_move, val)
- Wenn der unter der Adresse gespeicherte Wert
old_addr
istval
, werdennum_wake
Threads, die auf die Adresse wartenold_addr
, aufgeweckt undnum_move
Threads, die auf die Adresseold_addr
warten, in die Warteschlange gestellt, um jetzt auf die Adresse zu wartennew_addr
. Dies kann verwendet werden, um das Problem der donnernden Herde im Kielwasser zu vermeiden .
WAKE_OP(addr1, addr2, num1, num2, op, op_arg, cmp, cmp_arg)
- Lesen
addr2
, führen Sieop
mitop_arg
auf, und speichert das Ergebnis anaddr2
. Dann werdennum1
wartende Threads aufgewecktaddr1
, und wenn der zuvor gelesene Wert vonaddr2
Übereinstimmungencmp_arg
mit Vergleich verwendetcmp
wird, werdennum2
Threads aufgeweckt, die auf wartenaddr2
. Dieser sehr flexible und generische Wake-Mechanismus ist nützlich, um viele Synchronisationsprimitive zu implementieren.
Siehe auch
Verweise
Externe Links
- - futex()-Systemaufruf
- - futex-Semantik und -Benutzung
- Hubertus Franke, Rusty Russell, Matthew Kirkwood. Aufregung, Futexes und Furwocks: Fast Userlevel Locking in Linux , Ottawa Linux Symposium 2002.
- Drepper, Ulrich (2011). "Futexe sind knifflig" (PDF) . 1.6. Roter Hut.
- Bert Hubert (2004). Inoffizielle Futex-Manpages
- Ingo Molnar. " Robuste Futexes ", Linux-Kernel-Dokumentation
- " Priority Inheritance Futexes ", Linux-Kernel-Dokumentation