Fetch-and-add

Fetch-and-add ist ein Fachbegriff der Informatik, welcher ein Verfahren zur atomaren Veränderung eines Speicherbereichs beschreibt.

Arbeitsweise

Das Verfahren wird mithilfe eines Funktionsaufrufs, der vom Betriebssystem verarbeitet wird, implementiert. Der Inhalt einer Speicherzelle wird ausgelesen und im selben Speicherzyklus durch einen neuen Wert überschrieben, der um 1 größer ist. Der Vorteil ist, dass andere Prozesse den Wert der Variable während dieses Vorgangs nicht verändern können. Inkonsistenzen und Datenverluste sind somit ausgeschlossen. Für die Verwendung von Fetch-and-add muss eine entsprechende Hardware-Unterstützung vorhanden sein.

Implementierung

Beispielhaft soll eine mögliche Umsetzung der Technik in der Programmiersprache C angegeben werden. Je nach verwendeter Programmiersprache kann sich der Aufruf unterscheiden.

<<atomic>> int FetchAndAdd(address alterWert) {
    int wert = *alterWert;
    *alterWert = wert + 1;
    return wert;
}

Für diese Implementierung wird ein Zeiger auf die Speicherzelle, die verändert werden soll, verwendet (hier alterWert).

Abgrenzung zu anderen Verfahren

Neben Fetch-and-Add gibt es noch weitere Möglichkeiten, exklusiven Zugriff auf Speicherbereiche zu gewähren. So reicht es bei Einprozessorsystemen, die Ausführung von Interrupts zu verhindern, während der Speicherinhalt durch einen Prozess verändert wird. Auf Systemen mit mehreren Prozessoren (Multicore-Architekturen) reicht dieses Vorgehen jedoch nicht aus.

Eine weitere Alternative zu Fetch-and-add ist Compare-and-swap.

Literatur

Maurice Herlihy: Wait-free synchronization. In: ACM Trans. Program. Lang. Syst. 13. Jahrgang, Nr. 1, Januar 1991, S. 124–149, doi:10.1145/114005.102808 (brown.edu [PDF; abgerufen am 5. August 2009]).