Futex-Grundlagen

Futex (futex - Abkürzung für "Fast Userspace Mutex") ist ein Mechanismus, der von Linux-Entwicklern von IBM im Jahr 2002 vorgeschlagen und Ende 2003 in den Kernel aufgenommen wurde. Die Hauptidee bestand darin, eine effizientere Möglichkeit zum Synchronisieren von Benutzer-Threads mit einer minimalen Anzahl von Aufrufen an den Betriebssystemkern bereitzustellen.

In diesem Artikel werden wir die Futexe überprüfen, versuchen, die Prinzipien ihrer Arbeit zu verstehen und sie auch als Bausteine ​​verwenden, um übergeordnete (und uns vertraute) Synchronisationsobjekte zu erstellen.

Ein wichtiger Punkt: Futexes ist ein eher einfaches Tool, das sich nur bei der Entwicklung grundlegender Bibliotheken wie der Standard-C / C ++ - Bibliothek direkt lohnt. Es ist sehr unwahrscheinlich, dass Sie in einer regulären Anwendung Futexe verwenden müssen.

Motivation

Vor dem Aufkommen von Futexen war es erforderlich, jedes Mal Systemaufrufe (z. B. mit semop ) durchzuführen , um den Zugriff auf gemeinsam genutzte Ressourcen von mehreren Threads aus zu steuern. Dies ist bekanntlich ressourcenintensiv, da bei jedem Aufruf der Kontext vom Benutzermodus in den Kernelmodus geändert werden muss. Mit der Zunahme der Anzahl von Kernen in modernen Prozessoren und der Zunahme der Anzahl von Threads in Anwendungssoftware ist dies zu einem erheblichen Problem geworden. Es ist sogar noch „beleidigender“, da alle diese Aufrufe keine angewendete Funktion enthalten, keine Geschäftslogik implementieren, sondern nur den korrekten Betrieb des restlichen Codes garantieren.

Der Vorschlag, dem Betriebssystem ein neues Konzept von „Futex“ hinzuzufügen, basierte auf einer einfachen Beobachtung: In den meisten Fällen ist der Versuch, ein Synchronisationsobjekt zu erfassen, zum ersten Mal erfolgreich. Programmierer schreiben Software so, dass vom Sperren des Schlosses bis zum Entsperren so wenig Zeit wie möglich vergeht. Dies bedeutet, dass die Wahrscheinlichkeit sehr hoch ist, dass ein Versuch, einen anderen Thread zu erfassen, nicht auf Hindernisse stößt. Wenn ein Stream ein solches "freies" Synchronisationsobjekt erreicht, können wir es erfassen, ohne einen Systemaufruf mit relativ billigen atomaren Operationen durchzuführen. Und es besteht eine sehr große Chance, dass die atomare Operation erfolgreich funktioniert.

In diesem seltenen Fall gibt eine atomare Operation einen Fehler zurück, wenn wir immer noch versuchen, auf eine Ressource zuzugreifen, die von einem anderen Thread blockiert wurde. In diesem Fall haben wir zwei Möglichkeiten. Wir können entweder eine Spin-Sperre des Benutzermodus aktivieren und auf die Freigabe der Ressource warten (die die CPU-Ressourcen verschlingt), oder den Kernel bitten, uns in den Ruhemodus zu versetzen und auf die Freigabe der Ressource zu warten. Hier kommen die Futexe ins Spiel.

Einfache Verwendung von Futexen - Erwartung und Erwachen

Der Futex-Systemaufruf kombiniert eine Vielzahl von Funktionen. Wir werden hier keine komplexen Optionen betrachten (einige davon sind so ausführlich, dass sie nicht einmal in der offiziellen Dokumentation beschrieben werden), aber wir werden uns auf die Operationen FUTEX_WAIT und FUTEX_WAKE konzentrieren. Die Beschreibung in der offiziellen Dokumentation dient als gute Grundlage:

Der Systemaufruf futex () bietet Programmen eine Methode, um darauf zu warten, dass eine bestimmte Bedingung erfüllt wird. In der Regel verwendet dieser Systemaufruf ein Blockierungskonstrukt im Kontext der Synchronisierung des gemeinsam genutzten Speichers. Bei Verwendung von Futexen werden die Hauptsynchronisationsvorgänge im Benutzerbereich ausgeführt. User-Space-Programme führen den Systemaufruf futex () nur aus, wenn das Programm längere Zeit in den Standby-Modus wechseln muss, bis die Bedingung erfüllt ist. Außerdem kann futex () verwendet werden, um Prozesse oder Threads zu aktivieren, die eine bestimmte Bedingung erwarten.

Einfach ausgedrückt ist ein Futex ein Kernelkonstrukt, mit dessen Hilfe Benutzercode Threads synchronisieren kann, wenn etwas passiert. Einige Prozesse (oder Threads) können auf Ereignisse in einem FUTEX_WAIT-Aufruf warten, während andere diese Ereignisse mit FUTEX_WAKE aufrufen können. Das Warten funktioniert effizient - wartende Threads werden vom Kernel angehalten und verwenden keine Prozessorressourcen, bis sie bei Auftreten eines erwarteten Ereignisses aktiviert werden.

Nehmen Sie sich Zeit, um die gesamte Dokumentation zu lesen. Nun, oder lesen Sie zumindest die Abschnitte über FUTEX_WAIT und FUTEX_WAKE.

Schauen wir uns ein einfaches Beispiel an , das die grundlegende Verwendung von Futexen zur Koordinierung der Arbeit zweier Prozesse demonstriert.

Untergeordneter Prozess:

1. Wartet auf 0xA im allgemeinen Speichersteckplatz
2. Schreibt den Wert 0xB in diesen Steckplatz

Übergeordneter Prozess zu diesem Zeitpunkt:

1. Schreibt einen 0xA-Wert in einen gemeinsam genutzten Speichersteckplatz
2. Wartet darauf, dass 0xB darin angezeigt wird

Ein solcher „Handschlag“ zwischen zwei Prozessen. Hier ist der Code:

int main(int argc, char** argv) { int shm_id = shmget(IPC_PRIVATE, 4096, IPC_CREAT | 0666); if (shm_id < 0) { perror("shmget"); exit(1); } int* shared_data = shmat(shm_id, NULL, 0); *shared_data = 0; int forkstatus = fork(); if (forkstatus < 0) { perror("fork"); exit(1); } if (forkstatus == 0) { //   printf("child waiting for A\n"); wait_on_futex_value(shared_data, 0xA); printf("child writing B\n"); //  0xB         *shared_data = 0xB; wake_futex_blocking(shared_data); } else { //   printf("parent writing A\n"); //  0xA         *shared_data = 0xA; wake_futex_blocking(shared_data); printf("parent waiting for B\n"); wait_on_futex_value(shared_data, 0xB); // Wait for the child to terminate. wait(NULL); shmdt(shared_data); } return 0; } 

Achten Sie auf POSIX-Aufrufe, um gemeinsam genutzten Speicher zwischen Prozessen zuzuweisen. Wir konnten hier nicht die übliche Speicherzuordnung verwenden, da selbst die gleiche Adresse von Zeigern in verschiedenen Prozessen tatsächlich auf verschiedene Speicherblöcke verweisen würde (für jeden Prozess eindeutig).

Es ist zu beachten, dass dieses Beispiel etwas von den Kanonen abweicht, da der Futex ursprünglich erstellt wurde, um auf eine Änderung einer bestimmten Bedeutung „von etwas Bestimmtem zu etwas“ und nicht „von etwas zu etwas Bestimmtem“ zu warten. Ich habe dieses Beispiel gegeben, um eine solche Möglichkeit zu demonstrieren, und im Folgenden werden wir die Basisversion betrachten (darauf implementieren wir den Mutex).

Und hier ist der Funktionscode wait_on_futex_value:

 void wait_on_futex_value(int* futex_addr, int val) { while (1) { int futex_rc = futex(futex_addr, FUTEX_WAIT, val, NULL, NULL, 0); if (futex_rc == -1) { if (errno != EAGAIN) { perror("futex"); exit(1); } } else if (futex_rc == 0) { if (*futex_addr == val) { //    return; } } else { abort(); } } } 

Die Hauptaufgabe dieser Funktion (neben dem eigentlichen Aufruf des Futex-Systems) ist ein Zyklus, in dem wir ausgeführt werden, wenn wir falsch aufwachen (nicht an uns interessiert). Dies kann passieren, wenn ein neuer Wert, der von uns nicht erwartet wird, im gemeinsam genutzten Speichersteckplatz installiert wird. Nun, oder in dem Fall, in dem ein anderer Prozess früher als bei uns ausgelöst wurde (dies kann in unserem speziellen Fall nicht geschehen, ist aber allgemeiner möglich).

Futex-Semantik ist ziemlich knifflig! Der Aufruf von FUTEX_WAIT wird sofort zurückgegeben, wenn der Wert an der Futex-Adresse nicht dem übergebenen Argument val entspricht. In unserem Fall kann dies passieren, wenn der untergeordnete Prozess gewartet hat, bevor der übergeordnete Prozess den Wert 0xA in den Steckplatz geschrieben hat. Der Futex gibt in diesem Fall den Wert EAGAIN zurück.

Und hier ist der Funktionscode wake_futex_blocking:

 void wake_futex_blocking(int* futex_addr) { while (1) { int futex_rc = futex(futex_addr, FUTEX_WAKE, 1, NULL, NULL, 0); if (futex_rc == -1) { perror("futex wake"); exit(1); } else if (futex_rc > 0) { return; } } } 

Dies ist ein blockierender Wrapper über FUTEX_WAKE, der schnell arbeitet und einen Wert zurückgibt, unabhängig davon, wie viele Listener ihn erwarten. In unserem Beispiel wird dies als Teil eines „Handshakes“ verwendet, aber andere Verwendungen sind möglich.

Futexe sind Kernel-Warteschlangen für benutzerdefinierten Code.

Einfach ausgedrückt ist ein Futex eine kernelgesteuerte Warteschlange zum Lösen von benutzerdefinierten Codeaufgaben. Es ermöglicht dem Benutzercode, den Kernel aufzufordern, die Ausführung seines Threads anzuhalten, bis ein Ereignis eintritt, und gleichzeitig dem anderen Thread dieses Ereignis zu signalisieren und alle darauf wartenden Threads zu aktivieren. Zuvor haben wir die Möglichkeit erwähnt, eine Spin-Sperre im Benutzermodus zu organisieren und darauf zu warten, dass eine Bedingung erfüllt wird. Die Warteschlange im Kernel ist jedoch eine viel bessere Alternative, da sie uns Milliarden verschwendeter Prozessoranweisungen erspart, die in einer Warteschleife ausgeführt werden.

Hier ist das Diagramm aus dem Artikel „Eine Futex-Übersicht und ein Update“ auf LWN:



Im Linux-Kernel-Code sind die Futexe in der Datei kernel / futex.c implementiert. Der Kernel speichert eine Hash-Tabelle, in der die Schlüssel Adressen sind, um schnell die gewünschte Warteschlange zu finden und den aufrufenden Prozess hinzuzufügen. Natürlich ist nicht alles so einfach - schließlich muss der Kernel selbst den Zugriff auf die darin enthaltenen Daten synchronisieren und alle möglichen zusätzlichen Optionen für futeksov unterstützen.

Zeitlich begrenztes Warten mit FUTEX_WAIT

Der Futex-Systemaufruf verfügt über einen Timeout-Parameter, mit dem der Benutzer angeben kann, wie lange er warten möchte. Hier ist ein vollständiges Beispiel, in dem dies implementiert ist, aber hier ist der Schlüsselteil:

 printf("child waiting for A\n"); struct timespec timeout = {.tv_sec = 0, .tv_nsec = 500000000}; while (1) { unsigned long long t1 = time_ns(); int futex_rc = futex(shared_data, FUTEX_WAIT, 0xA, &timeout, NULL, 0); printf("child woken up rc=%d errno=%s, elapsed=%llu\n", futex_rc, futex_rc ? strerror(errno) : "", time_ns() - t1); if (futex_rc == 0 && *shared_data == 0xA) { break; } } 

Wenn das Warten um 500 ms verzögert wird, endet die Futex-Funktion und in der nächsten Iteration der Schleife können wir irgendwie darauf reagieren (etwas auf dem Bildschirm anzeigen, in das Protokoll schreiben, das Warten fortsetzen oder anhalten).

Verwenden eines Futex zum Implementieren eines Mutex

Wir haben diesen Artikel mit der Tatsache begonnen, dass Futexe bei der Implementierung übergeordneter Synchronisationsobjekte von praktischem Nutzen sind. Versuchen wir, sie (sowie Atomics) zu verwenden, um den klassischen Mutex zu implementieren. Die folgende Implementierung basiert auf dem Code aus dem Artikel „Futexes are Tricky“ von Ulrich Drepper.

In diesem Beispiel verwende ich C ++, hauptsächlich für die Verwendung von Atomics aus dem C ++ 11-Standard. Den vollständigen Code finden Sie hier , aber der wichtigste Teil ist:

 class Mutex { public: Mutex() : atom_(0) {} void lock() { int c = cmpxchg(&atom_, 0, 1); // If the lock was previously unlocked, there's nothing else for us to do. // Otherwise, we'll probably have to wait. if (c != 0) { do { // If the mutex is locked, we signal that we're waiting by setting the // atom to 2. A shortcut checks is it's 2 already and avoids the atomic // operation in this case. if (c == 2 || cmpxchg(&atom_, 1, 2) != 0) { // Here we have to actually sleep, because the mutex is actually // locked. Note that it's not necessary to loop around this syscall; // a spurious wakeup will do no harm since we only exit the do...while // loop when atom_ is indeed 0. syscall(SYS_futex, (int*)&atom_, FUTEX_WAIT, 2, 0, 0, 0); } // We're here when either: // (a) the mutex was in fact unlocked (by an intervening thread). // (b) we slept waiting for the atom and were awoken. // // So we try to lock the atom again. We set teh state to 2 because we // can't be certain there's no other thread at this exact point. So we // prefer to err on the safe side. } while ((c = cmpxchg(&atom_, 0, 2)) != 0); } } void unlock() { if (atom_.fetch_sub(1) != 1) { atom_.store(0); syscall(SYS_futex, (int*)&atom_, FUTEX_WAKE, 1, 0, 0, 0); } } private: // 0 means unlocked // 1 means locked, no waiters // 2 means locked, there are waiters in lock() std::atomic<int> atom_; }; 

In diesem Code ist die cmpxhg-Funktion ein einfacher Wrapper für die bequemere Verwendung von Atomen:

 // An atomic_compare_exchange wrapper with semantics expected by the paper's // mutex - return the old value stored in the atom. int cmpxchg(std::atomic<int>* atom, int expected, int desired) { int* ep = &expected; std::atomic_compare_exchange_strong(atom, ep, desired); return *ep; } 

Dieses Codebeispiel enthält viele Kommentare, die die Logik seiner Funktionsweise erläutern. Dies wird nicht schaden, da das Risiko groß ist, dass Sie eine etwas einfachere, aber völlig falsche Version davon schreiben möchten. Dieser Code ist auch nicht in allem perfekt. Zum Beispiel versucht er, eine Annahme über ein internes Gerät vom Typ std :: atomic zu machen, indem er seinen Inhalt in int * umwandelt, um ihn an den Futex-Aufruf weiterzuleiten. Dies ist in der Regel nicht der Fall. Der Code wird unter Linux x64 kompiliert und ausgeführt, es gibt jedoch keine Garantie für die Kompatibilität mit anderen Plattformen. Um dies zu erreichen, müssen wir eine Plattformabhängigkeitsschicht für Atome hinzufügen. Da dies nicht das Thema dieses Artikels ist (und es auch sehr unwahrscheinlich ist, dass Sie Futexe im selben C ++ - Modul mischen), wird diese Implementierung weggelassen. Dies ist nur eine Demonstration!

Glibc-Mutexe und Low-Level-Schlösser

So kamen wir zu dem Punkt, an dem glibc POSIX-Threads implementiert, von denen ein Teil der Typ pthread_mutex_t ist. Wie ich am Anfang dieses Artikels sagte, sind Futexe nicht ganz das, was ein gewöhnlicher Entwickler braucht. Sie werden von Laufzeitbibliotheken oder etwas sehr Spezialisiertem verwendet, um übergeordnete Synchronisationsprimitive zu implementieren. In diesem Zusammenhang ist es interessant, die Implementierung des Mutex für NPTL zu betrachten . Im Glibc-Code ist dies die Datei nptl / pthread_mutex_lock.c.

Der Code ist ziemlich kompliziert, da verschiedene Arten von Mutexen unterstützt werden müssen, aber wir können auf Wunsch recht vertraute Blöcke finden. Sie können sich auch die Dateien sysdeps / unix / sysv / linux / x86_64 / lowlevellock.h und nptl / lowlevellock.c ansehen. Der Code ist etwas verwirrend, aber die Kombination von Vergleichs- und Austausch- und Futex-Aufrufen ist immer noch einfach.

Der erste Kommentar der Datei systeds / nptl / lowlevellock.h sollte von Ihnen bereits gut verstanden werden:

 /* Low-level locks use a combination of atomic operations (to acquire and release lock ownership) and futex operations (to block until the state of a lock changes). A lock can be in one of three states: 0: not acquired, 1: acquired with no waiters; no other threads are blocked or about to block for changes to the lock state, >1: acquired, possibly with waiters; there may be other threads blocked or about to block for changes to the lock state. We expect that the common case is an uncontended lock, so we just need to transition the lock between states 0 and 1; releasing the lock does not need to wake any other blocked threads. If the lock is contended and a thread decides to block using a futex operation, then this thread needs to first change the state to >1; if this state is observed during lock release, the releasing thread will wake one of the potentially blocked threads. .. */ 

Gehen Sie Laufzeit-Futexe

Rantime Go verwendet libc (in den meisten Fällen) nicht. Daher kann es sich nicht auf die Implementierung von POSIX-Threads verlassen. Stattdessen werden direkt untergeordnete Systemaufrufe aufgerufen. Dies macht es zu einem guten Beispiel für die Verwendung von Futexen. Da es keine Möglichkeit gibt, pthread_mutex_t aufzurufen, müssen Sie Ihren eigenen Ersatz schreiben. Lassen Sie uns sehen, wie dies gemacht wird. Beginnen wir mit dem für den Benutzer sichtbaren Typ sync.Mutex (in src / sync / mutex.go).

Die Sperrmethode dieses Typs versucht, mithilfe der Atom-Swap-Operation die Sperre schnell zu erfassen. Wenn sich herausstellt, dass Sie warten müssen, ruft es runtime_SemacquireMutex auf, das runtime.lock aufruft. Diese Funktion ist in src / runtime / lock_futex.go definiert und deklariert mehrere Konstanten, die Ihnen bekannt vorkommen:

 const ( mutex_unlocked = 0 mutex_locked = 1 mutex_sleeping = 2 ... ) // Possible lock states are mutex_unlocked, mutex_locked and mutex_sleeping. // mutex_sleeping means that there is presumably at least one sleeping thread. 

runtime.lock versucht auch, die Sperre mithilfe einer atomaren Funktion zu erfassen. Dies ist sinnvoll, da runtime.lock an vielen Stellen der Go-Laufzeit aufgerufen wird. Es scheint mir jedoch möglich zu sein, den Code zu optimieren, indem beim Aufrufen von runtime.lock aus Mutex.lock zwei aufeinanderfolgende Aufrufe der atomaren Funktion entfernt werden.

Wenn sich herausstellt, dass Sie warten müssen, wird die plattformabhängige Funktion futexsleep aufgerufen, die für Linux in der Datei src / runtime / os_linux.go definiert ist. Diese Funktion führt einen Futex-Systemaufruf mit dem Code FUTEX_WAIT_PRIVATE durch (in diesem Fall ist dies geeignet, da die Go-Laufzeit in einem Prozess lebt).