Synchronisation

Woher die Nebenläufigkeit kommt

Ein Anwendungsprogramm mit einem Thread kann sich darauf verlassen, dass niemand seine Variablen verändert, während es arbeitet. Im Kernel gilt das praktisch nie. Dieselben Daten können gleichzeitig angefasst werden von

• anderen CPUs, die denselben Code oder anderen Kernel-Code ausführen,
• einem Interrupt-Handler, der den laufenden Code mitten in einer Operation unterbricht (Kapitel 8),
• einem Softirq, der beim Verlassen eines Interrupts läuft,
• einem anderen Task, wenn der Kernel-Code verdrängt wird (Kapitel 6) oder selbst schläft.

Ein Codeabschnitt, der gemeinsam genutzte Daten verändert und dabei nicht unterbrochen werden darf, heißt kritischer Abschnitt. Wie leicht dabei etwas schiefgeht, zeigt schon die einfachste Operation:

Eine solche Race ConditionRace ConditionFehler, bei dem das Ergebnis vom zufälligen zeitlichen Ablauf nebenläufiger Zugriffe abhängt, etwa wenn zwei CPUs gleichzeitig denselben Wert ändern. ist tückisch: Der Fehler tritt nur bei ungünstigem Timing auf, vielleicht einmal in einer Million Durchläufen, und verschwindet oft, sobald man Debug-Ausgaben einbaut. Im Kernel kann sie zu beschädigten Datenstrukturen, Speicherlecks, Abstürzen oder Sicherheitslücken führen.

Atomare Operationen

Die Grundbausteine aller Synchronisation sind Befehle, die die Hardware unteilbar ausführt. Für einfache Zähler und Flags reichen sie schon allein:

atomic_t aktive = ATOMIC_INIT(0);

atomic_inc(&aktive);                       /* unteilbar erhöhen */
if (atomic_dec_and_test(&aktive))          /* verringern, 0 erreicht? */
	alles_aufraeumen();

/* Compare-and-Swap: nur setzen, wenn der Wert noch 'alt' ist */
if (atomic_cmpxchg(&zustand, BEREIT, LAEUFT) == BEREIT)
	/* wir haben den Zustand gewonnen */;

set_bit(FLAG_AKTIV, &dev->flags);          /* atomare Bit-Operationen */

Für Referenzzähler gibt es den spezialisierten Typ refcount_t. Er erkennt Über- und Unterläufe und bleibt dann auf einem sicheren Wert stehen, statt wieder bei 0 zu beginnen. Viele frühere Sicherheitslücken beruhten auf solchen Überläufen: Ein Objekt wurde freigegeben, obwohl es noch benutzt wurde (use after free).

/* CPU 0 */                       /* CPU 1 */
daten = 42;                       while (!bereit)
bereit = 1;                               ;
                                  print(daten);   /* evtl. alter Wert! */

Spinlocks

Ein SpinlockSpinlockSperre, bei der ein wartender Prozessor in einer Schleife aktiv prüft, bis sie frei wird. Nur für sehr kurze Abschnitte; der Halter darf nicht schlafen. ist die einfachste Sperre: Wer sie nicht bekommt, prüft in einer Schleife immer wieder, ob sie frei geworden ist, er „dreht sich“ (to spin).

static DEFINE_SPINLOCK(liste_lock);

spin_lock(&liste_lock);
list_add(&eintrag->node, &liste);     /* kritischer Abschnitt – kurz halten! */
spin_unlock(&liste_lock);

Spinlocks haben strenge Regeln:

• Kurz halten. Jede wartende CPU verbrennt Rechenzeit.
• Niemals schlafen, solange man einen Spinlock hält. Kein Mutex, kein GFP_KERNEL, kein copy_from_user(), das einen Seitenfehler auslösen könnte. Ein schlafender Halter würde alle Wartenden unbegrenzt kreisen lassen.
• Während ein Spinlock gehalten wird, ist die Verdrängung abgeschaltet. Der Halter wird also nicht vom Scheduler unterbrochen.

Spinlocks und Interrupts

Kritisch wird es, wenn dieselben Daten auch in einem Interrupt-Handler benutzt werden. Hält Code im Prozesskontext die Sperre und kommt auf derselben CPU ein Interrupt, dessen Handler dieselbe Sperre will, dreht sich der Handler endlos: Der Halter kann erst weitermachen, wenn der Handler fertig ist. Das ist ein Deadlock auf einer einzigen CPU. Deshalb gibt es Varianten:

Mutexe und Semaphoren

Muss ein kritischer Abschnitt länger dauern oder darin geschlafen werden, etwa weil auf I/O gewartet oder Speicher angefordert wird, ist ein MutexMutexSperre mit gegenseitigem Ausschluss, bei der wartende Tasks schlafen gelegt werden. Darf nur im Prozesskontext benutzt werden. die richtige Wahl. Ein wartender Task wird schlafen gelegt, statt die CPU zu blockieren:

static DEFINE_MUTEX(konfig_lock);

mutex_lock(&konfig_lock);
err = konfiguration_neu_laden();       /* darf schlafen, z. B. Datei lesen */
mutex_unlock(&konfig_lock);

Mutexe sind nur im Prozesskontext erlaubt, nie in Interrupt-Handlern oder Softirqs, weil dort nicht geschlafen werden darf. Nur der Task, der den Mutex genommen hat, darf ihn wieder freigeben. Als Optimierung dreht sich ein wartender Task kurz, solange der aktuelle Halter auf einer anderen CPU läuft (optimistic spinning), denn dann wird der Mutex wahrscheinlich gleich frei, und ein teurer Schlaf-und-Weck-Zyklus wird gespart.

Weitere schlafende Sperren:

• Semaphoren (struct semaphore) erlauben bis zu n gleichzeitige Halter. Im Kernel werden sie kaum noch verwendet.
• Lese-Schreib-Semaphoren (rw_semaphore) erlauben viele gleichzeitige Leser oder einen Schreiber. Ein Beispiel ist die Sperre für den Adressraum eines Prozesses (mmap_lock, Kapitel 7).
• RT-Mutexe unterstützen Prioritätsvererbung: Hält ein niedrig priorisierter Task eine Sperre, auf die ein hoch priorisierter wartet, erbt der Halter vorübergehend die höhere Priorität. Das verhindert die Prioritätsinversion, ein klassisches Problem in Echtzeitsystemen.

Welche Sperre wofür?

Ohne Sperren lesen: Seqlocks und Per-CPU-Daten

Seqlocks eignen sich für kleine Daten, die sehr oft gelesen und selten geschrieben werden. Der Schreiber erhöht vor und nach dem Schreiben eine Folgenummer, die während des Schreibens also ungerade ist. Leser nehmen gar keine Sperre: Sie lesen Folgenummer, Daten und erneut die Folgenummer. Hat sich die Nummer geändert oder war sie ungerade, versuchen sie es einfach noch einmal:

do {
	seq = read_seqbegin(&zeit_lock);
	sek  = aktuelle_zeit.sek;
	nsek = aktuelle_zeit.nsek;
} while (read_seqretry(&zeit_lock, seq));

So arbeitet zum Beispiel die Zeitverwaltung des Kernels, auch die Zeitabfrage im vDSO (Kapitel 4).

Per-CPU-Variablen vermeiden Konkurrenz von vornherein: Jede CPU bekommt ihre eigene Kopie. Statistiken wie Paketzähler werden pro CPU geführt und nur beim Auslesen aufsummiert. Man muss lediglich verhindern, dass der Task während des Zugriffs auf eine andere CPU wechselt. Die Funktionen this_cpu_inc() und Verwandte erledigen das in einem einzigen Befehl.

RCU: Read-Copy-Update

Für Daten, die sehr oft gelesen und selten geändert werden, hat Linux ein eigenes, besonders leistungsfähiges Verfahren: RCURCU (Read-Copy-Update)Synchronisationsverfahren für überwiegend gelesene Daten: Leser brauchen keine Sperren, Schreiber arbeiten auf Kopien und geben alte Versionen erst nach einer Gnadenfrist frei.. Leser nehmen dabei keinerlei Sperre und schreiben nicht einmal in gemeinsam genutzten Speicher. Sie skalieren deshalb nahezu perfekt mit der Anzahl der CPUs.

In Code sieht das so aus:

/* Leser – beliebig viele gleichzeitig, auch im Interruptkontext */
rcu_read_lock();
r = rcu_dereference(routing_tabelle);   /* Zeiger sicher lesen */
ziel = suche(r, adresse);
rcu_read_unlock();

/* Schreiber – untereinander z. B. mit einem Mutex synchronisiert */
neu = kopiere_und_aendere(alt);
rcu_assign_pointer(routing_tabelle, neu);   /* veröffentlichen */
synchronize_rcu();                           /* Gnadenfrist abwarten */
kfree(alt);                                  /* oder kurz: kfree_rcu(alt, rcu) */

Woher weiß der Kernel, dass die Gnadenfrist vorbei ist? Ein RCU-Leser darf in seinem Leseabschnitt nicht schlafen (in der Grundvariante). Hat also jede CPU seit Beginn der Wartezeit mindestens einmal einen Ruhezustand durchlaufen, also einen Kontextwechsel, den Leerlauf oder die Rückkehr in den User Space, kann kein alter Leser mehr aktiv sein. RCU muss also nicht die Leser zählen, sondern nur beobachten, was die CPUs ohnehin tun.

RCU wird im Kernel an tausenden Stellen eingesetzt, unter anderem für Routing-Tabellen, den Dentry-Cache des VFS, die Prozessliste und die Liste der geladenen Module. Paul McKenney, der Hauptentwickler von RCU in Linux, hat das Verfahren ausführlich dokumentiert (Documentation/RCU/).

Deadlocks

Ein DeadlockDeadlock (Verklemmung)Zustand, in dem zwei oder mehr Beteiligte jeweils auf eine Sperre warten, die ein anderer hält, sodass keiner weiterkommt. entsteht, wenn sich Abläufe gegenseitig blockieren. Das klassische Muster heißt ABBA:

CPU 0                         CPU 1
mutex_lock(&A);               mutex_lock(&B);
mutex_lock(&B);  /* wartet */ mutex_lock(&A);  /* wartet */

Beide warten für immer aufeinander. Die wichtigste Regel dagegen lautet: Sperren immer in derselben, festgelegten Reihenfolge nehmen. Größere Subsysteme dokumentieren diese Reihenfolge ausdrücklich in Kommentaren.

Weil solche Fehler nur bei ungünstigem Timing auftreten, hat der Kernel einen eingebauten Prüfer: lockdep (CONFIG_PROVE_LOCKING). Er protokolliert zur Laufzeit, welche Sperren in welcher Reihenfolge und in welchem Kontext genommen werden, und meldet schon die bloße Möglichkeit eines Deadlocks, etwa „possible circular locking dependency detected“, auch wenn er tatsächlich noch nie aufgetreten ist. Kernel-Entwickler testen ihre Änderungen deshalb mit aktiviertem lockdep.

Selbst ausprobieren

// race.c – übersetzen mit: gcc -O2 -pthread -o race race.c
#include <pthread.h>
#include <stdatomic.h>
#include <stdio.h>

#define N 10000000

static volatile long counter;          /* ungeschützt */
static atomic_long atomic_counter;     /* atomar */

static void *worker(void *arg)
{
	(void)arg;
	for (long i = 0; i < N; i++)
		counter++;                              /* laden, erhöhen, speichern */
	for (long i = 0; i < N; i++)
		atomic_fetch_add(&atomic_counter, 1);   /* unteilbar */
	return NULL;
}

int main(void)
{
	pthread_t a, b;
	pthread_create(&a, NULL, worker, NULL);
	pthread_create(&b, NULL, worker, NULL);
	pthread_join(a, NULL);
	pthread_join(b, NULL);
	printf("erwartet:    %ld\n", 2L * N);
	printf("ungeschützt: %ld\n", counter);
	printf("atomar:      %ld\n", (long)atomic_counter);
	return 0;
}

gcc -O2 -pthread -o race race.c && ./race

# Wie warten Threads im User Space auf Sperren? Über den Systemaufruf futex
strace -f -c -e trace=futex ./race

# Konkurrenz um Kernel-Sperren messen (benötigt perf und Root-Rechte)
sudo perf lock contention -a -- sleep 5