Compare-and-swap
Compare-and-Swap (CAS, englisch für Vergleichen und Tauschen) ist eine atomare Operation in der Informatik, um Locking- und Synchronisationsoperationen zu implementieren. Eine Speicherstelle wird mit einem vorgegebenen Wert verglichen, und bei Übereinstimmung mit einem neuen Wert überschrieben. Am Rückgabewert muss abzulesen sein, ob der Tausch ausgeführt wurde.
Die CAS-Instruktion ist eine atomare Operation der CPU, d. h. ihr Ablauf kann und darf von keiner anderen Operation unterbrochen werden. Auf Intel-x86- und -Itanium-Prozessoren ist dies die CMPXCHG-Instruktion.
Andere atomare CPU-Instruktionen, die in ähnlicher Weise verwendet werden können, sind z. B. test-and-set und fetch-and-add. Auf RISC-Architekturen ist diese Operation meist als Load-Link/Store-Conditional (LL/SC) implementiert, da die RISC-Philosophie kombinierte read-modify-write Befehle nicht erlaubt. LL/SC hat auch eine etwas enger gefasste Semantik, da es auch nicht-verändernde Zugriffe auf die referenzierte Speicherstelle erkennen kann.
Verwendung
CAS wird zur Implementierung von Lockingobjekten, wie Semaphoren und Mutexen, und von nebenläufigen Datenstrukturenobjekten verwendet.
Ein simples Mutex-Schema (gegenseitiger Ausschluss) lässt sich per CAS über eine einfache Speicherstelle realisieren, die von mehreren Prozessen bzw. Threads gemeinsam verwendet wird. Möchte ein Thread in einen kritischen Abschnitt eintreten, versucht er per CAS atomar eine 0 (Mutex ungesperrt) durch eine 1 zu ersetzen. War das CAS erfolgreich, konnte also eine 1 in die Speicherstelle geschrieben werden, hat der Thread exklusiven Zugriff auf die geschützten Betriebsmittel. Alle anderen CAS-Operationen auf der Speicherstelle schlagen fehl, so dass die jeweiligen Threads aktiv warten oder die Kontrolle an die Prozessverwaltung des Betriebssystems abgeben müssen. Ein solches schnelles Mutex-Schema, in dem die Mitwirkung des Betriebssystems auf ein Minimum reduziert wird, ist z. B. als Futex (fast userspace mutex) im Linux-Betriebssystem implementiert.
Nebenläufige Datenstrukturobjekte können z. B. mit dem Read-Copy-Update-Schema implementiert werden. Dabei ist der Lesezugriff immer erlaubt; Schreibzugriffe werden zunächst auf einer Teilkopie der Datenstruktur ausgeführt, die dann atomar wieder in die ursprüngliche Struktur eingehängt wird.
In einem klassischen Aufsatz zeigte Maurice Herlihy 1991, dass CAS-Instruktionen zu einer Klasse von Synchronisationsobjekten gehören, die die Implementierung wartezeit-freier, nebenläufiger Datenstrukturobjekte (wait-free concurrent data object) für eine unbeschränkte Anzahl von nebenläufigen Prozessen erlaubt.[1]
Implementierung
Da der ununterbrochene Ablauf der Operation garantiert sein muss, muss die CAS-Instruktion auf Hardware-Ebene implementiert sein. Der folgende Pseudocode ist eine Veranschaulichung.
<< atomare Operation >>
function CompareAndSwap(speicherstelle, alt, neu) {
if *speicherstelle == alt then
*speicherstelle := neu
return true
else
return false
}
Da Speicher manipuliert wird, muss in speichergekoppelten Mehrprozessorsystemen (SMP) ein Verfahren implementiert sein, das die Kohärenz des Speichers und der einzelnen CPU Caches über Prozessorgrenzen hinweg gewährleistet (siehe Cache-Kohärenz).
Siehe auch
Einzelnachweise
- Maurice Herlihy: Wait-free synchronization. In: ACM Trans. Program. Lang. Syst.. 13, Nr. 1, Januar 1991, S. 124–149. Abgerufen am 20. Mai 2007.