Quelltext der Seite Compare-and-swap

'''Compare-and-Swap''' ('''CAS''', {{enS}} für ''Vergleichen und Tauschen'') ist eine [[atomare Operation]] in der [[Informatik]], um [[Lock|Locking-]] und [[Synchronisation]]soperationen 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 [[Prozessor|CPU]], d.&nbsp;h. ihr Ablauf kann und darf von keiner anderen Operation unterbrochen werden. Auf Intel-[[X86-Prozessor|x86]]- und -[[Itanium]]-Prozessoren ist dies die CMPXCHG-Instruktion.

Andere atomare CPU-Instruktionen, die in ähnlicher Weise verwendet werden können, sind z.&nbsp;B. [[test-and-set]] und [[fetch-and-add]]. Auf [[Reduced Instruction Set Computer|RISC]]-Architekturen ist diese Operation meist als [[Load-Link/Store-Conditional]] (LL/SC) implementiert, da die RISC-Philosophie kombinierte [[RMW-Befehl|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 [[Lock]]ingobjekten, wie [[Semaphor (Informatik)|Semaphoren]] und [[Mutex]]en, 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 [[Prozess (Informatik)|Prozessen]] bzw. [[Thread (Informatik)|Threads]] gemeinsam verwendet wird. Möchte ein Thread in einen [[Kritischer Abschnitt|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 [[Aktives Warten|aktiv warten]] oder die Kontrolle an die Prozessverwaltung des [[Betriebssystem]]s abgeben müssen. Ein solches schnelles Mutex-Schema, in dem die Mitwirkung des Betriebssystems auf ein Minimum reduziert wird, ist z.&nbsp;B. als [[Futex]] ''(fast userspace mutex)'' im [[Linux]]-Betriebssystem implementiert.

Nebenläufige Datenstrukturobjekte können z.&nbsp;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.<ref>{{cite journal |first=Maurice |last=Herlihy |title=Wait-free synchronization |journal=ACM Trans. Program. Lang. Syst. |volume=13 |issue=1 |pages=124–149 |date=1991-01 |url=https://cs.brown.edu/~mph/Herlihy91/p124-herlihy.pdf |access-date=2007-05-20 |language=en}}</ref>

== 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 [[Mehrprozessorsystem]]en ([[Symmetrisches Multiprozessorsystem|SMP]]) ein Verfahren implementiert sein, das die Kohärenz des Speichers und der einzelnen CPU [[Cache]]s über Prozessorgrenzen hinweg gewährleistet (siehe [[Cache-Kohärenz]]).

== Siehe auch ==
* [[Prozesssynchronisation]]
* [[Paralleler Algorithmus]]
* [[Nichtsequentielle Programmierung]]
* [[Parallele Programmierung]]
* [[Multithreading]]

== Einzelnachweise ==
<references />

[[Kategorie:Betriebssystemtheorie]]
[[Kategorie:Parallelverarbeitung]]