Compare-and-swap

Grundprinzip und Bedeutung

Compare-and-Swap (CAS, englisch für „Vergleichen und Tauschen“) ist eine atomare Operation der Informatik. Sie wird verwendet, um Locking- und Synchronisationsoperationen sowie nebenläufige Datenstrukturen zu implementieren. Eine Speicherstelle wird dabei mit einem vorgegebenen alten Wert verglichen. Stimmen die Werte überein, wird die Speicherstelle durch einen neuen Wert überschrieben. Der Rückgabewert zeigt an, ob dieser Tausch tatsächlich ausgeführt wurde.

Atomar bedeutet, dass der gesamte Ablauf nicht von einer anderen Operation unterbrochen werden kann. Dadurch kann geprüft und geändert werden, ohne dass zwischen diesen beiden Schritten ein anderer Prozess oder Thread denselben Speicher verändert. CAS eignet sich deshalb besonders für Situationen, in denen mehrere gleichzeitig ausgeführte Abläufe auf gemeinsam genutzte Daten zugreifen.

Hardware und verwandte Operationen

Weil der Ablauf ununterbrochen garantiert werden muss, muss CAS auf Hardware-Ebene implementiert sein. Auf Intel-x86- und -Itanium-Prozessoren steht dafür die CMPXCHG-Instruktion zur Verfügung.

Eine vereinfachte Darstellung lautet:

function CompareAndSwap(speicherstelle, alt, neu) { if *speicherstelle == alt then *speicherstelle := neu return true else return false }

Die Operation vergleicht also den Inhalt von speicherstelle mit alt. Nur bei Gleichheit wird der Inhalt durch neu ersetzt und true zurückgegeben. Bei ungleichem Inhalt bleibt die Speicherstelle unverändert und die Operation gibt false zurück.

Ähnlich verwendbare atomare CPU-Instruktionen sind test-and-set und fetch-and-add. Auf RISC-Architekturen wird CAS meist als Load-Link/Store-Conditional (LL/SC) umgesetzt, weil die RISC-Philosophie kombinierte read-modify-write-Befehle nicht erlaubt. LL/SC besitzt außerdem eine etwas enger gefasste Semantik: Es kann auch nicht verändernde Zugriffe auf die referenzierte Speicherstelle erkennen.

Da CAS Speicher verändert, muss in speichergekoppelten Mehrprozessorsystemen (SMP) zusätzlich die Kohärenz des Speichers und der einzelnen CPU-Caches über Prozessorgrenzen hinweg gewährleistet werden. Dieses Problem gehört zur Cache-Kohärenz.

Mutex und andere Synchronisationsobjekte

CAS kann zur Implementierung von Lockingobjekten wie Semaphoren und Mutexen verwendet werden. Ein Mutex (gegenseitiger Ausschluss) kontrolliert den Zugang zu einem kritischen Abschnitt, also zu einem Bereich, in dem geschützte Betriebsmittel genutzt werden.

Ein einfaches Mutex-Schema verwendet eine Speicherstelle, die von mehreren Prozessen oder Threads gemeinsam genutzt wird. Der Wert 0 bedeutet, dass der Mutex nicht gesperrt ist, der Wert 1 bedeutet, dass er gesperrt ist. Möchte ein Thread in den kritischen Abschnitt eintreten, versucht er per CAS atomar, 0 durch 1 zu ersetzen.

Ist das CAS erfolgreich, konnte die 1 geschrieben werden, und der Thread erhält exklusiven Zugriff auf die geschützten Betriebsmittel. Alle anderen CAS-Operationen auf dieser Speicherstelle schlagen dann fehl. Die betroffenen Threads können aktiv warten oder die Kontrolle an die Prozessverwaltung des Betriebssystems abgeben. Ein solches schnelles Mutex-Schema, bei dem die Mitwirkung des Betriebssystems auf ein Minimum reduziert wird, ist im Linux-Betriebssystem beispielsweise als Futex (fast userspace mutex) implementiert.

Nebenläufige Datenstrukturen und Wartefreiheit

CAS wird auch für nebenläufige Datenstrukturobjekte eingesetzt. Ein Beispiel ist das Read-copy-update-Schema. Dabei bleiben Lesezugriffe immer erlaubt. Schreibzugriffe werden zunächst auf einer Teilkopie der Datenstruktur ausgeführt. Anschließend wird diese Teilkopie atomar wieder in die ursprüngliche Struktur eingehängt.

Maurice Herlihy zeigte 1991 in einem klassischen Aufsatz, dass CAS-Instruktionen zu einer Klasse von Synchronisationsobjekten gehören, mit denen sich wartezeit-freie nebenläufige Datenstrukturobjekte (wait-free concurrent data object) für eine unbeschränkte Anzahl nebenläufiger Prozesse implementieren lassen. Die Bedeutung von CAS reicht damit über einfache Sperren hinaus: Die Operation bildet eine Grundlage für Synchronisationsverfahren und Datenstrukturen, die auch bei gleichzeitigen Zugriffen zuverlässig funktionieren sollen.