Threads, Wettlaufsituationen und Sperren

Ein Thread ist ein Ausführungsstrang innerhalb eines Prozesses. Mehrere Threads können an denselben Programmdaten arbeiten, aber jeder braucht seine eigene Position im Code und seine eigenen noch nicht abgeschlossenen Funktionsaufrufe.

Was gemeinsam genutzt wird und was einem Thread gehört

Threads eines Prozesses teilen sich Code, globale und statische Variablen, Heap-Objekte, offene Dateideskriptoren und die Prozesskennung. Jeder Thread hat seinen eigenen Befehlszähler, seine eigenen Register, seinen eigenen Stack und seine eigene Threadkennung. Ein globales int total bezeichnet ein gemeinsames Objekt. Ein gewöhnliches lokales int i in der Funktion eines Arbeitsthreads bezeichnet bei jedem Aufruf ein anderes Objekt.

Ein Prozess mit drei Threads hat drei Stacks an verschiedenen Adressen im selben Adressraum. Ein Stack ist kein geschützter Bereich: Ein anderer Thread kann eine lokale Variable erreichen, wenn er ihre Adresse erhält. Diese gemeinsame Nutzung ist nur gültig, solange die Variable existiert. Ein Zeiger in den abgeschlossenen Stackframe einer Funktion kann die Variable nicht am Leben erhalten. Große lokale Arrays und tiefe Rekursion können außerdem den Stack eines Threads erschöpfen.

Zwischen Threads wechseln

Das Betriebssystem speichert den Ausführungszustand jedes Threads in einem Threadkontrollblock, kurz TCB. Beim Wechsel von T1 zu T2 speichert es die Register von T1 und stellt die Register von T2 wieder her. Die unvollendete Berechnung von T1 bleibt in seinen gespeicherten Registern, bis er wieder läuft.

Bei Threads desselben Prozesses bleibt der Adressraum während des Wechsels gleich. Die Seitentabellen müssen sich nicht ändern, was diesen Wechsel meist weniger aufwendig macht als einen Wechsel zwischen Prozessen. Gemeinsamer Speicher bedeutet auch gemeinsame Fehlerfolgen: Ein ungültiger Schreibzugriff über einen Zeiger kann die Daten eines anderen Threads beschädigen, und ein Fehler, der den Prozess beendet, beendet jeden Thread.

Warum mehrere Threads nutzen?

Parallelität bedeutet, im selben Moment auf verschiedenen CPU-Kernen ausgeführt zu werden. Vier unabhängige Teile einer Berechnung können auf vier Kernen eine nahezu vierfache Beschleunigung erreichen, wenn gemeinsame Arbeit und Koordination nicht zu Engpässen werden. Threads erlauben einem Programm außerdem, Warten und Arbeit zu überlappen: Während ein Thread auf das Lesen von einer Festplatte oder eine Netzwerkantwort wartet, kann ein anderer die CPU nutzen.

Nebenläufigkeit bedeutet, dass Ausführungen in überlappenden Zeiträumen Fortschritte machen. Auf einem Kern wechselt der Scheduler zwischen Threads, sodass sie nebenläufig sind, ohne parallel zu laufen. Auch auf einem einzelnen Kern sind Nebenläufigkeitsfehler möglich: Ein Wechsel kann eine gemeinsame Aktualisierung zwischen ihren Maschinenbefehlen unterbrechen.

Wer plant die Threads ein?

Linux und Windows nutzen ein Eins-zu-eins-Modell: Jeder gewöhnliche Anwendungsthread entspricht einem vom Kernel eingeplanten Thread. Verschiedene Threads können auf verschiedenen Kernen laufen, und ein blockierender Aufruf blockiert den aufrufenden Thread. Eine Viele-zu-eins-Bibliothek plant mehrere Benutzerthreads auf einem Kernelthread ein. Ihre Wechsel können wenig aufwendig sein, aber sie kann diese Threads nicht auf mehreren Kernen ausführen, und ein blockierender Systemaufruf kann die ganze Gruppe anhalten.

Wird A vor B erzeugt, ist nicht garantiert, dass A zuerst läuft. Gibt A „A“ und B „B“ aus, kann entweder „AB“ oder „BA“ erscheinen. Die Erzeugungsreihenfolge legt fest, wann ein Thread zur Ausführung bereitsteht; der Scheduler wählt den Zeitpunkt seiner Ausführung.

Die Schnittstelle für POSIX-Threads, kurz pthreads, startet eine C-Funktion in einem anderen Thread. Binde <pthread.h> ein und erstelle das Programm mit einem Befehl wie gcc -pthread -o sum sum.c. Die Option -pthread liefert die Compiler- und Linkereinstellungen für Code mit Threads.

Einen Thread mit stabilen Argumenten erzeugen

Der Aufruf pthread_create(&t, NULL, worker, arg) speichert eine Threadkennung in t und startet worker(arg). Der Attributzeiger NULL fordert die Standardwerte an. Ein Arbeitsthread hat die Signatur void *worker(void *arg): Argument und Rückgabewert sind Zeiger. Mit einem Struct kann dieser eine Zeiger mehrere Felder übermitteln.

#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>

struct range { int lo, hi; long result; };

void *sum_range(void *arg) {
    struct range *r = arg;
    long sum = 0;
    for (int n = r->lo; n <= r->hi; n++)
        sum += n;
    r->result = sum;
    return NULL;
}

Der erzeugende Thread bereitet zwei Structs vor, {1, 50, 0} und {51, 100, 0}, und übergibt jedem Arbeitsthread eine andere Adresse. Halte beide Structs am Leben, bis die Arbeitsthreads fertig sind. Jeder Arbeitsthread summiert in seinem eigenen lokalen sum und schreibt nur sein eigenes Feld result.

pthread_create gibt bei Erfolg 0 und bei einem Fehler eine Fehlernummer zurück. Prüfe diese zurückgegebene Nummer direkt; der Aufruf setzt zur Fehlermeldung nicht errno. Nur eine erfolgreiche Erzeugung liefert einen Thread, auf den mit Join gewartet werden kann.

Vor dem Lesen der Ergebnisse mit Join warten

Nachdem beide Arbeitsthreads erfolgreich erzeugt wurden, ruft der Hauptthread pthread_join(t[0], NULL) und pthread_join(t[1], NULL) auf. Ein Join blockiert, bis der Zielthread endet. Ein erfolgreicher Join macht außerdem die Schreibzugriffe dieses Arbeitsthreads für den wartenden Thread sichtbar. Der Hauptthread kann dann 1.275 und 3.775 lesen und ohne Mutex zu 5.050 addieren: Die Arbeitsthreads haben getrennte Objekte beschrieben, und der Hauptthread hat vor dem Lesen gewartet.

Werden beide Threads vor dem Join gestartet, kann ihre Arbeit überlappen. Wird ein Arbeitsthread erzeugt und sofort mit Join auf ihn gewartet, bevor der nächste erzeugt wird, laufen die Arbeitsthreads nacheinander.

Hier ist das Hauptprogramm. Es beendet sich bei einem pthread-Fehler und verwendet daher nie eine Kennung aus einer fehlgeschlagenen Erzeugung:

static void require_success(int rc) {
    if (rc != 0) {
        fprintf(stderr, "pthread error: %d\n", rc);
        exit(EXIT_FAILURE);
    }
}

int main(void) {
    struct range jobs[2] = {{1, 50, 0}, {51, 100, 0}};
    pthread_t threads[2];
    for (int i = 0; i < 2; i++)
        require_success(pthread_create(&threads[i], NULL,
                                      sum_range, &jobs[i]));
    for (int i = 0; i < 2; i++)
        require_success(pthread_join(threads[i], NULL));
    printf("%ld\n", jobs[0].result + jobs[1].result);
    return 0;
}

Um einen zurückgegebenen Zeiger einzusammeln, übergib die Adresse, an der er abgelegt werden soll: void *answer; pthread_join(t, &answer);. Der Zeiger muss auf Speicher verweisen, der länger als der Arbeitsthread existiert, etwa zugewiesenen Heap-Speicher oder ein Struct des erzeugenden Threads. Die Rückgabe von &local_result durch den Arbeitsthread ist ungültig, weil seine lokale Variable mit der Rückkehr der Funktion endet.

Eine veränderliche Schleifenvariable nicht gemeinsam nutzen

Wird in einer Erzeugungsschleife jedem Arbeitsthread &i übergeben, wird wiederholt dieselbe Adresse übergeben. Arbeitsthreads können sie lesen, nachdem die Schleife den Wert geändert hat, sodass mehrere scheinbar dieselbe Kennung erhalten. Nutze stattdessen ein Array: Weise ids[i] = i zu, übergib &ids[i] und halte das Array am Leben und unverändert, bis alle Join-Aufrufe abgeschlossen sind.

Threads und Prozesse bewusst beenden

Die Rückkehr aus main oder der Aufruf von exit() in einem beliebigen Thread beendet den ganzen Prozess und kann Arbeitsthreads abbrechen. Der Hauptthread wartet normalerweise vor seiner Rückkehr mit Join auf sie. Ein Aufruf von pthread_exit() beendet nur den aufrufenden Thread; andere Threads können weiterlaufen.

Ein abgekoppelter Thread gibt seine Threadressourcen beim Ende automatisch frei und kann nicht mit Join abgewartet werden. Sorge dafür, dass jeder Thread, auf den mit Join gewartet werden kann, einmal abgewartet oder abgekoppelt wird. Join wartet auf den Abschluss; es schützt keine zwei Arbeitsthreads, die dasselbe Objekt aktualisieren, während beide laufen.

Die Anweisung counter++ sieht kurz aus, aber das gewöhnliche Erhöhen einer gemeinsam genutzten Ganzzahl ist keine unteilbare Operation. Üblicherweise wird ein Wert geladen, in einem Register addiert und das Ergebnis gespeichert. Zwischen diesen Schritten kann ein anderer Thread laufen.

Ein Ablauf, bei dem eine Erhöhung verloren geht

Beginne mit counter gleich 50. Betrachte Laden, Addieren und Speichern als getrennte Maschinenschritte:

Zwei Erhöhungen hätten 52 ergeben müssen. Stattdessen überschreibt T1 das Ergebnis von T2 mit einem aus dem älteren Wert 50 berechneten Wert. Das ist ein verlorenes Update.

Ein Kontextwechsel sichert die Register von T1 in seinem TCB. Wenn T1 fortgesetzt wird, enthält sein Register noch 51; der gemeinsame Zähler wird nicht allein deshalb neu geladen, weil T2 gelaufen ist. Der Fehler liegt in der ungeschützten Folge, nicht darin, dass der Scheduler ein falsches Register wiederherstellt.

Mit einer seriellen Ausführung vergleichen

Schließt T1 alle drei Schritte ab, bevor T2 lädt, speichert T1 51 und T2 danach 52. Auch die umgekehrte Reihenfolge der gesamten Threads ergibt 52. Das Ergebnis 51 der verzahnten Ausführung kann in keiner der beiden seriellen Reihenfolgen entstehen. Um diese Art von Fehler zu finden, markiere einen Lesezugriff, platziere danach einen Schreibzugriff eines anderen Threads und setze die Berechnung des ersten Threads mit dem veralteten Wert fort.

Dieser Ablauf ist ein Modell des Fehlers auf Maschinenebene. In tatsächlichem C bilden nicht synchronisierte, miteinander in Konflikt stehende Zugriffe auf eine gewöhnliche gemeinsame Ganzzahl einen Datenwettlauf, der undefiniertes Verhalten zur Folge hat. C beschränkt dieses Programm nicht auf die Ergebnisse eines einfachen Modells verzahnter Befehle.

Warum bestandene Tests ein schwacher Beleg sind

Zwei Threads, die jeweils 10.000.000 Erhöhungen ausführen, sollten 20.000.000 ergeben. Ungeschützte Versuchsläufe können unterschiedliche kleinere Summen ausgeben, etwa 19.345.221 und 19.221.041 in veröffentlichten Beispielen. Ein gut aussehender Lauf bedeutet nur, dass sein beobachtetes Ergebnis zufällig akzeptabel war.

Das anfällige Zeitfenster kann nur wenige Befehle breit sein. Andere Kernzahlen, Compilerentscheidungen oder Systemlasten können einen Ablauf aufdecken, der bei Tausenden früheren Läufen ausblieb. Führen zwei Threads im Modell jeweils eine Erhöhung ab null aus, erlaubt das Ablaufmodell 1 oder 2. Bei mindestens zwei Erhöhungen pro Thread können seltene Abläufe selbst bei steigender Anzahl beabsichtigter Erhöhungen eine Summe von nur 2 hinterlassen.

Die Operation korrigieren, nicht ihr Erscheinungsbild

Die Deklaration der Ganzzahl als volatile macht Laden, Addieren und Speichern nicht unteilbar und synchronisiert keine Threads. Alle Arbeit in eine Zeile zu schreiben, ändert nichts. Selbst ein x86-Befehl, der direkt zum Speicher addiert, braucht die passende atomare Form, um sich über Kerne hinweg abzustimmen.

Schütze das vollständige Read-Modify-Write mit einem gemeinsamen Mutex oder nutze eine atomare C11-Read-Modify-Write-Operation wie atomic_fetch_add. Dasselbe ist auf einem Kern nötig: Ein timerbedingter Wechsel kann Laden und Speichern auch ohne parallele Ausführung trennen.

Ein Nebenläufigkeitsfehler kann einen einzelnen Speicherzugriff oder eine ganze Geschäftsregel betreffen. Bestimme sowohl die gemeinsamen Objekte als auch die Operation, die anderen Threads unteilbar erscheinen muss.

Wettlaufsituation oder Datenwettlauf?

Eine Wettlaufsituation entsteht, wenn die Korrektheit vom relativen zeitlichen Ablauf abhängt. Ein Datenwettlauf entsteht, wenn verschiedene Threads ohne Synchronisierung auf dieselbe Speicherstelle zugreifen, mindestens einer sie schreibt und mindestens ein Zugriff nicht atomar ist. In C11 und C++11 hat ein Datenwettlauf undefiniertes Verhalten zur Folge.

Atomare Zugriffe können einen Datenwettlauf vermeiden, während eine größere Operation weiterhin eine Wettlaufsituation enthält. Einzeln geschützte Lese- und Schreibzugriffe halten beispielsweise eine Entscheidung zwischen diesen Zugriffen nicht gültig. Zwei Threads können jeweils einen ausreichenden Kontostand lesen, die Sperre freigeben und später aufgrund dieser veralteten Entscheidung Geld abheben.

Eine Abhebung durchgehen

Ein Kontostand beginnt bei 100. Zwei Threads fordern jeweils 80 an. Die Regel lautet, eine Abhebung nur zu akzeptieren, wenn der Kontostand sie deckt.

1. T1 prüft 100 und entscheidet, dass seine Abhebung möglich ist.
2. T2 prüft ebenfalls 100 und trifft dieselbe Entscheidung.
3. T1 zieht 80 ab, sodass 20 bleiben.
4. T2 handelt aufgrund seiner früheren Entscheidung und zieht 80 von 20 ab, sodass −60 bleiben.

Nur die Subtraktion zu schützen, behebt diesen Ablauf nicht. Schütze die Prüfung und die Subtraktion mit derselben Sperre, die durchgehend gehalten wird. Dann hinterlässt ein Thread 20 und der nächste prüft 20 und lehnt ab. In einem anderen ungeschützten Ablauf kann eine Subtraktion verloren gehen und nach Auszahlung beider Abhebungen 20 übrig bleiben, was ebenfalls falsch ist.

Den kritischen Abschnitt finden

Ein kritischer Abschnitt ist der Bereich für gemeinsame Daten, der konkurrierende Zugriffe ausschließen muss. Eine Read-Modify-Write-Folge liest zunächst Daten, berechnet einen neuen Wert und schreibt ihn zurück. Eine Folge aus Prüfen und anschließendem Handeln entscheidet, ob eine Handlung erlaubt ist, und führt sie dann aus. Auch Listenoperationen, verzögerte Initialisierung und Dateierzeugung können diese Muster enthalten.

Eine Sperre bietet wechselseitigen Ausschluss: Höchstens ein beteiligter Thread befindet sich gleichzeitig im geschützten Bereich. Eine atomare Operation erscheint anderen beteiligten Threads als eine vollständige Operation; sie können keinen halbfertigen Zustand beobachten. Ein Mutex bietet diese Sicht nur für Code, der derselben Sperrvereinbarung folgt.

Nicht jedes Objekt braucht eine Sperre. Daten, auf die ein Thread zugreift, bleiben privat, solange ihre Adresse nicht weitergegeben wird. Daten, die vor dem Start der Arbeitsthreads vollständig initialisiert und danach nur gelesen werden, können ohne Sperre gemeinsam genutzt werden. Beurteile, wer ein Objekt erreichen kann und ob Schreibzugriffe seine Nutzung überlappen, nicht nur, wo es deklariert wurde.

Was eine korrekte Lösung garantiert

• Wechselseitiger Ausschluss: Konkurrierende Threads können nicht gemeinsam eintreten.
• Fortschritt: Ist der Abschnitt frei und wollen Threads eintreten, können Threads, die nicht eintreten wollen, die Auswahl eines eintretenden Threads nicht unbegrenzt verzögern.
• Beschränktes Warten: Nach einer Anfrage ist begrenzt, wie viele konkurrierende Eintritte ihr vorausgehen können.

C11-atomic_fetch_add(&count, 1) führt eine atomare Aktualisierung auf einem atomic_int aus. Atomarität ist selbst auf einer Plattform garantiert, die die Operation mit einer internen Bibliothekssperre implementiert. Werden zwei Kontofelder einzeln atomar gemacht, wird eine Überweisung zwischen ihnen dadurch noch nicht zu einer atomaren Transaktion; auch die Beziehung zwischen den Feldern braucht Schutz.

Ein Mutex ist eine Sperre, durch die jeweils ein Thread einen geschützten Bereich besitzen kann. Ein Thread erwirbt sie vor dem Zugriff auf geschützte Daten und gibt sie danach frei. Hält ein anderer Thread sie bereits, wartet ein blockierender Sperraufruf.

Den gemeinsamen Mutex initialisieren

Verwende pthread_mutex_t aus <pthread.h>. Ein statischer Mutex kann mit pthread_mutex_t m = PTHREAD_MUTEX_INITIALIZER; beginnen. Ein dynamisch erzeugtes Objekt kann sein Feld mit pthread_mutex_init(&obj->lock, NULL) initialisieren. Die Initialisierung muss abgeschlossen sein, bevor ein Thread den Mutex verwendet.

Hier ist eine Zähleroperation mit einem statisch initialisierten gemeinsamen Mutex. Die Hilfsfunktion prüft pthread-Rückgabewerte, die direkt Fehlernummern sind:

#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>

static pthread_mutex_t m = PTHREAD_MUTEX_INITIALIZER;
static long counter = 0;  // guarded by m

static void check(int rc) {
    if (rc != 0) {
        fprintf(stderr, "pthread error: %d\n", rc);
        exit(EXIT_FAILURE);
    }
}

void increment(void) {
    check(pthread_mutex_lock(&m));
    counter = counter + 1;
    check(pthread_mutex_unlock(&m));
}

Jeder nebenläufige Lesezugriff und jede Aktualisierung von counter muss derselben Regel folgen. Eine separate Funktion mit einem anderen Mutex würde sich nicht mit increment abstimmen.

Was geschieht, während der Mutex gehalten wird?

T1 sperrt m, lädt den Zähler, rechnet und speichert. Ruft T2 währenddessen pthread_mutex_lock(&m) auf, kann er den Aufruf erst passieren, wenn er nach der Freigabe durch T1 den Mutex erworben hat. T1 kann weiterhin verdrängt werden: Ein Mutex verhindert konkurrierenden Eintritt, keine Kontextwechsel.

Halte für die Kontostandsregel den Mutex bereits vor der Auswertung von balance >= amount. Ziehe den Betrag nur bei bestandener Prüfung ab, halte Erfolg oder Misserfolg fest und gib dann die Sperre frei. Ein Kontostand von 100 und zwei Anfragen über 80 erlauben genau einen Erfolg und hinterlassen 20.

Wählen, wie gewartet wird

pthread_mutex_trylock(&m) kehrt sofort zurück: 0 bedeutet, dass der aufrufende Thread den Mutex erworben hat; EBUSY bedeutet, dass er ihn nicht erworben hat, weil der Mutex gehalten wurde. Auf dem Pfad bei belegtem Mutex kann der Thread andere Arbeit erledigen und darf nicht auf die geschützten Daten zugreifen. pthread_mutex_timedlock wartet bis zu einem absoluten Zeitpunkt. Auch bei diesen Schnittstellen müssen Rückgabecodes geprüft und darf eine Sperre nur nach erfolgreichem Erwerb freigegeben werden.

Besitz und Lebensdauer beachten

Der besitzende Thread gibt einen Mutex frei. Ein normaler nicht rekursiver Mutex blockiert, wenn sein Besitzer versucht, ihn erneut zu sperren. Ein fehlerprüfender Mutex meldet Fehler wie erneutes Sperren mit EDEADLK oder Freigabe durch einen anderen Thread mit EPERM. Ein rekursiver Mutex zählt wiederholte Erwerbungen durch seinen Besitzer und verlangt dieselbe Anzahl von Freigaben. Verlass dich nicht darauf, dass ein Standardmutex Fehlbedienung meldet: Sein Verhalten hängt vom zugeordneten Implementierungstyp und der Operation ab.

Wenn alle Threads den Mutex nicht mehr verwenden und er freigegeben ist, rufe pthread_mutex_destroy auf. Wird ein Objekt zerstört oder sein Speicher freigegeben, während ein anderer Thread es noch sperren kann, wird die Lebensdauer des Mutex verletzt. Die Übergabe des Mutex per Zeiger erhält seine Identität; durch Kopieren entsteht kein weiteres gültiges Handle für dieselbe Sperre.

Sperrgranularität bezeichnet den Umfang des gemeinsamen Zustands, den eine Sperre abdeckt. Sie bestimmt, welche Operationen aufeinander warten müssen, selbst wenn sie auf verschiedenen Kernen laufen.

Eine große Sperre oder mehrere kleinere?

Ein grobgranularer Entwurf schützt eine ganze Struktur oder ein Subsystem mit einem Mutex. Er hat eine einfache Schutzregel, aber auch voneinander unabhängige Operationen werden serialisiert. Ein feingranularer Entwurf weist einzelnen Konten, Buckets oder Bereichen getrennte Mutexe zu. Threads können dann gleichzeitig in verschiedenen Bereichen arbeiten, müssen dafür aber mehr Sperroperationen und kompliziertere Regeln berücksichtigen.

Lege die Sperre neben dem Zustand ab, den sie schützt:

struct account {
    pthread_mutex_t lock;
    long balance;
    unsigned id;
};

Eine Operation auf einem Konto erwirbt dessen Mutex. Eine Überweisung zwischen zwei verschiedenen Konten braucht beide, weil sie die Beziehung zwischen ihnen ändert. Wähle eine feste Reihenfolge, etwa aufsteigend nach Kontokennung, und verwende sie auf jedem Pfad. Andernfalls kann ein Thread A halten und auf B warten, während ein anderer B hält und auf A wartet.

Eine Sperre begrenzt den Durchsatz

Angenommen, jede Operation hält eine einzige globale Sperre für 2 µs. Von der geschützten Arbeit kann höchstens eine Operation pro 2 µs abgeschlossen werden:

Zusätzliche Kerne ermöglichen es nicht, dass zwei Operationen denselben Mutex gleichzeitig halten. Sperraufwand und andere Arbeit können die erreichte Rate weiter senken. Die geschützte Dauer liefert daher eine nützliche Schranke, die du berechnen kannst, bevor du eine Beschleunigung erwartest.

Den Abschnitt verkürzen, ohne die Operation zu zerstören

Bereite private Arbeit vor, bevor du den Mutex erwirbst. Weise beim Einfügen in eine Liste zuerst Speicher für den neuen Knoten zu und trage seinen Schlüssel ein. Erwirb den Listenmutex erst, wenn du den aktuellen Listenanfang liest und den Knoten einhängst. Schlägt die Speicherzuweisung fehl, wird keine Sperre gehalten.

Langsame Ein-/Ausgabe, Ausgaben oder ein unbekannter Callback können alle Wartenden aufhalten. Verlege solche Arbeit nach draußen, wenn die Daten dort gültig bleiben können. Halte eine Entscheidung und die davon abhängige Aktualisierung zusammen: Gibst du bei einer Abhebung zwischen der Prüfung des Kontostands und der Subtraktion die Sperre frei, ist das Ergebnis nicht mehr zuverlässig korrekt.

Drei verschiedene Eigenschaften bewerten

Beim wechselseitigen Ausschluss geht es darum, ob der Entwurf konkurrierenden Eintritt tatsächlich verhindert. Bei der Fairness geht es darum, ob ein wartender Thread irgendwann an die Reihe kommt oder verhungern kann. Bei der Leistung geht es um die Kosten der Sperre mit einem Thread, mehreren Threads auf einer CPU und Threads auf mehreren CPUs. Eine Sperre kann korrekt und trotzdem unfair oder langsam sein.

Ressourcenkonkurrenz entsteht, wenn Threads um eine bereits gehaltene Sperre konkurrieren. Bei starker Konkurrenz verschieben sie außerdem Cachezeilen der gemeinsamen Sperre und Daten zwischen Kernen. Ein veröffentlichtes Zählerexperiment benötigte etwa 0,03 s für eine Million Aktualisierungen durch einen Thread, aber über 5 s für zwei Threads mit je einer Million. Das sind Messwerte dieses Aufbaus, keine allgemein gültigen Zeiten.

Halte bei einem Skalierungsexperiment die Arbeit pro Thread konstant. Bei idealer Skalierung erledigen N Threads auf N Kernen das N-Fache der Arbeit in der ursprünglichen Zeit. Beginne mit einer einfachen korrekten Struktur, miss Warte- und Gesamtzeit und teile eine Sperre nur dort auf, wo die zusätzliche Nebenläufigkeit ihren Mehraufwand aufwiegt.

Ein Mutex kann vollkommen korrekt implementiert sein und trotzdem von einem Programm falsch verwendet werden. Prüfe den gesamten Ablauf einer Funktion einschließlich Lesezugriffen, Fehlern, Callbacks und der Zerstörung von Objekten.

Die Sperre bei jedem Verlassen freigeben

Diese Funktion gibt die Sperre auf ihrem Fehlerpfad nicht frei:

pthread_mutex_lock(&m);
if (failed) return -1;
update_shared_state();
pthread_mutex_unlock(&m);

Der zurückkehrende Thread kann enden, aber der Mutex bleibt gesperrt. Ein späterer Aufrufer wartet dann auf eine Freigabe, die nie erfolgt. Nutze einen gemeinsamen Aufräumpfad oder gib die Sperre vor jeder Rückkehr frei. Mit geprüften pthread-Aufrufen kann der Aufbau so aussehen:

int rc = -1;
check(pthread_mutex_lock(&m));
if (!failed) {
    update_shared_state();
    rc = 0;
}
check(pthread_mutex_unlock(&m));
return rc;

Ein einzelner Freigabepunkt ist leichter zu prüfen als viele verstreute. Entscheidend ist, dass jede erfolgreich erworbene Sperre bei jedem regulären Verlassen freigegeben wird.

Die Schutzregel auch beim Lesen befolgen

Eine Statusfunktion, die „nur liest“, kann mit einer aktualisierenden Funktion in einen Wettlauf geraten. Sie kann außerdem zusammengehörige Felder in verschiedenen Stadien einer Aktualisierung beobachten. Veröffentlicht eine Listenoperation einen Knoten, bevor seine Felder vollständig sind, kann ein ungeschützter Leser einem Zeiger zu unfertigen Daten folgen. Erwirb die dokumentierte Sperre für jeden Zugriff, dessen Korrektheit davon abhängt.

Verschiedene Mutexe für dasselbe Objekt zu verwenden, hilft nicht. Erwirbt T1 lockA und T2 lockB, können beide Erwerbungen gelingen. Ein in jedem Arbeitsthread neu lokal deklarierter Mutex macht diesen Fehler leicht übersehbar: Jeder Thread sperrt sein eigenes Objekt, sodass kein gemeinsamer Ausschluss besteht.

Identität und Operationsgrenzen erhalten

Ein pthread_mutex_t darf nicht durch Zuweisung oder durch Kopieren seines Structs kopiert und anschließend als zweites Mutex-Handle verwendet werden. Die Verwendung der Kopie ist undefiniertes Verhalten. Übergib einen Zeiger auf den ursprünglichen gemeinsamen Mutex.

Prüfe auch, wo Freigaben erfolgen. Eine Funktion, die zur Prüfung eines Kontostands sperrt, freigibt und später für die Subtraktion erneut sperrt, hat einzelne Zugriffe geschützt, aber die Entscheidung kann veralten. Halte die Sperre während der gesamten Folge aus Prüfung und anschließendem Handeln durchgehend.

Vermeiden, auf sich selbst zu warten

Ein Aufruf unbekannten Codes bei gehaltenem Mutex kann unerwartet erneut auf dasselbe geschützte Objekt zugreifen. Bei einem normalen Mutex blockiert ein zweiter Sperraufruf durch den Besitzer diesen selbst. Ein fehlerprüfender Mutex meldet diesen Fehler, während ein rekursiver Mutex verschachtelten Besitz erlaubt und entsprechende Freigaben verlangt. Wähle einen Typ bewusst; nutze Rekursion nicht, um einen unklaren Schutzentwurf zu verbergen.

Halte langsame Ein-/Ausgabe und Schlafphasen nach Möglichkeit aus einem gemeinsamen kritischen Abschnitt heraus. Stelle vor dem Zerstören des Mutex oder dem Freigeben seines Objekts sicher, dass kein Thread ihn besitzt oder erneut darauf zugreifen kann. Initialisierung, Nutzung und Zerstörung müssen eine klare Reihenfolge haben.

Laufzeitwerkzeuge zum Aufdecken beobachteter Fehler nutzen

ThreadSanitizer, aktiviert mit -fsanitize=thread, und Valgrinds Helgrind können Datenwettläufe und fehlerhafte Sperrnutzung in beobachteten Ausführungen melden. Verbinde ihre Meldungen mit einer Prüfung gemeinsamer Zugriffe und möglicher Verzahnungen. Ein fehlerfreier Lauf zeigt, dass das Werkzeug in diesen Ausführungen kein Problem gefunden hat; ein ungetesteter Pfad muss weiterhin analysiert werden.

Eine Sperre braucht eine zuverlässige Möglichkeit, einen Besitzer auszuwählen. Auf einen gewöhnlichen Lesezugriff gefolgt von einem gewöhnlichen Schreibzugriff entsteht eine Lücke in dieser Entscheidung, selbst wenn die geschützte Arbeit sehr kurz ist.

Die Kontrolle von Interrupts hat eine begrenzte Rolle

Auf einer CPU kann ein Kernel Interrupts um einen nicht blockierenden kritischen Abschnitt herum kurz abschalten, um dort eine durch Interrupts ausgelöste Verdrängung zu verhindern. Das setzt voraus, dass der Kernel auf der CPU bleibt, ohne freiwillig zu blockieren oder zu wechseln. Der Kernel nutzt diese Technik für kurze interne Operationen.

Sie ist kein allgemeiner Anwendungsmutex. Befehle zur Interruptsteuerung sind privilegiert; dürfte eine Anwendung sie uneingeschränkt nutzen, könnte sie die CPU monopolisieren. Das Abschalten von Interrupts auf einem Kern hindert andere Kerne nicht daran, auf dieselben Daten zuzugreifen. Lange Abschaltzeiten verzögern außerdem die Interruptbehandlung und können bei manchen Geräten zum Verlust von Ereignissen führen.

Den fehlerhaften Ablauf der Flagsperre verfolgen

Betrachte diesen C-ähnlichen Pseudocode:

while (flag == 1) { }
flag = 1;
// critical section
flag = 0;

Beginne mit flag bei 0. T1 prüft das Flag und verlässt die Schleife, pausiert dann aber vor der Zuweisung. T2 prüft dieselbe 0, setzt das Flag auf 1 und tritt ein. T1 wird fortgesetzt, setzt es auf 1 und tritt ebenfalls ein. Beide haben die Prüfung bestanden, bevor einer den Besitz beansprucht hat.

Würden Lesen und Schreiben einzeln atomar gemacht, entfiele ein Datenwettlauf auf dem Flag, aber in diesem Protokoll blieben es zwei getrennte Operationen. Die Besitzübernahme braucht ein atomares Read-Modify-Write oder einen umfassenderen Synchronisationsalgorithmus.

Die leere Schleife ist aktives Warten: wiederholtes Prüfen unter Verbrauch von CPU-Zeit. Auf einer CPU kann ein Wartender, der nach der Verdrängung des Besitzers aktiv wartet, nicht dafür sorgen, dass dieser die Sperre früher freigibt. Er muss den Besitzer schließlich laufen lassen.

Petersons Lösung für zwei Threads

Der Peterson-Algorithmus koordiniert zwei Threads mit einem Interessenflag pro Thread und einem gemeinsamen Bedienungszähler. Thread i führt aus:

flag[i] = 1;
turn = 1 - i;
while (flag[1 - i] == 1 && turn == 1 - i) { }
// critical section
flag[i] = 0;

Er meldet sein Interesse an, gibt bei Gleichstand dem anderen Thread Vorrang und wartet nur, solange der andere interessiert ist und Vorrang hat. Unter sequenzieller Konsistenz behalten die Operationen jedes Threads ihre Programmreihenfolge, und alle Threads beobachten eine gemeinsame Reihenfolge. In diesem Modell bietet der Peterson-Algorithmus wechselseitigen Ausschluss, Fortschritt und beschränktes Warten für zwei Threads.

Auch die Speicherordnung ist wichtig

Moderne Prozessoren und Compiler können Speicheroperationen in einer anderen Reihenfolge sichtbar machen, als sie im Quellcode stehen. Ein Schreibzugriff kann gepuffert bleiben, während ein späterer Lesezugriff den Speicher liest. Beide Threads können dann das Interessenflag des anderen als 0 sehen und beide eintreten. Gewöhnliche gemeinsame C-Ganzzahlen führen außerdem zu Datenwettläufen in C.

Eine gültige Implementierung braucht geeignete atomare Operationen und eine passende Reihenfolge, etwa sequenziell konsistente atomare C11-Operationen für die Flags und den Bedienungszähler. volatile bietet diese Synchronisierung nicht. Praktische Sperren verbinden eine unteilbare Besitzoperation mit Garantien zur Speicherordnung, sodass geschützte Zugriffe auf der richtigen Seite von Erwerb und Freigabe bleiben.

Ein atomares Read-Modify-Write verbindet das Lesen und Aktualisieren einer Speicherstelle zu einer unteilbaren Handlung. Es schließt die Lücke, durch die zwei Threads eine gewöhnliche Flagprüfung gemeinsam bestehen können.

Das Flag austauschen und seinen alten Wert prüfen

Test-and-Set, auch atomarer Austausch, schreibt einen neuen Wert und gibt den alten zurück. Bei einem anfänglich auf 0 gesetzten Flag tauscht T1 eine 1 ein und erhält 0 zurück, sodass er eintritt. T2 tauscht eine 1 ein und erhält 1 zurück, sodass er wartet. Bis die Freigabe 0 schreibt, kann kein weiterer Austausch 0 zurückgeben.

Hier ist ein C11-Spinlock mit den standardmäßig sequenziell konsistenten atomaren Operationen:

#include <stdatomic.h>

static atomic_flag held = ATOMIC_FLAG_INIT;

void lock(void) {
    while (atomic_flag_test_and_set(&held)) { }
}

void unlock(void) {
    atomic_flag_clear(&held);
}

Neben dem Flag ist auch die Reihenfolge wichtig. Der Erwerb muss dafür sorgen, dass nachfolgende Zugriffe des kritischen Abschnitts nach dem erfolgreichen Erwerb bleiben; die Freigabe muss dafür sorgen, dass frühere Zugriffe des kritischen Abschnitts vor der Freigabe bleiben. Auch das Zurücksetzen des Flags muss atomar sein; eine Mischung gewöhnlicher Schreibzugriffe mit atomaren Zugriffen implementiert diese Übergabe nicht.

Vor dem Ersetzen vergleichen

Compare-and-Swap, kurz CAS, ändert einen Wert nur, wenn er einem erwarteten Wert entspricht. Angenommen, zwei Threads lesen einen Zähler mit dem Wert 7 und wollen jeweils 1 addieren. T2 ändert 7 erfolgreich in 8. Der Versuch von T1, 7 in 8 zu ändern, scheitert nun, sodass T1 es ausgehend von 8 erneut versucht und den Wert in 9 ändert. Durch die Wiederholung bleiben beide Erhöhungen erhalten.

C11-atomic_compare_exchange_strong gibt Erfolg oder Misserfolg zurück und aktualisiert bei Misserfolg das Argument mit dem erwarteten Wert. Hardwareähnlicher Pseudocode gibt dagegen manchmal den alten gespeicherten Wert zurück. Prüfe, welche Konvention ein Ablauf verwendet. Auf x86 implementiert xchg mit Speicheroperand den Austausch, während lock cmpxchg atomaren Vergleich und Austausch bietet.

Weitere Hardwarebausteine

Load-Linked/Store-Conditional, kurz LL/SC, liest unter Aufbau einer Reservierung und versucht dann einen Schreibzugriff. Der bedingte Schreibzugriff scheitert, wenn ein anderer Schreibzugriff die Reservierung ungültig gemacht hat; er kann auch aus anderen Gründen scheitern und gehört daher in eine Wiederholungsschleife. LDXR/STXR von ARM und lr/sc von RISC-V unterstützen dieses Muster.

Fetch-and-Add addiert atomar und gibt den alten Wert zurück. C11 stellt es als atomic_fetch_add bereit; x86 bietet lock xadd. Die Rückgabe des alten Werts macht es nützlich, um eindeutige Ticketnummern zu vergeben.

C garantiert das atomare Verhalten seiner atomaren Bibliotheksoperationen. Es verlangt nicht, dass jeder atomare Typ sperrfrei ist; manche Operationen nutzen eine interne Bibliothekssperre. Für atomic_flag ist Sperrfreiheit garantiert, und atomic_is_lock_free prüft andere Objekte.

Korrekt bedeutet nicht fair oder schnell

Eine Test-and-Set-Sperre bietet wechselseitigen Ausschluss, aber keine Ankunftsreihenfolge: Ein Thread kann den Wettlauf nach einer Freigabe wiederholt verlieren und verhungern. Auf einer CPU können bei vier Threads mit 10 ms langen Round-Robin-Zeitscheiben drei Wartende 30 ms mit aktivem Warten verschwenden, bevor der verdrängte Besitzer wieder läuft. Auf mehreren Kernen kann bei laufendem Besitzer und kurzen Abschnitten ein kurzes aktives Warten den Aufwand für Blockieren und Aufwecken vermeiden.

Eine Test-and-Set-Sperre merkt sich, ob sie gehalten wird, aber nicht, wer gewartet hat. Eine Ticketsperre ergänzt eine Ankunftsreihenfolge durch einen atomaren Ticketgeber und einen Bedienungszähler.

Eine Nummer ziehen und darauf warten

Beide Zähler beginnen bei 0. Jeder aufrufende Thread erhöht ticket atomar und behält dessen alten Wert als mine. Er tritt erst ein, wenn turn gleich mine ist. Der Besitzer gibt die Sperre frei, indem er turn einmal erhöht.

#include <stdatomic.h>

static atomic_uint ticket = 0;
static atomic_uint turn = 0;

void lock(void) {
    unsigned mine = atomic_fetch_add(&ticket, 1);
    while (atomic_load(&turn) != mine) { }
}

void unlock(void) {
    atomic_fetch_add(&turn, 1);
}

Diese standardmäßigen atomaren C11-Operationen bieten sowohl Atomarität als auch sequenziell konsistente Ordnung. Jeder aufrufende Thread hält mine in seiner eigenen lokalen Variablen. Der gemeinsame Ticketzähler vergibt eindeutige ausstehende Nummern.

Drei Ankünfte verfolgen

A zieht Ticket 0 und tritt ein, weil turn 0 ist. B zieht Ticket 1 und wartet. C zieht Ticket 2 und wartet. Das nächste ungenutzte Ticket ist nun 3, während der aktuelle Bedienungszähler noch 0 ist.

Wenn A freigibt, wird turn 1, sodass B eintritt. C wartet weiterhin auf 2. Die Freigabe von B erhöht turn auf 2 und C tritt ein. Ein neu ankommender Thread erhält Ticket 3 und kann C nicht überholen.

Diese Unterscheidung ist bei der Ablaufverfolgung wichtig: ticket hält die nächste zu vergebende Nummer fest; turn hält die Nummer fest, die gerade bedient wird. Das Ziehen eines Tickets ändert nur den Ticketgeber. Die Freigabe schaltet die Bedienung weiter.

Was Fairness garantiert

Ein aufrufender Thread wartet hinter den Threads mit früheren Tickets. Wenn jeder Besitzer die Sperre irgendwann freigibt und die Threads davor laufen können, können später Ankommende ihn nicht überholen. Die Anzahl der konkurrierenden kritischen Abschnitte vor ihm ist durch die früheren ausstehenden Tickets begrenzt. Unter diesen Fortschrittsbedingungen bietet das beschränktes Warten und verhindert Verhungern.

Die Garantie betrifft die Eintrittsreihenfolge, nicht die verstrichene Zeit. Ein Besitzer, der lange aufgehalten wird, kann auch alle späteren Aufrufer lange warten lassen. Eine Ticketnummer kann den Scheduler nicht zwingen, ihren Besitzer auszuführen.

Welche Kosten die Ticketreihenfolge nicht beseitigt

Jeder Wartende wartet weiterhin aktiv. Wird der Thread, der als Nächster an der Reihe ist, nicht eingeplant, warten später angekommene lauffähige Threads, obwohl sich gerade kein Thread im kritischen Abschnitt befindet. Das sind Schedulingkosten der strengen Reihenfolge.

Wartende lesen außerdem eine gemeinsame Speicherstelle turn. Jede Freigabe ändert die Cachezeile, die alle beobachten, und erzeugt Verkehr zwischen den Kernen. Warteschlangenbasierte Spinlocks verringern diesen Verkehr, indem jeder Wartende eine eigene lokale Speicherstelle beobachtet; Linux wechselte von Ticket-Spinlocks zu warteschlangenbasierten Entwürfen.

Tatsächliche Ticketzähler verwenden vorzeichenlose Arithmetik. Gleichheitsprüfungen können über einen Überlauf hinweg funktionieren, wenn die Anzahl ausstehender Tickets kleiner als der Wertebereich des Zählers bleibt. Würde eine Nummer erneut vergeben, während ein früheres Ticket mit derselben Nummer noch aussteht, wären Eindeutigkeit und Ausschluss nicht mehr gewährleistet.

Eine korrekte Sperre kann den größten Teil einer CPU mit Warten verschwenden. Die richtige Wartestrategie hängt davon ab, ob der Besitzer laufen kann und wie lange er die Sperre halten wird.

Freiwillige Prozessorabgabe gibt einen Zug ab

Ein wartender Thread kann nach einem fehlgeschlagenen Erwerbsversuch yield() aufrufen. Die freiwillige Abgabe versetzt ihn vom Zustand „laufend“ in den Zustand „bereit“, sodass der Scheduler einen anderen Thread auswählen kann. Er bleibt lauffähig, kann also bald wieder ausgewählt werden und erneut scheitern. Bei 100 Threads auf einer CPU können bis zu 99 Wartende jeweils laufen und abgeben, bevor ein verdrängter Besitzer erneut an die Reihe kommt. Die Abgabe verringert aktives Warten, bietet aber keine faire Eintrittsreihenfolge.

Blockieren nimmt Wartende aus der ausführbaren Arbeit

Eine blockierende Sperre setzt einen erfolglosen Aufrufer auf eine Warteschlange. Während er blockiert ist, verbraucht er keine CPU-Zeit. Die Freigabe weckt einen Wartenden, damit er wieder laufen kann. Eine kleine interne Spinlock-Schutzsperre kann das Flag und die Warteschlange schützen; sie wird nur für kurze Verwaltungsarbeit gehalten.

Die Trennung zwischen „Blockieren beschließen“ und „tatsächlich blockieren“ birgt das Risiko eines verlorenen Wecksignals:

1. Ein wartender Thread reiht sich ein und gibt die Schutzsperre frei.
2. Er wird vor dem Aufruf von park() angehalten.
3. Der Besitzer gibt die Sperre frei und ruft für ihn unpark() auf.
4. Wird dieses Wecksignal verworfen, blockiert der Wartende später, ohne dass noch jemand ihn aufweckt.

setpark() von Solaris kündigt die Absicht zu blockieren an. Ein dazwischen eintreffendes Wecksignal bewirkt dann, dass der spätere Aufruf zum Blockieren sofort zurückkehrt. Das Protokoll verbindet die Entscheidung mit dem tatsächlichen Blockieren.

Linux nutzt atomaren Vergleich mit anschließendem Blockieren

Ein Futex verbindet ein Wort im Benutzerspeicher mit Kernelunterstützung für das Warten. futex_wait(addr, expected) blockiert nur, wenn das Wort noch dem erwarteten Wert entspricht; Prüfung und Blockierentscheidung erfolgen atomar gegenüber Operationen auf diesem Futex-Wort. Hat eine Freigabe es bereits geändert, blockiert der Aufrufer nicht aufgrund der veralteten Erwartung.

futex_wake(addr, n) weckt bis zu n Wartende. Eine nicht umkämpfte Sperre kann mit atomaren Befehlen im Benutzerraum erworben und freigegeben werden, sodass ein Systemaufruf entfällt. Die glibc-pthread-Mutexe von Linux nutzen Futexe für das Warten bei Ressourcenkonkurrenz. Ein Wecksignal macht einen Thread lauffähig; sein Sperrprotokoll muss dennoch den Besitz herstellen, bevor er auf geschützte Daten zugreift.

Kurz aktiv warten, dann blockieren

Eine zweiphasige Sperre wartet zunächst kurz aktiv und blockiert dann, falls das Warten andauert. Aktives Warten kann sich lohnen, wenn der Besitzer auf einem anderen Kern läuft und die erwartete Wartezeit kürzer als Blockieren und Aufwecken ist. Bei langen Wartezeiten oder mehr lauffähigen Threads als Kernen ist Blockieren vorzuziehen. Auf einer CPU kann ein aktiv Wartender einem nicht eingeplanten Besitzer nicht helfen, fertig zu werden.

Schedulingpriorität kann Fortschritt verhindern

Bei einer Prioritätsinversion wartet ein Thread mit hoher Priorität auf einen Mutex, den ein Thread mit niedriger Priorität hält, während Arbeit mit mittlerer Priorität den Besitzer von der CPU fernhält. Das Blockieren des hochpriorisierten Wartenden vermeidet aktives Warten, beseitigt aber nicht diese Schedulingverzögerung.

Prioritätsvererbung hebt die Priorität des Besitzers vorübergehend auf die seines höchstpriorisierten Wartenden an, sodass er fertig werden und die Sperre freigeben kann. Die Mars-Sonde Pathfinder der NASA erlebte 1997 durch Prioritätsinversion verursachte Neustarts; das Einschalten der Prioritätsvererbung für den Mutex behob das Problem. Ein aktiv wartender Thread mit hoher Priorität auf einer einzelnen CPU mit strengem Prioritätsscheduling kann noch schlimmer sein: Er kann verhindern, dass der niedrigpriorisierte Besitzer überhaupt läuft.

Ein gemeinsamer Zähler lässt sich leicht mit einem Mutex schützen. Seine Operationen increment, decrement und get erwerben jeweils dieselbe Sperre, führen ihre Aufgabe aus und geben sie frei. Er ist exakt, aber alle Aktualisierungen laufen durch eine gemeinsame Stelle.

Warum der exakte Zähler zum Engpass wird

Auf mehreren Kernen serialisiert ein Mutex die Zähleroperationen. Die Kerne übertragen außerdem den Besitz der Cachezeilen von Sperre und Zähler. Zusätzliche Arbeitsthreads können das Warten schneller erhöhen als die nützliche Arbeit. Ersetzt du den Mutex durch atomic_fetch_add, entfällt auf gängigen Prozessoren der ausdrückliche Sperraufwand, aber jede Aktualisierung schreibt weiterhin dieselbe gemeinsame Speicherstelle.

Ein approximativer Zähler, auch ungenauer Zähler genannt, verteilt Aktualisierungen auf lokale Zähler und überträgt sie gebündelt an einen globalen Zähler. Sein ausgegebener globaler Wert lässt aktuelle lokale Erhöhungen bewusst aus.

Die Aktualisierung von lokal nach global implementieren

Halte pro Kern einen Zähler und einen Mutex, dazu einen globalen Zähler mit eigenem Mutex und eine Schwelle S. Für jede Erhöhung:

1. Wähle den lokalen Platz für diese Aktualisierung und erwirb seinen Mutex.
2. Addiere 1 zum lokalen Zählerstand.
3. Erreicht er S, erwirb den globalen Mutex, während du den lokalen weiterhin hältst.
4. Addiere den lokalen Zählerstand zum globalen, setze den lokalen auf 0 zurück und gib den globalen Mutex frei.
5. Gib den lokalen Mutex frei.

Halte den gewählten Platz während der gesamten Aktualisierung unverändert. Threads mit verschiedenen Plätzen greifen gewöhnlich auf verschiedene Sperren zu und erwerben den globalen Mutex nur bei einer Übertragung. Auch das Lesen des globalen Zählerstands folgt seiner Sperrregel.

Eine gebündelte Übertragung verfolgen

Angenommen, bei vier Kernen und S gleich 5 sind ihre Anzahlen an Aktualisierungen 7, 3, 4 und 0. Kern 1 überträgt bei seiner fünften Erhöhung 5 und hat danach noch 2 lokale Erhöhungen. Die lokalen Zählerstände am Ende sind 2, 3, 4 und 0. Der globale Zählerstand ist 5 und die tatsächliche Summe 14: Neun Erhöhungen bleiben lokal.

Nach abgeschlossenen Aktualisierungen um jeweils eins liegt jeder lokale Zählerstand von 0 bis einschließlich S − 1. Bei P Kernen kann die globale Summe um höchstens folgenden Wert zurückliegen:

Bei vier Kernen und S gleich 5 beträgt die Schranke 16. Diese Schranke betrifft abgeschlossene Aktualisierungen und ihre verbleibenden lokalen Zählerstände; wende sie nicht mitten in einer Übertragung an.

Die Schwelle für die Aufgabe wählen

Eine kleinere Schwelle macht den globalen Wert aktueller, erfordert aber häufigeres Erwerben der globalen Sperre. Bei S gleich 1 wird jede Erhöhung global übertragen. Das verursacht zusätzlichen Aufwand für die lokale Sperre, ohne den globalen Engpass zu vermeiden. Eine größere Schwelle verbessert die Skalierung der Aktualisierungen, vergrößert aber den möglichen Rückstand. In einem veröffentlichten Experiment ermöglichte S gleich 1024 vier Threads, vier Millionen Aktualisierungen in nahezu derselben Zeit auszuführen, die ein Thread für eine Million benötigte.

Für eine exakte Momentaufnahme müssen vor dem Addieren der Zählerstände alle lokalen Mutexe in einer festen Reihenfolge und danach der globale Mutex gehalten werden. Diese Reihenfolge stimmt damit überein, dass Aktualisierungen eine lokale Sperre vor der globalen erwerben. Die Momentaufnahme hält nebenläufige Übertragungen während des Lesens an; das getrennte Lesen jedes Feldes könnte eine Übertragung doppelt zählen oder übersehen.

Approximative Zähler eignen sich für Statistiken, bei denen verzögerte Sichtbarkeit akzeptabel ist. Ein Referenzzähler, der bestimmt, wann Speicher freigegeben werden kann, braucht ein exaktes Verfahren: Ein zu niedriger Zählerstand könnte ein noch verwendetes Objekt freigeben.

Eine gemeinsame verkettete Liste muss sowohl ihre Verknüpfungen als auch die Lebensdauer ihrer Knoten erhalten. Ein Mutex um jede Operation ist ein nützlicher erster Entwurf, weil jeder gemeinsame Durchlauf und jede Änderung einer einzigen Regel folgt.

Wie zwei Einfügevorgänge einen Knoten verlieren

Angenommen, die Liste beginnt bei A. T1 bereitet Knoten X und T2 Knoten Y vor. Ohne gemeinsame Sperre können beide head == A lesen, das next ihres neuen Knotens auf A setzen und dann ihren eigenen Knoten in head speichern. Die spätere Zuweisung an den Listenanfang verdeckt den zuerst eingefügten Knoten. Dieser Knoten wird unerreichbar; ein Einfügevorgang geht verloren und sein Speicher bleibt belegt.

Die geschützte Folge muss das Lesen des aktuellen Listenanfangs, das Setzen der neuen Verknüpfung und das Veröffentlichen des neuen Listenanfangs umfassen. Eine Sperre nur um die letzte Zuweisung würde beiden Threads erlauben, Verknüpfungen aus demselben veralteten Listenanfang aufzubauen.

Private Daten vor dem Erwerb der Sperre vorbereiten

Ein neuer Knoten bleibt privat, bis er in die gemeinsame Liste eingehängt wird. Speicherzuweisung und Initialisierung des Schlüssels können vor dem Erwerb erfolgen. Mit der zuvor verwendeten pthread-Hilfsfunktion, die Rückgabewerte prüft, lässt sich das Einfügen so schreiben:

int insert(list_t *list, int key) {
    node_t *node = malloc(sizeof(*node));
    if (node == NULL) return -1;
    node->key = key;

    check(pthread_mutex_lock(&list->lock));
    node->next = list->head;
    list->head = node;
    check(pthread_mutex_unlock(&list->lock));
    return 0;
}

Schlägt die Speicherzuweisung fehl, kehrt die Funktion zurück, bevor ein Mutex gehalten wird. Der gemeinsame Abschnitt bleibt kurz, während das Prüfen von head und das Aktualisieren der Verknüpfung zusammenbleiben. Threadsichere Speicherzuweisung macht die Liste selbst nicht threadsicher; ihre Verknüpfungen brauchen weiterhin eigenen Schutz.

Lesende folgen derselben Regel

Eine Suche erwirbt den Listenmutex, bevor sie head liest, und hält ihn während des Durchlaufs. Das koordiniert sie mit Einfügen und Entfernen. Setze vor der Schleife eine Ergebnisvariable, aktualisiere sie bei einem Treffer und verlasse die Schleife zu einem einzigen Freigabepunkt vor der Rückkehr. Eine erfolgreiche vorzeitige Rückkehr innerhalb der gesperrten Schleife bräuchte andernfalls eine eigene Freigabe.

Bei diesem Entwurf hält das Entfernen denselben Mutex, während ein Knoten ausgehängt wird. Andere Durchläufe können sich nicht in diesem Knoten befinden, weil sie ebenfalls den Mutex brauchen. Gib ihn erst frei, wenn keine andere Operation ihn noch erreichen kann. Erlaubt eine Schnittstelle einem Aufrufer, einen Knotenzeiger nach der Freigabe der Sperre zu behalten, braucht diese zusätzliche Nutzung eine eigene Vereinbarung zur Lebensdauer; die Listensperre deckt sie allein nicht mehr ab.

Entscheiden, ob sich Sperren pro Knoten lohnen

Sperrkopplung erwirbt die Sperre des nächsten Knotens, bevor sie die des aktuellen freigibt. Diese Überlappung erhält beim Fortschreiten des Durchlaufs einen geschützten Pfad. Mehrere Operationen können dann verschiedene Bereiche der Liste belegen.

Die zusätzliche Nebenläufigkeit hat ihren Preis: Jeder besuchte Knoten bringt Sperr- und Freigabeoperationen mit sich, selbst wenn kein anderer Thread in der Nähe ist. Eine Arbeitslast mit vielen Durchläufen kann langsamer werden als die Version mit einem Mutex. Das Sperren von Knotengruppen ist ein Mittelweg. Vergleiche den komplizierteren Entwurf mit dem einfachen unter der tatsächlichen Arbeitslast, einschließlich erfolgloser Suchen und Entfernungspfade.

Ein Mutex pro Struktur ist ein guter Ausgangspunkt, kann aber Operationen serialisieren, die auf verschiedene Bereiche zugreifen. Zwei nützliche Verfeinerungen sind eine Sperre pro Warteschlangenende und eine Sperre pro Hash-Bucket.

Einen Dummyknoten am Warteschlangenanfang halten

Eine Warteschlange mit zwei Sperren beginnt mit einem Dummyknoten D und head == tail == D. D enthält kein aktuelles Warteschlangenelement. Das erste echte Element, falls vorhanden, liegt bei head->next. Ein Mutex für den Anfang serialisiert Entnahmen; ein Mutex für das Ende serialisiert Einreihungen. Ein Einreihen und ein Entnehmen können daher gleichzeitig fortschreiten.

Das Einreihen bereitet den Wert eines neuen Knotens und seinen leeren nächsten Zeiger privat vor. Unter dem Mutex für das Ende veröffentlicht es den Knoten über das Feld next des alten Endes und verschiebt tail auf den neuen Knoten. Das Entnehmen nutzt den Mutex für den Anfang, um den nächsten Zeiger des alten Dummyknotens zu lesen. Ist er null, gibt es die Sperre frei und meldet eine leere Warteschlange. Andernfalls kopiert es den ersten echten Wert, verschiebt head auf diesen Knoten, gibt die Sperre frei und gibt den alten Dummyknoten frei.

Der Knoten, der den zurückgegebenen Wert enthielt, wird zum nächsten Dummyknoten. Würde dieser Knoten sofort freigegeben, wäre head ein hängender Zeiger.

Den wandernden Dummyknoten verfolgen

Beginne mit D. Das Einreihen von 5 erzeugt N5 und verknüpft D -> N5, mit tail == N5. Das Einreihen von 8 fügt N8 hinzu und ergibt D -> N5 -> N8. Eine Entnahme gibt 5 zurück, verschiebt head auf N5 und gibt D frei. N5 ist nun der Dummyknoten; nur 8 bleibt als Wert in der Warteschlange. Nach einer weiteren Entnahme wird N8 zum Dummyknoten und die Warteschlange ist leer.

Die beiden Enden teilen sich weiterhin eine Verknüpfung

Ist die Warteschlange leer, kann das Einreihen das next des aktuellen Dummyknotens schreiben, während das Entnehmen es unter einem anderen Mutex liest. Die beiden Mutexe allein synchronisieren diese Zugriffe nicht. Deklariere in C11 next als atomaren Zeiger und veröffentliche und lies ihn mit geeigneter Ordnung; standardmäßige sequenziell konsistente atomare Schreib- und Lesezugriffe reichen aus. Die Veröffentlichung muss den vorbereiteten Knotenwert sichtbar machen, bevor die Entnahme ihn liest.

Das Warten auf ein Element braucht zusätzlich zum Sperren einen Signalisierungsmechanismus.

Nach Schlüssel hashen, dann den Bucket sperren

Eine Hashtabelle fester Größe kann in jedem Bucket eine threadsichere Liste mit eigenem Mutex nutzen. Bei 101 Buckets und bucket = key % 101 nutzen die Schlüssel 7 und 50 verschiedene Sperren. Die Schlüssel 7 und 108 werden beide Bucket 7 zugeordnet und müssen dort serialisiert werden. Kollisionen beeinflussen sowohl die Ressourcenkonkurrenz als auch die Länge der Suche.

Alle Zugriffe auf die Liste eines Buckets einschließlich Lesezugriffen folgen dessen Sperrregel. Eine Größenänderung ändert die Bucket-Zuordnung und verschiebt Einträge, sodass dieser einfache Entwurf währenddessen exklusiven Zugriff auf die gesamte Tabelle braucht. Ein Bucket-Mutex allein kann keine Änderung schützen, die jeden Bucket betrifft.

Erst nach dem Finden des Engpasses verfeinern

Beginne mit einer Übersicht des gemeinsamen Zustands: Welche Felder werden gemeinsam genutzt, welcher Mutex oder welche atomare Operation schützt jedes Feld und wann werden Knoten erreichbar oder können freigegeben werden? Prüfe jeden Rückkehrpfad und jeden Pfad bei fehlgeschlagener Speicherzuweisung. Analysiere Verzahnungen, teste unter Last mit einem Wettlaufdetektor und miss die Ressourcenkonkurrenz, bevor du feingranularere Sperren einführst.