Fetch-and-add

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[1], bądź jako rozszerzenie kompilatora[2]. Wraz 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#)

W bibliotece standardowej jest dostępna metoda Interlocked.Increment[4], 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[5].

Zobacz też

Przypisy

  1. ↑ InterlockedIncrement function (Windows). [w:] MSDN [on-line]. [dostęp 2012-11-27].
  2. ↑ _InterlockedIncrement. [w:] MSDN [on-line]. [dostęp 2012-11-27].
  3. ↑ Atomic operations library. 2012-11-02. [dostęp 2012-11-27]. (ang.).
  4. ↑ Interlocked.Increment Method. [w:] MSDN [on-line]. [dostęp 2012-11-27].
  5. ↑ Package java.util.concurrent.atomic. [dostęp 2012-11-27].

Bibliografia