Fetch-and-add (pobierz i dodaj) – 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.
Realizacja 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 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 C++ 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, bądź jako rozszerzenie kompilatora. Wraz z pojawieniem się C++11, pojawiły się standardowe mechanizmy ułatwiające korzystanie z wątków takie jak: atomic_fetch_add, atomic_fetch_add_explicit.
.NET Framework (C#) W bibliotece standardowej jest dostępna metoda Interlocked.Increment, która implementuje funkcjonalność fetch-and-add.
Java 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.
Zobacz też Compare-and-swap
Przypisy
Bibliografia
Kategoria:Obliczenia równoległe Kategoria:Programowanie równoległe