Bedingungsvariablen, Semaphore und Verklemmungen

Ein Mutex beantwortet die Frage „Wer darf jetzt auf diese Daten zugreifen?“. Er beantwortet nicht die Frage „Ist die Arbeit beendet?“. Um auf ein Ereignis zu warten, braucht ein Thread eine Aufzeichnung des Ereignisses und eine Möglichkeit, blockierend zu warten, bis sich diese Aufzeichnung ändert.

Warum aktives Warten ungünstig ist

Die Schleife while (done == 0) ; verbringt CPU-Zeit damit, wiederholt ein Flag zu prüfen. Auf einer CPU verzögert diese Arbeit den Kindthread, der das Flag setzen muss. In C ist das unsynchronisierte Lesen einer gewöhnlichen Variable, während ein anderer Thread sie beschreibt, außerdem ein Datenwettlauf. Der Compiler muss das Flag nicht bei jedem Durchlauf neu laden.

Eine Bedingungsvariable gibt Threads eine Warteschlange. POSIX stellt pthread_cond_t bereit, initialisiert mit PTHREAD_COND_INITIALIZER oder pthread_cond_init(). Die Warteschlange ist vom geprüften Zustand getrennt: done hält den Abschluss fest; die Bedingungsvariable bietet einen Ort zum blockierenden Warten.

Prüfung und Warten zusammenhalten

pthread_cond_wait(&c, &m) setzt voraus, dass der aufrufende Thread den Mutex m hält. Der Aufruf gibt diesen Mutex atomar frei und beginnt zu warten. Vor der Rückkehr erwirbt er den Mutex erneut. Das schließt die gefährliche Lücke, in der ein anderer Thread den Zustand ändern und signalisieren könnte, bevor der wartende Thread tatsächlich zu warten begonnen hat.

Hier wartet ein Elternthread auf den Abschluss eines Kindthreads. Die Namen lock, wait, signal und unlock kürzen die entsprechenden Aufrufe der Threadbibliothek ab.

/* Parent */
lock(&m);
while (done == 0)
    wait(&c, &m);
unlock(&m);

/* Child */
lock(&m);
done = 1;
signal(&c);
unlock(&m);

Anfangs ist done 0. Läuft der Elternthread zuerst, erwirbt er die Sperre, stellt fest, dass die Arbeit nicht abgeschlossen ist, und wartet. Das Warten gibt m frei, sodass der Kindthread den Mutex erwerben, done setzen und signalisieren kann. Der Elternthread erwirbt schließlich m erneut, prüft done noch einmal und fährt fort.

Läuft der Kindthread zuerst, hält er den Abschluss fest, bevor der Elternthread eintrifft. Sein Signal weckt niemanden auf, aber der später eintreffende Elternthread sieht done == 1 und überspringt das Warten. Die Lösung muss bei beiden Reihenfolgen korrekt sein.

Signale speichern keine Ereignisse

pthread_cond_signal(&c) hebt die Blockierung mindestens eines wartenden Threads auf, wenn Threads warten; POSIX erlaubt, dass mehr als einer aufwacht. Wartet niemand, hat der Aufruf keine Wirkung. pthread_cond_broadcast(&c) weckt alle derzeit wartenden Threads auf. Keiner der beiden Aufrufe hinterlegt eine Benachrichtigung für spätere Threads.

Wird done weggelassen, funktioniert das Join-Muster daher nicht: Ein Kindthread kann signalisieren, bevor sein Elternthread wartet. Danach blockiert sich der Elternthread, ohne dass noch ein Signal folgen wird. Das ist ein verlorenes Wecksignal. Wird done außerhalb des Mutex geprüft, entsteht eine weitere Lücke für ein verlorenes Wecksignal: Der Elternthread prüft und erhält falsch, der Kindthread setzt den Zustand auf wahr und signalisiert, dann beginnt der Elternthread zu warten.

Schütze die Zustandsprüfung und jede Zustandsänderung mit demselben Mutex. Halte ihn von der Prüfung bis zum Warteaufruf. Ein einfacher Signalisierungspfad ändert den Zustand und signalisiert, während er diesen Mutex noch hält. POSIX erlaubt das Signalisieren ohne gehaltenen Mutex, doch das Protokoll für den gemeinsamen Zustand muss trotzdem ein verlorenes Wecksignal verhindern.

Die Rückkehr aus einem Warteaufruf bedeutet, dass der Thread es erneut versuchen darf. Sie bedeutet nicht, dass die benötigte Bedingung noch erfüllt ist. Dieser Unterschied ist wichtig, wenn mehrere Threads um dieselben Daten konkurrieren.

Mesa- und Hoare-Semantik

POSIX, Java, C++-Bedingungsvariablen und Python-Bedingungsvariablen folgen dem Mesa-Verhalten. Hoares Monitore führten das stärkere Übergabemodell ein; Mesas Ansatz ist die übliche praktische Wahl.

Angenommen, C1 wartet darauf, dass ein Puffer mit einem Platz nicht mehr leer ist. Ein Erzeuger füllt ihn und signalisiert C1. C1 ist nun bereit, aber C2 kann den Mutex zuerst erwerben und das Element entnehmen. Wenn C1 schließlich den Mutex erneut erwirbt, ist der Puffer wieder leer.

lock(&m);
while (count == 0)
    wait(&filled, &m);
v = get();
unlock(&m);

Das while wiederholt die Prüfung nach jeder Rückkehr. Ein if prüft nur vor dem ersten Warten und würde C1 erlauben, get() auf einem leeren Puffer aufzurufen. Verwende auch bei einem Erzeuger und einem Verbraucher while: POSIX erlaubt außerdem spontanes Aufwachen, bei dem der Warteaufruf ohne zugehöriges Signal zurückkehrt.

Einen Thread oder alle aufwecken?

Ein Signal eignet sich, wenn die wartenden Threads dieselbe Bedingung benötigen und jeder die Änderung nutzen kann. Ein Broadcast ist nützlich, wenn mehrere fortfahren können oder wenn verschiedene wartende Threads unterschiedliche Mengen benötigen und der signalisierende Thread nicht den richtigen auswählen kann.

Betrachte einen Allokator mit 0 freien Bytes. Ta benötigt 100 Bytes und Tb 10. Ein anderer Thread gibt 50 Bytes frei. Ein Signal könnte Ta aufwecken, der weiterhin nicht fortfahren kann, sodass Tb blockiert bleibt, obwohl seine Anfrage erfüllt werden könnte. Ein Broadcast weckt beide auf. Sie erwerben den Mutex nacheinander erneut; Tb kann Speicher belegen, während Ta erneut wartet. Dies ist eine überdeckende Bedingung: Die Benachrichtigung deckt jeden wartenden Thread ab, der möglicherweise fortfahren kann.

Ein Broadcast kann zusätzliche Weckvorgänge, Kontextwechsel und Konkurrenz um den Mutex verursachen. Getrennte Bedingungsvariablen für verschiedene Prädikate können die Signalisierung gezielter machen. In einem Puffer sollten Erzeuger und Verbraucher nicht eine einzige undifferenzierte Signalwarteschlange gemeinsam nutzen.

Der Zusammenhang mit Monitoren

Ein Monitor bündelt gemeinsam genutzte Daten mit Operationen, die jeweils einen Thread zulassen, und Bedingungsvariablen zum Warten. Java-Objekte stellen eine Sperre und eine Wartemenge bereit. Innerhalb von synchronized kann ein Thread wait(), notify() oder notifyAll() aufrufen; werden diese aufgerufen, ohne den Monitor des Objekts zu besitzen, wird IllegalMonitorStateException ausgelöst.

Das Warten gibt nur den zugehörigen Mutex oder die Sperre des Java-Objekts frei. Hält ein Thread zusätzlich eine andere Sperre, bleibt diese zweite Sperre gehalten. Ein Erzeuger, der sie benötigt, kann dann möglicherweise die Bedingung nicht erfüllen. Prüfe beim Warten alle gehaltenen Sperren, nicht nur die im Aufruf genannte.

Erzeuger fügen einem Puffer fester Größe Elemente hinzu; Verbraucher entnehmen sie. Ein korrekter beschränkter Puffer verhindert das Überschreiben eines vollen Puffers, das Entnehmen aus einem leeren Puffer und gleichzeitige Änderungen an seinen Verwaltungsdaten. Sowohl die Anfragenwarteschlange eines Webservers als auch die Pipe zwischen grep error log.txt und wc -l passen zu diesem Muster.

Verfolge die Ringindizes

Ein Ringpuffer nutzt ein Array und zwei Indizes. fill_ptr bezeichnet den nächsten Schreibplatz; use_ptr bezeichnet den nächsten Leseplatz. Beide werden modulo MAX weitergesetzt. Ein separates count unterscheidet leer von voll, auch wenn die beiden Indizes gleich sind.

void put(int v) {
    buffer[fill_ptr] = v;
    fill_ptr = (fill_ptr + 1) % MAX;
    count++;
}
int get(void) {
    int v = buffer[use_ptr];
    use_ptr = (use_ptr + 1) % MAX;
    count--;
    return v;
}

Beginne mit Kapazität 3 und beiden Indizes bei 0. Das Einfügen von 7, 8 und 9 füllt die Plätze 0, 1 und 2. Der Schreibindex springt auf 0 zurück und count erreicht 3. Das Entnehmen gibt 7 zurück und setzt den Leseindex auf 1. Das Einfügen von 10 nutzt Platz 0 erneut. Das Array ist nun [10, 8, 9], aber die FIFO-Entnahme folgt dem Leseindex: Als Nächstes kommt 8, dann 9, dann 10.

Jedes Signal der entgegengesetzten Rolle zuordnen

Verwende einen Mutex, empty für Erzeuger, die auf Platz warten, und fill für Verbraucher, die auf ein Element warten. Initialisiere beide Bedingungsvariablen und den Mutex, bevor du Threads startest.

/* Producer: repeat for each item v */
lock(&m);
while (count == MAX)
    wait(&empty, &m);
put(v);
signal(&fill);
unlock(&m);

/* Consumer */
lock(&m);
while (count == 0)
    wait(&fill, &m);
v = get();
signal(&empty);
unlock(&m);

Die Prüfung und die Aktualisierung des Puffers bleiben in einem kritischen Abschnitt. Andernfalls könnten zwei Erzeuger beide einen freien Platz sehen und die Arbeit des jeweils anderen überschreiben. Das Warten gibt m frei, sodass die entgegengesetzte Rolle den Puffer ändern kann.

Warum eine Warteschlange ins Stocken geraten kann

Bei einer Bedingungsvariable und Signalen können Erzeuger und Verbraucher die falsche Rolle aufwecken. Bei Kapazität 1 blockieren sich C1 und C2 zunächst, weil der Puffer leer ist. P fügt ein Element ein, weckt C1 auf und wartet dann, weil der Puffer voll ist. C1 entnimmt das Element und signalisiert, aber das Signal kann C2 statt P aufwecken. C1 wartet erneut; auch C2 findet den Puffer leer vor und wartet. P bleibt blockiert, obwohl Platz verfügbar ist. Zwei Warteschlangen leiten jedes Signal an die Rolle, die nun fortfahren kann. Ein Broadcast auf einer gemeinsamen Warteschlange kann dieses Auswahlproblem vermeiden, verursacht aber zusätzliche Weckvorgänge.

Eine größere Kapazität fängt Lastspitzen ab und ermöglicht es, Erzeugungs- und Verbrauchsarbeit außerhalb des kurzen kritischen Abschnitts des Puffers zu überlappen. Die Aktualisierungen des Puffers selbst bleiben sequenziell. Bei Kapazität 1 müssen sich jedes Einfügen und jede Entnahme abwechseln.

Warte für ein sauberes Herunterfahren zunächst, bis jeder Erzeuger seine regulären Elemente abgelegt hat. Stelle dann pro Verbraucher ein reserviertes Datenendelement in die Warteschlange, etwa -1, wenn reguläre Elemente nicht negativ sind. Jeder Verbraucher beendet sich, nachdem er eines entnommen hat. Werden diese Marken gesendet, während Erzeuger noch aktiv sind, können reguläre Elemente ohne Verbraucher zurückbleiben.

Ein Semaphor enthält eine Ganzzahl, die durch atomare P- und V-Operationen geändert wird. Dijkstra führte sie in den 1960er-Jahren als P und V ein; POSIX nennt die Operationen sem_wait() und sem_post(). Atomar bedeutet, dass zwei Threads dieselbe Zähleroperation nicht gleichzeitig teilweise ausführen können.

Verfügbare Einheiten bestimmen den Anfangswert

sem_init(&s, 0, X) erzeugt einen unbenannten Semaphor mit dem Wert X. Das zweite Argument 0 wählt die gemeinsame Nutzung durch Threads eines Prozesses. Für die gemeinsame Nutzung zwischen Prozessen erfordert ein Argument ungleich null, dass sich der Semaphor im gemeinsam genutzten Speicher befindet.

Ein als Sperre verwendeter binärer Semaphor umschließt einen kritischen Abschnitt mit einer P- und einer V-Operation. Der Anfangswert 0 blockiert den ersten eintretenden Thread. Der Anfangswert 2 lässt zwei Threads eintreten und gewährleistet keinen wechselseitigen Ausschluss.

Zwei gleichwertige Zählermodelle

In Dijkstras Definition bleibt der Wert nicht negativ: Die P-Operation wartet blockierend, bis sie den Wert verringern kann, ohne unter null zu fallen, und die V-Operation fügt eine Einheit hinzu. Linux folgt dieser Konvention mit nicht negativen Werten.

Verwende für Ablaufverfolgungen von Hand das Zählermodell mit Vorzeichen: Die P-Operation verringert den Wert und blockiert, wenn der neue Wert negativ ist; die V-Operation erhöht ihn und weckt einen wartenden Thread auf, wenn einer blockiert ist. Der Betrag eines negativen Werts zählt in diesem Modell die blockiert wartenden Threads. Das ist eine Konvention zum Nachvollziehen, kein negativer Wert, den du von der Semaphorschnittstelle von Linux erwarten solltest.

Verfolge eine Sperre mit Anfangswert 1:

1. T0 führt eine P-Operation aus: 1 wird zu 0, sodass T0 eintritt.
2. T1 führt eine P-Operation aus: 0 wird zu −1, sodass T1 blockiert wird.
3. T0 führt eine V-Operation aus: −1 wird zu 0, sodass T1 fortfahren kann.
4. T1 wird fertig und führt eine V-Operation aus: 0 wird zu 1.

Das Wecksignal überträgt die vorhandene Erlaubnis an T1; eine weitere P-Operation ist nicht nötig, bevor T1 in seinen kritischen Abschnitt eintritt.

Eine V-Operation wird gespeichert

Wartet kein Thread, erhöht eine V-Operation die Anzahl der verfügbaren Einheiten. Eine spätere P-Operation kann diese Erlaubnis verbrauchen. Das ist nützlich, wenn ein Thread fertig wird, bevor der auf ihn wartende Thread zu warten begonnen hat. Das Signal einer Bedingungsvariable hat kein solches Gedächtnis.

Semaphore haben keinen Besitzer: Ein Thread kann eine P-Operation und ein anderer eine V-Operation ausführen. Ein Mutex gehört dem Thread, der ihn gesperrt hat; die Freigabe eines POSIX-Mutex mit Standardeinstellungen durch einen anderen Thread ist undefiniertes Verhalten. Der besitzerlose Semaphor unterstützt die Signalisierung, macht aber auch eine zusätzliche V-Operation schwerer zu diagnostizieren.

Ein Semaphor kann aus einem Mutex, einer Bedingungsvariable und einer nicht negativen Ganzzahl aufgebaut werden. Die P-Operation erwirbt die Sperre, wiederholt eine Schleife, solange value <= 0 gilt, wartet, verringert den Wert und gibt die Sperre frei. Die V-Operation erwirbt die Sperre, erhöht den Wert, signalisiert und gibt die Sperre frei. Der Mutex macht die Zähleroperationen atomar; die Schleife behandelt Weckvorgänge, nach denen keine Einheit verfügbar ist. Sperren mit Bedingungsvariablen und Semaphore können einander implementieren, obwohl die korrekte Implementierung einer Bedingungsvariable aus Semaphoren aufwendiger ist.

Dasselbe Paar aus P- und V-Operation kann ein Ereignis oder einen begrenzten Vorrat darstellen. Entscheide, was eine Erlaubnis bedeutet, bevor du den Anfangswert und die Stelle jeder Operation wählst.

Abschluss vor Verwendung sicherstellen

Wenn ein Elternthread auf einen Kindthread wartet, initialisiere finished mit 0. Der Kindthread führt nach Abschluss seiner Arbeit eine V-Operation aus. Der Elternthread führt eine P-Operation aus, bevor er das Ergebnis verwendet.

/* Child */
produce_result();
sem_post(&finished);

/* Parent */
sem_wait(&finished);
use_result();

Trifft der Elternthread zuerst ein, ändert sich der Wert mit Vorzeichen von 0 auf −1 und er blockiert sich. Die V-Operation des Kindthreads setzt den Wert auf 0 zurück und weckt ihn auf. Trifft der Kindthread zuerst ein, ändert seine V-Operation 0 zu 1; die spätere P-Operation ändert 1 zu 0, ohne zu blockieren. Ein abgeschlossenes Ereignis ermöglicht eine erfolgreiche P-Operation.

Einen Ressourcenpool zählen

Ein Pool aus vier Datenbankverbindungen nutzt einen mit 4 initialisierten Semaphor. Jeder Client führt eine P-Operation aus, bevor er eine Verbindung entleiht, und eine V-Operation, nachdem er sie zurückgegeben hat. Ein fünfter gleichzeitiger Entleiher blockiert sich. Der Semaphor zählt die Zulassungen; ein separater Mutex schützt weiterhin die gemeinsame Liste, aus der hervorgeht, welche Verbindung frei ist. Zwei zugelassene Threads dürfen nicht denselben Listeneintrag entfernen.

Drosselung wendet dieselbe Idee auf eine aufwendige Phase an. Angenommen, 100 Threads benötigen während der Verarbeitung jeweils 500 MB. Zusammen könnten sie 50.000 MB benötigen. Ein Rechner mit 8 GB hat bei dezimalen SI-Einheiten 8.000 MB. Die Zulassung von höchstens 12 Workern begrenzt diese Phase auf 6.000 MB und lässt 2.000 MB für andere Zwecke frei.

sem_wait(&processing_slots);
run_memory_heavy_phase();
sem_post(&processing_slots);

Jeder Pfad nach einer erfolgreichen P-Operation muss seine Erlaubnis zurückgeben, auch ein Fehlerpfad. Eine vergessene V-Operation verringert allmählich die Kapazität. Zwei V-Operationen erzeugen eine zusätzliche Erlaubnis und lassen mehr gleichzeitige Nutzer als vorgesehen zu.

Bei einem Rendezvous zusammentreffen

Ein Rendezvous erfordert, dass zwei Threads eintreffen, bevor einer von ihnen fortfährt. Initialisiere a_arrived und b_arrived mit 0.

/* A */
sem_post(&a_arrived);
sem_wait(&b_arrived);

/* B */
sem_post(&b_arrived);
sem_wait(&a_arrived);

Trifft A zuerst ein, hält es seine Ankunft fest und blockiert sich, um auf B zu warten. B hält seine Ankunft fest und kann die gespeicherte Erlaubnis von A verbrauchen. A kann dann die Erlaubnis von B verbrauchen. Werden beide Folgen umgekehrt, sodass vor der V-Operation gewartet wird, blockiert sich jeder Thread, bevor er etwas meldet.

Diese beiden Semaphore ermöglichen ein Treffen. Damit die Synchronisierung in wiederholten Runden erneut genutzt werden kann, muss verhindert werden, dass eine Runde Ankünfte einer anderen verbraucht; ein erfolgreicher Ablauf ist noch kein Entwurf für eine wiederverwendbare Barriere.

Ein Semaphor eignet sich gut für einen Zähler oder ein einfaches Ereignis. Eine Bedingungsvariable eignet sich für ein komplexeres Prädikat, etwa das Warten darauf, dass eine Warteschlange mehrere Elemente eines benötigten Typs enthält. In diesem Fall schützt der Mutex den Zustand, aus dem die Bedingung berechnet wird.

Ein Puffer mit Semaphoren trennt zwei Fragen: „Ist ein Element oder ein Platz verfügbar?“ und „Wer darf das Array jetzt aktualisieren?“. Zwei zählende Semaphore beantworten die erste Frage, ein Mutex die zweite.

Drei verschiedene Steuerungen einrichten

Initialisiere bei Kapazität MAX den Semaphor empty mit MAX, full mit 0 und den Mutex als freigegeben. Hier sind empty und full Semaphore, keine Bedingungsvariablen. Eine Erlaubnis von empty reserviert einen Platz; eine Erlaubnis von full reserviert ein Element.

/* Producer */
sem_wait(&empty);
lock(&mutex);
put(v);
unlock(&mutex);
sem_post(&full);

/* Consumer */
sem_wait(&full);
lock(&mutex);
v = get();
unlock(&mutex);
sem_post(&empty);

Der Erzeuger erwirbt Platz, bevor er auf den Ring zugreift, und gibt dann das fertige Element durch eine V-Operation auf full bekannt. Der Verbraucher erwirbt ein Element, entnimmt es unter dem Mutex und gibt durch eine V-Operation auf empty Platz zurück. Eine erfolgreiche P-Operation reserviert die Ressource bereits, daher brauchen diese Aufrufe keine Prädikatschleife wie bei einer Bedingungsvariable.

Einen Platz verfolgen

Anfangs ist empty 1 und full 0. Ein Verbraucher wartet auf full, ändert den Wert im Modell mit Vorzeichen auf −1 und blockiert sich. Der Erzeuger wartet auf empty und ändert den Wert von 1 auf 0. Er erwirbt den Mutex, fügt ein Element ein, gibt den Mutex frei und führt eine V-Operation auf full aus. Dadurch wird −1 zu 0 und die Blockierung des Verbrauchers aufgehoben.

Die nächste P-Operation des Erzeugers auf empty ändert 0 zu −1 und blockiert ihn. Der Verbraucher entnimmt das Element unter dem Mutex und führt eine V-Operation auf empty aus. Dadurch wird −1 zu 0 und die Blockierung des Erzeugers aufgehoben. Die Semaphorwerte übernehmen die Übergabe; für die Synchronisierung ist kein separates count nötig.

Bei einem größeren Puffer können mehrere Erzeuger den Freiplatzsemaphor passieren. Ohne den Mutex könnten beide denselben fill_ptr lesen und denselben Platz beschreiben. Eine Reservierung ist kein exklusiver Zugriff auf die Indizes des Arrays.

Warum Sperren vor dem Warten zu einer Verklemmung führen kann

Angenommen, der Verbraucher erwirbt mutex, bevor er auf full wartet. Ist der Puffer leer, blockiert er sich, während er den Mutex noch hält. Der Erzeuger braucht diesen Mutex, um das Element einzufügen, dessen V-Operation die Blockierung des Verbrauchers aufheben würde. Keiner kann seine Arbeit beenden.

Eine P-Operation gibt keinen Mutex frei. Der Warteaufruf einer Bedingungsvariable gibt ihren zugehörigen Mutex gezielt frei. Die Reihenfolge in diesem Puffer ist daher wichtig: zuerst reservieren, dann den Mutex erwerben, den Puffer ändern, den Mutex freigeben und anschließend die entgegengesetzte Erlaubnis bereitstellen.

Die allgemeinere Regel lautet, nicht blockierend zu warten, während man eine Sperre hält, die für die Operation benötigt wird, die die Blockierung aufheben kann. Diese Regel erklärt, warum beim Lese-Schreib-Algorithmus eine andere Anordnung sicher sein kann: Sein Schreiber benötigt die Sperre des Leserzählers nicht, um seine Ressource freizugeben.

Der Mutex kann selbst ein binärer Semaphor mit Anfangswert 1 sein. Seine Aufgabe bleibt der wechselseitige Ausschluss; die beiden anderen Semaphore zählen Ressourcen.

Strukturen mit vielen Lesezugriffen können mehrere Leser gleichzeitig zulassen, weil Lesen die Daten nicht ändert. Eine Lese-Schreib-Sperre lässt entweder eine Gruppe von Lesern oder einen Schreiber zu. Jede Änderung an den geschützten Daten erfordert Schreibzugriff.

Die Lesergruppe aufbauen

Verwende readers = 0, einen mit 1 initialisierten Semaphor lock zum Schutz dieses Zählers und einen mit 1 initialisierten Semaphor writelock zum Schutz der gemeinsam genutzten Ressource.

/* Acquire read access */
sem_wait(&lock);
readers++;
if (readers == 1)
    sem_wait(&writelock);
sem_post(&lock);

/* Release read access */
sem_wait(&lock);
readers--;
if (readers == 0)
    sem_post(&writelock);
sem_post(&lock);

Ein Schreiber wartet auf writelock, ändert die Daten und führt dann eine V-Operation auf writelock aus. Die Sperre des Zählers erwirbt er nicht. Der erste Leser erwirbt writelock für die Gruppe, und der letzte Leser gibt ihn zurück. Ein Semaphor eignet sich für diese Übergabe, weil der Thread, der die V-Operation ausführt, nicht der Thread sein muss, der ursprünglich gewartet hat.

Verfolge den Eintritt von R1: R1 erhöht readers auf 1 und erwirbt writelock. R2 erhöht den Zähler auf 2, ohne eine weitere Erlaubnis zu erwerben. Schreiber W wird nun an writelock blockiert. R1 verlässt den Abschnitt und senkt den Zähler auf 1. R2 verlässt ihn, senkt den Zähler auf 0 und führt eine V-Operation aus, sodass W allein schreiben kann.

Der erste Leser kann auf writelock warten, während er lock hält. Das erzeugt nicht die Verklemmung des beschränkten Puffers: Der aktuelle Schreiber benötigt die Sperre des Zählers nicht, um fertig zu werden und eine V-Operation auf writelock auszuführen.

Fairness ist eine eigene Eigenschaft

Dieser Entwurf bevorzugt Leser. Solange der Leserzähler positiv bleibt, kann sich ein weiterer Leser vor einem wartenden Schreiber der Gruppe anschließen. Ein ständiger Strom von Lesern, deren Zugriffe sich überlappen, kann den Schreiber unbegrenzt warten lassen: Verhungern von Schreibern.

Der grundlegende Entwurf gewährleistet Sicherheit, begrenzt aber nicht die Wartezeit eines Schreibers. Ein höherer Leserdurchsatz ist nicht gleichbedeutend mit fairer Bedienung.

Den richtigen Modus verwenden

Eine Lesesperre kann einen Schreibvorgang nicht vor anderen Lesern schützen. Selbst die Aktualisierung eines Cache-Zählers unter Lesezugriff kann einen Datenwettlauf mit einem anderen Leser verursachen. Um in diesem grundlegenden Entwurf die Sperre aufzuwerten, gib den Lesezugriff frei, erwirb Schreibzugriff und prüfe die Bedingung erneut. Wartet ein Thread auf Schreibzugriff, während er noch als Leser gezählt wird, kann er für immer auf sich selbst warten.

POSIX stellt pthread_rwlock_t, pthread_rwlock_rdlock(), pthread_rwlock_wrlock() und pthread_rwlock_unlock() bereit. Java bietet ReentrantReadWriteLock; C++17 bietet std::shared_mutex. Diese Sperren verursachen mehr Verwaltungsaufwand als ein einfacher Mutex. Miss die Arbeitslast: Kurze Abschnitte oder häufige Schreibzugriffe können dazu führen, dass ein einfacher Mutex genauso schnell oder schneller ist.

Eine Atomaritätsverletzung tritt auf, wenn Code darauf angewiesen ist, dass eine Gruppe von Zugriffen unteilbar ist, aber ein anderer Thread dazwischen handeln kann. Jeder einzelne Zugriff kann sinnvoll aussehen, während die kombinierte Operation scheitert.

Die Lücke nach der Prüfung finden

Betrachte einen gemeinsam genutzten Protokollpuffer:

/* T1 */
if (log->buf != NULL)
    write_out(log->buf);

/* T2 */
log->buf = NULL;

T1 kann einen Zeiger prüfen, der nicht null ist, pausieren und fortfahren, nachdem T2 ihn zurückgesetzt hat. T1 übergibt dann null an write_out(). Die beabsichtigte Garantie war nicht nur eine gültige Prüfung, sondern auch, dass der geprüfte Wert bis zum Aufruf nutzbar blieb.

Schütze Prüfung und Verwendung zusammen und die konkurrierende Zuweisung mit demselben Mutex:

/* T1 */
lock(&m);
if (log->buf != NULL)
    write_out(log->buf);
unlock(&m);

/* T2 */
lock(&m);
log->buf = NULL;
unlock(&m);

T2 läuft nun entweder vor oder nach der gesamten Operation von T1. Eine eigene Sperre für jeden Thread hilft nicht: Beide könnten ihre getrennten Sperren gleichzeitig halten. Wird nur T1 gesperrt, kann T2 weiterhin in der Lücke handeln.

Eine gültige Prüfung kann dennoch zu einem ungültigen Kontostand führen

Beginne mit einem Kontostand von 50. Zwei Threads wollen jeweils 30 abheben, aber nur, wenn genug vorhanden ist. Beide können 50 lesen und balance >= 30 bestehen, bevor einer handelt. Werden die Abhebungen dann ausgeführt, kann der Kontostand −10 betragen. Werden Prüfung und Subtraktion zusammen geschützt, bleiben nach der ersten Abhebung 20; der nächste Thread sieht 20 und lehnt ab.

Auch atomares Laden und atomares Subtrahieren machen dieses Paar nicht zu einer Transaktion. Ein anderer Thread kann zwischen der atomaren Prüfung und der atomaren Änderung handeln. Eine Sperre um die gesamte Entscheidung und Änderung setzt die erforderliche Grenze durch.

Dasselbe Problem tritt bei count++ auf: Laden, Addieren und Speichern sind getrennte Schritte. Zwei Threads können denselben alten Wert laden und denselben erhöhten Wert speichern, sodass ein Update verloren geht. Eine Sperre um die Erhöhung oder ein atomares Fetch-and-Add führt das erforderliche Update sicher aus.

Ergebnisse nutzen, ohne zu stark zu verallgemeinern

Lu und Kollegen untersuchten in einer Studie von 2008 105 behobene Nebenläufigkeitsfehler in MySQL, Apache, Mozilla und OpenOffice. Davon waren 74 Fehler ohne Verklemmung und 31 Verklemmungen. Atomaritäts- und Reihenfolgeverletzungen machten 97 % der untersuchten Fehler ohne Verklemmung aus. Dies sind Ergebnisse für die untersuchte Stichprobe, kein für jede Codebasis garantierter Prozentsatz.

Etwa 92 % der untersuchten Fehler ließen sich auslösen, indem die Reihenfolge von höchstens vier Speicherzugriffen kontrolliert wurde. Eine kleine Tabelle mit verzahnten Zugriffen kann daher aufschlussreicher sein als Tausende erfolgreicher gewöhnlicher Läufe. ThreadSanitizer hilft, ausgeführte Datenwettläufe zu finden, aber ein logischer Atomaritätsfehler kann bestehen bleiben, selbst wenn jeder einzelne Zugriff synchronisiert ist. Teste die Invariante der gesamten Operation, etwa „Eine erfolgreiche Abhebung überzieht den Kontostand nie.“

Eine Reihenfolgeverletzung bedeutet, dass Operation A vor Operation B geschehen muss, das Programm aber keine Synchronisierung bereitstellt, die dies garantiert. Wechselseitiger Ausschluss allein kann nicht festlegen, welche Operation zuerst kommt.

Ein Thread kann sofort laufen

Angenommen, ein erzeugender Thread speichert einen neu erzeugten Worker-Datensatz in einem gemeinsam genutzten Zeiger, während der Worker zu Beginn diesen Zeiger verwendet:

/* Creator */
worker = thread_create(worker_main);

/* New worker */
use(worker->state);

Der Worker kann laufen, bevor thread_create() zurückkehrt und bevor die Zuweisung abgeschlossen ist. Die Reihenfolge im Quellcode des erzeugenden Threads sagt nichts darüber aus, wann der neue Thread CPU-Zeit erhält. Ein erfolgreicher Lauf bedeutet lediglich, dass der erzeugende Thread diesen Wettlauf zufällig gewonnen hat.

Bereitschaft nach der Initialisierung bekannt geben

Füge ready = 0, den Mutex m und die Bedingungsvariable c hinzu. Der erzeugende Thread hält den Mutex, während er den Zeiger zuweist und die Bereitschaft bekannt gibt:

/* Creator */
lock(&m);
worker = thread_create(worker_main);
ready = 1;
signal(&c);
unlock(&m);

/* Worker, before using worker */
lock(&m);
while (ready == 0)
    wait(&c, &m);
unlock(&m);
use(worker->state);

Erreicht der Worker den Mutex zuerst, kann er die Bereitschaftsprüfung erst passieren, wenn der erzeugende Thread den Datensatz bekannt gegeben hat. Trifft er später ein, hält ready fest, dass die Initialisierung abgeschlossen ist. Halte den Datensatz am Leben, solange der Worker ihn verwendet, und synchronisiere spätere Änderungen.

Ein mit 0 initialisierter Semaphor bietet eine kürzere Übergabe: Der erzeugende Thread führt nach der Zuweisung des Zeigers eine V-Operation aus, und der Worker wartet vor dessen Verwendung. Existiert ein Ergebnis erst nach dem Abschluss eines Threads, stellt Join auf diesen Thread vor dem Lesen des Ergebnisses die erforderliche Reihenfolge her. Ebenso darf ein Objekt erst freigegeben werden, wenn seine Nutzer fertig sind, zum Beispiel mithilfe von Join oder einem korrekt synchronisierten Referenzzähler.

Warum Änderungen am zeitlichen Ablauf das Problem nicht beheben

Das Hinzufügen von sleep(1) oder sched_yield() ändert nur die Wahrscheinlichkeit des gewünschten Ablaufs. Ein langsameres oder ausgelastetes System kann den Verbraucher weiterhin zu früh fortfahren lassen. Ein Mutex um jede Operation verhindert Überlappungen, erlaubt aber weiterhin, dass die Verwendung den Mutex vor der Initialisierung erwirbt.

In der Studie von Lu und Kollegen war etwa ein Drittel der Fehler ohne Verklemmung auf Reihenfolgeverletzungen zurückzuführen, und etwa 73 % der Fehler ohne Verklemmung wurden nicht allein durch Hinzufügen oder Ändern von Sperren behoben. Bevor du ein Grundelement wählst, benenne die Operation, die abgeschlossen sein muss, und die Operation, die warten muss. Diese Abhängigkeit bestimmt, wohin die V-Operation, das Signal oder Join gehört.

Eine Gruppe von Threads ist verklemmt, wenn jeder auf etwas wartet, das nur ein anderer Thread der Gruppe bereitstellen kann. Keiner kann fortfahren und die Handlung ausführen, die die anderen freigibt. Das Programm kann bei vielen Abläufen funktionieren, bevor eine unglückliche Reihenfolge den Zyklus offenlegt.

Den Fehler mit zwei Sperren aufbauen

T1 erwirbt L1 und fordert als Nächstes L2 an. T2 erwirbt L2 und fordert als Nächstes L1 an. Erwirbt T1 zuerst L1 und dann T2 L2, blockieren beide beim zweiten Erwerb. Jeder Thread hält genau die Ressource, die der andere benötigt.

Dies kann sich in gewöhnlichen Funktionen verbergen. Wenn transfer(a, b) zuerst a und dann b sperrt, können gleichzeitige Aufrufe von transfer(x, y) und transfer(y, x) die Kontosperren in entgegengesetzter Reihenfolge erwerben. Kapselung macht einen Aufruf bequem, kann aber die dabei erworbenen Sperren verbergen.

Alle vier Bedingungen erkennen

Alle vier Bedingungen sind notwendig. Wird eine davon durch den Entwurf ausgeschlossen, werden Ressourcenverklemmungen verhindert. Exklusive Sperren und verschachtelter Erwerb allein belegen nicht, dass ein bestimmter Ablauf einen Zyklus erreicht hat.

Einen Wartegraphen lesen

Zeichne pro Thread einen Knoten. Zeichne T → U, wenn T auf eine Ressource wartet, die U hält. Bei Ressourcen mit jeweils einer Instanz, etwa exklusiven Sperren, zeigt ein Zyklus eine Verklemmung an.

Hält T1 die Ressource A und wartet auf B, hält T2 B und wartet auf C und hält T3 C und wartet auf A, lautet der Graph T1 → T2 → T3 → T1. Alle drei stecken fest. Fordert T3 stattdessen eine freie Sperre D an, kann er fertig werden und C freigeben, sodass T2 und danach T1 fortfahren können. Eine Kette ist kein Zyklus.

Haben Ressourcentypen mehrere austauschbare Instanzen, reicht ein Zyklus allein nicht aus: Eine weitere Instanz könnte verfügbar werden. Nutze Ressourcenanzahlen und ausstehende Anfragen, um diesen Fall zu beurteilen.

Speisende Philosophen und verwandte Fehler

Fünf Philosophen teilen sich fünf kreisförmig angeordnete Gabeln. Jeder benötigt beide benachbarten Gabeln. Nehmen alle zuerst ihre linke Gabel auf, können alle für immer auf ihre rechte Gabel warten. Wird die Erwerbsreihenfolge eines Philosophen umgekehrt, wird der Zyklus unterbrochen. Auch eine Begrenzung auf vier zugelassene Philosophen verhindert, dass alle fünf eine Gabel halten; mindestens ein zugelassener Philosoph kann beide Gabeln erhalten.

Verhungern bedeutet, dass ein Thread unbegrenzt wartet, während andere Fortschritte machen. Livelock bedeutet, dass Threads laufen und reagieren, aber wiederholt keinen Fortschritt erzielen. Eine verklemmte Gruppe ist blockiert. Ein Thread kann sich sogar selbst verklemmen, indem er einen gewöhnlichen, nicht rekursiven Mutex sperrt, den er bereits hält. Auch Semaphore und Bedingungsvariablen können Abhängigkeiten erzeugen: Ein wartender Thread, der eine vom signalisierenden Thread benötigte Sperre hält, kann einen Zyklus schließen, ohne ausdrücklich eine zweite Sperre zu erwerben.

Vorbeugung ändert den Entwurf so, dass eine notwendige Bedingung für Verklemmungen nicht entstehen kann. Eine Sperrreihenfolge ist oft der klarste Ansatz, weil sie die zyklische Abhängigkeit direkt angeht.

Eine Reihenfolge für alle Sperren festlegen

Weise Sperren eindeutige Schlüssel zu und erwirb Sperren mit niedrigeren Schlüsseln immer vor denen mit höheren. Sortiere bei Kontoübertragungen die Kontokennungen vor dem Sperren. Sowohl transfer(x, y) als auch transfer(y, x) erwerben dann zuerst dasselbe Konto. Bezeichnen die Kennungen dasselbe Konto, erwirb seine Sperre einmal.

Ein Zyklus würde erfordern, dass die Schlüssel im Kreis immer weiter steigen und zum Ausgangsschlüssel zurückkehren, was unmöglich ist. Jeder Erwerbspfad muss der Regel folgen. Eine einzige Hilfsfunktion, die die Reihenfolge umkehrt, stellt das Risiko wieder her. Das Linux-Werkzeug lockdep verfolgt beobachtete Sperrabhängigkeiten und meldet möglicherweise unsichere Reihenfolgen.

Alles oder nichts erwerben

Ein strenger Weg, Belegen und Anfordern auszuschließen, besteht darin, einem Thread seine vollständige Ressourcenmenge in einem Schritt oder gar nichts zuzuteilen. Er hält nie eine Teilmenge, während er auf den Rest wartet. Dies setzt voraus, dass die benötigten Ressourcen im Voraus bekannt sind, und kann die Nebenläufigkeit verringern.

Ein verwandtes Protokoll serialisiert Erwerbsfolgen mit einer globalen Vorbeugungssperre:

lock(&prevention);
lock(&L1);
lock(&L2);
unlock(&prevention);
/* use L1 and L2, then release them */

Alle Threads müssen ihre vollständige Menge unter dieser globalen Sperre erwerben, und die Freigabe von Ressourcen darf deren Erwerb nicht erfordern. Ein Thread kann weiterhin L1 halten, während er auf L2 wartet, sodass dies Belegen und Anfordern nicht wörtlich ausschließt. Es verhindert, dass andere Threads einen konkurrierenden teilweisen Erwerb beginnen. Kein Halter kann sich mitten in einer zweiten konkurrierenden Erwerbsfolge befinden. Der Preis besteht darin, Sperren früher zu halten und den Erwerb zu serialisieren.

Aufgeben und erneut versuchen

pthread_mutex_trylock() kehrt sofort mit EBUSY zurück, wenn eine Sperre nicht verfügbar ist. Ein Thread kann L1 erwerben, L2 versuchen und L1 freigeben, wenn der Versuch scheitert. Er muss auch andere teilweise erworbene Ressourcen freigeben, bevor er es erneut versucht.

Zwei Threads können wiederholt kollidieren, zurückweichen und es gleichzeitig erneut versuchen. Das ist ein Livelock: Beide werden ausgeführt, aber keiner wird fertig. Zufälliges Backoff verringert wiederholte Kollisionen; es macht die Wiederholungsschleife nicht zu einer Fairnessgarantie.

Eine Sperre durch eine atomare Operation ersetzen

Compare-and-Swap (CAS) ändert eine Speicherstelle nur, wenn sie noch einem erwarteten Wert entspricht. Gedanklich liest eine Wiederholungsschleife für atomares Addieren den alten Wert, versucht ihn durch den alten Wert plus die Erhöhung zu ersetzen und versucht es erneut, wenn ein anderer Thread ihn zuerst geändert hat. Tatsächliche C-Implementierungen nutzen atomare Typen und Operationen sowohl für das Lesen als auch für die Aktualisierung.

Wird der Erwerb einer Sperre entfernt, kann bei dieser Operation keine Sperrenverklemmung entstehen. Ein sperrfreier Algorithmus garantiert systemweiten Fortschritt, aber ein Thread kann bei seinen wiederholten Versuchen immer wieder unterliegen. Allgemeine sperrfreie Strukturen erfordern außerdem einen sorgfältigen Entwurf der Speicherlebensdauer.

Vermeidung prüft, ob eine vorgeschlagene Anfrage eine Möglichkeit offenlässt, damit jeder Thread fertig wird. Sie erlaubt die üblichen Muster der Ressourcennutzung, verzögert aber Anfragen, die die verbleibenden sicheren Abschlussreihenfolgen zerstören.

Sicher bedeutet eine mögliche Reihenfolge

Eine sichere Folge ordnet Threads so, dass jeder seinen verbleibenden maximalen Bedarf aus den derzeit freien Ressourcen und denen decken kann, die frühere Threads freigeben. Einem unsicheren Zustand fehlt eine solche garantierte Reihenfolge. Er muss noch nicht verklemmt sein: Threads könnten weniger als ihr Maximum anfordern oder Ressourcen frühzeitig freigeben.

Auch Ablaufplanung kann gefährliche Überlappungen vermeiden, indem sie sicherstellt, dass zwei konkurrierende Aufgaben ihre Phasen der Ressourcennutzung nicht gleichzeitig beginnen. Es reicht nicht aus, beide einfach auf eine CPU zu legen, weil sie weiterhin verdrängt werden und sich verzahnen können, während sie Ressourcen halten. Erforderlich ist die Garantie, dass sich die konkurrierenden Phasen nicht überlappen.

Die Tabellen des Bankieralgorithmus aufstellen

Erfasse für jeden Ressourcentyp die Verfügbarkeit Available. Erfasse für jeden Thread das Maximum Max, die Belegung Allocation und Need = Max - Allocation. Vergleiche Vektoren Komponente für Komponente, niemals anhand ihrer aufsummierten Werte.

Verwende die Gesamtmengen (7, 5, 6):

Die Belegungen ergeben zusammen (4, 3, 4), sodass Available = (3, 2, 2) verbleibt.

Die Sicherheitsprüfung durchgehen

Setze Work auf die Verfügbarkeit. Wähle einen noch nicht abgeschlossenen Thread, dessen Restbedarf zum Arbeitsvektor passt, simuliere seinen Abschluss und addiere seine Belegung zum Arbeitsvektor.

1. T1 passt zu (3, 2, 2). Die Rückgabe von (2, 0, 1) ergibt den Arbeitsvektor (5, 2, 3).
2. T0 passt. Die Rückgabe von (1, 1, 0) ergibt (6, 3, 3).
3. T2 passt. Die Rückgabe von (1, 1, 2) ergibt (7, 4, 5).
4. T3 passt. Die Rückgabe von (0, 1, 1) ergibt (7, 5, 6).

Jeder Thread wird in dieser Simulation fertig, also ist der Zustand sicher. Der Arbeitsvektor steigt um die Belegung, nicht um das Maximum: Die zusätzlich für den Abschluss vorübergehend zugeteilten Ressourcen werden ebenfalls zurückgegeben, sodass der Nettozuwachs dem entspricht, was der Thread ursprünglich hielt.

Probeweise bewilligen und erneut prüfen

Eine Anfrage muss sowohl zum Restbedarf des Threads als auch zur Verfügbarkeit passen. Subtrahiere sie dann von der Verfügbarkeit, addiere sie zur Belegung, subtrahiere sie vom Restbedarf und führe die Sicherheitsprüfung für diesen vorläufigen Zustand aus.

Ausgehend von der ursprünglichen Tabelle hinterlässt eine Anfrage von T2 nach (1, 0, 1) die Verfügbarkeit (2, 2, 1). T1 kann weiterhin zuerst laufen, gefolgt von T0, T2 und T3, also ist der Zustand sicher.

Fordert stattdessen T3 (2, 1, 1) an, bleibt die Verfügbarkeit (1, 1, 1). Der verbleibende Restbedarf von T3 ist (2, 0, 1). Kein Thread passt: T0 benötigt 4 von A, T1 benötigt 2 von B, T2 benötigt 2 von C und T3 benötigt 2 von A. Verzögere diese Anfrage trotz der derzeit freien Ressourcen.

Jede spätere Anfrage braucht dieselbe Prüfung. Vermeidung benötigt angegebene maximale Bedarfe und ein bekanntes Ressourcenmodell und eignet sich daher eher für vorhersehbare spezialisierte Systeme als für allgemeine Anwendungslasten.

Ein System kann Verklemmungen entstehen lassen, erkennen und beheben. Es nimmt dabei gelegentlichen Arbeitsverlust in Kauf und schränkt gewöhnliche Ressourcenanfragen dafür weniger ein. Erkennung ist nur nützlich, wenn eine praktikable Maßnahme zur Behebung existiert.

Zyklen blockierter Threads finden

Führe bei Ressourcen mit jeweils einer Instanz einen Wartegraphen und suche nach einem Zyklus, zum Beispiel mit Tiefensuche. Angenommen, die Kanten lauten T1 → T2, T2 → T3, T3 → T1 und T4 → T2. T1, T2 und T3 bilden den Zyklus. T4 ist dahinter blockiert; die eigene Ausführung von T4 kann keine Ressource freigeben, die diesen Zyklus auflöst.

Bei mehreren Instanzen reicht ein Zyklus nicht aus. Verwende die Verfügbarkeit, die Belegung und die aktuell ausstehende Anfrage jedes Threads. Beginne den Arbeitsvektor mit der Verfügbarkeit. Finde wiederholt eine passende Anfrage, simuliere den Abschluss und addiere die Belegung dieses Threads zum Arbeitsvektor. Anders als bei der Vermeidung nutzt diese Prüfung das, worauf Threads jetzt warten, nicht ihren möglichen zukünftigen Höchstbedarf.

Das übliche Verfahren zur Erkennung von Ressourcenverklemmungen stellt zunächst Threads ohne gehaltene Ressourcen zurück: Sie können keine gehaltenen Ressourcen zu einem Ressourcenzyklus beitragen. Unter den Threads, die Ressourcen halten, sind diejenigen, die bei der Prüfung nicht abgeschlossen werden, gemäß dem Modell verklemmt. Andere Threads können trotzdem am Fortschritt gehindert sein, weil sie von dieser Gruppe abhängen. Die Trennung des Zyklus von den dahinter blockierten abhängigen Threads hilft, ein geeignetes Opfer für die Behebung auszuwählen.

Beheben, ohne den gemeinsamen Zustand zu beschädigen

Ein System kann einen oder mehrere Prozesse beenden, Ressourcen durch Zurücksetzen auf einen Prüfpunkt zurückgewinnen oder neu starten. Wähle Opfer nach Behebungsaufwand, Priorität, bereits geleisteter Arbeit und gehaltenen Ressourcen. Prüfe nach dem Entfernen eines Opfers erneut: Mehrere unabhängige Zyklen können mehr als eine Maßnahme erfordern.

Einen beliebigen Thread zu beenden reicht nicht aus, wenn er einen Mutex gesperrt oder eine gemeinsame Struktur nur halb geändert zurücklässt. Die Behebung muss Ressourcen freigeben oder rekonstruieren und einen gültigen Zustand wiederherstellen. Transaktionssysteme können eine verklemmte Transaktion abbrechen, weil das Zurücksetzen zu ihrem Entwurf gehört. Eine gewöhnliche Anwendung benötigt stattdessen oft einen kontrollierten Neustart des Prozesses.

Zeitüberschreitungen sorgfältig deuten

pthread_mutex_timedlock() kann nach Ablauf einer Frist ETIMEDOUT zurückgeben. Ein Watchdog kann ein Gerät zurücksetzen, das keinen Fortschritt mehr meldet. Beide erkennen übermäßiges Warten; langes Warten kann aber auch durch langsame Ein-/Ausgabe oder Ablaufplanung entstehen. Eine Zeitüberschreitung ist ein Anlass zur Untersuchung oder Behebung, keine eindeutige Diagnose eines Zyklus.

Linux und Windows finden und beheben im Allgemeinen keine Zyklen zwischen den eigenen Sperren einer Anwendung. Das Programm muss seine gewählte Strategie implementieren. Wird bei der Behebung wiederholt dieselbe Arbeit als Opfer ausgewählt, kann diese Arbeit verhungern, obwohl jede einzelne Verklemmung aufgelöst wird.

Eine Ereignisschleife wartet auf Ereignisse und führt kurze Behandlungsroutinen auf einem Thread aus. Das Programm wählt ausdrücklich, welches bereite Ereignis als Nächstes behandelt wird. Node.js und nginx nutzen ereignisbasierte Entwürfe, um viele Verbindungen zu bedienen, ohne jeder Verbindung einen eigenen Thread zuzuweisen.

while (1) {
    events = get_events();
    /* handle each ready event, then return to the loop */
}

Synchrone Behandlungsroutinen derselben Schleife laufen einzeln nacheinander. Die gewöhnlichen Befehle einer Behandlungsroutine werden nicht von einer anderen Routine derselben Schleife unterbrochen. Die Schleife ist weiterhin darauf angewiesen, dass die Routinen zügig zurückkehren.

select-Mengen aufbauen und prüfen

select() akzeptiert Mengen von Deskriptoren, die auf Lese-, Schreib- und Ausnahmebedingungen überwacht werden sollen, sowie eine Wartezeit. Sein Argument nfds ist um eins größer als der höchste überwachte Deskriptor. Die Überwachung der Deskriptoren 3, 5 und 9 benötigt daher nfds = 10, nicht 3.

FD_ZERO(&readset);
FD_SET(3, &readset);
FD_SET(5, &readset);
FD_SET(9, &readset);
int n = select(10, &readset, NULL, NULL, NULL);
/* If n > 0, test each watched descriptor with FD_ISSET. */

Ist das Timeout-Argument ein Nullzeiger, wartet der Aufruf auf Bereitschaft; bei einer Wartezeit von null prüft er und kehrt sofort zurück. select() überschreibt die Mengen mit den bereiten Deskriptoren, baue sie daher vor jedem Aufruf erneut auf. Ein positiver Rückgabewert zählt die gesetzten Bits in den zurückgegebenen Mengen; ein in zwei Mengen bereiter Deskriptor zählt doppelt. Null bedeutet Zeitüberschreitung; −1 bedeutet Fehler.

Bereitschaft ist keine Datenübertragung. Das Programm ruft weiterhin read() oder recv() auf. Das Ende der Eingabe kann als Lesebereitschaft erscheinen; gibt ein Leseaufruf 0 zurück, hat die Gegenstelle ihre Sendeseite geschlossen. Behandle dieses Ergebnis, statt dieselbe beendete Eingabe wiederholt zur Bearbeitung zu übergeben.

Behandlungsroutinen kurz und nicht blockierend halten

Setze Sockets auf O_NONBLOCK. Kann eine Operation nicht fortfahren, gibt sie −1 zurück und setzt errno auf EAGAIN oder EWOULDBLOCK, sodass die Behandlungsroutine zur Schleife zurückkehren kann. Die Bereitschaft kann sich vor der Operation ändern, daher schützt der nicht blockierende Modus auch vor unerwartetem Warten nach einer Bereitschaftsmeldung.

Ein blockierender Lesevorgang innerhalb einer Behandlungsroutine verzögert jedes Ereignis in der Warteschlange. Bei 100 wartenden Anfragen und einem blockierenden Festplattenlesevorgang von 10 ms pro Routine wartet die letzte Anfrage etwa 990 ms, bevor ihr eigener Lesevorgang beginnt; der Stapel braucht etwa 1.000 ms. Der Thread verbrachte den Großteil dieser Zeit mit Warten, während bereite Arbeit in der Warteschlange lag.

Eine Bereitschaftsschnittstelle wählen

select() und poll() untersuchen bei jedem Aufruf die übergebene überwachte Menge, sodass ihr Aufwand mit deren Größe wächst. Linux bietet epoll; FreeBSD und macOS bieten kqueue. Die Überwachung nur weniger Deskriptoren macht einen hohen Deskriptorwert bei einem fd_set fester Größe nicht zulässig.

Netzwerkbereitschaft teilt einer Schleife mit, wann sie Ein-/Ausgabe versuchen kann. Bei gewöhnlichen Festplattendateien ist das anders: select() und poll() melden sie als bereit, selbst wenn der Zugriff auf ihre Daten noch auf den Speicher warten muss. Um weiterhin andere Ereignisse zu bedienen, reiche Arbeit asynchron ein und behandle ihr Ergebnis später.

Einreichen, anderswo weitermachen, Ergebnis abholen

Die asynchrone Ein-/Ausgabe von POSIX speichert eine Anfrage in struct aiocb. Wichtige Felder sind aio_fildes für den Dateideskriptor, aio_offset für die Dateiposition, aio_buf für das Ziel und aio_nbytes für die angeforderte Länge.

/* cb describes a read request */
aio_read(&cb);
/* Return to other work. Later: */
int status = aio_error(&cb);
/* EINPROGRESS: still running; 0: succeeded; otherwise an error. */
/* After completion, aio_return(&cb) collects its result. */

aio_read() stellt die Anfrage in die Warteschlange und kehrt zurück. Der Abschluss ist ein separates Ereignis. Wenn aio_error() den Abschluss anzeigt, liefert aio_return() das Ergebnis, etwa nach Erfolg die Anzahl gelesener Bytes. Eine Anfrage kann scheitern, und ein erfolgreicher Lesevorgang kann weniger Bytes als angefordert zurückgeben. Der Anfragedatensatz und sein Puffer müssen gültig bleiben, solange die Operation aussteht.

Das wiederholte Durchsuchen jeder Anfrage in einer engen Schleife verschwendet CPU-Zeit. aio_sigevent kann ein Abschlusssignal oder einen Callback konfigurieren. Linux io_uring nutzt Einreichungs- und Abschlusswarteschlangen; Windows-Ein-/Ausgabeabschlussports ermöglichen die abschlussbasierte Weiterleitung. Diese Schnittstellen lassen das Programm auf abgeschlossene Arbeit reagieren, ohne jede unerledigte Anfrage ständig erneut zu prüfen.

Zustand über die Lücke hinweg bewahren

Ein blockierter Thread behält die lokalen Variablen seiner Funktion auf seinem Stack. Eine Ereignisbehandlungsroutine, die Ein-/Ausgabe einreicht und zurückkehrt, muss speichern, was die spätere Behandlungsroutine benötigt. Diese ausdrückliche Verwaltung ist manuelle Stackverwaltung; der gespeicherte Zustand ist eine Fortsetzung.

Angenommen, ein Server liest Dateideskriptor 12 für einen Client an Socket 7. Beim Einreichen speichert er einen Datensatz, der diese Leseanfrage mit Socket 7 und ihrem Antwortzustand verknüpft. Wenn der Abschluss eintrifft, findet die Schleife den Datensatz, prüft das Leseergebnis und sendet die Antwort an den richtigen Client weiter. Getrennte Datensätze verhindern, dass bei mehreren ausstehenden Anfragen die Ziele verwechselt werden.

Die Fortsetzung sollte an die jeweilige Operation gebunden sein, nicht nur an eine Kennung, die später erneut verwendet werden könnte. Halte die Clientreferenz gültig, bis der Abschluss behandelt ist, und entferne den Datensatz, wenn die Aufgabe endet. Diese Einzelheiten zur Lebensdauer ersetzen Annahmen, die eine geradlinige blockierende Funktion auf ihrem Stack bewahren könnte.

Lesbare Syntax kann eine Suspendierung verbergen

Callbacks, Promises und async/await automatisieren einen Großteil dieser Zustandsspeicherung. In JavaScript suspendiert const data = await readFile(path); die Funktion, während ihre Ein-/Ausgabe aussteht. Andere Arbeit der Schleife kann laufen, und die Funktion wird später mit wiederhergestelltem lokalem Zustand fortgesetzt.

Asynchron bedeutet, dass der Aufrufer fortfahren kann, bevor die Operation abgeschlossen ist. Es bedeutet nicht, dass seine Behandlungsroutinen gleichzeitig auf mehreren CPU-Kernen laufen. Es bewirkt auch nicht, dass CPU-intensiver Code nach einem await automatisch den Prozessor abgibt: Dieser Code belegt den ausführenden Thread weiterhin, bis er zurückkehrt oder erneut suspendiert wird.

Eine Ereignisschleife eignet sich gut für viele meist untätige Verbindungen mit kurzen Arbeitsschüben. Ein threadbasierter Entwurf hält den Kontrollfluss und den Stack einer Aufgabe zusammen. Die beste Wahl hängt von Wartezeit, CPU-Arbeit, Speicher und der Weiterentwicklung des Codes ab.

Den Aufwand der Entwürfe vergleichen

Ein Chatserver mit 50.000 meist untätigen Verbindungen kann von Ereignisdatensätzen statt eines eigenen Threadstacks pro Verbindung profitieren. Ein Bildverarbeitungsprogramm mit aufwendigen Berechnungen pro Anfrage braucht genügend Worker, um die verfügbaren Kerne zu nutzen; eine einzelne ausgelastete Schleife kann diese Berechnungen nicht parallel ausführen.

Verborgene Wartevorgänge sind weiterhin wichtig

Eine Behandlungsroutine kann ins Stocken geraten, ohne eine offensichtlich blockierende Schnittstelle aufzurufen. Der Zugriff auf eine ausgelagerte Seite kann einen Festplattenlesevorgang auslösen. Während dieses Seitenfehlers wartet der Thread der Schleife. mlock() kann benötigte Seiten im Speicher halten, wenn das System die angeforderte Menge fixierten Speichers zulässt. Das bloße Entfernen ausdrücklicher blockierender Aufrufe beseitigt nicht jede Ursache für Verzögerungen.

Codeänderungen können einen weiteren verborgenen Wartevorgang einführen. Beginnt eine zuvor sofort zurückkehrende Hilfsfunktion damit, Daten abzurufen, muss ein ereignisbasierter Aufrufer seine Arbeit an einer Fortsetzung aufteilen oder den Aufruf auslagern. Der Stack eines blockierenden Threads speichert bereits, wo fortgesetzt werden muss und welcher lokale Zustand benötigt wird.

Die Stärken kombinieren

Ein hybrider Entwurf belässt die Netzwerkbereitschaft bei der Ereignisschleife und sendet blockierende oder CPU-intensive Aufgaben an einen Worker-Pool. Abschlüsse gelangen zur Behandlung der Antwort an die Schleife zurück. Node.js nutzt den Threadpool von libuv für Dateisystemoperationen, sodass eine asynchrone Schnittstelle durch Hintergrundthreads implementiert werden kann.

Um mehrere Kerne zu nutzen, kann ein Server pro Kern eine Ereignisschleife in getrennten Threads oder Prozessen ausführen. Nutzen diese Schleifen veränderliche Daten gemeinsam, benötigen sie die üblichen Sperren oder ein anderes Synchronisierungsprotokoll. Der Vorteil, keine Sperren zu benötigen, gilt für synchrone Behandlungsroutinen einer Schleife, nicht für jeden Teil eines ereignisbasierten Servers.

Eine Aufgabe kann sich über await hinweg verzahnen

Angenommen, ein Stück ist noch auf Lager. Eine Behandlungsroutine prüft die Verfügbarkeit, wartet auf die Zahlung und verringert dann den Bestand. Während sie suspendiert ist, kann eine andere Behandlungsroutine denselben Bestand prüfen und ebenfalls eine Zahlung beginnen. Beide Prüfungen können erfolgreich sein, bevor eine der Routinen den Bestand verringert. Keine zwei synchronen Behandlungsroutinen laufen gleichzeitig, dennoch ist die gesamte Prüf- und Aktualisierungsoperation nicht atomar.

Reserviere den Bestand vor der Abgabe der Ausführung durch eine synchronisierte Zustandsänderung und sieh einen Freigabepfad für eine fehlgeschlagene Zahlung vor. Alternativ prüfe unter einem Protokoll erneut, das einen zweiten Verkauf verhindert. Ein Mutex, der während einer langen Wartezeit gehalten wird, kann andere Fortschrittsprobleme verursachen. Entwirf deshalb den Zustandsübergang und seine Wiederherstellung ausdrücklich. Auch bei Ereigniscode musst du überlegen, welche Tatsachen über jede Suspendierung hinweg weiterhin gelten.