Compare-and-swap

Compare-and-Swap (CAS) (engl. für „Vergleichen und Tauschen“) -Instruktionen werden in der Informatik verwendet, 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.

Anwendung

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 geteilt 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

• Prozesssynchronisation
• Paralleler Algorithmus
• Nichtsequentielle Programmierung
• Parallele Programmierung
• Multithreading

Einzelnachweise

1. ↑ Maurice Herlihy: Wait-free synchronization. In: ACM Trans. Program. Lang. Syst.. 13, Nr. 1, January, 1991, S. 124-149. Abgerufen am 20.05.