Verklemmung: wenn eine Sperre zum Problem wird

Eine Sperre hat im letzten Kapitel das Rennen behoben, also liegt es nahe, noch eine hinzuzufuegen. Hier ist eine Ueberweisung zwischen zwei Konten, jedes mit eigener Sperre. Das ist der Fehler, der mehr Produktivsysteme umgebracht hat als jeder andere einzelne Fehler in der Nebenlaeufigkeit.

/* transfer.c */
void transfer(account *from, account *to, long cents) {
  mutex_lock(&from->lock);
  mutex_lock(&to->lock);
  from->balance -= cents;
  to->balance += cents;
  mutex_unlock(&to->lock);
  mutex_unlock(&from->lock);
}

transfer(&alice, &bob, 500);    /* thread 1 */
transfer(&bob, &alice, 700);    /* thread 2 */Jedes Konto hat eine eigene Sperre. Die beiden Aufrufe unten laufen gleichzeitig in zwei verschiedenen Threads.

Schau, wer was besitzt. Thread 1 hat die Sperre von alice erworben und will jetzt die Sperre von bob. Thread 2 hat die Sperre von bob erworben und will jetzt die von alice. Keiner wird je loslassen, weil keiner fertig geworden ist. Beide schlafen fuer immer. Damit das passiert, mussten vier Bedingungen gleichzeitig gelten; alle vier wurden 1971 benannt und sind bis heute die Checkliste.

mutual exclusion      request()
hold and wait         hold(A); request(B)
no preemption         request(B); loop
circular wait         T1 -> B, T2 -> A

all four hold   ->   deadlock
break any one   ->   no deadlockDie vier Coffman-Bedingungen. Brich eine beliebige davon, und eine Verklemmung wird unmoeglich, egal wie die Sperren benutzt werden.

Am billigsten bricht man hier die Kreisverkettung, und das Heilmittel ist eine Zeile: gib jedem sperrbaren Objekt eine globale Ordnung und erwirb Sperren immer in dieser Ordnung. Der klassische Trick ist der Adressvergleich - das Objekt, das im Speicher tiefer liegt, wird immer zuerst genommen. Dann koennen zwei Threads nicht Sperren halten, die der jeweils andere braucht, weil beide zuerst nach derselben greifen.

mutex_lock(&from->lock);   /* wrong: order depends on arguments */
mutex_lock(&to->lock);

mutex_lock(&lo->lock);     /* right: one global order, by address */
mutex_lock(&hi->lock);Beide Aufrufe nehmen jetzt zuerst die niedrigere Adresse, also wartet einer einfach auf den anderen, statt mit ihm zu kaempfen.

Die andere Bedingung, die man brechen kann, ist Halten und Warten. Mach jeden Erwerb zu allem oder nichts: ist die zweite Sperre gerade nicht frei, gib die erste frei und fang von vorn an. Niemand wartet, waehrend er etwas haelt, also kann kein Kreis von Haltern entstehen. Das funktioniert nur, wenn der Zustand nicht halb geaendert liegen bleibt: die Funktion muss alles tun oder nichts. Das ist eine echte Einschraenkung, und genau deshalb gibt es Transaktionen im Bankcode.

while (!mutex_trylock(&from->lock)) { /* backoff */ }
if (!mutex_trylock(&to->lock)) {
  mutex_unlock(&from->lock);
  return RETRY;                /* held nothing while waiting */
}

/* $ timeout 30 ./bank && echo ok || echo 'still stuck' */

Eine Verklemmung ist nicht die einzige Art, wie Arbeit stehen bleibt. Zwei Threads koennen auch weiterlaufen und sich gegenseitig rueckgaengig machen: jeder bemerkt einen Konflikt, gibt hoeflich seine Sperre frei und versucht es erneut - und beide versuchen es im selben Augenblick, fuer immer. Das ist ein Livelock. Die CPU laeuft auf 100%, die Logs sind voller Aktivitaet, und keine Transaktion wird je fertig. Das ist arguably schlimmer als eine Verklemmung, weil ein verklemmter Prozess bei null CPU steht und in einem Stackdump auftaucht, waehrend ein Livelock beschaeftigt und gesund aussieht. Das Heilmittel ist Zufall: exponentielles Zurueckweichen mit einer Zufallskomponente, damit die Threads nicht im Gleichschritt erneut versuchen.

deadlock    blocked,  cpu 0%
livelock    running,  cpu 100%
starvation  running,  cpu 100%

F1 holds B forever
F2 and F3 retry
F1 is frozenDrei Arten, wie Arbeit stehen bleibt, unterschieden nur danach, was der Prozessor tut und wer feststeckt.

Verhungern ist die dritte Fehlerart und sieht am harmlosesten aus. Nichts ist zyklisch und nichts blockiert: das System macht insgesamt Fortschritt, aber ein bestimmter Thread kommt nie an die Reihe. Die uebliche Ursache ist eine Leser-Schreiber-Sperre, die ankommende Leser immer bevorzugt: bei einem stetigen Strom von Lesern wartet ein Schreiber fuer immer. Ein Thread mit der niedrigsten Prioritaet auf einer ausgelasteten Maschine ist ein weiteres Beispiel. Verhungern ist ein Fairnessfehler und kein struktureller, und er kann Tage unentdeckt bleiben, weil die Durchsatzgraphen perfekt aussehen.

Und nun der Grund, warum der naheliegende Rat falsch ist. Eine Sperre hinzuzufuegen bringt keine Sicherheit, sondern eine Ressource, und jede neue Ressource ist eine neue Wartekante im Graphen. Zwei Sperren erzeugen einen moeglichen Kreis; zehn Sperren erzeugen 45 geordnete Paare, und jedes davon kann irgendwo im Code die falsche Reihenfolge sein. Eine Funktion, die drei getrennte Sperren nimmt und Code aufruft, der zwei weitere nimmt, hat eine Verklemmung an einer Stelle moeglich gemacht, an der niemand suchen wird. Sperren sind zudem nicht kompositionell: zwei unabhaengige Module, die jedes fuer sich korrekt sind, koennen sich verkeilen, sobald das eine das andere aufruft, waehrend es seine eigene Sperre haelt.

In der Praxis sind Sperren nicht die einzige Ressource, die sich verkeilen kann. Ein Thread, der eine Datenbankverbindung haelt und auf eine Verbindung aus demselben Pool wartet, hungert den Pool aus; zwei Dienste, die jeweils auf einen synchronen Aufruf des anderen warten, sind eine verteilte Verklemmung, die kein Stackdump eines einzelnen Prozesses zeigt. Im Betrieb findet man solche Faelle meist mit Zeitlimits und Wachhund-Threads: hat eine Transaktion in N Sekunden keinen Fortschritt gemacht, werden die Stapel aller Threads abgezogen und man sucht den Kreis. In einem laufenden Prozess sieht man ihn direkt - die Stapel der verklemmten Threads nennen die Sperre, auf die jeder wartet, und die Sperre, die jeder besitzt.