Fetch-and-add
Fetch-and-add (pobierz-i-dodaj) – w informatyce specjalna instrukcja procesora, która pozwala na modyfikację pamięci w niepodzielny sposób. Ma ona zastosowanie przy implementacji wzajemnego wykluczania i algorytmów współbieżnych w systemach wieloprocesorowych.
W systemach jednoprocesorowych do realizacji sekcji krytycznej wystarcza wyłączenie/zablokowanie obsługi przerwań przed jej rozpoczęciem. Jednak w systemach wieloprocesorowych, nawet przy zablokowanych przerwaniach, dwa lub więcej procesorów może dokonywać operacji dostępu do tej samej lokacji w pamięci w tym samym czasie. Instrukcja fetch-and-add pozwala procesorowi na atomowe zwiększenie wartości w pamięci, zapobiegając kolizjom od innych procesorów.
Spis treści |
Realizacja [edytuj]
Instrukcja fetch-and-add zachowuje się jak funkcja poniżej. Najistotniejsze jest to, że cała funkcja jest wykonana jako operacja atomowa. Żaden proces nie może przerwać działania funkcji i zarejestrować stan, który istnieje podczas jej wykonywania. Poniższy kod tylko wyjaśnia zachowanie instrukcji fetch-and-add. Jego realizacja rzeczywista wymaga wsparcia sprzętowego i nie może być zaimplementowana jako funkcja wysokiego poziomu.
<< operacja atomowa >>
function FetchAndAdd(address location) {
int value := *location
*location := value + 1
return value
}
x86 [edytuj]
W architekturze x86 od wersji procesora 8086 istnieje instrukcja ADD, w której jednym z argumentów docelowych może być adres w pamięci. Jeśli ową instrukcję poprzedzi się prefiksem LOCK, to jej działanie stanie się operacją atomową w systemach wieloprocesorowych. Jednak za jej pomocą nie można odczytać oryginalnej wartości z pamięci (chociaż można odczytać pewne flagi). Tę możliwość wprowadzono dopiero w procesorze 486 za pomocą instrukcji XADD.
Języki wysokiego poziomu [edytuj]
C++ [edytuj]
Początkowo standard języka C++ nie definiował metody dla operacji fetch-and-add. Taka funkcjonalność była dostępna dzięki wsparciu systemu operacyjnego[1], bądź jako rozszerzenie kompilatora[2]. W raz z pojawieniem się C++11, pojawiły się standardowe mechanizmy[3] ułatwiające korzystanie z wątków takie jak: atomic_fetch_add, atomic_fetch_add_explicit.
.NET Framework (C#) [edytuj]
W bibliotece standardowej jest dostępna metoda Interlocked.Increment[4], która implementuje funkcjonalność fetch-and-add.
Java [edytuj]
Począwszy od wersji 1.5, biblioteka standardowa zawiera pakiet java.util.concurrent.atomic, w którym znajdują się klasy AtomicInteger i AtomicLong zawierające metodę getAndIncrement będącymi implementacją fetch-and-add[5].
Zobacz też [edytuj]
Przypisy
- ↑ InterlockedIncrement function (Windows). W: MSDN [on-line]. [dostęp 2012-11-27].
- ↑ _InterlockedIncrement. W: MSDN [on-line]. [dostęp 2012-11-27].
- ↑ Atomic operations library (ang.). 2012-11-02. [dostęp 2012-11-27].
- ↑ Interlocked.Increment Method. W: MSDN [on-line]. [dostęp 2012-11-27].
- ↑ Package java.util.concurrent.atomic. [dostęp 2012-11-27].
Bibliografia [edytuj]
- Maurice Herlihy. Wait-free synchronization. „ACM Trans. Program. Lang. Syst.”. 13 (1), s. 124–149, styczeń 1991. doi:10.1145/114005.102808 (ang.). [dostęp 2012-11-24].
